LevelDB 學習筆記1：布隆過濾器

2022 年 4 月 8 日
筆記
LevelDB, 源碼分析

LevelDB 學習筆記1：布隆過濾器

底層是位數組，初始都是 0
插入時，用 k 個哈希函數對插入的數字做哈希，並用位數組長度取余，將對應位置 1
查找時，做同樣的哈希操作，查看這些位的值
- 如果所有位都是 1，說明數字可能存在
- 如果有某個位不是 1，說明數字一定不存在

數學結論

影響布隆過濾器精度的參數有

哈希函數的個數 k
布隆過濾器位數組的容量 m
布隆過濾器插入的數據數量 n

對於給定的 m 和 n，要想最小化錯誤率（假陽性），k 應該取

\[k=\frac{m}{n} \ln 2
\]

要求錯誤率不大於\(\varepsilon\)，k 取最優的情況下，m 應該至少為

\[m \geq – 1.44 \log _{2} \varepsilon * n
\]

布隆過濾器的優缺點

優點

空間效率高，可以在使用有限內存的情況下處理海量數據
- 1% 錯誤率並使用最佳 k 值的布隆過濾器，每個元素只需要使用約 9.6 位
插入和查詢都是常數複雜度，即 O(k)

缺點

存在誤判
刪除元素困難，因為簡單地將對應的位置 0 會影響其他元素的判斷
- 可以用一種叫 Counting Bloom filter 的變體

LevelDB 中的布隆過濾器

LevelDB 中利用布隆過濾器判斷指定的 key 值是否存在於 sstable 中

若過濾器認為 key 不在 sstable 中，那麼就沒必要查找這個 sstable 了
否則，key 有可能在 sstable 中，應該做查找

使用布隆過濾器可以有效的減少調用 DB::Get() 時的訪存次數，從而減小讀放大

LevelDB 中布隆過濾器的實現是 BloomFilterPolicy，它是接口類 FilterPolicy 的實現

FilterPolicy 類決定了查找過程中要不要讀取某個 sstable
允許用戶自定義 FilterPolicy 的子類來應用不同的過濾策略

LevelDB 實現時做了優化，它並不是使用 k 個哈希函數，而是應用 rsa2008 中提出的方法只生成一次哈希值，然後用 double-hashing 的方式生成一組哈希值

uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }

一般實現布隆過濾器時，都會選擇非加密哈希算法

加密哈希算法，比如 MD5、SHA1，安全性較高，難以找到碰撞或通過加密值反推原文
非加密哈希算法，比如 MurMurHash、CRC32、FNV，計算速度快
LevelDB 實現了一個類似於 MurMurHash 的非加密哈希算法

其他應用場景

緩存穿透

做查詢的時候，緩存沒有命中，就會到數據庫中去找，特別地，如果查找一個不存在的 key，那麼是一定無法命中緩存，必須去查數據庫的，如果有人惡意地使用大量請求來查不存在的 key，就會導致數據庫壓力過大，甚至崩潰，這種現象稱為緩存穿透

用布隆過濾器我們可以直接將這些針對不存在的 key 發起的請求過濾掉

Tags: LevelDB 源碼分析