服务器之家:专注于服务器技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|数据库技术|

服务器之家 - 数据库 - Redis - Redis高效检索地理位置的原理解析

Redis高效检索地理位置的原理解析

2021-08-10 17:56xindoo Redis

这篇文章主要介绍了Redis是如何高效检索地理位置,通过geo相关的命令,可以很容易在redis中存储和使用经纬度坐标信息,具体实现方法跟随小编一起看看吧

redis geo 用做存储地理位置信息,并对存储的信息进行操作。通过geo相关的命令,可以很容易在redis中存储和使用经纬度坐标信息。redis中提供的geo命令有如下几个:

  • geoadd:添加经纬度坐标和对应地理位置名称。
  • geopos:获取地理位置的经纬度坐标。
  • geodist:计算两个地理位置的距离。
  • georadius:根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
  • georadiusbymember:根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合。
  • geohash:计算一个或者多个经纬度坐标点的geohash值。

要理解redis的geo相关的命令是如何实现了,就得先理解geohash的原理,本质上这些命令就是对geohash数据的封装而已。

geohash

geohash是2008年gustavo niemeye发明用来编码经纬度信息的一种编码方式,比如北京市中心的经纬度坐标是116.404844,39.912279,通过12位geohash编码后就变成了wx4g0cg3vknd,它究竟是如何实现的?其实原理非常简单,就是二分,整个编码过程可以分为如下几步。

1. 转二进制

上过初中地理的我们都知道,地球上如何一个点就可以标识为某个经纬度坐标,经度的取值范围是东经0-180度和西经0-180度,维度的取值范围是北纬0到90和南纬0-90度。去掉东西南北,可以分别认为经度和维度的取值范围为[-180,180]和[-90,90]。

我们先来看经度,[-180,180]可以简单分成两个部分[-180,0]和[0,180],对于给定的一个具体值,我们用一个bit来标识是在[-180,0]还是[0,180]区间里。然后我们可以对这两个子区间继续细分,用更多的bit来标识是这个值是在哪个子区间里。就好比用二分查找,记录下每次查找的路径,往左就是0往右是1,查找完后我们就会得到一个0101的串,这个串就可以用来标识这个经度值。

同理维度也是一样,只不过他的取值返回变成了[-90,90]而已。通过这两种方式编码完成后,任意经纬度我们都可以得到两个由0和1组成的串。
比如还是北京市中心的经纬度坐标 116.404844,39.912279,我们先对116.404844做编码,得到其二进制为:

11010010110001101101

然后我们对维度39.912279编码得到二进制为:

10111000110000111001

2. 经纬度二进制合并

接下来我们只需要将上述二进制交错合并成一个即可,这里注意经度占偶数位,纬度占奇数位,得到最终的二进制。

1101101110000200111100000001111011010011

3. 将合并后的二进制做base32编码

最后我们将合并后的二进制做base32编码,将连续5位转化为一个0-31的十进制数,然后用对应的字符代替,将所有二进制位处理完后我们就完成了base32编码。编码表如下:

Redis高效检索地理位置的原理解析

最终得到geohash值wx4g0cg3vknd

Redis高效检索地理位置的原理解析

geohash是将空间不断的二分,然后将二分的路径转化为base32编码,最后保存下来,从原理可以看出,geohash表示的是一个区间,而不是一个点,geohash值越长,这个区间就越小,标识的位置也就越精确,下图是维基百科中不同长度geohash下的经纬度误差(lat:维度,lng:经度)

Redis高效检索地理位置的原理解析

geohash的用途及问题

geohash成功的将一个二维信息编码成了一个一维信息,这样编码我觉得有两个好处:1. 编码后数据长度变短,利于节省存储。2. 利于使用前缀检索。我们来详细说下第二点。

从上文中geohash的实现来看,只要两个坐标点的geohash有共同的前缀,你们我们就可以肯定这两个点在同一个区域内 (区域大小取决于共同前缀的长度)。这种特性给我们带来的好处就是,我们可以把所有坐标点按geohash做增序索引,然后查找的时候按前缀筛选,大幅提升检索的性能。

举个例子,假设我要找北京国贸附近3公里内的餐馆,已知国贸的geohash是wx4g41,那我也很轻易就可以计算出来我需要扫描哪些区域内的点。但有个点需要注意,上文我已经提到过,geohash值实际上是代表一个区域,而不是一个点,找到一批候选点之后还需要遍历一次计算下精确距离。

Redis高效检索地理位置的原理解析

geohash有个需要注意的问题。geohash是将二维的坐标点做了线下编码(如下图),有时候可能会给人一个误解就是如果两个geohash之间二进制的差异越小,这两个区间距离就越近,这完全是错误的,比如如下图0111和1000,这俩区间二进制只差0001但实际物理距离比较远。

Redis高效检索地理位置的原理解析

如果上图还不明显的话,我从wikipedia上拿到一张图,虚线是线性索引的路径,被虚线链接的两个块geohash值是非常相近的,如下图的(7,3)和(0,4),geohash值会非常相近,但实际物理距离非常远,这就是geohash的突变现象,这也导致了不能直接根据geohash的值来直接判定两个区域的距离大小。

