名詞解釋

1. 背景

2. 現(xiàn)狀分析

     2.1 現(xiàn)行框架分析

     2.2 現(xiàn)行調(diào)用時(shí)序分析

     2.3 現(xiàn)存問題分析

     2.4 業(yè)務(wù)需求分析

     2.5 基于當(dāng)前架構(gòu)所做嘗試

3. 問題拆解

     3.1 調(diào)用數(shù)據(jù)漏斗分析

     3.2 GEOHASH點(diǎn)對(duì)距離計(jì)算誤差分析

     3.3 GEOHASH點(diǎn)對(duì)距離計(jì)算面臨的問題分析

4. 新架構(gòu)演進(jìn)之路

     4.1 新的整體架構(gòu)

     4.2 新的調(diào)用時(shí)序

5. 上線驗(yàn)證與總結(jié)

    5.1 上線前的數(shù)據(jù)準(zhǔn)備

    5.2 上線后的數(shù)據(jù)驗(yàn)證與總結(jié)

    5.3 核心監(jiān)控?cái)?shù)據(jù)展示

6. 后續(xù)思考

7. 作者簡(jiǎn)介

8. 加入我們

名詞解釋：

        點(diǎn)對(duì)：包含起始和終止經(jīng)緯度的一組需要進(jìn)行距離計(jì)算的數(shù)據(jù)。

       有值率：一組距離計(jì)算的請(qǐng)求過來，能計(jì)算出多少距離值的比例，如某次請(qǐng)求需要計(jì)算60個(gè)點(diǎn)對(duì)的距離值，最終計(jì)算出54個(gè)點(diǎn)對(duì)的距離值，則有值率為90%。

1.背景

       達(dá)達(dá)集團(tuán)作為業(yè)內(nèi)領(lǐng)先的本地即時(shí)零售和配送平臺(tái)，每天都需要海量的距離計(jì)算來支撐業(yè)務(wù)的閉環(huán)，主要的距離計(jì)算場(chǎng)景分布在以下幾點(diǎn)：

1．騎士當(dāng)前位置和門店位置的距離。

2．計(jì)算運(yùn)費(fèi)所需要的精確距離。

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

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

5．客戶距離當(dāng)前給定范圍內(nèi)騎士的距離。

6．客戶距離當(dāng)前可配送門店的距離。

       隨著業(yè)務(wù)量的迅速增長，以及業(yè)務(wù)方對(duì)距離計(jì)算的精確度和時(shí)效性的更高的要求，現(xiàn)有的計(jì)算模式，系統(tǒng)架構(gòu)已經(jīng)無法滿足每日距離計(jì)算的需求，改進(jìn)迫在眉睫。

2. 現(xiàn)狀分析

2.1 現(xiàn)行框架分析

      各個(gè)業(yè)務(wù)方根據(jù)自己對(duì)距離計(jì)算的需求去請(qǐng)求地圖服務(wù)，而推薦訂單和派單時(shí)由于需要進(jìn)行海量距離計(jì)算，故大部分請(qǐng)求根本就沒到地圖服務(wù)，一般都是自己內(nèi)部采取某種方式計(jì)算了距離的估算值，具體的系統(tǒng)調(diào)用圖如下所示：

2.2 現(xiàn)行調(diào)用時(shí)序分析

具體的調(diào)用時(shí)序圖，如下所示：

2.3 現(xiàn)存問題分析

      從上面的系統(tǒng)調(diào)用圖和時(shí)序圖可以看出，當(dāng)前的計(jì)算方式和系統(tǒng)架構(gòu)存在以下問題：

1．距離計(jì)算數(shù)據(jù)并未沉淀下來，只是放在redis中。

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

3．過多的流量如果直接打到供應(yīng)商，會(huì)造成過高的調(diào)用成本。

4．無法實(shí)現(xiàn)距離計(jì)算精度差異化的需求。

 2.4 業(yè)務(wù)需求分析

經(jīng)過跟各個(gè)業(yè)務(wù)方的詳細(xì)需求了解，總結(jié)出需要實(shí)現(xiàn)以下距離計(jì)算的目標(biāo)：

2.5 基于當(dāng)前架構(gòu)所做嘗試

以上兩點(diǎn)就是業(yè)務(wù)方對(duì)距離計(jì)算調(diào)用量的絕對(duì)大頭，解決這兩個(gè)問題，才能真正意義上說地圖服務(wù)收攏了業(yè)務(wù)方且支持海量距離計(jì)算的需求，于是對(duì)于第一點(diǎn)需求我們做了以下下嘗試：

