2024q1 第 6 週測驗題

目的: 檢驗學員對 bitwise operation 和 Entropy 的認知

作答表單: 測驗 1 (針對 Linux 核心「設計」/「實作」課程)

測驗 1

Bloom filter 利用雜湊函數，在不用走訪全部元素的前提，「預測」特定字串是否存於資料結構中。因此時間複雜度是

$O(1)$，而非傳統逐一搜尋的

$O(n)$ 。

建構：

• n 個位元構成的 table
• k 個雜湊函數: h₁ 、 h₂ … h_k
• 每當要加入新字串 s 時，會將 s 透過這 k 個雜湊函數各自轉換為 table index (範圍: 0 到 n - 1) ，所以有 k 個雜湊函數，就該有 k 個 index ，然後將該 table[index] 上的位元 set (即指定為 1)

此後若要檢查該字串 s 是否存在時，只需要再執行前述 k 個雜湊函數，並檢查是否所有的 k 個位元都是 set 即可

動畫: Cube Drone - Bloom Filters

但該做法存在錯誤率，例如原本沒有在資料結構中的字串 s1 經過雜湊函數轉換後得出的位元的位置和另一個存在於資料結構中的字串 s2 經過雜湊函數轉換後的結果相同，如此一來，先前不存在的 s1 便會被認為存在，這就是 false positive (指進行實用測試後，測試結果可能無法反映出真正的面貌或狀況)。

Bloom filter 一類手法的應用很常見。例如在社群網站 Facebook，在搜尋欄鍵入名字時，能夠在 20 億個註冊使用者 (2017 年統計資料) 中很快找到結果，甚至是根據與使用者的關聯度排序。

延伸閱讀:

• Esoteric Data Structures and Where to Find Them
• Bloom Filters

• Bloom Filter 實作方式

首先，建立一個 n 個位元構成的 table，並將每個位元初始化為 0。

我們將所有的字串構成的集合 (set) 表示為 S = { x₁, x₂, x₃, … ,x_n }，Bloom Filter 會使用 k 個不同的雜湊函數，每個雜湊函數轉換後的範圍都是 0 到 n-1 (為了能夠對應上面建立的 n 個位元構成的 table)。而對每個 S 內的 element x_i，都需要經過 k 個雜湊函數，一一轉換成 k 個 index。轉換過後，table 上的這 k 個 index 的值就必須設定為 1。

注意: 可能會有同一個 index 被多次設定為 1 的狀況

Bloom Filter 這樣的機制，存在錯誤率。若今天想要找一個字串 x 在不在 S 中，這樣的資料結構只能保證某個 x₁ 一定不在 S 中，但沒辦法 100% 確定某個 x₂一定在 S 中。因為會有誤判 (false positive) 的可能。

此外，資料只能夠新增，而不能夠刪除，試想今天有二個字串 x₁, x₂ 經過某個雜湊函數 h_i 轉換後的結果 h_i(x₁) = h_i(x₂)，若今天要刪除 x₁ 而把 table 中 set 的 1 改為 0，豈不是連 x₂ 都受到影響？

• Bloom Filter 錯誤率計算

首先假設所有字串集合 S 裡面有 n 個字串，雜湊函數總共有 k 個，Bloom Filter 的 table 總共 m 位元。我們會判斷一個字串存在於 S 內，是看經過轉換後的每個位元都被 set 了，我們就會說可能這個字串在 S 內。但試想若是其實這個字串不在 S 內，但是其他的 a b c 等等字串經過轉換後的 index ，剛好涵蓋目標字串轉換後的 index，就造成了誤判這個字串在 S 內的情況。

如上述，Bloom Filter 存有錯誤機率，程式開發應顧及回報錯誤機率給使用者，以下分析錯誤率。

當我們把 S 內的所有字串，每一個由 k 個雜湊函數轉換成 index 並把 table[index] 設為 1，而全部轉換完畢時，table 中某個位元仍然是 0 的機率是

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

其中

$(1-{\displaystyle \frac{1}{m}})$ 是每次雜湊函數轉換後，table 的某個位元仍然是 0 的機率。因為我們把雜湊函數轉換後到每個 index (而這個 index 會被 set) 的機率視為相等 (每單位是

${\displaystyle \frac{1}{m}}$)，所以用 1 減掉即為不會被 set 的機率。我們總共需要做 kn 次雜湊運算，所以就得到

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

由

$(1-{\displaystyle \frac{1}{m}}{)}^m\approx e^{-1}$ 特性，可知

