共計 10789 個字符，預計需要花費 27 分鐘才能閱讀完成。

自動寫代碼機器人，免費開通

這篇文章給大家分享的是有關 Redis 如何實現“附近的人”功能的內容。丸趣 TV 小編覺得挺實用的，因此分享給大家做個參考，一起跟隨丸趣 TV 小編過來看看吧。

針對“附近的人”這一位置服務領域的應用場景，常見的可使用 PG、MySQL 和 MongoDB 等多種 DB 的空間索引進行實現。而 Redis 另辟蹊徑，結合其有序隊列 zset 以及 geohash 編碼，實現了空間搜索功能，且擁有極高的運行效率。本文將從源碼角度對其算法原理進行解析，并推算查詢時間復雜度。

操作命令

自 Redis 3.2 開始，Redis 基于 geohash 和有序集合提供了地理位置相關功能。

Redis Geo 模塊包含了以下 6 個命令：

GEOADD: 將給定的位置對象（緯度、經度、名字）添加到指定的 key;

GEOPOS: 從 key 里面返回所有給定位置對象的位置（經度和緯度）;

GEODIST: 返回兩個給定位置之間的距離;

GEOHASH: 返回一個或多個位置對象的 Geohash 表示;

GEORADIUS: 以給定的經緯度為中心，返回目標集合中與中心的距離不超過給定最大距離的所有位置對象;

GEORADIUSBYMEMBER: 以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。

其中，組合使用 GEOADD 和 GEORADIUS 可實現“附近的人”中“增”和“查”的基本功能。要實現微信中“附近的人”功能，可直接使用 GEORADIUSBYMEMBER 命令。其中“給定的位置對象”即為用戶本人，搜索的對象為其他用戶。不過本質上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用戶位置再通過該位置搜索附近滿足位置相互距離條件的其他用戶對象。

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

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

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

GEOADD

使用方式

GEOADD key longitude latitude member [longitude latitude member …]

將給定的位置對象（緯度、經度、名字）添加到指定的 key。

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

成功插入后的返回值：

(integer) N

其中 N 為成功插入的個數。

源碼分析

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
// 參數校驗
 /* 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;
 }
// 參數提取 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]);
// 參數遍歷 + 轉換
 /* 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];
 // 提取經緯度
 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;
 }
 // 將經緯度轉換為 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];
 // 設置有序集合的對象元素名稱和分值
 argv[2+i*2] = score;
 argv[3+i*2] = val;
 incrRefCount(val);
 }
// 調用 zadd 命令，存儲轉化好的對象
 /* Finally call ZADD that will do the work for us. */
 replaceClientCommandVector(c,argc,argv);
 zaddCommand(c);
}

通過源碼分析可以看出 Redis 內部使用有序集合 (zset) 保存位置對象，有序集合中每個元素都是一個帶位置的對象，元素的 score 值為其經緯度對應的 52 位的 geohash 值。

double 類型精度為 52 位；

geohash 是以 base32 的方式編碼，52bits 最高可存儲 10 位 geohash 值，對應地理區域大小為 0.6*0.6 米的格子。換句話說經 Redis geo 轉換過的位置理論上會有約 0.3*1.414=0.424 米的誤差。

算法小結

總結下 GEOADD 命令都干了啥：

1、參數提取和校驗；

2、將入參經緯度轉換為 52 位的 geohash 值（score）；

3、調用 ZADD 命令將 member 及其對應的 score 存入集合 key 中。

GEORADIUS

使用方式

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]

以給定的經緯度為中心，返回目標集合中與中心的距離不超過給定最大距離的所有位置對象。

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

額外參數：

– WITHDIST：在返回位置對象的同時，將位置對象與中心之間的距離也一并返回。距離的單位和用戶給定的范圍單位保持一致。

– WITHCOORD：將位置對象的經度和維度也一并返回。

– WITHHASH：以 52 位有符號整數的形式，返回位置對象經過原始 geohash 編碼的有序集合分值。這個選項主要用于底層應用或者調試，實際中的作用并不大。

