詳解布隆過濾器原理與實現

爲什麼需要布隆過濾器

想象一下遇到下面的場景你會如何處理:

  1. 手機號是否重複註冊

  2. 用戶是否參與過某秒殺活動

  3. 僞造請求大量 id 查詢不存在的記錄,此時緩存未命中, 如何避免緩存穿透

針對以上問題常規做法是:查詢數據庫,數據庫硬扛,如果壓力並不大可以使用此方法,保持簡單即可。

改進做法:用 list/set/tree 維護一個元素集合,判斷元素是否在集合內,時間複雜度或空間複雜度會比較高。如果是微服務的話可以用 redis 中的 list/set 數據結構, 數據規模非常大此方案的內存容量要求可能會非常高。

這些場景有個共同點,可以將問題抽象爲:如何高效判斷一個元素不在集合中?那麼有沒有一種更好方案能達到時間複雜度和空間複雜雙優呢?

有!布隆過濾器

什麼是布隆過濾器

布隆過濾器(英語:Bloom Filter)是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中,它的優點是空間效率和查詢時間都遠遠超過一般的算法。

工作原理

布隆過濾器的原理是,當一個元素被加入集合時,通過 K 個散列函數將這個元素映射成一個位數組中的 K 個點(offset),把它們置爲 1。檢索時,我們只要看看這些點是不是都是 1 就(大約)知道集合中有沒有它了:如果這些點有任何一個 0,則被檢元素一定不在;如果都是 1,則被檢元素很可能在。這就是布隆過濾器的基本思想。

簡單來說就是準備一個長度爲 m 的位數組並初始化所有元素爲 0,用 k 個散列函數對元素進行 k 次散列運算跟 len(m) 取餘得到 k 個位置並將 m 中對應位置設置爲 1。

布隆過濾器優缺點

優點:

  1. 空間佔用極小,因爲本身不存儲數據而是用比特位表示數據是否存在,某種程度有保密的效果。

  2. 插入與查詢時間複雜度均爲 O(k),常數級別,k 表示散列函數執行次數。

  3. 散列函數之間可以相互獨立,可以在硬件指令層加速計算。

缺點:

  1. 誤差(假陽性率)。

  2. 無法刪除。

誤差(假陽性率)

布隆過濾器可以 100% 判斷元素不在集合中,但是當元素在集合中時可能存在誤判,因爲當元素非常多時散列函數產生的 k 位點可能會重複。維基百科有關於假陽性率的數學推導(見文末鏈接)這裏我們直接給結論 (實際上是我沒看懂...),假設:

在創建布隆過濾器時我們爲了找到合適的 m 和 k ,可以根據預期元素數量 n 與 ε 來推導出最合適的 m 與 k 。

java 中 Guava, Redisson 實現布隆過濾器估算最優 m 和 k 採用的就是此算法:

// 計算哈希次數
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

// 計算位數組長度
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
        p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

無法刪除

位數組中的某些 k 點是多個元素重複使用的,假如我們將其中一個元素的 k 點全部置爲 0 則直接就會影響其他元素。這導致我們在使用布隆過濾器時無法處理元素被刪除的場景。

可以通過定時重建的方式清除髒數據。假如是通過 redis 來實現的話重建時不要直接刪除原有的 key,而是先生成好新的再通過 rename 命令即可,再刪除舊數據即可。

go-zero 中的 bloom filter 源碼分析

core/bloom/bloom.go一個布隆過濾器具備兩個核心屬性:

  1. 位數組:

  2. 散列函數

go-zero 實現的bloom filter中位數組採用的是Redis.bitmap,既然採用的是 redis 自然就支持分佈式場景,散列函數採用的是MurmurHash3

Redis.bitmap 爲什麼可以作爲位數組呢?

Redis 中的並沒有單獨的 bitmap 數據結構,底層使用的是動態字符串(SDS)實現,而 Redis 中的字符串實際都是以二進制存儲的。aASCII碼是 97,轉換爲二進制是:01100001,如果我們要將其轉換爲b只需要進一位即可:01100010。下面通過Redis.setbit實現這個操作:

