BloomFilter 原理及 Zset 实现原理

布隆过滤器原理

布隆过滤器基于哈希与位图结构。

核心公式：

1. 假设数据量为 n，预期的失误率为 p（布隆过滤器大小和每个样本的大小无关）。
2. 根据 n 和 p，算出 BloomFilter 一共需要多少个 bit 位，向上取整，记为 m。
3. 根据 m 和 n，算出 BloomFilter 需要多少个哈希函数，向上取整，记为 k。
4. 根据修正公式，算出真实的失误率 p_true。

Zset 实现原理

Zset 底层使用 ziplist 和 skiplist。

同时满足以下条件时使用 ziplist 编码：

1. 元素数量小于 128 个。
2. 所有 member 的长度都小于 64 字节。