关于java:简单几步实现-Redis-查询-附近的人

前言：针对“左近的人”这一位置服务畛域的利用场景，常见的可应用PG、MySQL和MongoDB等多种DB的空间索引进行实现。而Redis另辟蹊径，联合其有序队列zset以及geohash编码，实现了空间搜寻性能，且领有极高的运行效率。

本文将从源码角度对其算法原理进行解析，并推算查问工夫复杂度。

要提供残缺的“左近的人”服务，最根本的是要实现“增”、“删”、“查”的性能。以下将别离进行介绍，其中会重点对查问性能进行解析。

操作命令

自Redis 3.2开始，Redis基于geohash和有序汇合提供了地理位置相干性能。Redis Geo模块蕴含了以下6个命令：

GEOADD: 将给定的地位对象（纬度、经度、名字）增加到指定的key;
GEOPOS: 从key外面返回所有给定地位对象的地位（经度和纬度）;
GEODIST: 返回两个给定地位之间的间隔;
GEOHASH: 返回一个或多个地位对象的Geohash示意;
GEORADIUS: 以给定的经纬度为核心，返回指标汇合中与核心的间隔不超过给定最大间隔的所有地位对象;
GEORADIUSBYMEMBER: 以给定的地位对象为核心，返回与其间隔不超过给定最大间隔的所有地位对象。

其中，组合应用GEOADD和GEORADIUS可实现“左近的人”中“增”和“查”的基本功能。

要实现微信中“左近的人”性能，可间接应用GEORADIUSBYMEMBER命令。其中“给定的地位对象”即为用户自己，搜寻的对象为其余用户。

不过实质上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用户地位再通过该地位搜寻左近满足地位互相间隔条件的其余用户对象。

以下会从源码角度动手对GEOADD和GEORADIUS命令进行剖析，分析其算法原理。

Redis geo操作中只蕴含了“增”和“查”的操作，并没有专门的“删除”命令。次要是因为Redis外部应用有序汇合(zset)保留地位对象，可用zrem进行删除。

在Redis源码geo.c的文件正文中，只阐明了该文件为GEOADD、GEORADIUS和GEORADIUSBYMEMBER的实现文件（其实在也实现了另三个命令）。从侧面看出其余三个命令为辅助命令。

GEOADD

应用形式

GEOADD key longitude latitude member [longitude latitude member ...]

将给定的地位对象（纬度、经度、名字）增加到指定的key。

其中，key为汇合名称，member为该经纬度所对应的对象。在理论使用中，当所需存储的对象数量过多时，可通过设置多key(如一个省一个key)的形式对对象汇合变相做sharding，防止单汇合数量过多。

胜利插入后的返回值：

(integer) N

其中N为胜利插入的个数。

源码剖析

/* 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.60.6米的格子。换句话说经Redis geo转换过的地位实践上会有约0.31.414=0.424米的误差。

算法小结

简略总结下GEOADD命令都干了啥：
1、参数提取和校验；
2、将入参经纬度转换为52位的geohash值（score）；
3、调用ZADD命令将member及其对应的score存入汇合key中。

GEORADIUS

应用形式

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]

以给定的经纬度为核心，返回指标汇合中与核心的间隔不超过给定最大间隔的所有地位对象。

范畴单位：m | km | ft | mi –> 米 | 千米 | 英尺 | 英里

额定参数：

WITHDIST：在返回地位对象的同时，将地位对象与核心之间的间隔也一并返回。间隔的单位和用户给定的范畴单位保持一致。
WITHCOORD：将地位对象的经度和维度也一并返回。
WITHHASH：以 52 位有符号整数的模式，返回地位对象通过原始 geohash 编码的有序汇合分值。这个选项次要用于底层利用或者调试，理论中的作用并不大。
ASC|DESC：从近到远返回地位对象元素 | 从远到近返回地位对象元素。- COUNT count：选取前N个匹配地位对象元素。（不设置则返回所有元素） – STORE key：将返回后果的地理位置信息保留到指定key。- STORedisT key：将返回后果离中心点的间隔保留到指定key。

因为 STORE 和 STORedisT 两个选项的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技术上会被标记为写入命令，从而只会查问（写入）主实例，QPS过高时容易造成主实例读写压力过大。

为解决这个问题，在 Redis 3.2.10 和 Redis 4.0.0 中，别离新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO两个只读命令。

不过，在理论开发中笔者发现在java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 参数类中并不蕴含 STORE 和 STORedisT 两个参数选项，在调用georadius时是否真的只查问了主实例，还是进行了只读封装。感兴趣的敌人能够本人钻研下。

胜利查问后的返回值：

不带WITH限定，返回一个member list，如：

["member1","member2","member3"]

带WITH限定，member list中每个member也是一个嵌套list，如：

[ ["member1", distance1, [longitude1, latitude1]] ["member2", distance2, [longitude2, latitude2]]]

源码剖析

此段源码较长，看不下去的可间接看中文正文，或间接跳到小结局部

/* 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

GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
                                           double radius_meters) {
    return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}

//返回可能笼罩指标区域范畴的9个geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
//一些参数设置
    GeoHashRange long_range, lat_range;
    GeoHashRadius radius;
    GeoHashBits hash;
    GeoHashNeighbors neighbors;
    GeoHashArea area;
    double min_lon, max_lon, min_lat, max_lat;
    double bounds[4];
    int steps;

//计算指标区域外接矩形的经纬度范畴（指标区域为：以指标经纬度为核心，半径为指定间隔的圆）
    geohashBoundingBox(longitude, latitude, radius_meters, bounds);
    min_lon = bounds[0];
    min_lat = bounds[1];
    max_lon = bounds[2];
    max_lat = bounds[3];

//依据指标区域中心点纬度和半径，计算带查问的9个搜寻框的geohash精度（位）
//这里用到latitude次要是针对极地的状况对精度进行了一些调整（纬度越高，位数越小）
    steps = geohashEstimateStepsByRadius(radius_meters,latitude);

//设置经纬度最大最小值：-180<=longitude<=180, -85<=latitude<=85
    geohashGetCoordRange(&long_range,&lat_range);
    
//将待查经纬度按指定精度（steps）编码成geohash值
    geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
    
//将geohash值在8个方向上进行裁减，确定四周8个Box（neighbors）
    geohashNeighbors(&hash,&neighbors);
    
//依据hash值确定area经纬度范畴
    geohashDecode(long_range,lat_range,hash,&area);

//一些非凡状况解决
    ……

//构建并返回后果    
    radius.hash = hash;
    radius.neighbors = neighbors;
    radius.area = area;
    return radius;
}

对中心点及其四周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获取指标地位对象的：

1、参数提取和校验；

2、利用中心点和输出半径计算待查区域范畴。这个范畴参数包含满足条件的最高的geohash网格等级(精度) 以及对应的可能笼罩指标区域的九宫格地位；（后续会有具体阐明）

3、对九宫格进行遍历，依据每个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自身基于内存的存储个性，在理论应用过程中有十分高的运行效率。

关于java:简单几步实现-Redis-查询-附近的人

操作命令

GEOADD

应用形式

源码剖析

算法小结

GEORADIUS

应用形式

源码剖析

算法小结

算法剖析

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:简单几步实现-Redis-查询-附近的人

操作命令

GEOADD

应用形式

源码剖析

算法小结

GEORADIUS

应用形式

源码剖析

算法小结

算法剖析

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复