system desing 系统设计(十三)： LBS/O2O服务系统设计

 　   自从十几年前智能机和MBB开始普及，移动互联网迎来了井喷式的发展，到现在人手一部智能手机。既然是移动互联网，基于LBS的O2O自然是非常重要的业务之一，国内的滴滴、美团、饿了么都用过吧？这些O2O的后台又是怎么设计的了？

　　1、（1）先来分析一下业务场景：　　

　　• 第一阶段：
　　　　• Driver report locations
　　　　• Rider request Uber, match a driver with rider
　　• 第二阶段：
　　　　• Driver deny / accept a request
　　　　• Driver cancel a matched request
　　　　• Rider cancel a request
　　　　• Driver pick up a rider / start a trip
　　　　• Driver drop off a rider / end a trip
　　  串起来讲：司机上线，给后台上报自己的位置。如果有乘客想打车，也同时上报自己的位置。后台开始匹配，找到乘客附近的司机后通知司机接单，然后司机赶往乘客的地点接人，开始运送乘客。只要是打过滴滴的小伙伴肯定都能理解整个流程！
　  （2）再来分析一下通信的数据量，这会直接影响后台对性能的要求！从业务上讲，client和server之间最大的QPS就是location的上报了，尤其是driver的location，肯定是要每个固定的周期给server上报的，江湖传闻uber是4s的period，滴滴应该也类似，暂且也按照4s计算【上报周期越大，延迟越长，这就是大家在打车APP看到车和实际车位置总是不一致的原因】！这里以滴滴IPO时自己披露的运营数据为例来计算：招股书显示，滴滴全球年活跃用户为4.93亿，全球年活跃司机1500万。其中，滴滴在中国拥有3.77亿年活跃用户和1300万年活跃司机，2021年第一季度，中国出行业务日均交易量为25million次。我个人经常打滴滴，日常和司机师傅聊天时得知：滴滴强制要求司机师傅每天载客累计总时长不能超过8hour【核心是为了防止疲劳驾驶】。按照平均一单30minus计算，每个司机平均每天接16单。按照上面中国出行业务日均交易量为25million次计算，每天的active driver大约有25million/16=1.56million，所以这里就假设每日平均在线司机数量为1.56million：

　　• Average Driver QPS = 1.56million / 4 = 390k
　　　　• Driver report locations by every 4 seconds
　　• Peak Driver QPS = 390k * 2 = 780 k【早晚上下班高峰期，还有工业园区996社畜晚上10点后下班，这个QPS的压力是比较大的！】
　　计算出了diver的QPS，再来看看乘客rider的：和driver比，rider是不需要经常上报location的，只是到了需要打车的时候才需要上报自己的location。还是按照上述“中国出行业务日均交易量为25million次”来计算，乘客rider的QPS约：

　　• Average Rider QPS = 25million / 86400 = 290；

　　• Peak Rider iver QPS =  290 *2 = 580；这个QPS和driver的相比，几乎可以忽略不记.......

　　再来看看存储空间的需求：
　　• 假如每条Location都记录，并且每条记录100byte计算，每天需要：(390k+290)*100byte*86400=3.1T 
       • 假如只记录最后一次上报的Location，那么需要(390k+290)*100byte=37M

　　从数据量来看是非常大的，需要找读写都很快的存储系统！

 　  2、接下来站在开发角度，继续分析网约车服务：

 　　(1).乘客发出打车请求，服务器创建一次Trip
　　　　• 将 trip_id 返回给用户
　　　　• 乘客每隔几秒询问一次服务器是否匹配成功
　　(2). 服务器找到匹配的司机，写入Trip，状态为等待司机回应
　　　　• 同时修改 Driver Table 中的司机状态为不可用，并存入对应的 trip_id
　　(3). 司机汇报自己的位置
　　　　• 顺便在 Driver Table 中发现有分配给自己的 trip_id
　　　　• 去 Trip Table 查询对应的 Trip，返回给司机
　　(4). 司机接受打车请求
　　　　• 修改 Driver Table, Trip 中的状态信息
　　　　• 乘客发现自己匹配成功，获得司机信息
　　(5). 司机拒绝打车请求
　　　　• 修改 Driver Table，Trip 中的状态信息，标记该司机已经拒绝了该trip
　　　　• 重新匹配一个司机，重复第(2)步

　　整个流程图示如下：
　　

 　　为了配合上述流程，库表的模型设计如下：

 　 （1）driver角度：最频繁的就是上报location数据了！为了便于后续的复盘和追溯，driver每条的location数据都会在location table中持久保存！这张表写的频率远比读高，建议用nosql存储！由于这部分数据是存放在磁盘的，在和rider匹配时如果全部从磁盘读取，效率太低，所以diver的location数据还需要在内存的redis存一份，格式就是Driver table中的KV形式！注意：driver table的数据是记录driver最后一次上报的位置，所以每个driver只可能有1条数据存这里面。如果driver趴着一动不动，这个数据是不需要更新的！

             其次，如果匹配到rider的打车请求，会在trip table中更改status为“on the way to pick up”/"in trip"等！同时也在driver table中把status改成对应的值，避免再和其他rider匹配了！

