名詞解釋

1. 背景

2. 現狀分析

     2.1 現行框架分析

     2.2 現行調用時序分析

     2.3 現存問題分析

     2.4 業務需求分析

     2.5 基于當前架構所做嘗試

3. 問題拆解

     3.1 調用數據漏斗分析

     3.2 GEOHASH點對距離計算誤差分析

     3.3 GEOHASH點對距離計算面臨的問題分析

4. 新架構演進之路

     4.1 新的整體架構

     4.2 新的調用時序

5. 上線驗證與總結

    5.1 上線前的數據準備

    5.2 上線后的數據驗證與總結

    5.3 核心監控數據展示

6. 后續思考

7. 作者簡介

8. 加入我們

名詞解釋：

        點對：包含起始和終止經緯度的一組需要進行距離計算的數據。

       有值率：一組距離計算的請求過來，能計算出多少距離值的比例，如某次請求需要計算60個點對的距離值，最終計算出54個點對的距離值，則有值率為90%。

1.背景

       達達集團作為業內領先的本地即時零售和配送平臺，每天都需要海量的距離計算來支撐業務的閉環，主要的距離計算場景分布在以下幾點：

1．騎士當前位置和門店位置的距離。

2．計算運費所需要的精確距離。

3．推薦訂單時，對門店，騎士，訂單收貨人位置之間距離的綜合估算。

4．派單時，對門店，騎士和訂單收貨人位置之間距離的精確計算。

5．客戶距離當前給定范圍內騎士的距離。

6．客戶距離當前可配送門店的距離。

       隨著業務量的迅速增長，以及業務方對距離計算的精確度和時效性的更高的要求，現有的計算模式，系統架構已經無法滿足每日距離計算的需求，改進迫在眉睫。

2. 現狀分析

2.1 現行框架分析

      各個業務方根據自己對距離計算的需求去請求地圖服務，而推薦訂單和派單時由于需要進行海量距離計算，故大部分請求根本就沒到地圖服務，一般都是自己內部采取某種方式計算了距離的估算值，具體的系統調用圖如下所示：

2.2 現行調用時序分析

具體的調用時序圖，如下所示：

2.3 現存問題分析

      從上面的系統調用圖和時序圖可以看出，當前的計算方式和系統架構存在以下問題：

1．距離計算數據并未沉淀下來，只是放在redis中。

2．僅憑redis無法支持十億，百億級別的海量距離計算邏輯。

3．過多的流量如果直接打到供應商，會造成過高的調用成本。

4．無法實現距離計算精度差異化的需求。

 2.4 業務需求分析

經過跟各個業務方的詳細需求了解，總結出需要實現以下距離計算的目標：

2.5 基于當前架構所做嘗試

以上兩點就是業務方對距離計算調用量的絕對大頭，解決這兩個問題，才能真正意義上說地圖服務收攏了業務方且支持海量距離計算的需求，于是對于第一點需求我們做了以下下嘗試：

以上邏輯很清晰，即多線程并發去請求供應商，獲得點對的距離計算的結果，然后組裝返回給業務方，但是這種模式有以下幾個問題：

對于以上需求第二點，我們拉取了部分業務數據做了如下大致的數據分析：

從圖表中的數據分析可以很明顯的看出，如果我們在業務中使用直線的1.4倍來作為推薦訂單的距離計算估值，則總有40%以上的直線距離計算值跟實際值之間有25%以上的誤差，這個是業務上無法接受的。

需求也明確了，瓶頸也知曉了，如何演進出高并發，高可用，低成本的海量距離計算的架構，成為擺在地圖服務上的一道巨大的坎。

3. 問題拆解

 3.1 調用數據漏斗分析

對于目標需求1中的應用場景，我們對點對進行了系統性的大數據分析，拆解之后發現了以下特征：

1，起始和終止點是一樣的點對，占總點對的25%左右，這部分點對的距離計算直接請求到地圖供應商的話，也是要計算QPS的，當然也會消耗請求時間。

2，起始和終止點的直線距離非常接近（如30米以內）和非常遠（如20公里以上）的點對占3-5%左右，這部分點對的距離計算可以直接在內存中用直線的距離來計算，因為超近距離的點對的步行或者是騎行計算的值就是點對的直線值，而超遠距離的點對事實上就是位置漂移帶來的噪點，因為達達集團的業務中，超過20公里的配送范圍幾乎不存在，故可以忽略。

3，同一次批量請求中，還存在完全一樣的點對，比如一次請求的80個點對中，有12個點對是完全重復了，故這12個點對可以完全不去請求供應商。這部分比例大概是15%左右。

4，余下的點對中，大概有40%的能命中緩存。

      所以通過對請求數據持續幾天的分析和拆解，我們得出了以下漏斗：

上圖非常清楚的看出，分析拆解之后發現，流量打到供應商的點對只有34%左右，如果在按照日均5億點對的流量計算，最終打到供應商的流量是1.7億左右，那么平均QPS能降低到1968，而單次接口的響應時間能平均降低到200ms以下，看上去拆解之后方案可行，而此方案要解決如下幾個問題：

1，超近或者是超遠的點對直接返回直線距離或者是直線距離乘以某個系數，這需要業務調用方同意。

2，現行機制下的緩存命中率只有40%，這個是偏低的，需要想辦法充實緩存點對，讓其命中率達到60%甚至是70%，而且這個機制希望是長久的，能持續保證其高命中率的。

3.2 GEOHASH點對距離計算誤差分析

 對于目標需求2中的應用場景，其實就是希望拿到兩個點對之間的能計算一個估算距離值，但是差距最好不能超過10%，且時間響應一定要控制在50ms以內。于是我們也進行了大數據分析與問題拆解，得出了以下結論：

