概述

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

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

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

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

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

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

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

布隆過(guò)濾器原理

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

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

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

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

go-zero 中的布隆過(guò)濾器算法

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

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)
}

算法時(shí)序圖

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

Bitmap setbit 操作

// 對(duì) 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 操作

// 對(duì) 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 操作？

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

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

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

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

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

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

最新評(píng)論