布穀鳥過濾器

基本概念

布穀鳥過濾器 是一種節省內存空間的概率數據結構，基於 布穀鳥哈希算法 實現的過濾器，和 布隆過濾器 一樣，用於檢測指定元素是否存在於某個集合中，返回結果語義是 “元素一定不存在” 或 “有較大可能存在”。

和布隆過濾器比較

優點

• 布穀鳥過濾器支持刪除元素，布隆過濾器不支持

• 高負載因子場景下，布穀鳥過濾器查詢效率更高

• 對於存儲數據量較大且期望誤判率較低 (小於 3%) 的場景下，布穀鳥過濾器存儲空間開銷更低

• 布穀鳥過濾器比布隆過濾器更容易實現

缺點

• 布穀鳥過濾器採用一種備用候選桶的方案，候選桶與首選桶可以通過 位置 + 值指紋的哈希 通過 異或計算 得出，這種對應關係要求桶的大小必須是 2 的指數倍數 (如 4, 8, 16, 32...)

• 布隆過濾器插入時計算好哈希直接寫入位即可，而布穀鳥過濾器在計算後可能會出現對應位置上已經存儲了指紋，這時就需要將已存儲的值踢出到候選桶，碰撞概率和插入耗時隨着表元素增多而增大，因此其插入性能低於布隆過濾器

• 布隆過濾器插入重複元素時沒有影響 (可以重複插入)，而布穀鳥過濾器對已存在的值會執行 踢出 操作，因此重複元素的插入存在上限

• 布穀鳥過濾器的刪除並不完美，刪除操作在相同哈希值僅被插入一次時是完美的，如果元素沒有插入就進行刪除，可能會出現誤刪除 (刪除了相同哈希值的其他元素)， 如果元素插入了多次，但是每次刪除操作只刪除一個值，那麼就需要知道元素插入了多少次才能徹底刪除，或者循環刪除直到失敗爲止

PS: 如果只需要保證 一定不存在 語義，那麼刪除時不論是否存在重複元素，直接刪除即可。

布穀鳥哈希算法描述

• 使用兩個哈希函數 H1, H2 和兩個哈希表 T1, T2

• 插入元素 x

• 計算 x 的兩個哈希值 idx1 = H1(x), idx2 = H2(x)

• 如果 T1[idx1], T2[idx2] 有一個爲空，插入 x, 兩者都爲空，隨便選一個插入 x

• 如果 T1[idx1], T2[idx2] 都不爲空，則隨便選擇其中一個 (設爲 y) 將其踢出，插入 x

• 重複上述過程，插入元素 y

• 如果插入時，踢出次數過多，則說明哈希表滿了，進行擴容 (ReHash)，擴容完成後再次插入

• 查詢元素 x

• 讀取 T1[idx1], T2[idx2] 的值，和 x 比較

算法示例

圖 (a) 算法過程描述:

• 插入元素 x

• 將對應桶的元素 y 踢出

• 將元素 y 插入到桶 z

• 將對應桶的元素 z 踢出

• 將元素 z 插入到其他桶中

圖 (b) 算法過程描述:

• 插入元素 x

• 插入失敗，因爲桶已經滿了

• 觸發擴容

僞代碼

按照算法描述，翻譯成僞代碼如下 (不考慮併發情況):

package main

import (
 "math/rand"
 "time"
)

const (
 TSize = 1024 // 假設表的大小爲 1024
)

var (
 T1 = make(map[int]any, TSize) // 哈希表 1
 T2 = make(map[int]any, TSize) // 哈希表 2
)

// 哈希函數 1
// 返回隨機數作爲哈希值
func H1(x any) int {
 rand.Seed(time.Now().UnixNano())
 return rand.Intn(TSize)
}

// 哈希函數 2
// 返回隨機數作爲哈希值
func H2(x any) int {
 rand.Seed(time.Now().UnixNano())
 return rand.Intn(TSize)
}

// 擴容操作，這裏省略具體實現
func ReHash() {
 // do something
}

