本文由云 + 社区发表作者：腾讯云数据库团队
随着国内服务共享化的热潮普及，共享单车，共享雨伞，共享充电宝等各种服务如雨后春笋，随之而来的 LBS 服务定位问题成为了后端服务的一个挑战。MongoDB 对 LBS 查询的支持较为友好，也是各大 LBS 服务商的首选数据库。腾讯云 MongoDB 团队在运营中发现，原生 MongoDB 在 LBS 服务场景下有较大的性能瓶颈，经腾讯云团队专业的定位分析与优化后，云 MongoDB 在 LBS 服务的综合性能上，有 10 倍以上的提升。腾讯云 MongoDB 提供的优异综合性能，为国内各大 LBS 服务商，例如摩拜单车等，提供了强有力的保障。
LBS 业务特点
以共享单车服务为例，LBS 业务具有 2 个特点，分别是时间周期性和坐标分布不均匀。
一．时间周期性
高峰期与低谷期的 QPS 量相差明显，并且高峰期和低峰期的时间点相对固定。
二. 坐标分布不均匀
坐地铁的上班族，如果留意可能会发现，在上班早高峰时，地铁周围摆满了共享单车，而下班 时段，地铁周围的共享单车数量非常少。如下图，经纬度（121，31.44）附近集中了 99% 以上 的坐标。此外，一些特殊事件也会造成点的分布不均匀，例如深圳湾公园在特殊家假日涌入大量的客户，同时这个地域也会投放大量的单车。部分地域单车量非常集中，而其他地域就非常稀疏。
MongoDB 的 LBS 服务原理
MongoDB 中使用 2d_index 或 2d_sphere_index 来创建地理位置索引(geoIndex), 两者差别不大，下面我们以 2d_index 为例来介绍。
一．2D 索引的创建与使用
db.coll.createIndex({“lag”:”2d”}, {“bits”:int}))
通过上述命令来创建一个 2d 索引，索引的精度通过 bits 来指定，bits 越大，索引的精度就越高。更大的 bits 带来的插入的 overhead 可以忽略不计
db.runCommand({
geoNear: tableName,
maxDistance: 0.0001567855942887398,
distanceMultiplier: 6378137.0,
num: 30,
near: [113.8679388183982, 22.58905429302385],
spherical: true|false})
通过上述命令来查询一个索引，其中 spherical：true|false 表示应该如何理解创建的 2d 索引，false 表示将索引理解为平面 2d 索引，true 表示将索引理解为球面经纬度索引。这一点比较有意思，一个 2d 索引可以表达两种含义，而不同的含义是在查询时被理解的，而不是在索引创建时。
二．2D 索引的理论 MongoDB 使用 GeoHash 的技术来构建 2d 索引（见 wiki geohash 文字链 https://en.wikipedia.org/wiki…RecordId 的索引映射方式存储在 Btree 中
很显然的，一个 2bits 的精度能把平面分为 4 个 grid，一个 4bits 的精度能把平面分为 16 个 grid。2d 索引的默认精度是长宽各为 26，索引把地球分为 (2^26)(2^26) 块，每一块的边长估算为 2PI6371000/(1<<26) = 0.57 米 mongodb 的官网上说的 60cm 的精度就是这么估算出来的 By default, a 2d index on legacy coordinate pairs uses 26 bits of precision, which isroughly equivalent to 2 feet or 60 centimeters of precision using the default range of-180 to 180
三.2D 索引在 Mongodb 中的存储
上面我们讲到 Mongodb 使用平面四叉树的方式计算 Geohash。事实上，平面四叉树仅存在于运算的过程中，在实际存储中并不会被使用到。
插入 对于一个经纬度坐标 [x,y]，MongoDb 计算出该坐标在 2d 平面内的 grid 编号，该编号为是一个 52bit 的 int64 类型，该类型被用作 btree 的 key，因此实际数据是按照 {GeoHashId->RecordValue} 的方式被插入到 btree 中的。
查询 对于 geo2D 索引的查询，常用的有 geoNear 和 geoWithin 两种。geoNear 查找距离某个点最近的 N 个点的坐标并返回，该需求可以说是构成了 LBS 服务的基础（陌陌，滴滴，摩拜），geoWithin 是查询一个多边形内的所有点并返回。我们着重介绍使用最广泛的 geoNear 查询。
geoNear 的查询过程, 查询语句如下
db.runCommand(
{
geoNear: “places”, //table Name
near: [-73.9667, 40.78] , // central point
spherical: true, // treat the index as a spherical index
query: {category: “public”} // filters
maxDistance: 0.0001531 // distance in about one kilometer
}
geoNear 可以理解为一个从起始点开始的不断向外扩散的环形搜索过程。如下图所示：由于圆自身的性质，外环的任意点到圆心的距离一定大于内环任意点到圆心的距离，所以以圆 环进行扩张迭代的好处是：1）减少需要排序比较的点的个数 2）能够尽早发现满足条件的点从而返回，避免不必要的搜索 MongoDB 在实现的细节中，如果内环搜索到的点数过少，圆环每次扩张的步长会倍增
MongoDB LBS 服务遇到的问题
部分大客户在使用 MongoDB 的 geoNear 功能查找附近的对象时，经常会发生慢查询较多的问题，早高峰压力是低谷时段的 10-20 倍，坐标不均匀的情况慢查询严重，濒临雪崩。初步分析发现，这些查询扫描了过多的点集。如下图，查找 500 米范围内，距离最近的 10 条记录，花费了 500ms，扫描了 24000+ 的记录。类似的慢查询占据了高峰期 5% 左右的查询量
测试环境复现与定位 排查数据库的性能问题，主要从锁等待,IO 等待,CPU 消耗三封面分析。上面的截图扫描了过多的记录，直觉上是 CPU 或者 IO 消耗性的瓶颈。为了严谨起见，我们在测试环境复现后，发现慢日志中无明显的 timeAcquiringMicroseconds 项排除了 MongoDB 执行层面的锁竞争问题，并选用较大内存的机器使得数据常驻内存，发现上述用例依旧需要 200ms 以上的执行时间。10 核的 CPU 资源针对截图中的 case，只能支持 50QPS。
为何扫描集如此大 上面我们说过，MongoDB 搜索距离最近的点的过程是一个环形扩张的过程，如果内环满足条件的点不够多，每次的扩张半径都会倍增。因此在遇到内环点稀少，外环有密集点的场景时，容易陷入 BadCase。如下图，我们希望找到离中心点距离最近的三个点。由于圆环扩张太快，外环做了很多的无用扫描与排序。这样的用例很符合实际场景，早高峰车辆聚集在地铁周围，你从家出发一路向地铁，边走边找，共享单车软件上动态搜索距你最近的 10 辆车，附近只有三两辆，于是扩大搜索半径到地铁周围，将地铁周围的所有几千辆车都扫描计算一遍，返回距离你最近的其余的七八辆
问题的解决
问题我们已经知道了，我们对此的优化方式是控制每一圈的搜索量，为此我们为 geoNear 命令增加了两个参数，将其传入 NearStage 中。hintCorrectNum 可以控制结果品质的下限，返回的前 N 个一定是最靠近中心点的 N 个点。hintScan 用以控制扫描集的大小的上限。
hintScan: 已经扫描的点集大小大于 hintScan 后，做模糊处理。hintCorrectNum: 已经返回的结果数大于 hintCorrectNum 后，做模糊处理。
该优化本质上是通过牺牲品质来尽快返回结果。对于国内大部分 LBS 服务来说，完全的严格最近并不是必要的。且可以通过控制参数获得严格最近的效果。在搜索过程中，密集的点落到一个环内，本身距离相差也不会不大。该优化在上线后，将部分大客户的 MongoDB 性能上限从单机 1000QPS 提升了 10 倍到 10000QPS 以上。
和 Redis3.2 的对比
Redis3.2 也加入了地理位置查询的功能，我们也将开源 Redis 和云数据库 MongoDB 进行对比。Redis 使用方式：GEORADIUS appname 120.993965 31.449034 500 m count 30 asc。在密集数据集场景下，使用腾讯云 MongoDB 和开源的 Redis 进行了性能对比。下图是在密集数据集上，在 24 核 CPU 机器上，MongoDB 单实例与 Redis 单实例的测试对比。需要注意的是 Redis 本身是单线程的内存缓存数据库。MongoDB 是多线程的高可用持久化的数据库，两者的使用场景有较大不同。
总结
MongoDB 原生的 geoNear 接口是国内各大 LBS 应用的主流选择。原生 MongoDB 在点集稠密的情况下，geoNear 接口效率会急剧下降，单机甚至不到 1000QPS。腾讯云 MongoDB 团队对此进行了持续的优化，在不影响效果的前提下，geoNear 的效率有 10 倍以上的提升，为我们的客户如摩拜提供了强力的支持，同时相比 Redis3.2 也有较大的性能优势。
此文已由腾讯云 + 社区在各渠道发布
获取更多新鲜技术干货，可以关注我们腾讯云技术社区 - 云加社区官方号及知乎机构号