Redis高效检索地理位置的原理解析

但在实际使用geohash过程中,时常会遇到跨域搜索的情况,比如我要在上图(3,3)这个区间内某个点上搜索距它1个距离单位的所有其他点集,这个点集有可能横跨(3,3)加上它周围8个邻域的9个区间,突变的问题会导致这9个区间的geohash不是线性跳转的,但也不是没法计算,实际上可以通过特殊的位运算可以很轻易计算出某个geohash的8个邻域,具体可参考redis源码中src/geohash.c中geohashneighbors()的具体实现,geohashneighbors使用了geohash_move_x和geohash_move_y两个函数实现了geohash左右和上下的移动,这样可以很容易组合出8个邻域的geohash值了。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static void geohash_move_x(geohashbits *hash, int8_t d) {
    if (d == 0)
        return;
 
    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaull;
    uint64_t y = hash->bits & 0x5555555555555555ull;
 
    uint64_t zz = 0x5555555555555555ull >> (64 - hash->step * 2);
 
    if (d > 0) {
        x = x + (zz + 1);
    } else {
        x = x | zz;
        x = x - (zz + 1);
    }
 
    x &= (0xaaaaaaaaaaaaaaaaull >> (64 - hash->step * 2));
    hash->bits = (x | y);
}
 
static void geohash_move_y(geohashbits *hash, int8_t d) {
    if (d == 0)
        return;
 
    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaull;
    uint64_t y = hash->bits & 0x5555555555555555ull;
 
    uint64_t zz = 0xaaaaaaaaaaaaaaaaull >> (64 - hash->step * 2);
    if (d > 0) {
        y = y + (zz + 1);
    } else {
        y = y | zz;
        y = y - (zz + 1);
    }
    y &= (0x5555555555555555ull >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

geo in redis

上文中花了大量篇幅讲解了geohash的实现,其实看到这里,你基本上已经理解了redis中的geohash的实现了。本质上redis中的geo就是对geohash的封装,具体geohash相关的代码就不给大家列了(可自行查阅),就给大家介绍下redis geo里的大体流程。
首先,可能大家最好奇的是geohash在redis中是怎么存储的,从geoadd命令的实现可以一窥端倪。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* geoadd key [ch] [nx|xx] long lat name [long2 lat2 name2 ... longn latn namen] */
void geoaddcommand(client *c) {
    int xx = 0, nx = 0, longidx = 2;
    int i;
 
    /* 解析可选参数 */
    while (longidx < c->argc) {
        char *opt = c->argv[longidx]->ptr;
        if (!strcasecmp(opt,"nx")) nx = 1;
        else if (!strcasecmp(opt,"xx")) xx = 1;
        else if (!strcasecmp(opt,"ch")) {}
        else break;
        longidx++;
    }
 
    if ((c->argc - longidx) % 3 || (xx && nx)) {
        /* 解析所有的经纬度值和member,并对其个数做校验 */
            addreplyerrorobject(c,shared.syntaxerr);
        return;
    }
 
    /* 构建zadd的参数数组 */
    int elements = (c->argc - longidx) / 3;
    int argc = longidx+elements*2; /* zadd key [ch] [nx|xx] score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createrawstringobject("zadd",4);
    for (i = 1; i < longidx; i++) {
        argv[i] = c->argv[i];
        incrrefcount(argv[i]);
    }
 
    /* 以3个参数为一组,将所有的经纬度和member信息从参数列表里解析出来,并放到zadd的参数数组中 */
    for (i = 0; i < elements; i++) {
        double xy[2];
 
        if (extractlonglatorreply(c, (c->argv+longidx)+(i*3),xy) == c_err) {
            for (i = 0; i < argc; i++)
                if (argv[i]) decrrefcount(argv[i]);
            zfree(argv);
            return;
        }
 
        /* 将经纬度坐标转化成score信息 */
        geohashbits hash;
        geohashencodewgs84(xy[0], xy[1], geo_step_max, &hash);
        geohashfix52bits bits = geohashalign52bits(hash);
        robj *score = createobject(obj_string, sdsfromlonglong(bits));
        robj *val = c->argv[longidx + i * 3 + 2];
        argv[longidx+i*2] = score;
        argv[longidx+1+i*2] = val;
        incrrefcount(val);
    }
 
    /* 转化成zadd命令所需要的参数格式*/
    replaceclientcommandvector(c,argc,argv);
    zaddcommand(c);
}

原来geo的存储只是zset包了一层壳(是不是有点小失望),关于zset的具体实现可以参考我之前写的文章redis中skiplist的实现。

我们再来详细看下georadius的大体执行流程(代码偏长,故删除大量细节代码)。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void georadiusgeneric(client *c, int srckeyindex, int flags) {
    robj *storekey = null;
    int storedist = 0; /* 0 for store, 1 for storedist. */
 
    /* 根据key找找到对应的zojb */
    robj *zobj = null;
    if ((zobj = lookupkeyreadorreply(c, c->argv[srckeyindex], shared.emptyarray)) == null ||
        checktype(c, zobj, obj_zset)) {
        return;
    }
 
    /* 解析请求中的经纬度值 */
    int base_args;
    geoshape shape = {0};
    if (flags & radius_coords) {
    /*
     * 各种必选参数的解析,省略细节代码,主要是解析坐标点信息和半径  
     */
    }
 
    /* 解析所有的可选参数. */
    int withdist = 0, withhash = 0, withcoords = 0;
    int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
    int sort = sort_none;
    int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
    long long count = 0;  /* max number of results to return. 0 means unlimited. */
    if (c->argc > base_args) {
    /*
     * 各种可选参数的解析,省略细节代码  
     */
    }
    
    /* get all neighbor geohash boxes for our radius search
     * 获取到要查找范围内所有的9个geo邻域 */
    geohashradius georadius = geohashcalculateareasbyshapewgs84(&shape);
 
    /* 创建geoarray存储结果列表 */
    geoarray *ga = geoarraycreate();
    /* 扫描9个区域中是否有满足条的点,有就放到geoarray中 */
    membersofallneighbors(zobj, georadius, &shape, ga, any ? count : 0);
 
    /* 如果没有匹配结果,返回空对象 */
    if (ga->used == 0 && storekey == null) {
        addreply(c,shared.emptyarray);
        geoarrayfree(ga);
        return;
    }
 
    long result_length = ga->used;
    long returned_items = (count == 0 || result_length < count) ?
                          result_length : count;
    long option_length = 0;
 
    /*
     * 后续一些参数逻辑,比如处理排序,存储……
     */
    // 释放geoarray占用的空间
    geoarrayfree(ga);
}

上述代码删减了大量细节,有兴趣的同学可以自行查阅。不过可以看出georadius的整体流程非常清晰。

解析请求参数。计算目标坐标所在的geohash和8个邻居。在zset中查找这9个区域中满足距离限制的所有点集。处理排序等后续逻辑。清理临时存储空间。

结语

由于文章篇幅有限,而且着重讲解了geohash的实现,并未展开讲解redis中geo相关的各种细节,如读者有兴趣可以详细阅读redis中的src/geo.c了解各类细节。

参考资料

wikipedia geohash

geohash算法原理及实现

本文是redis源码剖析系列博文,同时也有与之对应的redis中文注释版,有想深入学习redis的同学,欢迎star和关注。
redis中文注解版仓库:https://github.com/xindoo/redis
redis源码剖析专栏:https://zxs.io/s/1h

以上就是redis是如何高效检索地理位置的详细内容,更多关于redis检索地理位置的资料请关注服务器之家其它相关文章!

原文链接:https://blog.csdn.net/xindoo/article/details/117635546

延伸 · 阅读

精彩推荐
  • RedisRedis Template实现分布式锁的实例代码

    Redis Template实现分布式锁的实例代码

    这篇文章主要介绍了Redis Template实现分布式锁,需要的朋友可以参考下 ...

    晴天小哥哥2592019-11-18
  • Redis详解三分钟快速搭建分布式高可用的Redis集群

    详解三分钟快速搭建分布式高可用的Redis集群

    这篇文章主要介绍了详解三分钟快速搭建分布式高可用的Redis集群,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...

    万猫学社4502021-07-25
  • RedisRedis 6.X Cluster 集群搭建

    Redis 6.X Cluster 集群搭建

    码哥带大家完成在 CentOS 7 中安装 Redis 6.x 教程。在学习 Redis Cluster 集群之前,我们需要先搭建一套集群环境。机器有限,实现目标是一台机器上搭建 6 个节...

    码哥字节15752021-04-07
  • RedisRedis集群的5种使用方式,各自优缺点分析

    Redis集群的5种使用方式,各自优缺点分析

    Redis 多副本,采用主从(replication)部署结构,相较于单副本而言最大的特点就是主从实例间数据实时同步,并且提供数据持久化和备份策略。...

    优知学院4082021-08-10
  • Redis如何使用Redis锁处理并发问题详解

    如何使用Redis锁处理并发问题详解

    这篇文章主要给大家介绍了关于如何使用Redis锁处理并发问题的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Redis具有一定的参考学习...

    haofly4522019-11-26
  • Redis关于Redis数据库入门详细介绍

    关于Redis数据库入门详细介绍

    大家好,本篇文章主要讲的是关于Redis数据库入门详细介绍,感兴趣的同学赶快来看一看吧,对你有帮助的话记得收藏一下,方便下次浏览...

    沃尔码6982022-01-24
  • Redisredis缓存存储Session原理机制

    redis缓存存储Session原理机制

    这篇文章主要为大家介绍了redis缓存存储Session原理机制详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪...

    程序媛张小妍9252021-11-25
  • Redis《面试八股文》之 Redis十六卷

    《面试八股文》之 Redis十六卷

    redis 作为我们最常用的内存数据库,很多地方你都能够发现它的身影,比如说登录信息的存储,分布式锁的使用,其经常被我们当做缓存去使用。...

    moon聊技术8182021-07-26