轉(zhuǎn)載請(qǐng)聲明出處哦~，本篇文章發(fā)布于luozhiyun的博客： https://www.luozhiyun.com/archives/453

介紹

在我們工作中，如果遇到如網(wǎng)頁(yè) URL 去重、垃圾郵件識(shí)別、大集合中重復(fù)元素的判斷一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。如果通過(guò)性能最好的Hash表來(lái)進(jìn)行判斷，那么隨著集合中元素的增加，我們需要的存儲(chǔ)空間也會(huì)呈現(xiàn)線(xiàn)性增長(zhǎng)，最終達(dá)到瓶頸。

所以很多時(shí)候會(huì)選擇使用布隆過(guò)濾器來(lái)做這件事。布隆過(guò)濾器通過(guò)一個(gè)固定大小的二進(jìn)制向量或者位圖（bitmap），然后通過(guò)映射函數(shù)來(lái)將存儲(chǔ)到 bitmap 中的鍵值進(jìn)行映射大大減少了空間成本，布隆過(guò)濾器存儲(chǔ)空間和插入/查詢(xún)時(shí)間都是常數(shù) O(K)。但是隨著存入的元素?cái)?shù)量增加，布隆過(guò)濾器誤算率會(huì)隨之增加，并且也不能刪除元素。

想要體驗(yàn)布隆過(guò)濾器的插入步驟的可以看看這里： https://www.jasondavies.com/bloomfilter/

于是布谷鳥(niǎo)過(guò)濾器(Cuckoo filter)華麗降世了。在論文《Cuckoo Filter: Practically Better Than Bloom》中直接說(shuō)到布隆過(guò)濾器的缺點(diǎn)：

A limitation of standard Bloom filters is that one cannot remove existing items without rebuilding the entire filter.

論文中也提到了布谷鳥(niǎo)過(guò)濾器4大優(yōu)點(diǎn)：

• 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%.

翻譯如下：

1. 支持動(dòng)態(tài)的新增和刪除元素；
2. 提供了比傳統(tǒng)布隆過(guò)濾器更高的查找性能，即使在接近滿(mǎn)的情況下（比如空間利用率達(dá)到 95% 的時(shí)候）；
3. 更容易實(shí)現(xiàn)；
4. 如果要求錯(cuò)誤率小于3%，那么在許多實(shí)際應(yīng)用中，它比布隆過(guò)濾器占用的空間更小

實(shí)現(xiàn)原理

簡(jiǎn)單工作原理

可以簡(jiǎn)單的把布谷鳥(niǎo)過(guò)濾器里面有兩個(gè) hash 表T1、T2，兩個(gè) hash 表對(duì)應(yīng)兩個(gè) hash 函數(shù)H1、H2。

具體的插入步驟如下：

• 當(dāng)一個(gè)不存在的元素插入的時(shí)候，會(huì)先根據(jù) H1 計(jì)算出其在 T1 表的位置，如果該位置為空則可以放進(jìn)去。
• 如果該位置不為空，則根據(jù) H2 計(jì)算出其在 T2 表的位置，如果該位置為空則可以放進(jìn)去。
• 如果T1 表和 T2 表的位置元素都不為空，那么就隨機(jī)的選擇一個(gè) hash 表將其元素踢出。
• 被踢出的元素會(huì)循環(huán)的去找自己的另一個(gè)位置，如果被暫了也會(huì)隨機(jī)選擇一個(gè)將其踢出，被踢出的元素又會(huì)循環(huán)找位置；
• 如果出現(xiàn)循環(huán)踢出導(dǎo)致放不進(jìn)元素的情況，那么會(huì)設(shè)置一個(gè)閾值，超出了某個(gè)閾值，就認(rèn)為這個(gè) hash 表已經(jīng)幾乎滿(mǎn)了，這時(shí)候就需要對(duì)它進(jìn)行擴(kuò)容，重新放置所有元素。

下面舉一個(gè)例子來(lái)說(shuō)明：

如果想要插入一個(gè)元素Z到過(guò)濾器里：

• 首先會(huì)將Z進(jìn)行 hash 計(jì)算，發(fā)現(xiàn) T1 和 T2 對(duì)應(yīng)的槽位1和槽位2都已經(jīng)被占了；
• 隨機(jī)將 T1 中的槽位1中的元素 X 踢出，X 的 T2 對(duì)應(yīng)的槽位4已經(jīng)被元素 3 占了；
• 將 T2 中的槽位4中的元素 3 踢出，元素 3 在 hash 計(jì)算之后發(fā)現(xiàn) T1 的槽位6是空的，那么將元素3放入到 T1 的槽位6中。

當(dāng) Z 插入完畢之后如下：

布谷鳥(niǎo)過(guò)濾器

