一、引言

依托達(dá)達(dá)的高效配送和大量?jī)?yōu)秀零售合作伙伴，京東到家為消費(fèi)者提供生鮮蔬果、日用百貨、醫(yī)藥健康、鮮花蛋糕、個(gè)護(hù)美妝等海量商品 1 小時(shí)配送到家的極致服務(wù)體驗(yàn)，在整個(gè)服務(wù)過程中，京東到家基于LBS將消費(fèi)者和線下商家聯(lián)系到一起，進(jìn)而促成交易為消費(fèi)者提供便利，在這背后定位系統(tǒng)是如何為京東到家提供基礎(chǔ)的定位能力呢?本文從技術(shù)角度介紹了京東到家定位系統(tǒng)的演進(jìn)過程以及遇到的問題。

[[255461]]

二、定位系統(tǒng)是做什么的?

1. 業(yè)務(wù)簡(jiǎn)介

打開京東到家app，進(jìn)入首頁然后下拉，我們可以看到附近的店鋪模塊，如下圖所示：

這個(gè)“附近”模塊是典型的定位系統(tǒng)的應(yīng)用，圖中藍(lán)色方框區(qū)域內(nèi)容為當(dāng)前坐標(biāo)的POI名稱，紅色方框區(qū)域內(nèi)容為當(dāng)前坐標(biāo)附近的門店信息，紅色橢圓區(qū)域內(nèi)容為當(dāng)前坐標(biāo)與門店之間的距離。

簡(jiǎn)單介紹下實(shí)現(xiàn)流程：

• 第一步，打開app,手機(jī)可以通過內(nèi)置的GPS模塊獲取當(dāng)前位置的經(jīng)緯度;
• 第二步，首頁網(wǎng)關(guān)拿到當(dāng)前位置的經(jīng)緯度去請(qǐng)求地址系統(tǒng)，由地址系統(tǒng)訪問相應(yīng)的GIS服務(wù)得到POI信息并返回;
• 第三步，首頁網(wǎng)關(guān)根據(jù)POI信息去請(qǐng)求定位系統(tǒng)，定位系統(tǒng)返回附近的門店列表以及距離信息;
• 第四步，首頁網(wǎng)關(guān)補(bǔ)全門店的其他信息，比如評(píng)分、銷量、運(yùn)費(fèi)等等信息，然后返回給app端展示。

大體流程如下圖所示：

除了這個(gè)典型的應(yīng)用外，到家的很多系統(tǒng)都依賴定位系統(tǒng)，比如多門店的搜索、運(yùn)費(fèi)的計(jì)算、提單時(shí)的超區(qū)校驗(yàn)、訂單時(shí)效的計(jì)算……統(tǒng)計(jì)下來有50+的系統(tǒng)，這些系統(tǒng)幾乎涵蓋了用戶的整個(gè)購(gòu)物過程，仔細(xì)想想也是情理之中，到家的許多業(yè)務(wù)都是基于位置展開的，這也正是o2o電商和傳統(tǒng)電商的一個(gè)重要區(qū)別。

2. 核心職責(zé)

從眾多的業(yè)務(wù)場(chǎng)景歸納下來，定位系統(tǒng)有兩個(gè)核心職責(zé)，如下圖所示：

• 距離計(jì)算：計(jì)算兩個(gè)坐標(biāo)點(diǎn)的距離，多數(shù)為門店坐標(biāo)與用戶坐標(biāo)之間的距離
• 定位門店：得到用戶坐標(biāo)附近的門店信息，門店的配送范圍多種多樣，用戶看到的為配送范圍覆蓋用戶坐標(biāo)的門店

3. 架構(gòu)演進(jìn)過程

依據(jù)職責(zé)不同定位系統(tǒng)劃分為距離服務(wù)和定位服務(wù)，下面分開介紹這兩個(gè)服務(wù)的演進(jìn)過程。

(1) 距離服務(wù)

a. 直線距離

這是所說的直線距離，實(shí)際為球面距離，我們認(rèn)為地球是一個(gè)規(guī)則的球體，球面上的兩個(gè)點(diǎn)，可以通過一系列的幾何公式推導(dǎo)得出一個(gè)距離公式，將兩個(gè)點(diǎn)的經(jīng)緯度代入公式即可算出球面距離，這里就不展開了可自行搜索相關(guān)資料。那么我們?yōu)槭裁匆?jí)，直線距離存在怎樣的問題呢?如下圖所示，

圖中，起點(diǎn)到終點(diǎn)之間直線距離為390米，由于兩點(diǎn)之間隔著河和橋，實(shí)際的步行距離達(dá)到了1766米，實(shí)際的步行距離為直線距離的四倍之多，類似這種情況下展示給用戶直線距離，存在一定的不合理，影響用戶的體驗(yàn);另一方面，由于達(dá)達(dá)側(cè)計(jì)算運(yùn)費(fèi)使用的是步行距離，到家側(cè)使用直線距離，兩邊測(cè)算的距離不一致，無形中也給到家平臺(tái)帶來一定的損失，基于以上的原因，距離服務(wù)升級(jí)為使用步行距離。

