亲宝软件园·资讯

展开

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

xindoo 人气:0
想了解Redis高效检索地理位置的原理解析的相关内容吗,xindoo在本文为您仔细讲解Redis检索地理位置的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Redis检索地理位置,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

加载全部内容

相关教程
猜你喜欢
用户评论