redis georadius源码分析与性能优化

原文地址: https://blog.fanscore.cn/a/51/
背景

最近接到一个需求，开发中使用了redis georadius命令取附近给定距离内的点。完工后对服务进行压测后发现georadius的性能比预期要差，因此我分析了georadius的源码，并对原始的实现方案进行了优化，总结成了本文。

我们生产环境使用的redis版本为4.0.13，因此本文redis源码皆为4.0.13版本的源码

redis geo原理

往redis中添加坐标的命令是GEOADD key longitude latitude member [longitude latitude member ...]，实际上redis会将经纬度转成一个52bit的整数作为zset的score，然后添加到zset中，所以实际上redis geo底层就是个zset，你甚至可以直接使用zset的命令来操作一个geo类型的key。
那么经纬度是如何转成52bit整数的呢？业内广泛使用的方法是首先对经纬度分别按照二分法编码，然后将各自的编码交叉组合成最后的编码。我们以116.505021, 39.950898这个坐标为例看下如何编码：

• 第一次二分操作，把经度分为两个区间：[-180,0)和[0,180]，116.505021落在右区间，因此用1表示第一次编码后的值
  
• 第二次二分操作，把[0,180]分为两个区间[0,90)和[90,180]，116.505021落在右区间，因此用1表示第二次编码后的值
  
• 第三次二分操作，把[90,180]分为两个区间[90,135)和[135,180]，116.505021落在左区间，因此用0表示第二次编码后的值
  
• 按照这种方法依次处理，做完5次后，得到经度值的5位编码值：11010
  

分区次数左区间右区间经度116.505021在区间编码值1[-180, 0)[0, 180][0, 180]12[0, 90)[90, 180][90, 180]13[90, 135)[135, 180][90, 135])04[90, 112.5)[112.5, 135][112.5, 135]15[112.5, 123.75)[123.75, 180][112.5, 123.75]0

• 按照同样的方法对纬度值进行编码，得到纬度值的5位编码值：10111
  

分区次数左区间右区间纬度39.950898在区间编码值1[-90, 0)[0, 90][0, 90]12[0, 45)[45, 90][0, 45]03[0, 22.5)[22.5, 45][22.5, 45])14[22.5, 33.75)[33.75, 45][33.75, 45]15[33.75, 39.375)[39.375, 45][39.375, 45]1然后将经度编码11010和纬度编码值10111交叉得到最终geohash值1110011101

通常会使用base32将编码值转成字符串表示的hash值，与本文无关这里不多做介绍

根据如上的算法通常可以直观的写出如下的代码：

1. // 该代码来源于https://github.com/HDT3213/godis/blob/master/lib/geohash/geohash.go
2. func encode0(latitude, longitude float64, bitSize uint) ([]byte, [2][2]float64) {
3.         box := [2][2]float64{
4.                 {-180, 180}, // lng
5.                 {-90, 90},   // lat
6.         }
7.         pos := [2]float64{longitude, latitude}
8.         hash := &bytes.Buffer{}
9.         bit := 0
10.         var precision uint = 0
11.         code := uint8(0)
12.         for precision < bitSize {
13.                 for direction, val := range pos {
14.                         mid := (box[direction][0] + box[direction][1]) / 2
15.                         if val < mid {
16.                                 box[direction][1] = mid
17.                         } else {
18.                                 box[direction][0] = mid
19.                                 code |= bits[bit]
20.                         }
21.                         bit++
22.                         if bit == 8 {
23.                                 hash.WriteByte(code)
24.                                 bit = 0
25.                                 code = 0
26.                         }
27.                         precision++
28.                         if precision == bitSize {
29.                                 break
30.                         }
31.                 }
32.         }
33.         if code > 0 {
34.                 hash.WriteByte(code)
35.         }
36.         return hash.Bytes(), box
37. }

复制代码

可以看到基本就是上述算法的实际描述，但是redis源码中却是另外一种算法：

