关于java:Redis源码剖析之GEORedis是如何高效检索地理位置的

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 编码。编码表如下：

最终失去 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 的整体流程十分清晰。

1. 解析申请参数。
2. 计算指标坐标所在的 geohash 和 8 个街坊。
3. 在 zset 中查找这 9 个区域中满足间隔限度的所有点集。
4. 解决排序等后续逻辑。
5. 清理长期存储空间。

结语

因为文章篇幅无限，而且着重解说了 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