$$(1-{\displaystyle \frac{1}{m}}{)}^{kn}=((1-{\displaystyle \frac{1}{m}}{)}^m{)}^{\frac{kn}{m}}\approx (e^{-1}{)}^{\frac{kn}{m}}\approx e^{-\frac{kn}{m}}$$
這就是當全部字串轉換完畢時，某個位元還沒有被 set 的機率。

因此誤判的機率等同於全部經由 k 個雜湊轉完後的 k 位元已被其他人 set 的機率:
轉完後某個位元被 set 機率是:

$1-e^{-\frac{kn}{m}}$，因此某 k 位元被 set 機率為:

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

• 如何選 k 值？

• k: 多少個不同雜湊函數
• m: table size 的大小

為確保錯誤率最小，也就是讓

$(1-e^{-\frac{kn}{m}}{)}^k$ 的值是最小。先把原式改寫成

$(e^{kln(1-e^{-\frac{kn}{m}})})$，我們只要使

$k\ln (1-e^{-\frac{kn}{m}})$ 最小，原式就是最小值。可以看出當

$e^{-\frac{kn}{m}}={\displaystyle \frac{1}{2}}$ 時，會達到最小值。因此

$k=ln2{\displaystyle \frac{m}{n}}$ 即能達到最小值。

Bloom Filter calculator 和 Bloom Filter calculator 2 這二個網站可以透過設定自己要的錯誤率與資料的多寡，得到 k 和 m 值。

• Bloom Filter error rate 視覺化

縱軸是雜湊函數的數量、橫軸是 table size，並以錯誤率做為深淺來製圖，畫面中紫色線條為

$y=ln2\cdot \frac{x}{93827}$，其中 93827 為測試用的字典中項目數量。

我們想要最小的空間及執行速度，並符合可預測的錯誤率，於是期望的數值在可行域的左下角。

為了讓圖片不明顯的部分，能被看得清楚，將圖片轉為灰階後做直方圖均衡化

把此圖視為高線圖，可以發現山谷都在

$k=ln2\frac{m}{n}$上，而在這裡實際的意義就是錯誤率最小值發生在

$k=ln2\frac{m}{n}$與推導的結果相符。透過開四次方根把錯誤率之間的差距加大，再製圖，可更明顯看出上述的內容。

bloom.[ch] 是上述 Bloom filter 的實作，並利用 Check 進行測試，預期的執行輸出如下: (假設 malloc 不會遇到任何錯誤)

Running suite(s): Bloom Filter
100%: Checks: 6, Failures: 0, Errors: 0

安裝 Check 套件:

sudo apt-get install check

Bloom filter 程式碼 (部分遮蔽)

編譯和測試:

$ gcc -Wall -O2 -o bloom bloom.c test-bloom.c \
      -lcheck -lsubunit -lm -lpthread -lrt          
$ ./bloom

作答規範:

• 依循第一次作業指定的程式碼風格書寫，並採用最簡短的形式
• AAAA 和 BBBB 是表示式，不得出現 % (modulo) 運算子，變數應當在 integer literal 前出現
• CCCC 和 EEEE 是整數，用最簡短的方式書寫
• DDDD 是表示式
• FFFF, GGGG, HHHH 為表示式 (不得出現 ; 字元)，應包含 popcount，小括號對 (即 ( 和 ) 構成的 pair) 的數量僅為 1，也就是函式呼叫所用
• IIII 和 JJJJ 為表示式

由於 Bloom filter 的限制，後來出現一系列改進的替代選擇，例如 Meta 發展的 Ribbon Filter (用於 RocksDB)、空間使用率更高且支援 delete 操作的 Cuckoo filter、空間使用率較 Cuckoo filter 高的 Xor filter，以及進一步改良的 Binary Fuse Filters。

• 之前學員的筆記: Xor Filter 論文與實作、實作 XOR Filter 並改善

延伸問題:

1. 解釋上述程式碼運作原理 (要從 Entropy 來解讀)，指出可改進之處並著手進行。
2. 在 Linux 核心原始程式碼中找到 Bloom filter 的應用案例 (例如 eBPF) 並探討其運用方式。
3. 雜湊函數的表現對於 Bloom filter 相當重要，請參照 Linux 核心的應用案例，說明其雜湊函數的選擇，並探討更換其他實作以有更好表現的可能。
4. 評估引入 Bloom filter 的替代選擇到 Linux 核心。