IM即时通讯里“附近的人”功能实现方法？微信陌陌

第一节绪论

基本是陌生人社交占主导地位的 IM产品，都会加入“邻居”、“邻居 xxx”这样的产品特征，以 LBS (地理位置)为导向(微信这一熟人社交产品为什么也有“邻居”呢？那当然是历史原因了，最初微信并不是想借此来引流…)由于“近邻xxx”这一类似功能，在产品运营初期，对种子用户的积累起了很大作用(某一方面的需求，对人来说，是上帝赋予的最原始的冲动，你知道...)。

例如下面这张图片中的几个主流移动端 IM中的“附近 xxx”特性：

因此，对于许多刚开始使用 IM的开发人员来说，“身边的人”或类似的功能，在技术实现方面还是有点摸不着头脑。这篇文章会简单的向你解释一下“周围的人”的基本理论，并以 Redis的 GEO系列地理位置操作指令为例，通过理论联系实际的方式向你解释它们是如何有效实施的。

读解：本文适合具有一定 Redis使用经验的服务器后端开发人员阅读， IM移动客户端开发人员没有必要阅读太多的文章(理论上还可以了解一些)，必竟“附近 xxx”功能主要工作于服务端，而非客户端。

IM开发干货系列文章

这是这个系列的第19篇文章，总目录如下：

即时通讯信息传递保证机制实现(一)：保证在线实时信息的可靠传递(二)：保证离线信息的可靠传递(三)：如何保证即时通讯信息的“顺序”和“一致性”？在即时通讯单人聊天和群聊中，状态同步应该使用“推”还是“拉”？即时通讯群聊消息这么复杂，怎么保证不丢不重？Android端 IM智能心跳算法(包括样例代码)的设计与实现探讨-移动端 IM登录时拉取数据如何作到省流量？简单易懂：基于集群的移动端 IM接入层负载均衡方案共享；浅析移动端 IM多点登陆和消息漫游原理； IM开发基本知识补课(一)：正确理解 HTTP SSO前置单点登陆接口原理； IM开发基本知识补课(二)：如何设计一个具有大量图片文件的服务器端存储架构？“IM开发基础知识补课”(三)：快速了解 Service Database读写分离原理及实践建议”“IM开发基础知识补课”(四)：如何在 HTTP短连接中正确理解 Cookie、 Session和 Token？”“IM群聊信息的已读回执功能如何实现？”即时通讯群聊信息是储存1 (即扩散读)或多储存(即扩散写)？信息技术开发基础知识补课(五)：简明，正确理解和使用好 MQ消息队列；探讨如何保证信息技术开发的时序，降低成本；信息技术开发基础知识补课(六)：数据库使用 NoSQL还是 SQL？看完这篇就够了！即时通讯中“邻居”功能实现的原则是什么？怎样才能有效的实施呢？《IM开发基础知识补课(七)：主流移动端账号登录方式的原理与设计思路》(本文)《IM开发基础知识补课(八)：最通俗、最彻底地了解字符乱码问题的本质》《IM如何实现扫码登入？搞懂一篇文章主流应用的扫码登陆技术原理 IM要做手机扫码登陆？首先来看一下微信的扫码登录功能的技术原理： IM开发的基本知识补课(九)：要开发 IM群集？首先要弄明白 RPC是什么！

三、“邻里”功能原理

事实上，“近邻”的功能原理并不复杂。

这需要做两件事：

一、所有使用即时通讯产品的用户，在使用“近邻”功能之前，先提交自己的地理位置信息；二、根据“我”的地理位置计算其他人与我之间的距离；三、按步骤2计算出的距离由近到远，排序。

产品技术上的具体实施原则，也易于理解：

一是手机端(ios, android等)，通过系统的 API可以轻松地抓取用户的当前位置(即经纬度数据)；二是基于第一步中的经纬度数据，可以轻松地计算两点之间的距离(计算公式原理，可以百度一下，我的几何和数学知识都还给了老师，不会告诉你)；三是第二步中的计算结果排序就简单多了，没什么好说的。

对 IM初学者来说，也许在第二步中是根据经纬度数据计算出两点之间的距离，觉得有些困难，实际上是根据数据公式(自已百度一下，有点复杂，哥就不贴了)，用代码实现，只有十多行代码。

这里有一个简单的 Java版本实现：

