go語(yǔ)言中布隆過(guò)濾器低空間成本判斷元素是否存在方式

第go語(yǔ)言中布隆過(guò)濾器低空間成本判斷元素是否存在方式目錄簡(jiǎn)介原理數(shù)據(jù)結(jié)構(gòu)添加判斷存在哈希函數(shù)布隆過(guò)濾器大小、哈希函數(shù)數(shù)量、誤判率應(yīng)用場(chǎng)景數(shù)據(jù)庫(kù)黑名單實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)初始化添加元素判斷元素是否存在

簡(jiǎn)介

布隆過(guò)濾器（BloomFilter）是一種用于判斷元素是否存在的方式，它的空間成本非常小，速度也很快。

但是由于它是基于概率的，因此它存在一定的誤判率，它的Contains()操作如果返回true只是表示元素可能存在集合內(nèi)，返回false則表示元素一定不存在集合內(nèi)。因此適合用于能夠容忍一定誤判元素存在集合內(nèi)的場(chǎng)景，比如緩存。

它一秒能夠進(jìn)行上百萬(wàn)次操作（主要取決于哈希函數(shù)的速度），并且1億數(shù)據(jù)在誤判率1%的情況下，只需要114MB內(nèi)存。

原理

數(shù)據(jù)結(jié)構(gòu)

布隆過(guò)濾器的數(shù)據(jù)結(jié)構(gòu)是一個(gè)位向量，也就是一個(gè)由0、1所組成的向量（下面是一個(gè)初始向量）：

添加

每個(gè)元素添加進(jìn)布隆過(guò)濾器前，都會(huì)經(jīng)過(guò)多個(gè)不同的哈希函數(shù)，計(jì)算出不同的哈希值，然后映射到位向量上，也就是對(duì)應(yīng)的位上面置1：

判斷存在

判斷元素是否存在也是如上圖流程，根據(jù)哈希函數(shù)映射的位置，判斷所有映射位置是否都為1，如果是則元素可能存在，否則元素一定不存在。

由于不同的值通過(guò)哈希函數(shù)之后可能會(huì)映射到相同的位置，因此如果一個(gè)不存在的元素對(duì)應(yīng)的位位置都被其他元素所設(shè)置位1，則查詢時(shí)就會(huì)誤判：

假設(shè)上圖元素3334并沒(méi)有加入集合，但是由于它映射的位置已經(jīng)被其他元素所映射，則查詢時(shí)會(huì)誤判。

哈希函數(shù)

布隆過(guò)濾器里面的哈希函數(shù)需要是彼此獨(dú)立且均勻分布（類(lèi)似于哈希表的哈希函數(shù)），而且需要盡可能的快，比如murmur3就是一個(gè)很好的選擇。

布隆過(guò)濾器的性能?chē)?yán)重依賴于哈希函數(shù)的性能，而一般哈希函數(shù)的性能則依賴于輸入串（一般為字節(jié)數(shù)組）的長(zhǎng)度，因此為了提高布隆過(guò)濾器的性能建議減少輸入串的長(zhǎng)度。

下面是一個(gè)簡(jiǎn)單的性能測(cè)試，單位是字節(jié)，可以看到時(shí)間的消耗隨著元素的增大基本是線性增長(zhǎng)的：

cpu:Intel(R)Core(TM)i5-10210UCPU@1.60GHz

BenchmarkAddAndContains/1-81805840659.6ns/op1.52MB/s0B/op0allocs/op

BenchmarkAddAndContains/2-81824064696.4ns/op2.87MB/s0B/op0allocs/op

BenchmarkAddAndContains/4-81819742649.5ns/op6.16MB/s0B/op0allocs/op

BenchmarkAddAndContains/8-81828371653.2ns/op12.25MB/s0B/op0allocs/op

BenchmarkAddAndContains/16-81828426642.0ns/op24.92MB/s0B/op0allocs/op

BenchmarkAddAndContains/32-82106834565.7ns/op56.57MB/s0B/op0allocs/op

BenchmarkAddAndContains/64-82063895579.3ns/op110.48MB/s0B/op0allocs/op

BenchmarkAddAndContains/128-81767673666.1ns/op192.17MB/s0B/op0allocs/op

BenchmarkAddAndContains/256-81292918916.9ns/op279.21MB/s0B/op0allocs/op

BenchmarkAddAndContains/512-87496661590ns/op322.11MB/s0B/op0allocs/op

BenchmarkAddAndContains/1024-83880152933ns/op349.12MB/s0B/op0allocs/op

BenchmarkAddAndContains/2048-82034045603ns/op365.51MB/s0B/op0allocs/op

BenchmarkAddAndContains/4096-810513411303ns/op362.38MB/s0B/op0allocs/op

