IM里「附近的人」功能實現原理是什麼？如何高效率地實現它？

• 2019 年 11 月 13 日
• 筆記

本文引用了餓了么資深開發工程師萬汨「Redis 到底是怎麼實現「附近的人」這個功能的呢？」一文的內容，感謝原作者的分享，為了提升文章品質，即時通訊收錄時有內容補充和修訂。

1、引言

基本上以陌生人社交為主的IM產品里，都會增加「附近的人」、「附近的xxx」這種以LBS（地理位置）為導向的產品特色（微信這個熟人社交產品里為啥也有「附近的人」？這當然是歷史原因了，微信當初還不是想藉此引流嘛。。。），因為「附近的xxx」這種類似功能在產品運營早期，對於種子用戶的積累有很大幫助（必竟某種需求，對於人類來說，是上帝賦予的最原始衝動，你懂的…）。

比如下圖中的幾款主流移動端IM中的「附近的xxx」功能：

那麼，對於很多即時通訊（IM）的開發者初學者來說，「附近的人」或者類似功能，在技術實現上還有點摸不着頭腦。本文將簡要的為你講解「附近的人」的基本理論原理，並以Redis的GEO系列地理位置操作指令為例，理論聯繫實際地為你講解它們是如何被高效實現的。

閱讀提示：本文適合有一定Redis使用經驗的服務器後端開發人員閱讀，IM移動客戶端開發人員沒有太多閱讀的必要（理論原理倒是可以知道一下），必竟「附近的xxx」功能主要工作在服務端，而不在客戶端。

3、「附近的人」功能原理

其實，「附近的人」功能原理並不複雜。

它需要做以下兩件事情：

1）所有使用該IM產品的人，在使用「附近的人」功能前提交自已的地理位置； 2）根據「我」的地理位置，計算出別人跟我的距離； 3）將第2步中計算出的距離由近及遠，進行排序。

具體在產品技術上的實現原理，也很容易理解：

1）現在移動端（ios、android等），通過系統的API很容易抓到用戶當前的位置（即經緯度數據）； 2）根據第1步中的經緯度數據，很容易計算出兩個點之間的距離（計算公式原理，可以百度一下，我的幾何和數學知識都還給老師了，給你講不了）； 3）對第2步中的計算結果排序就更簡單了，沒什麼好提的。

對於IM新手來說，可能對於第2步中的根據經緯度數據計算出兩點距離，覺得有點難度，實際上根據數據公式（自已百度一下吧，有點複雜，哥不貼了），用代碼來實現，只有短短的十來行代碼。

下面是一個簡單的Java版實現：