// 隨機踢出一個元素
// 返回踢出的哈希桶編號以及元素索引
func KicksOut(x any) any {
 // 哈希桶已滿
 if len(T1) == TSize && len(T2) == TSize {
  return nil
 }

 rand.Seed(time.Now().UnixNano())
 n := rand.Intn(2)

 var y any // 被踢出的元素 y

 // 直接利用 Go map 的無序遍歷特性
 // 遍歷時將 [第一個元素] 作爲隨機元素踢出
 if n == 0 {
  // 從 T1 桶隨機選擇一個元素踢出
  for k, v := range T1 {
   // 將 x 插入到 y 的桶 (覆蓋式)
   T1[k] = x
   y = v
   break
  }
 } else {
  // 從 T2 桶隨機選擇一個元素踢出
  for k, v := range T2 {
   // 將 x 插入到 y 的桶 (覆蓋式)
   T2[k] = x
   y = v
   break
  }
 }

 return y
}

// 插入元素
func Insert(x any) bool {
 idx1, idx2 := H1(x), H2(x)

 // 如果 T1 桶對應桶爲空，則插入 T1
 if _, ok := T1[idx1]; !ok {
  T1[idx1] = x
  return true
 }
 // 如果 T2 桶對應桶爲空，則插入 T2
 if _, ok := T2[idx2]; !ok {
  T2[idx2] = x
  return true
 }

 y := KicksOut(x)
 // 哈希桶已滿，進行擴容
 if y == nil {
  ReHash()
 }

 // 插入元素 y
 return Insert(y)
}

不同的版本

一個哈希桶

兩個哈希函數和一個哈希桶

如圖所示，在未發生哈希碰撞之前，哈希桶的利用率只有 50%。

四路哈希桶

兩個哈希函數和四路哈希桶

如圖所示是一個改進的哈希桶，每個桶有 4 個槽位，當哈希函數映射到同一個桶時，其它 3 個槽位如果有空位，那麼就不會有元素被踢出，降低了碰撞概率。

布穀鳥過濾器

布穀鳥過濾器 對 布穀鳥哈希算法 進行了如下優化改進:

• 使用多路哈希桶提高桶的利用率

• 只存儲 key 的指紋以減少內存使用

通過異或計算尋找新桶

異或計算性質: 三個值中的任意兩個值進行異或計算，都可以得出第三個值。

示例代碼: 數字 1, 2, 3 執行異或計算

package main

func main() {
 println(1 ^ 2) // 3
 println(3 ^ 1) // 2
 println(3 ^ 2) // 1
}

布穀鳥過濾器 爲了節省內存，保存的是 x 的指紋信息，而非源值，那麼當某個元素 x 被踢出時，需要找一個新桶 h2(x)，如何在不損失 x 的指紋信息的情況下，計算新桶 (候選桶) 並存儲呢？

布穀鳥過濾器 採用了巧妙的算法: 將桶 h1(x) 和 x 的指紋信息哈希值 hash( finger(x) ) 進行 異或計算 得出新的桶，這樣當新桶的值後面被踢出時， 可以通過 異或計算 反轉得到 x 的指紋信息。

對於元素 x, 計算兩個哈希值:

h1(x) = hash(x), h2(x) = h1(x) ⊕ hash(x’s fingerprint)

踢出桶上的元素時 (不管該桶是 h1(x) 還是 h2(x))，直接使用該桶的索引 index 和存儲在桶中的指紋信息計算備用桶 j

j = i ⊕ hash(fingerprint)

均衡分配

此外，指紋與桶進行 異或計算 之前會進行哈希，從而在表中均衡分配。如果備用位使用 i ⊕ hash(fingerprint) 計算時不將指紋進行哈希，且指紋的大小與表的大小相比很小，那麼踢出的元素最終會落在鄰近的桶。

例如使用 8 位指紋，踢出的元素將被放置到離桶 i 最多 256 (2^8) 的桶，因爲 異或計算 將改變桶索引的低 8 位，而高位不會改變。 哈希指紋可以確保這些元素可以重新定位到哈希表的不同的桶中，達到均衡分配，減少哈希碰撞並提高表的利用率。

空間優化

較大的桶可以提高表的利用率，使用 2 個哈希函數，桶大小爲 1 時，負載因子爲 50% (上面提到的第一種布穀鳥哈希算法版本)， 但是當使用桶大小 2, 4, 8 時，負載因子分別會增加到 84%, 95%, 98%。

實驗數據表明，當誤判率 r > 0.002 時，每個桶使用 2 個槽位比 4 個槽位效果更好，當 r 爲到 0.00001 < r ≤ 0.002 時，每個桶 4 個槽位可以最小化空間。

