快捷導(dǎo)航

go-zero源碼閱讀之布隆過濾器實(shí)現(xiàn)代碼

更新時(shí)間：2023年02月08日 09:30:39 作者：飛飛羽毛球

布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難，這篇文章主要介紹了go-zero源碼閱讀-布隆過濾器,需要的朋友可以參考下

一. 布隆過濾器簡介

布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

二. 常用場景

1. 解決緩存穿透

2. 數(shù)據(jù)去重，如用戶是否發(fā)送過短信

3. 特定數(shù)據(jù)識(shí)別

三. go-zero的布隆過濾器實(shí)現(xiàn)

1. 簡介

依賴redis.bitmap, 將數(shù)據(jù)多次hash后，插入到多個(gè)特定位，并設(shè)置為1。當(dāng)進(jìn)行數(shù)據(jù)檢測時(shí)，經(jīng)過相同hash后，檢測所有位，只要其中一位為0，則代表數(shù)據(jù)不存在，否則數(shù)據(jù)可能存在。

2. 布隆過濾器結(jié)構(gòu)體

type (
	// A Filter is a bloom filter.
    // 結(jié)構(gòu)體
	Filter struct {
		bits   uint
		bitSet bitSetProvider
	}
 
    // 位數(shù)組接口定義 
	bitSetProvider interface {
		check([]uint) (bool, error)
		set([]uint) error
	}
)

3. 初始化方法

func New(store *redis.Redis, key string, bits uint) *Filter {
	return &Filter{
		bits:   bits,
		bitSet: newRedisBitSet(store, key, bits),
	}
}

初始化方法比較簡單，具體操作依賴newRedisBitSet

4. newRedisBitSet方法

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

簡單的初始化, 初始化結(jié)束

5. 數(shù)據(jù)添加--Add

func (f *Filter) Add(data []byte) error {
    // 獲取數(shù)據(jù)多次hash后的各key
	locations := f.getLocations(data)
    // 插入數(shù)據(jù)
	return f.bitSet.set(locations)
}

首先獲取hash后的key的切片，然后調(diào)用set方法，將數(shù)據(jù)插入位數(shù)組(redis.bitmap)

6. 數(shù)據(jù)添加--set

func (r *redisBitSet) set(offsets []uint) error {
    // 將[]uint轉(zhuǎn)為[]string
	args, err := r.buildOffsetArgs(offsets)
	if err != nil {
		return err
	}
    // 執(zhí)行l(wèi)ua腳本
	_, err = r.store.Eval(setScript, []string{r.key}, args)
	if err == redis.Nil {
		return nil
	}
 
	return err
}

首先將[]uint轉(zhuǎn)為[]string, 因?yàn)閞edis lua需要[]string,然后執(zhí)行l(wèi)ua腳本進(jìn)行數(shù)據(jù)插入，使用lua是為了保證原子性

7. 數(shù)據(jù)添加--lua腳本

setScript = `
for _, offset in ipairs(ARGV) do
	redis.call("setbit", KEYS[1], offset, 1)
end
`

for循環(huán)獲取到每個(gè)偏移量，使用setbit命令設(shè)置各偏移量為1

8. 數(shù)據(jù)檢測--Exists

func (f *Filter) Exists(data []byte) (bool, error) {
    // 同數(shù)據(jù)set一致，獲取數(shù)據(jù)多次hash后，偏移量切片
	locations := f.getLocations(data)
    // 調(diào)用check方法進(jìn)行檢測
	isSet, err := f.bitSet.check(locations)
	if err != nil {
		return false, err
	}
 
	return isSet, nil
}

首先調(diào)用getLocations方法獲取數(shù)據(jù)多次hash后偏移量切片，調(diào)用check方法進(jìn)行數(shù)據(jù)檢測

9. 數(shù)據(jù)檢測--check

func (r *redisBitSet) check(offsets []uint) (bool, error) {
    // []uint轉(zhuǎn)為[]string,和set調(diào)用的一致
	args, err := r.buildOffsetArgs(offsets)
	if err != nil {
		return false, err
	}
 
    //執(zhí)行l(wèi)ua腳本，檢測各偏移量數(shù)據(jù)是否都存在 
	resp, err := r.store.Eval(testScript, []string{r.key}, args)
    // 根據(jù)返回值判斷數(shù)據(jù)是否存在
   // 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
}

執(zhí)行l(wèi)ua腳本判斷數(shù)據(jù)是否存在，根據(jù)返回值返回?cái)?shù)據(jù)是否存在

10. 數(shù)據(jù)檢測--lua腳本

testScript = `
for _, offset in ipairs(ARGV) do
	if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
		return false
	end
end
return true
`

fou循環(huán)判斷各偏移量是否存在，只要有一個(gè)為0,就代表數(shù)據(jù)不存在，各offset都為1則代表數(shù)據(jù)存在

到此這篇關(guān)于go-zero源碼閱讀-布隆過濾器的文章就介紹到這了,更多相關(guān)go-zero布隆過濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片