常见分布式应用系统设计图解(五):Proximity 系统

今天是介绍 Proximity 系统,我不知道怎么翻译恰当,就保留英文原文。虽说词义上说的只是 “相似度”,但多数说的是 “地理” 上的相似度。因此,这一类系统多为基于地理上的邻近程度来提供服务的,核心功能就是要找到某人、物或地点地理位置附近的其它人、物或地点。比如像打车系统 Uber、滴滴的叫车功能,比如像大众点评、Yelp 或者百度地图、Google Map 中寻找附近餐馆的功能,或者是 “ 附近的人” 之类基于地理信息的 app 上的小功能。

从读写的角度看,基本上这类功能都要存储位置信息,基于位置的 “寻找” 是很核心的需求,因此读往往比较重。但是写的话差异就比较大了,像有一些应用,比如打车系统,需要司机和乘客双方匹配,而且双方又往往在地理位置上的移动中,因此每几秒钟就要汇报并记录一下位置,有非常重的写;但是像 “寻找附近餐馆” 这样功能,匹配双方至少有一方基本上地理位置是固定的,往往就不是这样了。

在这里我们选择其中相对较复杂的打车系统来讨论。

  • 大的功能上面,它包括两个部分。一个是单纯的位置汇报,比如每 10 秒钟,司机和乘客都要汇报自己的当前位置(经度和纬度),这也是图中最上面和最下面的两个横着的箭头,汇报给 Location Service。
  • 第二个是这个打车的流程。乘客发起一个打车请求,Ride Service 收到以后,去 Location Service 找一个范围内的 available 的车,然后按照根据距离的顺序,通过 Notification Service 向司机发送通知。为了提高效率,可以同时发送给几个司机,让司机抢单。司机收到并接受请求以后,Ride Service 让 Location Service 更新司机的状态为 unavailable, 再通过 Notification Service 告知用户正式匹配到的车。如果找不到司机,扩大搜索范围去 Location Service 继续寻找。
  • 这里司机也好,乘客也好,和 Notification Service 的连接,使用 push 模型,可以通过 long poll 或者 socket 连接实现。
  • 打车的信息存放在 Ride DB 里面,这个数据库可以是一个 RDB,也可以是一个 KV 的数据库。
  • Location Service 的实现是一个 Proximity 系统的核心。在这里它主要要做两件事,一个是接受司机和乘客位置的汇报并记录;一个是接受 Ride Service 的请求,返回一定范围内匹配到的 available 的司机。
  • 这个匹配机制有大致有这样两种实现方式(之前在这篇文章中都提到过):
    • 一种是使用 QuadTree,就是说把地图上任意一个区域都划分成四个子区域,每个区域如果节点超过一个阈值,就继续划分。
    • 第二种是使用 Geohash,本质上就是降维。降维的原因是,一维的数据管理和查找起来要容易得多,二维的数据要做到高效查找比较困难。我们的查找条件是基于经纬度的,而不是一个单值;我们存储的数据也都是一个个经纬度形成的点,因此,Geohash 的办法就是把查找条件和存储的数据全部都变成一个个单值,这样就可以利用我们熟悉的一维数组区域查找的技术来高效实现(比如把它索引化,而索引化其实是可以通过 B+树来实现的,因此 Geohash 的查询时间复杂度和 QuadTree 是可以在同一个数量级的,都是 log n)。
  • 由于写的频率太高,可能导致上面的树(无论哪一种)出现节点分裂和合并过于频繁,造成性能和资源竞争的压力,因此可以做两个优化:
    • 这个 location 数据的写入,可以不非常实时,比如对于没有处于接单状态的司机,可以合并几次写入到一次再写入。
    • 节点的分裂还是合并设置阈值,并且分裂阈值要大于合并阈值,阈值以内不发生节点变化。比如说,一个大节点的下一层,同样数量的司机,可能分布在 x 个子节点,也可能分布在 x+1 个子节点。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

247 次阅读

Leave a Reply

Your email address will not be published.

back to top