以上邏輯很清晰，即多線程并發(fā)去請(qǐng)求供應(yīng)商，獲得點(diǎn)對(duì)的距離計(jì)算的結(jié)果，然后組裝返回給業(yè)務(wù)方，但是這種模式有以下幾個(gè)問題：

對(duì)于以上需求第二點(diǎn)，我們拉取了部分業(yè)務(wù)數(shù)據(jù)做了如下大致的數(shù)據(jù)分析：

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

需求也明確了，瓶頸也知曉了，如何演進(jìn)出高并發(fā)，高可用，低成本的海量距離計(jì)算的架構(gòu)，成為擺在地圖服務(wù)上的一道巨大的坎。

3. 問題拆解

 3.1 調(diào)用數(shù)據(jù)漏斗分析

對(duì)于目標(biāo)需求1中的應(yīng)用場(chǎng)景，我們對(duì)點(diǎn)對(duì)進(jìn)行了系統(tǒng)性的大數(shù)據(jù)分析，拆解之后發(fā)現(xiàn)了以下特征：

1，起始和終止點(diǎn)是一樣的點(diǎn)對(duì)，占總點(diǎn)對(duì)的25%左右，這部分點(diǎn)對(duì)的距離計(jì)算直接請(qǐng)求到地圖供應(yīng)商的話，也是要計(jì)算QPS的，當(dāng)然也會(huì)消耗請(qǐng)求時(shí)間。

2，起始和終止點(diǎn)的直線距離非常接近（如30米以內(nèi)）和非常遠(yuǎn)（如20公里以上）的點(diǎn)對(duì)占3-5%左右，這部分點(diǎn)對(duì)的距離計(jì)算可以直接在內(nèi)存中用直線的距離來計(jì)算，因?yàn)槌嚯x的點(diǎn)對(duì)的步行或者是騎行計(jì)算的值就是點(diǎn)對(duì)的直線值，而超遠(yuǎn)距離的點(diǎn)對(duì)事實(shí)上就是位置漂移帶來的噪點(diǎn)，因?yàn)檫_(dá)達(dá)集團(tuán)的業(yè)務(wù)中，超過20公里的配送范圍幾乎不存在，故可以忽略。

3，同一次批量請(qǐng)求中，還存在完全一樣的點(diǎn)對(duì)，比如一次請(qǐng)求的80個(gè)點(diǎn)對(duì)中，有12個(gè)點(diǎn)對(duì)是完全重復(fù)了，故這12個(gè)點(diǎn)對(duì)可以完全不去請(qǐng)求供應(yīng)商。這部分比例大概是15%左右。

4，余下的點(diǎn)對(duì)中，大概有40%的能命中緩存。

      所以通過對(duì)請(qǐng)求數(shù)據(jù)持續(xù)幾天的分析和拆解，我們得出了以下漏斗：

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

1，超近或者是超遠(yuǎn)的點(diǎn)對(duì)直接返回直線距離或者是直線距離乘以某個(gè)系數(shù)，這需要業(yè)務(wù)調(diào)用方同意。

2，現(xiàn)行機(jī)制下的緩存命中率只有40%，這個(gè)是偏低的，需要想辦法充實(shí)緩存點(diǎn)對(duì)，讓其命中率達(dá)到60%甚至是70%，而且這個(gè)機(jī)制希望是長久的，能持續(xù)保證其高命中率的。

3.2 GEOHASH點(diǎn)對(duì)距離計(jì)算誤差分析

 對(duì)于目標(biāo)需求2中的應(yīng)用場(chǎng)景，其實(shí)就是希望拿到兩個(gè)點(diǎn)對(duì)之間的能計(jì)算一個(gè)估算距離值，但是差距最好不能超過10%，且時(shí)間響應(yīng)一定要控制在50ms以內(nèi)。于是我們也進(jìn)行了大數(shù)據(jù)分析與問題拆解，得出了以下結(jié)論：

1，分析顯示7位GEOHASH點(diǎn)對(duì)與實(shí)際距離計(jì)算的誤差在20%以內(nèi)的比例約為82%

2，分析顯示8位GEOHASH點(diǎn)對(duì)與實(shí)際距離計(jì)算的誤差在20%以內(nèi)的比例約為92%

 具體差異如下圖所示：

