Redis高效检索地理位置的原理解析

Redis GEO 用做存储地理位置信息,并对存储的信息进行操作。通过geo相关的命令,可以很容易在redis中存储和使用经纬度坐标信息。Redis中提供的Geo命令有如下几个:

  • geoadd:添加经纬度坐标和对应地理位置名称。
  • geopos:获取地理位置的经纬度坐标。
  • geodist:计算两个地理位置的距离。
  • georadius:根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
  • georadiusbymember:根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合。
  • geohash:计算一个或者多个经纬度坐标点的geohash值。

要理解Redis的GEO相关的命令是如何实现了,就得先理解geohash的原理,本质上这些命令就是对geohash数据的封装而已。

geohash

geohash是2008年Gustavo Niemeye发明用来编码经纬度信息的一种编码方式,比如北京市中心的经纬度坐标是116.404844,39.912279,通过12位geohash编码后就变成了wx4g0cg3vknd,它究竟是如何实现的?其实原理非常简单,就是二分,整个编码过程可以分为如下几步。

1. 转二进制

上过初中地理的我们都知道,地球上如何一个点就可以标识为某个经纬度坐标,经度的取值范围是东经0-180度和西经0-180度,维度的取值范围是北纬0到90和南纬0-90度。去掉东西南北,可以分别认为经度和维度的取值范围为[-180,180]和[-90,90]。

我们先来看经度,[-180,180]可以简单分成两个部分[-180,0]和[0,180],对于给定的一个具体值,我们用一个bit来标识是在[-180,0]还是[0,180]区间里。然后我们可以对这两个子区间继续细分,用更多的bit来标识是这个值是在哪个子区间里。就好比用二分查找,记录下每次查找的路径,往左就是0往右是1,查找完后我们就会得到一个0101的串,这个串就可以用来标识这个经度值。

同理维度也是一样,只不过他的取值返回变成了[-90,90]而已。通过这两种方式编码完成后,任意经纬度我们都可以得到两个由0和1组成的串。
比如还是北京市中心的经纬度坐标 116.404844,39.912279,我们先对116.404844做编码,得到其二进制为:

11010010110001101101

然后我们对维度39.912279编码得到二进制为:

10111000110000111001

2. 经纬度二进制合并

接下来我们只需要将上述二进制交错合并成一个即可,这里注意经度占偶数位,纬度占奇数位,得到最终的二进制。

1101101110000200111100000001111011010011

3. 将合并后的二进制做base32编码

最后我们将合并后的二进制做base32编码,将连续5位转化为一个0-31的十进制数,然后用对应的字符代替,将所有二进制位处理完后我们就完成了base32编码。编码表如下:

最终得到geohash值wx4g0cg3vknd

geohash是将空间不断的二分,然后将二分的路径转化为base32编码,最后保存下来,从原理可以看出,geohash表示的是一个区间,而不是一个点,geohash值越长,这个区间就越小,标识的位置也就越精确,下图是维基百科中不同长度geohash下的经纬度误差(lat:维度,lng:经度)

geohash的用途及问题

geohash成功的将一个二维信息编码成了一个一维信息,这样编码我觉得有两个好处:1. 编码后数据长度变短,利于节省存储。2. 利于使用前缀检索。我们来详细说下第二点。

从上文中geohash的实现来看,只要两个坐标点的geohash有共同的前缀,你们我们就可以肯定这两个点在同一个区域内 (区域大小取决于共同前缀的长度)。这种特性给我们带来的好处就是,我们可以把所有坐标点按geohash做增序索引,然后查找的时候按前缀筛选,大幅提升检索的性能。

举个例子,假设我要找北京国贸附近3公里内的餐馆,已知国贸的geohash是wx4g41,那我也很轻易就可以计算出来我需要扫描哪些区域内的点。但有个点需要注意,上文我已经提到过,geohash值实际上是代表一个区域,而不是一个点,找到一批候选点之后还需要遍历一次计算下精确距离。

geohash有个需要注意的问题。geohash是将二维的坐标点做了线下编码(如下图),有时候可能会给人一个误解就是如果两个geohash之间二进制的差异越小,这两个区间距离就越近,这完全是错误的,比如如下图0111和1000,这俩区间二进制只差0001但实际物理距离比较远。