布谷鳥(niǎo)過(guò)濾器和上面的實(shí)現(xiàn)原理結(jié)構(gòu)是差不多的，不同的是上面的數(shù)組結(jié)構(gòu)會(huì)存儲(chǔ)整個(gè)元素，而布谷鳥(niǎo)過(guò)濾器中只會(huì)存儲(chǔ)元素的幾個(gè) bit ，稱(chēng)作指紋信息。這里是犧牲了數(shù)據(jù)的精確性換取了空間效率。

上面的實(shí)現(xiàn)方案中，hash 表中每個(gè)槽位只能存放一個(gè)元素，空間利用率只有50%，而在布谷鳥(niǎo)過(guò)濾器中每個(gè)槽位可以存放多個(gè)元素，從一維變成了二維。論文中表示：

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.

也就是當(dāng)有兩個(gè) hash 函數(shù)的時(shí)候，使用一維數(shù)組空間利用率只有50%，當(dāng)每個(gè)槽位可以存放2，4，8個(gè)元素的時(shí)候，空間利用率就會(huì)飆升到 84%，95%，98%。

如下圖，表示的是一個(gè)二維數(shù)組，每個(gè)槽位可以存放 4 個(gè)元素，和上面的實(shí)現(xiàn)有所不同的是，沒(méi)有采用兩個(gè)數(shù)組來(lái)存放，而是只用了一個(gè)：

說(shuō)完了數(shù)據(jù)結(jié)構(gòu)的改變，下面再說(shuō)說(shuō)位置計(jì)算的改變。

我們?cè)谏厦婧?jiǎn)單實(shí)現(xiàn)的位置計(jì)算公式是這樣做的：

p1 = hash1(x) % 數(shù)組長(zhǎng)度
p2 = hash2(x) % 數(shù)組長(zhǎng)度

而布谷鳥(niǎo)過(guò)濾器計(jì)算位置公式可以在論文中看到是這樣：

f = fingerprint(x);
i1 = hash(x);
i2 = i1 ⊕ hash( f);

我們可以看到在計(jì)算位置 i2 的時(shí)候是通過(guò) i1 和元素 X 對(duì)應(yīng)的指紋信息取異或計(jì)算出來(lái)。指紋信息在上面已經(jīng)解釋過(guò)了，是元素 X 的幾個(gè) bit ，犧牲了一定精度，但是換取了空間。

那么這里為什么需要用到異或呢？因?yàn)檫@樣可以用到異或的自反性： A ⊕ B ⊕ B = A ，這樣就不需要知道當(dāng)前的位置是 i1 還是 i2，只需要將當(dāng)前的位置和 hash(f) 進(jìn)行異或計(jì)算就可以得到另一個(gè)位置。

這里有個(gè)細(xì)節(jié)需要注意的是，計(jì)算 i2 的時(shí)候是需要先將元素 X 的 fingerprint 進(jìn)行 hash ，然后才取異或，論文也說(shuō)明了：

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.

如果直接進(jìn)行異或處理，那么很可能 i1 和 i2 的位置相隔很近，尤其是在比較小的 hash 表中，這樣無(wú)形之中增加了碰撞的概率。

除此之外還有一個(gè)約束條件是布谷鳥(niǎo)過(guò)濾器強(qiáng)制數(shù)組的長(zhǎng)度必須是 2 的指數(shù)，所以在布谷鳥(niǎo)過(guò)濾器中不需要對(duì)數(shù)組的長(zhǎng)度取模，取而代之的是取 hash 值的最后 n 位。

如一個(gè)布谷鳥(niǎo)過(guò)濾器中數(shù)組的長(zhǎng)度2^8即256，那么取 hash 值的最后 n 位即： hash & 255 這樣就可以得到最終的位置信息。如下最后得到位置信息是 23 ：

代碼實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)

const bucketSize = 4
type fingerprint byte
// 二維數(shù)組，大小是4
type bucket [bucketSize]fingerprint

type Filter struct {
	// 一維數(shù)組
	buckets []bucket
	// Filter 中已插入的元素
	count  uint
	// 數(shù)組buckets長(zhǎng)度中對(duì)應(yīng)二進(jìn)制包含0的個(gè)數(shù)
	bucketPow uint
}

在這里我們假定一個(gè)指紋 fingerprint 占用的字節(jié)數(shù)是 1byte ，每個(gè)位置有 4 個(gè)座位。

初始化

var (
	altHash = [256]uint{}
	masks = [65]uint{}
)

func init() {
	for i := 0; i < 256; i++ {
  // 用于緩存 256 個(gè)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
	}
}

