Go語言實現佈谷鳥過濾器的方法
轉載請聲明出處哦~，本篇文章發佈於luozhiyun的博客： https://www.luozhiyun.com/archives/453
介紹
在我們工作中，如果遇到如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷一般想到的是將集合中所有元素保存起來，然後通過比較確定。如果通過性能最好的Hash表來進行判斷，那麼隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。
所以很多時候會選擇使用佈隆過濾器來做這件事。佈隆過濾器通過一個固定大小的二進制向量或者位圖（bitmap），然後通過映射函數來將存儲到 bitmap 中的鍵值進行映射大大減少瞭空間成本，佈隆過濾器存儲空間和插入/查詢時間都是常數 O(K)。但是隨著存入的元素數量增加，佈隆過濾器誤算率會隨之增加，並且也不能刪除元素。
想要體驗佈隆過濾器的插入步驟的可以看看這裡： https://www.jasondavies.com/bloomfilter/
於是佈谷鳥過濾器(Cuckoo filter)華麗降世瞭。在論文《Cuckoo Filter: Practically Better Than Bloom》中直接說到佈隆過濾器的缺點：
A limitation of standard Bloom filters is that one cannot remove existing items without rebuilding the entire filter.
論文中也提到瞭佈谷鳥過濾器4大優點：
- It supports adding and removing items dynamically;
- It provides higher lookup performance than traditional Bloom filters, even when close to full (e.g., 95% space utilized);
- It is easier to implement than alternatives such as the quotient filter; and
- It uses less space than Bloom filters in many practical applications, if the target false positive rate is less than 3%.
翻譯如下：
- 支持動態的新增和刪除元素；
- 提供瞭比傳統佈隆過濾器更高的查找性能，即使在接近滿的情況下（比如空間利用率達到 95% 的時候）；
- 更容易實現；
- 如果要求錯誤率小於3%，那麼在許多實際應用中，它比佈隆過濾器占用的空間更小
實現原理
簡單工作原理
可以簡單的把佈谷鳥過濾器裡面有兩個 hash 表T1、T2，兩個 hash 表對應兩個 hash 函數H1、H2。
具體的插入步驟如下：
- 當一個不存在的元素插入的時候，會先根據 H1 計算出其在 T1 表的位置，如果該位置為空則可以放進去。
- 如果該位置不為空，則根據 H2 計算出其在 T2 表的位置，如果該位置為空則可以放進去。
- 如果T1 表和 T2 表的位置元素都不為空，那麼就隨機的選擇一個 hash 表將其元素踢出。
- 被踢出的元素會循環的去找自己的另一個位置，如果被暫瞭也會隨機選擇一個將其踢出，被踢出的元素又會循環找位置；
- 如果出現循環踢出導致放不進元素的情況，那麼會設置一個閾值，超出瞭某個閾值，就認為這個 hash 表已經幾乎滿瞭，這時候就需要對它進行擴容，重新放置所有元素。
下面舉一個例子來說明：
如果想要插入一個元素Z到過濾器裡：
- 首先會將Z進行 hash 計算，發現 T1 和 T2 對應的槽位1和槽位2都已經被占瞭；
- 隨機將 T1 中的槽位1中的元素 X 踢出，X 的 T2 對應的槽位4已經被元素 3 占瞭；
- 將 T2 中的槽位4中的元素 3 踢出，元素 3 在 hash 計算之後發現 T1 的槽位6是空的，那麼將元素3放入到 T1 的槽位6中。
當 Z 插入完畢之後如下：
佈谷鳥過濾器
佈谷鳥過濾器和上面的實現原理結構是差不多的，不同的是上面的數組結構會存儲整個元素，而佈谷鳥過濾器中隻會存儲元素的幾個 bit ，稱作指紋信息。這裡是犧牲瞭數據的精確性換取瞭空間效率。
上面的實現方案中，hash 表中每個槽位隻能存放一個元素，空間利用率隻有50%，而在佈谷鳥過濾器中每個槽位可以存放多個元素，從一維變成瞭二維。論文中表示：
With k = 2 hash functions, the load factor α is 50% when the bucket size b = 1 (i.e., the hash table is directly mapped), but increases to 84%, 95% or 98% respectively using bucket size b = 2, 4 or 8.
也就是當有兩個 hash 函數的時候，使用一維數組空間利用率隻有50%，當每個槽位可以存放2，4，8個元素的時候，空間利用率就會飆升到 84%，95%，98%。
如下圖，表示的是一個二維數組，每個槽位可以存放 4 個元素，和上面的實現有所不同的是，沒有采用兩個數組來存放，而是隻用瞭一個：
說完瞭數據結構的改變，下面再說說位置計算的改變。
我們在上面簡單實現的位置計算公式是這樣做的：
p1 = hash1(x) % 數組長度 p2 = hash2(x) % 數組長度
而佈谷鳥過濾器計算位置公式可以在論文中看到是這樣：
f = fingerprint(x); i1 = hash(x); i2 = i1 ⊕ hash( f);
我們可以看到在計算位置 i2 的時候是通過 i1 和元素 X 對應的指紋信息取異或計算出來。指紋信息在上面已經解釋過瞭，是元素 X 的幾個 bit ，犧牲瞭一定精度，但是換取瞭空間。
那麼這裡為什麼需要用到異或呢？因為這樣可以用到異或的自反性： A ⊕ B ⊕ B = A ，這樣就不需要知道當前的位置是 i1 還是 i2，隻需要將當前的位置和 hash(f) 進行異或計算就可以得到另一個位置。
這裡有個細節需要註意的是，計算 i2 的時候是需要先將元素 X 的 fingerprint 進行 hash ，然後才取異或，論文也說明瞭：
If the alternate location were calculated by “i⊕fingerprint” without hashing the fingerprint, the items kicked out from nearby buckets would land close to each other in the table, if the size of the fingerprint is small compared to the table size.
如果直接進行異或處理，那麼很可能 i1 和 i2 的位置相隔很近，尤其是在比較小的 hash 表中，這樣無形之中增加瞭碰撞的概率。
除此之外還有一個約束條件是佈谷鳥過濾器強制數組的長度必須是 2 的指數，所以在佈谷鳥過濾器中不需要對數組的長度取模，取而代之的是取 hash 值的最後 n 位。
如一個佈谷鳥過濾器中數組的長度2^8即256，那麼取 hash 值的最後 n 位即： hash & 255 這樣就可以得到最終的位置信息。如下最後得到位置信息是 23 ：
代碼實現
數據結構
const bucketSize = 4
type fingerprint byte
// 二維數組，大小是4
type bucket [bucketSize]fingerprint
type Filter struct {
// 一維數組
buckets []bucket
// Filter 中已插入的元素
count uint
// 數組buckets長度中對應二進制包含0的個數
bucketPow uint
}
在這裡我們假定一個指紋 fingerprint 占用的字節數是 1byte ，每個位置有 4 個座位。
初始化
var (
altHash = [256]uint{}
masks = [65]uint{}
)
func init() {
for i := 0; i < 256; i++ {
// 用於緩存 256 個fingerprint的hash信息
altHash[i] = (uint(metro.Hash64([]byte{byte(i)}, 1337)))
}
for i := uint(0); i <= 64; i++ {
// 取 hash 值的最後 n 位
masks[i] = (1 << i) - 1
}
}
這個 init 函數會緩存初始化兩個全局變量 altHash 和 masks。因為 fingerprint 長度是 1byte ，所以在初始化 altHash 的時候使用一個 256 大小的數組取緩存對應的 hash 信息，避免每次都需要重新計算；masks 是用來取 hash 值的最後 n 位，稍後會用到。
我們會使用一個 NewFilter 函數，通過傳入過濾器可容納大小來獲取過濾器 Filter：
func NewFilter(capacity uint) *Filter {
// 計算 buckets 數組大小
capacity = getNextPow2(uint64(capacity)) / bucketSize
if capacity == 0 {
capacity = 1
}
buckets := make([]bucket, capacity)
return &Filter{
buckets: buckets,
count: 0,
// 獲取 buckets 數組大小的二進制中以 0 結尾的個數
bucketPow: uint(bits.TrailingZeros(capacity)),
}
}
NewFilter 函數會通過 getNextPow2 將 capacity 調整到 2 的指數倍，如果傳入的 capacity 是 9 ，那麼調用 getNextPow2 後會返回 16；然後計算好 buckets 數組長度，實例化 Filter 返回；bucketPow 返回的是二進制中以 0 結尾的個數，因為 capacity 是 2 的指數倍，所以 bucketPow 是 capacity 二進制的位數減 1。
插入元素
func (cf *Filter) Insert(data []byte) bool {
// 獲取 data 的 fingerprint 以及 位置 i1
i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
// 將 fingerprint 插入到 Filter 的 buckets 數組中
if cf.insert(fp, i1) {
return true
}
// 獲取位置 i2
i2 := getAltIndex(fp, i1, cf.bucketPow)
// 將 fingerprint 插入到 Filter 的 buckets 數組中
if cf.insert(fp, i2) {
return true
}
// 插入失敗，那麼進行循環插入踢出元素
return cf.reinsert(fp, randi(i1, i2))
}
func (cf *Filter) insert(fp fingerprint, i uint) bool {
// 獲取 buckets 中的槽位進行插入
if cf.buckets[i].insert(fp) {
// Filter 中元素個數+1
cf.count++
return true
}
return false
}
func (b *bucket) insert(fp fingerprint) bool {
// 遍歷槽位的 4 個元素，如果為空則插入
for i, tfp := range b {
if tfp == nullFp {
b[i] = fp
return true
}
}
return false
}
- getIndexAndFingerprint 函數會獲取 data 的指紋 fingerprint，以及位置 i1；
- 然後調用 insert 插入到 Filter 的 buckets 數組中，如果 buckets 數組中對應的槽位 i1 的 4 個元素已經滿瞭，那麼嘗試獲取位置 i2 ，並將元素嘗試插入到 buckets 數組中對應的槽位 i2 中；
- 對應的槽位 i2 也滿瞭，那麼 調用 reinsert 方法隨機獲取槽位 i1、i2 中的某個位置進行搶占，然後將老元素踢出並循環重復插入。
下面看看 getIndexAndFingerprint 是如何獲取 fingerprint 以及槽位 i1：
func getIndexAndFingerprint(data []byte, bucketPow uint) (uint, fingerprint) {
// 將 data 進行hash
hash := metro.Hash64(data, 1337)
// 取 hash 的指紋信息
fp := getFingerprint(hash)
// 取 hash 高32位，對 hash 的高32位進行取與獲取槽位 i1
i1 := uint(hash>>32) & masks[bucketPow]
return i1, fingerprint(fp)
}
// 取 hash 的指紋信息
func getFingerprint(hash uint64) byte {
fp := byte(hash%255 + 1)
return fp
}
getIndexAndFingerprint 中對 data 進行 hash 完後會對其結果取模獲取指紋信息，然後再取 hash 值的高 32 位進行取與，獲取槽位 i1。masks 在初始化的時候已經看過瞭， masks[bucketPow] 獲取的二進制結果全是 1 ，用來取 hash 的低位的值。
假如初始化傳入的 capacity 是1024，那麼計算到 bucketPow 是 8，對應取到 masks[8] = (1 << 8) - 1 結果是 255 ，二進制是 1111，1111 ，和 hash 的高 32 取與 得到最後 buckets 中的槽位 i1 ：
func getAltIndex(fp fingerprint, i uint, bucketPow uint) uint {
mask := masks[bucketPow]
hash := altHash[fp] & mask
return i ^ hash
}
getAltIndex 中獲取槽位是通過使用 altHash 來獲取指紋信息的 hash 值，然後取異或後返回槽位值。需要註意的是，這裡由於異或的特性，所以傳入的不管是槽位 i1，還是槽位 i2 都可以返回對應的另一個槽位。
下面看看循環踢出插入 reinsert：
const maxCuckooCount = 500
func (cf *Filter) reinsert(fp fingerprint, i uint) bool {
// 默認循環 500 次
for k := 0; k < maxCuckooCount; k++ {
// 隨機從槽位中選取一個元素
j := rand.Intn(bucketSize)
oldfp := fp
// 獲取槽位中的值
fp = cf.buckets[i][j]
// 將當前循環的值插入
cf.buckets[i][j] = oldfp
// 獲取另一個槽位
i = getAltIndex(fp, i, cf.bucketPow)
if cf.insert(fp, i) {
return true
}
}
return false
}
這裡會最大循環 500 次獲取槽位信息。因為每個槽位最多可以存放 4 個元素，所以使用 rand 隨機從 4 個位置中取一個元素踢出，然後將當次循環的元素插入，再獲取被踢出元素的另一個槽位信息，再調用 insert 進行插入。
上圖展示瞭元素 X 在插入到 hash 表的時候，hash 兩次發現對應的槽位 0 和 3 都已經滿瞭，那麼隨機搶占瞭槽位 3 其中一個元素，被搶占的元素重新 hash 之後插入到槽位 5 的第三個位置上。
查詢數據
查詢數據的時候，就是看看對應的位置上有沒有對應的指紋信息：
func (cf *Filter) Lookup(data []byte) bool {
// 獲取槽位 i1 以及指紋信息
i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
// 遍歷槽位中 4 個位置，查看有沒有相同元素
if cf.buckets[i1].getFingerprintIndex(fp) > -1 {
return true
}
// 獲取另一個槽位 i2
i2 := getAltIndex(fp, i1, cf.bucketPow)
// 遍歷槽位 i2 中 4 個位置，查看有沒有相同元素
return cf.buckets[i2].getFingerprintIndex(fp) > -1
}
func (b *bucket) getFingerprintIndex(fp fingerprint) int {
for i, tfp := range b {
if tfp == fp {
return i
}
}
return -1
}
刪除數據
刪除數據的時候，也隻是抹掉該槽位上的指紋信息：
func (cf *Filter) Delete(data []byte) bool {
// 獲取槽位 i1 以及指紋信息
i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
// 嘗試刪除指紋信息
if cf.delete(fp, i1) {
return true
}
// 獲取槽位 i2
i2 := getAltIndex(fp, i1, cf.bucketPow)
// 嘗試刪除指紋信息
return cf.delete(fp, i2)
}
func (cf *Filter) delete(fp fingerprint, i uint) bool {
// 遍歷槽位 4個元素，嘗試刪除指紋信息
if cf.buckets[i].delete(fp) {
if cf.count > 0 {
cf.count--
}
return true
}
return false
}
func (b *bucket) delete(fp fingerprint) bool {
for i, tfp := range b {
// 指紋信息相同，將此槽位置空
if tfp == fp {
b[i] = nullFp
return true
}
}
return false
}
缺點
實現完佈谷鳥過濾器後，我們不妨想一下，如果佈谷鳥過濾器對同一個元素進行多次連續的插入會怎樣？
那麼這個元素會霸占兩個槽位上的所有位置，最後在插入第 9 個相同元素的時候，會一直循環擠兌，直到最大循環次數，然後返回一個 false：
如果插入之前做一次檢查能不能解決問題呢？這樣確實不會出現循環擠兌的情況，但是會出現一定概率的誤判情況。
由上面的實現我們可以知道，在每個位置裡設置的指紋信息是 1byte，256 種可能，如果兩個元素的 hash 位置相同，指紋相同，那麼這個插入檢查會認為它們是相等的導致認為元素已存在。
事實上，我們可以通過調整指紋信息的保存量來降低誤判情況，如在上面的實現中，指紋信息是 1byte 保存8位信息誤判概率是0.03，當指紋信息增加到 2bytes 保存16位信息誤判概率會降低至 0.0001。
Reference
Cuckoo Filter: Practically Better Than Bloom https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
Cuckoo Hashing Visualization http://www.lkozma.net/cuckoo_hashing_visualization/
Cuckoo Filter https://github.com/seiflotfy/cuckoofilter
到此這篇關於Go語言實現佈谷鳥過濾器的方法的文章就介紹到這瞭,更多相關Go 佈谷鳥過濾器內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！