京東到家的LBS定位系統架構是如何演進的
一、引言
依托達達的高效配送和大量優秀零售合作伙伴，京東到家為消費者提供生鮮蔬果、日用百貨、醫藥健康、鮮花蛋糕、個護美妝等海量商品 1 小時配送到家的極致服務體驗，在整個服務過程中，京東到家基于LBS將消費者和線下商家聯系到一起，進而促成交易為消費者提供便利，在這背后定位系統是如何為京東到家提供基礎的定位能力呢?本文從技術角度介紹了京東到家定位系統的演進過程以及遇到的問題。
二、定位系統是做什么的?
1. 業務簡介
打開京東到家app，進入首頁然后下拉，我們可以看到附近的店鋪模塊，如下圖所示：
這個“附近”模塊是典型的定位系統的應用，圖中藍色方框區域內容為當前坐標的POI名稱，紅色方框區域內容為當前坐標附近的門店信息，紅色橢圓區域內容為當前坐標與門店之間的距離。
簡單介紹下實現流程：
- 第一步，打開app,手機可以通過內置的GPS模塊獲取當前位置的經緯度;
- 第二步，首頁網關拿到當前位置的經緯度去請求地址系統，由地址系統訪問相應的GIS服務得到POI信息并返回;
- 第三步，首頁網關根據POI信息去請求定位系統，定位系統返回附近的門店列表以及距離信息;
- 第四步，首頁網關補全門店的其他信息，比如評分、銷量、運費等等信息，然后返回給app端展示。
大體流程如下圖所示：
除了這個典型的應用外，到家的很多系統都依賴定位系統，比如多門店的搜索、運費的計算、提單時的超區校驗、訂單時效的計算……統計下來有50+的系統，這些系統幾乎涵蓋了用戶的整個購物過程，仔細想想也是情理之中，到家的許多業務都是基于位置展開的，這也正是o2o電商和傳統電商的一個重要區別。
2. 核心職責
從眾多的業務場景歸納下來，定位系統有兩個核心職責，如下圖所示：
- 距離計算：計算兩個坐標點的距離，多數為門店坐標與用戶坐標之間的距離
- 定位門店：得到用戶坐標附近的門店信息，門店的配送范圍多種多樣，用戶看到的為配送范圍覆蓋用戶坐標的門店
3. 架構演進過程
依據職責不同定位系統劃分為距離服務和定位服務，下面分開介紹這兩個服務的演進過程。
(1) 距離服務
a. 直線距離
這是所說的直線距離，實際為球面距離，我們認為地球是一個規則的球體，球面上的兩個點，可以通過一系列的幾何公式推導得出一個距離公式，將兩個點的經緯度代入公式即可算出球面距離，這里就不展開了可自行搜索相關資料。那么我們為什么要升級，直線距離存在怎樣的問題呢?如下圖所示，
圖中，起點到終點之間直線距離為390米，由于兩點之間隔著河和橋，實際的步行距離達到了1766米，實際的步行距離為直線距離的四倍之多，類似這種情況下展示給用戶直線距離，存在一定的不合理，影響用戶的體驗;另一方面，由于達達側計算運費使用的是步行距離，到家側使用直線距離，兩邊測算的距離不一致，無形中也給到家平臺帶來一定的損失，基于以上的原因，距離服務升級為使用步行距離。
b. 步行距離
計算兩點之間的步行距離，由于涉及到道路的規劃、距離的測算等等元素，自己實現不現實，我們采用的是使用GIS服務計算步行距離，但距離服務作為到家的一個基礎的服務，同步請求GIS服務顯然不能滿足我們對性能的要求，因此也催生了我們現在的方案，如下圖所示：
大體上分為兩個階段：
- 階段一，初始化階段，初始化服務拉取近半年的訂單信息，使用訂單中的門店地址經緯度和用戶收貨地址經緯度結合GIS服務，計算出步行距離并初始化到距離信息庫。
- 階段二，自更新階段，對于已下過訂單的老用戶請求步行距離時，可命中返回距離信息庫的步行距離;而對于新用戶，在距離信息庫中不能命中，此時我們采用的是估算步行距離，使用直線距離乘以經驗參數作為估算步行距離返回給用戶，新用戶繼續下單，距離服務實時的監聽訂單系統的訂單消息，進一步的豐富距離信息庫，此用戶再次請求距離時，距離服務即可命中庫中的步行距離;隨著用戶的不斷下單，距離服務實時訂閱訂單消息，實現了自動更新、自我豐富。
(2) 定位服務
定位服務的演進基本分為三個階段，如下圖所示：
a. 樸素匹配
到家發展初期，只有少數幾個門店，一一列舉出這些門店，判斷配送范圍是否覆蓋用戶坐標，從而匹配出覆蓋門店，但隨著門店的增加，此方案不再適用進入到下一階段。
b. 最小覆蓋矩形
計算門店的配送范圍的最小覆蓋矩形，將所有門店的最小覆蓋矩形坐標持久化到數據庫中，通過sql語句方式篩選出覆蓋用戶坐標的門店，此方案支撐了到家一段時間的業務發展，隨著用戶量的增加，到家訪問量也不斷增長，通過數據庫查詢的方式逐漸不能滿足我們對性能的要求，進而開始繼續演化。
c. 基于墨卡托投影倒排
墨卡托投影
墨卡托投影是正軸等角圓柱投影，假設一個與地軸方向一致的圓柱切或割于地球，按等角條件，將經緯網投影到圓柱面上，將圓柱面展為平面后，即得本投影。經過墨卡托投影后的經線是均勻分布的，緯線是垂直于經線的一組平行直線，也就是說經過投影以后我們把球面轉化成了平面。
墨卡托坐標
由上述公式經度λ、緯度θ對應的墨卡托坐標就是(x\*R, y\*R)，其中R為地球半徑。通過墨卡托投影，將坐標系轉換為平面坐標系，由此，可以依照某種規則將我國所覆蓋的區域分成若干大小相同的正方形區域進行標記編號,這些方格就是我們構建倒排索引的基礎。
倒排索引
假設現在有三個門店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
- - ……
構建倒排：
門店配送范圍的倒排索引構建過程如下：
定位過程：
依賴于倒排索引，定位門店的流程如下：
(3) 定位服務架構
采用倒排索引方案實現定位服務，極大的提升了定位服務的性能，系統不再是業務發展的瓶頸，架構圖如下所示：
- 服務節點：對外提供定位服務，本地內存存儲全量倒排、門店基本信息，門店覆蓋范圍變更，節點需要重新構建對應的倒排信息，并且同步門店的基本信息。
- 后臺web：處理門店變更消息，構建對應正排索引，產生門店變更任務供服務節點使用。
三、問題以及優化
架構趨于穩定，但隨著業務的發展，還是出現了一些新的問題，針對這些問題，我們也做了進一步的優化。
1. 新的問題
- 定位精準度不足，如下圖所示，雖然門店的配送范圍覆蓋了方格，但是紅色標記區域實際不在門店的配送范圍內，實際的運營過程中出現了不少類似的問題，給商家和用戶造成了困擾。
- 瞬時流量影響服務穩定性，平臺存在一些配送范圍特別大的門店，比如鮮花門店的配送范圍是覆蓋整個城市，由于倒排索引的構建在每個服務節點都會進行，一旦這種門店上下線，服務節點性能會產生較大的波動，造成調用方超時。
- JVM內存暴漲，由于倒排索引存儲于服務節點的JVM內存，門店不斷增加，jvm使用內存越來越大，達到了22G+,大內存下GC時間也隨著服務器的運行不斷增加，yongGC時間過長，影響了服務的響應時間，一旦發生oldGC服務將處于不可用的狀態，這個問題相當嚴重。
2. 優化策略
- 定位精準化，在定位過程中加入實時計算是否覆蓋模塊，過濾掉不覆蓋用戶坐標的門店。
- 索引后置、流量削峰
- 優化架構
服務架構也做了一些調整，新的架構如圖所示：
3. 優化效果
經過這次優化以后，問題得到了很好的解決，數據對比如下圖所示，值得一提的是，服務的平均性能由原來的2ms增加到了4ms，雖然響應時間有所增加，但增加的幅度完全在業務的可接受范圍內，帶來的好處卻是相當明顯的。
- 不再需要大內存機器支撐服務，節約了資源
- 不再需要定期手動GC，減少了人工運維的成本
- 服務性能更加平穩，響應時間不再會出現較大波動
四、總結
定位系統作為京東到家的基礎服務，為到家提供了核心的定位以及距離服務，隨著到家平臺的不斷發展，定位系統也隨著不斷的演進優化，每一次演進優化都朝著提供穩定高可用服務的目標走出堅實的一步，為到家業務的飛速發展提供強有力的保障。
作者簡介：趙帥，軟件工程師，就職于京東到家后臺研發部，負責交易，售后、定位，api網關等系統。
【本文來自51CTO專欄作者張開濤的微信公眾號(開濤的博客)，公眾號id: kaitao-1234567】