這個(gè) init 函數(shù)會(huì)緩存初始化兩個(gè)全局變量 altHash 和 masks。因?yàn)?fingerprint 長(zhǎng)度是 1byte ，所以在初始化 altHash 的時(shí)候使用一個(gè) 256 大小的數(shù)組取緩存對(duì)應(yīng)的 hash 信息，避免每次都需要重新計(jì)算；masks 是用來(lái)取 hash 值的最后 n 位，稍后會(huì)用到。

我們會(huì)使用一個(gè) NewFilter 函數(shù)，通過(guò)傳入過(guò)濾器可容納大小來(lái)獲取過(guò)濾器 Filter：

func NewFilter(capacity uint) *Filter {
 // 計(jì)算 buckets 數(shù)組大小
	capacity = getNextPow2(uint64(capacity)) / bucketSize
	if capacity == 0 {
		capacity = 1
	}
	buckets := make([]bucket, capacity)
	return &Filter{
		buckets: buckets,
		count:  0,
  // 獲取 buckets 數(shù)組大小的二進(jìn)制中以 0 結(jié)尾的個(gè)數(shù)
		bucketPow: uint(bits.TrailingZeros(capacity)),
	}
}

NewFilter 函數(shù)會(huì)通過(guò) getNextPow2 將 capacity 調(diào)整到 2 的指數(shù)倍，如果傳入的 capacity 是 9 ，那么調(diào)用 getNextPow2 后會(huì)返回 16；然后計(jì)算好 buckets 數(shù)組長(zhǎng)度，實(shí)例化 Filter 返回；bucketPow 返回的是二進(jìn)制中以 0 結(jié)尾的個(gè)數(shù)，因?yàn)?capacity 是 2 的指數(shù)倍，所以 bucketPow 是 capacity 二進(jìn)制的位數(shù)減 1。

插入元素

func (cf *Filter) Insert(data []byte) bool {
	// 獲取 data 的 fingerprint 以及 位置 i1
	i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
	// 將 fingerprint 插入到 Filter 的 buckets 數(shù)組中
	if cf.insert(fp, i1) {
		return true
	}
	// 獲取位置 i2
	i2 := getAltIndex(fp, i1, cf.bucketPow)
	// 將 fingerprint 插入到 Filter 的 buckets 數(shù)組中
	if cf.insert(fp, i2) {
		return true
	}
	// 插入失敗，那么進(jìn)行循環(huán)插入踢出元素
	return cf.reinsert(fp, randi(i1, i2))
}

func (cf *Filter) insert(fp fingerprint, i uint) bool {
 // 獲取 buckets 中的槽位進(jìn)行插入
	if cf.buckets[i].insert(fp) {
  // Filter 中元素個(gè)數(shù)+1
		cf.count++
		return true
	}
	return false
}

func (b *bucket) insert(fp fingerprint) bool {
 // 遍歷槽位的 4 個(gè)元素，如果為空則插入
	for i, tfp := range b {
		if tfp == nullFp {
			b[i] = fp
			return true
		}
	}
	return false
}

• getIndexAndFingerprint 函數(shù)會(huì)獲取 data 的指紋 fingerprint，以及位置 i1；
• 然后調(diào)用 insert 插入到 Filter 的 buckets 數(shù)組中，如果 buckets 數(shù)組中對(duì)應(yīng)的槽位 i1 的 4 個(gè)元素已經(jīng)滿(mǎn)了，那么嘗試獲取位置 i2 ，并將元素嘗試插入到 buckets 數(shù)組中對(duì)應(yīng)的槽位 i2 中；
• 對(duì)應(yīng)的槽位 i2 也滿(mǎn)了，那么 調(diào)用 reinsert 方法隨機(jī)獲取槽位 i1、i2 中的某個(gè)位置進(jìn)行搶占，然后將老元素踢出并循環(huán)重復(fù)插入。

下面看看 getIndexAndFingerprint 是如何獲取 fingerprint 以及槽位 i1：

