用 Redis 高效实现GEO地理位置相关功能

作者: ___n | 来源:发表于2019-10-23 11:12 被阅读0次

自 Redis 3.2 开始，Redis 基于 GEOHASH 和有序集合提供了地理位置相关功能。

Redis Geo 模块包含了以下 6 个命令:

GEOADD：将给定的位置对象（纬度、经度、名字）添加到指定的 Key。
GEOPOS：从 Key 里面返回所有给定位置对象的位置（经度和纬度）。
GEODIST：返回两个给定位置之间的距离。
GEOHASH：返回一个或多个位置对象的 GeoHASH 表示。
GEORADIUS：以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象。
GEORADIUSBYMEMBER：以给定的位置对象为中心，返回与其距离不超过给定最大距离的所有位置对象。

应用

GEOADD

添加经纬度信息,时间复杂度为O(log(N))
有效的经度从-180度到180度。
有效的纬度从-85.05112878度到85.05112878度。
当坐标位置超出上述指定范围时，该命令将会返回一个错误。

redis> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2

GEOPOS

查找指定key的经纬度信息，可以指定多个key，批量返回，时间复杂度为O(log(N))
GEOPOS 命令返回一个数组，数组中的每个项都由两个元素组成：第一个元素为给定位置元素的经度，而第二个元素则为给定位置元素的纬度。
当给定的位置元素不存在时，对应的数组项为空值。

redis> GEOPOS Sicily Palermo Catania NonExisting
1) 1) "13.361389338970184"
   2) "38.115556395496299"
2) 1) "15.087267458438873"
   2) "37.50266842333162"
3) (nil)

GEODIST

返回两个地方的距离，可以指定单位unit ，比如米m，千米km，英里mi，英尺ft，
如果两个位置之间的其中一个不存在，那么命令返回空值。
如果用户没有显式地指定单位参数，那么 GEODIST 默认使用米作为单位。
GEODIST 命令在计算距离时会假设地球为完美的球形，在极限情况下，这一假设最大会造成 0.5% 的误差。
计算出的距离会以双精度浮点数的形式被返回。如果给定的位置元素不存在，那么命令返回空值。
时间复杂度为O(log(N))

redis> GEODIST Sicily Palermo Catania
"166274.15156960039"
redis> GEODIST Sicily Palermo Catania km
"166.27415156960038"
redis> GEODIST Sicily Palermo Catania mi
"103.31822459492736"
redis> GEODIST Sicily Foo Bar
(nil)

GEORADIUS

以给定的经纬度为中心，返回键包含的位置元素当中，与中心的距离不超过给定最大距离的所有位置元素。
范围可以使用以下其中一个单位：

m 表示单位为米。
km 表示单位为千米。
mi 表示单位为英里。
ft 表示单位为英尺。
在给定以下可选项时，命令会返回额外的信息：

WITHDIST: 在返回位置元素的同时，将位置元素与中心之间的距离也一并返回。距离的单位和用户给定的范围单位保持一致。

WITHCOORD: 将位置元素的经度和维度也一并返回。

WITHHASH: 以 52 位有符号整数的形式，返回位置元素经过原始 geohash 编码的有序集合分值。这个选项主要用于底层应用或者调试，实际中的作用并不大。
命令默认返回未排序的位置元素。通过以下两个参数，用户可以指定被返回位置元素的排序方式：

ASC: 根据中心的位置，按照从近到远的方式返回位置元素。

DESC: 根据中心的位置，按照从远到近的方式返回位置元素。
在默认情况下， GEORADIUS 命令会返回所有匹配的位置元素。虽然用户可以使用 COUNT <count> 选项去获取前 N 个匹配元素，但是因为命令在内部可能会需要对所有被匹配的元素进行处理，所以在对一个非常大的区域进行搜索时，即使只使用 COUNT 选项去获取少量元素，命令的执行速度也可能会非常慢。但是从另一方面来说，使用 COUNT 选项去减少需要返回的元素数量，对于减少带宽来说仍然是非常有用的。
在没有给定任何 WITH 选项的情况下，命令只会返回一个像 [“New York”,”Milan”,”Paris”] 这样的线性（linear）列表。
在指定了 WITHCOORD 、 WITHDIST 、 WITHHASH 等选项的情况下，命令返回一个二层嵌套数组，内层的每个子数组就表示一个元素。
在返回嵌套数组时，子数组的第一个元素总是位置元素的名字。至于额外的信息，则会作为子数组的后续元素，按照以下顺序被返回：

