作者簡(jiǎn)介

萬(wàn)汨，餓了么資深開發(fā)工程師。iOS，Go，Java均有涉獵。目前主攻大數(shù)據(jù)開發(fā)。喜歡騎行、爬山。

前言：針對(duì)“附近的人”這一位置服務(wù)領(lǐng)域的應(yīng)用場(chǎng)景，常見的可使用PG、MySQL和MongoDB等多種DB的空間索引進(jìn)行實(shí)現(xiàn)。而Redis另辟蹊徑，結(jié)合其有序隊(duì)列zset以及geohash編碼，實(shí)現(xiàn)了空間搜索功能，且擁有極高的運(yùn)行效率。

本文將從源碼角度對(duì)其算法原理進(jìn)行解析，并推算查詢時(shí)間復(fù)雜度。

要提供完整的“附近的人”服務(wù)，最基本的是要實(shí)現(xiàn)“增”、“刪”、“查”的功能。以下將分別進(jìn)行介紹，其中會(huì)重點(diǎn)對(duì)查詢功能進(jìn)行解析。

操作命令

自Redis 3.2開始，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ì)象”即為用戶本人，搜索的對(duì)象為其他用戶。

不過(guò)本質(zhì)上，GEORADIUSBYMEMBER = GEOPOS GEORADIUS，即先查找用戶位置再通過(guò)該位置搜索附近滿足位置相互距離條件的其他用戶對(duì)象。

以下會(huì)從源碼角度入手對(duì)GEOADD和GEORADIUS命令進(jìn)行分析，剖析其算法原理。

Redis geo操作中只包含了“增”和“查”的操作，并沒(méi)有專門的“刪除”命令。主要是因?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

使用方式

GEOADD?key?longitude?latitude?member?[longitude?latitude?member?...]
將給定的位置對(duì)象（緯度、經(jīng)度、名字）添加到指定的key。

其中，key為集合名稱，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?????????double?xy[2];

????//提取經(jīng)緯度
????????if?(extractLongLatOrReply(c,?(c->argv 2) (i*3),xy)?==?C_ERR)?{
????????????for?(i?=?0;?i?????????????????if?(argv[i])?decrRefCount(argv[i]);
????????????zfree(argv);
????????????return;
????????}
????
????//將經(jīng)緯度轉(zhuǎn)換為52位的geohash作為分值?