False Positive Rate

$m$: 表示BloomFilter bit array的长度;
$k$: 表示hash函数个数;
$n$: 表示插入元素的个数;

假设hash函数以等概率选择bit array的下标，那么经过$k$个hash函数之后，某个bit位未被设置为1的概率为:

$$ (1 - \frac{1}{m})^k $$

在插入$n$个元素之后，某个bit位仍然没有被设置为1的概率为:

$$ (1 - \frac{1}{m})^{kn} $$

因此在插入$n$个元素之后，某个bit位被设置为1的概率为:

$$ p = 1 - (1 - \frac{1}{m})^{kn} $$

对于一个不存在于集合中的元素，...

1. 概览

要谈论 LevelDB 的 Compaction 就不得不从 LevelDB 的整个数据写入流程入手。LevelDB 的基本写入流程大致为：

1. 数据先写入到 WAL 日志中，做持久化
2. 然后数据同步到mutable memtable中
3. 当mutable memtable大小达到Options.write_buffer_size设置的大小时，就会变成immutable memtable，并且创建一个新的mutable memtable
4. 后台的 Compaction 线程会把immutable memtabledump 成 sstable 文件，并设置于 Level 0 层
5. 当 Level i 达到一定条件后，...