分享 基于地址位置,查询附近的人 ,解决方案及性能分析 [已更新, 详见下面的结论]

easyhappy · 2014年10月15日 · 最后由 wjh_2010 回复于 2016年05月08日 · 34627 次阅读
本帖已被设为精华帖!

1、场景介绍

对于很多 LBS 应用来说,让用户寻找周围的好友 可能 都是一个必不可少的功能,下面 我们就以这个功能为例:

  • 显示我附近的人
  • 由近到远排序
  • 显示距离

对于以上的问题, 目前解决方案有很多种, 比如:

a. 基于 MySQL 数据库 b. 采用 GeoHash 索引,基于 MySQL c. MySQL 空间存储(MySQL Spatial Extensions) d. 使用 MongoDB 存储地理位置信息 e. 使用 PostgreSQL 存储地理位置信息

关于 a、b、c, 这篇文章 已经很好的说明了, 这里就不一一赘述, 下面我们主要是基于方案 d 深入探讨一些东西。

2、使用 MongoDB 存储地理位置信息

MongoDB 原生支持地理位置索引,可以直接用于位置距离计算和查询。查询结果默认将会由近到远排序,而且查询结果也包含目标点对象、距离目标点的距离等信息。

而且 geoNear 是 MongoDB 原生支持的查询函数,所以性能上也做到了高度的优化,完全可以应付生产环境的压力。

3、MongoDB 索引介绍

2d index:

使用 2d index 能够将数据作为 2 维平面上的点存储起来, 在 MongoDB 2.2 以前 推荐使用 2d index 索引。 现在 MongodDB 2.6 了, 推荐使用 2dspere index

2dsphere index:

2dsphere index 支持球体的查询和计算,同时它支持数据存储为GeoJSON 和传统坐标。

4、性能测试

先说说 测试环境:

Mac Pro(处理器 Intel Core i5、2.4 GHz、2 核、16G 内存) + Mongo 2.6 + Rails4.1.4

model 代码:

class User
   field :location,        type: Array
   index({ location: "2d"}, { background: true })
   # 或者 index({ location: "2dsphere"}, { background: true })

  class << self
    def nearby(coordinate, max_distance=5)
       # 5公里内, 符合条件的记录, 默认取100个。同时会按照距离的远近 进行排序。
       self.geo_near(coordinate).max_distance(max_distance.fdiv   6371).spherical.distance_multiplier(6371000)
    end
  end
end

使用 命令1的 查询时间:

User.nearby([117.490219, 40.962954]).count
# 5公里内, 符合条件的记录, 默认取100个。同时会按照距离的远近 进行排序。
# 距离 存在 attributes["geo_near_distance"] 中, example:User.nearby([117.490219, 40.962954]).first["geo_near_distance"]

通过测试发现, 使用 2d index 在数据量 变大的过程中, 查询时间 会变的 非常慢, 而使用 2d sphere index 基本可以控制在 0.5s 左右。这里 留下一个问题: 为什么会是这样的?

使用命令2

User.where(:location => {"$within" => {"$centerSphere" => [[116.490219, 42.962954], (5.fdiv(6371) )]}}).count
# 5公里内, 符合条件的记录、默认会选出所有符合条件的结果。
# 缺点是 需要自己进行排序, 且需要自己计算 geo_near_distance。

命令2 因为不需要 对 符合条件的结果 进行排序, 所以 查询时间 相比 命令1的 查询时间 大大减少。

备注: 每 1w 条 数据的插入时间是 8s 左右。

5、其他的一些 概念的东西

MongoDB 查询地理位置默认有 3 种距离单位: 米 (meters) 平面单位 (flat units,可以理解为经纬度的 “一度”) 弧度 (radians)

2d 索引能同时支持 $center 和 $centerSphere, 2dsphere 索引支持 $centerSphere。 关于距离单位,$center 默认是度,$centerSphere 默认距离是弧度。

6、使用 PostgreSQL 存储地理位置信息

关于 PostgreSQL 和 Rails 的结合, 可以参考 我同事@windstill文章, 这里就不具体描述了

测试环境介绍:

