Redis 概率相关的数据类型HyperLogLogBloom filter 布隆过滤器Cuckoo filter 布谷鸟过滤器Count-min sketchTOPKt-digest参考HyperLogLog估算集合中唯一值的个数不精确的去重计数标准误差为 0.81%最多占用 12 KB 的空间。原理基于伯努利实验抛硬币想要连续 K 次均为反面则需要尝试 N 次实验。N 和 K 的关系为 N 2K。HyperLogLog 将值 hash 为数字记录最低位连续 0 的最大数量作为 K进而估计出唯一值的个数 N。为了避免极端值的影响使用了 214 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、count1如果新元素的 fingerprint 与桶中的 fingerprint 相等则 count如果 fingerprint 不一致说明发生了哈希冲突。根据 P b−count(b1, 通常取 1.08) 计算出衰减概率 P然后生成一个 (0, 1) 的随机数 R。如果 R P则桶中的 count–如果此时 count 0 则 fingerprint 不变否则将 fingerprint 更新为新元素的 fingerprintcount 设为 1.如果 R P则桶保持不变。衰减概率 P 是根据 count 计算的count 越大 P 就越小。频率低的元素很快就衰减到 0而频率高的元素则不容易衰减。t-digest估算数据流的百分位数比如估算指定百分位的值估算某个值所处的百分位估算指定排名的值估算某个值的排名计算修剪平均数去除数据两端特定比例的极端值后计算剩余数据的均值。参考Probabilistic | Docs热点数据检测 HeavyKeeper在高并发的场景中热点数据一直是我们需要关注的问题。如何去衡量热点数据是关键。这篇文 - 掘金