Linux 核心專題: Bloom filter 研究

# Linux 核心專題: Bloom filter 研究 > 執行人: bevmmf > ==[解說錄影(一)](https://www.youtube.com/watch?v=X4fBhhK3LLs&ab_channel=Erazer)== > [GitHub](https://github.com/bevmmf/LKBF_test_user) ## Reviewed by `I-Ying-Tsai` 想詢問 Bloom Filter 於並行環境下，如何進行 bit array 的 thread-safe 寫入？ :::success 最簡單的方式就是在 bloom 函式 caller 外用 grain-coarsed lock 保護此臨界區。但此鎖的粒度粗，會有大量鎖競爭。或是在 bloom 函式的實作使用 atomic C11，因為標準 bloom filter 的操作單步可完成且具交換律且冪等性，天生適合使用 lock-free 之atomic operation 處理。但若是支援刪除之 counting bloom filter 以開銷成本來講就不太適合 lock-free 了。更詳細部分下方有講述。 ::: ## TODO: 闡述 bloom filter 的原理 > 以第一手材料為主，研讀相關論文，要有對應的數學分析為何需要多個 hash function? 近似值背後的數學原理 ## TODO: 解讀 Bloom filter 在 Linux 核心的應用 > 分析原始程式碼，並嘗試抽取和改寫出可單獨測試的使用者空間 (或核心模組)，設計相關實驗 ## TODO: 針對並行環境開發的 bloom filter 變體 > 研讀 2024 年「[並行程式設計](https://hackmd.io/@sysprog/Skyd45U8A)」報告 (含講解錄影和提問) 的第 10 週測驗題，以此為基礎，開發並行版本的 bloom filter，量化其效能表現，並提出改進方案 ## 簡述探討 bloom filter 的原理、在 Linux 核心的應用，以及擴充為適合用於並行環境。 Bloom Filter 是一種允許可控制錯誤率的機率性資料結構。儘管它在 1970 年即由 Burton Howard Bloom 提出，今日於大數據與作業系統核心仍扮演重要角色，例如 Linux 自 5.16 版本起便在 eBPF 引入 Bloom Filter map，加速高頻率存在性查詢之應用場景。本報告將從原始問題出發，說明 Bloom Filter 的設計動機、數學模型，並深入 Linux 核心實作，最終透過實驗量化其效能與誤判率。並進一步設計、實作與量化適用於多執行緒／多核心並行環境的 Bloom Filter 變體 ## bloom filter 原理與學理分析 ### 1.背景 &emsp;&emsp;Bloom filter(1970) 所要解決的問題是 50 萬字詞字典的自動斷字 (hyphenation)。在排版系統中，90 % 的單字可由簡單規則判定斷字位置，餘下 10 % 需查表處理。若能先用一個快取結構快速判斷「此單字是否屬於特殊表」，便可節省大量 I/O 與字典查詢時間。Bloom Filter 正是為了滿足「記憶體極度有限、誤判成本低、查詢需 O(1) 時間」這類場景而誕生。而該 paper 在 1970 年就被發表。 > Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7), 422-426. ### 2.原理 &emsp;&emsp;Bloom Filter 是一種用來測試某元素是否存在於集合中的機率性資料結構。它由以下兩個主要部分構成： 1. Bit Array：大小為 m ，所有 bit 初始設為 0。 2. Hash Functions：共有 k 個獨立 hash functions，每個 hash function 將輸入映射至 bit array 的一個索引位置。以下為 bloom filter 完整結構圖 ```graphviz digraph BloomFilter { rankdir=LR; node [shape=box, style=filled, fillcolor=lightblue]; edge [color=navy]; // Input elements subgraph cluster_input { label="Input Elements (n)"; color=lightgrey; style=filled; element1 [label="Element 1"]; element2 [label="Element 2"]; element3 [label="Element ..."]; elementn [label="Element n"]; {rank=same;element2 -> element1 -> elementn -> element3 [style=invis, constraint=true];} } // Hash functions subgraph cluster_hash { label="Hash Functions (k)"; color=lightgrey; style=filled; hash1 [label="Hash 1", shape=oval, fillcolor=green]; hash2 [label="Hash 2", shape=oval, fillcolor=green]; hash3 [label="Hash ...", shape=oval, fillcolor=green]; hashk [label="Hash k", shape=oval, fillcolor=green]; {rank=same; hash1 -> hash2 -> hash3 -> hashk [style=invis]} } // Bit array subgraph cluster_bitarray { label="Bit Array (m bits)"; color=lightgrey; style=filled; bitarray [label="0 0 1 0 1 ... 0", shape=rectangle, width=4, fillcolor=lightyellow]; } // Edges from elements to hash functions element1 -> hash1; element1 -> hash2; element1 -> hash3; element1 -> hashk; element2 -> hash1; element2 -> hash2; element2 -> hash3; element2 -> hashk; element3 -> hash1; element3 -> hash2; element3 -> hash3; element3 -> hashk; elementn -> hash1; elementn -> hash2; elementn -> hash3; elementn -> hashk; // Edges from hash functions to bit array hash1 -> bitarray [label="Set bit"]; hash2 -> bitarray [label="Set bit"]; hash3 -> bitarray [label="Set bit"]; hashk -> bitarray [label="Set bit"]; // Parameters table with adjusted padding and width params [shape=none, label=< <table border="0" cellborder="1" cellspacing="0" cellpadding="8"> <tr><td>Parameters</td></tr> <tr><td width="200">m: Bit array length</td></tr> <tr><td width="200">n: Number of elements</td></tr> <tr><td width="200">k: Number of hash functions</td></tr> </table> >]; } ``` 而為了實現高效率查詢，bloom filter 有兩個 operations 作為運作方式。 1. Insert：將欲插入的元素透過 k 個 hash function 分別映射出 k 個位元位置，並將這些位置的位元設為 1。 2. Query：查詢一個元素是否存在時，同樣使用 k 個雜湊函式計算位元索引位置，檢查這些位置的位元是否皆為 1： - 若至少有一個位元為 0，則該元素一定不在集合中。 - 若全部皆為 1，則該元素可能存在於集合中，但存在誤判的可能性（False Positive），此也為 bloom filter 最大之議題。 #### Bloom Filter 與 Hash Table 比較 &emsp;&emsp;Bloom Filter 與 Hash Table 都是常見的查詢用資料結構，將兩者進行比較有助於理解 Bloom Filter 的設計取捨與適用場景。它並非取代 Hash Table，而是補足其在「空間效率」與「可接受錯誤率」情況下的不足。因此，在實務應用中，兩者往往搭配使用，例如：Bloom Filter 先篩選可能存在的元素，減少 Hash Table 的查詢次數與記憶體壓力。下表整理兩者在功能、效能與空間使用上的差異： | | Bloom Filter | Hash Table | |-------------|-------------------------------|----------------------| | 功能 | 僅支持存在性查詢 無法存取具體資料 標準實作不支持刪除 | 支持鍵值對存取資料 支持插入、刪除、更新 | | 時間複雜度 | insert 和 query：皆為常數時間 O(k)（k 為hash function 數） | 平均：O(1) 最壞：O(n)（大量hash collision） | | 空間複雜度 | O(m) (m 為 bit array 大小) 每元素約需幾 $\frac{m}{n}$ bit | O(n)，( n 為元素數量 ) 每元素需數十 bytes 的string(key) | | 誤報與精確性 | 存在 false positive (隨元素數量n增加而上升) | 查詢結果精確，無誤報由上表可知，Bloom Filter 在「純粹判斷是否存在」這件事上，查詢速度和記憶體使用量都通常遠優於一般的 Hash Table，只是它會帶來 False Positive 的風險。 ### 3.FPR 建模 FPR 對 Bloom filter 有著巨大的影響。以工程角度，我們追求最小誤差與風險，因此我們嘗試建模並使之規格有定性甚至最佳化。以下是建模流程(符號部分以上述 bloom filter 完整結構圖為準) : 1. 先考慮單次加入元素 : 先假設 hash function 設計足夠好，mapping 夠平均，則每個 hash function 使 bit array 中某個 bit 被翻成 1 的機率是 $\frac{1}{m}$ ，最後可得 - 某個 bit 沒被翻的機率是$$(1-\frac{1}{m})^k$$ - 某個 bit 被翻成1的機率是$$1-(1-\frac{1}{m})^k$$ 2. 再考慮加入 n 個元素後 - 某個 bit 沒被翻的機率是$$(1-\frac{1}{m})^{kn}$$ - 某個 bit 被翻成1的機率是$$1-(1-\frac{1}{m})^{kn}$$ 最後 false positive 發生的機率就是加入的一新 $y$ ，查詢 $y$ 時產生誤報， k 個 hash function 映射到 bit array 的機率。加入一假設為關於 k 個 hash function 映射後的 bit array 為獨立不重疊，結果即為某 k 個 bit 已被翻成 1 的機率 : $$P_{fp} \approx [1-(1-\frac{1}{m})^{kn}]^k$$ 又可數學近似為以下 $$P_{fp}\approx[1-e^{-\frac{kn}{m}}]^k$$ #### 近似值背後之數學原理 &emsp;&emsp;此數學近似原理稱為指數的極限近似(limit definition of exponential/the exponential approximation)。此近似也應用於機率論裡，二項分佈到 Poisson 分佈的極限定理（Poisson limit theorem）。 $$\lim_{n \to \infty} \left(1 - \frac{\lambda}{n}\right)^n = e^{-\lambda}$$ 首先，進行此數學近似的原因有四。 1. **數值計算穩定性** 當 `m` 很大時，直接計算 $(1-\frac{1}{m})^{kn}$ 可能會遇到 float underflow(下溢) 或 float round-off error (捨入誤差)。而指數函數 $e^{-\frac{kn}{m}}$ 在電腦上通常有更穩定且優化的實作。 2. **使數學推導容易** 若用原始二項式形式，推導過程會非常繁瑣且不易化簡。因此近似成指數可以方便對表達式做微分等取極值之操作。 3. **與 Poisson distribution model 對應** 當我們將 `n` 個元素各 hash `k` 次，總共會有 `kn` 次「hash 到某 bit」的事件。假設 bit array 長度為 `m`，那麼某個特定位元被命中的機率為 1/m，每次機率很小，但事件很多，這種情況在機率論中可以近似為 Poisson 分佈： $$ 某個 bit 被設為 1 的次數 ≈ Poisson(λ)， λ = \frac{kn}{m} $$ 而在 Poisson 分佈中，事件「這個 bit 從未被設定為 1」的機率為： $$P(X = 0) = e^{-λ} = e^{-kn/m}$$ 這個剛好就是我們近似的結果。 4. **指數近似已足夠精準** 實際系統設計時，通常只需知道「FPR的大致行為」與「如何依需求調整 `m`、`n`、`k`。指數近似已足夠精準以下是指數極限近似之推導 : ##### 從極限定義出發以下式為例 $$L = \lim_{n \to \infty} \left(1 + \frac{x}{n} \right)^n$$ 取自然對數（$ln$）： $$ \ln L = \lim_{n \to \infty} \ln\left( \left(1 + \frac{x}{n} \right)^n \right) = \lim_{n \to \infty} n \cdot \ln\left(1 + \frac{x}{n} \right) $$ ##### 自然對數的泰勒展開自然對數的泰勒展開式為 : $$ \ln(1+y)=y-\frac{y^{2}}{2}+\frac{y^{3}}{3}-\frac{y^{4}}{4}+\cdots $$ 當 y 值極小時能近似成 : $$ \ln(1 + y) = y - \frac{y^2}{2} + O(y^3) $$ 在這裡令 $y = \frac{x}{n}$，當 $n \to \infty$ 時，$y \to 0$，因此可以展開為： $$ \ln\left(1 + \frac{x}{n}\right) = \frac{x}{n} - \frac{1}{2} \cdot \frac{x^2}{n^2} + O\left(\frac{1}{n^3}\right) $$ ##### 帶入並取極限將展開式帶入之前的公式中： $$ n \cdot \ln\left(1 + \frac{x}{n}\right) = n \left( \frac{x}{n} - \frac{x^2}{2n^2} + O\left(\frac{1}{n^3}\right) \right) = x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) $$ 當 $n \to \infty$ 時，$-\frac{x^2}{2n}$ 和更高階的項趨近於 0，因此： $$ \ln L = \lim_{n \to \infty} \left( x - \frac{x^2}{2n} + \cdots \right) = x $$ 最後下取指數得證 $$ L= \lim_{n \to \infty} \left(1 + \frac{x}{n}\right)^n = e^x $$ ### 4.為何需要多個 hash function 為解答此問題，可從第三部分之 FPR 建模固定其餘變量做定性觀察。 - `m`為變量，固定其他 ![image](https://hackmd.io/_uploads/B1PDKu2kxl.png) `m` 增加 => $-\frac{kn}{m}$ 變大 => $P_{fp}$ 變小因此`m` 越大越好 - `n`為變量，固定其他 ![image](https://hackmd.io/_uploads/SJQYYOhyll.png) `n` 增加 => $-\frac{kn}{m}$ 變小 => $P_{fp}$ 變大因此 `n` 越小越好 - `k`為變量，固定其他 ![image](https://hackmd.io/_uploads/rJjMwt_1lg.png) `k` 增加 => $e^{-\frac{kn}{m}}$變小 => $[1-e^{-\frac{kn}{m}}]$變大，但開次方數也變大。因此由此實驗可知 `k` 有一個最佳值（$P_{fp}$ 最小點），過大或過小都不好。 ### 5. 實務設計 Bloom filter 配置 #### 最佳 k 值配置 > **最佳雜湊函式數** > \\[ > \boxed{\,k^* \;=\; \dfrac{m}{n}\,\ln 2\,} > \\] 以下是數學推導 : 目標為對給定的位元陣列大小 \$m\$ 與元素數 \$n\$，求使偽陽性機率 \\[ P_{\text{fp}}(k) \;=\; \bigl(1-e^{-kn/m}\bigr)^{k} \\] 步驟 1：取對數化簡因為 \$\ln(x)\$ 在 \$x>0\$ 上嚴格遞增，最小化 \$P_{\text{fp}}\$ 等同最小化其對數 \\[ \ln P_{\text{fp}}(k) \;=\; k\,\ln\!\bigl(1-e^{-kn/m}\bigr) \;=\; L(k). \\] --- 步驟 2：設置輔助變數令 \\[ x \;=\; e^{-kn/m}, \qquad\Longrightarrow\qquad k \;=\; \frac{m}{n}\,\ln\!\frac1x. \\] --- 步驟 3：對 \$L(k)\$ 取導並令其為 0 \\[ \begin{aligned} \frac{dL}{dk} &= \ln(1-x) \;+\; k\,\frac{x}{1-x}\,\Bigl(\!-\frac{n}{m}\Bigr) \\[4pt] &= \ln(1-x) - \frac{x\ln x}{1-x}. \end{aligned} \\] 令 \$ \tfrac{dL}{dk}=0 \$： \\[ (1-x)\,\ln(1-x) = -x\,\ln x. \\] 此等式在 \$0<x<1\$ 僅有唯一解 **\$x=\tfrac12\$**。 --- 步驟 4：回代求 \$k\$ \\[ e^{-kn/m} = \tfrac12 \;\;\Longrightarrow\;\; k \;=\; \frac{m}{n}\,\ln 2. \\] --- 在 \$k=k^{*}\$ 時，\$\ln P_{\text{fp}}\$ 取得全域最小值，因此偽陽性機率亦達到最小。 #### bloom filter 會有幾種常見設計方式 : 1. 若記憶體固定以 m,n 求出最佳 k，再反推 ε 是否符合需求。 2. 先估 n 與可接受 ε 用表中第 2 行算出 m，再帶入算 k。 3. 動態集合以飽和公式預留安全係數，或採用 Scalable/Counting Bloom Filter 變體 | 固定 | 設定 | 輸出 | 公式 | | ----- | -------------- | ------------------- | --------------------------------------------------------------------------------------------------------------- | | $m,n$ | 已知可用記憶體、要存的元素數 | **最佳 k** | $k = \frac{m}{n}\ln 2$ (ref 2) | | $n,ε$ | 元素數與容忍FPR | **所需 m** | $m = -\frac{n\ln\varepsilon}{(\ln 2)^2}$ (ref 2) | | $ε$ | 目標FPR | **所需 k** (搭配最佳 m/n) | $k = -\frac{\ln\varepsilon}{\ln 2}$ (ref 2) | | $m,k$ | 預算好的位元與hash fucntion nr | **可容納 n** (飽和前上限) | $n_{\max}\!\approx\!-\frac{m}{k}\ln\!\bigl(1-\alpha\bigr)$（$\alpha$ 為允許的 1 位比例，如 0.95） | #### 輔助設計網站 [Bloom Filter calculator](https://hur.st/bloomfilter/?n=5000&p=3&m=&k=45) 和 [Bloom Filter calculator](https://krisives.github.io/bloom-calculator/) 2 這二個網站可以透過設定自己要的錯誤率與資料的多寡，得到 k 和 m 值。 ## 在 Linux 核心之 Bloom filter ### struct ```c struct bpf_bloom_filter { struct bpf_map map; // u32 bitset_mask; u32 hash_seed; // u32 nr_hash_funcs; // number of hash funciton unsigned long bitset[];// }; ``` 1. `hash_seed` : 用於驅動 hash functions 亂度之值 2. `nr_hash_funcs` : 即 number of hash functions k 3. `bitset[]` : 即 bloom filter 之核心 bit array 1. `bpf_map` 結構之 map : 根據此 bloom filter 結構前綴有 bpf 表示此資料結構為針對 bpf 設計的一個 bloom filter ，因此內嵌一個 `bpf_map` 結構。但 bloom filter 是一通用工具，所以其他地方需要高效檢索時也能使用此 `bpf_bloom filter` 。 2. `bitset_mask` : 用於使經過 hash function 映射的過大 `h` 值限制在 bit array 大小範圍內。透過 `h & bitset_mask` 做類似取餘數動作(`h % nr_bits`)，取得一不超過 bit array 大小(`nr_bits`)的值作為 bit index 。 ### 配置設計 ```c nr_hash_funcs = attr->map_extra; if (nr_hash_funcs == 0) nr_hash_funcs = 5; ``` 由 `bpf_map_create()` 時可設定此 bloom filter 之 `n` 與 `k`。`n` 由 `attr->max_entries` 設置。而 `k` 為 `nr_hash_funcs` ，由 `attr->map_extra` 之 low 4 bit 儲存。且值為 0 時 `nr_hash_funcs` 設為預設值 5 。 ```c if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) || check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) || nr_bits > (1UL << 31)) { bitset_bytes = BITS_TO_BYTES(U32_MAX); bitset_mask = U32_MAX; } else { if (nr_bits <= BITS_PER_LONG) nr_bits = BITS_PER_LONG; // at least 64 bits else nr_bits = roundup_pow_of_two(nr_bits); bitset_bytes = BITS_TO_BYTES(nr_bits); bitset_mask = nr_bits - 1; } ``` 當決定 `max_entries` 與 `nr_hash_funcs` 即可由 ref [2] paper 之最優最優位元數公式求得 `m` 。 $$ m = n * k / ln(2)$$ 這裡使用 7 / 5 近似 1 / ln(2)，因此計算公式為：`nr_bits` = (n * k * 7) / 5。 - overflow 處理使用 check_mul_overflow 檢查乘法是否溢出 u32。若以下任一條件成立： a. n * k 溢出， b. (n * k / 5) * 7 溢出， c. nr_bits > 2^31，則設置： `bitset_bytes = BITS_TO_BYTES(U32_MAX)`：bit array 大小設為 2^32 位元（即 4GB），轉換為位元組數。且 `bitset_mask = U32_MAX`：位掩碼設為最大值。 - 正常情況處理(若無溢出) - 最小值調整：若 nr_bits <= BITS_PER_LONG（通常為 64），則將 nr_bits 設為 BITS_PER_LONG，確保位陣列有最小規模。 - 向上取整：否則將 nr_bits 向上取整到最接近的 2 的冪次方（使用 roundup_pow_of_two），這是為了使用位掩碼進行高效 hash 計算。 - 最終計算： bitset_bytes = BITS_TO_BYTES(nr_bits)：將位元數轉換為位元組數（通常 8 位元 = 1 位元組）。 bitset_mask = nr_bits - 1：位掩碼用於快速取模運算（例如，若 nr_bits = 8，則 bitset_mask = 7，即 0b111）。 ### hash function ```c static u32 hash(struct bpf_bloom_filter *bloom, void *value, u32 value_size, u32 index) { u32 h; if (likely(value_size % 4 == 0)) h = jhash2(value, value_size / 4, bloom->hash_seed + index); else h = jhash(value, value_size, bloom->hash_seed + index); return h & bloom->bitset_mask; } ``` 此 kernel bpf bloom filter 根據每筆資料大小使用不同的 hash function。若每個 element 資料大小為 4 bytes 的倍數，即使用專為處理之更高效的 jhash2。若非則使用 jhash。而 index 的設計讓使用者只要將 index + 1 即可使用不同的 hash function，方便使用多個 hash function 之場合。最後使用 bit array mask 與 hash value h 取按位元與，輸出之值為該資料經過一 hash function 之後映射到 bit array 之位置 index。 #### 為何使用 jhash ? 核心之 hash 除了 `jhash` 外還有一些如 `hash_long`、`hash_ptr`（位於 include/linux/hash.h），用於簡單的數值或指標雜湊。或是 `siphash`（位於 include/linux/siphash.h）用於更高安全性的場景。或是在 crypto/ dir 的 `SHA-1`、`MD5` ，有複雜的計算，主要適用於驗證。 - 高效能與低開銷相較於加密雜湊（如 SHA），jhash 非加密用途，減少計算負擔。適合核心環境的高效能需求，尤其在網路封包處理等即時場景。 ```c if (likely(value_size % 4 == 0)) h = jhash2(value, value_size / 4, bloom->hash_seed + index); else h = jhash(value, value_size, bloom->hash_seed + index); ``` 使用 jhash2（針對 4 字節對齊資料）或 jhash（通用情況），優化不同資料大小的處理。 - 多雜湊支援 jhash 透過種子偏移（bloom->hash_seed + index）生成多個獨立雜湊值 ```c for (i = 0; i < bloom->nr_hash_funcs; i++) { h = hash(bloom, value, map->value_size, i); set_bit(h, bloom->bitset); } ``` - 良好分佈是 Bob Jenkins 提出的 Jenkins 雜湊演算法的變體，專為快速、均勻分佈設計。該演算法透過多輪位元操作（移位、加法、異或）混合輸入資料，破壞輸入模式的規律性，確保輸出均勻。機制由以下概念實現 ```c #define __jhash_mix(a, b, c) \ // include/linux/jhash.h { \ a -= c; a ^= rol32(c, 4); c += b; \ b -= a; b ^= rol32(a, 6); a += c; \ c -= b; c ^= rol32(b, 8); b += a; \ a -= c; a ^= rol32(c, 16); c += b; \ b -= a; b ^= rol32(a, 19); a += c; \ c -= b; c ^= rol32(b, 4); b += a; \ } ``` jhash 和 jhash2 使用三個狀態變數（a, b, c）進行迭代混合，每次處理輸入資料的一部分。多次位元旋轉（rol32）與異或（^）操作打亂輸入資料的位元模式，確保小輸入差異產生大輸出差異（雪崩效應）。每輪混合將 a, b, c 相互影響，放大輸入的微小變化，減少輸出集中於特定值的可能性。統整與其他核心 hash 比較，為何 jhash 最適合做為 bloom filter 之 hash structure | 雜湊函數 | 均勻分佈 | 靈活性 | 安全性 | 多雜湊優化 | 效能 | 適用性 | |------------|----------|------------------|----------------|------------------|------|----------| | jhash | 高 | 高（任意資料） | 中（隨機種子） | 高（種子偏移） | 高 | 最適合 | | hash_long | 低 | 低（僅數值） | 低（無種子） | 無 | 高 | 不適合 | | hash_ptr | 低 | 低（僅指標） | 低（無種子） | 無 | 高 | 不適合 | | siphash | 高 | 高（任意資料） | 高（隨機種子） | 中（種子偏移） | 中 | 次優 | | SHA-1/MD5 | 高 | 高（任意資料） | 高（抗碰撞） | 低（高開銷） | 低 | 不適合 | jhash 在均勻分佈、靈活性與安全性、多雜湊需求間取得最佳平衡，效能高且核心原生，適合 Bloom Filter 的即時場景。由 `commit b37a1b90d915` 可知。 ## Linux 核心的 BPF Bloom filter 實驗 ### 核心內 bloom filter selftest benchmark ### 討論實際狀況不同 k 時之 FPR 以下實驗將 libbpf userspace helper 作為實驗環境搭建。雖然比起寫 ebpf 程式能直接在核心層級生成 `bpf_map` 來說會多了 system call 與 copy 的開銷。對於離線統計來說並無影響。 [github](https://github.com/bevmmf/LKBF_test_user) | k | Run 1 | Run 2 | Run 3 | Run 4 | Run 5 | Run 6 | Run 7 | Run 8 | Run 9 | Run10 | Average | |---|------:|------:|------:|------:|------:|------:|------:|------:|------:|-------:|-------:| | 1 | 60.261 | 60.145 | 60.279 | 59.870 | 60.245 | 59.927 | 59.879 | 60.326 | 59.898 | 60.079 | 60.091 | | 2 | 35.817 | 35.839 | 36.157 | 35.868 | 35.688 | 35.514 | 36.277 | 35.872 | 35.728 | 35.775 | 35.853 | | 3 | 12.527 | 12.105 | 12.041 | 12.244 | 12.302 | 12.060 | 12.232 | 12.210 | 12.161 | 12.331 | 12.221 | | 4 | 13.044 | 12.989 | 12.709 | 12.910 | 12.980 | 12.805 | 12.899 | 13.304 | 12.819 | 13.093 | 12.955 | | 5 | 1.653 | 1.586 | 1.525 | 1.595 | 1.652 | 1.614 | 1.563 | 1.636 | 1.502 | 1.560 | 1.586 | | 6 | 1.445 | 1.458 | 1.525 | 1.578 | 1.506 | 1.557 | 1.575 | 1.482 | 1.485 | 1.506 | 1.512 | | 7 | 1.508 | 1.590 | 1.573 | 1.521 | 1.635 | 1.545 | 1.522 | 1.531 | 1.510 | 1.513 | 1.548 | | 8 | 1.575 | 1.731 | 1.644 | 1.587 | 1.644 | 1.693 | 1.694 | 1.644 | 1.770 | 1.613 | 1.660 | | 9 | 1.844 | 1.803 | 1.871 | 1.842 | 1.913 | 1.871 | 1.960 | 1.894 | 1.862 | 1.903 | 1.876 | | 10 | 0.023 | 0.030 | 0.026 | 0.025 | 0.034 | 0.025 | 0.031 | 0.027 | 0.016 | 0.029 | 0.029 | | 11 | 0.021 | 0.025 | 0.031 | 0.026 | 0.025 | 0.021 | 0.015 | 0.020 | 0.029 | 0.023 | 0.024 | | 12 | 0.020 | 0.022 | 0.028 | 0.017 | 0.031 | 0.019 | 0.023 | 0.033 | 0.023 | 0.020 | 0.024 | | 13 | 0.022 | 0.028 | 0.022 | 0.021 | 0.028 | 0.018 | 0.026 | 0.026 | 0.024 | 0.014 | 0.023 | | 14 | 0.017 | 0.019 | 0.027 | 0.019 | 0.026 | 0.025 | 0.026 | 0.028 | 0.021 | 0.034 | 0.024 | | 15 | 0.023 | 0.020 | 0.033 | 0.022 | 0.027 | 0.025 | 0.025 | 0.027 | 0.025 | 0.024 | 0.025 | 以上是對不同 k 時所作的實驗數據，並根據中央極限定理取十次平均使數據盡可能呈現常態分佈。而此實驗以過載插入為背景，使 FPR 值放大以便觀察定性。由於 `bpf_bloom_filter` 之實作設計，能精確設定的只有 k 與 n ，m 會隨前面兩者做變動。首先，能看到在 k = 5 時 FPR 相較前面有大幅度的下降，由此能看出為何當初開發者會以 5 作為預設雜湊函數數量。且下一次 FPR 大幅降低為 k = 10 時。 :::danger 務必依循課程教材規範的術語，見: https://hackmd.io/@sysprog/it-vocabulary ::: :::success 收到，已修正 ::: 第二，隨 k 增大，FPR 為愈來愈低。先前 FPR 建模在 k = 10 以上時 FPR 應開始轉而上升，與此看似相不符合。但這是因為 `bpf_bloom_filter` 的實作設計為 bit array size m 會與 k 呈比例，又 m 越大使 FPR 下降，因此實驗結果才會呈現此情況。 ## 針對並行環境開發的 bloom filter 對於 2024 第十周之測驗題並行之 bloom filter 實作為以下 : [Commit 46a0c48](https://github.com/bevmmf/concurrent_bloom_filter/commit/46a0c4882c5d0f50e970cf3cbbd89556a83d5915) 而此實作的 concurrency model 是 Multi-Process（fork + 管線把計數結果送回)。這樣的問題是每個 process 擁有私有 Bloom Filter，且彼此之間互相隔離。這樣就沒有 thread-safe 的議題需要去探討，沒有同步的問題，但這樣會有的問題是每個 process 各自擁有 256MB 之 Bloom filter 產生，因為 Copy-on-Write (COW) 導致每個 child process 都有此 bloom filter 之副本而大大增加記憶體之開銷。首先先改進 bloom.c 實作 ```diff +#define BLOOM_BYTEIDX(bit) ((bit) >> 3) +#define BLOOM_BITMASK(bit) (1u << ((bit) & 7u)) struct bloom_s { - volatile char data[BLOOMFILTER_SIZE_BYTE]; + size_t nbits; /* bit 總數，可彈性調整 */ + _Atomic unsigned char *data; /* 動態配置的位元陣列 */ }; -static inline int get(bloom_t *filter, size_t key) { - uint64_t idx = key / sizeof(char); - uint8_t bit = 1u << (key % sizeof(char)); - return (filter->data[idx] & bit) != 0; -} -static inline int set(bloom_t *filter, size_t key) { - uint64_t idx = key / sizeof(char); - uint64_t bit = 1u << (key % sizeof(char)); - return (atomic_fetch_or(&filter->data[idx], bit) & bit) == 0; -} +static inline int bloom_get(const bloom_t *bf, uint32_t bit) { + unsigned char byte = atomic_load_explicit(&bf->data[BLOOM_BYTEIDX(bit)],memory_order_relaxed); + return (byte & BLOOM_BITMASK(bit)) != 0; +} +static inline void bloom_set(bloom_t *bf, uint32_t bit) { + atomic_fetch_or_explicit(&bf->data[BLOOM_BYTEIDX(bit)], BLOOM_BITMASK(bit), memory_order_relaxed); +} -bloom_t *bloom_new(bloom_allocator allocator) { - bloom_t *filter = allocator(sizeof(bloom_t)); - memset(filter, 0, sizeof(bloom_t)); - return filter; -} +bloom_t *bloom_new(bloom_allocator alloc) { + if (!alloc) alloc = malloc; + bloom_t *bf = alloc(sizeof *bf); + if (!bf) return NULL; + bf->nbits = BLOOMFILTER_BITS; + size_t nbytes = bf->nbits / 8; + bf->data = (_Atomic unsigned char *)calloc(nbytes, 1); + if (!bf->data) { free(bf); return NULL; } + return bf; +} -void bloom_destroy(bloom_t **filter, bloom_deallocator dealloc) { - dealloc(*filter, sizeof(bloom_t)); - *filter = NULL; -} +void bloom_destroy(bloom_t **pbf, bloom_deallocator dealloc) { + if (!pbf || !*pbf) return; + if (!dealloc) dealloc = (bloom_deallocator)free; + dealloc((void*)(*pbf)->data, 0); + dealloc(*pbf, 0); + *pbf = NULL; +} ``` 以上部份將原本固定 16 MiB 內嵌陣列實作改成可調大小、動態配置之 bloom filter。結構體多了一個 size_t nbits，讓使用者隨建構決定實際位元數。此外，將原本讀取只用 volatile 處理位陣列數據修改成用 `atomic_load_explicit` ，保證所有執行緒看到一致狀態，不會出現寫完馬上讀卻看不到的風險。再來是對原本沒有 shared memory 之並行程式更改成 shared memory 且用 coarsed-grain mutex 處理同步問題 : [commit da102ee](https://github.com/bevmmf/concurrent_bloom_filter/commit/da102ee1ef10678cbacf07c567a3e4375c6b7e0e) 之後使用 thread sanitizer 測試過為正確，無 data race 。但 throughput 上與前者 multi-process 版本相比落差大。而此項原因可能為鎖粒度過大，將來能以以下為改進方向: 1. 用讀寫鎖 (rwlock) 取代大鎖 coarse-grained mutex 目前所有操作，包含查詢（lookup）和插入（add）都共用同一把互斥鎖，造成 85 % 的查詢也要排隊。因為讀操作不互斥，查詢只要拿「讀鎖（rdlock）」，多個讀者可以同時進；插入時才拿「寫鎖（wrlock）」，確保獨佔寫入，理論上查詢就能同步並行。 2. Striping 細粒度鎖即使是讀寫鎖，寫入仍要獨占；而且整張 bit-array 都在同一把鎖下，還是有競爭。若是將 bit array 切成多段，並將每段都配一把鎖，就能讓每個 thread 間在不同區段間同步進行。執行緒就能在操作不同區段時同時進行，彼此不必等待，大幅降低鎖競爭，提高效能。 3. 自旋鎖(spin-lock) 即便把 mutex 換成 rwlock，對於超短的關鍵區（只改幾個 bit）來說，每次呼叫 `pthread_mutex_lock` 還是要切到核心態、做系統呼叫，這個開銷有時候比鎖本身還大。所以我們可以改用自旋鎖，直接在使用者態忙等拿鎖，完全跳過上下文切換；如果發現自旋等太久，就主動讓出 CPU。這樣對於極短的臨界區，拿鎖跟解鎖都能瞬間完成。 ## reference & note [1] [Bloom, B. H., “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.](https://crystal.uta.edu/~mcguigan/cse6350/papers/Bloom.pdf) [2] [Andrei Broder & Michael Mitzenmacher, “Network Applications of Bloom Filters: A Survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509, 2002.](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf) - [Linux 核心設計: eBPF](https://hackmd.io/@RinHizakura/S1DGq8ebw) - [commit b37a1b90d915（“bpf: Add bloom filter map implementation”，2021）](https://lore.kernel.org/bpf/517a137d-66aa-8aa8-a064-fad8ae0c7fa8@fb.com/) - [SipHash - a short input PRF](https://www.kernel.org/doc/html/v5.5/security/siphash.html) - [kernel/bpf/bloom_filter.c](https://elixir.bootlin.com/linux/v6.12.28/source/kernel/bpf/bloom_filter.c) - [Documentation/bpf/map_bloom_filter.rst](https://elixir.bootlin.com/linux/v6.12.28/source/Documentation/bpf/map_bloom_filter.rst) - [Documentation/bpf/maps.rst](https://elixir.bootlin.com/linux/v6.12.28/source/Documentation/bpf/maps.rst) [研讀筆記](https://hackmd.io/dr5sJrI3QFSROnV-t3KNQA)