b. 步行距離

計(jì)算兩點(diǎn)之間的步行距離，由于涉及到道路的規(guī)劃、距離的測(cè)算等等元素，自己實(shí)現(xiàn)不現(xiàn)實(shí)，我們采用的是使用GIS服務(wù)計(jì)算步行距離，但距離服務(wù)作為到家的一個(gè)基礎(chǔ)的服務(wù)，同步請(qǐng)求GIS服務(wù)顯然不能滿足我們對(duì)性能的要求，因此也催生了我們現(xiàn)在的方案，如下圖所示：

大體上分為兩個(gè)階段：

• 階段一，初始化階段，初始化服務(wù)拉取近半年的訂單信息，使用訂單中的門店地址經(jīng)緯度和用戶收貨地址經(jīng)緯度結(jié)合GIS服務(wù)，計(jì)算出步行距離并初始化到距離信息庫(kù)。
• 階段二，自更新階段，對(duì)于已下過訂單的老用戶請(qǐng)求步行距離時(shí)，可命中返回距離信息庫(kù)的步行距離;而對(duì)于新用戶，在距離信息庫(kù)中不能命中，此時(shí)我們采用的是估算步行距離，使用直線距離乘以經(jīng)驗(yàn)參數(shù)作為估算步行距離返回給用戶，新用戶繼續(xù)下單，距離服務(wù)實(shí)時(shí)的監(jiān)聽訂單系統(tǒng)的訂單消息，進(jìn)一步的豐富距離信息庫(kù)，此用戶再次請(qǐng)求距離時(shí)，距離服務(wù)即可命中庫(kù)中的步行距離;隨著用戶的不斷下單，距離服務(wù)實(shí)時(shí)訂閱訂單消息，實(shí)現(xiàn)了自動(dòng)更新、自我豐富。

(2) 定位服務(wù)

定位服務(wù)的演進(jìn)基本分為三個(gè)階段，如下圖所示：

a. 樸素匹配

到家發(fā)展初期，只有少數(shù)幾個(gè)門店，一一列舉出這些門店，判斷配送范圍是否覆蓋用戶坐標(biāo)，從而匹配出覆蓋門店，但隨著門店的增加，此方案不再適用進(jìn)入到下一階段。

b. 最小覆蓋矩形

計(jì)算門店的配送范圍的最小覆蓋矩形，將所有門店的最小覆蓋矩形坐標(biāo)持久化到數(shù)據(jù)庫(kù)中，通過sql語句方式篩選出覆蓋用戶坐標(biāo)的門店，此方案支撐了到家一段時(shí)間的業(yè)務(wù)發(fā)展，隨著用戶量的增加，到家訪問量也不斷增長(zhǎng)，通過數(shù)據(jù)庫(kù)查詢的方式逐漸不能滿足我們對(duì)性能的要求，進(jìn)而開始繼續(xù)演化。

c. 基于墨卡托投影倒排

墨卡托投影 

墨卡托投影是正軸等角圓柱投影，假設(shè)一個(gè)與地軸方向一致的圓柱切或割于地球，按等角條件，將經(jīng)緯網(wǎng)投影到圓柱面上，將圓柱面展為平面后，即得本投影。經(jīng)過墨卡托投影后的經(jīng)線是均勻分布的，緯線是垂直于經(jīng)線的一組平行直線，也就是說經(jīng)過投影以后我們把球面轉(zhuǎn)化成了平面。

墨卡托坐標(biāo)

由上述公式經(jīng)度λ、緯度θ對(duì)應(yīng)的墨卡托坐標(biāo)就是(x\*R, y\*R)，其中R為地球半徑。通過墨卡托投影，將坐標(biāo)系轉(zhuǎn)換為平面坐標(biāo)系，由此，可以依照某種規(guī)則將我國(guó)所覆蓋的區(qū)域分成若干大小相同的正方形區(qū)域進(jìn)行標(biāo)記編號(hào),這些方格就是我們構(gòu)建倒排索引的基礎(chǔ)。

倒排索引 

假設(shè)現(xiàn)在有三個(gè)門店s1、s2、s3,三個(gè)門店有不同形狀的配送范圍，每個(gè)方格都有自己的編號(hào)，如上圖所示。

正排索引：

構(gòu)建出每個(gè)門店覆蓋的方格列表，即正排索引

• - s1: B2,C2,D2,B3,C3,D3,B4,C4,D4
• - s2: C1,D1,C2,D2
• - s3: C0,D0,E0,C1,D1,E1,D2

倒排索引：

依賴正排索引，構(gòu)建出方格對(duì)應(yīng)的覆蓋門店的列表，即倒排索引

• - C0: s3
• - C1: s2, s3
• - D2: s1, s2, s3
• - ……

構(gòu)建倒排：