set foo a
OK
get foo
"a"
setbit foo 6 1
0
setbit foo 7 0  
1  
get foo  
"b"

bitmap 底層使用的動態字符串可以實現動態擴容,當 offset 到高位時其他位置 bitmap 將會自動補 0,最大支持 2^32-1 長度的位數組(佔用內存 512M),需要注意的是分配大內存會阻塞Redis進程。根據上面的算法原理可以知道實現布隆過濾器主要做三件事情:

  1. k 次散列函數計算出 k 個位點。

  2. 插入時將位數組中 k 個位點的值設置爲 1。

  3. 查詢時根據 1 的計算結果判斷 k 位點是否全部爲 1,否則表示該元素一定不存在。

下面來看看 go-zero 是如何實現的:

對象定義

// 表示經過多少散列函數計算
// 固定14次
maps = 14

type (
    // 定義布隆過濾器結構體
    Filter struct {
        bits   uint
        bitSet bitSetProvider
    }
    // 位數組操作接口定義
    bitSetProvider interface {
        check([]uint) (bool, error)
        set([]uint) error
    }
)

位數組操作接口實現

首先需要理解兩段 lua 腳本:

// ARGV:偏移量offset數組
// KYES[1]: setbit操作的key
// 全部設置爲1
setScript = `
    for _, offset in ipairs(ARGV) do
        redis.call("setbit", KEYS[1], offset, 1)
    end
    `
// ARGV:偏移量offset數組
// KYES[1]: setbit操作的key
// 檢查是否全部爲1
testScript = `
    for _, offset in ipairs(ARGV) do
        if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
            return false
        end
    end
    return true
    `

爲什麼一定要用 lua 腳本呢? 因爲需要保證整個操作是原子性執行的。

// redis位數組
type redisBitSet struct {
    store *redis.Client
    key   string
    bits  uint
}
// 檢查偏移量offset數組是否全部爲1
// 是:元素可能存在
// 否:元素一定不存在
func (r *redisBitSet) check(offsets []uint) (bool, error) {
    args, err := r.buildOffsetArgs(offsets)
    if err != nil {
        return false, err
    }
    // 執行腳本
    resp, err := r.store.Eval(testScript, []string{r.key}, args)
    // 這裏需要注意一下,底層使用的go-redis
    // redis.Nil表示key不存在的情況需特殊判斷
    if err == redis.Nil {
        return false, nil
    } else if err != nil {
        return false, err
    }

    exists, ok := resp.(int64)
    if !ok {
        return false, nil
    }

    return exists == 1, nil
}

// 將k位點全部設置爲1
func (r *redisBitSet) set(offsets []uint) error {
    args, err := r.buildOffsetArgs(offsets)
    if err != nil {
        return err
    }
    _, err = r.store.Eval(setScript, []string{r.key}, args)
    // 底層使用的是go-redis,redis.Nil表示操作的key不存在
    // 需要針對key不存在的情況特殊判斷
    if err == redis.Nil {
        return nil
    } else if err != nil {
        return err
    }
    return nil
}

// 構建偏移量offset字符串數組,因爲go-redis執行lua腳本時參數定義爲[]stringy
// 因此需要轉換一下
func (r *redisBitSet) buildOffsetArgs(offsets []uint) ([]string, error) {
    var args []string
    for _, offset := range offsets {
        if offset >= r.bits {
            return nil, ErrTooLargeOffset
        }
        args = append(args, strconv.FormatUint(uint64(offset), 10))
    }
    return args, nil
}

// 刪除
func (r *redisBitSet) del() error {
    _, err := r.store.Del(r.key)
    return err
}

// 自動過期
func (r *redisBitSet) expire(seconds int) error {
    return r.store.Expire(r.key, seconds)
}

func newRedisBitSet(store *redis.Client, key string, bits uint) *redisBitSet {
    return &redisBitSet{
        store: store,
        key:   key,
        bits:  bits,
    }
}

到這裏位數組操作就全部實現了,接下來看下如何通過 k 個散列函數計算出 k 個位點

