針對“附近的人”這一位置服務(wù)領(lǐng)域的應(yīng)用場景，常見的可使用 PG、MySQL 和 MongoDB 等多種 DB 的空間索引進(jìn)行實現(xiàn)。

[[279964]]
圖片來自 Pexels 

而 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 < 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作為分值 & 提取對象名稱 
        /* 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è)置有序集合的對象元素名稱和分值 
        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)保存位置對象，有序集合中每個元素都是一個帶位置的對象，元素的 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 命令都干了啥：

• 參數(shù)提取和校驗
• 將入?yún)⒔?jīng)緯度轉(zhuǎn)換為 52 位的 GEOHASH 值(Score)
• 調(diào)用 ZADD 命令將 Member 及其對應(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)集合中與中心的距離不超過給定最大距離的所有位置對象。

范圍單位：m | km | ft | mi --> 米 | 千米 | 英尺 | 英里

額外參數(shù)：

• WITHDIST：在返回位置對象的同時，將位置對象與中心之間的距離也一并返回。距離的單位和用戶給定的范圍單位保持一致。
• WITHCOORD：將位置對象的經(jīng)度和維度也一并返回。
• WITHHASH：以 52 位有符號整數(shù)的形式，返回位置對象經(jīng)過原始 GEOHASH 編碼的有序集合分值。這個選項主要用于底層應(yīng)用或者調(diào)試，實際中的作用并不大。
• ASC|DESC：從近到遠(yuǎn)返回位置對象元素 | 從遠(yuǎn)到近返回位置對象元素。
• COUNT count：選取前 N 個匹配位置對象元素。(不設(shè)置則返回所有元素)
• STORE key：將返回結(jié)果的地理位置信息保存到指定 key。
• STORedisT key：將返回結(jié)果離中心點的距離保存到指定 Key。

由于 STORE 和 STORedisT 兩個選項的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技術(shù)上會被標(biāo)記為寫入命令，從而只會查詢(寫入)主實例，QPS 過高時容易造成主實例讀寫壓力過大。

為解決這個問題，在 Redis 3.2.10 和 Redis 4.0.0 中，分別新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO 兩個只讀命令。

不過，在實際開發(fā)中筆者發(fā)現(xiàn) 在 java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 參數(shù)類中并不包含 STORE 和 STORedisT 兩個參數(shù)選項。

在調(diào)用 GEORADIUS 時是否真的只查詢了主實例，還是進(jìn)行了只讀封裝。感興趣的朋友可以自己研究下。

成功查詢后的返回值，不帶 WITH 限定，返回一個 member list，如：

["member1","member2","member3"] 

帶 WITH 限定，Member List 中每個 Member 也是一個嵌套 List，如：

[ 
    ["member1", distance1, [longitude1, latitude1]] 
    ["member2", distance2, [longitude2, latitude2]] 
] 

源碼分析

PS：此段源碼較長，看不下去的可直接看中文注釋，或直接跳到小結(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)中心點經(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)) < 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; 
 
//利用中心點和半徑計算目標(biāo)區(qū)域范圍 
    GeoHashRadius georadius = 
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters); 
 
//對中心點及其周圍8個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); 
} 

上文代碼中最核心的步驟有兩個，一是“計算中心點范圍”，二是“對中心點及其周圍 8 個 GEOHASH 網(wǎng)格區(qū)域進(jìn)行查找”。

對應(yīng)的是如下兩個函數(shù)：

• geohashGetAreasByRadiusWGS84
• membersOfAllNeighbors

我們依次來看：

①計算中心點范圍

// geohash_helper.c

/* 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)中心點經(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)) < 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; 
 
//利用中心點和半徑計算目標(biāo)區(qū)域范圍 
    GeoHashRadius georadius = 
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters); 
 
//對中心點及其周圍8個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); 
} 

②對中心點及其周圍 8 個 GEOHASH 網(wǎng)格區(qū)域進(jìn)行查找

// 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中搜索目標(biāo)點 
    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時可能出現(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集合中滿足條件的點 
    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個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范圍內(nèi)的首個元素（跳表數(shù)據(jù)結(jié)構(gòu)，效率可比擬于二叉查找樹），沒有則返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; 
    } 
 
//構(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)位置對象的：

• 參數(shù)提取和校驗。
• 利用中心點和輸入半徑計算待查區(qū)域范圍。這個范圍參數(shù)包括滿足條件的最高的 GEOHASH 網(wǎng)格等級(精度)以及對應(yīng)的能夠覆蓋目標(biāo)區(qū)域的九宮格位置(后續(xù)會有詳細(xì)說明)。
• 對九宮格進(jìn)行遍歷，根據(jù)每個 GEOHASH 網(wǎng)格的范圍框選出位置對象。進(jìn)一步找出與中心點距離小于輸入半徑的對象，進(jìn)行返回。

直接描述不太好理解，我們通過如下兩張圖再對算法進(jìn)行簡單的演示：

令左圖的中心為搜索中心，綠色圓形區(qū)域為目標(biāo)區(qū)域，所有點為待搜索的位置對象，紅色點則為滿足條件的位置對象。

在實際搜索時,首先會根據(jù)搜索半徑計算 GEOHASH 網(wǎng)格等級(即右圖中網(wǎng)格大小等級)，并確定九宮格位置(即紅色九宮格位置信息)。

再依次查找計算九宮格中的點(藍(lán)點和紅點)與中心點的距離，最終篩選出距離范圍內(nèi)的點(紅點)。

算法分析

為什么要用這種算法策略進(jìn)行查詢，或者說這種策略的優(yōu)勢在哪，讓我們以問答的方式進(jìn)行分析說明。

①為什么要找到滿足條件的最高的 GEOHASH 網(wǎng)格等級?為什么用九宮格?

這其實是一個問題，本質(zhì)上是對所有的元素對象進(jìn)行了一次初步篩選。在多層 GEOHASH 網(wǎng)格中，每個低等級的 GEOHASH 網(wǎng)格都是由 4 個高一級的網(wǎng)格拼接而成(如圖)。

換句話說，GEOHASH 網(wǎng)格等級越高，所覆蓋的地理位置范圍就越小。當(dāng)我們根據(jù)輸入半徑和中心點位置計算出的能夠覆蓋目標(biāo)區(qū)域的最高等級的九宮格(網(wǎng)格)時，就已經(jīng)對九宮格外的元素進(jìn)行了篩除。

這里之所以使用九宮格，而不用單個網(wǎng)格，主要原因還是為了避免邊界情況，盡可能縮小查詢區(qū)域范圍。

試想以 0 經(jīng)緯度為中心，就算查 1 米范圍，單個網(wǎng)格覆蓋的話也得查整個地球區(qū)域。而向四周八個方向擴展一圈可有效避免這個問題。

②如何通過 GEOHASH 網(wǎng)格的范圍框選出元素對象?效率如何?

首先在每個 GEOHASH 網(wǎng)格中的 GEOHASH 值都是連續(xù)的，有固定范圍。所以只要找出有序集合中，處在該范圍的位置對象即可。

以下是有序集合的跳表數(shù)據(jù)結(jié)構(gòu)：

其擁有類似二叉查找樹的查詢效率，操作平均時間復(fù)雜性為 O(log(N))。且最底層的所有元素都以鏈表的形式按序排列。

所以在查詢時，只要找到集合中處在目標(biāo) GEOHASH 網(wǎng)格中的第一個值，后續(xù)依次對比即可，不用多次查找。

九宮格不能一起查，要一個個遍歷的原因也在于九宮格各網(wǎng)格對應(yīng)的 GEOHASH 值不具有連續(xù)性。只有連續(xù)了，查詢效率才會高，不然要多做許多距離運算。

綜上，我們從源碼角度解析了 Redis Geo 模塊中 “增(GEOADD)” 和 “查(GEORADIUS)” 的詳細(xì)過程。

并可推算出 Redis 中 GEORADIUS 查找附近的人功能，時間復(fù)雜度為：O(N+log(M))。

其中 N 為指定半徑范圍內(nèi)的位置元素數(shù)量，而 M 則是被九宮格圈住計算距離的元素的數(shù)量。

結(jié)合 Redis 本身基于內(nèi)存的存儲特性，在實際使用過程中有非常高的運行效率。

作者：萬汨

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