（感謝網友 @我的上鋪叫路遙 投稿）

對于海量數據處理業務，我們通常需要一個索引數據結構，用來幫助查詢，快速判斷數據記錄是否存在，這種數據結構通常又叫過濾器(filter)。考慮這樣一個場景，上網的時候需要在瀏覽器上輸入URL，這時瀏覽器需要去判斷這是否一個惡意的網站，它將對本地緩存的成千上萬的URL索引進行過濾，如果不存在，就放行，如果（可能）存在，則向遠程服務端發起驗證請求，并回饋客戶端給出警告。

索引的存儲又分為有序和無序，前者使用關聯式容器，比如B樹，后者使用哈希算法。這兩類算法各有優劣：比如，關聯式容器時間復雜度穩定O(logN)，且支持范圍查詢；又比如哈希算法的查詢、增刪都比較快O(1)，但這是在理想狀態下的情形，遇到碰撞嚴重的情況，哈希算法的時間復雜度會退化到O(n)。因此，選擇一個好的哈希算法是很重要的。

時下一個非常流行的哈希索引結構就是bloom filter，它類似于bitmap這樣的hashset，所以空間利用率很高。其獨特的地方在于它使用多個哈希函數來避免哈希碰撞，如圖所示（來源wikipedia），bit數組初始化為全0，插入x時，x被3個哈希函數分別映射到3個不同的bit位上并置1，查詢x時，只有被這3個函數映射到的bit位全部是1才能說明x可能存在，但凡至少出現一個0表示x肯定不存在。

但是，bloom filter的這種位圖模式帶來兩個問題：一個是誤報（false positives），在查詢時能提供“一定不存在”，但只能提供“可能存在”，因為存在其它元素被映射到部分相同bit位上，導致該位置1，那么一個不存在的元素可能會被誤報成存在；另一個是漏報（false nagatives），同樣道理，如果刪除了某個元素，導致該映射bit位被置0，那么本來存在的元素會被漏報成不存在。由于后者問題嚴重得多，所以bloom filter必須確保“definitely no”從而容忍“probably yes”，不允許元素的刪除。

關于元素刪除的問題，一個改良方案是對bloom filter引入計數，但這樣一來，原來每個bit空間就要擴張成一個計數值，空間效率上又降低了。

Cuckoo Hashing

為了解決這一問題，本文引入了一種新的哈希算法——cuckoo filter，它既可以確保該元素存在的必然性，又可以在不違背此前提下刪除任意元素，僅僅比bitmap犧牲了微量空間效率。先說明一下，這個算法的思想來源是一篇CMU論文，筆者按照其思路用C語言做了一個簡單實現（Github），附上對一段文本數據進行導入導出的正確性測試。

接下來我會結合自己的示例代碼講解哈希算法的實現。我們先來看看cuckoo hashing有什么特點，它的哈希函數是成對的（具體的實現可以根據需求設計），每一個元素都是兩個，分別映射到兩個位置，一個是記錄的位置，另一個是備用位置。這個備用位置是處理碰撞時用的，這就要說到cuckoo這個名詞的典故了，中文名叫布谷鳥，這種鳥有一種即狡猾又貪婪的習性，它不肯自己筑巢，而是把蛋下到別的鳥巢里，而且它的幼鳥又會比別的鳥早出生，布谷幼鳥天生有一種殘忍的動作，幼鳥會拼命把未出生的其它鳥蛋擠出窩巢，今后以便獨享“養父母”的食物。借助生物學上這一典故，cuckoo hashing處理碰撞的方法，就是把原來占用位置的這個元素踢走，不過被踢出去的元素還要比鳥蛋幸運，因為它還有一個備用位置可以安置，如果備用位置上還有人，再把它踢走，如此往復。直到被踢的次數達到一個上限，才確認哈希表已滿，并執行rehash操作。如下圖所示（圖片來源）：

我們不禁要問發生哈希碰撞之前的空間利用率是多少呢？不幸地告訴你，一維數組的哈希表上跟其它哈希函數沒什么區別，也就50%而已。但如果是二維的呢？

