【Redis】Redis 高级数据结构 - bitmap 和 hyperLogLog

业务场景

问题：假设我们现在有一个网站，需要记录每天的 UV 数据，那应该采取什么方案来实现呢？

如果只是统计网站的 PV，那么给每个网页配置一个独立的 Redis Key 即可，key 中可以加上日期信息实现历史数据的记录。这样每当有一个用户访问当前网站，就对应执行一次 incrby。但是 UV 不同，它需要实现去重的操作，说到去重，大家第一时间想起的可能就是 set 或者 hashmap 这样的数据结构。但是如果网站的流量达到千万级别甚至上亿，那么它们就会十分消耗内存了。因此，我们还可以考虑使用 redis 中其他的高级数据结构。

位图 bitmap

在日常的业务中，常常会存在一些场景需要维护大量的 boolean 类型数据，true 和 false 或者是 0 和 1。如果使用 hash 那种 key-value 的形式，当数据量非常大，达到上亿的量级时，对内存空间的需求可是极大的。Redis 提供的位图数据结构就可以用来处理这些业务，它基于 bit 进行存储，所以非常节约空间，进行二进制相关计算时速度非常快，而且方便扩容。打卡签到是一个常见的应用场景。

严格来说，位图不是数据结构，它实际上就是一个普通的字符串，通过 byte 数组的形式进行存储。初始化时，每个 bit 的数值默认为 0，set 操作后对应位置将置为 1。

常用命令：

setbit <key> <offset> <value>
getbit <key> <offset>
bitcount <key> <start> <end>
exists <key>
get <key>

当 key 不存在时，会自动生成一个新的字符串值。位图所包含的位的设置或者清除，取决于 value，它的值可以为 0 或者 1。offset 的数值必须大于或者等于 0，小于 2 32 2^{32} 232，即 bit 映射的范围被限定在 512 MB 以内。字符串会进行伸展以确保可以将 value 写入到更大的 offset 位置上，当字符串进行伸展时，空白位置以 0 填充。

对于 offset 较大的 setbit 操作来说，内存分配的过程有可能会造成 Redis 服务器被阻塞，因此需要考虑到性能问题。

相比于 set，bitmap 大大节省了内存，但是对于多个大对象的统计任务，仍然会占用很大的内存空间，因此这个时候使用 HyperLogLog 就能满足我们的需求。

HyperLogLog

基本概念

HyperLogLog 是一个用来做基数统计的算法结构，它可以通过输入元素来计算基数，而不会输入元素本身，通过对基数的计算进行统计，从而对原始数据提供不精确的去重统计方案。其标准误差为 0.81%，对于上千万或者上亿的数据统计来说，这样的结果是可以接受的。

常用命令：

pfadd <key> <value>
pfcount <key>
pfmerge <dest_key> <source_key>

在 Redis 里，每个 HyperLogLog 键最多可占用 12 KB 的内存，用于处理将近 2 64 2^{64} 264 个不同元素的基数。这与耗费内存去存储所有元素的集合相比节约了极大的内存。但是，由于 HyperLogLog 只会根据输入元素来计算基数，而不会存储基数元素本身，所以它不能像其他数据结构那样，返回输入的元素。

HyperLogLog 的实现是通过概率算法计算基数的数量，因此存在一定的误差。其概率算法主要是基于我们非常熟悉的“伯努利试验”。

伯努利试验

“伯努利试验”的典故来源于“抛硬币”：硬币拥有正反两个面，向上抛出一枚硬币，其落下后向上的面为正面或者反面的概率都为 50%。假设一直抛硬币，直到它第一次出现正面为止，我们就记录为一次完整的试验。这个试验就叫做“伯努利试验”。

如果执行了 n 次伯努利试验，那就意味着出现了 n 次的正面，假设每一次伯努利试验抛硬币的次数为 k i k_i ki​，那么必然存在一个最大值 k m a x k_{max} kmax​，就是说，满足：

• n 次伯努利试验的投掷次数都不大于 k m a x k_{max} kmax​
• n 次伯努利试验中，至少有一次的投掷次数等于 k m a x k_{max} kmax​

然后通过极大似然估算的方法，可以得到：
n = 2 k m a x n = 2^{k_{max}} n=2kmax​
需要注意的是，这个通过概率统计计算得到的结果，需要在足够多次试验的前提下才能得到合适的结果，如果次数过少，由于偶然性的存在，得到的结果误差会非常大。

从 LogLog 到 HyperLogLog

如果我们将上面说到的 n 次试验作为一轮，单独取出一轮的 k m a x k_{max} kmax​ 进行估算可能会存在比较大的误差，那么我们可以进行多轮的试验，取 k m a x k_{max} kmax​ 的平均数进行估算，那样的结果将会更加准确。因此，可以使用下面的这个估算公式：
D V = C ∗ m ∗ 2 k ‾ DV = C * m * 2^{\overline{k}} DV=C∗m∗2k
这里 DV 指的是 distinct value，也就是我们说的基数；m 代表试验的轮数；C 是修正因子常数；而 k ‾ \overline{k} k 就是每轮试验得到的 k m a x k_{max} kmax​ 的平均数。

