使用 MySQL 实现搜索附近的人
背景介绍
现今地理位置功能非常普及, 在很多网站, 手机 app 等都有体现, 现实中这个功能也方便了我们的吃穿住行, 比如我们普通大众经常使用的附近的人附近的餐厅等就是基于这个功能来实现, 其可以应用到以下相关功能:
商店: 找到你当前的位置;
社交: 找到你附近的朋友;
地图: 找到附近感兴趣的地方;
从这方面来看, 如何找到当前的位置是我们的首要任务, 庆幸的是现今的很多 gps 设备可以完成该任务, 比如我们常用的手机打开 gps 功能后, 相关的 app 即可获取到经纬度地理位置信息, 我们通过经纬度即可计算出相应的地理位置, 再就是计算两个经纬度之间的距离, 等等. 其背后的技术实现值得我们持续深入的学习下去,下文会简单介绍地理位置实现的方式, 后面则着重介绍如何使用 MySQL 实现附近的人的功能.
经纬度
详见: 经纬度
首先了解经纬度需要学习下地理知识, 经纬度是经度与纬度的合称组成的坐标系统, 称为地理坐标系统, 他是利用三度空间的球面来定义地球上的空间的球面坐标系统, 能够标示地球上的任意一个位置.
如下图所示:
纬线和经线都是人类为度量方便而假设处理的辅助线.
纬线
纬线定义为地球表面某点随地球自转所形成的轨迹, 如上图所示, 任何一根纬线都是圆形而且两两平行. 纬线的长度时赤道的周长诚意纬线的纬度的余弦.
经线
经线也称子午线, 定义为地球表面连接南北两极的大圆线上的半圆弧. 任两根经线的长度相等，相交于南北两极点, 每一根经线都有其相对应的数值，称为经度, 经线指示南北方向。
距离计算
我们以 (lng1, lat1) 表是A点的经度和纬度, (lng2, lat2) 表示B点的经度和纬度, 地球为一个接近椭圆的球体, 赤道半径为 6378.14 千米, 极半径为 6356.755千米, 平均半径则为 6371.004 千米. 我们标记为 R. 如果以 0 度经线为基准, 东经取经度的正值, 西经取负值, 北纬取 90 - 纬度值(90 - latitude), 南纬取 90 + 纬度值 (90+latitude), 可以得到计算两点的距离公式:
C = sin(MLatA)*sin(MLatB)*cos(MLonA-MLonB) + cos(MLatA)*cos(MLatB)
Distance = R*Arccos(C)*Pi/180
这里的单位是千米, 如果是其它单位记得换算.
google 地图提供的方法则是如下公式:
实现方式
如果清楚了如何计算两点之间的距离, 那么附近的人, 附件的餐馆等也就很容易得到, 以当前的位置为圆心, 附近的距离为半径, 获取到在该圆面积下所有的点即是搜索到的结果, 下面我们介绍不同工具的实现方式和各自的优缺点.
redis
redis 从 3.2 版本开始支持位置信息的操作, 提供了 6 个相关的操作方法分别为以下:
GEOADD: 向指定的 key 中增加位置成员;
GEODIST: 计算指定 key 中两个成员之间的距离;
GEOHASH: 返回指定成员的 geohash 结果;
GEOPOS: 返回指定 key 中成员的位置信息;
GEORADIUS: 返回 key 中成员周围指定距离之内的所有成员;
GEORADIUSBYMEMBER: 同 GEORADIUS, 不过以成员名标识当前的位置信息;
从这方面看, redis 提供了很大的便利, 但是所有的成员只能放到一个指定的 key 中. 所以如果要选用 redis, 需要考虑以下优缺点:
优点:
1. 简单, redis 接口调用即可, 方法也不多;
2. 适合集合较少的应用;
缺点:
1. 集合太大容易引起性能瓶颈;
2. 没有过期时间和删除成员的方法, 需要开发人员根据业务规则遍历 key 清除;
3. 没有额外的 hook 相关的功能, 需要开发人员做很多工作;
tile38
tile38 是新兴且开源的地理位置数据库, 兼容 redis 协议. 看活跃程度国外还有人用, 国内就没怎么发现. 如果选用 tile38 则需要考虑一下优缺点:
优点:
1. 功能函数丰富, 有很多惊喜的功能, 比如超时设置, hook 调用通知, json 接口等;
2. golang 语言编写, 部署方便;
3. 支持主从, 以 redis 的 aof 格式存储数据;
4. 搜索函数比起 redis 丰富了很多;
缺点:
1. 不是特别稳定, github 还有很多未解决的 issue;
2. 没有配置文件, 都在代码里控制, 不清楚作者有没有这方面的打算;
3. 内存使用和磁盘刷新的策略还不明朗, 需要读代码才能确定;
Mongodb
Mongodb 也提供了地理位置相关的功能, 操作函数较丰富, 几何方面的支持也很全, 不过不能使用地理位置索引作为分区的键. 读者可以参考使用 mongodb 完成地理位置相关的功能;
Postgis
PostgreSQL 的扩展 Postgis 则提供了很全面的空间相关的操作函数, 基于 OpenGIS 实现了很多几何空间相关的函数, 同样 postgis 也支持空间相关的索引. 国内使用 postgresql 的人不多, 如果要选用该扩展, 学习成本较大, 另外成员的过期时间需要开发者实现.
MySQL
MySQL 从 5.6 开始基于 OpenGIS 实现了很多空间相关的函数, 不过仅 MyISAM 引擎支持空间索引, 在 5.7 中 InnoDB 引擎才开始支持空间索引. 功能上类似 PostGIS, 也提供了很多几何空间方面的操作函数, 比如点, 线, 多边形的操作等, 不过其存在时间不长, 比起 postgis 功能上也不是特别丰富, 一些位置距离的计算需要靠开发者自己完成, 相关的过期时间也需要开发者完成. 详细可参考文章 mysql-spatial-functions , 下文主要介绍以传统的方式计算两个地理位置之间的距离, MySQL 的空间数据类型可参考 Spatial Data Type, 下文会给出一个简单的实例.
MySQL 计算位置之间的距离
在经纬度小节中我们了解了两个公式用来计算两个位置之间的距离, 该小节我们以测试数据说明如何实现. 测试需要的表结构和数据:
表结构:
CREATE TABLE `geotest` (
`userid` int(10) NOT NULL,
`longitude` decimal(9,6) NOT NULL,
`latitude` decimal(9,6) NOT NULL,
`create_time` datetime DEFAULT NULL,
UNIQUE KEY `unq_uid` (`userid`),
KEY `idx_lat_lng` (`longitude`,`latitude`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
测试数据:
insert geotest values(10000, 116.417480, 40.003033, now());
insert geotest values(10001, 116.437480, 40.004033, now());
insert geotest values(10002, 116.457480, 40.005033, now());
insert geotest values(10003, 116.477480, 40.006033, now());
......
......
第一种公式中, google 为我们介绍了如何使用 sql 来获取附近的点, 如下所示, 我们选用 6371km 作为地球的半径,根据上述小节的计算公式推断:
C = sin(MLatA)*sin(MLatB)*cos(MLonA-MLonB) + cos(MLatA)*cos(MLatB)
Distance = R*Arccos(C)*Pi/180
google 地图的计算公式可以参考 geo_search
两个位置之间的距离则可以换算成以下公式:
R*arccos( cos( radians(latA)*cos( radians(latB) ) * cos( radians(lonA - lonB) )) + sin( radians(latA)*cos(latB) ))
radians 函数计算出相应的弧度信息, 得到下面的 sql:
SELECT
user_id, (
6371 * acos (
cos ( radians(40.003033) )
* cos( radians( latitude ) )
* cos( radians( longitude ) - radians(116.417481) )
+ sin ( radians(40.003033) )
* sin( radians( latitude ) )
)
) AS distance
FROM geotest
HAVING distance < 1
ORDER BY distance
LIMIT 0 , 20;
上面的 sql 从 geotest 中从 geotest 表中获取到经度(116.417481) 和纬度(40.003033) 位置附近 1km 所有的user_id 信息.
观察这个 sql, 可以预见到在表数据较大的时候仅建立复合索引 idx_lat_lng 肯定会遇到性能瓶颈, 因为每行记录都需要做相关的运算, 才能跑出最后的结果.
所以要提高该 sql 的性能就需要尽量过滤不需要的 longitude 和 latitude 两列的值. 参考 geo_search 和 fastest-way-to-find-distance, 在近距离的情况下我们可以认为当前区域内的所有位置都在一个平面内, 虽然有点误差, 但是比起地球这么大的椭球, 我们完全可以忽略其中的误差. 以经纬度来讲, 1 纬度约等于 69 英里, 大约 111044.736 米, 其中的换算公式为:
1°latitude ~= 69 miles
1°longitude ~= cos(latitude)*69 miles
所以对于位置信息(lng, lat), 我们可以计算出以其为中心周边指定距离的四个点, 如下图所示:
+-------------+
| |
| |
| + |
| |
| |
+-------------+
计算公式如下:
lng1 = lon - dist/abs(cos(radians(lat))*69)
lng2 = lon + dist/abs(cos(radians(lat))*69)
lat1 = lat - (dist/69);
lat2 = lat + (dist/69);
四个点的坐标就分别为 (lng1, lat1), (lng1, lat2), (lng2, lat1), (lng2, lat2), 所以存在于该四个点组成的平面之间的点即可以被认为在(lng, lat) 的 dist 距离内.
基于上述的规则, 修改 sql 为以下:
SELECT
user_id, (
6371 * acos (
cos ( radians(40.003033) )
* cos( radians( latitude ) )
* cos( radians( longitude ) - radians(116.417481) )
+ sin ( radians(40.003033) )
* sin( radians( latitude ) )
)
) AS distance
FROM geotest
WHERE longitude BETWEEN lng1 AND lng2
AND latitude BETWEEN lat1 AND lat2
HAVING distance < 1
ORDER BY distance
LIMIT 0 , 20;
这样就能很好的使用索引, 如果还想增加超时设置, 可以在 sql 里加上 create_time 条件进行过滤, 比如只查找最近一天的附近的用户. 另外开发者也可以结合使用 sphinx 或 elasticsearch 得到更好的性能.
下面为根据上面介绍的规则整理成存储过程, 方便开发者调用访问. 这里我们将地球半径的公里数转换为米即为 6371392.89m, 69英里则转为 111044.736m, 如下存储过程返回 user_id 和 距离(米):
DELIMITER $$
drop procedure if exists geo_dist$$
create procedure geo_dist(IN lng decimal(9, 6), IN lat decimal(9, 6), IN dist int)
begin
declare lng1 decimal(9, 6); declare lng2 decimal(16, 13);
declare lat1 decimal(9, 6); declare lat1 decimal(16, 13);
-- calculate lng and lat for the rectangle, in meters unit
set lng1 = lng - dist/abs(cos(radians(lat))*111044.736);
set lng2 = lng + dist/abs(cos(radians(lat))*111044.736);
set lat1 = lat - (dist/111044.736);
set lat2 = lat + (dist/111044.736);
-- run the query
select user_id, round((
6371392.89 * acos (
cos ( radians(lat) )
* cos( radians( latitude ) )
* cos( radians( longitude ) - radians(lng) )
+ sin ( radians(lat) )
* sin( radians( latitude ) )
)
), 0) AS distance
from user_position
where lng between lng1 and lng2
and lat between lat1 and lat2
having distance < dist
ORDER BY distance
LIMIT 0 , 20;
END$$
DELIMITER ;
运行存储过程, 取出该经纬度下附近 5km 的用户和距离(m):
mysql > call geo_dist(116.4174800000000, 40.0030330000000, 5000);
+---------+----------+
| user_id | distance |
+---------+----------+
| 10000 | 0 |
| 10001 | 1707 |
| 10002 | 3414 |
+---------+----------+
3 rows in set (0.00 sec)
Query OK, 0 rows affected (0.01 sec)
10001 用户和指定的经纬度距离为1707米, 我们在 redis 3.2 版本中进行简单测试, 可以看到结果都很相近:
127.0.0.1:6380> geoadd tttt 116.417480 40.003033 t1
(integer) 0
127.0.0.1:6380> geoadd tttt 116.437481 40.004034 t2
(integer) 0
127.0.0.1:6380> GEODIST tttt t1 t2
"1707.5093"
在 MySQL 5.6/5.7 版本中则可以直接使用 ST_Distance_Sphere 函数计算两个地理位置的距离, 默认情况下, radius 参数为地球的极半径 6370986 米, 返回的结果单位为米, 如下所示
CREATE TABLE `geotest` (
`userid` int(10) NOT NULL,
`geoaddr` geometry NOT NULL,
`create_time` datetime DEFAULT NULL,
UNIQUE KEY `unq_uid` (`userid`),
SPATIAL KEY `spa_geo` (`geoaddr`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
mysql > insert geotest values(10000, POINT(116.417480 40.003033), now());
mysql > insert geotest values(10001, POINT(116.437480, 40.004033), now());
mysql > insert geotest values(10002, POINT(116.457480, 40.005033), now());
mysql > insert geotest values(10003, POINT(116.477480, 40.006033), now());
mysql > select userid, ST_Distance_Sphere(POINT(116.4174800000000, 40.0030330000000), geoaddr) as distance
from geotest
where ST_Distance_Sphere(POINT(116.4174800000000, 40.0030330000000), geoaddr) < 5000;
+--------+--------------------+
| userid | distance |
+--------+--------------------+
| 10000 | 0 |
| 10001 | 1707.1384059048478 |
| 10002 | 3414.2518917034054 |
+--------+--------------------+
3 rows in set (0.00 sec)
mysql > set @pt1 = ST_GeomFromText('POINT(116.417480 40.003033)');
Query OK, 0 rows affected (0.00 sec)
mysql > set @pt2 = ST_GeomFromText('POINT(116.437481 40.004034)');
Query OK, 0 rows affected (0.00 sec)
mysql > select ST_Distance_Sphere(@pt1, @pt2) as distance;
+--------------------+
| distance |
+--------------------+
| 1707.2306341756278 |
+--------------------+
1 row in set (0.01 sec)
总结
这里我们了解了以传统的方式在 MySQL 中实现搜索附近的人的功能实现, 实际上限于笔者的了解, mongodb 和 postgis 都提供了很丰富的几何空间相关的操作函数及索引, MySQL 的新版也做了很多这方面的改进, 有需要的读者可以仔细阅读本文中相关的引用链接找到最佳的解决方案.