# 2019q3 Homework5 (quiz5)
contributed by < `kaeteyaruyo` >
## 測驗 `1`
### [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. 請回想你撰寫過 (或深入追蹤過) 的程式碼，思考導入 Bloom/Quotient filer 的機會及效益，並實際量化分析。
:::
### 解題
相較於 Bloom filter 是使用 k 個雜湊函數來製作指紋（其實是製作 index，然後用 $C^n_k$ 個 index 可能的排列組合作為指紋）， Quotient filter 則是使用一次雜湊函數，將雜湊值分拆成兩個部份，MSB (或是高位的數個 bit）的部份作為 bin index，剩下的部份作為辨認用的指紋，再搭配額外3個 meta-data bits，來達到避免碰撞、可刪除的功能。
Quotient filter 的運作原理如下：
#### 名詞定義及基本概念
* 將每一筆資料雜湊成一個 $p$ 個 bit 的雜湊值。後 $r$ 個 bit 作為 remainder，而前 $q = p - r$ 個 bit 作為 quotient。 Quotient 的功用是作為雜湊表的 index, 因此雜湊表必須要有 $2^q$ 個 entries。
* 當一筆資料 $d$ 傳入並經過雜湊運算，我們將其拆解成 quotient $d_Q$ 和 remainder $d_R$，然後將 $d_R$ 的值存入雜湊表 $table[d_Q]$ 的槽 (slot) 裡，我們將這第一個存進去的槽稱作正規槽 (canonical slot)。然而，由於雜湊函數偶爾仍有多對一的輸出發生（兩個不同數字的雜湊值相同，稱為硬碰撞 (hard collision)），或是兩個數字的雜湊值雖不同但他們的 $d_Q$ 相同（軟碰撞(soft collision)），這些碰撞都會造成兩個數字想要存進同一個槽裡的狀況發生。每當偵測到欲存入的正規槽已經有資料時，我們就會將這筆新的資料存到正規槽右邊的槽裡。如果右邊的槽也被佔據，我們就必須將右邊的那些資料再往右邊移，把新資料放進空出來的那個槽。
* Quotient filter 保證這些有同樣 Quotient 的 Remainder 會被儲存在一群相連的槽當中，這樣一個連續的槽的集合，我們稱之為一個 Run。由於上述存入規則，我們無法保證每個 Run 的第一個成員一定是被放在他的正規槽之中。
* 如果一個 Run 的第一個成員正好被放在他的正規槽當中，則我們稱這個 Run 與他右邊那些相連的 Run 一起組成了一個 Cluster。 Cluster 的範圍是到下一個未使用的槽或是下一個 Cluster 的出現為止。
* 我們使用額外的三個 bit 記錄 slot 的使用與位移狀況：
* `is_occupied`： 如果這個槽是某個 Remainder 的正規槽（表示有東西放在裏面， occupied），則設為 1。（但這個 Remainder 不一定正好放在這個槽裡）
* `is_continuation`： 如果這個槽裏面有 Remainder，但並不是其所屬 Run 的第一個 Remainder（表示他是延續在某個人後面， continuation），則設為 1。
* `is_shifted`： 如果這個槽並不是裡面放的 Remainder 的正規槽（表示原本放在裡面的東西被位移過， shifted），則設為 1。
#### 查詢資料
1. 計算該資料的雜湊值，並且拆解成 $d_Q$ 和$d_R$ 兩個部份。
2. 查看雜湊表中 $table[d_Q]$ 的 meta-bit:
* 如果三個 bit 都是 0，表示該槽為空，此筆資料必不存在。
* 若 `is_occupied` 為 set，表示該資料所屬的 Run 裏面有東西（但不一定有這筆資料）
3. 尋找資料所屬的 Run 在哪裡（有可能就在這個格子裡，但也有可能整個 Run 被右移）。為了找到 $d_Q$ 所屬的 Run 的開頭，我們必須先找到這個 Run 所屬的 cluster。
* 從 $table[d_Q]$ 開始，我們往左找到第一個 `is_shift` 是 claer 的槽，這意味著他是 cluster 的頭。
* 在途中如果我們經過了 a 個 `is_occupied` 是 set 的槽，表示 $d_Q$ 是這個 cluster 裡的第 a 個 Run。
* 接著我們從這個位置開始往右邊看，如果遇到一個槽的 `is_continuation` 是 clear，表示我們跳過了一個 Run。
* 一直到往右走，直到找到了 $d_Q$ 所屬的 Run。
4. 在資料所屬的 Run 中比對所有元素，是不是和 $d_R$ 一樣。如果有，表示資料 $d$ 有 $1 - \varepsilon$ 的機率是存在於資料庫中的。（$\varepsilon$ 是硬碰撞發生的機率）
（以上作法稱作 [Linear probing](https://en.wikipedia.org/wiki/Linear_probing)）
#### 插入資料
1. 插入資料前，我們需要先檢查這筆資料是不是已經在資料庫裡了，如果沒有才進行插入，因此要先執行跟查詢的步驟一樣的動作。
2. 由於在做查詢時不管有沒有找到，最後一個步驟時我們必定是停在該資料所屬的 Run 裏面，如果沒找到，就直接將資料插入該 Run 即可。
3. 為了加速搜尋效率，一般來說同一個 Run 裡頭的資料會是有序排列。當我們確定要將新資料插在哪一個槽之後，我們必須把該槽以及其後的所有資料都往右邊搬，然後再更新資料以及相關的 meta-bit。
* 位移資料並不會影響到位移後的槽的 `is_occupied` bit，那是由 Quotient 決定的。
* 如果新資料是該 Run 的第一個 Remainder，那麼原本的第一個資料（現在的第二個）就會變成 continuation，因此我們需要更新他的 `is_continuation` bit。
* 任何被位移過的資料，其位移後所屬的槽都要 set `is_shifted` bit。
Quotient Filter 可以有效解決一般的 Bloom filter 的問題：
#### False positive
Bloom filter 最主要的 False positive 來源是因為：多筆資料的 set bin 組合可能會剛好組成並不在資料庫當中的資料的 set bin 組合（可以視為是軟碰撞）。這是在資料量變多時難以避免的，若 table 不夠長，在過多的資料進來時很可能所有的 bin 都被設為 1，這樣無論查詢什麼資料都會回傳 true 了。
而 Quotient Filter 主要的貢獻在於解決了軟碰撞的問題。當軟碰撞發生時， Quotient Filter 並非直接覆蓋資料，而是將資料儲存在目前沒被用到的空間中，以此避免資料的損失。如果能搭配設計較好的雜湊函數，降低硬碰撞發生的機率，那麼 False positive 的機率就可以降的很低。不過相對的，為了管理資料位移的狀況， Quotient Filter 會用上比 Bloom filter 10 – 25% 的空間。
#### The inability to delete items
在 Bloom filter 中表達一個資料的方法是 set bin 的組合，這種表示法會造成各個資料之間的存在無法互相獨立（一個 bin 可能同時代表了多筆資料的存在），進而造成無法單獨刪除一筆資料的結果（clear 掉代表該資料的所有 bit 可能會進而影響其它資料的部份 bit）。
而 Quotient Filter 中表達一個資料的方法正是該資料的雜湊值，只是分拆成兩個部份儲存而已。如果沒有硬碰撞的情況發生，則每一筆資料的存在都是獨立的，想要刪除資料時，只要先查詢到資料所在的位置，再進行移除即可，不會影響到其它資料的存在（只會影響到其所在位置）。
#### The inability to resize dynamically
Bloom filter 當中的 k 個雜湊函數的值域都必須限制在 $[0, n - 1]$ 才行，這導致一旦選定了雜湊函數，表的大小也就跟著被限定了。如果更換雜湊函數來放大值域，無法保證已存在的資料經過新的雜湊函數出來的值也會跟原本一樣，甚至連要透過表內的狀態還原目前資料庫裡有哪些資料並保存都難以進行。因此可以說是無法 resize。
但 Quotient Filter 並沒有這樣的限制，因為只有一個雜湊函數，一個資料只會對應到一個指紋。而表的大小是受到 Quotient 的長度影響，變更 Quotient 的長度即可調整表的大小。雖然每次調整大小時會有搬動資料的成本，但不會造成資料的損失。
#### Poor scaling out of RAM
所謂的 scaling out，指的是在資源不足時，增添一份相同的資源來補充的作法。 Scaling out of RAM，指的是當記憶體不足時，就再增添一張新的記憶體來加大儲存空間的作法。
由於上述 Bloom filter 無法 resize 的特性，就算增加新的記憶體，也無法利用到新的儲存空間。而 Quotient Filter 可 resize 的特性正好突破了這個限制。
#### The inability to count the number of occurrences of each item
雖然上文中有提到，插入時一般來說會先檢查該資料是否存在，不存在才插入。但如果有維護資料存入次數的需要的話，其實可以新增一個 metadata 的欄位（如將 metadata 以一個 byte 的大小表示，前 3 bit 是上述的 metabit，剩下5個 bit 作為 counter），在存入資料時一併維護即可。
另一種改良版的 Counting quotient filter，在一個 remainder 被插入多於一次的時候，他的下一個格子會被用來當作他的 occurrence counter。這種作法是基於「Remainder 總是按升序儲存」這個事實，當走訪一個 Run 的途中遇到了比上一個格子小的資料，就可以知道這個格子存的是 count， 而不是下一個 remainder。然而這種作法在 counter 數到很大，以及 remainder 為 0 時需要做額外的處理。（但由於原論文的連結已經失效了，無法看到原作者提出了什麼樣的處理方式...）
### 延伸問題
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) 為例，其頁面上方有一段簡短敘述：
> Bloom filter is a bit vector which allows the HW a fast lookup on a small size bit vector, that may reduce the number of lookups on the A-TCAM memory. PEABFE register allows setting values to the bits of the bit vector mentioned above.
Add the register to be later used in A-TCAM optimizations.
這說明了接下來的程式碼是以一個小型 bit vector 作為速查表，減少直接存取記憶體的次數，用來做與 A-TCAM 記憶體有關的最佳化用的。
這段程式碼出現在[與 mlxsw 相關的暫存器設定](https://github.com/torvalds/linux/blob/81160dda9a7aad13c04e78bb2cfd3c4630e3afab/drivers/net/ethernet/mellanox/mlxsw/reg.h)當中。 [mlxsw](https://github.com/mellanox/mlxsw/wiki) 是一個交換器的管理工具，而 bloom filter 被應用在實作 [Policy engine](https://searchitoperations.techtarget.com/definition/policy-engine) 上。
```cpp
/* PEABFE - Policy-Engine Algorithmic Bloom Filter Entries Register
* ----------------------------------------------------------------
* This register configures the Bloom filter entries.
*/
#define MLXSW_REG_PEABFE_ID 0x3022
#define MLXSW_REG_PEABFE_BASE_LEN 0x10
#define MLXSW_REG_PEABFE_BF_REC_LEN 0x4
#define MLXSW_REG_PEABFE_BF_REC_MAX_COUNT 256
#define MLXSW_REG_PEABFE_LEN (MLXSW_REG_PEABFE_BASE_LEN + \
MLXSW_REG_PEABFE_BF_REC_LEN * \
MLXSW_REG_PEABFE_BF_REC_MAX_COUNT)
// 定義並註冊這一系列暫存器的基本資料
MLXSW_REG_DEFINE(peabfe, MLXSW_REG_PEABFE_ID, MLXSW_REG_PEABFE_LEN);
// 將被更新的 BF entry 總數
MLXSW_ITEM32(reg, peabfe, size, 0x00, 0, 9);
// BF 的格子，可為 set 和 clear 兩個狀態
MLXSW_ITEM32_INDEXED(reg, peabfe, bf_entry_state,
MLXSW_REG_PEABFE_BASE_LEN, 31, 1,
MLXSW_REG_PEABFE_BF_REC_LEN, 0x00, false);
// BF 的 entry bank
MLXSW_ITEM32_INDEXED(reg, peabfe, bf_entry_bank,
MLXSW_REG_PEABFE_BASE_LEN, 24, 4,
MLXSW_REG_PEABFE_BF_REC_LEN, 0x00, false);
// BF entry 的 index
MLXSW_ITEM32_INDEXED(reg, peabfe, bf_entry_index,
MLXSW_REG_PEABFE_BASE_LEN, 0, 24,
MLXSW_REG_PEABFE_BF_REC_LEN, 0x00, false);
// 雖然不知道為什麼取這個名字，但看內容物是在做記憶體初始化的，
// 會將 payload 這塊記憶體全部設為 0
static inline void mlxsw_reg_peabfe_pack(char *payload)
{
MLXSW_REG_ZERO(peabfe, payload);
}
static inline void mlxsw_reg_peabfe_rec_pack(char *payload, int rec_index,
u8 state, u8 bank, u32 bf_index)
{
// 先知道 payload 裡的 entry 有多少個
u8 num_rec = mlxsw_reg_peabfe_size_get(payload);
// 如果要更新的位置大於目前的 entry 數量，就把數量 + 1，然後再更新
if (rec_index >= num_rec)
mlxsw_reg_peabfe_size_set(payload, rec_index + 1);
// 更新 BF entry
mlxsw_reg_peabfe_bf_entry_state_set(payload, rec_index, state);
mlxsw_reg_peabfe_bf_entry_bank_set(payload, rec_index, bank);
mlxsw_reg_peabfe_bf_entry_index_set(payload, rec_index, bf_index);
}
```
這些暫存器與其 initializer 和 setter 在 [spectrum_acl_bloom_filter.c](https://github.com/torvalds/linux/blob/63bdf4284c38a48af21745ceb148a087b190cd21/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_bloom_filter.c) 當中被呼叫到，用來新增和刪除 filter 當中的 entry。所有相關的程式邏輯可以在[這些檔案](https://github.com/torvalds/linux/search?q=mlxsw+table+bf&unscoped_q=mlxsw+table+bf&type=Code)中找到，從檔名來看，這些程式碼應該是 [ACLs](https://github.com/Mellanox/mlxsw/wiki/ACLs) 這項 feature 的實作，其功能是用來管理封包轉發規則。
（有許多跟網路相關的操作細節我看的不是很清楚，只知道大致上的用意和目的是這樣而已。未來如果能看懂這些專業術語的話再回來補上更詳細的說明Q）
2. 請回想你撰寫過 (或深入追蹤過) 的程式碼，思考導入 Bloom/Quotient filer 的機會及效益，並實際量化分析。
待補充（可以等寫完dict作業再補上嗎QQ）
## 測驗 `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 */
}
```
其作用是檢查 lhs 指標所指向的 Quotient Filter 是否是 rhs 指標所指向物件的子集合 (subset)，若是則回傳 `true`，反之回傳 `false`。
完成上述 `is_subsetof` 函式的實作，作答時需要張貼完整函式宣告及內容。
### 解題
```cpp
/* Check if @lhs is a subset of @rhs */
bool qf_is_subsetof(quotient_filter *lhs,
quotient_filter *rhs) {
// 建立並初始化一個疊代器
qf_iterator qfi;
qfi_start(lhs, &qfi);
// 當 lhs 中還有東西時
while (!qfi_done(lhs, &qfi)) {
// 一一取出 lhs 中的每一個 hash 值
uint64_t hash = qfi_next(lhs, &qfi);
// 如果有任何一個 hash 值不在 rhs 中，表示 lhs 不是 rhs 的子集合，回傳 false
if(!qf_may_contain(rhs, hash)){
return false;
}
}
// 如果有每一個 lhs 中的 hash 值都在 rhs 中，表示 lhs 是 rhs 的子集合，回傳 true
return true;
}
```
## 測驗 `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` 函式的實作，作答時需要張貼完整宣告及內容。
### 解題
```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;
// 初始化 qf_out， 以 qf1 和 qf2 當中較大的 q 和 r 為主。如果初始化過程失敗，回傳 false
if(!qf_init(qf_out, qf1->qbits > qf2->qbits ? qf1->qbits + 1 : qf2->qbits + 1, qf1->rbits > qf2->rbits ? qf1->rbits : qf2->rbits))
return false;
// 遍歷過 qf1，將當中的所有 hash 值存入 qf_out
qfi_start(qf1, &qfi);
while (!qfi_done(qf1, &qfi)) {
uint64_t hash = qfi_next(qf1, &qfi);
// 若存入失敗，回傳false
if(!qf_insert(qf_out, hash))
return false;
}
// 遍歷過 qf2，將當中的所有 hash 值存入 qf_out
qfi_start(qf2, &qfi);
while (!qfi_done(qf2, &qfi)) {
uint64_t hash = qfi_next(qf2, &qfi);
// 若存入失敗，回傳false
if(!qf_insert(qf_out, hash))
return false;
}
return true;
}
```
## 測驗 `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` 驗證程式碼，作答時需要張貼完整宣告及內容，還要簡述你的檢驗項目和想法。
### 解題
```cpp
bool qf_is_consistent(quotient_filter *qf) {
// 確定該存在的元素都存在 / 非0
assert(qf->qbits);
assert(qf->rbits);
assert(qf->table);
// 確定元素計數器的值沒有超過容量
assert(qf->entries <= qf->max_size);
// 如果計數器表示沒有資料，遍歷過整個儲存空間卻有資料的話，回傳 false
if (qf->entries == 0) {
for (uint64_t start = 0; start < qf->max_size; ++start)
if (get_elem(qf, start) != 0) return false;
return true;
}
else
{
// 如果有資料的話
for (uint64_t start = 0; start < qf->max_size; ++start){
uint64_t elt = get_elem(qf, start);
uint8_t meta = (uint8_t)(elt & 7);
// 有資料，但是該資料所在的槽卻顯示為空，回傳 false
if (elt != 0 && is_empty_element(elt)) return false;
// 不可能出現的 metabit 組合，回傳 fasle
if (meta == 2 || meta == 3) return false;
}
return true;
}
}
```
* `is_continuation` 為 set 但 `is_shifted` 為 clear，是不可能出現的 metabit 組合，因為 continuation 勢必是從他的正規槽中被移出來了，才會變成 continuation 的，所以 `is_continuation` set 時 `is_shifted` 一定也會是 set。
## 測驗 `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/)
:::
### 作答
```cpp
bool qf_remove(quotient_filter *qf, uint64_t hash)
{
// Returns false if the hash uses more than q+r bits
uint64_t highbits = hash >> (qf->qbits + qf->rbits);
if (highbits)
return false;
// Get element (remainder + meta-bits) stored in qf[fq]
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 qf[fq] is not occupied (which means this slot is not canonical slot for anyone)
// or entry count is zero (which means there is nothing in filter)
// then just return ture
if (!is_occupied(T_fq) || !qf->entries)
return true;
// Otherwise, there might be something in qf[fq],
// need to find it out and delete
uint64_t start = find_run_index(qf, fq);
uint64_t s = start;
uint64_t rem;
// Find the offending table index and store in s
do {
rem = get_remainder(get_elem(qf, s));
// If found, break
if (rem == fr) {
break;
}
// Else if rem has been greater than fr, which means there is no fr
// ('cause remainders ared store in ascending order), just return true
else if (rem > fr) {
return true;
}
// Else, keep finding
s = incr(qf, s);
} while (is_continuation(get_elem(qf, s)));
// If there is no fr, return ture
if (rem != fr) {
return true;
}
// Pick up element to be removed, and check whether it is start of run
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)) {
clr_occupied(kill);
}
// Remove hash
delete_entry(qf, s, fq);
// If after removal of entry, there is still something in the slot,
// which means there is a remainder become new start of run
// need to set its shifted and continuation bit to 0
if (replace_run_start) {
uint64_t new_start = get_elem(qf, s);
if (new_start){
set_elem(qf, s, clr_continuation(new_start));
set_elem(qf, s, clr_shifted(new_start));
}
}
// Decrease entry count
--qf->entries;
return true;
}
```
### 延伸問題
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