共计 10140 个字符，预计需要花费 26 分钟才能阅读完成。
前言：针对“左近的人”这一位置服务畛域的利用场景，常见的可应用 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 自身基于内存的存储个性，在理论应用过程中有十分高的运行效率。