很顯然分析結(jié)果顯示以上的誤差率是完全達(dá)到業(yè)務(wù)方需求的，所以設(shè)計(jì)了先取8位GEOHASH點(diǎn)對(duì)的距離計(jì)算值，取不到的話再取7位GEOHASH點(diǎn)對(duì)的距離計(jì)算值的方案，這樣的話距離誤差在20%內(nèi)的比例能中和到89%左右，如果有值率能達(dá)到92%以上，則對(duì)業(yè)務(wù)來說是完全能接受的。

3.3 GEOHASH點(diǎn)對(duì)距離計(jì)算面臨的問題分析

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

1，需要有海量的庫存GEOHASH點(diǎn)對(duì)數(shù)據(jù)保證超高命中率，如15億個(gè)GEOHASH點(diǎn)對(duì)。

2，響應(yīng)時(shí)間要在50ms以內(nèi)，意味著只能是直接查mysql或者是redis，顯然如果使用redis的話，至少要在一定時(shí)間內(nèi)維護(hù)15億+的GEOHASH點(diǎn)對(duì)，這個(gè)至少需要800G的redis內(nèi)存，硬件成本是無法接受的，剩下唯一一個(gè)選擇，即mysql，必須設(shè)計(jì)極簡(jiǎn)的庫表結(jié)構(gòu)來持久化GEOHASH點(diǎn)對(duì)，使得查詢時(shí)間控制在30ms以內(nèi)。

4. 新架構(gòu)演進(jìn)之路

4.1 新的整體架構(gòu)

基于以上對(duì)問題的分析和拆解，我們?cè)O(shè)計(jì)了新的以下的系統(tǒng)架構(gòu)，具體如下圖所示：

存量點(diǎn)對(duì)清洗模塊：主要是對(duì)各個(gè)業(yè)務(wù)方自己埋點(diǎn)沉淀的數(shù)據(jù)和歷史上的訂單數(shù)據(jù)進(jìn)行收集整理后放入指定的庫表，等待業(yè)務(wù)低谷時(shí)去調(diào)供應(yīng)商計(jì)算出結(jié)果后寫GEOHASH庫和redis。

GEOHASH模塊：主要是提供七位，八位，八位七位混合的各種GEOHASH點(diǎn)對(duì)的查詢邏輯，以及將收集來的各類點(diǎn)對(duì)通過供應(yīng)商計(jì)算出距離之后以GEOHASH值的方式持久化到mysql，設(shè)計(jì)了極簡(jiǎn)的庫表結(jié)構(gòu)，即三個(gè)字段，如下所示：

極簡(jiǎn)的數(shù)據(jù)結(jié)構(gòu)保證了當(dāng)GEOHASH點(diǎn)對(duì)達(dá)到30億時(shí)，單次200個(gè)點(diǎn)對(duì)以內(nèi)的查詢響應(yīng)時(shí)間仍然能控制在30ms以內(nèi)。

直線距離計(jì)算模塊：主要提供地球上任意兩個(gè)點(diǎn)對(duì)之間的直線距離，這個(gè)是有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)公式，直接在內(nèi)存中進(jìn)行計(jì)算，不耗費(fèi)供應(yīng)商QPS，也幾乎不耗費(fèi)計(jì)算時(shí)間，微秒內(nèi)即可返回計(jì)算結(jié)果，同時(shí)提供各類超長，超近距離的埋點(diǎn)監(jiān)控。

點(diǎn)對(duì)異步拾漏：主要是對(duì)所有打到供應(yīng)商的流量中由于各種原因無法返回計(jì)算值的點(diǎn)對(duì)，如QPS超限，PV超限，或者是供應(yīng)商計(jì)算失敗等這些原因?qū)е略擖c(diǎn)對(duì)無法返回計(jì)算結(jié)果后，收集存入指定的庫表后放入指定的庫表，等待業(yè)務(wù)低谷時(shí)重新去調(diào)供應(yīng)商計(jì)算出結(jié)果后寫入GEOHASH庫和redis。

共享緩存模式：即無論對(duì)于任何業(yè)務(wù)方的請(qǐng)求，所有的緩存只按照供應(yīng)商-距離計(jì)算模式（步行/騎行/電動(dòng)自行車）-點(diǎn)對(duì)的方式進(jìn)行存儲(chǔ)，每一類緩存大家一起共用，避免各自為戰(zhàn)的情況。

業(yè)務(wù)低谷定時(shí)任務(wù)：就是對(duì)以上幾點(diǎn)中所有收集來的點(diǎn)對(duì)進(jìn)行跑批，即在業(yè)務(wù)低谷期（晚上九點(diǎn)到第二天凌晨四點(diǎn)期間）將這些點(diǎn)對(duì)去請(qǐng)求供應(yīng)商獲取相關(guān)的距離值后寫入GEOHASH表和redis。