k 次散列計算出 k 個位點

// k次散列計算出k個offset
func (f *Filter) getLocations(data []byte) []uint {
    // 創建指定容量的切片
    locations := make([]uint, maps)
    // maps表示k值,作者定義爲了常量:14
    for i := uint(0); i < maps; i++ {
        // 哈希計算,使用的是"MurmurHash3"算法,並每次追加一個固定的i字節進行計算
        hashValue := hash.Hash(append(data, byte(i)))
        // 取下標offset
        locations[i] = uint(hashValue % uint64(f.bits))
    }
  
    return locations
}

插入與查詢

添加與查詢實現就非常簡單了,組合一下上面的函數就行。

// 添加元素
func (f *Filter) Add(data []byte) error {
    locations := f.getLocations(data)
    return f.bitSet.set(locations)
}

// 檢查是否存在
func (f *Filter) Exists(data []byte) (bool, error) {
    locations := f.getLocations(data)
    isSet, err := f.bitSet.check(locations)
    if err != nil {
        return false, err
    }
    if !isSet {
        return false, nil
    }

    return true, nil
}

改進建議

整體實現非常簡潔高效,那麼有沒有改進的空間呢?

個人認爲還是有的,上面提到過自動計算最優 m 與 k 的數學公式,如果創建參數改爲:

預期總數量expectedInsertions

期望誤差falseProbability

就更好了,雖然作者註釋裏特別提到了誤差說明,但是實際上作爲很多開發者對位數組長度並不敏感,無法直觀知道 bits 傳多少預期誤差會是多少。

// New create a Filter, store is the backed redis, key is the key for the bloom filter,
// bits is how many bits will be used, maps is how many hashes for each addition.
// best practices:
// elements - means how many actual elements
// when maps = 14, formula: 0.7*(bits/maps)bits = 20*elements, the error rate is 0.000067 < 1e-4
// for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
func New(store *redis.Redis, key string, bits uint) *Filter {
    return &Filter{
        bits:   bits,
        bitSet: newRedisBitSet(store, key, bits),
    }
}

// expectedInsertions - 預期總數量
// falseProbability - 預期誤差
// 這裏也可以改爲option模式不會破壞原有的兼容性
func NewFilter(store *redis.Redis, key string, expectedInsertions uint, falseProbability float64) *Filter {
    bits := optimalNumOfBits(expectedInsertions, falseProbability)
    k := optimalNumOfHashFunctions(bits, expectedInsertions)
    return &Filter{
        bits:   bits,
        bitSet: newRedisBitSet(store, key, bits),
        k:      k,
    }
}

// 計算最優哈希次數
func optimalNumOfHashFunctions(m, n uint) uint {
    return uint(math.Round(float64(m) / float64(n) * math.Log(2)))
}

// 計算最優數組長度
func optimalNumOfBits(n uint, p float64) uint {
    return uint(float64(-n) * math.Log(p) / (math.Log(2) * math.Log(2)))
}

回到問題

如何預防非法 id 導致緩存穿透?

由於 id 不存在導致請求無法命中緩存流量直接打到數據庫,同時數據庫也不存在該記錄導致無法寫入緩存,高併發場景這無疑會極大增加數據庫壓力。解決方案有兩種:

  1. 採用布隆過濾器

數據寫入數據庫時需同步寫入布隆過濾器,同時如果存在髒數據場景(比如:刪除)則需要定時重建布隆過濾器,使用 redis 作爲存儲時不可以直接刪除 bloom.key,可以採用 rename key 的方式更新 bloom

  1. 緩存與數據庫同時無法命中時向緩存寫入一個過期時間較短的空值。

資料

布隆過濾器(Bloom Filter)原理及 Guava 中的具體實現

布隆過濾器 - 維基百科

Redis.setbit

項目地址

https://github.com/zeromicro/go-zero

歡迎使用 go-zerostar 支持我們!

微信交流羣

關注『微服務實踐』公衆號並點擊 交流羣 獲取社區羣二維碼。

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