– ASC|DESC：從近到遠返回位置對象元素 | 從遠到近返回位置對象元素。

– COUNT count：選取前 N 個匹配位置對象元素。（不設置則返回所有元素）

– STORE key：將返回結果的地理位置信息保存到指定 key。

– STORedisT key：將返回結果離中心點的距離保存到指定 key。

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

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

成功查詢后的返回值：

不帶 WITH 限定，返回一個 member list，如：

[member1 , member2 , member3]

帶 WITH 限定，member list 中每個 member 也是一個嵌套 list，如：

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

源碼分析

此段源碼較長，看不下去的可直接看中文注釋，或直接跳到小結部分

/* 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. */
// 根據 key 獲取有序集合
 robj *zobj = NULL;
 if ((zobj = lookupKeyReadOrReply(c, key, shared.null[c- resp])) == NULL ||
 checkType(c, zobj, OBJ_ZSET)) {
 return;
 }
// 根據用戶輸入（經緯度 /member）確認中心點經緯度
 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;
 }
// 獲取可選參數  （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  參數
 if (storekey   (withdist || withhash || withcoords)) {
 addReplyError(c,
  STORE option in GEORADIUS is not compatible with  
  WITHDIST, WITHHASH and WITHCOORDS options 
 return;
 }
// 設定排序
 if (count != 0   sort == SORT_NONE) sort = SORT_ASC;
// 利用中心點和半徑計算目標區域范圍
 GeoHashRadius georadius =
 geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
// 對中心點及其周圍 8 個 geohash 網格區域進行查找，找出范圍內元素對象
 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;
 }
// 一些返回值的設定和返回
 ……
 geoArrayFree(ga);
}

上文代碼中最核心的步驟有兩個，一是“計算中心點范圍”，二是“對中心點及其周圍 8 個 geohash 網格區域進行查找”。對應的是 geohashGetAreasByRadiusWGS84 和 membersOfAllNeighbors 兩個函數。我們依次來看：

計算中心點范圍：

// geohash_helper.c
GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
 double radius_meters) { return geohashGetAreasByRadius(longitude, latitude, radius_meters);
// 返回能夠覆蓋目標區域范圍的 9 個 geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
// 一些參數設置
 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;
// 計算目標區域外接矩形的經緯度范圍（目標區域為：以目標經緯度為中心，半徑為指定距離的圓） geohashBoundingBox(longitude, latitude, radius_meters, bounds);
 min_lon = bounds[0];
 min_lat = bounds[1];
 max_lon = bounds[2];
 max_lat = bounds[3];
// 根據目標區域中心點緯度和半徑，計算帶查詢的 9 個搜索框的 geohash 精度（位）// 這里用到 latitude 主要是針對極地的情況對精度進行了一些調整（緯度越高，位數越?。?nbsp;steps = geohashEstimateStepsByRadius(radius_meters,latitude);
// 設置經緯度最大最小值：-180 =longitude =180, -85 =latitude =85
 geohashGetCoordRange(long_range, lat_range);
// 將待查經緯度按指定精度（steps）編碼成 geohash 值
 geohashEncode(long_range, lat_range,longitude,latitude,steps, hash);
// 將 geohash 值在 8 個方向上進行擴充，確定周圍 8 個 Box（neighbors） geohashNeighbors(hash, neighbors);
// 根據 hash 值確定 area 經緯度范圍
 geohashDecode(long_range,lat_range,hash, area);
// 一些特殊情況處理
 ……
// 構建并返回結果  
 radius.hash = hash;
 radius.neighbors = neighbors;
 radius.area = area;
 return radius;
}

對中心點及其周圍 8 個 geohash 網格區域進行查找:

