达达集团地图服务百亿级距离计算的演进之路

名词解释

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，架构线上运行一年来未发生高可用问题，是否意味着在更大流量时进来时，高可用是否能顶的住？