1. int geohashEncode(const GeoHashRange *long_range, const GeoHashRange *lat_range,
2.                   double longitude, double latitude, uint8_t step,
3.                   GeoHashBits *hash) {
4.     // 参数检查此处代码省略
5.     ...
6.    
7.     double lat_offset =
8.         (latitude - lat_range->min) / (lat_range->max - lat_range->min);
9.     double long_offset =
10.         (longitude - long_range->min) / (long_range->max - long_range->min);
12.     lat_offset *= (1 << step);
13.     long_offset *= (1 << step);
14.     // lat_offset与long_offset交叉
15.     hash->bits = interleave64(lat_offset, long_offset);
16.     return 1;
17. }

复制代码

调用encode0函数就能计算出给定点在step = geohashEstimateStepsByRadius()精度级别所在矩形区域的geohash值。接下来计算该矩形区域附近的八个区域。

1. const double MERCATOR_MAX = 20037726.37;
3. uint8_t geohashEstimateStepsByRadius(double range_meters, double lat) {
4.     if (range_meters == 0) return 26;
5.     int step = 1;
6.     while (range_meters < MERCATOR_MAX) {
7.         range_meters *= 2;
8.         step++;
9.     }
10.     step -= 2;
11.     // 高纬度地区地球半径小因此适当降低精度
12.     if (lat > 66 || lat < -66) {
13.         step--;
14.         if (lat > 80 || lat < -80) step--;
15.     }
17.     if (step < 1) step = 1;
18.     if (step > 26) step = 26;
19.     return step;
20. }

复制代码

一个区域的东侧区域只要将经度的编码值+1即可，反之西侧区域只要将经度编码值-1即可，北侧区域只要将纬度的编码值+1即可，南侧区域只要将纬度的编码值-1即可。对应redis源码如下:

1. ...
2. // 调用encode0函数计算geohash
3. geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
4. // 计算出附近八个区域
5. geohashNeighbors(&hash,&neighbors);
6. ...

复制代码

如上图所示，当给定点在中心区域的东北侧时，西北、西、西南、南、东南五个方向的区域中的所有点距离给定点肯定超过了给定距离，所以可以过滤掉，redis代码如下所示：

1. void geohashNeighbors(const GeoHashBits *hash, GeoHashNeighbors *neighbors) {
2.     neighbors->east = *hash;
3.     neighbors->west = *hash;
4.     neighbors->north = *hash;
5.     neighbors->south = *hash;
6.     neighbors->south_east = *hash;
7.     neighbors->south_west = *hash;
8.     neighbors->north_east = *hash;
9.     neighbors->north_west = *hash;
10.     // 纬度加1就是东侧区域
11.     geohash_move_x(&neighbors->east, 1);
12.     geohash_move_y(&neighbors->east, 0);
13.     // 纬度减1就是西侧区域
14.     geohash_move_x(&neighbors->west, -1);
15.     geohash_move_y(&neighbors->west, 0);
16.     // 精度减1就是南侧区域
17.     geohash_move_x(&neighbors->south, 0);
18.     geohash_move_y(&neighbors->south, -1);
20.     geohash_move_x(&neighbors->north, 0);
21.     geohash_move_y(&neighbors->north, 1);
23.     geohash_move_x(&neighbors->north_west, -1);
24.     geohash_move_y(&neighbors->north_west, 1);
26.     geohash_move_x(&neighbors->north_east, 1);
27.     geohash_move_y(&neighbors->north_east, 1);
29.     geohash_move_x(&neighbors->south_east, 1);
30.     geohash_move_y(&neighbors->south_east, -1);
32.     geohash_move_x(&neighbors->south_west, -1);
33.     geohash_move_y(&neighbors->south_west, -1);
34. }

复制代码

计算出区块后下一步就需要将九宫格区域中的所有坐标点拿出来，依次计算与给定点的距离，然后过滤出符合给定距离的点