半排序桶

半排序的本質是: 對每個指紋取 4 位，該 4 位可以表示爲一個 16 進制，對於 b 個指紋的 4 位存儲就可以表示爲 b 個 16 進制，進行 重複組合計算 後， 可以通過索引其位置來找到對應的指紋 (也就是某個組合值)。

假設每個桶包含 b = 4 個指紋，每個指紋 f = 4 bit，一個未壓縮的桶佔 4 x 4 = 16 bit。但是如果我們對每個 4 位指紋進行排序（空項被視爲存儲值爲 "0" 的指紋)， 那麼共有 3876 個重複組合值。如果我們預先計算並將 3876 個值存儲在一個額外的表中 (表中每個位置表示一個指紋組合)，並將桶替換爲預先計算好的表， 那麼桶可以用 12 bit 表示整個表 (2 ^ 12 = 4096> 3876)，而不是 16 bit 表示桶，這樣算下來，平均每個指紋可以節省 1 bit。

3876 是怎樣計算出來的？

重複組合數學公式

其中 n 表示被選擇的東西個數， r 表示選擇個數，(順序可以重複)。

根據數學公式，我們可以編寫如下代碼:

package main

import "fmt"

// 計算重複組合數量
func multiCombination(n, r int) int {
 if n == 0 || r == 0 {
  return 0
 }
 numerator := 1
 denominator := 1
 for i := 1; i <= r; i++ {
  numerator *= n + i - 1
  denominator *= i
 }
 return numerator / denominator
}

func main() {
 fmt.Printf("n = %d, r = %d, combinations = %d\n", 16, 4, multiCombination(16, 4))
}

在上面的代碼中，計算了在 16 bit 中 4 bit 指紋的重複組合數量。

$ go run main.go

# 輸出如下
n = 16, r = 4, combinations = 3876

開源庫

有了前文的理論基礎後，接下來一起探索下具體的代碼實現。筆者選擇開源的 linvon/cuckoo-filter 作爲研究 布穀鳥過濾器 代碼實現，版本爲 v0.4.0。

這個庫的優點

這裏直接引用庫作者的原文:

在翻閱了 Github 上 cuckoofilter 的 golang 實現後，發現已有的實現都存在一些缺點:

• 絕大部分的庫都是固定 b 和 f 的，即假陽性率也是固定的，適應性不好

• 所有的庫 f 都是以字節爲單位的，只能以 8 的倍數來調整，不方便調整假陽性率

• 所有的庫都沒有實現半排序桶，相比於布隆過濾器的優勢大打折扣

因爲作者的場景需要更優的空間和自定的假陽性率，因此移植了原論文的 C++ 實現，並做了一些優化，主要包括:

• 支持調節參數

• 支持半排序桶

• 壓縮空間到緊湊的位數組，按位存儲指紋

• 支持二進制序列化

示例

package main

import (
 "fmt"
 "github.com/linvon/cuckoo-filter"
)

func main() {
 // 初始化一個布穀鳥過濾器
 // 使用半排序桶
 //    每個桶包含 4 個指紋, 每個指紋 4 bits
 // 最大存放元素數量 4096
 cf := cuckoo.NewFilter(4, 4, 1<<12, cuckoo.TableTypePacked)

 // 添加一些元素
 cf.Add([]byte(`Hello World`))
 cf.Add([]byte(`Hello Golang`))

 // 檢測元素是否存在
 fmt.Printf("%v\n", cf.Contain([]byte(`Hello World`)))
 fmt.Printf("%v\n", cf.Contain([]byte(`Hello Golang`)))
 fmt.Printf("%v\n", cf.Contain([]byte(`Hello Rust`)))

 // 輸出元素數量
 fmt.Printf("filter size = %d\n", cf.Size())

 // 刪除元素
 cf.Delete([]byte(`Hello World`))

 // 輸出過濾器統計信息
 fmt.Println("\n", cf.Info())
}

$ go run main.go

# 輸出如下

true
true
false
filter size = 2

CuckooFilter Status:

PackedHashtable with tag size: 4 bits
4 packed bits(3 bits after compression) and 0 direct bits
Associativity: 4
Total # of rows: 2048
Total # slots: 8192

Keys stored: 1
Load factor: 0.0001220703125
Hashtable size: 3 KB
bit/key:   24632