一個改進的哈希表如下圖所示，每個桶（bucket）有4路槽位（slot）。當哈希函數映射到同一個bucket中，在其它三路slot未被填滿之前，是不會有元素被踢的，這大大緩沖了碰撞的幾率。筆者自己的簡單實現上測過，采用二維哈希表（4路slot）大約80%的占用率（CMU論文數據據說達到90%以上，應該是擴大了slot關聯數目所致）。

Cuckoo Filter設計與實現

cuckoo hashing的原理介紹完了，下面就來演示一下筆者自己實現的一個cuckoo filter應用，簡單易用為主，不到500行C代碼。應用場景是這樣的：假設有一段文本數據，我們把它通過cuckoo filter導入到一個虛擬的flash中，再把它導出到另一個文本文件中。flash存儲的單元頁面是一個log_entry，里面包含了一對key/value，value就是文本數據，key就是這段大小的數據的SHA1值（照理說SHA1是可以通過數據源生成，沒必要存儲到flash，但這里主要為了測試而故意設計的，萬一key和value之間沒有推導關系呢）。

#define SECTOR_SIZE    (1 << 10)

define DAT_LEN        (SECTOR_SIZE - 20)  / minus sha1 size /
/* The log entries store key-value pairs on flash and the

size of each entry is assumed just one sector fit.
*/
struct log_entry {
 uint8_t sha1[20];
 uint8_t data[DAT_LEN];

};</pre> 
順便說明一下DAT_LEN設置，之前我們設計了一個虛擬flash（用malloc模擬出來），由于flash的單位是按頁大小SECTOR_SIZE讀寫，這里假設每個log_entry正好一個頁大小，當然可以根據實際情況調整。 
以上是flash的存儲結構，至于哈希表里的slot有三個成員tag，status和offset，分別是哈希值，狀態值和在flash的偏移位置。其中status有三個枚舉值：AVAILIBLE，OCCUPIED，DELETED，分別表示這個slot是空閑的，占用的還是被刪除的。至于tag，按理說應該有兩個哈希值，對應兩個哈希函數，但其中一個已經對應bucket的位置上了，所以我們只要保存另一個備用bucket的位置就行了，這樣萬一被踢，只要用這個tag就可以找到它的另一個安身之所。 
enum { AVAILIBLE, OCCUPIED, DELETED, };

/* The in-memory hash bucket cache is to filter keys (which is assumed SHA1) via

cuckoo hashing function and map keys to log entries stored on flash.
*/
struct hash_slot_cache {
 uint32_t tag : 30;  /* summary of key */
 uint32_t status : 2;  /* FSM */
 uint32_t offset;  /* offset on flash memory */

};</pre> 
乍看之下size有點大是嗎？沒關系，你也可以根據情況調整數據類型大小，比如uint16_t，這里僅僅為了測試正確性。 
至于哈希表以及bucket和slot的創建見初始化代碼。buckets是一個二級指針，每個bucket指向4個slot大小的緩存，即4路slot，那么bucket_num也就是slot_num的1/4。這里我們故意把slot_num調小了點，為的是測試rehash的發生。 
#define ASSOC_WAY  (4)  / 4-way association /

struct hash_table {
    struct hash_slot_cache *buckets;
    struct hash_slot_cache slots;
    uint32_t slot_num;
    uint32_t bucket_num;
};
int cuckoo_filter_init(size_t size)
{
    ...
    / Allocate hash slots /
    hash_table.slot_num = nvrom_size / SECTOR_SIZE;
    / Make rehashing happen /
    hash_table.slot_num /= 4;
    hash_table.slots = calloc(hash_table.slot_num, sizeof(struct hash_slot_cache));
    if (hash_table.slots == NULL) {
        return -1;
    }

/* Allocate hash buckets associated with slots */
hash_table.bucket_num = hash_table.slot_num / ASSOC_WAY;
hash_table.buckets = malloc(hash_table.bucket_num * sizeof(struct hash_slot_cache *));
if (hash_table.buckets == NULL) {
    free(hash_table.slots);
    return -1;
}
for (i = 0; i < hash_table.bucket_num; i++) {
    hash_table.buckets[i] = &hash_table.slots[i * ASSOC_WAY];
}

}</pre> 
下面是哈希函數的設計，這里有兩個，前面提到既然key是20字節的SHA1值，我們就可以分別是對key的低32位和高32位進行位運算，只要bucket_num滿足2的冪次方，我們就可以將key的一部分同bucket_num – 1相與，就可以定位到相應的bucket位置上，注意bucket_num隨著rehash而增大，哈希函數簡單的好處是求哈希值十分快。 

