Redis高级数据结构 HyperLogLog，布隆过滤器

56 阅读 0 评论 37 点赞

我是靠谱客的博主大气鸡，最近开发中收集的这篇文章主要介绍Redis高级数据结构 HyperLogLog，布隆过滤器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Redis中的高级数据结构
五、HyperLogLog
HyperLogLog：redis高级数据结构，用于解决统计问题，提供不精确的去重计数方案（标准误差0.81%）
1、使用方法
pfadd：增加计数（和set的asdd用法一样，来一个往里面放一个）
pfcount：获取计数（和scard的用法一样，直接获取计数）
pfmerage：将多个pf计数累加再一起形成一个新的pf值

2、使用HyperLogLog注意事项
HyperLogLog不太适用于统计单个用户的相关数据，因为这个数据结构需要12kb的存储空间，用户量过大时空间成本过高
在redis中再计数比较小时HyperLogLog使用的是稀疏矩阵，计数变大时占用空间超过阈值时，变成稠密矩阵（才会占用12kb）
再redis中HyperLogLog实现中使用多个桶（六位寄存器）进行独立计数，一共有16384个（2^14）,
每个桶的maxbits需要6个bit最大可以表示maxbits=63，所以每个键占内存（2^14）*6/8=12kb

六、布隆过滤器（高级数据结构）
主要用于类如新闻推送的（大量数据）去重
Bloom Filter特点：
去重时节省空间（90%以上）
稍微有一点不准确
Bloom Filter是什么
Bloom Filter：为一个不精确的set，当使用contians判断某个对象是否存在是可能误判
如果布隆过滤器判断某个值不存在时，这个值肯定不存在；如果是存在时就不一定存在

Bloom算法：类似于hash set 用来判断某个元素（key）是否在某个集合中
算法：

首先需要k个hash函数，每个函数可以把key散列成为1个整数
初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
优点：不需要存储key，节省空间
缺点：
算法判断key在集合中时，有一定的概率key其实不在集合中
无法删除

Redis中的Bloom Filter
利用Redis的BitMap实现布隆过滤器的底层映射。使用 docker 可以直接在 redis 中体验布隆过滤器。
命令：

docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
docker exec -it bloomfilter redis-cli

布隆过滤器的基本用法：
bf.add: 添加元素，一次添加一个元素
bf.exists:查找元素是否存在，一次查询一个
bf.madd:一次添加多个元素
bf.mexists：一次查询多个元素
bf.reserve:显式创建，如果key存在则报错
三个参数：
key
error_rate：错误率，越小需要的空间越大（默认：0.01）
initial_size:预计放入的元素数量，当实际数量超出这个数值时，误判率会上升
需要提前设置一个较大的数值避免超出导致误判率上升（默认100）
注意：
initial_size过大会浪费存储空间，过小会造成seror_rate上升，
使用前需要尽可能准确的预估元素数量，还需要加上一定的冗余空间

布隆过滤器的原理
布隆过滤器：在redis的数据结构中就是一个大型位数组和几个不一样的无偏hash函数
无偏：就是可以把元素的hash值算的比较均匀，使得元素被hash映射到数组中的位置比较随机
添加（add）：
向布隆过滤器添加一个key时，会使用多个hash函数对key进行hash，得到整数索引值，
然后对数组长度取模运算找到一个位置，每个hash函数都会算出一个不同的位置，将这些位置都置为1，完成add操作
查询key是否存在：
和add一样hash算出那几个位置，查看是否都为1，有一个为0则不存在，如果全为1也不一定存在

七、简单限流
限流：当系统处理能力有限时，阻止计划外的请求对系统施压
简单限流：使用滑动时间窗口（定宽），使用redis中的zset中的score的值，圈出可通过的时间范围
只需要保留时间窗口内的数据外的可以舍弃
缺点：如果短时间内的记录很大，就会消耗大量的空间

漏斗限流：容量有限，漏嘴的流速代表，系统允许该行为的最大频率，剩余空间代表当前行为可以持续进行的数量
redis中的限流模块为Redis-Cell(使用漏斗算法)，提供原子限流指令
指令：cl.throttle
cl.throttle alvin:reply 15 30 60 1
代表：允许用户alvin的回复频率为60s最多30次，漏斗的初始容量为15