以浮点数格式返回的中心与位置元素之间的距离，单位与用户指定范围时的单位一致。

geohash 整数。

由两个元素组成的坐标，分别为经度和纬度。
时间复杂度为O(N+log(M))，N为指定半径范围内的元素个数，M为要返回的个数

# WITHDIST
redis> GEORADIUS Sicily 15 37 200 km WITHDIST
1) 1) "Palermo"
   2) "190.4424"
2) 1) "Catania"
   2) "56.4413"
# WITHCOORD
redis> GEORADIUS Sicily 15 37 200 km WITHCOORD
1) 1) "Palermo"
   2) 1) "13.361389338970184"
      2) "38.115556395496299"
2) 1) "Catania"
   2) 1) "15.087267458438873"
      2) "37.50266842333162"
# WITHDIST WITHCOORD
redis> GEORADIUS Sicily 15 37 200 km WITHDIST WITHCOORD
1) 1) "Palermo"
   2) "190.4424"
   3) 1) "13.361389338970184"
      2) "38.115556395496299"
2) 1) "Catania"
   2) "56.4413"
   3) 1) "15.087267458438873"
      2) "37.50266842333162"

GEORADIUSBYMEMBER

根据指定的地点查询半径在指定范围内的位置

可以指定WITHDIST返回距离，WITHCOORD返回经纬度，WITHHASH返回geohash值

可以指定ASC或DESC，根据距离来排序

可以指定COUNT限定返回的记录数
时间复杂度为O(log(N)+M)，N为指定半径范围内的元素个数，M为要返回的个数

redis> GEOADD Sicily 13.583333 37.316667 "Agrigento"
(integer) 1
redis> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2
redis> GEORADIUSBYMEMBER Sicily Agrigento 100 km
1) "Agrigento"
2) "Palermo"

GEOHASH

该命令将返回11个字符的Geohash字符串，所以没有精度Geohash，损失相比，使用内部52位表示。返回的geohashes具有以下特性：

他们可以缩短从右边的字符。它将失去精度，但仍将指向同一地区。

它可以在 geohash.org 网站使用，网址 http://geohash.org/<geohash-string>。查询例子：http://geohash.org/sqdtr74hyu0.

与类似的前缀字符串是附近，但相反的是不正确的，这是可能的，用不同的前缀字符串附近。
查找一个位置的时间复杂度为O(log(N))

redis> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2
redis> GEOHASH Sicily Palermo Catania
1) "sqc8b49rny0"
2) "sqdtr74hyu0"

下面是源码分析

GEOADD

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {

//参数校验
    /* Check arguments number for sanity. */
    if ((c->argc - 2) % 3 != 0) {
        /* Need an odd number of arguments if we got this far... */
        addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] "
                         "[x2] [y2] [name2] ... ");
        return;
    }

//参数提取Redis
    int elements = (c->argc - 2) / 3;
    int argc = 2+elements*2; /* ZADD key score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createRawStringObject("zadd",4);
    argv[1] = c->argv[1]; /* key */
    incrRefCount(argv[1]);

//参数遍历+转换
    /* Create the argument vector to call ZADD in order to add all
     * the score,value pairs to the requested zset, where score is actually
     * an encoded version of lat,long. */
    int i;
    for (i = 0; i < elements; i++) {
        double xy[2];

    //提取经纬度
        if (extractLongLatOrReply(c, (c->argv+2)+(i*3),xy) == C_ERR) {
            for (i = 0; i < argc; i++)
                if (argv[i]) decrRefCount(argv[i]);
            zfree(argv);
            return;
        }

    //将经纬度转换为52位的geohash作为分值 & 提取对象名称
        /* Turn the coordinates into the score of the element. */
        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[2 + i * 3 + 2];

    //设置有序集合的对象元素名称和分值
        argv[2+i*2] = score;
        argv[3+i*2] = val;
        incrRefCount(val);
    }