#define cuckoo_hash_lsb(key, count)  (((size_t *)(key))[0] & (count - 1))

define cuckoo_hash_msb(key, count)  (((size_t *)(key))[1] & (count - 1))</pre> 
終于要講解cuckoo filter最重要的三個操作了——查詢、插入還有刪除。查詢操作是簡單的，我們對傳進來的參數key進行兩次哈希求值tag[0]和tag[1]，并先用tag[0]定位到bucket的位置，從4路slot中再去對比tag[1]。只有比中了tag后，由于只是key的一部分，我們再去從flash中驗證完整的key，并把數據在flash中的偏移值read_addr輸出返回。相應的，如果bucket[tag[0]]的4路slot都沒有比中，我們再去bucket[tag[1]]中比對（代碼略），如果還比不中，可以肯定這個key不存在。這種設計的好處就是減少了不必要的flash讀操作，每次比對的是內存中的tag而不需要完整的key。 
static int cuckoo_hash_get(struct hash_table table, uint8_t key, uint8_t *read_addr)
{
    int i, j;
    uint8_t addr;
    uint32_t tag[2], offset;
    struct hash_slot_cache *slot;


tag[0] = cuckoo_hash_lsb(key, table->bucket_num);
tag[1] = cuckoo_hash_msb(key, table->bucket_num);

/* Filter the key and verify if it exists. */
slot = table-&gt;buckets[tag[0]];
for (i = 0; i bucket_num) == slot[i].tag) {
    if (slot[i].status == OCCUPIED) {
        offset = slot[i].offset;
        addr = key_verify(key, offset);
        if (addr != NULL) {
            if (read_addr != NULL) {
                *read_addr = addr;
            }
            break;
        }
    } else if (slot[i].status == DELETED) {
        return DELETED;
    }
}
...

}</pre> 
接下來先將簡單的刪除操作，之所以簡單是因為delete除了將相應slot的狀態值設置一下之外，其實什么都沒有干，也就是說它不會真正到flash里面去把數據清除掉。為什么？很簡單，沒有必要。還有一個原因，flash的寫操作之前需要擦除整個頁面，這種擦除是會折壽的，所以很多flash支持隨機讀，但必須保持順序寫。 

static void cuckoo_hash_delete(struct hash_table table, uint8_t key)
{
    uint32_t i, j, tag[2];
    struct hash_slot_cache *slot;


tag[0] = cuckoo_hash_lsb(key, table->bucket_num);
tag[1] = cuckoo_hash_msb(key, table->bucket_num);

slot = table->buckets[tag[0]];
for (i = 0; i bucket_num) == slot[i].tag) {
    slot[i].status = DELETED;
    return;
}
...

}</pre> 
了解了flash的讀寫特性，你就知道為啥插入操作在flash層面要設計成append。不過我們這里不討論過多flash細節，哈希表層面的插入邏輯其實跟查詢差不多，我就不貼代碼了。這里要貼的是如何判斷并處理碰撞，其實這里也沒啥玄機，就是用old_tag和old_offset保存一下臨時變量，以便一個元素被踢出去之后還能找到備用的安身之所。但這里會有一個判斷，每次踢人都會計數，當alt_cnt大于512時候表示哈希表真的快滿了，這時候需要rehash了。 

