Redis深度历险阅读笔记(4)

Bitmap,位图

bitmap,每一位用来存放一个状态,以节约空间。用于数据量大、但是状态少的情况。通常是用来判断某个状态是否存在。

事实上,我在之前准备面试的时候,已经整理过一篇关于海量数据的文章:Carey’s 海量数据

Redis提供了位图数据结构。它的内容就是byte数组,我们可以用get/set来查改整个位图,也可以使用getbit/setbit来处理位图中的元素。

使用方法

我们可以将位图看作普通字符串,只是包含了特殊的指令。

> set key value
OK

> getbit key 1       # 获取第1个位置的值
(integer) 1
> setbit key 1 0     # 设置第1个位置的值为0
(integer) 1
> get key
"6alue"

统计和查找

通过bitcount可以统计指定范围内1的个数,通过bitpos可以查找指定范围内第一个出现的0或1。

应用场景:以用户id为key,统计签到次数

> set key value
OK

> bitcount key 0 1          # 查询第0-1位字符中1的个数
(integer) 8

> bitpos key 1              # 第一个1出现的位置
(integer) 1
> bitpos key 0              # 第一个0出现的位置
(integer) 0

> bitpos key 1 1 n(n>=1)    # 从第一个字符开始,第一个1出现的位置
(integer) 9

注:区间范围是针对字符串的,而非bit位,因此区间的位范围必须是8的倍数。(这里感觉有点坑啊,既然是bitcount,为什么不是按照bit位的区间范围来计算?)

魔术指令bitfield「3.2」

bitfield有三个子指令,分别是get/set/incrby,它们都可以对指定位片段进行读写,但是最多只能处理64个连续的位,如果超过64位,就得使用多个子指令,bitfield可以一次执行多个子指令。

> set key value
OK

> bitfield key get u8 0      # 获取第0个bit位开始的8位,返回无符号数('v'的ASCII码)
(integer) 118
> bitfield key get u8 8      # 同上,'a'的ASCII码
(integer) 97

> bitfield key set u8 16 97  # 将第16个bit位开始的8位设置为无符号数97的二进制码
(integer) 118
> get key                    # 这个时候获取到的第三位字符变成了'a'
"vaaue"

> bitfield key incrby u8 16 1 # 将第16个bit位开始的8位无符号数自增1,默认策略溢出则折返
(integer) 98
> get key
"vabue"

incrby溢出策略

> bitfield key overflow [param] incrby u8 16 1
  1. wrap:默认值,折返
  2. sat:饱和截断,超过了范围就停留在最大最小值
  3. fail:报错不执行

HyperLogLog,基数统计

提供不精确的去重计数方案,标准误差是0.81%。

使用方法

> pfadd key user1
(integer) 1
> pfcount key
(integer) 1

pf

指:Philippe Flajolet,HyperLogLog这个数据结构的发明人

Philippe Flajolet

pfmerge

将多个pf计数值累计在一起形成一个新的pf值。

> pfadd key1 a
> pfadd key1 b
> pfadd key1 c
> pfcount key1
(integer) 3
> pfadd key2 a
> pfadd key2 d
> pfcount key2
(integer) 2
> pfmerge key1 key2        # 将key2中的计数值合入key1
OK
> pfcount key1             # 因为key1中已有key2中的'a',所以值为4
(integer) 4

消耗

计数较小时,采用稀疏矩阵,空间占用很小。 计数较大时,一次性转变为稠密矩阵,占用12k。 因此不适用与以大量数据为key的情况:比如统计单个用户相关的数据。

算法原理

HHL demo

HHL

给定N个随机数,计算这些随机数末尾的第一个1出现的位置,得到maxbit=k,N约等于2^k。

简单来说可以将一个二进制数比做一次抛硬币实验,第一个1出现即第一次抛到正面。进行了N次进行抛硬币实验,每次分别记录下第一次抛到正面的抛掷次数k,那么可以用n次实验中最大的抛掷次数kmax来预估实验组数量N:N=2^kmax。

这样的实验结果并不足够准确,HHL为了提高准确度,引入了【分桶平均】的概念:

将统计数据划分为m个桶,每个桶分别统计各自的kmax,算出N后,以m个桶的调和平均值为N,以期望过滤到不健康的数值,减小误差。

Redis中用了2^14个桶,每个桶的maxbits需要6个bits来存储,最大可以表示maxbits=63,最大可以估算2^64-1个数于是总共占用内存就是2^14*6/8=12k字节。

BloomFilter,布隆过滤器

一个可以存放大量数据的Set,但是呢,不怎么精确。 不精确是指:当它说某个值存在的时候,这个值可能不存在,但是它说某个值不存在,这个值一定不存在。

使用方法「4.0」

首先要拉取支持布隆过滤器的redis镜像:

docker pull redislabs/rebloom
docker run --name blredis -d -p6379:6379 redislabs/rebloom
docker exec -it bfredis redis-cli

试一下布隆过滤器:

> bf.add key user1
(integer) 1
> bf.exists key user1
(integer) 1
> bf.exists key user2
(integer) 0
可以更改默认布隆过滤器的参数
> bf.reserve key 0.0001 100000 # 将错误率设置为0.0001,预计元素数量为100000
OK

注意事项

  1. 错误率默认值:0.01,预计元素数量默认值:100
  2. 错误率越小越耗内存,预期元素数量越大越耗内存
  3. 超出预期元素数量,误判率会上升

原理

它引入了k个哈希函数,通过哈希函数映射k个位置置为1,这样子更加节约内存,但是会出现一定的误判率。

BloomFilter

注:如果要错误率和预期元素数量计算内存,可以使用:布隆计算器

Reference

神奇的HyperLogLog算法

后记

写完这篇,我就要回学校写毕业论文啦!可能会鸽一段时间,也可能不。(谁知道呢)

Table of Contents