BenchmarkAddAndContains/8192-85230522067ns/op371.23MB/s0B/op0allocs/op

布隆過(guò)濾器大小、哈希函數(shù)數(shù)量、誤判率

布隆過(guò)濾器的大小、哈希函數(shù)數(shù)量和誤判率之間是互相影響的，如果我們想減少誤判率，則需要更大的布隆過(guò)濾器和更多的哈希函數(shù)。但是我們很難直觀的計(jì)算出這些參數(shù)，還好有兩個(gè)公式可以幫助我們計(jì)算出準(zhǔn)確的數(shù)值：

在我們可以確定我們的元素?cái)?shù)量和能夠容忍的錯(cuò)誤率的情況下，我們可以根據(jù)下面公式計(jì)算布隆過(guò)濾器大小和哈希函數(shù)數(shù)量：

n=元素?cái)?shù)量

m=布隆過(guò)濾器大?。ㄎ粩?shù)）

k=哈希函數(shù)數(shù)量

fpr=錯(cuò)誤率（falsePositiveRate，假陽(yáng)性率）

m=n*(-ln(fpr)/(ln2*ln2))

k=ln2*m/n

應(yīng)用場(chǎng)景

數(shù)據(jù)庫(kù)

布隆過(guò)濾器可以提前過(guò)濾所查詢數(shù)據(jù)并不存在的請(qǐng)求，避免對(duì)磁盤(pán)訪問(wèn)的耗時(shí)。比如LevelDB就使用了布隆過(guò)濾器過(guò)濾請(qǐng)求/google/leve。

黑名單

假設(shè)有10億個(gè)黑名單URL，每個(gè)URL大小為64字節(jié)。使用BloomFilter，如果錯(cuò)誤率為0.1%，只需要1.4GB內(nèi)存，如果錯(cuò)誤率為0.0001%，也只需要2.9GB內(nèi)存。

實(shí)現(xiàn)

這里簡(jiǎn)單的介紹一下Golang的實(shí)現(xiàn)方式。

代碼：/jiaxwu/gomm

由于我們沒(méi)辦法直接申請(qǐng)一個(gè)bit組成的數(shù)組，因此我們使用uint64表示64個(gè)bit。

typeFilterstruct{

bits[]uint64//bit數(shù)組

bitsCntuint64//bit位數(shù)

hashs[]*hash.Hash//不同哈希函數(shù)

初始化

在初始化的時(shí)候，我們需要根據(jù)上面提到的兩個(gè)公式，計(jì)算布隆過(guò)濾器的大小和哈希函數(shù)的數(shù)量。

//capacity：容量

//falsePositiveRate：誤判率

funcNew(capacityuint64,falsePositiveRatefloat64)*Filter{

//bit數(shù)量

ln2:=math.Log(2.0)

factor:=-math.Log(falsePositiveRate)/(ln2*ln2)

bitsCnt:=mmath.Max(1,uint64(float64(capacity)*factor))

//哈希函數(shù)數(shù)量

hashsCnt:=mmath.Max(1,int(ln2*float64(bitsCnt)/float64(capacity)))

hashs:=make([]*hash.Hash,hashsCnt)

fori:=0;ihashsCnt;i++{

hashs[i]=hash.New()

returnamp;Filter{

bits:make([]uint64,(bitsCnt+63)/64),

bitsCnt:bitsCnt,

hashs:hashs,

添加元素

添加元素的時(shí)候，把每個(gè)哈希函數(shù)映射的位置都設(shè)置為1。這里需要注意，因?yàn)槭怯玫膗int64的數(shù)組，因此需要把按照bit計(jì)算的偏移，轉(zhuǎn)換為按照64位計(jì)算的數(shù)組下標(biāo)和對(duì)應(yīng)下標(biāo)元素里面的偏移。

//添加元素

func(f*Filter)Add(b[]byte){

for_,h:=rangef.hashs{

index,offset:=f.pos(h,b)

f.bits[index]|=1offset

//獲取對(duì)應(yīng)元素下標(biāo)和偏移

func(f*Filter)pos(h*hash.Hash,b[]byte)(uint64,uint64){

hashValue:=h.Sum64(b)

//按照位計(jì)算的偏移

bitsIndex:=hashValue%f.bitsCnt

//因?yàn)橐粋€(gè)元素64位，因此需要轉(zhuǎn)換

index:=bitsIndex/uint64Bits

//在一個(gè)元素里面的偏移

offset:=bitsIndex%uint64Bits

returnindex,offset

判斷元素是否存在

同理，只是這里我們?nèi)绻l(fā)現(xiàn)某一位不為1則可以直接返回false。

//元素是否存在

//true表示可能存在

func(f*Filter)Contains(b[]byte)bool{

for_,h:=rangef.hashs{

index,offset:=