地理附近系统
<p>[TOC]</p>
<h1>概述</h1>
<p>核心功能就是要找到某人、物或地点地理位置附近的其它人、物或地点。比如像打车系统 Uber、滴滴的叫车功能，比如像大众点评、Yelp 或者百度地图、Google Map 中寻找附近餐馆的功能，或者是 “ 附近的人” 之类基于地理信息的 app 上的小功能。</p>
<p>从读写的角度看，基本上这类功能都要存储位置信息，基于位置的 “寻找” 是很核心的需求，因此读往往比较重。但是写的话差异就比较大了，像有一些应用，比如打车系统，需要司机和乘客双方匹配，而且双方又往往在地理位置上的移动中，因此每几秒钟就要汇报并记录一下位置，有非常重的写；但是像 “寻找附近餐馆” 这样功能，匹配双方至少有一方基本上地理位置是固定的，往往就不是这样了。</p>
<h1>架构图</h1>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitFile?sign=99f0b6abb10b6b0e39a4c3837757168f&file=file.png" alt="" /></p>
<h1>说明</h1>
<ul>
<li>大的功能上面，它包括两个部分。一个是单纯的位置汇报，比如每 10 秒钟，司机和乘客都要汇报自己的当前位置（经度和纬度），这也是图中最上面和最下面的两个横着的箭头，汇报给 Location Service。</li>
<li>第二个是这个打车的流程。乘客发起一个打车请求，Ride Service 收到以后，去 Location Service 找一个范围内的 available 的车，然后按照根据距离的顺序，通过 Notification Service 向司机发送通知。为了提高效率，可以同时发送给几个司机，让司机抢单。司机收到并接受请求以后，Ride Service 让 Location Service 更新司机的状态为 unavailable， 再通过 Notification Service 告知用户正式匹配到的车。如果找不到司机，扩大搜索范围去 Location Service 继续寻找。</li>
<li>这里司机也好，乘客也好，和 Notification Service 的连接，使用 push 模型，可以通过 long poll 或者 socket 连接实现。</li>
<li>打车的信息存放在 Ride DB 里面，这个数据库可以是一个 RDB，也可以是一个 KV 的数据库。</li>
<li>Location Service 的实现是一个 Proximity 系统的核心。在这里它主要要做两件事，一个是接受司机和乘客位置的汇报并记录；一个是接受 Ride Service 的请求，返回一定范围内匹配到的 available 的司机。</li>
<li>这个匹配机制有大致有这样两种实现方式（之前在<a href="https://www.raychase.net/5615" title="这篇文章">这篇文章</a>中都提到过）：
<ul>
<li>一种是使用 <a href="https://en.wikipedia.org/wiki/Quadtree" title="QuadTree">QuadTree</a>，就是说把地图上任意一个区域都划分成四个子区域，每个区域如果节点超过一个阈值，就继续划分。</li>
<li>第二种是使用 <a href="https://en.wikipedia.org/wiki/Geohash" title="Geohash">Geohash</a>，本质上就是降维。降维的原因是，一维的数据管理和查找起来要容易得多，二维的数据要做到高效查找比较困难。我们的查找条件是基于经纬度的，而不是一个单值；我们存储的数据也都是一个个经纬度形成的点，因此，Geohash 的办法就是把查找条件和存储的数据全部都变成一个个单值，这样就可以利用我们熟悉的一维数组区域查找的技术来高效实现（比如把它索引化，而索引化其实是可以通过 B+树来实现的，因此 Geohash 的查询时间复杂度和 QuadTree 是可以在同一个数量级的，都是 log n）。</li>
</ul></li>
<li>由于写的频率太高，可能导致上面的树（无论哪一种）出现节点分裂和合并过于频繁，造成性能和资源竞争的压力，因此可以做两个优化：
<ul>
<li>这个 location 数据的写入，可以不非常实时，比如对于没有处于接单状态的司机，可以合并几次写入到一次再写入。</li>
<li>节点的分裂还是合并设置阈值，并且分裂阈值要大于合并阈值，阈值以内不发生节点变化。比如说，一个大节点的下一层，同样数量的司机，可能分布在 x 个子节点，也可能分布在 x+1 个子节点。</li>
</ul></li>
</ul>
<h1>参考</h1>
<p><a href="https://www.raychase.net/6312">https://www.raychase.net/6312</a></p>