static int cuckoo_hash_collide(struct hash_table table, uint32_t tag, uint32_t p_offset)
{
    int i, j, k, alt_cnt;
    uint32_t old_tag[2], offset, old_offset;
    struct hash_slot_cache slot;


/* Kick out the old bucket and move it to the alternative bucket. */
offset = *p_offset;
slot = table->buckets[tag[0]];
old_tag[0] = tag[0];
old_tag[1] = slot[0].tag;
old_offset = slot[0].offset;
slot[0].tag = tag[1];
slot[0].offset = offset;
i = 0 ^ 1;
k = 0;
alt_cnt = 0;


KICK_OUT:
    slot = table->buckets[old_tag[i]];
    for (j = 0; j < ASSOC_WAY; j++) {
        if (offset == INVALID_OFFSET && slot[j].status == DELETED) {
            slot[j].status = OCCUPIED;
            slot[j].tag = old_tag[i ^ 1];
            *p_offset = offset = slot[j].offset;
            break;
        } else if (slot[j].status == AVAILIBLE) {
            slot[j].status = OCCUPIED;
            slot[j].tag = old_tag[i ^ 1];
            slot[j].offset = old_offset;
            break;
        }
    }

if (j == ASSOC_WAY) {
    if (++alt_cnt > 512) {
        if (k == ASSOC_WAY - 1) {
            /* Hash table is almost full and needs to be resized */
            return 1;
        } else {
            k++;
        }
    }
    uint32_t tmp_tag = slot[k].tag;
    uint32_t tmp_offset = slot[k].offset;
    slot[k].tag = old_tag[i ^ 1];
    slot[k].offset = old_offset;
    old_tag[i ^ 1] = tmp_tag;
    old_offset = tmp_offset;
    i ^= 1;
    goto KICK_OUT;
}

return 0;

}</pre> 
rehash的邏輯也很簡單，無非就是把哈希表中的buckets和slots重新realloc一下，空間擴展一倍，然后再從flash中的key重新插入到新的哈希表里去。這里有個陷阱要注意，千萬不能有相同的key混進來！雖然cuckoo hashing不像開鏈法那樣會退化成O(n)，但由于每個元素有兩個哈希值，而且每次計算的哈希值隨著哈希表rehash的規模而不同，相同的key并不能立即檢測到沖突，但當相同的key達到一定規模后，噩夢就開始了，由于rehash里面有插入操作，一旦在這里觸發碰撞，又會觸發rehash，這時就是一個rehash不斷遞歸的過程，由于其中老的內存沒釋放，新的內存不斷重新分配，整個程序就如同陷入DoS攻擊一般癱瘓了。所以每次插入操作前一定要判斷一下key是否已經存在過，并且對rehash里的插入使用碰撞斷言防止此類情況發生。筆者在測試中不幸中了這樣的彩蛋，調試了大半天才搞清楚原因，搞IT的同學們記住一定要防小人啊~ 

static void cuckoo_rehash(struct hash_table table)
{
    ...
    uint8_t read_addr = nvrom_base_addr;
    uint32_t entries = log_entries;
    while (entries--) {
        uint8_t key[20];
        uint32_t offset = read_addr - nvrom_base_addr;
        for (i = 0; i &lt; 20; i++) {
            key[i] = flash_read(read_addr);
            read_addr++;
        }
        /* Duplicated keys in hash table which can cause eternal


     * hashing collision! Be careful of that!
     */
    assert(!cuckoo_hash_put(table, key, &offset));
    if (cuckoo_hash_get(&old_table, key, NULL) == DELETED) {
        cuckoo_hash_delete(table, key);
    }
    read_addr += DAT_LEN;
}
...

}</pre> 
到此為止代碼的邏輯還是比較簡單，使用效果如何呢？我來幫你找個大文件unqlite.c測試一下，這是一個嵌入式數據庫源代碼，共59959行代碼。作為需要導入的文件，編譯我們的cuckoo filter，然后執行： 

./cuckoo_db unqlite.c output.c
 
你會發現生成output.c正好也是59959行代碼，一分不差，probably yes終于變成了definitely yes。同時也可以看到，cuckoo filter真的很快！如果你想看hashing的整個過程，可以參照README里把調試宏打開。最后，歡迎給這個小玩意提交PR！ 

參考資料 

Cuckoo Filter的論文和PPT：Cuckoo Filter: Practically Better Than Bloom 



歡迎關注CoolShell微信公眾賬號 


（轉載本站文章請注明作者和出處 酷 殼 – CoolShell.cn ，請勿用于任何商業用途） 

——=== 訪問 酷殼404頁面 尋找遺失兒童。 ===——