• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    Redis高效检索地理位置的原理解析

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

    要理解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编码。编码表如下:

    最终得到geohash值wx4g0cg3vknd

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

    geohash的用途及问题

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

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

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

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

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

    但在实际使用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值了。

    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命令的实现可以一窥端倪。

    /* 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的大体执行流程(代码偏长,故删除大量细节代码)。

    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检索地理位置的资料请关注脚本之家其它相关文章!

    您可能感兴趣的文章:
    • redis数据库查找key在内存中的位置的方法
    • PHP redis实现超迷你全文检索
    上一篇:Redis可视化客户端小结
    下一篇:Redis 哨兵集群的实现
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

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