針對“附近的人”這一位置服務(wù)領(lǐng)域的應(yīng)用場景，常見的可使用PG、MySQL和MongoDB等多種DB的空間索引進(jìn)行實(shí)現(xiàn)。而redis另辟蹊徑，結(jié)合其有序隊(duì)列zset以及geohash編碼，實(shí)現(xiàn)了空間搜索功能，且擁有極高的運(yùn)行效率。本文將從源碼角度對其算法原理進(jìn)行解析，并推算查詢時(shí)間復(fù)雜度。
專注于為中小企業(yè)提供網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)郊區(qū)免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了成百上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
要提供完整的“附近的人”服務(wù)，最基本的是要實(shí)現(xiàn)“增”、“刪”、“查”的功能。以下將分別進(jìn)行介紹，其中會重點(diǎn)對查詢功能進(jìn)行解析。
自Redis 3.2開始，Redis基于geohash和有序集合提供了地理位置相關(guān)功能。 Redis Geo模塊包含了以下6個(gè)命令：
GEOADD: 將給定的位置對象（緯度、經(jīng)度、名字）添加到指定的key;
GEOPOS: 從key里面返回所有給定位置對象的位置（經(jīng)度和緯度）;
GEODIST: 返回兩個(gè)給定位置之間的距離;
GEOHASH: 返回一個(gè)或多個(gè)位置對象的Geohash表示;
GEORADIUS: 以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過給定最大距離的所有位置對象;
GEORADIUSBYMEMBER: 以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。
其中，組合使用GEOADD和GEORADIUS可實(shí)現(xiàn)“附近的人”中“增”和“查”的基本功能。要實(shí)現(xiàn)微信中“附近的人”功能，可直接使用GEORADIUSBYMEMBER命令。其中“給定的位置對象”即為用戶本人，搜索的對象為其他用戶。不過本質(zhì)上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用戶位置再通過該位置搜索附近滿足位置相互距離條件的其他用戶對象。
以下會從源碼角度入手對GEOADD和GEORADIUS命令進(jìn)行分析，剖析其算法原理。
Redis geo操作中只包含了“增”和“查”的操作，并沒有專門的“刪除”命令。主要是因?yàn)镽edis內(nèi)部使用有序集合(zset)保存位置對象，可用zrem進(jìn)行刪除。
在Redis源碼geo.c的文件注釋中，只說明了該文件為GEOADD、GEORADIUS和GEORADIUSBYMEMBER的實(shí)現(xiàn)文件（其實(shí)在也實(shí)現(xiàn)了另三個(gè)命令）。從側(cè)面看出其他三個(gè)命令為輔助命令。
使用方式
GEOADD?key?longitude?latitude?member?[longitude?latitude?member?...]
將給定的位置對象（緯度、經(jīng)度、名字）添加到指定的key。
其中，key為集合名稱，member為該經(jīng)緯度所對應(yīng)的對象。在實(shí)際運(yùn)用中，當(dāng)所需存儲的對象數(shù)量過多時(shí)，可通過設(shè)置多key(如一個(gè)省一個(gè)key)的方式對對象集合變相做sharding，避免單集合數(shù)量過多。
成功插入后的返回值：
(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?argv+2)+(i*3),xy)?==?C_ERR)?{
?for?(i?=?0;?i?argv[2?+?i?*?3?+?2];?//設(shè)置有序集合的對象元素名稱和分值
?argv[2+i*2]?=?score;
?argv[3+i*2]?=?val;
?incrRefCount(val);
?}//調(diào)用zadd命令，存儲轉(zhuǎn)化好的對象
?/*?Finally?call?ZADD?that?will?do?the?work?for?us.?*/
?replaceClientCommandVector(c,argc,argv);
?zaddCommand(c);
}通過源碼分析可以看出Redis內(nèi)部使用有序集合(zset)保存位置對象，有序集合中每個(gè)元素都是一個(gè)帶位置的對象，元素的score值為其經(jīng)緯度對應(yīng)的52位的geohash值。
double類型精度為52位；
geohash是以base32的方式編碼，52bits最高可存儲10位geohash值，對應(yīng)地理區(qū)域大小為0.6*0.6米的格子。換句話說經(jīng)Redis geo轉(zhuǎn)換過的位置理論上會有約0.3*1.414=0.424米的誤差。
算法小結(jié)
簡單總結(jié)下GEOADD命令都干了啥：
1、參數(shù)提取和校驗(yàn)；
2、將入?yún)⒔?jīng)緯度轉(zhuǎn)換為52位的geohash值（score）；
3、調(diào)用ZADD命令將member及其對應(yīng)的score存入集合key中。
使用方式
GEORADIUS?key?longitude?latitude?radius?m|km|ft|mi?[WITHCOORD]?[WITHDIST]?[WITHHASH]?[ASC|DESC]?[COUNT?count]?[STORE?key]?[STORedisT?key]
以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過給定最大距離的所有位置對象。
范圍單位：m | km | ft | mi --> 米 | 千米 | 英尺 | 英里
額外參數(shù)：
- WITHDIST：在返回位置對象的同時(shí)，將位置對象與中心之間的距離也一并返回。距離的單位和用戶給定的范圍單位保持一致。
- WITHCOORD：將位置對象的經(jīng)度和維度也一并返回。
- WITHHASH：以 52 位有符號整數(shù)的形式，返回位置對象經(jīng)過原始 geohash 編碼的有序集合分值。這個(gè)選項(xiàng)主要用于底層應(yīng)用或者調(diào)試，實(shí)際中的作用并不大。
- ASC|DESC：從近到遠(yuǎn)返回位置對象元素 | 從遠(yuǎn)到近返回位置對象元素。 - COUNT count：選取前N個(gè)匹配位置對象元素。（不設(shè)置則返回所有元素） - STORE key：將返回結(jié)果的地理位置信息保存到指定key。 - STORedisT key：將返回結(jié)果離中心點(diǎn)的距離保存到指定key。
由于 STORE 和 STORedisT 兩個(gè)選項(xiàng)的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技術(shù)上會被標(biāo)記為寫入命令，從而只會查詢（寫入）主實(shí)例，QPS過高時(shí)容易造成主實(shí)例讀寫壓力過大。 為解決這個(gè)問題，在 Redis 3.2.10 和 Redis 4.0.0 中，分別新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO兩個(gè)只讀命令。
不過，在實(shí)際開發(fā)中筆者發(fā)現(xiàn) 在java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 參數(shù)類中并不包含 STORE 和 STORedisT 兩個(gè)參數(shù)選項(xiàng)，在調(diào)用georadius時(shí)是否真的只查詢了主實(shí)例，還是進(jìn)行了只讀封裝。感興趣的朋友可以自己研究下。
成功查詢后的返回值：
不帶WITH限定，返回一個(gè)member list，如：
["member1","member2","member3"]
帶WITH限定，member list中每個(gè)member也是一個(gè)嵌套list，如：
[ ["member1",?distance1,?[longitude1,?latitude1]] ["member2",?distance2,?[longitude2,?latitude2]] ]
源碼分析
此段源碼較長，看不下去的可直接看中文注釋，或直接跳到小結(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ù)用戶輸入（經(jīng)緯度/member）確認(rèn)中心點(diǎn)經(jīng)緯度
?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))?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);//對中心點(diǎn)及其周圍8個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找，找出范圍內(nèi)元素對象
?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)范圍”，二是“對中心點(diǎn)及其周圍8個(gè)geohash網(wǎng)格區(qū)域進(jìn)行查找”。對應(yīng)的是geohashGetAreasByRadiusWGS84和membersOfAllNeighbors兩個(gè)函數(shù)。我們依次來看：
計(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è)geohashBoxGeoHashRadius?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ì)算帶查詢的9個(gè)搜索框的geohash精度（位）//這里用到latitude主要是針對極地的情況對精度進(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ò)充，確定周圍8個(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;
}對中心點(diǎn)及其周圍8個(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?5000KM時(shí)可能出現(xiàn))
?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內(nèi)的最大、最小geohash值（52位）
?GeoHashFix52Bits?min,?max;
?scoresOfGeoHashBox(hash,&min,&max);//根據(jù)最大、最小geohash值篩選zobj集合中滿足條件的點(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)，效率可比擬于二叉查找樹），沒有則返0
?if?((ln?=?zslFirstInRange(zsl,?&range))?==?NULL)?{?/*?Nothing?exists?starting?at?our?min.?No?results.?*/
?return?0;
?} //從首個(gè)元素開始遍歷集合
?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)建并返回滿足條件的元素
?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é)
拋開眾多可選參數(shù)不談，簡單總結(jié)下GEORADIUS命令是怎么利用geohash獲取目標(biāo)位置對象的：
1、參數(shù)提取和校驗(yàn)；
2、利用中心點(diǎn)和輸入半徑計(jì)算待查區(qū)域范圍。這個(gè)范圍參數(shù)包括滿足條件的最高的geohash網(wǎng)格等級(精度) 以及 對應(yīng)的能夠覆蓋目標(biāo)區(qū)域的九宮格位置；（后續(xù)會有詳細(xì)說明）
3、對九宮格進(jìn)行遍歷，根據(jù)每個(gè)geohash網(wǎng)格的范圍框選出位置對象。進(jìn)一步找出與中心點(diǎn)距離小于輸入半徑的對象，進(jìn)行返回。
直接描述不太好理解，我們通過如下兩張圖在對算法進(jìn)行簡單的演示：
令左圖的中心為搜索中心，綠色圓形區(qū)域?yàn)槟繕?biāo)區(qū)域，所有點(diǎn)為待搜索的位置對象，紅色點(diǎn)則為滿足條件的位置對象。
在實(shí)際搜索時(shí),首先會根據(jù)搜索半徑計(jì)算geohash網(wǎng)格等級（即右圖中網(wǎng)格大小等級），并確定九宮格位置（即紅色九宮格位置信息）；再依次查找計(jì)算九宮格中的點(diǎn)（藍(lán)點(diǎn)和紅點(diǎn)）與中心點(diǎn)的距離，最終篩選出距離范圍內(nèi)的點(diǎn)（紅點(diǎn)）。
算法分析
為什么要用這種算法策略進(jìn)行查詢，或者說這種策略的優(yōu)勢在哪，讓我們以問答的方式進(jìn)行分析說明。
為什么要找到滿足條件的最高的geohash網(wǎng)格等級？為什么用九宮格？
這其實(shí)是一個(gè)問題，本質(zhì)上是對所有的元素對象進(jìn)行了一次初步篩選。 在多層geohash網(wǎng)格中，每個(gè)低等級的geohash網(wǎng)格都是由4個(gè)高一級的網(wǎng)格拼接而成（如圖）。
換句話說，geohash網(wǎng)格等級越高，所覆蓋的地理位置范圍就越小。 當(dāng)我們根據(jù)輸入半徑和中心點(diǎn)位置計(jì)算出的能夠覆蓋目標(biāo)區(qū)域的最高等級的九宮格（網(wǎng)格）時(shí)，就已經(jīng)對九宮格外的元素進(jìn)行了篩除。 這里之所以使用九宮格，而不用單個(gè)網(wǎng)格，主要原因還是為了避免邊界情況，盡可能縮小查詢區(qū)域范圍。試想以0經(jīng)緯度為中心，就算查1米范圍，單個(gè)網(wǎng)格覆蓋的話也得查整個(gè)地球區(qū)域。而向四周八個(gè)方向擴(kuò)展一圈可有效避免這個(gè)問題。
如何通過geohash網(wǎng)格的范圍框選出元素對象？效率如何？
首先在每個(gè)geohash網(wǎng)格中的geohash值都是連續(xù)的，有固定范圍。所以只要找出有序集合中，處在該范圍的位置對象即可。以下是有序集合的跳表數(shù)據(jù)結(jié)構(gòu)：
其擁有類似二叉查找樹的查詢效率，操作平均時(shí)間復(fù)雜性為O(log(N))。且最底層的所有元素都以鏈表的形式按序排列。所以在查詢時(shí)，只要找到集合中處在目標(biāo)geohash網(wǎng)格中的第一個(gè)值，后續(xù)依次對比即可，不用多次查找。 九宮格不能一起查，要一個(gè)個(gè)遍歷的原因也在于九宮格各網(wǎng)格對應(yīng)的geohash值不具有連續(xù)性。只有連續(xù)了，查詢效率才會高，不然要多做許多距離運(yùn)算。
綜上，我們從源碼角度解析了Redis Geo模塊中 “增（GEOADD）” 和 “查（GEORADIUS）” 的詳細(xì)過程。并可推算出Redis中GEORADIUS查找附近的人功能，時(shí)間復(fù)雜度為：O(N+log(M))，其中N為指定半徑范圍內(nèi)的位置元素?cái)?shù)量，而M則是被九宮格圈住計(jì)算距離的元素的數(shù)量。結(jié)合Redis本身基于內(nèi)存的存儲特性，在實(shí)際使用過程中有非常高的運(yùn)行效率。
讀者福利
加微信：haolagui521備注51CTO領(lǐng)取附送學(xué)習(xí)進(jìn)階架構(gòu)資料、PDF書籍文檔、面試資料
