Redis 到底是怎么實(shí)現(xiàn)“附近的人”這個(gè)功能的呢？
前言：針對(duì)“附近的人”這一位置服務(wù)領(lǐng)域的應(yīng)用場(chǎng)景，常見(jiàn)的可使用PG、MySQL和MongoDB等多種DB的空間索引進(jìn)行實(shí)現(xiàn)。而Redis另辟蹊徑，結(jié)合其有序隊(duì)列zset以及geohash編碼，實(shí)現(xiàn)了空間搜索功能，且擁有極高的運(yùn)行效率。
本文將從源碼角度對(duì)其算法原理進(jìn)行解析，并推算查詢(xún)時(shí)間復(fù)雜度。
要提供完整的“附近的人”服務(wù)，最基本的是要實(shí)現(xiàn)“增”、“刪”、“查”的功能。以下將分別進(jìn)行介紹，其中會(huì)重點(diǎn)對(duì)查詢(xún)功能進(jìn)行解析。
操作命令
自Redis 3.2開(kāi)始，Redis基于geohash和有序集合提供了地理位置相關(guān)功能。Redis Geo模塊包含了以下6個(gè)命令：
GEOADD: 將給定的位置對(duì)象（緯度、經(jīng)度、名字）添加到指定的key;
GEOPOS: 從key里面返回所有給定位置對(duì)象的位置（經(jīng)度和緯度）;
GEODIST: 返回兩個(gè)給定位置之間的距離;
GEOHASH: 返回一個(gè)或多個(gè)位置對(duì)象的Geohash表示;
GEORADIUS: 以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過(guò)給定最大距離的所有位置對(duì)象;
GEORADIUSBYMEMBER: 以給定的位置對(duì)象為中心，返回與其距離不超過(guò)給定最大距離的所有位置對(duì)象。
其中，組合使用GEOADD和GEORADIUS可實(shí)現(xiàn)“附近的人”中“增”和“查”的基本功能。
要實(shí)現(xiàn)微信中“附近的人”功能，可直接使用GEORADIUSBYMEMBER命令。其中“給定的位置對(duì)象”即為用戶(hù)本人，搜索的對(duì)象為其他用戶(hù)。
不過(guò)本質(zhì)上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用戶(hù)位置再通過(guò)該位置搜索附近滿(mǎn)足位置相互距離條件的其他用戶(hù)對(duì)象。
以下會(huì)從源碼角度入手對(duì)GEOADD和GEORADIUS命令進(jìn)行分析，剖析其算法原理。
Redis geo操作中只包含了“增”和“查”的操作，并沒(méi)有專(zhuān)門(mén)的“刪除”命令。主要是因?yàn)镽edis內(nèi)部使用有序集合(zset)保存位置對(duì)象，可用zrem進(jìn)行刪除。
在Redis源碼geo.c的文件注釋中，只說(shuō)明了該文件為GEOADD、GEORADIUS和GEORADIUSBYMEMBER的實(shí)現(xiàn)文件（其實(shí)在也實(shí)現(xiàn)了另三個(gè)命令）。從側(cè)面看出其他三個(gè)命令為輔助命令。
使用方式
GEOADD key longitude latitude member [longitude latitude member ...]
將給定的位置對(duì)象（緯度、經(jīng)度、名字）添加到指定的key。
其中，key為集合名稱(chēng)，member為該經(jīng)緯度所對(duì)應(yīng)的對(duì)象。在實(shí)際運(yùn)用中，當(dāng)所需存儲(chǔ)的對(duì)象數(shù)量過(guò)多時(shí)，可通過(guò)設(shè)置多key(如一個(gè)省一個(gè)key)的方式對(duì)對(duì)象集合變相做sharding，避免單集合數(shù)量過(guò)多。
成功插入后的返回值：
(integer) N
其中N為成功插入的個(gè)數(shù)。
源碼分析
/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
//參數(shù)校驗(yàn)
/* 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;
}
//參數(shù)提取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]);
//參數(shù)遍歷+轉(zhuǎn)換
/* 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];
//提取經(jīng)緯度
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;
}
//將經(jīng)緯度轉(zhuǎn)換為52位的geohash作為分值 & 提取對(duì)象名稱(chēng)
/* 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];
//設(shè)置有序集合的對(duì)象元素名稱(chēng)和分值
argv[2+i*2] = score;
argv[3+i*2] = val;
incrRefCount(val);
}
//調(diào)用zadd命令，存儲(chǔ)轉(zhuǎn)化好的對(duì)象
/* Finally call ZADD that will do the work for us. */
replaceClientCommandVector(c,argc,argv);
zaddCommand(c);
}
通過(guò)源碼分析可以看出Redis內(nèi)部使用有序集合(zset)保存位置對(duì)象，有序集合中每個(gè)元素都是一個(gè)帶位置的對(duì)象，元素的score值為其經(jīng)緯度對(duì)應(yīng)的52位的geohash值。
double類(lèi)型精度為52位；
geohash是以base32的方式編碼，52bits最高可存儲(chǔ)10位geohash值，對(duì)應(yīng)地理區(qū)域大小為0.60.6米的格子。換句話(huà)說(shuō)經(jīng)Redis geo轉(zhuǎn)換過(guò)的位置理論上會(huì)有約0.31.414=0.424米的誤差。
簡(jiǎn)單總結(jié)下GEOADD命令都干了啥：
1、參數(shù)提取和校驗(yàn)；
2、將入?yún)⒔?jīng)緯度轉(zhuǎn)換為52位的geohash值（score）；
3、調(diào)用ZADD命令將member及其對(duì)應(yīng)的score存入集合key中。
GEORADIUS
使用方式
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]
以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過(guò)給定最大距離的所有位置對(duì)象。
范圍單位：m | km | ft | mi --> 米 | 千米 | 英尺 | 英里
額外參數(shù)：
- WITHDIST：在返回位置對(duì)象的同時(shí)，將位置對(duì)象與中心之間的距離也一并返回。距離的單位和用戶(hù)給定的范圍單位保持一致。
- WITHCOORD：將位置對(duì)象的經(jīng)度和維度也一并返回。
- WITHHASH：以 52 位有符號(hào)整數(shù)的形式，返回位置對(duì)象經(jīng)過(guò)原始 geohash 編碼的有序集合分值。這個(gè)選項(xiàng)主要用于底層應(yīng)用或者調(diào)試，實(shí)際中的作用并不大。
- ASC|DESC：從近到遠(yuǎn)返回位置對(duì)象元素 | 從遠(yuǎn)到近返回位置對(duì)象元素。- COUNT count：選取前N個(gè)匹配位置對(duì)象元素。（不設(shè)置則返回所有元素） - STORE key：將返回結(jié)果的地理位置信息保存到指定key。- STORedisT key：將返回結(jié)果離中心點(diǎn)的距離保存到指定key。
由于 STORE 和 STORedisT 兩個(gè)選項(xiàng)的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技術(shù)上會(huì)被標(biāo)記為寫(xiě)入命令，從而只會(huì)查詢(xún)（寫(xiě)入）主實(shí)例，QPS過(guò)高時(shí)容易造成主實(shí)例讀寫(xiě)壓力過(guò)大。
為解決這個(gè)問(wèn)題，在 Redis 3.2.10 和 Redis 4.0.0 中，分別新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO兩個(gè)只讀命令。
不過(guò)，在實(shí)際開(kāi)發(fā)中筆者發(fā)現(xiàn) 在java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 參數(shù)類(lèi)中并不包含 STORE 和 STORedisT 兩個(gè)參數(shù)選項(xiàng)，在調(diào)用georadius時(shí)是否真的只查詢(xún)了主實(shí)例，還是進(jìn)行了只讀封裝。感興趣的朋友可以自己研究下。
成功查詢(xún)后的返回值：
不帶WITH限定，返回一個(gè)member list，如：
["member1","member2","member3"]
帶WITH限定，member list中每個(gè)member也是一個(gè)嵌套list，如：
[
["member1", distance1, [longitude1, latitude1]]
["member2", distance2, [longitude2, latitude2]]
]
源碼分析
注：此段源碼較長(zhǎng)，看不下去的可直接看中文注釋?zhuān)蛑苯犹叫〗Y(jié)部分
/* 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. */
//根據(jù)key獲取有序集合
robj *zobj = NULL;
if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
checkType(c, zobj, OBJ_ZSET)) {
return;
}
//根據(jù)用戶(hù)輸入（經(jīng)緯度/member）確認(rèn)中心點(diǎn)經(jīng)緯度
int base_args;
double xy[2] = { 0 };
if (flags & RADIUS_COORDS) {
……
}
//獲取查詢(xún)范圍距離
double radius_meters = 0, conversion = 1;
if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
&conversion)) < 0) {
return;
}
//獲取可選參數(shù) （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 參數(shù)
if (storekey && (withdist || withhash || withcoords)) {
addReplyError(c,
"STORE option in GEORADIUS is not compatible with "
"WITHDIST, WITHHASH and WITHCOORDS options");
return;
}
//設(shè)定排序
if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;
//利用中心點(diǎn)和半徑計(jì)算目標(biāo)區(qū)域范圍
GeoHashRadius georadius =
geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
//對(duì)中心點(diǎn)及其周?chē)?個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找，找出范圍內(nèi)元素對(duì)象
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;
}
//一些返回值的設(shè)定和返回
……
geoArrayFree(ga);
}
上文代碼中最核心的步驟有兩個(gè)，一是“計(jì)算中心點(diǎn)范圍”，二是“對(duì)中心點(diǎn)及其周?chē)?個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找”。
對(duì)應(yīng)的是geohashGetAreasByRadiusWGS84和membersOfAllNeighbors兩個(gè)函數(shù)。
我們依次來(lái)看：
計(jì)算中心點(diǎn)范圍：
// geohash_helper.c
GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
double radius_meters) {
return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}
//返回能夠覆蓋目標(biāo)區(qū)域范圍的9個(gè)geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
//一些參數(shù)設(shè)置
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;
//計(jì)算目標(biāo)區(qū)域外接矩形的經(jīng)緯度范圍（目標(biāo)區(qū)域?yàn)椋阂阅繕?biāo)經(jīng)緯度為中心，半徑為指定距離的圓）
geohashBoundingBox(longitude, latitude, radius_meters, bounds);
min_lon = bounds[0];
min_lat = bounds[1];
max_lon = bounds[2];
max_lat = bounds[3];
//根據(jù)目標(biāo)區(qū)域中心點(diǎn)緯度和半徑，計(jì)算帶查詢(xún)的9個(gè)搜索框的geohash精度（位）
//這里用到latitude主要是針對(duì)極地的情況對(duì)精度進(jìn)行了一些調(diào)整（緯度越高，位數(shù)越小）
steps = geohashEstimateStepsByRadius(radius_meters,latitude);
//設(shè)置經(jīng)緯度最大最小值：-180<=longitude<=180, -85<=latitude<=85
geohashGetCoordRange(&long_range,&lat_range);
//將待查經(jīng)緯度按指定精度（steps）編碼成geohash值
geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
//將geohash值在8個(gè)方向上進(jìn)行擴(kuò)充，確定周?chē)?個(gè)Box（neighbors）
geohashNeighbors(&hash,&neighbors);
//根據(jù)hash值確定area經(jīng)緯度范圍
geohashDecode(long_range,lat_range,hash,&area);
//一些特殊情況處理
……
//構(gòu)建并返回結(jié)果
radius.hash = hash;
radius.neighbors = neighbors;
radius.area = area;
return radius;
}
對(duì)中心點(diǎn)及其周?chē)?個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找:
// geo.c
//在9個(gè)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個(gè)搜索hashBox
neighbors[0] = n.hash;
……
neighbors[8] = n.neighbors.south_west;
//在每個(gè)hashBox中搜索目標(biāo)點(diǎn)
for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
if (HASHISZERO(neighbors[i])) {
if (debugmsg) D("neighbors[%d] is zero",i);
continue;
}
//剔除可能的重復(fù)hashBox (搜索半徑>5000KM時(shí)可能出現(xiàn))
if (last_processed &&
neighbors[i].bits == neighbors[last_processed].bits &&
neighbors[i].step == neighbors[last_processed].step)
{
continue;
}
//搜索hashBox中滿(mǎn)足條件的對(duì)象
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內(nèi)的最大、最小geohash值（52位）
GeoHashFix52Bits min, max;
scoresOfGeoHashBox(hash,&min,&max);
//根據(jù)最大、最小geohash值篩選zobj集合中滿(mǎn)足條件的點(diǎn)
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的參數(shù)邊界設(shè)置（即9個(gè)hashBox其中一個(gè)的邊界范圍）
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范圍內(nèi)的首個(gè)元素（跳表數(shù)據(jù)結(jié)構(gòu)，效率可比擬于二叉查找樹(shù)），沒(méi)有則返0
if ((ln = zslFirstInRange(zsl, &range)) == NULL) {
/* Nothing exists starting at our min. No results. */
return 0;
}
//從首個(gè)元素開(kāi)始遍歷集合
while (ln) {
sds ele = ln->ele;
//遍歷元素超出range范圍則break
/* Abort when the node is no longer in range. */
if (!zslValueLteMax(ln->score, &range))
break;
//元素校驗(yàn)（計(jì)算元素與中心點(diǎn)的距離）
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];
//解碼錯(cuò)誤, 返回error
if (!decodeGeohash(score,xy)) return C_ERR; /* Can't decode. */
//最終距離校驗(yàn)(計(jì)算球面距離distance看是否小于radius)
if (!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
radius, &distance))
{
return C_ERR;
}
//構(gòu)建并返回滿(mǎn)足條件的元素
geoPoint *gp = geoArrayAppend(ga);
gp->longitude = xy[0];
gp->latitude = xy[1];
gp->dist = distance;
gp->member = member;
gp->score = score;
return C_OK;
}
算法小結(jié)
拋開(kāi)眾多可選參數(shù)不談，簡(jiǎn)單總結(jié)下GEORADIUS命令是怎么利用geohash獲取目標(biāo)位置對(duì)象的：
1、參數(shù)提取和校驗(yàn)；
2、利用中心點(diǎn)和輸入半徑計(jì)算待查區(qū)域范圍。這個(gè)范圍參數(shù)包括滿(mǎn)足條件的最高的geohash網(wǎng)格等級(jí)(精度) 以及 對(duì)應(yīng)的能夠覆蓋目標(biāo)區(qū)域的九宮格位置；（后續(xù)會(huì)有詳細(xì)說(shuō)明）
3、對(duì)九宮格進(jìn)行遍歷，根據(jù)每個(gè)geohash網(wǎng)格的范圍框選出位置對(duì)象。進(jìn)一步找出與中心點(diǎn)距離小于輸入半徑的對(duì)象，進(jìn)行返回。
直接描述不太好理解，我們通過(guò)如下兩張圖在對(duì)算法進(jìn)行簡(jiǎn)單的演示：
令左圖的中心為搜索中心，綠色圓形區(qū)域?yàn)槟繕?biāo)區(qū)域，所有點(diǎn)為待搜索的位置對(duì)象，紅色點(diǎn)則為滿(mǎn)足條件的位置對(duì)象。
在實(shí)際搜索時(shí),首先會(huì)根據(jù)搜索半徑計(jì)算geohash網(wǎng)格等級(jí)（即右圖中網(wǎng)格大小等級(jí)），并確定九宮格位置（即紅色九宮格位置信息）；再依次查找計(jì)算九宮格中的點(diǎn)（藍(lán)點(diǎn)和紅點(diǎn)）與中心點(diǎn)的距離，最終篩選出距離范圍內(nèi)的點(diǎn)（紅點(diǎn)）。
算法分析
為什么要用這種算法策略進(jìn)行查詢(xún)，或者說(shuō)這種策略的優(yōu)勢(shì)在哪，讓我們以問(wèn)答的方式進(jìn)行分析說(shuō)明。
為什么要找到滿(mǎn)足條件的最高的geohash網(wǎng)格等級(jí)？為什么用九宮格？
這其實(shí)是一個(gè)問(wèn)題，本質(zhì)上是對(duì)所有的元素對(duì)象進(jìn)行了一次初步篩選。在多層geohash網(wǎng)格中，每個(gè)低等級(jí)的geohash網(wǎng)格都是由4個(gè)高一級(jí)的網(wǎng)格拼接而成（如圖）。
換句話(huà)說(shuō)，geohash網(wǎng)格等級(jí)越高，所覆蓋的地理位置范圍就越小。當(dāng)我們根據(jù)輸入半徑和中心點(diǎn)位置計(jì)算出的能夠覆蓋目標(biāo)區(qū)域的最高等級(jí)的九宮格（網(wǎng)格）時(shí)，就已經(jīng)對(duì)九宮格外的元素進(jìn)行了篩除。
這里之所以使用九宮格，而不用單個(gè)網(wǎng)格，主要原因還是為了避免邊界情況，盡可能縮小查詢(xún)區(qū)域范圍。試想以0經(jīng)緯度為中心，就算查1米范圍，單個(gè)網(wǎng)格覆蓋的話(huà)也得查整個(gè)地球區(qū)域。而向四周八個(gè)方向擴(kuò)展一圈可有效避免這個(gè)問(wèn)題。
如何通過(guò)geohash網(wǎng)格的范圍框選出元素對(duì)象？效率如何？
首先在每個(gè)geohash網(wǎng)格中的geohash值都是連續(xù)的，有固定范圍。所以只要找出有序集合中，處在該范圍的位置對(duì)象即可。以下是有序集合的跳表數(shù)據(jù)結(jié)構(gòu)：
其擁有類(lèi)似二叉查找樹(shù)的查詢(xún)效率，操作平均時(shí)間復(fù)雜性為O(log(N))。且最底層的所有元素都以鏈表的形式按序排列。
所以在查詢(xún)時(shí)，只要找到集合中處在目標(biāo)geohash網(wǎng)格中的第一個(gè)值，后續(xù)依次對(duì)比即可，不用多次查找。
九宮格不能一起查，要一個(gè)個(gè)遍歷的原因也在于九宮格各網(wǎng)格對(duì)應(yīng)的geohash值不具有連續(xù)性。只有連續(xù)了，查詢(xún)效率才會(huì)高，不然要多做許多距離運(yùn)算。
綜上，我們從源碼角度解析了Redis Geo模塊中 “增（GEOADD）” 和 “查（GEORADIUS）” 的詳細(xì)過(guò)程。并可推算出Redis中GEORADIUS查找附近的人功能，時(shí)間復(fù)雜度為：O(N+log(M))
其中N為指定半徑范圍內(nèi)的位置元素?cái)?shù)量，而M則是被九宮格圈住計(jì)算距離的元素的數(shù)量。結(jié)合Redis本身基于內(nèi)存的存儲(chǔ)特性，在實(shí)際使用過(guò)程中有非常高的運(yùn)行效率
往期推薦
關(guān)注我回復(fù)「加群」，加入Spring技術(shù)交流群