源碼解析

接口

linvon/cuckoo-filter 實現了 普通單表 和空間優化的 基於半排序桶的壓縮表，將兩者的通用部分抽象爲 table 接口，通過運行時的 工廠方法 可以在初始化時根據不同的參數生成不同的過濾器。

const (
 // 普通表
 TableTypeSingle = 0

 // 壓縮表
 TableTypePacked = 1
)

type table interface {
  ...
}

func getTable(tableType uint) interface{} {
 switch tableType {
 case TableTypePacked:
  return NewPackedTable()
 default:
  return NewSingleTable()
 }
}

UML

過濾器數據結構

victimCache 結構體表示過濾器執行 Add 操作時被 踢出 的元素對象。

type victimCache struct {
 index uint
 tag   uint32
 used  bool
}

Filter 結構體表示 過濾器 對象，非常簡潔，只有三個字段: 被踢出元素, 元素數量, 底層用於存儲的表實例。

type Filter struct {
 victim   victimCache
 numItems uint
 table    table
}

初始化過濾器

func NewFilter(tagsPerBucket, bitsPerItem, maxNumKeys, tableType uint) *Filter {
 // 根據表內存放元素和每個桶的元素指紋數量，計算需要的桶的數量
 numBuckets := getNextPow2(uint64(maxNumKeys / tagsPerBucket))

 // 如果表的負載因子過高，就將桶的數量擴容 (翻 1 倍)
 // 負載因子如何計算出來的呢？
 //    框架這裏進行了 3 個硬編碼的值:
 //        默認:      0.99
 //        桶大小爲 2: 0.85
 //        桶大小爲 4: 0.96
 if float64(maxNumKeys)/float64(numBuckets*tagsPerBucket) > maxLoadFactor(tagsPerBucket) {
  numBuckets <<= 1
 }

 // 桶最少得有 1 個
 if numBuckets == 0 {
  numBuckets = 1
 }

 // 工廠方法根據參數類型生成過濾器
 table := getTable(tableType).(table)

 // 表初始化
 _ = table.Init(tagsPerBucket, bitsPerItem, numBuckets, nil)
 return &Filter{
  table: table,
 }
}

添加元素

Add 方法添加一個元素到表中，返回是否添加成功。

func (f *Filter) Add(item []byte) bool {
 // 如果被踢出的元素沒有找到可用的桶
 // 那麼繼續添加元素只會進入惡行循環，降低性能
 // 此時直接返回即可
 if f.victim.used {
  return false
 }

 // 計算哈希值和桶索引，然後將元素添加到表中對應的桶
 i, tag := f.generateIndexTagHash(item)
 return f.addImpl(i, tag)
}

查找元素

Contain 方法檢測給定元素是否存在於表中。

func (f *Filter) Contain(key []byte) bool {
 // 計算元素的哈希值和桶索引
 i1, tag := f.generateIndexTagHash(key)
 // 計算候選桶索引
 i2 := f.altIndex(i1, tag)

 hit := f.victim.used && tag == f.victim.tag && (i1 == f.victim.index || i2 == f.victim.index)

 // 滿足以下兩個條件之一，說明參數元素存在於表中:
 //    1. 參數元素和表內被踢出元素的哈希值以及桶位置相同
 //    2. 在表的某個桶內找到了相同的參數元素哈希
 if hit || f.table.FindTagInBuckets(i1, i2, tag) {
  return true
 }
 return false
}

計算元素數量

Size 方法計算表內當前存儲的元素數量，如果 被踢出元素 一直沒有找到可用的桶，元素數量 + 1。

func (f *Filter) Size() uint {
 var c uint
 if f.victim.used {
  c = 1
 }
 return f.numItems + c
}

計算負載因子

LoadFactor 方法計算當前表的 負載因子, 計算公式爲:

表內當前元素數量 / 表內可存儲元素數量

func (f *Filter) LoadFactor() float64 {
 return 1.0 * float64(f.Size()) / float64(f.table.SizeInTags())
}

重置過濾器

Reset 方法會重置過濾器，相當於重新初始化。

func (f *Filter) Reset() {
    // 底層表內元素初始化爲 0
    f.table.Reset()

    // 元素計數歸 0
    f.numItems = 0

    // 重置被踢出元素
    f.victim.index = 0
    f.victim.tag = 0
    f.victim.used = false
}

