2019q3 第 5 週測驗題

注意須知:

1. 答題時請先建立一份 HackMD 共筆，並設定其存取權限為「任何人都可讀取、已登入系統者可編輯」，隨後將 HackMD 網址張貼於表單中。每題都是申論題，答題時請善用 LaTeX 語法;
2. 可翻閱書籍、可使用網頁搜尋引擎，亦可使用編譯器和除錯器來實驗，但在測驗期間 (15:00-23:50 Oct 10)，禁止任何形式的討論;
3. 以合法 C 語言 (C99 以上的規格) 撰寫程式碼，需列出完整程式碼;
4. 題目較之前測驗更長，請務必耐心閱讀
5. 為了避免學員大量從給定素材中直接複製貼上原文，作答時請儘量用漢語書寫 (當然，程式碼、數學表達式、關鍵字和科技詞彙不在此限);
6. 測驗題共 6 題，每題 20 分

---

測驗 1

本題引導學員實作 Quotient Filters，在這之前需要先對 Bloom Filter 有概念。

• 何謂 Bloom Filter

當我們要在大量的資料中搜尋一個字串時，最簡單的方式就是走訪每個資料存放單位，對應的時間複雜度是

$O(n)$。

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

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

$O(n)$ 。

• n-bits 的 table
• k 個 hash fucntion: h₁ 、 h₁ … 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

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

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

延伸閱讀:

• Esoteric Data Structures and Where to Find Them
• Bloom Filter 影片解說

• Bloom Filter 實作方式

首先，建立一個 n bits 的 table，並將每個 bit 初始化為 0。

我們將所有的字串構成的集合 (set) 表示為 S = { x₁, x₂, x₃, … ,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₁ 一定不在 S 中，但沒辦法 100% 確定某個 x₂一定在 S 中。因為會有誤判 (false positive ) 的可能。

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

• 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-{\displaystyle \frac{1}{m}}{)}^{kn}$ 。

其中

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

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

$(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}}$
以上為全部的字串轉完後某個 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

如何選參數值

• k: 多少個不同 hash
• m: table size 的大小

如何選 k 值?

我們必須讓錯誤率是最小值，因此必須讓

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

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

$kln(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 值。

Quotient Filters

請詳細觀看 San Diego State University 的 Rob Edwards 教授的解說影片: Counting Quotient Filters (可開字幕)。

一般的 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 提到的 Quotient filter 就著眼於解決上述問題。

請嘗試總結上述材料，解釋為何 Quotient filter 得以解決 Bloom filter 存在的限制和 false positive 問題，需要特別標注對應的場景和分析 (包含缺點，如更大的空間開銷)。

延伸問題:

1. 舉出 Linux 核心中應用 Bloom filter / Quotient Filter 的案例，像是 Add Policy Engine Algorithmic Bloom Filter Entries Register 和 Linux Socket Filtering aka Berkeley Packet Filter (BPF)，並予以解說;
2. 本系列課程希望破除一項迷思：很多人 (特別是台灣軟體工程師) 對 Linux 核心存在嚴重偏見，以為只要基本的邏輯觀念，而不需要數學，事實上，Linux 核心大量充斥著各式數學，例如離散數學及機率統計 (歡迎下學期選修「Linux 核心設計」課程)。在 Linux 核心原始程式碼中，藉由 Bloom Filter 來檢索一個元素是否在一個集合中，空間效率極高，利用 bitwise 簡潔地表示一個集合，空間效率和查詢時間都勝於常見演算法。請回想你撰寫過 (或深入追蹤過) 的程式碼，思考導入 Bloom/Quotient filer 的機會及效益，並實際量化分析。

---

測驗 2

承測驗 1，考慮 quotient-filter 是個 Quotient filter 實作，編譯和執行方式如下:

$ 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:

/* 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 裡頭的各項:

/*
 * 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, 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:

#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 */
}

檢驗的手法很多，例如:

    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:

/**
 * 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: 的考量和限制為何如此。

延伸問題:

1. 參照 cqf: A General-Purpose Counting Filter: Counting Quotient Filter 這份實作，學習其測試程式，除了新增尚有刪去 key/hash，善用測驗 4 發展的 qf_is_consistent 函式，在操作後檢驗 Quotient filter 的一致性;
2. 設計足以比較 sysprog21/quotient-filter 和 cqf 效能表現的實驗，可參照 論文 A General-Purpose Counting Filter: Making Every Bit Count 的手法，並予以分析;
3. 效能分析的過程請善用 Linux 的 perf 工具
   • 參考 使用 perf_events 分析程式效能 和 簡介 perf_events 與 Call Graph

---

測驗 6

承測驗 2，研究 cqf: A General-Purpose Counting Filter: Counting Quotient Filter 這份實作，搭配對應的論文 A General-Purpose Counting Filter: Making Every Bit Count，指出其相較於 sysprog21/quotient-filter 有哪些相同的功能，又額外實作了哪些機制，請儘量描述。

例如: 在 src/gqf_file.c 的實作中，cqf 支援檔案操作，但 sysprog21/quotient-filter 僅能處理 in-memory 的資料，並且 src/gqf_file.c 利用 madvise 系統呼叫以提示 Linux 虛擬記憶體管理器做更好的分頁處理。

---