# 2019q3 homework5 quiz5
contributed by < `nckuoverload` >

###### tags: `sysprog2019`

## 測驗`1`

Counting Quotient Filter (以下簡稱 CQF ) 在 wikipedia 的描述中，它是一種雜湊表 (hash table) 。
整個演算法流程上可以參考 [Wikipedia](https://en.wikipedia.org/wiki/Quotient_filter) ，或是搭配題目給予的影片去理解。

整個演算法相較於 Bloom Filter 在時間複雜度上優越許多，在空間複雜度上需要較多的空間，在題目給予或是主要可以參考的[論文](https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pdf)都有詳細的記載。

### A1: The inability to delete items.
Bloom Filter 不能刪除的原因在內文有提到。
:::info
此外，資料只能夠新增，而不能夠刪除，試想今天有兩個字串 x~1~, x~2~ 經過某個 hash function h~i~ 轉換後的結果 h~i~(x~1~) = h~i~(x~2~)，若今天要刪除 x~1~ 而把 table 中 set 的 1 改為 0，豈不是連 x~2~ 都受到影響？
:::

在 QF 中，會有 location (可以理解為address) 和 value 兩個部分，可以透過 locaiton 的部分尋找該值所在的位置，假如發生碰撞 (collision) 時，可透過線性 (linear) 或是二次方程 (quadratic) 去往下一個位置，因此可以理解為每一個值經過 hash function 後，可以得到一個可找到的位置，也因此可以透過清除該位置來達到刪除的效果。

### A2: Poor scaling out of RAM.
在題目提供的[參考資料](https://blog.acolyer.org/2017/08/08/a-general-purpose-counting-filter-making-every-bit-count/)中，所引用的[論文](https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pdf)有提到關於上述問題的詳述，因此借用其中一段來定義 Poor scaling out of RAM 。
:::info
Storage systems, especially log-structured merge (LSM) tree [25] based systems [4,32] and deduplication systems [14, 15, 34], use AMQs to avoid expensive queries for items that are not present. These storage systems are generally forced to keep the AMQ in RAM (instead of on SSD) to get reasonable performance, which limit their scalability
:::

簡單來說，因為這些演算法通常應用在儲存系統 (Storage system) 上，為了要有較合理的表現，所以會將這些雜湊表放在 RAM 中。也因此擴展性會較低。

在 CQF 中，每次的查詢、插入都需要 O(1) I/Os ，所以它不需要長期將雜湊表維持在 RAM 中。

### A3: The inability to resize dynamically.
在 Bloom Filter 中，若是要建立一個 BF ，必須事先設定陣列大小，然後這個大小就不可變更。
但在 CQF 中，只要事先設定 hash function 要返回幾個 bit 大小。

可參考自引用的[論文 p781, ch.4](https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pdf)。

### A4: The inability to count the number of occurrences of each item, especially with skewed input distributions.

### A5: False Positive

## 測驗`2`

bool qf_is_subsetof(quotient_filter *lhs, quotient_filter *rhs)
{
    qf_iterator qfi;
    qfi_start(lhs, &qfi);
    uint64_t target = qfi.quotient;
    for (int i = 0; i < lhs->entries; i++) {
        if (!qf_may_contain(rhs, target)) {
            return false;
        } else {
            target = qfi_next(lhs, &qfi);
        }
    }
    return true;
}

這題主要要找兩個參數，第一個參數是否為第二個參數的子集合。
首先使用 `qf_iterator` 來當作跌代器，並設一個參數當目標 `target` ，針對每一個節點使用 `qf_may_contain` 去比對是否有可能存在在第二個參數的集合中。
但因為 false positive 的問題，所以不一定為真。

## 測驗`3`

bool qf_merge(quotient_filter *qf_out,
              quotient_filter *qf1,
              quotient_filter *qf2)
{
    qf_iterator qfi;
    /* Write your code here */
    if ((qf2->entries + qf1->entries) > qf_out->max_size) {
        return false;
    }
    qfi_start(qf1, &qfi);
    uint64_t temp = qfi.quotient;
    for (int i = 0; i < qf1->entries; i++) {
        if (!qf_insert(qf_out, temp)) {
            return false;
        }
        temp = qfi_next(qf1, &qfi);
    }
    qfi_start(qf2, &qfi);
    temp = qfi.quotient;
    for (int i = 0; i < qf2->entries; i++) {
        if (!qf_insert(qf_out, temp)) {
            return false;
        }
        temp = qfi_next(qf2, &qfi);
    }
    return true;
}

題目主要要求合併兩個 `quotient_filter` ，使用的方法上比較直觀，先將第一個使用 `qf_insert` 加入 `qf_out` ，之後再將第二個依照一樣的方式加入。

## 測驗`4`

#include <assert.h>
bool qf_is_consistent(quotient_filter *qf)
{
    assert(qf->qbits);
    assert(qf->rbits);
    assert(qf->table);
    assert(qf->entries <= qf->max_size);
    /* Write your code here */
    // example
    int count = 0;
    for (uint64_t start = 0; start < qf->max_size; ++start) {
        uint64_t elem = get_elem(qf, start);
        printf("%p \n", elem);
        if (elem != 0) {
            count++;
        }
    }
    if (qf->entries != count) {
        return false;
    }
    return true;
}

題目主要是希望可以針對 `quotient filter` 的特性去做一些審查，但有些部分沒有實作出來，這部分算是沒有完成，只是將原本審查是否 entries 為 0 的情況下目標內還含有非空的變數，改成重新計算一次 size 和 entries 是否相等。