如果上图还不明显的话,我从Wikipedia上拿到一张图,虚线是线性索引的路径,被虚线链接的两个块geohash值是非常相近的,如下图的(7,3)和(0,4),geohash值会非常相近,但实际物理距离非常远,这就是geohash的突变现象,这也导致了不能直接根据geohash的值来直接判定两个区域的距离大小。

但在实际使用geohash过程中,时常会遇到跨域搜索的情况,比如我要在上图(3,3)这个区间内某个点上搜索距它1个距离单位的所有其他点集,这个点集有可能横跨(3,3)加上它周围8个邻域的9个区间,突变的问题会导致这9个区间的geohash不是线性跳转的,但也不是没法计算,实际上可以通过特殊的位运算可以很轻易计算出某个geohash的8个邻域,具体可参考redis源码中src/geohash.c中geohashNeighbors()的具体实现,geohashNeighbors使用了geohash_move_x和geohash_move_y两个函数实现了geohash左右和上下的移动,这样可以很容易组合出8个邻域的geohash值了。

static void geohash_move_x(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits & 0x5555555555555555ULL;

    uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);

    if (d > 0) {
        x = x + (zz + 1);
    } else {
        x = x | zz;
        x = x - (zz + 1);
    }

    x &= (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

static void geohash_move_y(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits & 0x5555555555555555ULL;

    uint64_t zz = 0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2);
    if (d > 0) {
        y = y + (zz + 1);
    } else {
        y = y | zz;
        y = y - (zz + 1);
    }
    y &= (0x5555555555555555ULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

Geo in redis

上文中花了大量篇幅讲解了geohash的实现,其实看到这里,你基本上已经理解了redis中的geohash的实现了。本质上redis中的geo就是对geohash的封装,具体geohash相关的代码就不给大家列了(可自行查阅),就给大家介绍下redis geo里的大体流程。
首先,可能大家最好奇的是geohash在redis中是怎么存储的,从geoadd命令的实现可以一窥端倪。

/* GEOADD key [CH] [NX|XX] long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
    int xx = 0, nx = 0, longidx = 2;
    int i;

    /* 解析可选参数 */
    while (longidx < c->argc) {
        char *opt = c->argv[longidx]->ptr;
        if (!strcasecmp(opt,"nx")) nx = 1;
        else if (!strcasecmp(opt,"xx")) xx = 1;
        else if (!strcasecmp(opt,"ch")) {}
        else break;
        longidx++;
    }

    if ((c->argc - longidx) % 3 || (xx && nx)) {
        /* 解析所有的经纬度值和member,并对其个数做校验 */
            addReplyErrorObject(c,shared.syntaxerr);
        return;
    }

    /* 构建zadd的参数数组 */
    int elements = (c->argc - longidx) / 3;
    int argc = longidx+elements*2; /* ZADD key [CH] [NX|XX] score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createRawStringObject("zadd",4);
    for (i = 1; i < longidx; i++) {
        argv[i] = c->argv[i];
        incrRefCount(argv[i]);
    }

    /* 以3个参数为一组,将所有的经纬度和member信息从参数列表里解析出来,并放到zadd的参数数组中 */
    for (i = 0; i < elements; i++) {
        double xy[2];

        if (extractLongLatOrReply(c, (c->argv+longidx)+(i*3),xy) == C_ERR) {
            for (i = 0; i < argc; i++)
                if (argv[i]) decrRefCount(argv[i]);
            zfree(argv);
            return;
        }

        /* 将经纬度坐标转化成score信息 */
        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[longidx + i * 3 + 2];
        argv[longidx+i*2] = score;
        argv[longidx+1+i*2] = val;
        incrRefCount(val);
    }

    /* 转化成zadd命令所需要的参数格式*/
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

原来geo的存储只是zset包了一层壳(是不是有点小失望),关于zset的具体实现可以参考我之前写的文章redis中skiplist的实现。

我们再来详细看下georadius的大体执行流程(代码偏长,故删除大量细节代码)。

void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
    robj *storekey = NULL;
    int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */

    /* 根据key找找到对应的zojb */
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

    /* 解析请求中的经纬度值 */
    int base_args;
    GeoShape shape = {0};
    if (flags & RADIUS_COORDS) {
    /*
     * 各种必选参数的解析,省略细节代码,主要是解析坐标点信息和半径
     */
    }

    /* 解析所有的可选参数. */
    int withdist = 0, withhash = 0, withcoords = 0;
    int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
    int sort = SORT_NONE;
    int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
    long long count = 0;  /* Max number of results to return. 0 means unlimited. */
    if (c->argc > base_args) {
    /*
     * 各种可选参数的解析,省略细节代码
     */
    }

    /* Get all neighbor geohash boxes for our radius search
     * 获取到要查找范围内所有的9个geo邻域 */
    GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(&shape);

    /* 创建geoArray存储结果列表 */
    geoArray *ga = geoArrayCreate();
    /* 扫描9个区域中是否有满足条的点,有就放到geoArray中 */
    membersOfAllNeighbors(zobj, georadius, &shape, ga, any ? count : 0);

    /* 如果没有匹配结果,返回空对象 */
    if (ga->used == 0 && storekey == NULL) {
        addReply(c,shared.emptyarray);
        geoArrayFree(ga);
        return;
    }

    long result_length = ga->used;
    long returned_items = (count == 0 || result_length < count) ?
                          result_length : count;
    long option_length = 0;

    /*
     * 后续一些参数逻辑,比如处理排序,存储……
     */
    // 释放geoArray占用的空间
    geoArrayFree(ga);
}

上述代码删减了大量细节,有兴趣的同学可以自行查阅。不过可以看出georadius的整体流程非常清晰。

解析请求参数。计算目标坐标所在的geohash和8个邻居。在zset中查找这9个区域中满足距离限制的所有点集。处理排序等后续逻辑。清理临时存储空间。

结语

由于文章篇幅有限,而且着重讲解了geohash的实现,并未展开讲解redis中geo相关的各种细节,如读者有兴趣可以详细阅读redis中的src/geo.c了解各类细节。

参考资料

wikipedia geohash

Geohash算法原理及实现

本文是Redis源码剖析系列博文,同时也有与之对应的Redis中文注释版,有想深入学习Redis的同学,欢迎star和关注。
Redis中文注解版仓库:https://github.com/xindoo/Redis
Redis源码剖析专栏:https://zxs.io/s/1h

以上就是Redis是如何高效检索地理位置的详细内容,更多关于Redis检索地理位置的资料请关注我们其它相关文章!

(0)

相关推荐

  • PHP redis实现超迷你全文检索

    情景: 我们平台有好多游戏, 运营的同事在查询某一款游戏的时候, 目前使用的是html的select下拉列表的展现形式, 运营的同事得一个个去找,然后选中,耗时又费眼 效果: 输入"三国"或者"国三", 将自动列出所有包含"三国"的游戏名字, 输入不限顺序; 例如输入"杀三国",仍然会将"三国杀"这款游戏找出来 实现: 我用redis的集合+PHP的array_intersect()和mb系列函数, 实现了

  • redis数据库查找key在内存中的位置的方法

    一.预先需要了解的知识1.redis 中的每一个数据库,都由一个 redisDb 的结构存储.其中,redisDb.id 存储着 redis 数据库以整数表示的号码.redisDb.dict 存储着该库所有的键值对数据.redisDb.expires 保存着每一个键的过期时间.2.当redis 服务器初始化时,会预先分配 16 个数据库(该数量可以通过配置文件配置),所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中.当我们选择数据库 select n

  • Redis高效检索地理位置的原理解析

    Redis GEO 用做存储地理位置信息,并对存储的信息进行操作.通过geo相关的命令,可以很容易在redis中存储和使用经纬度坐标信息.Redis中提供的Geo命令有如下几个: geoadd:添加经纬度坐标和对应地理位置名称. geopos:获取地理位置的经纬度坐标. geodist:计算两个地理位置的距离. georadius:根据用户给定的经纬度坐标来获取指定范围内的地理位置集合. georadiusbymember:根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合. geoh

  • php redis setnx分布式锁简单原理解析

    我就废话不多说了,大家还是直接看代码吧~ <?php //高并发分布式锁 header("Content-type:text/html;charset=utf-8"); $redis = new Redis(); $redis->connect('127.0.0.1', 6379); echo "Connection to server sucessfully"; //echo $redis->get("name");exit;

  • 高效异步redis客户端aredis优劣势原理解析

    背景 aredis 是一款由同步的 redis 客户端 redis-py 改写而成的高效的异步 redis 客户端,在最新的 1.0.7 版本中完成了对于 redis 集群的支持. 改动 主要重写了底部建立连接和读取数据部分的代码,接口部分都向下兼容,便于使用者从 redis-py 的同步代码迁移到 async 和 await 的协程版本,详细文档请看 aredis 文档 使用 安装 pip install aredis 具体姿势可以参阅项目文档和例子,接口向下兼容 redis-py,支持 Py

  • Redis数据结构SortedSet的底层原理解析

    目录 概述 一些常用命令 实现 跳跃表 跳表的插入 压缩列表 概述 一些常用命令 存储:zadd key score value 获取:zrange key start end 获取:同时获取分数:zrange key start end with score 删除:zrem key value 存储的时候我们可以发现,是有一个score(分数)的,这个就是用来排序的字段. 实现 先说结论,SortedSet底层,根据配置会在不同的时候选用两种不同的数据结构zset,或ziplist进行存储:

  • 使用Redis实现令牌桶算法原理解析

    在限流算法中有一种令牌桶算法,该算法可以应对短暂的突发流量,这对于现实环境中流量不怎么均匀的情况特别有用,不会频繁的触发限流,对调用方比较友好. 例如,当前限制10qps,大多数情况下不会超过此数量,但偶尔会达到30qps,然后很快就会恢复正常,假设这种突发流量不会对系统稳定性产生影响,我们可以在一定程度上允许这种瞬时突发流量,从而为用户带来更好的可用性体验.这就是使用令牌桶算法的地方. 令牌桶算法原理 如下图所示,该算法的基本原理是:有一个容量为X的令牌桶,每Y单位时间内将Z个令牌放入该桶.如

  • Redis主从配置和底层实现原理解析(实战记录)

    我们使用Redis的时候往往都是主从模式或者集群架构,不会使用单台Redis服务. 一.Redis主从配置实战 我们使用master节点写输入,然后将数据同步到slave节点,从节点可以提供读取或者备份的功能,分担master节点压力. redis主从架构搭建,配置从节点步骤 1. 复制一份redis.conf文件为redis-6380.conf cp ./redis.conf ./conf/redis-6380.conf 2.打开redis-6380.conf配置文件,将相关配置修改为如下值:

  • Redis 的查询很快的原因解析及Redis 如何保证查询的高效

    目录 Redis如何保证高效的查询效率 为什么Redis比较快 Redis中的数据结构 1.简单动态字符串 2.链表 3.字典 4.跳表 5.整数数组 6.压缩列表 为什么单线程还能很快 基于多路复用的高性能I/O模型 单线程处理IO请求性能瓶颈 总结 参考 Redis 如何保证高效的查询效率 为什么 Redis 比较快 Redis 中的查询速度为什么那么快呢? 1.因为它是内存数据库: 2.归功于它的数据结构: 3.Redis 中是单线程: 4.Redis 中使用了多路复用. Redis 中的

  • python实现布隆过滤器及原理解析

    在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

  • SpringBoot服务监控机制原理解析(面试官常问)

    前言 任何一个服务如果没有监控,那就是两眼一抹黑,无法知道当前服务的运行情况,也就无法对可能出现的异常状况进行很好的处理,所以对任意一个服务来说,监控都是必不可少的. 就目前而言,大部分微服务应用都是基于 SpringBoot 来构建,所以了解 SpringBoot 的监控特性是非常有必要的,而 SpringBoot 也提供了一些特性来帮助我们监控应用. 本文基于 SpringBoot 2.3.1.RELEASE 版本演示. SpringBoot 监控 SpringBoot 中的监控可以分为 H

  • Java常用集合与原理解析

    目录 迭代器 集合框架中的接口 具体集合 散列码 树集 队列 优先队列 映射 基本映射 映射视图 弱散列映射 链接散列集合映射 枚举集与映射 标识散列映射 Java 最初版本只为常用的数据结构提供了很少的一组类:Vector.Stack.Hashtable.BitSet 与 Enumeration 接口 迭代器 public interface Collection<E> { boolean add(E element); Iterator<E> iterator(); ... }

随机推荐