　　      完成打车后，需要在driver table中把状态改成可用；同时trip table中的status也要改成“cancelled”或“end”！

      （2）站在rider角度，唯一的目的就是匹配diver，所以rider上报自己的location后，后台是要第一时间匹配相应的driver的，怎么做了？利用geohash算法！匹配的结果以KV形式保存在user location table中！由于driver的location在不断变化，所以user location table的数据也是在不断变化的，这就对这个table读写效率的要求很高了，最终还是采用redis最合适！截至目前，redis需要存放的数据有driver table和user location table！

　　当rider需要打车时，发出request请求后，这个请求需要在trip table中新增一条记录。这条记录除了driver_id外，其他的字段都可以填写完毕！一旦从user location table中匹配上了driver，就要第一时间填写driver_id字段，并更新statuse字段了！

 　　3、（1）rider和driver上报的都是原始的经纬度数据，怎么匹配了？这里用的geohash算法了，这是一种典型的二分计算法，具体原理这里不赘诉了，最终的结果就是可以把二维的经纬度数据转成一个字符串。根据字符串相同字符的个数，来确认两个坐标点之间的距离，如下：比如两个getohash算法结果的字符串前面4个字符都是相同的，那么这两个点的距离不超过20km；

 　　下面是3家互联网大厂总部的geohash值：

　　• LinkedIn HQ: 9q9hu3hhsjxx
　　• Google HQ: 9q9hvu7wbq2s
　　• Facebook HQ: 9q9j45zvr0se

　　可以看到：linkedIn和google有4位相同，距离不超过20km，员工跳巢都很方便，但facebook就不同了，只有3位相同，相距不超过78km，严重影响了人员流动.....

　　现在以Google HQ: 9q9hvu7wbq2sw为例，怎么匹配附近的driver？这本质上就是个字符串匹配的问题，怎么高效快速匹配了？

　 （2）站在打车角度，driver和rider的距离也就第5、6最合适了，也就是距离控制在2.4km以内，所以字符串匹配到第5位就够了！站在工程快速实现的角度考虑，有这么几种方法：

　 （2.1）SQL 数据库
　　　　• 首先需要对 geohash 建索引
　　　　　　• CREATE INDEX on geohash;
　　　　• 使用 Like Query
　　　　　　• SELECT * FROM location WHERE geohash LIKE` 9q9hv%`;

　　　　由于location table的写入量巨大，sql数据库显然是不合适的，这里直接pass不考虑了！

　　(2.2) NoSQL - Cassandra
　　　　　　• 将 geohash 设为 column key
　　　　　　• 使用 range query (9q9hv0, 9q9hvz)

　　        把location table存在nosql数据库，同时计算出geohash的值，设置为column key【rowkey还是driver_id】，然后用range query (9q9hv0, 9q9hvz)，这是完全可行的！

　　（2.3）NoSQL - Redis
　　　　　　• Driver 的位置分级存储
　　　　　　　　• 如 Driver 的位置如果是 9q9hvt，则存储在 9q9hvt， 9q9hv， 9q9h 这 3 个 key 中【和search engine的typeahead是不是很类似了？完全可以用MapReduce来处理】
　　　　　　　　• 6位 geohash 的精度已经在一公里以内，对于 Uber 这类应用足够了
　　　　　　• key = 9q9hvt, value = set of drivers in this location

　　　　　　所以user location table的key既可以放rider的geohash，也可以放driver的geohash！如果是rider的geohash，后续用drive的geohash做predix match！

 　（3）为了提速，在存放driver table和location table的时候使用redis。redis速度是快，但也不是一点缺陷都没有：内存贵！其实也可以用其他的nosql数据库替代，大不了多增加一些大磁盘的服务器嘛！既然一定要用多台机器的话，我们可以用 1000 台 Cassandra / Riak这样的 NoSQL 数据库，平均每台分摊 300 的QPS， 能更好的处理 Replica 和挂掉之后恢复的问题；

参考：

1、https://github.com/uber/ringpop-node  RingPop架构

2、https://github.com/uber/tchannel  tchannel RPC协议

3、https://github.com/google/s2-geometry-library-java  google S2
4、https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf    Dynamo: Amazon’s Highly Available Key-value Store

5、https://www.bilibili.com/video/BV1Za411Y7rz?p=95&vd_source=241a5bcb1c13e6828e519dd1f78f35b2  基于LBS的服务

6、https://www.sohu.com/a/472168419_121092262  滴滴运营的财务数据

7、https://zhuanlan.zhihu.com/p/35940647  geohash算法原理