//调用zadd命令，存储转化好的对象
    /* Finally call ZADD that will do the work for us. */
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

通过源码分析可以看出 Redis 内部使用有序集合（ZSET）保存位置对象，有序集合中每个元素都是一个带位置的对象，元素的 Score 值为其经纬度对应的 52 位的 GEOHASH 值。

Double 类型精度为 52 位；GEOHASH 是以 base32 的方式编码，52bits 最高可存储 10 位 GEOHASH 值，对应地理区域大小为 0.6*0.6 米的格子。

换句话说经 Redis Geo 转换过的位置理论上会有约 0.3*1.414=0.424 米的误差。

算法小结

简单总结下 GEOADD 命令都干了啥：

参数提取和校验
将入参经纬度转换为 52 位的 GEOHASH 值（Score）
调用 ZADD 命令将 Member 及其对应的 Score 存入集合 Key 中。

GEORADIUS

/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
 *                               [COUNT count] [STORE key] [STORedisT key]
 * GEORADIUSBYMEMBER key member radius unit ... options ... */
void georadiusGeneric(client *c, int flags) {
    robj *key = c->argv[1];
    robj *storekey = NULL;
    int stoRedist = 0; /* 0 for STORE, 1 for STORedisT. */

//根据key获取有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

//根据用户输入（经纬度/member）确认中心点经纬度
    int base_args;
    double xy[2] = { 0 };
    if (flags & RADIUS_COORDS) {
        ……
    }

//获取查询范围距离
    double radius_meters = 0, conversion = 1;
    if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
                                                &conversion)) < 0) {
        return;
    }

//获取可选参数 （withdist、withhash、withcoords、sort、count）
    int withdist = 0, withhash = 0, withcoords = 0;
    int sort = SORT_NONE;
    long long count = 0;
    if (c->argc > base_args) {
        ... ...
    }

//获取 STORE 和 STORedisT 参数
    if (storekey && (withdist || withhash || withcoords)) {
        addReplyError(c,
            "STORE option in GEORADIUS is not compatible with "
            "WITHDIST, WITHHASH and WITHCOORDS options");
        return;
    }

//设定排序
    if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;

//利用中心点和半径计算目标区域范围
    GeoHashRadius georadius =
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);

//对中心点及其周围8个geohash网格区域进行查找，找出范围内元素对象
    geoArray *ga = geoArrayCreate();
    membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);

//未匹配返空
    /* If no matching results, the user gets an empty reply. */
    if (ga->used == 0 && storekey == NULL) {
        addReplyNull(c);
        geoArrayFree(ga);
        return;
    }

//一些返回值的设定和返回
    ……
    geoArrayFree(ga);
}

上文代码中最核心的步骤有两个，一是“计算中心点范围”，二是“对中心点及其周围 8 个 GEOHASH 网格区域进行查找”。

对应的是如下两个函数：

geohashGetAreasByRadiusWGS84
membersOfAllNeighbors

我们依次来看：

①计算中心点范围

// geohash_helper.c

/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
 *                               [COUNT count] [STORE key] [STORedisT key]
 * GEORADIUSBYMEMBER key member radius unit ... options ... */
void georadiusGeneric(client *c, int flags) {
    robj *key = c->argv[1];
    robj *storekey = NULL;
    int stoRedist = 0; /* 0 for STORE, 1 for STORedisT. */

//根据key获取有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

//根据用户输入（经纬度/member）确认中心点经纬度
    int base_args;
    double xy[2] = { 0 };
    if (flags & RADIUS_COORDS) {
        ……
    }

//获取查询范围距离
    double radius_meters = 0, conversion = 1;
    if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
                                                &conversion)) < 0) {
        return;
    }