Mac Pro(处理器 Intel Core i5、2.4 GHz、2 核、16G 内存) + PostgreSQL 9.3.5 + PostGis2.1.3(PostgreSQL 的扩展) + Rails4.1.4

备注:postgis完整实现了opengis 的 Simple Features标准之中的空间对象模型和函数

测试命令

User.select("users.*, st_distance(location, 'point(116.458104 39.966293)') as distance").where("st_dwithin(location, 'point(116.458104 39.966293)', 10000)").order("distance")
# 查找10公里 内结果, 并按照距离进行排序

测试结果:

7、结论

关于地理位置的计算, 其实 Mysql、MongoDB、PostgreSQL 都支持,只不过 MongoDB 和 PostgreSQL 支持的更好一些。 而且通过 测试我们可以发现 MongoDB 在数据量 变大的时候, 查询的瓶颈 会变的越来越大。反过来看 PostgreSQL, 它的查询时间基本是随着 数据量的增长, 而线性增长的。

所以 如果你的应用 数据量不大 或者说在百万级别的话 可以考虑用 MongoDB。但是如果数据量是千万级别或者更高的话, 推荐使用 PostgreSQL。

当然了 由于我们这个项目业务既 需要 事务,又需要 Geo 计算, 所以选择 PostgreSQL 作为我们的主数据库。

8、留坑

后期 会在使用 PostgreSQL 使用一段 时间后, 深入的总结一些关于它的东东...

谁知道 ruby-china 的 table markdown 怎么写的, 我调了半天, 没有调好 😪

#1 楼 @meeasyhappy 除了详细性能测试结果,最好有一个总结,大概哪个方案的总体优劣势。因为有些人想看详细,有些很懒只想知道答案。

还有一种方案是通过 spinx 或者 elasticsearch 来处理 lbs

@as181920 这个在完善中... 我是想等 PostgreSQL 的测试结果 出来之后 在给出一个 最终的结果。

非商业程序可尝试百度地图 api,有相关的支持。

@xiaogui 我这个是商业的。 而且真实需求 不是 查找附近的人 (这个是我为了举例子用的)

小伙伴们挺赞!

赞!能问一下坐标获取用得是?有对比过差别吗?

喜欢有数据的对比,结论就是,使用PostgreSQL就好

#8 楼 @ziqa 因为是测试数据, 所以是基于某一个 [经度, 维度] 上下浮动 随机的数据 大概 1000 万个。

#9 楼 @small_fish__ 之前 用的是 Mysql + Mongo, 为了说服老大 换数据库, 肯定要给他看数据了.... 嘿嘿

#10 楼 @meeasyhappy 😓 其实我想问的是生产中获取坐标哪个服务更好用……

百度地图 就 ok 了

#12 楼 @meeasyhappy 请注意,百度地图在使用中可能需要进行坐标转换。

那坐标的存储格式是啥?point(213.132 2313.2) 直接字符串存入数据库?

#16 楼 @rubyu2 这个方案还是基于 geohash 的,基于 geohash 的解决方案有个缺点不能直接算出准确距离。看到楼主的测试数据目前 PostgreSQL 方案很好了

#15 楼 @wangping 存的是空间数据类型,需要 Postgis 扩展支持,地理空间数据类型有 Point, Linestring, Polygon 等

Order.where("st_dwithin(location, 'point(116.458104 39.966293)', 10000)")