/** * 計算地球上任意兩點(經緯度)距離 * * @param long1 第一點經度 * @param lat1 第一點緯度 * @param long2 第二點經度 * @param lat2 第二點緯度 * @return 返回距離 單位：米 */ public static double Distance(double long1, double lat1, double long2, double lat2) { double a, b, R; R = 6378137; // 地球半徑 lat1 = lat1 * Math.PI / 180.0; lat2 = lat2 * Math.PI / 180.0; a = lat1 – lat2; b = (long1 – long2) * Math.PI / 180.0; double d; double sa2, sb2; sa2 = Math.sin(a / 2.0); sb2 = Math.sin(b / 2.0); d = 2* R * Math.asin(Math.sqrt(sa2 * sa2 + Math.cos(lat1) * Math.cos(lat2) * sb2 * sb2)); return d; }

在進行代碼測試的時候，可以結合這個在線工具網頁進行結果檢驗：http://www.hhlink.com/%E7%BB%8F%E7%BA%AC%E5%BA%A6/

嗯，看起來好簡單！

4、自已從零實現的話，沒有難度嗎？

嗯，通過上一節的原理講解，目前為止，看起來確實很簡單。

但，如果自已從零實現的話，對於IM這種高性能、高並發場景來說，確實有一點難度，難不在移動客戶端，而是在服務端。

技術難點主要包括：

1）如何高效地進行兩點距離的計算，對於高並發服務端來說，像上一節中的代碼那樣，一個一個計算，還是有點不高效； 2）如何高效地進行地理圍欄的圈定（難道是把所有當前在線的用戶，離我的距離都一一算一遍，然後按距離進行篩選？那性能豈不是噩夢？）。

那，有救嗎？答案是有！繼續看下一節。

5、Redis里的GEO地理位置相關指令，就能很好的上述問題

針對「附近的人」這一位置服務領域的應用場景，服務端高性能場景下，常見的可使用PG、MySQL和MongoDB等多種DB的空間索引進行實現。

而Redis另闢蹊徑，結合其有序隊列zset以及geohash編碼，實現了空間搜索功能，且擁有極高的運行效率。

要提供完整的「附近的人」這樣的功能或服務，最基本的是要實現「增」、「刪」、「查」的功能。本文餘下的文字，以下將分別進行介紹，其中會重點對查詢功能進行解析。並將從Redis源碼角度對其算法原理進行解析，並推算查詢時間複雜度。

Redis相關資源：

1）Redis官網：https://redis.io 2）Redis的GEO指令說明（英文）：https://redis.io/commands 3）Redis的GEO指令說明（中文）：http://redisdoc.com/geo/geoadd.html

6、Redis的GEO地理位置操作指令

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

Redis中的6個地理位置相關操作指令（見官方文檔）：

Redis Geo模塊的6個指令用途說明：

1）GEOADD：將給定的位置對象（緯度、經度、名字）添加到指定的key； 2）GEOPOS：從key裏面返回所有給定位置對象的位置（經度和緯度）； 3）GEODIST：返回兩個給定位置之間的距離； 4）GEOHASH：返回一個或多個位置對象的Geohash表示； 5）GEORADIUS：以給定的經緯度為中心，返回目標集合中與中心的距離不超過給定最大距離的所有位置對象； 6）GEORADIUSBYMEMBER：以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。

其中，組合使用GEOADD和GEORADIUS可實現「附近的人」中「增」和「查」的基本功能。要實現類似於微信中「附近的人」功能，可直接使用GEORADIUSBYMEMBER命令。

其中「給定的位置對象」即為用戶本人，搜索的對象為其他用戶。不過本質上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用戶位置再通過該位置搜索附近滿足位置相互距離條件的其他用戶對象。

使用時的注意點：

1）Redis GEO操作中只包含了「增」和「查」的操作，並無專門「刪除」命令。主要是因為Redis內部使用有序集合(zset)保存位置對象，可用zrem刪除； 2）在Redis源碼geo.c的文件注釋中，只說明了該文件為GEOADD、GEORADIUS和GEORADIUSBYMEMBER的實現； 3）從側面看出其他三個命令為輔助命令。

本文的餘下內容，將會從源碼角度入手，着生理地對GEOADD和GEORADIUS命令進行分析，剖析其算法原理。

7、Redis的GEOADD指令是如何高效實現的

7.1 使用方式

GEOADD key longitude latitude member [longitude latitude member …]

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

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

成功插入後的返回值：

(integer) N

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

7.2 源碼分析

/* 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源碼分析可以看出，Redis內部使用有序集合(zset)保存位置對象，有序集合中每個元素都是一個帶位置的對象，元素的score值為其經緯度對應的52位的geohash值：

1）double類型精度為52位；

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

7.3 算法小結

簡單總結下GEOADD命令都幹了啥：

1）參數提取和校驗；

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

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

8、Redis的GEORADIUS指令是如何高效實現的

8.1 使用方式

1GEORADIUS 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兩個只讀命令。

不過，在實際開發中筆者發現 在java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 參數類中並不包含 STORE 和 STORedisT 兩個參數選項，在調用georadius時是否真的只查詢了主實例，還是進行了只讀封裝。感興趣的朋友可以自己研究下。

成功查詢後的返回值：

不帶WITH限定，返回一個member list，如：["member1","member2","member3"]

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

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

8.2 源碼分析

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

/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC] * [COUNT count] [STORE key] [STORedisT key] * GEORADIUSBYMEMBER key member radius unit … options … */ voidgeoradiusGeneric(client *c, intflags) { 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主要是針對極地的情況對精度進行了一些調整（緯度越高，位數越小） 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; } returncount; } 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_torigincount = 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範圍內的首個元素（跳錶數據結構，效率可比擬於二叉查找樹），沒有則返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; } } returnga->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)) returnC_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; }

8.3 算法小結

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

1）參數提取和校驗；

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

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

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

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

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

8.4 算法分析

為什麼要用這種算法策略進行查詢，或者說這種策略的優勢在哪，讓我們以問答的方式進行分析說明。

為什麼要找到滿足條件的最高的geohash網格等級？為什麼用九宮格？

這其實是一個問題，本質上是對所有的元素對象進行了一次初步篩選。 在多層geohash網格中，每個低等級的geohash網格都是由4個高一級的網格拼接而成（如下圖）。

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

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

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

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

9、本文小結

綜合上述章節，我們從源碼角度解析了Redis Geo模塊中 「增（GEOADD）」 和 「查（GEORADIUS）」 的詳細過程。並可推算出Redis中GEORADIUS查找附近的人功能，時間複雜度為：O(N+log(M))。

其中：

1）N為九宮格範圍內的位置元素數量（要算距離）；

2）M是指定層級格子的數量；

3）log(M)是跳錶結構中找到每個格子首元素的時間複雜度（這個過程一般會進行9次）。

結合Redis本身基於內存的存儲特性，在實際使用過程中有非常高的運行效率。

以上，就是本文的全部答案，不知是否對你有幫助！