前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分布式之redis的三大衍生数据结构

分布式之redis的三大衍生数据结构

作者头像
Java_老男孩
发布2019-12-02 16:49:34
4800
发布2019-12-02 16:49:34
举报
文章被收录于专栏:老男孩成长之路

引言

说起redis的数据结构,大家可能对五大基础数据类型比较熟悉:StringHashListSetSorted Set。那么除此之外,还有三大衍生数据结构,大家平时是很少接触的,即:bitmapshyperlogloggeo 另外,我觉得,这三个数据结构,只能说是锦上添花。真正在项目中,我还真没用过。 下面大家来看看这三大数据结构的定义用途

bitmaps

定义

说到这个bitmaps,其实它就是String,但它可以对String的位进行操作。然后呢,这个位操作,有自己的命令,所以和操作Stringredis命令又不大一样! 可以这么理解

bitmaps为一个以位为单位的数组,数组的每个单元只能存储0和1

下面举个例子,比如我们要做一个set操作,keywvalueh,那么执行如下命令

代码语言:javascript
复制
127.0.0.1:6379> set w h
OK
127.0.0.1:6379> get w
"h"

那么h的ASCII为0110 1000 接下来,你可以用位命令getbit命令取出,取出每一位的内容。

代码语言:javascript
复制
127.0.0.1:6379> getbit w 0 #用getbit获取w第0位的值
(integer) 0
127.0.0.1:6379> getbit w 1 #用getbit获取w第1位的值
(integer) 1
127.0.0.1:6379> getbit w 2 #用getbit获取w第2位的值
(integer) 1
127.0.0.1:6379> getbit w 3 #用getbit获取w第3位的值
(integer) 0
用途

网上传言,此结构用来统计一定时间内的,活跃的用户数,使用bitmap的结构比传统的set结构省空间。然而,这种用途有很大的局限性,我后文会说到。先说一下,网上的说法。 假设有30个用户,其中有5个用户,在2018-10-04这天登陆了。假设这5个用户的userid=2,4,8,11,12。 那么,我们假设key为users:2018-10-04,将其value值用于记录用户登陆信息。那么为了记录上述5个用户登陆过,我们将该value值的第2位,第4位,第8位,第11位,第12位设为1,即执行下述命令

代码语言:javascript
复制
127.0.0.1:6379> setbit users:2018-10-04 2 1
(integer) 0
127.0.0.1:6379> setbit users:2018-10-04 4 1
(integer) 0
127.0.0.1:6379> setbit users:2018-10-04 8 1
(integer) 0
127.0.0.1:6379> setbit users:2018-10-04 11 1
(integer) 0
127.0.0.1:6379> setbit users:2018-10-04 12 1
(integer) 0

这个时候,比如你要判断userid=11的用户,在2018-10-04这天,有没有登陆过,就执行下述命令

代码语言:javascript
复制
127.0.0.1:6379> getbit users:2018-10-04 11
(integer) 1

结果为1,就代表用户登陆过。如果返回结果为0,则代表用户没登陆过。 如果要统计,2018-10-04,这一天登陆的用户数,可以执行下面的命令

代码语言:javascript
复制
127.0.0.1:6379> bitcount users:2018-10-04
(integer) 5

上面的命令就可以统计出,2018-10-04,这一天5个用户登陆过。 ok,到这里大家就查不多能明白了。 先说一下,这里的userid=2,4,8,11,12,可以理解为偏移量。比如实际项目中的userid位1000002,那么偏移量就是2。大家在项目中,可以灵活变通。 然而这种方式有一个局限性。我们在实际项目中,如果userid是使用uuid生成的,那么,你要如何根据这些userid生成偏移量?莫非你还要去找一个hash函数,生成偏移量?就算找到了相应的hash函数,你能确保一定不发生hash碰撞,导致偏移量一致? 所以,大家了解即可。

HyperLogLog

定义