0102030405070809111213151718192021222324/**计算地球上任意两点的距离*@paramlong1第一点经度*@paramlat1*@paramlat2){double a, b, R; R=6378137;//地球半径lat1=lat1* Math. PI/180.0; PI/180.0; a=lat1-lat2; R=6378137;//地球半径lath1=lat1*Math.si n (b/2.0);sb2=Math.si n (b/2.0);**Math.si n (b/2.0)；

当执行代码测试时，可以将结果检查与此在线工具网页结合起来：http://www.hhlink.com/%E7%BB%8F%E7%BA%AC%E5%BA%A6/

看起来真简单啊！

自已从零开始实现的话，不会有困难吧？

好吧，从上一节的原理来看，到现在为止，它似乎真的很简单。

但是，如果是从零开始实现的话，那么 IM这一高性能、高并发性的场景就有一定的难度，难的不在于移动客户端，而在于服务端。

其中技术难题包括：

如何有效地计算两点之间的距离，对于高并发的服务端来说，一次只有一个计算，正如前一节所述的代码所说，还是有点不够有效；2)如何有效地计算地理圈(是否将所有当前在线的用户，与我的距离一一计算，然后根据距离筛选？这样做岂不是一场噩梦？

那么，有救了？回答是！回顾下一部分。

Redis中的 GEO地理位置相关指令，可以很好地解决以上问题

在服务端高性能场景下，针对“近人”这一位置服务领域的应用场景，可以使用 PG、 MySQL和 MongoDB等多个DB实现公共空间索引。

但 Redis却另辟蹊径，将有序队列 zset与 geohash编码相结合，实现了具有极高效率的空间搜索功能。

为了提供完整的“近邻”这样的功能或服务，最基本的就是实现“添加”，“删除”，“查找”等功能。这篇文章剩下的内容，分别在下面介绍，并着重于查询功能的解析。并且从 Redis源码的角度分析了它的算法原理，推算出查询的时间复杂性。

Redis相关资料：

1) Redis网站：https://redis.io2) Redis GEO指令说明(英文):https://redis.io/commands3) Redis GEO指令(中文):http://redisdoc.com/geo/geoadd.html

Redis的 GEO地理定位操作指南

从 Redis3.2版本开始， Redis提供了基于 geohash和顺序集合的地理位置相关功能。

6条与 Redis地理位置有关的操作指示(见官方文档)：

关于 Redis Geo模块的6种说明说明：

1) GEOADD：向指定的 key添加给定位置对象(纬度、经度、名字);2) GEOPOS：从 key返回所有给定位置对象的位置(经度和纬度);3) GEODIST：返回两个给定位置之间的距离；4) GEOHASH：返回一个或多个指定位置对象的Geohash表示；5) GEORADIUS：返回目标集合中所有离中心最远的位置对象；6) GEORADIUSBYMEMBER：以指定的位置对象为中心，返回与指定的最远距离的所有位置对象。

在这些方法中，结合使用 GEOADD和 GEORADIUS可以实现在“邻居”中“添加”和“查找”的基本功能。为了实现类似微信上的“邻居”功能，可以直接使用 GEORADIUSBYMEMBER命令。

在这里，“给定地点对象”是用户本身，而搜索对象是其他用户。但实际上， GEORADIUSBYMEMBER= GEOPOS+ GEORADIUS是指先查找用户位置，然后在此位置搜索附近符合位置间距离条件的其他用户对象。

在使用过程中注意：

Redis GEO操作仅包括“添加”和“查找”操作，而没有专门的“删除”命令。这主要是因为 Redis内部使用了有序集合(zset)来保存位置对象，可以使用 zrem进行删除；2)在 Redis源代码 geo. c的文件注释中，仅说明了 GEOADD、GEORADIUS和 GEORADIUSBYMEMBER的实现；3)从侧面看，另外三个命令也是辅助命令。

本论文剩余部分，将从源代码的角度，生理性地对 GEOADD和 GEORADIUS命令进行分析，剖析其算法原理。

Redis的 GEOADD指令是如何有效地执行的

7.1用途

1GEOADD key longitude latitude member [longitude latitude member ...]

上面的命令，向指定的 key添加给定的地点对象(纬度、经度、名字)。

key是集合名称， member是这个经纬度对应的对象。实际上，当需要存储的对象数量过多时，可以通过设置多key (例如一个省一个 key)的方式对对象集合进行变相的 sharding操作，以避免单集合数量过多。

已成功插入返回值：

1(integer) N

这里 N是成功插入的数目。

7.2来源分析

01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455/* 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值为 geohash值，它与其经纬度相对应的52位：

1)双精度类型精度为52位；

2) geohash以base32的方式进行编码，52 bits最多能存储10位 geohash值，对应于地理区域大小0.6*0.6米的网格。换言之，经过 Redisgeo变换的位置在理论上将存在大约0.3*1.414=0.424米的误差。

7.3算法摘要

简述一下 GEOADD命令的作用：

一是参数提取和检查；二是将输入 geohash值转换为52位的输入经纬度(score)；三是调用 ZADD命令，将member和相应的 score放入集合 key中。

八， 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编码。这一选项主要用于底层应用或调试，实际上没有什么实际意义。

SC| DESC：从近到远返回位置对象元素|从远到近返回位置对象元素。

COUNT count：选择匹配位置对象元素之前的 N个。(没有设置时将返回所有元素)

- STORE键：将地理位置信息保存到返回结果的指定键。

- STORedisT键：返回结果到中心点的距离保

I