計算誤判率

FalsePositiveRate 方法計算 過濾器 的 誤判率，需要注意的是，該方法會調用 Reset 方法重置 過濾器。

func (f *Filter) FalsePositiveRate() float64 {
 n1 := make([]byte, 4)

 f.Reset() // 重置過濾器

 // 獲取底層表可存儲元素數量
 n := f.table.SizeInTags()
 // 循環向表內添加元素，元素爲 [0 ... n]
 for i := uint32(0); i < uint32(n); i++ {
  binary.BigEndian.PutUint32(n1, i)
  f.Add(n1)
 }

 // 計算誤判率採用的檢測次數 (這裏硬編碼爲 10 W)
 var rounds uint32 = 100000
 // 誤判計數
 fp := 0
 for i := uint32(0); i < rounds; i++ {
  // 給定一個不可能存在表中的元素
  binary.BigEndian.PutUint32(n1, i+uint32(n)+1)
  // 正常情況下，Contain 方法返回的都是 false
  if f.Contain(n1) {
   // 如果 Contain 方法返回 true, 則屬於誤判
   // 誤判計數 + 1
   fp++
  }
 }
 f.Reset()  // 重置過濾器

 // 誤判計數 / 檢測次數 = 誤判率
 return float64(fp) / float64(rounds)
}

哈希算法

module github.com/linvon/cuckoo-filter

go 1.14

require github.com/dgryski/go-metro v0.0.0-20200812162917-85c65e2d0165

從 go.mod 文件定義中可以看到，linvon/cuckoo-filter 使用的哈希算法是 MetroHash。

MetroHash 是一個哈希函數算法，可用於計算輸入數據的 64 位 和 128 位哈希值，支持增量式哈希計算，具有較高的性能和較低的碰撞率概率。

func (f *Filter) altIndex(index uint, tag uint32) uint {
 // 0x5bd1e995 是 MurmurHash2 算法的哈希常量
 return f.indexHash(uint32(index) ^ (tag * 0x5bd1e995))
}

此外，在計算 候選桶 的索引時，也用到了 Murmur2 算法。

省略部分

普通單表 和 壓縮表 的底層表存儲實現，由於時間關係不再展開分析，感興趣的讀者可以自行閱讀源代碼。

調用關係圖

調用關係示意圖

小結

本文概括了 布穀鳥過濾器 的算法描述，並對比了其和 布隆過濾器 的主要差異。在代碼實現方面，筆者選擇了開源的 linvon/cuckoo-filter[1], 着重分析了庫的接口設計和主要 API 方法實現。最後順帶提一下，如果讀者決定使用 linvon/cuckoo-filter 到項目中，需要注意的是: 庫內部並沒有做 併發限制，使用 Add, Contain 等方法時可能會遇到常見的 併發競態 問題，這就要求調用方在使用時需要做好相應的併發處理。

Reference

• Cuckoo Filter: Practically Better Than Bloom[2]

• Cuckoo filter[3]

• 布穀鳥哈希和布穀鳥過濾器 [4]

• 布穀鳥過濾器實戰對比與調參指南 [5]

• 布穀鳥過濾器：實際上優於布隆過濾器 [6]

• linvon/cuckoo-filter[7]

• Cuckoo Hashing Visualization[8]

• List of hash functions[9]

鏈接

[1]

linvon/cuckoo-filter: https://github.com/linvon/cuckoo-filter

[2]

Cuckoo Filter: Practically Better Than Bloom: http://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf

[3]

Cuckoo filter: https://en.wikipedia.org/wiki/Cuckoo_filter

[4]

布穀鳥哈希和布穀鳥過濾器: https://www.qtmuniao.com/2021/12/07/cuckoo-hash-and-cuckoo-filter/

[5]

布穀鳥過濾器實戰對比與調參指南: http://www.linvon.cn/posts/cuckoo_guide/

[6]

布穀鳥過濾器：實際上優於布隆過濾器: http://www.linvon.cn/posts/cuckoo/

[7]

linvon/cuckoo-filter: https://github.com/linvon/cuckoo-filter

[8]

Cuckoo Hashing Visualization: http://www.lkozma.net/cuckoo_hashing_visualization/

[9]

List of hash functions: https://en.wikipedia.org/wiki/List_of_hash_functions

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/pmx73QJx5bGMRkBn122Afw