概述

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點(diǎn)是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識別率和刪除困難。——引自：[維基百科]

如果對概念沒有很深的理解，我們可以通過一個實(shí)際業(yè)務(wù)場景出發(fā)，來加深對這個組件的理解，假設(shè)我們需要判斷一個值是否在一個集合中，這個判斷結(jié)果允許有一定的誤差，你靈光一閃而過的解決方案是不是這樣？

func contains(list []any, item any) bool {
   for _, i := range list {
      if i == item {
         return true
      }
   }
   return false
}

這是最原始，最簡單粗暴的解決方案，不難看出，該算法的時間復(fù)雜度為 O(n)，當(dāng)我們要從 100w 數(shù)據(jù)判斷是否存在某一個元素是否存在時，你能想到哪些優(yōu)化方案？是不是首先要降低時間復(fù)雜度，那么我們將該算法稍作修改，代碼如下：

func contains(m map[any]struct{}, item any) bool {
   _, ok := m[item]
   return ok
}

將數(shù)據(jù)結(jié)構(gòu)稍作修改，從數(shù)組改為 map，其時間復(fù)雜度由原來的 O(n) 降低至 O(1)，簡單從時間復(fù)雜度上來看，是不是已經(jīng)能夠完全解決問題了，如果我們將空間復(fù)雜度放進(jìn)來一起考慮呢？那么數(shù)組和 map 的空間復(fù)雜度都是 O(n)，100萬的數(shù)據(jù)，如果一個數(shù)據(jù)空間暫用為 1k，那么 100萬數(shù)據(jù)暫用空間約 980Mb，如果每個視頻的評論積贊數(shù)都用這個算法，那以目前短視頻這種量，一個視頻得搞 1G 來存，這顯然行不通的，有沒有剛好的方案呢。

我們可以基于 redis bitmap 做操作，redis 的 bitmap 是基于字符串的，如果按照一個用戶一個偏移量來計(jì)算，100萬個用戶的點(diǎn)贊大約會用約 12k 的空間，且讀寫的時間復(fù)雜度均是 O(1)，這相對于 map 來看，這個優(yōu)化空間量級非常大，也很可觀，其實(shí)到這里一般的業(yè)務(wù)需求完全夠用了，假設(shè)一個用戶平均每個視頻有100萬贊，每個用戶終身暫定有 10000 個視頻，那么一個用戶需要消耗 117 Mb，這個相比于用戶給平臺帶來的收益那是微乎其微的。我們緊接著繼續(xù)深討，如果該公司有1億用戶，且每個用戶都需要消耗117Mb，那么所有用戶將消耗 11158 Tb,按照目前 redis 行情計(jì)算，集群版，2分片（每分片 1G 存儲）計(jì)算，大約 2900元/年，因此 11158 Tb 一年要花費(fèi) 331 億元，真要這么搞，恐怕面試的時候就讓你回家等消息了。

布隆過濾器原理

布隆過濾器的原理是，當(dāng)一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點(diǎn)，把它們置為1。檢索時，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。——引自：[維基百科]

如果用布隆過濾器，則可以縮小 2^k，假設(shè) k 為 16，那么上述費(fèi)用立馬會從331億元減少至約 51萬元，這個成本降幅那是相當(dāng)哇塞。

優(yōu)缺點(diǎn)

從上述描述我們已經(jīng)清晰的感知到，布隆過濾器相比于其他數(shù)據(jù)結(jié)構(gòu)，其時間復(fù)雜度和空間復(fù)雜度都有足夠的優(yōu)勢，但空間復(fù)雜度的優(yōu)勢又是其劣勢，可想而知，將1億個用戶，每個用戶100萬數(shù)據(jù)落在固定長度中的某 k 位位圖上，其會有沖突概率的，因此給業(yè)務(wù)帶來的感知是誤算率會隨著位圖的長度降低而增高，由于沖突導(dǎo)致的誤算，因此布隆過濾器是不允許做刪除操作的，誰知道有多少個沖突數(shù)據(jù)落在了這 k 個點(diǎn)上。

go-zero 中的布隆過濾器算法

go-zero 中的布隆過濾器也是基于 redis bitmap 的，其主要由 4 個方法組成：// 代碼為偽代碼

type Bloom interface{
  Add(data []byte) error
  AddCtx(ctx context.Context, data []byte) error
  Exists(data []byte) (bool, error)
  ExistsCtx(ctx context.Context, data []byte) (bool, error)
}

算法時序圖

計(jì)算偏移量 - getLocations

func (f *Filter) getLocations(data []byte) []uint {
   locations := make([]uint, maps)
   for i := uint(0); i < maps; i++ {
      hashValue := hash.Hash(append(data, byte(i)))
      locations[i] = uint(hashValue % uint64(f.bits))
   }
   return locations
}

根據(jù)維基百科定義，『通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點(diǎn)』，那么期望結(jié)果是每個散列函數(shù)映射的偏移量都不同，在 go-zero 中，其巧妙通過散列函數(shù)的索引與數(shù)據(jù)字節(jié)組充足成一個字節(jié)組來對新的字節(jié)組進(jìn)行 hash 計(jì)算得到不同的 hash 值，然后再將該值與用戶期望的位圖長度進(jìn)行取模計(jì)算得到偏移量。

Bitmap setbit 操作

// 對 redis bitmap 進(jìn)行 setbit 操作
var setScript = redis.NewScript(`
for _, offset in ipairs(ARGV) do
   redis.call("setbit", KEYS[1], offset, 1)
end
`)
func (r *redisBitSet) set(ctx context.Context, offsets []uint) error {
   ...
   _, err = r.store.ScriptRunCtx(ctx, setScript, []string{r.key}, args)
   if err == redis.Nil {
      return nil
   }
   return err
}

Bitmap getbit 操作

// 對 redis getbit 進(jìn)行 setbit 操作
var testScript = redis.NewScript(`
for _, offset in ipairs(ARGV) do
   if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
      return false
   end
end
return true
`)
func (r *redisBitSet) check(ctx context.Context, offsets []uint) (bool, error) {
   ...
   resp, err := r.store.ScriptRunCtx(ctx, testScript, []string{r.key}, args)
   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
}

FAQ

1. 為什么使用 LUA 腳本進(jìn)行 bitmap 操作？

由于我們需要對 14 個 bitmap 偏移量進(jìn)行操作：

• lua 腳本可以將多個指令一次性發(fā)送
• 原子操作

2. 為什么采用 14 個散列函數(shù)，這個數(shù)值怎么來的？

最佳實(shí)踐參考：https://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

當(dāng)散列函數(shù)個數(shù)為 14 時，且位圖長度在20，其誤算率可達(dá)到最低，在 0.000067。

以上就是go-zero 組件介紹：布隆過濾器的詳細(xì)內(nèi)容，更多關(guān)于go-zero 組件布隆過濾器的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論