HyperLogLog并不是一种数据结构,而是一种算法,可以利用极小的内存空间完成独立总数的统计。 其实,大家可能对该算法比较陌生。我们java中有一个库叫stream-lib,其中也实现了HyperLogLog算法。我大概说一下该算法的原理,我不想去长篇大论的搬出数学论文来,大家看着也无聊,这里Hyper指的是超级的意思,它的前世是LogLog算法。这里我蜻蜓点水的装13一下,大家能领悟到精髓即可。 假设有如下对话

我:"小曲啊,假设啊,我一轮丢5次硬币,丢了很多轮之后,发现这几轮中,最多出现连续的2次反面1次正面,你能猜出来我丢了多少轮么!" 小曲:"应该没几轮吧,顶多就七八轮。" 我:"卧槽,这么机智,怎么算的?" 小曲:"很简单啊,正反面概率都是1/2,连着二次反面,一次正面。不就是1/21/21/2么!" 我:"那要是最多出现连续的4次反面1次正面呢?" 小曲:"那应该是很多很多轮吧!" 我:"果然机智!"

上述聊天,出自我和同事曲之间的,日常互吹!如有雷同,纯属巧合!

好了,原理讲完了!只是他的估算算法比较复杂!没这么简单而已!而且这么估,误差还比较大!下面给出算法的伪代码。

代码语言:javascript
复制
输入:一个集合
输出:集合的独立总数
算法:
     max = 0
     对于集合中的每个元素:
               hashCode = hash(元素)
               num = hashCode二进制表示中最前面连续的0的数量
               if num > max:
                   max = num
     最后的结果是2的(max + 1)次幂

需要说明的是

代码语言:javascript
复制
hashCode = hash(元素)

就是把你的输入元素,映射成二进制长串。映射成二进制长串后,就可以类比到我最先说的抛硬币的结果了。至于最后的结果为什么用(max+1),大家可以去查文献。毕竟这文章是在讲redis,不是在讲这个算法。而且这个算法,后面还经过了一系列演进,比如将入参集合分为m个部分,然后将m个部分的结果求一个平均数(avg),最后以2的(avg + 1)次幂,来估计独立总数!这些读者有兴趣可以自行查询!

用途

这个结构可以非常省内存的去统计各种计数,比如注册IP数、每日访问IP数。当然,存在误差!Redis官方给出的数字是0.81%的失误率。 用法也很简单如下所示

代码语言:javascript
复制
127.0.0.1:6379> pfadd ips:2018-10-04 "127.0.0.1" "127.0.0.2" "127.0.0.3" "127.0.0.4" 
(integer) 1
127.0.0.1:6379> pfcount ips:2018-10-04
(integer) 4

上面就是演示了,2018-10-04这天,约4个ip登陆了系统! 网上有一张和传统集合结构的占用空间对比图,贴出来,给大家看看

注意了,再强调一次,使用此结构是存在误差的!比如你pfadd了一百万条数据进去,结果pfcount的结果可能就999756条!

Geo

定义

Geo可以用于存储经纬度、计算两地之间的距离、范围计算等。其底层实现是zset。

用途

主要有以下六组命令

  • geoadd:增加某个地理位置的坐标。
  • geopos:获取某个地理位置的坐标。
  • geodist:获取两个地理位置的距离。
  • georadius:根据给定地理位置坐标获取指定范围内的地理位置集合。
  • georadiusbymember:根据给定地理位置获取指定范围内的地理位置集合
  • geohash:获取某个地理位置的geohash值。

我这里直接贴官网文档的例子,大家有兴趣可以自行查询. 首先,先给key增加两个坐标

代码语言:javascript
复制
redis> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2

其次,计算两个坐标之间的举例

代码语言:javascript
复制
redis> GEODIST Sicily Palermo Catania
"166274.15156960039"

最后,计算距离经纬度(15,37)距离100km200km范围内的坐标有哪些

代码语言:javascript
复制
redis> GEORADIUS Sicily 15 37 100 km
1) "Catania"

redis> GEORADIUS Sicily 15 37 200 km
1) "Palermo"
2) "Catania"
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 引言
  • bitmaps
    • 定义
      • 用途
      • HyperLogLog
        • 定义
          • 用途
          • Geo
            • 定义
              • 用途
              相关产品与服务
              云数据库 Redis
              腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档