1，分析顯示7位GEOHASH點對與實際距離計算的誤差在20%以內的比例約為82%

2，分析顯示8位GEOHASH點對與實際距離計算的誤差在20%以內的比例約為92%

 具體差異如下圖所示：

很顯然分析結果顯示以上的誤差率是完全達到業務方需求的，所以設計了先取8位GEOHASH點對的距離計算值，取不到的話再取7位GEOHASH點對的距離計算值的方案，這樣的話距離誤差在20%內的比例能中和到89%左右，如果有值率能達到92%以上，則對業務來說是完全能接受的。

3.3 GEOHASH點對距離計算面臨的問題分析

此GEOHASH的方案需要解決如下問題：

1，需要有海量的庫存GEOHASH點對數據保證超高命中率，如15億個GEOHASH點對。

2，響應時間要在50ms以內，意味著只能是直接查mysql或者是redis，顯然如果使用redis的話，至少要在一定時間內維護15億+的GEOHASH點對，這個至少需要800G的redis內存，硬件成本是無法接受的，剩下唯一一個選擇，即mysql，必須設計極簡的庫表結構來持久化GEOHASH點對，使得查詢時間控制在30ms以內。

4. 新架構演進之路

4.1 新的整體架構

基于以上對問題的分析和拆解，我們設計了新的以下的系統架構，具體如下圖所示：

存量點對清洗模塊：主要是對各個業務方自己埋點沉淀的數據和歷史上的訂單數據進行收集整理后放入指定的庫表，等待業務低谷時去調供應商計算出結果后寫GEOHASH庫和redis。

GEOHASH模塊：主要是提供七位，八位，八位七位混合的各種GEOHASH點對的查詢邏輯，以及將收集來的各類點對通過供應商計算出距離之后以GEOHASH值的方式持久化到mysql，設計了極簡的庫表結構，即三個字段，如下所示：

極簡的數據結構保證了當GEOHASH點對達到30億時，單次200個點對以內的查詢響應時間仍然能控制在30ms以內。

直線距離計算模塊：主要提供地球上任意兩個點對之間的直線距離，這個是有一個標準的數學公式，直接在內存中進行計算，不耗費供應商QPS，也幾乎不耗費計算時間，微秒內即可返回計算結果，同時提供各類超長，超近距離的埋點監控。

點對異步拾漏：主要是對所有打到供應商的流量中由于各種原因無法返回計算值的點對，如QPS超限，PV超限，或者是供應商計算失敗等這些原因導致該點對無法返回計算結果后，收集存入指定的庫表后放入指定的庫表，等待業務低谷時重新去調供應商計算出結果后寫入GEOHASH庫和redis。

共享緩存模式：即無論對于任何業務方的請求，所有的緩存只按照供應商-距離計算模式（步行/騎行/電動自行車）-點對的方式進行存儲，每一類緩存大家一起共用，避免各自為戰的情況。

業務低谷定時任務：就是對以上幾點中所有收集來的點對進行跑批，即在業務低谷期（晚上九點到第二天凌晨四點期間）將這些點對去請求供應商獲取相關的距離值后寫入GEOHASH表和redis。

4.2 新的調用時序

    根據以上整體的系統架構設計出了以下的調用時序圖：

5. 上線驗證與總結

5.1 上線前的數據準備

整體功能大概在2020年8月左右全面上線，上線之前做了如下幾個事情：

1，預熱了存量的點對大約7億，分別寫入了7位GEOHASH庫，8位GEOHASH庫和redis。

2，將最近半年內的存量即時配訂單數據進行了預熱。分別寫入了7位GEOHASH庫，8位GEOHASH庫和redis。

5.2 上線后的數據驗證與總結

上線后三天以內，監控到了以下數據：

1，派單業務調用的批量精準距離計算接口的日請求點對大概在6億左右，其中redis緩存命中率達到了45%左右，接口整體有值率達到了96%左右。接口平均響應時間控制在了80ms左右，且對供應商的請求QPS控制在了1000左右。

2，推薦訂單業務對GEOHASH點對距離值的調用達到了8億左右，其中7位GEOHASH查詢接口有值率達到了79%左右，8位GEOHASH的有值率達到了32%左右，先查詢8位，在查詢7位的有值率達到82%。接口平均響應時間控制在了25ms左右。

以上監控的數據，完全滿足了業務的需求，而事實上從線下反饋來看，派錯單和推薦不合理的訂單的反饋減少10%以上。

得益于完善的點對拾漏邏輯和存量數據清洗邏輯，各項統計KPI一直在正向上穩步前進，到2020年雙11時，推薦訂單業務當日調用達到37億點對，派單業務當日調用達到34億點對。

到了上線一年后的2021年8月份，在8月14號農歷七夕節，調用達到了歷史巔峰：

基礎數據的存儲和緩存也達到了歷史巔峰：

5.3 核心監控數據展示

具體的監控數據如下圖所示：

1，推薦訂單點對總數和命中率監控報表：

2，派單業務點對監控圖：

3，緩存數據各項監控圖：

由此可見在2021年的七夕節當天，整個地圖服務接收到的點對距離計算的總流量超過了90億次，而在當天，系統只出現了5次超時報警，請求到供應商的QPS當天平均只有2743，說明目前的系統完全能支撐日100億次的點對距離計算的請求，而且以極低的成本實現了該架構。

6. 后續思考

1，目前的調用峰值無限接近100億次，如果未來一兩年內業務量增長一倍，需要計算的點對會在300億以上，當前的架構是否能達到超高的有值率，超快的響應時間？

2，架構線上運行一年來未發生高可用問題，是否意味著在更大流量時進來時，高可用是否能頂的?。?/p>