快捷導航

go-zero?組件布隆過濾器使用示例詳解

更新時間：2023年05月24日 14:01:17 作者：Keson

這篇文章主要為大家介紹了go-zero組件介紹之布隆過濾器使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

概述

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

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

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

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

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

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

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

布隆過濾器原理

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

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

優(yōu)缺點

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

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

算法時序圖

計算偏移量 - 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個點』，那么期望結(jié)果是每個散列函數(shù)映射的偏移量都不同，在 go-zero 中，其巧妙通過散列函數(shù)的索引與數(shù)據(jù)字節(jié)組充足成一個字節(jié)組來對新的字節(jié)組進行 hash 計算得到不同的 hash 值，然后再將該值與用戶期望的位圖長度進行取模計算得到偏移量。

Bitmap setbit 操作

// 對 redis bitmap 進行 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 進行 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
}