//获取可选参数 （withdist、withhash、withcoords、sort、count）
    int withdist = 0, withhash = 0, withcoords = 0;
    int sort = SORT_NONE;
    long long count = 0;
    if (c->argc > base_args) {
        ... ...
    }

//获取 STORE 和 STORedisT 参数
    if (storekey && (withdist || withhash || withcoords)) {
        addReplyError(c,
            "STORE option in GEORADIUS is not compatible with "
            "WITHDIST, WITHHASH and WITHCOORDS options");
        return;
    }

//设定排序
    if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;

//利用中心点和半径计算目标区域范围
    GeoHashRadius georadius =
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);

//对中心点及其周围8个geohash网格区域进行查找，找出范围内元素对象
    geoArray *ga = geoArrayCreate();
    membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);

//未匹配返空
    /* If no matching results, the user gets an empty reply. */
    if (ga->used == 0 && storekey == NULL) {
        addReplyNull(c);
        geoArrayFree(ga);
        return;
    }

//一些返回值的设定和返回
    ……
    geoArrayFree(ga);
}

②对中心点及其周围 8 个 GEOHASH 网格区域进行查找
// geo.c

//在9个hashBox中获取想要的元素
int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
    GeoHashBits neighbors[9];
    unsigned int i, count = 0, last_processed = 0;
    int debugmsg = 0;

//获取9个搜索hashBox
    neighbors[0] = n.hash;
    ……
    neighbors[8] = n.neighbors.south_west;

//在每个hashBox中搜索目标点
    for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
        if (HASHISZERO(neighbors[i])) {
            if (debugmsg) D("neighbors[%d] is zero",i);
            continue;
        }

    //剔除可能的重复hashBox (搜索半径>5000KM时可能出现)
        if (last_processed &&
            neighbors[i].bits == neighbors[last_processed].bits &&
            neighbors[i].step == neighbors[last_processed].step)
        {
            continue;
        }

    //搜索hashBox中满足条件的对象    
        count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
        last_processed = i;
    }
    return count;
}


int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
//获取hashBox内的最大、最小geohash值（52位）
    GeoHashFix52Bits min, max;
    scoresOfGeoHashBox(hash,&min,&max);

//根据最大、最小geohash值筛选zobj集合中满足条件的点
    return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
}


int geoGetPointsInRange(robj *zobj, double min, double max, double lon, double lat, double radius, geoArray *ga) {

//搜索Range的参数边界设置（即9个hashBox其中一个的边界范围）
    zrangespec range = { .min = min, .max = max, .minex = 0, .maxex = 1 };
    size_t origincount = ga->used;
    sds member;

//搜索集合zobj可能有ZIPLIST和SKIPLIST两种编码方式，这里以SKIPLIST为例，逻辑是一样的
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        ……
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplist *zsl = zs->zsl;
        zskiplistNode *ln;

    //获取在hashBox范围内的首个元素（跳表数据结构，效率可比拟于二叉查找树），没有则返0
        if ((ln = zslFirstInRange(zsl, &range)) == NULL) {
            /* Nothing exists starting at our min.  No results. */
            return 0;
        }

    //从首个元素开始遍历集合
        while (ln) {
            sds ele = ln->ele;
        //遍历元素超出range范围则break
            /* Abort when the node is no longer in range. */
            if (!zslValueLteMax(ln->score, &range))
                break;
        //元素校验（计算元素与中心点的距离）
            ele = sdsdup(ele);
            if (geoAppendIfWithinRadius(ga,lon,lat,radius,ln->score,ele)
                == C_ERR) sdsfree(ele);
            ln = ln->level[0].forward;
        }
    }
    return ga->used - origincount;
}

int geoAppendIfWithinRadius(geoArray *ga, double lon, double lat, double radius, double score, sds member) {
    double distance, xy[2];

//解码错误, 返回error
    if (!decodeGeohash(score,xy)) return C_ERR; /* Can't decode. */

//最终距离校验(计算球面距离distance看是否小于radius)
    if (!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
                                           radius, &distance))
    {
        return C_ERR;
    }

