# 2019q3 第 5 週測驗題
:::danger
注意須知:
1. 答題時請先建立一份 HackMD 共筆，並設定其存取權限為「任何人都可讀取、已登入系統者可編輯」，隨後將 HackMD 網址張貼於表單中。每題都是[申論題](https://zh.wikipedia.org/zh-tw/%E7%94%B3%E8%AB%96%E9%A1%8C)，答題時請==善用 LaTeX 語法==;
2. 可翻閱書籍、可使用網頁搜尋引擎，亦可使用編譯器和除錯器來實驗，但在測驗期間 (`15:00`-`23:50` Oct 10)，禁止任何形式的討論;
3. 以合法 C 語言 (C99 以上的規格) 撰寫程式碼，需列出完整程式碼;
4. 題目較之前測驗更長，請務必耐心閱讀
5. 為了避免學員大量從給定素材中直接複製貼上原文，作答時==請儘量用漢語書寫== (當然，程式碼、數學表達式、關鍵字和科技詞彙不在此限);
6. 測驗題共 6 題，每題 20 分
:::
---
## 測驗 `1`
本題引導學員實作 [Quotient Filters](https://en.wikipedia.org/wiki/Quotient_filter)，在這之前需要先對 [Bloom Filter](https://en.wikipedia.org/wiki/Bloom_filter) 有概念。
- [ ] 何謂 Bloom Filter
當我們要在大量的資料中搜尋一個字串時，最簡單的方式就是走訪每個資料存放單位，對應的時間複雜度是 $O(n)$。
Bloom filter 利用 hash function，在不用走訪全部元素的前提，**預測**特定字串是否存於資料結構中。因此時間複雜度是 $O(1)$，而非傳統逐一尋訪的 $O(n)$ 。
* n-bits 的 table
* k 個 hash fucntion: h~1~ 、 h~1~ ... h~k~
* 每當要加入新字串 s 時，會將 s 透過這 k 個 hash function 各自轉換為 table index (範圍: `0` 到 `n - 1`) ，所以有 k 個 hash function ，就該有 k 個 index ，然後將該 `table[index]` 上的 bit set
* 下次若要檢查該字串 s 是否存在時，只需要再跑一次那 k 個 hash function ，並檢查是否所有的 k 個 bit 都是 set 即可
* 動畫: [Cube Drone - Bloom Filters](https://www.youtube.com/watch?v=-SuTGoFYjZs)
但這做法**存在錯誤率**，例如原本沒有在資料結構中的字串 s1 經過 hash 轉換後得出的 bit 的位置和另一個存在於資料結構中的字串 s2 經過 hash 之後的結果相同，如此一來，先前不存在的 s1 便會被認為存在，這就是 [false positive](https://en.wikipedia.org/wiki/False_positives_and_false_negatives) (指進行實用測試後，測試結果有機會不能反映出真正的面貌或狀況)。
Bloom filter 一類手法的應用很常見。例如在社群網站 Facebook，在搜尋欄鍵入名字時，能夠在 [20 億個註冊使用者](https://www.bnext.com.tw/article/45104/facebook-maus-surpasses-2-billion) (2017 年統計資料) 中很快的找到結果，甚至是根據與使用者的關聯度排序。
延伸閱讀:
* [Esoteric Data Structures and Where to Find Them](https://youtu.be/-8UZhDjgeZU?t=607)
* [Bloom Filter 影片解說](https://www.youtube.com/watch?v=bEmBh1HtYrw)
- [ ] Bloom Filter 實作方式
首先，建立一個 n bits 的 table，並將每個 bit 初始化為 0。
我們將所有的字串構成的集合 (set) 表示為 S = { x~1~, x~2~, x~3~, ... ,x~n~ }，Bloom Filter 會使用 k 個不同的 hash function，每個 hash function 轉換後的範圍都是 0 到 n-1 (為了能夠對應上面建立的 n bits table)。而對每個 S 內的 element x~i~，都需要經過 k 個 hash function，一一轉換成 k 個 index。轉換過後，table 上的這 k 個 index 的值就必須設定為 `1`。
> 注意: 可能會有同一個 index 被多次設定為 `1` 的狀況
Bloom Filter 這樣的機制，存在一定的錯誤率。若今天想要找一個字串 x 在不在 S 中，這樣的資料結構只能保證某個 x~1~ 一定不在 S 中，但沒辦法 100% 確定某個 x~2~一定在 S 中。因為會有誤判 (false positive ) 的可能。
此外，資料只能夠新增，而不能夠刪除，試想今天有兩個字串 x~1~, x~2~ 經過某個 hash function h~i~ 轉換後的結果 h~i~(x~1~) = h~i~(x~2~)，若今天要刪除 x~1~ 而把 table 中 set 的 1 改為 0，豈不是連 x~2~ 都受到影響？
- [ ] Bloom Filter 錯誤率計算
首先假設我們的所有字串集合 S 裡面有 n 個字串， hash 總共有 k 個，Bloom Filter 的 table 總共 m bits。我們會判斷一個字串存在於 S 內，是看經過轉換後的每個 bits 都被 set 了，我們就會說可能這個字串在 S 內。但試想若是其實這個字串不在 S 內，但是其他的 a b c 等等字串經過轉換後的 index ，剛好涵蓋了我們的目標字串轉換後的 index，就造成了誤判這個字串在 S 內的情況。
如上述，Bloom Filter 存有錯誤機率，程式開發應顧及回報錯誤機率給使用者，以下分析錯誤率。
當我們把 S 內的所有字串，每一個由 k 個 hash 轉換成 index 並把 `table[index]` 設為 1，而全部轉完後， table 中某個 bits 仍然是 0 的機率是 $(1-\dfrac{1}{m})^{kn}$ 。
其中 $(1-\dfrac{1}{m})$ 是每次 hash 轉換後，table 的某個 bit 仍然是 0 的機率。因為我們把 hash 轉換後到每個 index (而這個 index 會被 set) 的機率視為相等 (每人 $\dfrac{1}{m}$)，所以用 1 減掉即為不會被 set 的機率。我們總共需要做 kn 次 hash，所以就得到答案$(1-\dfrac{1}{m})^{kn}$。
由 $(1-\dfrac{1}{m})^{m}≈e^{-1}$ 特性，$(1-\dfrac{1}{m})^{kn}=((1-\dfrac{1}{m})^{m})^{\frac{kn}{m}}≈(e^{-1})^{\frac{kn}{m}}≈e^{-\frac{kn}{m}}$
以上為全部的字串轉完後某個 bit 還沒有被 set 的機率。
因此誤判的機率等同於全部經由 k 個 hash 轉完後的 k bit 已經被其他人 set 的機率:
轉完後某個 bit 被 set 機率是: $1-e^{-\frac{kn}{m}}$，因此某 k bit 被 set 機率為: ==$(1-e^{-\frac{kn}{m}})^k$==
延伸閱讀:
* [Bloom Filter](https://blog.csdn.net/jiaomeng/article/details/1495500)
### 如何選參數值
* k: 多少個不同 hash
* m: table size 的大小
**如何選 k 值?**
我們必須讓錯誤率是最小值，因此必須讓 $(1-e^{-\frac{kn}{m}})^k$ 的值是最小。先把原式改寫成 $(e^{k\ ln(1-e^{-\frac{kn}{m}})})$，我們只要使 ${k\ ln(1-e^{-\frac{kn}{m}})}$ 最小，原式就是最小值。可以看出當 $e^{-\frac{kn}{m}}=\dfrac{1}{2}$ 時，會達到最小值。因此 ==$k=ln2\dfrac{m}{n}$== 即能達到最小值。
[Bloom Filter calculator](https://hur.st/bloomfilter/?n=5000&p=3&m=&k=45) 和 [Bloom Filter calculator 2](https://krisives.github.io/bloom-calculator/) 這兩個網站可以透過設定自己要的錯誤率與資料的多寡，得到 `k` 和 `m` 值。
### [Quotient Filters](https://en.wikipedia.org/wiki/Quotient_filter)
請詳細觀看 San Diego State University 的 Rob Edwards 教授的解說影片: [Counting Quotient Filters](https://youtu.be/oMFHkuVoF70) (可開字幕)。
一般的 Bloom filter 存在以下問題：
* The inability to delete items
* Poor scaling out of RAM
* The inability to resize dynamically
* The inability to count the number of occurrences of each item, especially with skewed input distributions.
在 [A general purpose counting filter: making every bit count](https://blog.acolyer.org/2017/08/08/a-general-purpose-counting-filter-making-every-bit-count/) 提到的 Quotient filter 就著眼於解決上述問題。
請嘗試總結上述材料，解釋為何 Quotient filter 得以解決 Bloom filter 存在的限制和 [false positive](https://en.wikipedia.org/wiki/False_positives_and_false_negatives) 問題，需要特別標注對應的場景和分析 (包含缺點，如更大的空間開銷)。
:::success
延伸問題:
1. 舉出 Linux 核心中應用 Bloom filter / Quotient Filter 的案例，像是 [Add Policy Engine Algorithmic Bloom Filter Entries Register](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=418089a850c751ada5e3535d0e71c3312fe3c432) 和 [Linux Socket Filtering aka Berkeley Packet Filter (BPF)](https://www.kernel.org/doc/Documentation/networking/filter.txt)，並予以解說;
2. 本系列課程希望破除一項迷思：很多人 (特別是台灣軟體工程師) 對 Linux 核心存在嚴重偏見，以為只要基本的邏輯觀念，而不需要數學，事實上，Linux 核心大量充斥著各式數學，例如離散數學及機率統計 (歡迎下學期選修「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程)。在 Linux 核心原始程式碼中，藉由 Bloom Filter 來檢索一個元素是否在一個集合中，空間效率極高，利用 bitwise 簡潔地表示一個集合，空間效率和查詢時間都勝於常見演算法。請回想你撰寫過 (或深入追蹤過) 的程式碼，思考導入 Bloom/Quotient filer 的機會及效益，並實際量化分析。
:::
---
## 測驗 `2`
承測驗 `1`，考慮 [quotient-filter](https://github.com/sysprog21/quotient-filter) 是個 Quotient filter 實作，編譯和執行方式如下:
```shell
$ make
$ ./bench
```
程式執行輸出如下:
```
Testing 201326592 random inserts and 1000000 lookups........... done (27 seconds).
Testing 65536 contiguous inserts and 1000000 lookups........... done (72 seconds).
```
請利用 `quotient-filter.c` 裡頭的函式，實作 `qf_is_subsetof`:
```cpp
/* Check if @lhs is a subset of @rhs */
bool qf_is_subsetof(quotient_filter *lhs,
quotient_filter *rhs) {
qf_iterator qfi;
/* Write your own code */
}
```
其作用是檢查 lhr 指標所指向的 Quotient Filter 是否是 rhs 指標所指向物件的子集合 (subset)，若是則回傳 `true`，反之回傳 `false`。
完成上述 `is_subsetof` 函式的實作，作答時需要張貼完整函式宣告及內容。
---
## 測驗 `3`
承測驗 `2`，實作 `qf_merge`，使其得以合併兩個 Quotient filter 裡頭的各項:
```cpp
/*
* Initializes qf_out and copies over all elements from qf1 and qf2.
* Caution: qf_out holds twice as many entries as either qf1 or qf2.
*
* Returns false on ENOMEM.
*/
bool qf_merge(quotient_filter *qf_out,
quotient_filter *qf1,
quotient_filter *qf2) {
qf_iterator qfi;
/* Write your code here */
}
```
註: 依據 [glibc: Error Codes](https://www.gnu.org/software/libc/manual/html_node/Error-Codes.html), `ENOMEM` 意味著 "Cannot allocate memory."
> The system cannot allocate more virtual memory because its capacity is full.
完成上述 `qf_merge` 函式的實作，作答時需要張貼完整宣告及內容。
---
## 測驗 `4`
承測驗 `3`，考慮到操作過程中可能會發生非預期狀況，我們想透過 `qf_is_consistent` 函式來檢驗給定的 quotient_filter 指標對應的物件是否為有效的 Quotient filter:
```cpp
#include <assert.h>
bool qf_is_consistent(quotient_filter *qf) {
assert(qf->qbits);
assert(qf->rbits);
assert(qf->qf_table);
assert(qf->entries <= qf->max_size);
/* Write your code here */
}
```
檢驗的手法很多，例如:
```cpp
if (qf->entries == 0) {
for (uint64_t start = 0; start < qf->max_size; ++start)
if (get_elem(qf, start) != 0) return false;
return true;
}
```
請儘量依據 Quotient filter 特性，撰寫對應的 `qf_is_consistent` 驗證程式碼，作答時需要張貼完整宣告及內容，還要簡述你的檢驗項目和想法。
---
## 測驗 `5`
承測驗 `2`，實作 `qf_remove`，得以自 Quotient filter 中移除特定的 hash:
```cpp
/**
* Removes a hash from the Quotient filter.
*
* Caution: If you plan on using this function, make sure that your hash
* function emits no more than q+r bits. Consider the following scenario;
* insert(qf, A:X) # X is in the lowest q+r bits.
* insert(qf, B:X) # This is a no-op, since X is already in the table.
* remove(qf, A:X) # X is removed from the table.
*
* Now, may-contain(qf, B:X) == false, which is a ruinous false negative.
*
* Returns false if the hash uses more than q+r bits.
*/
bool qf_remove(quotient_filter *qf, uint64_t hash) {
uint64_t highbits = hash >> (qf->qbits + qf->rbits);
if (highbits)
return false;
uint64_t fq = hash_to_quotient(qf, hash);
uint64_t fr = hash_to_remainder(qf, hash);
uint64_t T_fq = get_elem(qf, fq);
if (!is_occupied(T_fq) || !qf->entries)
return true;
uint64_t start = find_run_index(qf, fq);
uint64_t s = start;
uint64_t rem;
/* Find the offending table index (or give up). */
do {
rem = get_remainder(get_elem(qf, s));
if (rem == fr) {
break;
} else if (rem > fr) {
return true;
}
s = incr(qf, s);
} while (is_continuation(get_elem(qf, s)));
if (rem != fr)
return true;
uint64_t kill = (s == fq) ? T_fq : get_elem(qf, s);
bool replace_run_start = is_run_start(kill);
/* If we are deleting the last entry in a run, clear `is_occupied'. */
if (is_run_start(kill)) {
uint64_t next = get_elem(qf, incr(qf, s));
if (!is_continuation(next)) {
T_fq = clr_occupied(T_fq);
set_elem(qf, fq, T_fq);
}
}
delete_entry(qf, s, fq);
if (replace_run_start) {
/* Write your code here */
}
--qf->entries;
return true;
}
```
完成上述 `qf_remove` 函式的實作，作答時需要張貼程式碼，並解說程式碼運作原理，同時也該解說程式註解中 `Caution:` 的考量和限制為何如此。
:::success
延伸問題:
1. 參照 [cqf](https://github.com/splatlab/cqf): A General-Purpose Counting Filter: Counting Quotient Filter 這份實作，學習其[測試程式](https://github.com/splatlab/cqf/blob/master/src/test.c)，除了新增尚有刪去 key/hash，善用測驗 `4` 發展的 `qf_is_consistent` 函式，在操作後檢驗 Quotient filter 的一致性;
2. 設計足以比較 [sysprog21/quotient-filter](https://github.com/sysprog21/quotient-filter) 和 [cqf](https://github.com/splatlab/cqf) 效能表現的實驗，可參照 論文 [A General-Purpose Counting Filter: Making Every Bit Count](https://dl.acm.org/citation.cfm?id=3035963) 的手法，並予以分析;
3. 效能分析的過程請善用 Linux 的 [perf 工具](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
* 參考 [使用 perf_events 分析程式效能](https://zh-blog.logan.tw/2019/07/10/analyze-program-performance-with-perf-events/) 和 [簡介 perf_events 與 Call Graph](https://zh-blog.logan.tw/2019/10/06/intro-to-perf-events-and-call-graph/)
:::
---
## 測驗 `6`
承測驗 `2`，研究 [cqf](https://github.com/splatlab/cqf): A General-Purpose Counting Filter: Counting Quotient Filter 這份實作，搭配對應的論文 [A General-Purpose Counting Filter: Making Every Bit Count](https://dl.acm.org/citation.cfm?id=3035963)，指出其相較於 [sysprog21/quotient-filter](https://github.com/sysprog21/quotient-filter) 有哪些相同的功能，又額外實作了哪些機制，請儘量描述。
例如: 在 [src/gqf_file.c](https://github.com/splatlab/cqf/blob/master/src/gqf_file.c) 的實作中，[cqf](https://github.com/splatlab/cqf) 支援檔案操作，但 [sysprog21/quotient-filter](https://github.com/sysprog21/quotient-filter) 僅能處理 in-memory 的資料，並且 [src/gqf_file.c](https://github.com/splatlab/cqf/blob/master/src/gqf_file.c) 利用 madvise 系統呼叫以提示 Linux 虛擬記憶體管理器做更好的分頁處理。
---
Sign in with Wallet
Connect another wallet