1、引言
基本上以陌生人社交为主的IM产品里，都会增加“附近的人”、“附近的xxx”这种以LBS（地理位置）为导向的产品特色（微信这个熟人社交产品里为啥也有“附近的人”？这当然是历史原因了，微信当初还不是想借此引流嘛。。。），因为“附近的xxx”这种类似功能在产品运营早期，对于种子用户的积累有很大帮助（必竟某种需求，对于人类来说，是上帝赋予的最原始冲动，你懂的...）。
比如下图中的几款主流移动端IM中的“附近的xxx”功能：
那么，对于很多即时通讯（IM）的开发者初学者来说，“附近的人”或者类似功能，在技术实现上还有点摸不着头脑。本文将简要的为你讲解“附近的人”的基本理论原理，并以Redis的GEO系列地理位置操作指令为例，理论联系实际地为你讲解它们是如何被高效实现的。
阅读提示：本文适合有一定Redis使用经验的服务器后端开发人员阅读，IM移动客户端开发人员没有太多阅读的必要（理论原理倒是可以知道一下），必竟“附近的xxx”功能主要工作在服务端，而不在客户端。
2、IM开发干货系列文章
本文是系列文章中的第19篇，总目录如下：
3、“附近的人”功能原理
其实，“附近的人”功能原理并不复杂。
它需要做以下两件事情：
具体在产品技术上的实现原理，也很容易理解：
对于IM新手来说，可能对于第2步中的根据经纬度数据计算出两点距离，觉得有点难度，实际上根据数据公式（自已百度一下吧，有点复杂，哥不贴了），用代码来实现，只有短短的十来行代码。
下面是一个简单的Java版实现：
在进行代码测试的时候，可以结合这个在线工具网页进行结果检验：http://www.hhlink.com/%E7%BB%8F%E7%BA%AC%E5%BA%A6/
嗯，看起来好简单！
4、自已从零实现的话，没有难度吗？
嗯，通过上一节的原理讲解，目前为止，看起来确实很简单。
但，如果自已从零实现的话，对于IM这种高性能、高并发场景来说，确实有一点难度，难不在移动客户端，而是在服务端。
技术难点主要包括：
那，有救吗？答案是有！继续看下一节。
5、Redis里的GEO地理位置相关指令，就能很好的上述问题
针对“附近的人”这一位置服务领域的应用场景，服务端高性能场景下，常见的可使用PG、MySQL和MongoDB等多种DB的空间索引进行实现。
而Redis另辟蹊径，结合其有序队列zset以及geohash编码，实现了空间搜索功能，且拥有极高的运行效率。
要提供完整的“附近的人”这样的功能或服务，最基本的是要实现“增”、“删”、“查”的功能。本文余下的文字，以下将分别进行介绍，其中会重点对查询功能进行解析。并将从Redis源码角度对其算法原理进行解析，并推算查询时间复杂度。
Redis相关资源：
6、Redis的GEO地理位置操作指令
自 Redis 3.2版 开始，Redis基于geohash和有序集合提供了地理位置相关功能。
Redis中的6个地理位置相关操作指令（见官方文档）：
Redis Geo模块的6个指令用途说明：
其中，组合使用GEOADD和GEORADIUS可实现“附近的人”中“增”和“查”的基本功能。要实现类似于微信中“附近的人”功能，可直接使用GEORADIUSBYMEMBER命令。
其中“给定的位置对象”即为用户本人，搜索的对象为其他用户。不过本质上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用户位置再通过该位置搜索附近满足位置相互距离条件的其他用户对象。
使用时的注意点：
本文的余下内容，将会从源码角度入手，着生理地对GEOADD和GEORADIUS命令进行分析，剖析其算法原理。
7、Redis的GEOADD指令是如何高效实现的
7.1 使用方式
以上命令，将给定的位置对象（纬度、经度、名字）添加到指定的key。
其中，key为集合名称，member为该经纬度所对应的对象。在实际运用中，当所需存储的对象数量过多时，可通过设置多key(如一个省一个key)的方式对对象集合变相做sharding，避免单集合数量过多。
成功插入后的返回值：
其中N为成功插入的个数。
7.2 源码分析
通过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]
以上指令，将以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象。
由于 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，如：
8.2 源码分析
此段源码较长，看不下去的可直接看中文注释，或直接跳到小结部分。
上文代码中最核心的步骤有两个：
对应的是geohashGetAreasByRadiusWGS84和membersOfAllNeighbors两个函数。
我们依次来看。
计算中心点范围：
对中心点及其周围8个geohash网格区域进行查找:
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本身基于内存的存储特性，在实际使用过程中有非常高的运行效率。
以上，就是本文的全部答案，不知是否对你有帮助！