// 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 中搜索目標點
 for (i = 0; i   sizeof(neighbors) / sizeof(*neighbors); i++) { if (HASHISZERO(neighbors[i])) { if (debugmsg) D(neighbors[%d] is zero ,i);
 continue;
 }
// 剔除可能的重復 hashBox (搜索半徑 5000KM 時可能出現)
 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 內的最大、最小 geohash 值（52 位） GeoHashFix52Bits min, max;
 scoresOfGeoHashBox(hash, min, max);
// 根據最大、最小 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 的參數邊界設置（即 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- 
 zskiplist *zsl = zs- 
 zskiplistNode *ln;
// 獲取在 hashBox 范圍內的首個元素（跳表數據結構，效率可比擬于二叉查找樹），沒有則返 0
 if ((ln = zslFirstInRange(zsl,  range)) == NULL) {
 /* Nothing exists starting at our min. No results. */
 return 0;
 }
// 從首個元素開始遍歷集合
 while (ln) {
 sds ele = ln- 
// 遍歷元素超出 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;
 }
// 構建并返回滿足條件的元素
 geoPoint *gp = geoArrayAppend(ga);
 gp- longitude = xy[0];
 gp- latitude = xy[1];
 gp- dist = distance;
 gp- member = member;
 gp- score = score;
 return C_OK;
}

算法小結

拋開眾多可選參數不談，簡單總結下 GEORADIUS 命令是怎么利用 geohash 獲取目標位置對象的：

1、參數提取和校驗；

2、利用中心點和輸入半徑計算待查區域范圍。這個范圍參數包括滿足條件的最高的 geohash 網格等級(精度) 以及 對應的能夠覆蓋目標區域的九宮格位置；（后續會有詳細說明）

3、對九宮格進行遍歷，根據每個 geohash 網格的范圍框選出位置對象。進一步找出與中心點距離小于輸入半徑的對象，進行返回。

通過如下兩張圖在對算法進行簡單的演示：

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

在實際搜索時, 首先會根據搜索半徑計算 geohash 網格等級（即右圖中網格大小等級），并確定九宮格位置（即紅色九宮格位置信息）；再依次查找計算九宮格中的點（藍點和紅點）與中心點的距離，最終篩選出距離范圍內的點（紅點）。

算法分析

為什么要用這種算法策略進行查詢，或者說這種策略的優勢在哪，

為什么要找到滿足條件的最高的 geohash 網格等級？為什么用九宮格？這其實是一個問題，本質上是對所有的元素對象進行了一次初步篩選。在多層 geohash 網格中，每個低等級的 geohash 網格都是由 4 個高一級的網格拼接而成（如圖）。

換句話說，geohash 網格等級越高，所覆蓋的地理位置范圍就越小。當我們根據輸入半徑和中心點位置計算出的能夠覆蓋目標區域的最高等級的九宮格（網格）時，就已經對九宮格外的元素進行了篩除。這里之所以使用九宮格，而不用單個網格，主要原因還是為了避免邊界情況，盡可能縮小查詢區域范圍。試想以 0 經緯度為中心，就算查 1 米范圍，單個網格覆蓋的話也得查整個地球區域。而向四周八個方向擴展一圈可有效避免這個問題。

如何通過 geohash 網格的范圍框選出元素對象？效率如何？

首先在每個 geohash 網格中的 geohash 值都是連續的，有固定范圍。所以只要找出有序集合中，處在該范圍的位置對象即可。以下是有序集合的跳表數據結構：

其擁有類似二叉查找樹的查詢效率，操作平均時間復雜性為 O(log(N))。且最底層的所有元素都以鏈表的形式按序排列。所以在查詢時，只要找到集合中處在目標 geohash 網格中的第一個值，后續依次對比即可，不用多次查找。九宮格不能一起查，要一個個遍歷的原因也在于九宮格各網格對應的 geohash 值不具有連續性。只有連續了，查詢效率才會高，不然要多做許多距離運算。

綜上，從源碼角度解析了 Redis Geo 模塊中“增（GEOADD）”和“查（GEORADIUS）”的詳細過程。并可推算出 Redis 中 GEORADIUS 查找附近的人功能，時間復雜度為：O(N+log(M))，其中 N 為指定半徑范圍內的位置元素數量，而 M 則是被九宮格圈住計算距離的元素的數量。結合 Redis 本身基于內存的存儲特性，在實際使用過程中有非常高的運行效率。

感謝各位的閱讀！關于“Redis 如何實現“附近的人”功能”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！