1. if (steps >= 2) {
2.     if (area.latitude.min < min_lat) {
3.         GZERO(neighbors.south); // 南侧区域置零，过滤南侧区域
4.         GZERO(neighbors.south_west);
5.         GZERO(neighbors.south_east);
6.     }
7.     if (area.latitude.max > max_lat) {
8.         GZERO(neighbors.north);
9.         GZERO(neighbors.north_east);
10.         GZERO(neighbors.north_west);
11.     }
12.     if (area.longitude.min < min_lon) {
13.         GZERO(neighbors.west);
14.         GZERO(neighbors.south_west);
15.         GZERO(neighbors.north_west);
16.     }
17.     if (area.longitude.max > max_lon) {
18.         GZERO(neighbors.east);
19.         GZERO(neighbors.south_east);
20.         GZERO(neighbors.north_east);
21.     }
22. }

复制代码

georadius优化

从上一节中可以看到，给定距离范围越大，则九宫格区域越大，九宫格区域内的点就越多，而每个点都需要计算与中间点的距离，距离计算又涉及到大量的三角函数计算，所以这部分计算是十分消耗CPU的。又因为redis工作线程是单线程的，因此无法充分利用多核，无法通过增加redis server的CPU核数来提升性能，只能添加从库。

距离计算算法及优化可以看下美团的这篇文章: https://tech.meituan.com/2014/09/05/lucene-distance.html

对于这个问题，我们可以将九宫格以及距离计算部分提升到我们的应用程序即redis客户端来进行，步骤如下：

• 在客户端计算出九宫格区域，然后转为zset score的范围
  
• 使用zrangebyscore命令从redis取出score范围内的所有点
  
• 遍历所有点依次计算与给定点的距离，筛选出符合距离条件的点
  

陌陌好像也是使用了这种方案：https://mp.weixin.qq.com/s/DL2P49y4R1AE2MIdkxkZtQ

由于我们使用golang进行开发，因此我将redis中的georadius部分代码转为了golang代码，并整理成一个库开源在了github：https://github.com/Orlion/go-georadius
原本的写法是:

1. // 遍历九宫格内所有点，依次计算与给定点的距离，然后过滤出符合给定距离的点添加到ga中
2. int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
3.     GeoHashBits neighbors[9];
4.     unsigned int i, count = 0, last_processed = 0;
5.     int debugmsg = 1;
7.     neighbors[0] = n.hash;
8.     neighbors[1] = n.neighbors.north;
9.     neighbors[2] = n.neighbors.south;
10.     neighbors[3] = n.neighbors.east;
11.     neighbors[4] = n.neighbors.west;
12.     neighbors[5] = n.neighbors.north_east;
13.     neighbors[6] = n.neighbors.north_west;
14.     neighbors[7] = n.neighbors.south_east;
15.     neighbors[8] = n.neighbors.south_west;
17.     // 遍历九宫格
18.     for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
19.         ...
20.         // 当给定距离过大时，区块可能会重复
21.         if (last_processed &&
22.             neighbors[i].bits == neighbors[last_processed].bits &&
23.             neighbors[i].step == neighbors[last_processed].step)
24.         {
25.             continue;
26.         }
27.         // 取出宫格内所有点，依次计算距离，符合条件后添加到ga中
28.         count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
29.         last_processed = i;
30.     }
31.     return count;
32. }
34. int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
35.     GeoHashFix52Bits min, max;
36.     // 根据区块的geohash值计算出对应的zset的score的上下限[min,max]
37.     scoresOfGeoHashBox(hash,&min,&max);
38.     // 取出底层的zset中的[min,max]范围内的元素，依次计算距离，符合条件后添加到ga中
39.     return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
40. }

复制代码

改造后：

1. client.GeoRadius(key, longitude, latitude, &redis.GeoRadiusQuery{
2.         Radius:    1000,
3.         Unit:      "m", // 距离单位
4.         Count:     1,          // 返回1条
5.         WithCoord: true,       // 将位置元素的经纬度一并返回
6.         WithDist:  true,       // 一并返回距离
7. })

复制代码

压测结果对比

43w坐标点，取附近50km（九宫格内有14774点，符合条件的点约6000个）
50km优化前

