--- tags: sysprog --- # 2019q3 Homework5 (quiz5) contributed by < `rageNami` `yxguo2536` > ## 測驗 `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. 本系列課程希望破除一項迷思：很多人 (特別是台灣軟體工程師) 對 Linux 核心存在嚴重偏見，以為只要基本的邏輯觀念，而不需要數學，事實上，Linux 核心大量充斥著各式數學，例如離散數學及機率統計 (歡迎下學期選修「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程)。在 Linux 核心原始程式碼中，藉由 Bloom Filter 來檢索一個元素是否在一個集合中，空間效率極高，利用 bitwise 簡潔地表示一個集合，空間效率和查詢時間都勝於常見演算法。請回想你撰寫過 (或深入追蹤過) 的程式碼，思考導入 Bloom/Quotient filer 的機會及效益，並實際量化分析。 ::: #### The inability to delete items Bloom Filter 是一組 bit array，而資料 (item) 經過雜湊函數後會映射到 bit array 中的特定 bit position。然而，這些 bits 是共用的，也就是說，資料的存在並非互相獨立，同一個 bit position 可能對應到多筆資料，我無法將特定 bit position 設為 clear 來刪除特定 item，因為有可能連帶影響到其他 items 的存在。 Quotient Filter 可以做到刪除，因為 table 內部劃分成數個槽位 (slots)，每個槽位能存放一筆資料且槽位之間的資料互相獨立。刪除的時候只要把該槽位清空，並按照特定規則將同一 cluster 內資料往前挪動補上被刪除槽位的空位。 因此，資料的刪除不會影響其他資料的存在，只是會影響其他資料的擺放位置。 #### The inability to resize dynamically 在 Bloom Filter 的建置過程中，我們首先要配置一個 n bits 空間的 hash table，之後讓每個 hash function 的輸出值域配合 table size 限定在 [0, n-1] 之間。 而當我今天想要擴增 table 大小變成 M bits 以容納更多 elements，那我勢必得要修改 hash function，使他們的輸出值域變成 [0, M-1]，但如此一來我們就必須對 table 中現有的 elements 都以新的 hash function re-hashing 一次，如此才能讓所有 elements 擺放到新 table 中的正確位置，而要縮減 table 大小時也是同理。 因此，Bloom Filter 沒辦法在不 re-hashing 的前提下做到 resize。 但 Quotient Filter 不一樣，資料經過雜湊函數後會變成 p-bits 的整數，再將其拆成 q-bits quotient 和 r-bits remainder 來決定資料的 index (quotient) 和 fingerprint (remainder)，並使得 q + r = p，也因此這個 table 會有 $2^q$ 個 entries。 當我今天想要擴增 table size，我需要做的就是把更多 bits 分配給 q、更少 bits 分配給 r，以維持 q + r = p。 過程中，我並沒有丟失或變更原本的 p-bits 資料，因此 resizing 雖會有資料搬移的成本，但因為 hash function 沒有變動所以不需要 re-hashing。 #### Poor scaling out of RAM to SSD Bloom Filter 之所以難以把儲存媒介從記憶體轉移到硬碟，是因為他沒辦法限制 lookup / insert 操作會存取的記憶體範圍。 對於 n bits table，最糟情況下可能會需要存取 index = 0 和 index = n-1 的記憶體位址。 如此便會很容易發生 cache miss 進而造成額外的時間開銷。 cahce miss 的時間成本對於部分應用來說或許還能夠接受，因為 cache 和 記憶體的存取速度差距不大。 但在硬碟上也會有同樣的問題，硬碟的資料是以 block 為單位加載進記憶體。 如果我們需要存取的資料橫跨數個 block 的範圍，那麼就容易造成 page fault，需要再把硬碟上的 block 搬到記憶體。 然而，硬碟與記憶體的存取速度相差甚遠，甚至有大約 10,000 倍的差距，這就導致 Bloom Filter 在以硬碟為儲存媒介時並不實用。 為了解決此問題，我們會希望資料的擺放位置可以限制讓大多數操作都只存取小範圍內的記憶體位置。 如果有資料結構符合這樣的特性，我們會說此資料結構有 good data locality 。 而 Quotient Filter 相比 Bloom Filter，就有更好的 data locality。在進行 lookup 時，Quotient Filter 只需要走訪目標 cluster 中每個 slot 的 metabits 以找到目標 run，再走訪目標 run 中每個 slot 的 remainder，就能完成搜尋。 因此其資料範圍相對 Bloom Filter 是更集中的。 甚至在 Rank-and-Select Quotient Filter ( RSQF ) 中，data locality 有更進一步的優化，因為他可以更快找到目標 run 的開頭位置。 相比原版 QF 要從 cluster 中一次一 slot 檢查其 metabits，RSQF 的 rank 和 select 操作可以一次處理 64 bits metadata，從原本的 bit operation 改成了 word operation。 #### The inability to count the number of occurrences of each item, especially with skewed input distributions. 由 Bloom Filter 衍伸出來的 Counting Bloom Filter 雖然可以做到 counting ，但他是採用 fixed-sized counter 的設計，當數量太多就會溢位。 而解決辦法就是當有任何一個 counter 滿了，就加大整體的 table size 已獲得更大的 counter 空間。 然而，這種設計卻不適合拿來儲存 skewed data input，因為他必須把 table size 加到很大才能確保每個 counter 都能容納資料集中出現頻率最高的 element，但對於其餘絕大部分 counter 來說就會造成越來越多的空間浪費。 而 Counting Quotient Filter 採用的是 variable-sized counter，因此對於 skewed data input 也有很高的適應性。 #### Quotienet Filter 與 Bloom Filter 的空間效率分析 [Don’t Thrash: How to Cache Your Hash on Flash](https://vldb.org/pvldb/vol5/p1627_michaelabender_vldb2012.pdf) 比較 Bloom Filter 和 Quotient Filter 的錯誤率(false positive rate)與空間使用率(bits/element)，如下圖所示。 ![](https://i.imgur.com/YxiZY6d.png) - Bloom Filter - [False positive rate](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903775)=$(1−e^{-\frac{kn}{m}})^k$ > k: number of independent hash functions > m: bit size of table > n: number of objects mapped into the Bloom filter > when , false positive rate has a minimum. - Bit per element =$\frac{m}{n}$ - Quotient Filter - bits per elements S : $\frac{(r+3)}{\alpha}$ - [False positive rate $\delta$ : ](https://vldb.org/pvldb/vol5/p1627_michaelabender_vldb2012.pdf) $1-(1-\frac{1}{2^p})^{\alpha2^q}= 1-(1-\frac{1}{2^p})^{\alpha2^q} \approx 1-e^{\frac{-{\alpha2^q}}{2^p}} = 1-e^{\frac{-{\alpha}}{2^r}}$ > p : # of bits of hashed fingerprint > q : # of bits of quotient > r : # of bits of remainder > $\alpha$ : load factor > n : # of inserted elements, equal to $\alpha * 2^q$ 論文中為了讓 Bloom filter 的錯誤率最小，選擇 $k=\ln{2}\frac{m}{n}$。當 m = 8n ，錯誤率為 1.56% (實際上為 2.15%)。而 Quotient Filter 的錯誤率與 (p, q, r, n) 相關，如果我們使用的 hash function 生成 64 bits hash(即 p=64 )，計算在 α=0.9 or 0.75 下不同 (q, r) 的錯誤率和空間使用率的關係。 ![](https://i.imgur.com/IiwsK5m.png) **Bloom Filter** -log(錯誤率) | Bit/element | ---|--- 1.03643 |5 1.23821 |6 1.46020 |7 1.66601 |8 1.87001 |9 6.25956 |30 **Quotient Filter** -log(錯誤率) | Bit/element | ---|--- 0.97305 |6.7 1.26203 |7.8 1.55700 |8.9 1.85499 |10.0 7.27048 |30.0 從圖表得知 Quotient Filter (3bits, alpha=0.9)隨著錯誤率減少對於每個 element 使用的空間會多同樣錯誤率的 Bloom Filter 約 20% (Bit/element=30 時多16%)。 ## 測驗 `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` 函式的實作，作答時需要張貼完整函式宣告及內容。 ```c bool qf_is_subsetof(quotient_filter *lhs, quotient_filter *rhs) { qf_iterator lqfi; // Check if each element in @lhs also exist in @rhs qfi_start(lhs, &lqfi); while(!qfi_done(lhs, &lqfi)){ if(!qf_may_contain(rhs, qfi_next(lhs, &lqfi))){ return false; } } 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` 函式的實作，作答時需要張貼完整宣告及內容。 ```c bool qf_merge(quotient_filter *qf_out, quotient_filter *qf1, quotient_filter *qf2) { qf_iterator qfi; // Allocate memory for @qf_out #define MAX(a,b) ((a)>(b)? (a) : (b)) uint32_t q = MAX(qf1->qbits, qf2->qbits); uint32_t r = MAX(qf1->rbits, qf2->rbits); if(!qf_init(qf_out, q, r)){ return false; } // For every element in @qf1 @qf2, insert them into @qf_out qfi_start(qf1, &qfi); while(!qfi_done(qf1, &qfi)){ qf_insert(qf_out, qfi_next(qf1, &qfi)); } qfi_start(qf2, &qfi); while(!qfi_done(qf2, &qfi)){ qf_insert(qf_out, qfi_next(qf2, &qfi)); } 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` 驗證程式碼，作答時需要張貼完整宣告及內容，還要簡述你的檢驗項目和想法。 ```c bool qf_is_consistent(quotient_filter *qf) { // Make sure all the properties of quotient_filter exist (non-zero) assert(qf->qbits); assert(qf->rbits); assert(qf->elem_bits); assert(qf->qf_table); assert(qf->index_mask); assert(qf->elem_mask); assert(qf->rmask); // Make sure entry counter doesn't exceed max size assert(qf->entries <= qf->max_size); // When entry counter is 0, make sure no elements contain in table // When entry counter isn't 0, make sure all elements' metabits is legal 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{ qf_iterator qfi; qfi_start(qf, &qfi); while(!qfi_done(qf, &qfi)){ uint64_t elt = qfi_next(qf, &qfi); if( is_continuation(elt) && !is_shifted(elt) ) { // if `is_continuation` is set, `is_shifted` must be set too. return false; } } return true; } } ``` --- ## 測驗 `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:` 的考量和限制為何如此。 **qf_remove實作** ```clike= 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 */ 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)); T_fq &= ~1ULL | (next & 2ULL) >> 1; set_elem(qf, fq, T_fq); } delete_entry(qf, s, fq); if (replace_run_start) { uint64_t next = get_elem(qf, s); /* Clear continuation bit. */ next &= ~2; if (s==fq && is_run_start(next)) { /* The new start is in the canonical slot. */ next &= ~4; } set_elem(qf, s, next); } --qf->entries; return true; } ``` 7~30 行:先尋找 hash 所屬 run 的起始點，循序往下找到對應的 slot ，若沒有符合的remainder 代表 filter 內不存在，返回 true。 36~40 行:移除前，先確定 hash 是否為 run 唯一一個元素，視情況清空 canonical slot 的 `is_occupied` 44 行後: `delete_entry` 雖然會刪掉 `qf[s]` ，並且將 cluster 內剩餘的元素往前移 (可能不包含 is_occupied 的 metadata) ，對於更新後的第一項資料 `qf[s]` ，如果成為新 run 的首項 (replace_run_start = 1)，需要更新 metadata: - is_occupied: 無需考慮 - is_continuation: run of start 的 is_continuation bit 恆為 0 - is_shifted: 對照 quotient filter 的[表格](https://en.wikipedia.org/wiki/Quotient_filter)，`is_shifted = 0` 只有在下述兩者成立 1. slot 為 start of run 且處於自身的 canonical slot 2. empty slot 位移前的 empty slot 經過位移後仍為 empty slot，要考慮的情況只有 1. **Caution的考量** 回頭看此份 quotient filter 的 `qf_insert` 實作，除了 input hash 有著 `uint64_t` 的限制，接下來依照 `qf_init` 所宣告的 quotient/remainder bit length 切成 `fq` 和 `fr` 以尋找對應的 slot。 ```clike= bool qf_insert(quotient_filter *qf, uint64_t hash) { if (qf->entries >= qf->max_size) return false; uint64_t fq = hash_to_quotient(qf, hash); uint64_t fr = hash_to_remainder(qf, hash); ... } ``` :::info 因為 `qf_insert` 允許使用者輸入大於 `q+r` bits 卻又小於 64 bits (uint64_t) 的 hash 才有接下來的問題 ::: 現在 insert 兩組 hash 到 quotient filter 內，分別是 `A:X` 和 `B:X` ，`X` 為長度 q+r 的 lower bits，也就是 quotient filter 進行操作所需的 quotient + remainder，剩下的 remaining bits (A/B) 會在 insert 時被捨棄掉。考慮下列情況： ```clike= insert(qf, A:X) insert(qf, B:X) remove(qf, A:X) ``` 以 quotient filter 的角度看來 `A:X` 和 `B:X` 使用到同一個 slot，於是使用 `remove(A:X)` 移除對應 element 的同時 `B:X` 對應的 element 也會被移除，造成查詢時的 ruinous false negative 。原始程式消極的在 `qf_remove` 剔除了這個操作: ```clike= uint64_t highbits = hash >> (qf->qbits + qf->rbits); if (highbits) return false; ``` 問題來了，成功插入 quotient filter 的 `A:X` 如何移除? :::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) 有哪些相同的功能，又額外實作了哪些機制，請儘量描述。 相較 [sysprog21/quotient-filter](https://github.com/sysprog21/quotient-filter) 實做的 quotient filter，[splatlab/cqf](https://github.com/splatlab/cqf) 實做的 (counting) quotient filter 主要多了以下幾個功能： 1. 檔案操作 [quotient-filter/quotient-filter.c](https://github.com/sysprog21/quotient-filter/blob/master/quotient-filter.c) 實做的 hash table 是儲存在記憶體內的。而 cqf 除了可以使用記憶體外， [src/gqf_file.c](https://github.com/splatlab/cqf/blob/master/src/gqf_file.c) 的實做也使 cqf 可以把 table 建在硬碟上。 ```c bool qf_initfile(QF *qf, uint64_t nslots, uint64_t key_bits, uint64_t value_bits, enum qf_hashmode hash, uint32_t seed, const char *filename) { ... // 取得 file descriptor qf->runtimedata->f_info.fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, S_IRWXU); ... // 配置檔案空間 ret = posix_fallocate(qf->runtimedata->f_info.fd, 0, total_num_bytes); ... // 將檔案空間映射到記憶體上 qf->metadata = (qfmetadata *)mmap(NULL, total_num_bytes, PROT_READ | PROT_WRITE, MAP_SHARED, qf->runtimedata->f_info.fd, 0); ... // 提示 kernal 我們不會照順序讀寫，請它停止預設的 read ahead 預讀模式 ret = madvise(qf->metadata, total_num_bytes, MADV_RANDOM); ... } ``` 一般要進行檔案操作，常見的做法是以 fopen()、fprintf()、fscanf() 等函式來進行。 但這邊 [src/gqf_file.c](https://github.com/splatlab/cqf/blob/master/src/gqf_file.c) 的實做則是以 mmap() 把硬碟空間映射到記憶體。如此一來，只有建立檔案、關閉檔案的函式會有別於一般的 qf 操作，其餘 insert / lookup / remove 函式都是通用的。 2. 雜湊函式 qf 中沒有提供雜湊函式，所以其實這份 quotient filter 實做其實還不完整。而 [src/hashutil.c](https://github.com/splatlab/cqf/blob/master/src/hashutil.c) 有提供兩種雜湊函式，一種是基於標準函式庫 libssl ，另一種是可逆的 MurmurHash。 3. 支援多執行緒 cqf 支援平行運算，為此 [src/partitioned_counter.c](https://github.com/splatlab/cqf/blob/master/src/partitioned_counter.c) 中使用了大量 C11 新增的原子操作，用以管理多核心之間的資料同步問題。 ```c void pc_sync(pc_t *pc) { for (uint32_t i = 0; i < pc->num_counters; i++) { int64_t c = __atomic_exchange_n(&pc->local_counters[i].counter, 0, __ATOMIC_SEQ_CST); __atomic_fetch_add(pc->global_counter, c, __ATOMIC_SEQ_CST); } } ``` --- ## 延伸問題 1. 設計足以比較 sysprog21/quotient-filter 和 cqf 效能表現的實驗，可參照 論文 A General-Purpose Counting Filter: Making Every Bit Count 的手法，並予以分析; **實驗目標** 紀錄 load factor = [0.05, 0.95] 情況下 QF/CQF 的 insertion/lookup throughput 。 因為 QF 沒有 counting 的功能，所以相較原論文的測試，同樣的一筆資料 CQF 也只會插入一次。 ```clike= // 原論文測試 uint64_t key_count = 100000000; int ret = qf_insert(&qf, vals[i], 0, key_count, QF_NO_LOCK); // 此處的測試 uint64_t key_count = 1; int ret = qf_insert(&qf, vals[i], 0, key_count, QF_NO_LOCK); ``` 完整的測試腳本在[github](https://github.com/yxguo2536/quotient-filter/blob/master/src/bench2.c)。 **實驗環境** ```bash # 取得硬體資訊 ~$ sudo lshw # 印出核心版本 ~$ uname -r # 查看發行版資訊 ~$ lsb_release -a ``` - Ubuntu 19.10 (eoan) - Linux 5.3.0-24-generic - Intel i5-8500 3.00Hz 6C/6T > L1/L2/L3: 384KiB/1536KiB/9MiB > C-states: ON > [SpeedStep](https://forums.anandtech.com/threads/actual-difference-between-speedstep-and-turbo-boost.2226820/#post-33017497): ON > TurboBoost: ON > - DDR4 2666MHz 16G > Single Channel - Micron CT250MX500SSD1 > EXT4 VOLUME > 560 MB/s Read, 510 MB/s Write > [Random Read/Write IOPS](https://www.crucial.com/wcsstore/CrucialSAS/pdf/product-flyer/crucial-mx500-ssd-productflyer-en.pdf): 95K/90K **實驗結果** - In memory - insertion ![](https://i.imgur.com/y1n5adY.png) - lookup ![](https://i.imgur.com/mGm9PVU.png) - On disk - insertion ![](https://i.imgur.com/AE2MlaE.png) - lookup ![](https://i.imgur.com/TFwXS34.png) 目前我們做的實驗還不完善。由上圖可以看到，主要有 2 個問題還無法解決： 1. 做 insertion 時，理論上執行效率應該是嚴格遞減，但實際上第一個取樣點的執行效率卻出奇的低效 2. 單純考慮資料結構，論文提出的 CQF 設計理應有比一般 QF 更好的 data locality，進而可以有更高的執行效率。 然而在實做上，我們發現 CQF 竟然比一般的 QF 更慢，這一點難以解釋。 不過撇除上述兩點，我們還是可以看出 CQF 有一個優點 ： 它的執行效率比一般 QF 更加穩定，不管 insertion 或 lookup 都不會因為 load factor 的成長而有顯著的下滑。 因此 CQF 有機會應用在需要即時回應的系統上。 ## 參考資料 1. [Quotient Filter - Wikipedia](https://en.wikipedia.org/wiki/Quotient_filter) 2. [quotient filter解读](https://blog.csdn.net/qq_25956141/article/details/80987461) 3. [Locality of reference - Wikipedia](https://en.wikipedia.org/wiki/Locality_of_reference) 4. [Hash table - Wikipedia](https://en.wikipedia.org/wiki/Hash_table#Key_statistics) 5. [kaeteyaruyo 的共筆](https://hackmd.io/@kaeteyaruyo/2019q3_quiz5) 6. [vedantk/quotient-filter - Github](https://github.com/vedantk/quotient-filter/blob/master/qf.c) 7. [C++11开发中的Atomic原子操作](https://www.cnblogs.com/the-tops/p/6347584.html) 8. [Symbols in LaTeX and HTML](https://www.stevesque.com/symbols/)