Order.select("orders.*, st_distance(location, 'point(116.458104 39.966293)') as distance").where("st_dwithin(location, 'point(116.458104 39.966293)', 10000)").order("distance”)

Order.where("ST_Intersects('SRID=4326;POLYGON((116.424031 39.955045, 116.468731 39.955045, 116.468731 39.983357, 116.424031 39.983357, 116.424031 39.955045))',location)")

Order.select("orders.*, st_distance(location, 'point(116.458104 39.966293)') as distance").where("ST_Intersects('SRID=4326;POLYGON((116.424031 39.955045, 116.468731 39.955045, 116.468731 39.983357, 116.424031 39.983357, 116.424031 39.955045))',location)").order("distance")

(Postgresql+Postgis)对于数据量 1002W,以上四种查询的时间分别为 12.0ms、15.3ms、1.6ms、2.0ms

尝试下 Postgres 的 PostGIS

如果是基于 PG,推荐读一下这个系列的文章: http://daniel-azuma.com/articles/georails

我的总数据量200w左右。 nearSphere 一个坐标的总量在42w左右, 为啥我查询的时间要 2s(2000ms) 多呢? 下面是具体的数据:

数据存储的格式如下:

{
"postid":NumberLong(97040),
"accountid":NumberLong(348670),
"location":{
    "type":"Point",
    "coordinates":[
        112.56531,
        32.425657
    ]
},
"type":NumberLong(1),
"countspreads":NumberLong(6),
"countavailablespreads":NumberLong(6),
"timestamp":NumberLong(1428131578)
}

** 索引在 location 字段上面 **

{
        "v" : 1,
        "key" : {
            "location" : "2dsphere"
        },
        "name" : "location_2dsphere",
        "2dsphereIndexVersion" : 2
    }

** 查询语句 **

db.example.find({"location":{"$nearSphere":{"$geometry":{"type":"Point","coordinates":[113.547821,22.18648]},"$maxDistance":50000, "$minDistance":0}}}).explain()

结果如下

{
    "cursor" : "S2NearCursor",
    "isMultiKey" : false,
    "n" : 145255,
    "nscannedObjects" : 1290016,
    "nscanned" : 1290016,
    "nscannedObjectsAllPlans" : 1290016,
    "nscannedAllPlans" : 1290016,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 4087,
    "indexBounds" : {

    },
    "server" : "DB-SH-01:27017",
    "filterSet" : false
}

注意我的 $maxDistance 很大, 根据 explain 结果看,扫描了 100w+ 的记录,查询时间预计是 4087ms。 如果缩小 $maxDistance 到 500, 结果如下:

{
    "cursor" : "S2NearCursor",
    "isMultiKey" : false,
    "n" : 21445,
    "nscannedObjects" : 102965,
    "nscanned" : 102965,
    "nscannedObjectsAllPlans" : 102965,
    "nscannedAllPlans" : 102965,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 0,
    "nChunkSkips" : 0,
    "millis" : 634,
    "indexBounds" : {

    },
    "server" : "DB-SH-01:27017",
    "filterSet" : false
}

这里看到扫描的记录数是 10w+, 预计时间是 634ms 依然很大。 后面我记录把$maxDistance缩小到0.0001,扫描的记录数也在 8w 左右,而时间徘徊在 600ms 左右。 无法再减少。 这个时间是完全无法接受的。

不知道楼主如何测试出来100w记录能够在30ms左右的

#24 楼 @nevernet coordinates 字段建索引了么?

#25 楼 @windstill 索引不在 coordinates 上,在 location 字段上。 如下:

{
        "v" : 1,
        "key" : {
            "location" : "2dsphere",
        },
        "name" : "location_2dsphere,
        "ns" : "db.example",
        "2dsphereIndexVersion" : 2
    }
26楼 已删除

#26 楼 @nevernet 你可以先试下中心点用传统的坐标方式: db.example.find({"location":{"$nearSphere":[113.547821,22.18648],"$maxDistance":50000, "$minDistance":0}}).explain()

#26 楼 @nevernet 从 explain 的结果看,cursor 是 S2NearCursor,我在最新的官方文档中没找到这个。不知道你的 mongodb 是什么版本,据说 2.4 版本有一个索引问题,在 2.5 版本中修复了,https://jira.mongodb.org/browse/SERVER-9257

这里有个类似的问题,http://stackoverflow.com/questions/20825328/mongodb-compound-geospatial-ascending-index-issues

#29 楼 @windstill 用传统坐标试过的。 之前就是传统坐标。 也不是组合索引, 当然组合和非组合索引都试过。

mongodb version 2.6.x

stackoverflow 基本被我翻烂了。:)

所以我现在估计并不是单纯的索引问题,因为这个 collection 被 insert, update 也很频繁,也可能是其他原因引起 v2.6 下都是库级锁,所以很蛋疼。

用 Mongodb3.0 和 PostGIS 2.1.7 做测试 Mongodb 的性能大概是 postgis 的两倍

对于 GPS 附近点查询,建议使用快速全球索引,mongoDb 的性能太低了。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册