1. ga := make([]redis.Z, 0)
2. ranges := geo.NeighborRanges(longitude, latitude, 1000)
3. for _, v := range ranges {
4.     zs, _ := client.ZRangeByScoreWithScores(key, redis.ZRangeBy{
5.                 Min: strconv.Itoa(int(v[0])),
6.                 Max: strconv.Itoa(int(v[1])),
7.         }).Result()
8.         for _, z := range zs {
9.             dist := geox.GetDistanceByScore(longitude, latitude, uint64(z.Score))
10.                 if dist < 1000 {
11.                     ga = append(ga, z)
12.                 }
13.         }
14. }

复制代码

50km优化后

1. Concurrency Level:      5
2. Time taken for tests:   89.770 seconds
3. Complete requests:      5000
4. Failed requests:        0
5. Write errors:           0
6. Total transferred:      720000 bytes
7. HTML transferred:       0 bytes
8. Requests per second:    55.70 [#/sec] (mean)
9. Time per request:       89.770 [ms] (mean)
10. Time per request:       17.954 [ms] (mean, across all concurrent requests)
11. Transfer rate:          7.83 [Kbytes/sec] received
13. Connection Times (ms)
14.               min  mean[+/-sd] median   max
15. Connect:        0    0   0.0      0       0
16. Processing:    23   90  10.7     90     159
17. Waiting:       23   89  10.7     89     159
18. Total:         23   90  10.7     90     159
20. Percentage of the requests served within a certain time (ms)
21.   50%     90
22.   66%     93
23.   75%     96
24.   80%     97
25.   90%    102
26.   95%    107
27.   98%    111
28.   99%    116
29. 100%    159 (longest request)

复制代码

可以看到性能并没有巨大的提升，我们减小距离范围到5km（符合条件的点有130个）再看下压测结果
5km优化前

1. Concurrency Level:      5
2. Time taken for tests:   75.447 seconds
3. Complete requests:      5000
4. Failed requests:        0
5. Write errors:           0
6. Total transferred:      720000 bytes
7. HTML transferred:       0 bytes
8. Requests per second:    66.27 [#/sec] (mean)
9. Time per request:       75.447 [ms] (mean)
10. Time per request:       15.089 [ms] (mean, across all concurrent requests)
11. Transfer rate:          9.32 [Kbytes/sec] received
13. Connection Times (ms)
14.               min  mean[+/-sd] median   max
15. Connect:        0    0   0.0      0       0
16. Processing:    21   75  14.2     75     159
17. Waiting:       21   75  14.1     75     159
18. Total:         21   75  14.2     75     159
20. Percentage of the requests served within a certain time (ms)
21.   50%     75
22.   66%     80
23.   75%     84
24.   80%     86
25.   90%     92
26.   95%     98
27.   98%    104
28.   99%    111
29. 100%    159 (longest request)

复制代码

5km优化后

1. Concurrency Level:      5
2. Time taken for tests:   14.006 seconds
3. Complete requests:      5000
4. Failed requests:        0
5. Write errors:           0
6. Total transferred:      720000 bytes
7. HTML transferred:       0 bytes
8. Requests per second:    356.99 [#/sec] (mean)
9. Time per request:       14.006 [ms] (mean)
10. Time per request:       2.801 [ms] (mean, across all concurrent requests)
11. Transfer rate:          50.20 [Kbytes/sec] received
13. Connection Times (ms)
14.               min  mean[+/-sd] median   max
15. Connect:        0    0   0.0      0       0
16. Processing:     2   14   5.5     12      33
17. Waiting:        2   14   5.5     12      33
18. Total:          2   14   5.5     12      34
20. Percentage of the requests served within a certain time (ms)
21.   50%     12
22.   66%     16
23.   75%     19
24.   80%     20
25.   90%     22
26.   95%     23
27.   98%     27
28.   99%     28
29. 100%     34 (longest request)

复制代码

可以看到当优化后性能更差了


猜测造成这个结果的原因应该是附近5km九宫格内的点比较少，所以优化后实际没减少多少距离计算，但多了n(n