4.2 新的調(diào)用時(shí)序

    根據(jù)以上整體的系統(tǒng)架構(gòu)設(shè)計(jì)出了以下的調(diào)用時(shí)序圖：

5. 上線驗(yàn)證與總結(jié)

5.1 上線前的數(shù)據(jù)準(zhǔn)備

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

1，預(yù)熱了存量的點(diǎn)對(duì)大約7億，分別寫入了7位GEOHASH庫，8位GEOHASH庫和redis。

2，將最近半年內(nèi)的存量即時(shí)配訂單數(shù)據(jù)進(jìn)行了預(yù)熱。分別寫入了7位GEOHASH庫，8位GEOHASH庫和redis。

5.2 上線后的數(shù)據(jù)驗(yàn)證與總結(jié)

上線后三天以內(nèi)，監(jiān)控到了以下數(shù)據(jù)：

1，派單業(yè)務(wù)調(diào)用的批量精準(zhǔn)距離計(jì)算接口的日請(qǐng)求點(diǎn)對(duì)大概在6億左右，其中redis緩存命中率達(dá)到了45%左右，接口整體有值率達(dá)到了96%左右。接口平均響應(yīng)時(shí)間控制在了80ms左右，且對(duì)供應(yīng)商的請(qǐng)求QPS控制在了1000左右。

2，推薦訂單業(yè)務(wù)對(duì)GEOHASH點(diǎn)對(duì)距離值的調(diào)用達(dá)到了8億左右，其中7位GEOHASH查詢接口有值率達(dá)到了79%左右，8位GEOHASH的有值率達(dá)到了32%左右，先查詢8位，在查詢7位的有值率達(dá)到82%。接口平均響應(yīng)時(shí)間控制在了25ms左右。

以上監(jiān)控的數(shù)據(jù)，完全滿足了業(yè)務(wù)的需求，而事實(shí)上從線下反饋來看，派錯(cuò)單和推薦不合理的訂單的反饋減少10%以上。

得益于完善的點(diǎn)對(duì)拾漏邏輯和存量數(shù)據(jù)清洗邏輯，各項(xiàng)統(tǒng)計(jì)KPI一直在正向上穩(wěn)步前進(jìn)，到2020年雙11時(shí)，推薦訂單業(yè)務(wù)當(dāng)日調(diào)用達(dá)到37億點(diǎn)對(duì)，派單業(yè)務(wù)當(dāng)日調(diào)用達(dá)到34億點(diǎn)對(duì)。

到了上線一年后的2021年8月份，在8月14號(hào)農(nóng)歷七夕節(jié)，調(diào)用達(dá)到了歷史巔峰：

基礎(chǔ)數(shù)據(jù)的存儲(chǔ)和緩存也達(dá)到了歷史巔峰：

5.3 核心監(jiān)控?cái)?shù)據(jù)展示

具體的監(jiān)控?cái)?shù)據(jù)如下圖所示：

1，推薦訂單點(diǎn)對(duì)總數(shù)和命中率監(jiān)控報(bào)表：

2，派單業(yè)務(wù)點(diǎn)對(duì)監(jiān)控圖：

3，緩存數(shù)據(jù)各項(xiàng)監(jiān)控圖：

由此可見在2021年的七夕節(jié)當(dāng)天，整個(gè)地圖服務(wù)接收到的點(diǎn)對(duì)距離計(jì)算的總流量超過了90億次，而在當(dāng)天，系統(tǒng)只出現(xiàn)了5次超時(shí)報(bào)警，請(qǐng)求到供應(yīng)商的QPS當(dāng)天平均只有2743，說明目前的系統(tǒng)完全能支撐日100億次的點(diǎn)對(duì)距離計(jì)算的請(qǐng)求，而且以極低的成本實(shí)現(xiàn)了該架構(gòu)。

6. 后續(xù)思考

1，目前的調(diào)用峰值無限接近100億次，如果未來一兩年內(nèi)業(yè)務(wù)量增長一倍，需要計(jì)算的點(diǎn)對(duì)會(huì)在300億以上，當(dāng)前的架構(gòu)是否能達(dá)到超高的有值率，超快的響應(yīng)時(shí)間？

2，架構(gòu)線上運(yùn)行一年來未發(fā)生高可用問題，是否意味著在更大流量時(shí)進(jìn)來時(shí)，高可用是否能頂?shù)淖。?/p>