前文回顧
- LevelDB 完全解析（0）：基本原理和整體架構(gòu)
- LevelDB 完全解析（1）：MemTable
- LevelDB 完全解析（2）：Log
- LevelDB 完全解析（3）：SSTable
- LevelDB 完全解析（4）：Manifest
- LevelDB 完全解析（5）：Cache
Bloom Filter
LevelDB 可以設(shè)置通過(guò) bloom filter 來(lái)減少不必要的讀 I/O 次數(shù)。
1970 年，Burton Howard Bloom 在論文 Space/Time Trade-offs in Hash Coding with Allowable Errors 提出了 bloom filter。
Bloom filter 的實(shí)現(xiàn)一般由一個(gè)或多個(gè) bitmap 和多個(gè)哈希函數(shù)組成，可以用于檢索一個(gè)元素是否在一個(gè)集合中。
- 優(yōu)點(diǎn)是空間效率高、查詢時(shí)間是常數(shù)復(fù)雜度，并且和每個(gè) key 的長(zhǎng)度無(wú)關(guān)。
- 缺點(diǎn)是有一定的誤識(shí)別率（false positive，通常平均每個(gè)元素只需要不到 10 bits 的空間就能把錯(cuò)誤率控制在 1% 左右），同時(shí)不支持刪除操作。
- 關(guān)于刪除操作，也許有人會(huì)想把 bitmap 變成整數(shù)數(shù)組，然后每插入一個(gè)元素就把對(duì)應(yīng)的計(jì)數(shù)器加 1，刪除元素時(shí)將計(jì)數(shù)器減掉就可以了。這樣做有兩個(gè)問(wèn)題：
- 消耗的內(nèi)存大大增加。如果使用 uint8 的整數(shù)數(shù)組，內(nèi)存是原來(lái)的 8 倍，并且最大只能計(jì)數(shù)到 255。而使用 uint16、uint32 會(huì)消耗更多的內(nèi)存。
- 要保證安全地刪除元素，首先我們必須保證刪除的元素的確在 bloom filter 中。這一點(diǎn)單憑這個(gè)過(guò)濾器是無(wú)法保證的。
假設(shè) m 為 bitmap 的長(zhǎng)度，n 是元素的總數(shù)，k 是哈希函數(shù)的個(gè)數(shù)，則平均每個(gè) key 消耗的內(nèi)存 bits_per_key = m / n。
對(duì)于給定的 bits_per_key，要使誤識(shí)別率最低，則 k 的取值為 bits_per_key * ln2。<br />
如果我們希望誤識(shí)別率為 e，則
比如當(dāng) e = 0.01 時(shí)，可以通過(guò)公式簡(jiǎn)單計(jì)算得到 bits_per_key ~= 9.567。也就是說(shuō)，一個(gè) key 消耗不到 10 bits 就能將誤識(shí)別率控制在 1% 左右。
具體的數(shù)學(xué)推導(dǎo)過(guò)程可以參考 bloom filter 的維基百科。
實(shí)現(xiàn)
LevelDB 中的 bloom filter 的實(shí)現(xiàn)是 BloomFilterPolicy，它繼承了 FilterPolicy 抽象類，實(shí)現(xiàn)了兩個(gè)接口：
- CreateFilter - 根據(jù) key 列表創(chuàng)建 filter。
- KeyMayMatch - 判斷一個(gè) key 是否可能存在。如果 key 存在，一定返回 true。如果 key 不存在，可能返回 true 也可能返回 false。
