Redis 到底是怎么实现“附近的人”这个功能的？

点击上方“后端技术精选”，选择“置顶公众号”

技术文章第一时间送达！

作者：饿了么物流团队 juejin.im/post/5da40462f265da5baf410a11

juejin.im/post/5da40462f265da5baf410a11

前言：针对“附近的人”这一位置服务领域的应用场景，常见的可使用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

使用方式

<section class="mpa-template" mpa-preserve="t" mpa-from-tpl="t"><section class="mpa-template" mpa-preserve="t" mpa-from-tpl="t"><pre style="margin:0;padding:0;border-radius:none;background:none;"><code style="border-radius: 4px;font-size: 0.85em;margin: 0px 0.15em;background: rgb(40, 44, 52);color: rgb(171, 178, 191);display: block;padding: 6px;overflow-x: auto;white-space: nowrap;" class="hljs-default">GEOADD key longitude latitude member [longitude latitude member ...]

源码分析

double类型精度为52位； geohash是以base32的方式编码，52bits最高可存储10位geohash值，对应地理区域大小为0.6*0.6米的格子。换句话说经Redis geo转换过的位置理论上会有约0.3*1.414=0.424米的误差。

算法小结

GEORADIUS

使用方式

由于 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时是否真的只查询了主实例，还是进行了只读封装。感兴趣的朋友可以自己研究下。

源码分析

此段源码较长，看不下去的可直接看中文注释，或直接跳到小结部分

计算中心点范围：

对中心点及其周围8个geohash网格区域进行查找:

算法小结

算法分析

END

Java面试题专栏

欢迎长按下图关注公众号后端技术精选

原文始发于微信公众号（后端技术精选）：