//构建并返回满足条件的元素
    geoPoint *gp = geoArrayAppend(ga);
    gp->longitude = xy[0];
    gp->latitude = xy[1];
    gp->dist = distance;
    gp->member = member;
    gp->score = score;
    return C_OK;
}

算法小结

抛开众多可选参数不谈，简单总结下 GEORADIUS 命令是怎么利用 GEOHASH 获取目标位置对象的：

参数提取和校验。
利用中心点和输入半径计算待查区域范围。这个范围参数包括满足条件的最高的 GEOHASH 网格等级（精度）以及对应的能够覆盖目标区域的九宫格位置（后续会有详细说明）。
对九宫格进行遍历，根据每个 GEOHASH 网格的范围框选出位置对象。进一步找出与中心点距离小于输入半径的对象，进行返回。

直接描述不太好理解，我们通过如下两张图再对算法进行简单的演示：

令左图的中心为搜索中心，绿色圆形区域为目标区域，所有点为待搜索的位置对象，红色点则为满足条件的位置对象。

在实际搜索时,首先会根据搜索半径计算 GEOHASH 网格等级（即右图中网格大小等级），并确定九宫格位置（即红色九宫格位置信息）。

再依次查找计算九宫格中的点（蓝点和红点）与中心点的距离，最终筛选出距离范围内的点（红点）。

算法分析

为什么要用这种算法策略进行查询，或者说这种策略的优势在哪，让我们以问答的方式进行分析说明。

①为什么要找到满足条件的最高的 GEOHASH 网格等级？为什么用九宫格？

这其实是一个问题，本质上是对所有的元素对象进行了一次初步筛选。在多层 GEOHASH 网格中，每个低等级的 GEOHASH 网格都是由 4 个高一级的网格拼接而成（如图）。

换句话说，GEOHASH 网格等级越高，所覆盖的地理位置范围就越小。当我们根据输入半径和中心点位置计算出的能够覆盖目标区域的最高等级的九宫格（网格）时，就已经对九宫格外的元素进行了筛除。

这里之所以使用九宫格，而不用单个网格，主要原因还是为了避免边界情况，尽可能缩小查询区域范围。试想以 0 经纬度为中心，就算查 1 米范围，单个网格覆盖的话也得查整个地球区域。而向四周八个方向扩展一圈可有效避免这个问题。

②如何通过 GEOHASH 网格的范围框选出元素对象？效率如何？

首先在每个 GEOHASH 网格中的 GEOHASH 值都是连续的，有固定范围。所以只要找出有序集合中，处在该范围的位置对象即可。

以下是有序集合的跳表数据结构：

其拥有类似二叉查找树的查询效率，操作平均时间复杂性为 O(log(N))。且最底层的所有元素都以链表的形式按序排列。
所以在查询时，只要找到集合中处在目标 GEOHASH 网格中的第一个值，后续依次对比即可，不用多次查找。九宫格不能一起查，要一个个遍历的原因也在于九宫格各网格对应的 GEOHASH 值不具有连续性。
只有连续了，查询效率才会高，不然要多做许多距离运算。
综上，我们从源码角度解析了 Redis Geo 模块中 “增（GEOADD）” 和 “查（GEORADIUS）” 的详细过程。并可推算出 Redis 中 GEORADIUS 查找附近的人功能，时间复杂度为：O(N+log(M))。
其中 N 为指定半径范围内的位置元素数量，而 M 则是被九宫格圈住计算距离的元素的数量。
结合 Redis 本身基于内存的存储特性，在实际使用过程中有非常高的运行效率。

用 Redis 高效实现GEO地理位置相关功能

应用

GEOADD

GEOPOS

GEODIST

GEORADIUS

GEORADIUSBYMEMBER

GEOHASH

下面是源码分析

GEOADD

简单总结下 GEOADD 命令都干了啥：

GEORADIUS

对应的是如下两个函数：

抛开众多可选参数不谈，简单总结下 GEORADIUS 命令是怎么利用 GEOHASH 获取目标位置对象的：

直接描述不太好理解，我们通过如下两张图再对算法进行简单的演示：

以下是有序集合的跳表数据结构：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

技术分享