建站
咨詢
售后
建站咨詢
新聞中心
對于海量數(shù)據(jù)處理業(yè)務(wù)，我們通常需要一個(gè)索引數(shù)據(jù)結(jié)構(gòu)，用來幫助查詢，快速判斷數(shù)據(jù)記錄是否存在，這種數(shù)據(jù)結(jié)構(gòu)通常又叫過濾器(filter)。考慮這樣一個(gè)場景，上網(wǎng)的時(shí)候需要在瀏覽器上輸入U(xiǎn)RL，這時(shí)瀏覽器需要去判斷這是否一個(gè)惡意的網(wǎng)站，它將對本地緩存的成千上萬的URL索引進(jìn)行過濾，如果不存在，就放行，如果(可能)存在，則向遠(yuǎn)程服務(wù)端發(fā)起驗(yàn)證請求，并回饋客戶端給出警告。
站在用戶的角度思考問題，與客戶深入溝通，找到肥城網(wǎng)站設(shè)計(jì)與肥城網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都做網(wǎng)站、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、國際域名空間、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋肥城地區(qū)。
索引的存儲(chǔ)又分為有序和無序，前者使用關(guān)聯(lián)式容器，比如B樹，后者使用哈希算法。這兩類算法各有優(yōu)劣：比如，關(guān)聯(lián)式容器時(shí)間復(fù)雜度穩(wěn)定O(logN)，且支持范圍查詢;又比如哈希算法的查詢、增刪都比較快O(1)，但這是在理想狀態(tài)下的情形，遇到碰撞嚴(yán)重的情況，哈希算法的時(shí)間復(fù)雜度會(huì)退化到O(n)。因此，選擇一個(gè)好的哈希算法是很重要的。
時(shí)下一個(gè)非常流行的哈希索引結(jié)構(gòu)就是bloom filter[1]，它類似于bitmap這樣的hashset，所以空間利用率很高。其獨(dú)特的地方在于它使用多個(gè)哈希函數(shù)來避免哈希碰撞，如圖所示(來源wikipedia[2])，bit數(shù)組初始化為全0，插入x時(shí)，x被3個(gè)哈希函數(shù)分別映射到3個(gè)不同的bit位上并置1，查詢x時(shí)，只有被這3個(gè)函數(shù)映射到的bit位全部是1才能說明x可能存在，但凡至少出現(xiàn)一個(gè)0表示x肯定不存在。
Bloom_filter
但是，bloom filter的這種位圖模式帶來兩個(gè)問題：一個(gè)是誤報(bào)(false positives)，在查詢時(shí)能提供“一定不存在”，但只能提供“可能存在”，因?yàn)榇嬖谄渌乇挥成涞讲糠窒嗤琤it位上，導(dǎo)致該位置1，那么一個(gè)不存在的元素可能會(huì)被誤報(bào)成存在;另一個(gè)是漏報(bào)(false nagatives)，同樣道理，如果刪除了某個(gè)元素，導(dǎo)致該映射bit位被置0，那么本來存在的元素會(huì)被漏報(bào)成不存在。由于后者問題嚴(yán)重得多，所以bloom filter必須確?！癲efinitely no”從而容忍“probably yes”，不允許元素的刪除。
關(guān)于元素刪除的問題，一個(gè)改良方案是對bloom filter引入計(jì)數(shù)，但這樣一來，原來每個(gè)bit空間就要擴(kuò)張成一個(gè)計(jì)數(shù)值，空間效率上又降低了。
Cuckoo Hashing
為了解決這一問題，本文引入了一種新的哈希算法——cuckoo filter，它既可以確保該元素存在的必然性，又可以在不違背此前提下刪除任意元素，僅僅比bitmap犧牲了微量空間效率。先說明一下，這個(gè)算法的思想來源是一篇CMU論文[3]，筆者按照其思路用C語言做了一個(gè)簡單實(shí)現(xiàn)(Github地址[4])，附上對一段文本數(shù)據(jù)進(jìn)行導(dǎo)入導(dǎo)出的正確性測試。
接下來我會(huì)結(jié)合自己的示例代碼講解哈希算法的實(shí)現(xiàn)。我們先來看看cuckoo hashing有什么特點(diǎn)，它的哈希函數(shù)是成對的(具體的實(shí)現(xiàn)可以根據(jù)需求設(shè)計(jì))，每一個(gè)元素都是兩個(gè)，分別映射到兩個(gè)位置，一個(gè)是記錄的位置，另一個(gè)是備用位置。這個(gè)備用位置是處理碰撞時(shí)用的，這就要說到cuckoo這個(gè)名詞的典故了，中文名叫布谷鳥，這種鳥有一種即狡猾又貪婪的習(xí)性，它不肯自己筑巢，而是把蛋下到別的鳥巢里，而且它的幼鳥又會(huì)比別的鳥早出生，布谷幼鳥天生有一種殘忍的動(dòng)作，幼鳥會(huì)拼命把未出生的其它鳥蛋擠出窩巢，今后以便獨(dú)享“養(yǎng)父母”的食物。借助生物學(xué)上這一典故，cuckoo hashing處理碰撞的方法，就是把原來占用位置的這個(gè)元素踢走，不過被踢出去的元素還要比鳥蛋幸運(yùn)，因?yàn)樗€有一個(gè)備用位置可以安置，如果備用位置上還有人，再把它踢走，如此往復(fù)。直到被踢的次數(shù)達(dá)到一個(gè)上限，才確認(rèn)哈希表已滿，并執(zhí)行rehash操作。如下圖所示(圖片來源[5])：
cuckoo_preview
我們不禁要問發(fā)生哈希碰撞之前的空間利用率是多少呢?不幸地告訴你，一維數(shù)組的哈希表上跟其它哈希函數(shù)沒什么區(qū)別，也就50%而已。但如果是二維的呢?
一個(gè)改進(jìn)的哈希表如下圖所示，每個(gè)桶(bucket)有4路槽位(slot)。當(dāng)哈希函數(shù)映射到同一個(gè)bucket中，在其它三路slot未被填滿之前，是不會(huì)有元素被踢的，這大大緩沖了碰撞的幾率。筆者自己的簡單實(shí)現(xiàn)上測過，采用二維哈希表(4路slot)大約80%的占用率(CMU論文數(shù)據(jù)據(jù)說達(dá)到90%以上，應(yīng)該是擴(kuò)大了slot關(guān)聯(lián)數(shù)目所致)。
cuckoo hashing
Cuckoo Filter設(shè)計(jì)與實(shí)現(xiàn)
cuckoo hashing的原理介紹完了，下面就來演示一下筆者自己實(shí)現(xiàn)的一個(gè)cuckoo filter應(yīng)用，簡單易用為主，不到500行C代碼。應(yīng)用場景是這樣的：假設(shè)有一段文本數(shù)據(jù)，我們把它通過cuckoo filter導(dǎo)入到一個(gè)虛擬的flash中，再把它導(dǎo)出到另一個(gè)文本文件中。flash存儲(chǔ)的單元頁面是一個(gè)log_entry，里面包含了一對key/value，value就是文本數(shù)據(jù)，key就是這段大小的數(shù)據(jù)的SHA1值(照理說SHA1是可以通過數(shù)據(jù)源生成，沒必要存儲(chǔ)到flash，但這里主要為了測試而故意設(shè)計(jì)的，萬一key和value之間沒有推導(dǎo)關(guān)系呢)。
#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];
};
順便說明一下DAT_LEN設(shè)置，之前我們設(shè)計(jì)了一個(gè)虛擬flash(用malloc模擬出來)，由于flash的單位是按頁大小SECTOR_SIZE讀寫，這里假設(shè)每個(gè)log_entry正好一個(gè)頁大小，當(dāng)然可以根據(jù)實(shí)際情況調(diào)整。
以上是flash的存儲(chǔ)結(jié)構(gòu)，至于哈希表里的slot有三個(gè)成員tag，status和offset，分別是哈希值，狀態(tài)值和在flash的偏移位置。其中status有三個(gè)枚舉值：AVAILIBLE，OCCUPIED，DELETED，分別表示這個(gè)slot是空閑的，占用的還是被刪除的。至于tag，按理說應(yīng)該有兩個(gè)哈希值，對應(yīng)兩個(gè)哈希函數(shù)，但其中一個(gè)已經(jīng)對應(yīng)bucket的位置上了，所以我們只要保存另一個(gè)備用bucket的位置就行了，這樣萬一被踢，只要用這個(gè)tag就可以找到它的另一個(gè)安身之所。
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 */
};乍看之下size有點(diǎn)大是嗎?沒關(guān)系，你也可以根據(jù)情況調(diào)整數(shù)據(jù)類型大小，比如uint16_t，這里僅僅為了測試正確性。
至于哈希表以及bucket和slot的創(chuàng)建見初始化代碼。buckets是一個(gè)二級指針，每個(gè)bucket指向4個(gè)slot大小的緩存，即4路slot，那么bucket_num也就是slot_num的1/4。這里我們故意把slot_num調(diào)小了點(diǎn)，為的是測試rehash的發(fā)生。
#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];
}
}
下面是哈希函數(shù)的設(shè)計(jì)，這里有兩個(gè)，前面提到既然key是20字節(jié)的SHA1值，我們就可以分別是對key的低32位和高32位進(jìn)行位運(yùn)算，只要bucket_num滿足2的冪次方，我們就可以將key的一部分同bucket_num – 1相與，就可以定位到相應(yīng)的bucket位置上，注意bucket_num隨著rehash而增大，哈希函數(shù)簡單的好處是求哈希值十分快。
#define cuckoo_hash_lsb(key, count) (((size_t *)(key))[0] & (count - 1))
#define cuckoo_hash_msb(key, count) (((size_t *)(key))[1] & (count - 1))
終于要講解cuckoo filter最重要的三個(gè)操作了——查詢、插入還有刪除。查詢操作是簡單的，我們對傳進(jìn)來的參數(shù)key進(jìn)行兩次哈希求值tag[0]和tag[1]，并先用tag[0]定位到bucket的位置，從4路slot中再去對比tag[1]。只有比中了tag后，由于只是key的一部分，我們再去從flash中驗(yàn)證完整的key，并把數(shù)據(jù)在flash中的偏移值read_addr輸出返回。相應(yīng)的，如果bucket[tag[0]]的4路slot都沒有比中，我們再去bucket[tag[1]]中比對(代碼略)，如果還比不中，可以肯定這個(gè)key不存在。這種設(shè)計(jì)的好處就是減少了不必要的flash讀操作，每次比對的是內(nèi)存中的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->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;
}
}
...
}
接下來先將簡單的刪除操作，之所以簡單是因?yàn)閐elete除了將相應(yīng)slot的狀態(tài)值設(shè)置一下之外，其實(shí)什么都沒有干，也就是說它不會(huì)真正到flash里面去把數(shù)據(jù)清除掉。為什么?很簡單，沒有必要。還有一個(gè)原因，flash的寫操作之前需要擦除整個(gè)頁面，這種擦除是會(huì)折壽的，所以很多flash支持隨機(jī)讀，但必須保持順序?qū)憽?/p>
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;
}
...
}
了解了flash的讀寫特性，你就知道為啥插入操作在flash層面要設(shè)計(jì)成append。不過我們這里不討論過多flash細(xì)節(jié)，哈希表層面的插入邏輯其實(shí)跟查詢差不多，我就不貼代碼了。這里要貼的是如何判斷并處理碰撞，其實(shí)這里也沒啥玄機(jī)，就是用old_tag和old_offset保存一下臨時(shí)變量，以便一個(gè)元素被踢出去之后還能找到備用的安身之所。但這里會(huì)有一個(gè)判斷，每次踢人都會(huì)計(jì)數(shù)，當(dāng)alt_cnt大于512時(shí)候表示哈希表真的快滿了，這時(shí)候需要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;
}
rehash的邏輯也很簡單，無非就是把哈希表中的buckets和slots重新realloc一下，空間擴(kuò)展一倍，然后再從flash中的key重新插入到新的哈希表里去。這里有個(gè)陷阱要注意，千萬不能有相同的key混進(jìn)來!雖然cuckoo hashing不像開鏈法那樣會(huì)退化成O(n)，但由于每個(gè)元素有兩個(gè)哈希值，而且每次計(jì)算的哈希值隨著哈希表rehash的規(guī)模而不同，相同的key并不能立即檢測到?jīng)_突，但當(dāng)相同的key達(dá)到一定規(guī)模后，噩夢就開始了，由于rehash里面有插入操作，一旦在這里觸發(fā)碰撞，又會(huì)觸發(fā)rehash，這時(shí)就是一個(gè)rehash不斷遞歸的過程，由于其中老的內(nèi)存沒釋放，新的內(nèi)存不斷重新分配，整個(gè)程序就如同陷入DoS攻擊一般癱瘓了。所以每次插入操作前一定要判斷一下key是否已經(jīng)存在過，并且對rehash里的插入使用碰撞斷言防止此類情況發(fā)生。筆者在測試中不幸中了這樣的彩蛋，調(diào)試了大半天才搞清楚原因，搞IT的同學(xué)們記住一定要防小人啊......
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 < 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;
}
...
}
到此為止代碼的邏輯還是比較簡單，使用效果如何呢?我來幫你找個(gè)大文件unqlite.c[6]測試一下，這是一個(gè)嵌入式數(shù)據(jù)庫源代碼，共59959行代碼。作為需要導(dǎo)入的文件，編譯我們的cuckoo filter，然后執(zhí)行：
./cuckoo_db unqlite.c output.c
你會(huì)發(fā)現(xiàn)生成output.c正好也是59959行代碼，一分不差，probably yes終于變成了definitely yes。同時(shí)也可以看到，cuckoo filter真的很快!如果你想看hashing的整個(gè)過程，可以參照README[7]里把調(diào)試宏打開。最后，歡迎給這個(gè)小玩意[8]提交PR!
參考資料
[1]bloom filter：https://en.wikipedia.org/wiki/Bloom_filter
[2]來源wikipedia：https://en.wikipedia.org/wiki/Bloom_filter
[3]CMU論文：https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
[4]github地址：https://github.com/begeekmyfriend/CuckooFilter
[5]布谷鳥解決碰撞沖突： http://codecapsule.com/2013/07/20/cuckoo-hashing/
[6]unqlite.c：https://github.com/unqlite/unqlite/blob/master/unqlite.c
[7]README：https://github.com/begeekmyfriend/CuckooFilter/blob/master/README.md
[8]https://github.com/begeekmyfriend/CuckooFilter
Cuckoo Filter論文：https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
Cuckoo Filter PPT：https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pptx
文章標(biāo)題：作為一名后臺(tái)開發(fā)人員，你必須知道的兩種過濾器
地址分享：http://fisionsoft.com.cn/article/dhsejgg.html
