如何使用?Redis?實現(xiàn)?“附近的人”?這個功能？

作者簡介

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

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

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

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

操作命令

自Redis 3.2開始，Redis基于geohash和有序集合提供了地理位置相關(guān)功能。Redis Geo模塊包含了以下6個命令：

• GEOADD: 將給定的位置對象（緯度、經(jīng)度、名字）添加到指定的key;
• GEOPOS: 從key里面返回所有給定位置對象的位置（經(jīng)度和緯度）;
• GEODIST: 返回兩個給定位置之間的距離;
• GEOHASH: 返回一個或多個位置對象的Geohash表示;
• GEORADIUS: 以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過給定最大距離的所有位置對象;
• GEORADIUSBYMEMBER: 以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。

其中，組合使用GEOADD和GEORADIUS可實現(xiàn)“附近的人”中“增”和“查”的基本功能。

要實現(xiàn)微信中“附近的人”功能，可直接使用GEORADIUSBYMEMBER命令。其中“給定的位置對象”即為用戶本人，搜索的對象為其他用戶。

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

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

Redis geo操作中只包含了“增”和“查”的操作，并沒有專門的“刪除”命令。主要是因為Redis內(nèi)部使用有序集合(zset)保存位置對象，可用zrem進(jìn)行刪除。

在Redis源碼geo.c的文件注釋中，只說明了該文件為GEOADD、GEORADIUS和GEORADIUSBYMEMBER的實現(xiàn)文件（其實在也實現(xiàn)了另三個命令）。從側(cè)面看出其他三個命令為輔助命令。

GEOADD

使用方式

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

其中，key為集合名稱，member為該經(jīng)緯度所對應(yīng)的對象。在實際運用中，當(dāng)所需存儲的對象數(shù)量過多時，可通過設(shè)置多key(如一個省一個key)的方式對對象集合變相做sharding，避免單集合數(shù)量過多。

成功插入后的返回值：

(integer)?N
其中N為成功插入的個數(shù)。

源碼分析

/*?GEOADD?key?long?lat?name?[long2?lat2?name2?...?longN?latN?nameN]?*/
void?geoaddCommand(client?*c)?{

//參數(shù)校驗
????/*?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作為分值?