我们都是架构师!
关注架构师(JiaGouX),添加“星标”
获取每天技术干货,一起成为牛逼架构师
技术群请加若飞:1321113940 进架构师群
投稿、合作、版权等邮箱:admin@137x.com
因公众号更改推送规则,请点“在看”并加“星标”第一时间获取精彩技术分享
生活必备技能——查找周边
1. 用Mysql数据库来查找附近的POI
const (
dr = math.Pi / 180.0
earthRadius = 6372797.560856
)
func degRad(ang float64) float64 {
return ang * dr
}
// Distance : 计算两个给定坐标之间的距离,单位为米
func Distance(latitude1, longitude1, latitude2, longitude2 float64) float64 {
radLat1 := degRad(latitude1)
radLat2 := degRad(latitude2)
a := radLat1 - radLat2
b := degRad(longitude1) - degRad(longitude2)
return 2 * earthRadius * math.Asin(math.Sqrt(math.Pow(math.Sin(a/2), 2)+
math.Cos(radLat1)*math.Cos(radLat2)*math.Pow(math.Sin(b/2), 2)))
}
positions
:CREATE TABLE `positions` (
`id` bitint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
`poi_uid` varchar(64) NOT NULL COMMENT 'poi的唯一id',
`lng` double(15, 7) NOT NULL COMMENT 'poi的经度',
`lat` double(15, 7) NOT NULL COMMENT 'poi的纬度',
... //其他poi属性字段信息
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
有了数据表,给定一个用户的地理位置坐标($poi_lat, $poi_lng),就可以根据前边提到的三角函数写出SQL计算每个poi和给定坐标的距离,排序取出距离最近的topN条POI数据了。
SELECT
`id`, `poi_uid`, `lng`, `lat`, ...
ROUND(
6371.393 * 2 * ASIN(
SQRT(
POW(
SIN(
(
'$poi_lat' * 3.1415926 / 180 - `lat` * PI() / 180
) / 2
),
2
) + COS('$poi_lat' * 3.1415926 / 180) * COS(`lat` * PI() / 180) * POW(
SIN(
(
'$poi_lng' * 3.1415926 / 180 - `lng` * PI() / 180
) / 2
),
2
)
)
) * 1000
) AS distance_um
FROM
`positions`
ORDER BY
distance_um ASC
LIMIT '$topN'
为了加快查询,我们可以建立(lng, lat)的联合索引:
alter table `positions` add index idx_lng_lat(`lng`, `lat`)
idx_lng_lat
的联合索引存储了id
, lng
, lat
三个字段的值。执行上述SQL时,Innodb引擎会优先选择数据体积较小的idx_lng_lat
B+树完成排序和取值,然后拿到查询的数据记录根据主键id
到主键索引中回表查询取出其他的字段信息(poi_uid
, ...)返回给客户端。lng
, lat
使用了三角函数计算公式(并不是天然有序的),Innodb引擎在排序的时候还是会扫描二级索引idx_lng_lat
的所有记录来计算距离distance_num
。好在Mysql5.6版本以后对topN的查询做了优化,使用优先队列(堆排序)减少了内存使用,但是当POI记录成百上千万的时候,扫描所有的POI计算距离再进行排序,这个计算量实在太大了,性能指标无法满足业务需求。一般的解决方法是通过经纬度设定一个正方形范围来限定POI的数量,然后对正方形内的POI全量扫描并排序,这样可以限制扫描POI的数量。2. 降维查询 —— GeoHash算法实现
between...and...
或者in
语句快速范围查询呢? 业界比较通用的地理位置编码算法——GeoHash算法,就可以实现将二维经纬度数据映射到一维整数,然后提供给B+树、SkipList、前缀树等支持快速范围检索的数据结构进行POI查找了;几乎所有的数据库或中间件(例如Mongo、Redis、ES、Mysql等等)都使用GeoHash算法实现了自己的空间索引来支持对地理位置的距离查询业务。[-90, 0]
用0表示,[0, 90]
用1表示;经度[-180, 0]
用0表示,[0, 180]
用1表示。经度在前纬度在后,这样四个部分都有了一个二进制编码。GeoHash长度(base32编码) | Lat位数(bit) | Lng位数(bit) | km误差 |
---|---|---|---|
1 | 2 | 3 | ±2500 |
2 | 5 | 5 | ±630 |
3 | 7 | 8 | ±78 |
4 | 10 | 10 | ±20 |
5 | 12 | 13 | ±2.4 |
6 | 15 | 15 | ±0.61 |
7 | 17 | 18 | ±0.076 |
8 | 20 | 20 | ±0.01911 |
9 | 22 | 23 | ±0.00478 |
10 | 25 | 25 | ±0.0005971 |
11 | 27 | 28 | ±0.0001492 |
12 | 30 | 30 | ±0.0000186 |
(lng, lat)
给编码映射成一个无符号正整数,其中正整数的二进制中奇数位是经度,偶数位是纬度。Go语言有uint8,uint16,uint32, uint64几种规格的正整数,可以使用这些正整数的中一部分位(比如uint64有64个bit位,使用其中的52个bit位存储GeoHash的编码值)。使用的位数越多,能够表达的坐标就越是精确,通过前边GeoHash的精度误差表可以看出,使用52bit进行编码已经可以将误差范围控制在1米以内了,这对于大多数业务来说都是可以接受的。(116.30778,40.056859)
为例,采用二分查找思想对其进行编码,这种算法虽然速度慢,但是方便理解。[-180, 180]
分为两份:[-180, 0], [0, 180]
;116.30778 位于右侧,将编码值第一个位标记为1;然后再对纬度编码,将[-90, 90]
分为两份:[-90, 0], [0, 90]
;40.056859位于右侧,将编码值的第二位标记为1;第一轮编码结束。[0, 180]
分为两份:[0, 90], [90, 180]
;116.30778 位于右侧,将编码值的第三位标记为1;然后再对纬度编码,将[0, 90]
分为两份:[0, 45], [45, 90]
;40.056859位于左侧,将编码值的第四位标记为0;第二轮编码结束。经过两轮编码,我们得到了百度大厦的坐标位于前边切分的网格1110中。116.30778
,偶数位的纬度会无限趋向40.056859
。最终将经度编码和纬度编码奇偶位交叉到一个uint64的整数中。const defaultBitSize = 52 // 一共使用52个位, 其中26个位表示经度, 26个位表示纬度
// return: geohash, llbox
func encode0(lng, lat float64, bitSize uint) ([]byte, [2][2]float64) {
llbox := [2][2]float64{
{-180, 180}, // lng
{-90, 90}, // lat
}
pos := [2]float64{lng, lat}
hash := &bytes.Buffer{}
bit := 0
var step uint8 = 0
code := uint8(0)
for step < bitSize {
for direction, val := range pos {
mid := (llbox[direction][0] + llbox[direction][1]) / 2
if val < mid {
llbox[direction][1] = mid
} else {
llbox[direction][0] = mid
code |= 1 << (7 - bit) //[]uint8{128, 64, 32, 16, 8, 4, 2, 1}
}
bit++
if bit == 8 {
hash.WriteByte(code)
bit = 0
code = 0
}
step++
if step == bitSize {
break
}
}
}
// 最后不足8bit有剩余的作为一个字节
if code > 0 {
hash.WriteByte(code)
}
return hash.Bytes(), llbox
}
// ToUint64 将geohash code转化为uint64表达
func ToUint64(buf []byte) uint64 {
// padding
if len(buf) < 8 {
buf2 := make([]byte, 8)
copy(buf2, buf)
return binary.BigEndian.Uint64(buf2)
}
return binary.BigEndian.Uint64(buf)
}
// hashcode转换为base32编码
var enc = base32.NewEncoding("0123456789bcdefghjkmnpqrstuvwxyz").WithPadding(base32.NoPadding)
// ToStr 将geohash code进行base32编码
func ToStr(buf []byte) string {
return enc.EncodeToString(buf)
}
wx4g41
,根据前边二分法的切割网格的过程分析,可以根据查找半径r动态计算GeoHash编码的长度,Go语言实现代码如下:mercatorMax = 20037726.37 // pi * earthRadius
func geohashEstimatePrecisionByRadius(radiusMeters float64, latitude float64) (step uint8) {
step = 1
for radiusMeters < mercatorMax {
radiusMeters *= 2
step++
}
step -= 2
if latitude > 66 || latitude < -66 {
step--
if latitude > 80 || latitude < -80 {
step--
}
}
if step < 1 {
step = 1
}
if step > 32 {
step = 32
}
return step*2 - 1
}
step*2 - 1
,这是因为要确保经度比纬度多一次切割,这样才能保证切分的网格是正方形。wx4g41
后,扫描网格内的所有POI,可以看到POI点2并不在网格中,真实的查找周边POI业务场景中,遗漏符合条件的POI是无法接受的。// GetNeighbours 根据给定的 geohash code 返回坐标半径内的所有网格块
func GetNeighbours(latitude, longitude, radiusMeters float64) [][2]uint64 {
step := geohashEstimatePrecisionByRadius(radiusMeters, latitude)
center, box := encode0(latitude, longitude, step)
height := box[0][1] - box[0][0]
width := box[1][1] - box[1][0]
centerLng := (box[0][1] + box[0][0]) / 2
centerLat := (box[1][1] + box[1][0]) / 2
maxLat := centerLat + height
minLat := centerLat - height
maxLng := centerLng + width
minLng := centerLng - width
var result [9][2]uint64
leftUpper, _ := encode0(maxLat, minLng, step)
result[0] = toRange(leftUpper, step)
upper, _ := encode0(maxLat, centerLng, step)
result[1] = toRange(upper, step)
rightUpper, _ := encode0(maxLat, maxLng, step)
result[2] = toRange(rightUpper, step)
left, _ := encode0(centerLat, minLng, step)
result[3] = toRange(left, step)
result[4] = toRange(center, step)
right, _ := encode0(centerLat, maxLng, step)
result[5] = toRange(right, step)
leftDown, _ := encode0(minLat, minLng, step)
result[6] = toRange(leftDown, step)
down, _ := encode0(minLat, centerLng, step)
result[7] = toRange(down, step)
rightDown, _ := encode0(minLat, maxLng, step)
result[8] = toRange(rightDown, step)
return result[1:]
}
// toRange : 将 geohash 转化为uint64的范围
func toRange(scope []byte, step uint8) [2]uint64 {
lower := ToUint64(scope)
radius := uint64(1 << (64 - step))
upper := lower + radius
return [2]uint64{lower, upper}
}
positions
添加三个GeoHash字段(geohash_4、geohash_5、geohash_6
)方便范围检索,他们的字段类型是char定长字段,并且由于字段区分度高,比较简短,我们再将覆盖索引idx_lng_lat
拆分成3个覆盖索引。现在的positions
数据表如下所示:CREATE TABLE `positions` (
`id` bitint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
`poi_uid` varchar(64) NOT NULL COMMENT 'poi的唯一id',
`lng` double(15, 7) NOT NULL COMMENT 'poi的经度',
`lat` double(15, 7) NOT NULL COMMENT 'poi的纬度',
`geohash_4` char(4) NOT NULL DEFAULT '' COMMENT 'geohash的前4位',
`geohash_5` char(5) NOT NULL DEFAULT '' COMMENT 'geohash的前5位',
`geohash_6` char(4) NOT NULL DEFAULT '' COMMENT 'geohash的前6位',
... //其他poi属性字段信息
PRIMARY KEY (`id`),
INDEX KEY `idx_geohash4_lng_lat`(`geohash4`, `lng`, `lat`),
INDEX KEY `idx_geohash5_lng_lat`(`geohash5`, `lng`, `lat`),
INDEX KEY `idx_geohash6_lng_lat`(`geohash6`, `lng`, `lat`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
我们的业务逻辑上就可以对周边检索的SQL根据得到的九宫格GeoHash字符串编码进行范围查询了:
SELECT
`id`, `poi_uid`, `lng`, `lat`, ...
ROUND(
6371.393 * 2 * ASIN(
SQRT(
POW(
SIN(
(
'$poi_lat' * 3.1415926 / 180 - `lat` * PI() / 180
) / 2
),
2
) + COS('$poi_lat' * 3.1415926 / 180) * COS(`lat` * PI() / 180) * POW(
SIN(
(
'$poi_lng' * 3.1415926 / 180 - `lng` * PI() / 180
) / 2
),
2
)
)
) * 1000
) AS distance_um
FROM
`positions`
WHERE `geohash_6` in ("wx4gef", "wx4g44", "wx4g40", "wx4g41",
"wx4g42", "wx4g43", "wx4g1c","wx4g1b", "wx4g46")
ORDER BY
distance_um ASC
LIMIT '$topN'
idx_geohash6_lng_lat
没有获取到topN的POI记录,就可以根据我们的估算,再次扩大距离,使用idx_geohash5_lng_lat
、idx_geohash4_lng_lat
覆盖索引再次查询。就拿检索周边的美食店铺来说,在城市的热门地区,美食店铺POI密集,idx_geohash6_lng_lat
足以覆盖大多数的查询;而对于偏僻地区,美食店铺POI比较少,通常查询idx_geohash6_lng_lat
,扫描的数据也会比较少,查询比较快,用户请求量也不大。所以给Mysql添加GeoHash字符串索引,渐进式匹配召回POI是一个解决周边检索业务很好的方案。3. RedisGeo 快速检索周边
zset
实现POI的范围检索。在Redis中,经纬度使用52位的GeoHash整数编码作为zset的score,zset的score是64位double类型,但是对于52位的整数值,它可以无损存储。positions
数据表中的POI添加到geo容器里,使用geoadd命令(支持批量)即可redis-cli
127.0.0.1:6379> geoadd positions 116.412893 39.948795 abcdf
(integer) 1
127.0.0.1:6379> geoadd positions 116.492893 39.548795 fdsafasf
(integer) 1
127.0.0.1:6379> geoadd positions 116.472893 39.148795 gdfsdas 116.482893 39.048795 sdgdgd
(integer) 2
第二步和Mysql的查询类似,使用georadius来完成,例如给定一个定位点(116.432893 39.178795),查询50km以内的最近的top3 POI
127.0.0.1:6379> georadius positions 116.432893 39.178795 20 km withdist count 3 asc
1) 1) "gdfsdas"
2) "4.7992"
2) 1) "sdgdgd"
2) "15.0896"
同样的,redis也存在查找topN的POI不完整的情况,我们也可以使用渐进式召回的策略查找,为了减少redis请求的网络io,可以使用Lua脚本封装渐进式召回的逻辑。
Redis 7.0 新增了# Redis Functions的新特性,支持自定义lua函数维护在redis的服务端,并随着集群做传播,它是原子性的,可以组合redis现有的所有指令作为新的功能使用,感兴趣的读者可以了解一下。
4. Geo本地索引构建与并发查询
package fastgeo
import (
"math/rand"
"strconv"
"testing"
"time"
)
var fastGeo *FastGeo
// init : 初始化fastgeo实例
func init() {
fastGeo = MakeFastGeo()
lngMin, lngMax := 116171356, 116638188
latMin, latMax := 39748529, 40155613
rand.Seed(time.Now().UnixNano())
// 插入100万的poi坐标
for i := 1; i <= 1000000; i++ {
lngRandom := float64(rand.Intn(lngMax-lngMin) + lngMin) / 1000000
latRandom := float64(rand.Intn(latMax-latMin) + latMin) / 1000000
fastGeo.GeoAdd(lngRandom, latRandom, strconv.Itoa(i))
}
}
// BenchmarkFastGeo_GeoRadius : 压测GeoRadius函数
func BenchmarkFastGeo_GeoRadius(b *testing.B) {
lngMin, lngMax := 116171356, 116638188
latMin, latMax := 39748529, 40155613
rand.Seed(time.Now().UnixNano())
for n := 0; n < b.N; n++ {
lngRandom := float64(rand.Intn(lngMax-lngMin) + lngMin) / 1000000
latRandom := float64(rand.Intn(latMax-latMin) + latMin) / 1000000
// 随机生成经纬度坐标并查询附近10km所有的POI
fastGeo.GeoRadius(lngRandom, latRandom, 10000, 0, 100)
}
}
GeoRadius
,Go语言实现并发查找也很简单,在计算出九宫格的GeoHash范围后,使用waitGroup添加9个协程分别查询各自网格中的POI;待所有的协程完成工作后将结果merge起来,按照距离排序使用内置函数即可。// GeoRadius : 获取指定半径内的元素
func (fastGeo *FastGeo) GeoRadius(lng, lat, radius float64, offset, limit int64) []string {
areas := geohash.GetNeighbours(lat, lng, radius)
parallelNum := len(areas)
var waitGroup sync.WaitGroup
waitGroup.Add(parallelNum)
var mutex sync.Mutex
members := make([]string, 0)
for _, area := range areas {
go func(area [2]uint64) {
lower := &sortedset.ScoreBorder{Value: float64(area[0])}
upper := &sortedset.ScoreBorder{Value: float64(area[1])}
elements := fastGeo.Container.RangeByScore(lower, upper, offset, limit, true)
for _, elem := range elements {
mutex.Lock()
members = append(members, elem.Member)
mutex.Unlock()
}
}(area)
}
waitGroup.Done()
// todo: 根据距离排序
return members
}
5. 总结与展望
本文结合周边检POI的业务场景,跟大家分享了Mysql和Redis如何使用优化;对GeoHash的编码原理做了详细的介绍,并附有源码实现。文章的最后给出了构建自己本地Geo索引库的思路,业务中有需要的读者可以借鉴实现。总体来说周边检索POI的技术实现并不难,但是越来越多的周边检索服务出现在我们的生活中,给我们带来了很多便利,希望有兴趣的开发者在工作中遇到此类问题时能够借鉴本文的思路。
对于GeoHash中的实现,Redis在经纬度位交叉编码、查找九宫格采用的算法思路,都比本文中介绍的更优。本文的初衷是帮助读者理解GeoHash的原理,感兴趣肯钻研的读者推荐研究一下Redis的Geo代码实现。
在真实的业务场景中,除了周边检索POI,还有根据其他因素检索排序的需求,例如大众点评上的美食,距离只是影响其中展现的一个因素,价格、大众评分、用户搜索分类也会影响POI排名。对于此类业务场景,需要构建更复杂的索引,其中包含Geo索引、倒排索引等等,后续笔者也会继续研究此类通用业务,期望将来实现一个本地通用的索引库帮助开发者做更多的事情。
笔者水平有限,文中有不足或错误之处,欢迎留言指正。
往期推荐
如喜欢本文,请点击右上角,把文章分享到朋友圈
如有想了解学习的技术点,请留言给若飞安排分享
·END·
相关阅读:
作者:绘你一世倾城
来源:juejin.cn/post/7147308676745789453
版权申明:内容来源网络,仅供分享学习,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢!
我们都是架构师!
关注架构师(JiaGouX),添加“星标”
获取每天技术干货,一起成为牛逼架构师
技术群请加若飞:1321113940 进架构师群
投稿、合作、版权等邮箱:admin@137x.com