在整個服務過程中，京東到家基于LBS將消費者和線下商家聯(lián)系到一起，進而促成交易，為消費者提供便利，在這背后定位系統(tǒng)是如何為京東到家提供基礎的定位能力呢？本文從技術角度介紹了京東到家定位系統(tǒng)的演進過程以及遇到的問題。

定位系統(tǒng)是做什么的？

1、業(yè)務簡介

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

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

實現(xiàn)流程：

• 第一步，打開APP，手機可以通過內(nèi)置的GPS模塊獲取當前位置的經(jīng)緯度

• 第二步，首頁網(wǎng)關拿到當前位置的經(jīng)緯度去請求地址系統(tǒng)，由地址系統(tǒng)訪問相應的GIS服務得到POI信息并返回

• 第三步，首頁網(wǎng)關根據(jù)POI信息去請求定位系統(tǒng)，定位系統(tǒng)返回附近的門店列表以及距離信息

• 第四步，首頁網(wǎng)關補全門店的其他信息，比如評分、銷量、運費等，然后返回給APP端展示

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

2、核心職責

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

1）距離計算

計算兩個坐標點的距離，多數(shù)為門店坐標與用戶坐標之間的距離。

2）定位門店

得到用戶坐標附近的門店信息，門店的配送范圍多種多樣，用戶看到的為配送范圍覆蓋用戶坐標的門店。

架構演進過程

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

1、距離服務

1）直線距離

這里所說的直線距離，實際為球面距離。地球是一個規(guī)則的球體，球面上的兩個點，可以通過一系列的幾何公式推導得出一個距離公式，將兩個點的經(jīng)緯度代入公式即可算出球面距離。那么為什么要升級，直線距離存在怎樣的問題呢？如下圖所示：

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

2）步行距離

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

大體上分為兩個階段：

• 階段一，初始化階段

  初始化服務拉取近半年的訂單信息，使用訂單中的門店地址經(jīng)緯度和用戶收貨地址經(jīng)緯度結合GIS服務，計算出步行距離并初始化到距離信息庫。

• 階段二，自更新階段

  對于已下過訂單的老用戶請求步行距離時，可命中返回距離信息庫的步行距離；對于新用戶，在距離信息庫中不能命中，此時估算步行距離，使用直線距離乘以經(jīng)驗參數(shù)作為估算步行距離返回給用戶，新用戶繼續(xù)下單，距離服務實時的監(jiān)聽訂單系統(tǒng)的訂單消息，進一步豐富距離信息庫，此用戶再次請求距離時，距離服務即可命中庫中的步行距離；隨著用戶的不斷下單，距離服務實時訂閱訂單消息，實現(xiàn)自動更新、自我豐富。

2、定位服務

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

1）樸素匹配

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

2）最小覆蓋矩形

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

3）基于墨卡托投影倒排

A、墨卡托投影

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

B、墨卡托坐標

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

C、倒排索引

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

構建出每個門店覆蓋的方格列表，即正排索引。

• s1: B2,C2,D2,B3,C3,D3,B4,C4,D4

• s2: C1,D1,C2,D2

• s3: C0,D0,E0,C1,D1,E1,D2

依賴正排索引，構建出方格對應的覆蓋門店的列表，即倒排索引。

• C0: s3

• C1: s2, s3

• D2: s1, s2, s3

• ……

門店配送范圍的倒排索引構建過程如下：

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

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

• 服務節(jié)點：對外提供定位服務，本地內(nèi)存存儲全量倒排、門店基本信息，門店覆蓋范圍變更，節(jié)點需要重新構建對應的倒排信息，并且同步門店的基本信息

• 后臺web：處理門店的變更消息，構建對應正排索引，產(chǎn)生門店變更任務供服務節(jié)點使用

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

架構趨于穩(wěn)定，但隨著業(yè)務的發(fā)展，出現(xiàn)了一些新的問題。針對這些問題，系統(tǒng)做了進一步的優(yōu)化。

1）新的問題

A、定位精準度不足

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

B、瞬時流量影響服務穩(wěn)定性

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

C、JVM內(nèi)存暴漲

由于倒排索引存儲于服務節(jié)點的JVM內(nèi)存，門店不斷增加，JVM使用內(nèi)存越來越大，大內(nèi)存下GC時間也隨著服務器的運行不斷增加，YongGC時間過長，影響服務的響應時間，一旦發(fā)生OldGC服務將處于不可用的狀態(tài)，這個問題相當嚴重。

2）優(yōu)化策略

A、定位精準化，在定位過程中加入實時計算是否覆蓋模塊，過濾掉不覆蓋用戶坐標的門店。

B、索引后置、流量削峰

C、優(yōu)化架構，調(diào)整服務架構，新的架構如下圖所示：

3）優(yōu)化效果

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

• 不再需要大內(nèi)存機器支撐服務，節(jié)約了資源

• 不再需要定期手動GC，減少了人工運維的成本

• 服務性能更加平穩(wěn)，響應時間不再會出現(xiàn)較大波動

總結

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