Redis 概率相关的数据类型

HyperLogLog

估算集合中唯一值的个数，不精确的去重计数，标准误差为 0.81%，最多占用 12 KB 的空间。

原理：基于伯努利实验，抛硬币想要连续 K 次均为反面，则需要尝试 N 次实验。N 和 K 的关系为 N = 2^K。HyperLogLog 将值 hash 为数字，记录最低位连续 0 的最大数量作为 K，进而估计出唯一值的个数 N。为了避免极端值的影响，使用了 2¹⁴= 16384 个桶，然后取调和平均数。

一共 16384 个桶，每个桶用 6bit 记录最大连续数，空间为 16384 * 6 / 8 = 12288byte = 12kb。

Bloom filter 布隆过滤器

判断某个元素是否存在于某个集合中，可能会误判。如果返回不存在则值一定不存在，如果返回存在则值可能存在也可能不存在。

添加的原理：对值使用 N 个 hash 函数得到 N 个 hash 值，hash 值对 bitmap 长度取模后，将 bitmap 的 N 个位置设置为 1。

判断是否存在的原理：使用同样的方式 hash 取模后，判断 bitmap 的 N 个位置，如果有位置是 0，则肯定不存在，如果都为 1 则可能存在。

创建 Bloom filter 时可以指定误报率、预期容量、扩展因子。当容量达到上限时，会自动创建子 Bloom filter，容量 = 当前预期容量 * 扩展因子。子过滤器会增加查询时的延迟，因为若一个子过滤器返回不存在，会继续检查下一个过滤器。

Cuckoo filter 布谷鸟过滤器

与 Bloom filter 一样，用于判断某个元素是否存在于某个集合中，也可能会误判。如果返回不存在则值一定不存在，如果返回存在则值可能存在也可能不存在。

Bloom filter 不支持删除，想要删除元素必须重建。而 Cuckoo filter 支持删除。

Count-min sketch

估计集合中某个元素出现的频率。可能高估，但绝不会低估。

更新的原理：有w * d的二维数组，且有 d 个 hash 函数，执行update(element, count)时，使用d个 hash 函数对element进行 hash 得到 d 个 hash 值，然后分别对w取模，得到 d 个数组下标index，然后将 d 个数组对应index位置的值累加上count。

index_1 = hash_1(element) % w index_2 = hash_2(element) % w ... index_d = hash_d(element) % w arr_1[index_1]+=count arr_2[index_2]+=count ... arr_d[index_d]+=count

查询频率的原理：按照上述步骤得到 d 个数组下标后，分别获取数组对应位置的值后再取最小值。

index_1 = hash_1(element) % w index_2 = hash_2(element) % w ... index_d = hash_d(element) % w res = min(arr_1[index_1], arr_2[index_2],..., arr_d[index_d])

取最小值的原因：多个不同的元素可能发生 hash 碰撞，导致该位置的计数是多个元素的总和。一个元素在 d 个数组中计数的最小值是最接近真实值的一个。

TOPK

估算数据流中出现频率最高的 K 个元素。

原理：基于 HeavyKeepers 算法，使用了最小堆和指数衰减计数策略。由一个最小堆和二维数组构成，最小堆负责实时维护 topk；二维数组负责统计元素出现的频率，与 Count-min sketch（简称 CMS） 的操作类似，区别在于 CMS 只存储了 count，而 TOPK 同时存储了元素的 fingerprint 和 count。在添加元素时 CMS 是直接在 count 上累加，而 TOPK 是有条件的。

• 如果桶为空，则直接写入 fingerprint、count=1
• 如果新元素的 fingerprint 与桶中的 fingerprint 相等，则 count++
• 如果 fingerprint 不一致，说明发生了哈希冲突。根据 P = b^−count(b>1, 通常取 1.08) 计算出衰减概率 P，然后生成一个 (0, 1) 的随机数 R。
  • 如果 R <= P，则桶中的 count–，如果此时 count> 0 则 fingerprint 不变，否则将 fingerprint 更新为新元素的 fingerprint，count 设为 1.
  • 如果 R > P，则桶保持不变。

衰减概率 P 是根据 count 计算的，count 越大 P 就越小。频率低的元素很快就衰减到 0，而频率高的元素则不容易衰减。

t-digest

估算数据流的百分位数，比如估算指定百分位的值，估算某个值所处的百分位，估算指定排名的值，估算某个值的排名，计算修剪平均数（去除数据两端特定比例的极端值后计算剩余数据的均值）。

参考

1. Probabilistic | Docs
2. 热点数据检测 HeavyKeeper在高并发的场景中，热点数据一直是我们需要关注的问题。如何去衡量热点数据是关键。这篇文 - 掘金