首頁 > 資料庫 > Redis > 主體

Redis BloomFilter布隆過濾器如何實現

WBOY
發布: 2023-05-30 13:41:09
轉載
1539 人瀏覽過

    Bloom Filter 概念

    一個名叫布隆的人在1970年提出了布隆過濾器(英文名:Bloom Filter)。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用來檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的演算法,缺點是有一定的誤辨識率和刪除困難。

    Bloom Filter 原理

    布隆過濾器的原理是,當一個元素被加入集合時,透過K個雜湊函數將這個元素映射成一個位元組中的K個點,把它們置為1。檢索時,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點有任何一個0,則被檢元素一定不在;如果都是1,則被檢元素很可能在。這就是布隆過濾器的基本想法。

    Bloom Filter跟單一雜湊函數Bit-Map不同之處在於:Bloom Filter使用了k個雜湊函數,每個字串跟k個bit對應。從而降低了衝突的機率

    Redis BloomFilter布隆過濾器如何實現

    快取穿透

    Redis BloomFilter布隆過濾器如何實現

    每次查詢都會直接打到DB

    #簡而言之,言而簡之就是我們先把我們資料庫的資料都載入到我們的篩選器中,例如資料庫的id現在有:1、2、3

    那就用id:1 為例子他在上圖中經過三次hash之後,把三次原本值0的地方改為1

    下次資料進來查詢的時候如果id的值是1,那麼我就把1拿去三次hash 發現三次hash的值,跟上面的三個位置完全一樣,那就能證明過濾器中有1的

    反之如果不一樣就表示不存在了

    那應用的場景在哪裡呢?一般我們都會用來防止快取擊穿

    簡單來說就是你資料庫的id都是1開始然後自增的,那我知道你介面是透過id查詢的,我就拿負數去查詢,這時候,會發現快取裡面沒這個數據,我又去資料庫查也沒有,一個請求這樣,100個,1000個,10000個呢?你的DB基本上就扛不住了,如果在快取裡面加上這個,是不是就不存在了,你判斷沒這個資料就不去查了,直接return一個資料為空不就好了嘛。

    這玩意這麼好使那有啥缺點麼?有的,我們接著往下看

    Bloom Filter的缺點

    bloom filter之所以能做到在時間和空間上的效率比較高,是因為犧牲了判斷的準確率、刪除的便利性

    儘管容器可能不包含應查找的元素,但由於雜湊操作,這些元素在k 個雜湊位置的值都為1,所以可能會導致誤判。透過建立一個白名單來儲存可能會誤判的元素,當Bloom Filter中儲存的是黑名單時,可以降低誤判率。

    刪除困難。一個放入容器的元素映射到bit數組的k個位置上是1,刪除的時候不能簡單的直接置為0,可能會影響其他元素的判斷。可以採用Counting Bloom Filter

    常見問題

    1、為何要使用多個雜湊函數?

    如果只使用一個雜湊函數,Hash本身就會經常發生衝突。例如長度100的數組,如果只使用一個雜湊函數,添加一個元素後,添加第二個元素時衝突的機率為1%,添加第三個元素時衝突的機率為2%…但如果使用兩個個雜湊函數,加入一個元素後,加入第二個元素時衝突的機率降為萬分之4(四種可能的衝突情況,情況總數100x100)

    go語言實作

    package main
    import (
    	"fmt"
    	"github.com/bits-and-blooms/bitset"
    )
    //设置哈希数组默认大小为16
    const DefaultSize = 16
    //设置种子,保证不同哈希函数有不同的计算方式
    var seeds = []uint{7, 11, 13, 31, 37, 61}
    //布隆过滤器结构,包括二进制数组和多个哈希函数
    type BloomFilter struct {
    	//使用第三方库
    	set *bitset.BitSet
    	//指定长度为6
    	hashFuncs [6]func(seed uint, value string) uint
    }
    //构造一个布隆过滤器,包括数组和哈希函数的初始化
    func NewBloomFilter() *BloomFilter {
    	bf := new(BloomFilter)
    	bf.set = bitset.New(DefaultSize)
    
    	for i := 0; i < len(bf.hashFuncs); i++ {
    		bf.hashFuncs[i] = createHash()
    	}
    	return bf
    }
    //构造6个哈希函数,每个哈希函数有参数seed保证计算方式的不同
    func createHash() func(seed uint, value string) uint {
    	return func(seed uint, value string) uint {
    		var result uint = 0
    		for i := 0; i < len(value); i++ {
    			result = result*seed + uint(value[i])
    		}
    		//length = 2^n 时,X % length = X & (length - 1)
    		return result & (DefaultSize - 1)
    	}
    }
    //添加元素
    func (b *BloomFilter) add(value string) {
    	for i, f := range b.hashFuncs {
    		//将哈希函数计算结果对应的数组位置1
    		b.set.Set(f(seeds[i], value))
    	}
    }
    //判断元素是否存在
    func (b *BloomFilter) contains(value string) bool {
    	//调用每个哈希函数,并且判断数组对应位是否为1
    	//如果不为1,直接返回false,表明一定不存在
    	for i, f := range b.hashFuncs {
    		//result = result && b.set.Test(f(seeds[i], value))
    		if !b.set.Test(f(seeds[i], value)) {
    			return false
    		}
    	}
    	return true
    }
    func main() {
    	filter := NewBloomFilter()
    	filter.add("asd")
    	fmt.Println(filter.contains("asd"))
    	fmt.Println(filter.contains("2222"))
    	fmt.Println(filter.contains("155343"))
    }
    登入後複製

    輸出結果如下:

    true
    false
    false

    以上是Redis BloomFilter布隆過濾器如何實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

    相關標籤:
    來源:yisu.com
    本網站聲明
    本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
    熱門教學
    更多>
    最新下載
    更多>
    網站特效
    網站源碼
    網站素材
    前端模板