go-zero源碼閱讀之布隆過濾器實現(xiàn)代碼
一. 布隆過濾器簡介
布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。
二. 常用場景
1. 解決緩存穿透
2. 數(shù)據(jù)去重，如用戶是否發(fā)送過短信
3. 特定數(shù)據(jù)識別
三. go-zero的布隆過濾器實現(xiàn)
1. 簡介
依賴redis.bitmap, 將數(shù)據(jù)多次hash后，插入到多個特定位，并設置為1。當進行數(shù)據(jù)檢測時，經(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, 因為redis lua需要[]string,然后執(zhí)行l(wèi)ua腳本進行數(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)獲取到每個偏移量，使用setbit命令設置各偏移量為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方法進行檢測
isSet, err := f.bitSet.check(locations)
if err != nil {
return false, err
}
return isSet, nil
}首先調(diào)用getLocations方法獲取數(shù)據(jù)多次hash后偏移量切片，調(diào)用check方法進行數(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ù)返回值返回數(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)判斷各偏移量是否存在，只要有一個為0,就代表數(shù)據(jù)不存在，各offset都為1則代表數(shù)據(jù)存在
到此這篇關(guān)于go-zero源碼閱讀-布隆過濾器的文章就介紹到這了,更多相關(guān)go-zero布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
golang?gorm模型結(jié)構(gòu)體的定義示例
這篇文章主要為大家介紹了golang?gorm模型結(jié)構(gòu)體的定義示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2022-04-04
Go?chassis云原生微服務開發(fā)框架應用編程實戰(zhàn)
這篇文章主要為大家介紹了Go?chassis云原生微服務開發(fā)框架應用編程實戰(zhàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要介紹了golang不到30行代碼實現(xiàn)依賴注入的方法,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
golang?chan傳遞數(shù)據(jù)的性能開銷詳解
這篇文章主要為大家詳細介紹了Golang中chan在接收和發(fā)送數(shù)據(jù)時因為“復制”而產(chǎn)生的開銷,文中的示例代碼講解詳細,感興趣的小伙伴可以了解下2024-01-01
Mutex?是?Go?語言中互斥鎖的實現(xiàn)，它是一種同步機制，用于控制多個?goroutine?之間的并發(fā)訪問。本文將著重介紹?Go?的?Mutex?并發(fā)原語，希望對大家有所幫助2023-03-03
goroutine?不是os線程、不是綠色線程（由語言運行時管理的線程），是協(xié)程。協(xié)程是一種非搶占式的簡單并發(fā)子goroutine（函數(shù)、閉包或方法），也就是說，它們不能被中斷。取而代之的是，協(xié)程有多個點，允許暫?；蛑匦逻M入?—Go語言并發(fā)之道2022-06-06
這篇文章主要為大家介紹了從錯誤中學習改正Go語言五個壞習慣提高編程技巧示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
Go并發(fā)編程實現(xiàn)數(shù)據(jù)競爭
本文主要介紹了Go并發(fā)編程實現(xiàn)數(shù)據(jù)競爭，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
sync.Cond?表示的是條件變量，它是一種同步機制，用來協(xié)調(diào)多個?goroutine?之間的同步。本文將通過示例為大家介紹Go語言中sync.Cond的使用，需要的可以參考一下2023-01-01
這篇文章主要給大家介紹了如何在Go網(wǎng)絡請求中配置代理的方法,文章通過代碼示例介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2023-09-09