func getIndexAndFingerprint(data []byte, bucketPow uint) (uint, fingerprint) {
 // 將 data 進(jìn)行hash
	hash := metro.Hash64(data, 1337)
 // 取 hash 的指紋信息
	fp := getFingerprint(hash)
	// 取 hash 高32位，對(duì) hash 的高32位進(jìn)行取與獲取槽位 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 中對(duì) data 進(jìn)行 hash 完后會(huì)對(duì)其結(jié)果取模獲取指紋信息，然后再取 hash 值的高 32 位進(jìn)行取與，獲取槽位 i1。masks 在初始化的時(shí)候已經(jīng)看過(guò)了， masks[bucketPow] 獲取的二進(jìn)制結(jié)果全是 1 ，用來(lái)取 hash 的低位的值。

假如初始化傳入的 capacity 是1024，那么計(jì)算到 bucketPow 是 8，對(duì)應(yīng)取到 masks[8] = (1 << 8) - 1 結(jié)果是 255 ，二進(jìn)制是 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 中獲取槽位是通過(guò)使用 altHash 來(lái)獲取指紋信息的 hash 值，然后取異或后返回槽位值。需要注意的是，這里由于異或的特性，所以傳入的不管是槽位 i1，還是槽位 i2 都可以返回對(duì)應(yīng)的另一個(gè)槽位。

下面看看循環(huán)踢出插入 reinsert：

const maxCuckooCount = 500

func (cf *Filter) reinsert(fp fingerprint, i uint) bool {
 // 默認(rèn)循環(huán) 500 次
	for k := 0; k < maxCuckooCount; k++ {
  // 隨機(jī)從槽位中選取一個(gè)元素
		j := rand.Intn(bucketSize)
		oldfp := fp
  // 獲取槽位中的值 
		fp = cf.buckets[i][j]
  // 將當(dāng)前循環(huán)的值插入
		cf.buckets[i][j] = oldfp

		// 獲取另一個(gè)槽位
		i = getAltIndex(fp, i, cf.bucketPow)
		if cf.insert(fp, i) {
			return true
		}
	}
	return false
}

這里會(huì)最大循環(huán) 500 次獲取槽位信息。因?yàn)槊總€(gè)槽位最多可以存放 4 個(gè)元素，所以使用 rand 隨機(jī)從 4 個(gè)位置中取一個(gè)元素踢出，然后將當(dāng)次循環(huán)的元素插入，再獲取被踢出元素的另一個(gè)槽位信息，再調(diào)用 insert 進(jìn)行插入。

上圖展示了元素 X 在插入到 hash 表的時(shí)候，hash 兩次發(fā)現(xiàn)對(duì)應(yīng)的槽位 0 和 3 都已經(jīng)滿(mǎn)了，那么隨機(jī)搶占了槽位 3 其中一個(gè)元素，被搶占的元素重新 hash 之后插入到槽位 5 的第三個(gè)位置上。

查詢(xún)數(shù)據(jù)

查詢(xún)數(shù)據(jù)的時(shí)候，就是看看對(duì)應(yīng)的位置上有沒(méi)有對(duì)應(yīng)的指紋信息：

func (cf *Filter) Lookup(data []byte) bool {
 // 獲取槽位 i1 以及指紋信息
	i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
 // 遍歷槽位中 4 個(gè)位置，查看有沒(méi)有相同元素
	if cf.buckets[i1].getFingerprintIndex(fp) > -1 {
		return true
	}
 // 獲取另一個(gè)槽位 i2
	i2 := getAltIndex(fp, i1, cf.bucketPow)
 // 遍歷槽位 i2 中 4 個(gè)位置，查看有沒(méi)有相同元素
	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
}

刪除數(shù)據(jù)

刪除數(shù)據(jù)的時(shí)候，也只是抹掉該槽位上的指紋信息：

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個(gè)元素，嘗試刪除指紋信息
	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
}

缺點(diǎn)

實(shí)現(xiàn)完布谷鳥(niǎo)過(guò)濾器后，我們不妨想一下，如果布谷鳥(niǎo)過(guò)濾器對(duì)同一個(gè)元素進(jìn)行多次連續(xù)的插入會(huì)怎樣？

那么這個(gè)元素會(huì)霸占兩個(gè)槽位上的所有位置，最后在插入第 9 個(gè)相同元素的時(shí)候，會(huì)一直循環(huán)擠兌，直到最大循環(huán)次數(shù)，然后返回一個(gè) false：

如果插入之前做一次檢查能不能解決問(wèn)題呢？這樣確實(shí)不會(huì)出現(xiàn)循環(huán)擠兌的情況，但是會(huì)出現(xiàn)一定概率的誤判情況。

由上面的實(shí)現(xiàn)我們可以知道，在每個(gè)位置里設(shè)置的指紋信息是 1byte，256 種可能，如果兩個(gè)元素的 hash 位置相同，指紋相同，那么這個(gè)插入檢查會(huì)認(rèn)為它們是相等的導(dǎo)致認(rèn)為元素已存在。

事實(shí)上，我們可以通過(guò)調(diào)整指紋信息的保存量來(lái)降低誤判情況，如在上面的實(shí)現(xiàn)中，指紋信息是 1byte 保存8位信息誤判概率是0.03，當(dāng)指紋信息增加到 2bytes 保存16位信息誤判概率會(huì)降低至 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

到此這篇關(guān)于Go語(yǔ)言實(shí)現(xiàn)布谷鳥(niǎo)過(guò)濾器的方法的文章就介紹到這了,更多相關(guān)Go 布谷鳥(niǎo)過(guò)濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！