門店配送范圍的倒排索引構(gòu)建過程如下：

定位過程：

依賴于倒排索引，定位門店的流程如下：

(3) 定位服務(wù)架構(gòu)

采用倒排索引方案實(shí)現(xiàn)定位服務(wù)，極大的提升了定位服務(wù)的性能，系統(tǒng)不再是業(yè)務(wù)發(fā)展的瓶頸，架構(gòu)圖如下所示：

• 服務(wù)節(jié)點(diǎn)：對(duì)外提供定位服務(wù)，本地內(nèi)存存儲(chǔ)全量倒排、門店基本信息，門店覆蓋范圍變更，節(jié)點(diǎn)需要重新構(gòu)建對(duì)應(yīng)的倒排信息，并且同步門店的基本信息。
• 后臺(tái)web：處理門店變更消息，構(gòu)建對(duì)應(yīng)正排索引，產(chǎn)生門店變更任務(wù)供服務(wù)節(jié)點(diǎn)使用。

三、問題以及優(yōu)化

架構(gòu)趨于穩(wěn)定，但隨著業(yè)務(wù)的發(fā)展，還是出現(xiàn)了一些新的問題，針對(duì)這些問題，我們也做了進(jìn)一步的優(yōu)化。

1. 新的問題

• 定位精準(zhǔn)度不足，如下圖所示，雖然門店的配送范圍覆蓋了方格，但是紅色標(biāo)記區(qū)域?qū)嶋H不在門店的配送范圍內(nèi)，實(shí)際的運(yùn)營(yíng)過程中出現(xiàn)了不少類似的問題，給商家和用戶造成了困擾。



• 瞬時(shí)流量影響服務(wù)穩(wěn)定性，平臺(tái)存在一些配送范圍特別大的門店，比如鮮花門店的配送范圍是覆蓋整個(gè)城市，由于倒排索引的構(gòu)建在每個(gè)服務(wù)節(jié)點(diǎn)都會(huì)進(jìn)行，一旦這種門店上下線，服務(wù)節(jié)點(diǎn)性能會(huì)產(chǎn)生較大的波動(dòng)，造成調(diào)用方超時(shí)。



• JVM內(nèi)存暴漲，由于倒排索引存儲(chǔ)于服務(wù)節(jié)點(diǎn)的JVM內(nèi)存，門店不斷增加，jvm使用內(nèi)存越來越大，達(dá)到了22G+,大內(nèi)存下GC時(shí)間也隨著服務(wù)器的運(yùn)行不斷增加，yongGC時(shí)間過長(zhǎng)，影響了服務(wù)的響應(yīng)時(shí)間，一旦發(fā)生oldGC服務(wù)將處于不可用的狀態(tài)，這個(gè)問題相當(dāng)嚴(yán)重。

2. 優(yōu)化策略

• 定位精準(zhǔn)化，在定位過程中加入實(shí)時(shí)計(jì)算是否覆蓋模塊，過濾掉不覆蓋用戶坐標(biāo)的門店。



• 索引后置、流量削峰



• 優(yōu)化架構(gòu)

服務(wù)架構(gòu)也做了一些調(diào)整，新的架構(gòu)如圖所示：

3. 優(yōu)化效果

經(jīng)過這次優(yōu)化以后，問題得到了很好的解決，數(shù)據(jù)對(duì)比如下圖所示，值得一提的是，服務(wù)的平均性能由原來的2ms增加到了4ms，雖然響應(yīng)時(shí)間有所增加，但增加的幅度完全在業(yè)務(wù)的可接受范圍內(nèi)，帶來的好處卻是相當(dāng)明顯的。

• 不再需要大內(nèi)存機(jī)器支撐服務(wù)，節(jié)約了資源
• 不再需要定期手動(dòng)GC，減少了人工運(yùn)維的成本
• 服務(wù)性能更加平穩(wěn)，響應(yīng)時(shí)間不再會(huì)出現(xiàn)較大波動(dòng)

四、總結(jié)

定位系統(tǒng)作為京東到家的基礎(chǔ)服務(wù)，為到家提供了核心的定位以及距離服務(wù)，隨著到家平臺(tái)的不斷發(fā)展，定位系統(tǒng)也隨著不斷的演進(jìn)優(yōu)化，每一次演進(jìn)優(yōu)化都朝著提供穩(wěn)定高可用服務(wù)的目標(biāo)走出堅(jiān)實(shí)的一步，為到家業(yè)務(wù)的飛速發(fā)展提供強(qiáng)有力的保障。

作者簡(jiǎn)介：趙帥，軟件工程師，就職于京東到家后臺(tái)研發(fā)部，負(fù)責(zé)交易，售后、定位，api網(wǎng)關(guān)等系統(tǒng)。

【本文來自51CTO專欄作者張開濤的微信公眾號(hào)(開濤的博客)，公眾號(hào)id: kaitao-1234567】 

戳這里，看該作者更多好文