一、引言

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

[[255461]]

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

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

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

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

簡單介紹下實現(xiàn)流程：

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

大體流程如下圖所示：

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

2. 核心職責(zé)

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

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

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

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

(1) 距離服務(wù)

a. 直線距離

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

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

b. 步行距離

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

大體上分為兩個階段：

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

(2) 定位服務(wù)

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

a. 樸素匹配

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

b. 最小覆蓋矩形

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

c. 基于墨卡托投影倒排

墨卡托投影 

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

墨卡托坐標(biāo)

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

倒排索引 

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

正排索引：

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

• - 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)建出方格對應(yīng)的覆蓋門店的列表，即倒排索引

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

構(gòu)建倒排：

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

定位過程：

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

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

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

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

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

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

1. 新的問題

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



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



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

2. 優(yōu)化策略

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



• 索引后置、流量削峰



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

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

3. 優(yōu)化效果

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

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

四、總結(jié)

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

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

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

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