LogLog 和 HyperLogLog 的区别就在于，前者使用的是一般平均数，也就是
k ‾ = （ k m a x 1 + . . . + k m a x m ) / m \overline{k} = （k_{max_1} + ... + k_{max_m}) / m k=（kmax1​​+...+kmaxm​​)/m
而后者使用的是调用平均数
H n = 1 1 n Σ i = 1 n 1 k m a x i = n Σ i = 1 n 1 k m a x i H_n = \frac{1}{\frac{1}{n}\Sigma^n_{i=1}\frac{1}{k_{max_i}}} = \frac{n}{\Sigma^n_{i=1}\frac{1}{k_{max_i}}} Hn​=n1​Σi=1n​kmaxi​​1​1​=Σi=1n​kmaxi​​1​n​
使用调和平均数的好处在于，它不容易受到极端值，尤其是大数值对计算结果的影响。

实现过程

那么 redis 中的 HyperLogLog 怎么跟上面的伯努利估算结果联系起来呢？实际上，HyperLogLog 算法在输入元素是通过存储元素 hash 值第一个出现 1 的位置进行计算的。具体实现过程是：

1. hash 比特串

通过 hash 函数，将输入的元素转化为比特串，这样比特串中就出现了大量的 0 和 1。然后我们可以从右往左，从低位往高位看，第一次出现 1 的最大次数就是我们需要的 k m a x k_{max} kmax​。

2. 分桶

分桶也就是我们试验中提到的分多少轮。一个比特串长度为 L，我们可以以 bit 为单位，将其看作一个长度为 L，每个元素分别为一个 bit 的数组。然后把这个数组平局分为 m 组，也就是分为 m 轮，每组含有相同的 bit 数，记为 p。

在 redis 中，HyperLogLog 的配置为：m = 16834，p=6，L=16834*6。因此占用的内存空间大小为：
16834 ∗ 6 / 8 / 1024 = 12 K B 16834 * 6 / 8 / 1024 = 12 KB 16834∗6/8/1024=12KB

3. 对应

在统计 UV 的问题中，我们常常通过 id 来标识每一个用户，因此可以对用户的 id 进行 hash 运算，从而得到比特串。从前面 redis 的配置我们可以知道，hyperLogLog 的实现设有 16384 = 2 14 2^{14} 214 个桶，每个桶有 6 位，最大可以表达的数字为 11111 1 ( 2 ) = 6 3 10 111111_{(2)} = 63_{10} 111111(2)​=6310​。

当 redis 输入元素时，会通过 hash 函数将元素转化成 64 位的比特串，将前 14 位的二进制值转换成对应的 10 进制值就是桶标号，14 位比特位刚好可以把配置的 14 个桶充分使用，不浪费资源。减去前 14 位剩下的 50 位中，第一次出现 1 的位置，将位置下标转换为 2 进制作为存储的值。由于每个桶是由 6 个 bit 组成，即最大可以存储的值为 2 6 − 1 = 63 > 50 2^6 - 1 = 63 \gt 50 26−1=63>50，因此可以确保转换得到的数值总是能够存储到桶中。

通过上述的操作，就可以将不同的 id 分配到不同的桶当中。如果不同的值被分配到同一个桶中，那么则保留较大的数值。最后，基本能够保证每个桶都有一个 k m a x k_{max} kmax​，此时调用 pfcount 时，就会按照前面介绍的估算方法，计算出统计值。

其他补充

常数 C 的选择

修正因子常数 C，它的选择常常与 m 有关。假设 m 为桶数，p 为 m 以 2 为底的对数，那么：
p = l o g 2 m p = log_2 m p=log2​m
然后常数 C 的取值满足一下规则：

switch (p) {
    case 4:
        C = 0.673 * m * m; break;
    case 5:
        C = 0.697 * m * m; break;
    case 6:
        C = 0.709* m * m; break;
    default:
        C = (0.7213 / (1 + 1.079 / m)) * m * m; break;
}

结果校正

在数据总量比较小的时候，很容易就预测偏大，所以我们需要对结果进行一些校正。假设 DV 代表估计的基数值，m 代表桶的数量，V 代表结果为 0 的桶的数目，log 表示自然对数，那么：

if DV < 2.5 * m:
    DV = m * log(m/V)

假设我分配了 64 个桶（即 m = 64），当数据量很小时，那肯定有大量桶中没有数据，也就说他们的估计值是 0，V 就代表这样的桶的数目。事实证明，这个校正的效果是非常好，在数据量小的时，估计得非常准确。

存储结构的调整

在 redis 中，HyperLogLog 结构最大都是固定的 16384 个桶。但是在实际应用中，其数据存储格式会有两种形态：

• 稀疏矩阵：HyperLogLog 在计数比较小时，它的存储空间是采用稀疏矩阵空间，因此内存占用较小。
• 密集矩阵：当计数慢慢变大的时候，稀疏矩阵占用的空间会逐渐变大，超过了阈值时会一次性转变为密集矩阵，占用空间大概是 12 K。

由于 HyperLogLog 占用的空间相对比较大，且存在一定的标准差，所以它更多被使用在大量数据的统计当中，而不适合统计单个用户相关的数据。