C#實(shí)現(xiàn)從位圖到布隆過(guò)濾器的方法

第C#實(shí)現(xiàn)從位圖到布隆過(guò)濾器的方法目錄前言布隆過(guò)濾器簡(jiǎn)介數(shù)據(jù)的存儲(chǔ)Hash沖突的解決方案為什么布隆過(guò)濾器不支持刪除用C#實(shí)現(xiàn)Bitmap位運(yùn)算利用位運(yùn)算創(chuàng)建Bitmap用C#實(shí)現(xiàn)布隆過(guò)濾器MurmurHash3的使用將任意類型的key轉(zhuǎn)換為byte數(shù)組Funnel與Sink的定義Sink的實(shí)現(xiàn)k個(gè)Hash函數(shù)與布隆過(guò)濾器實(shí)現(xiàn)擴(kuò)展帶計(jì)數(shù)器的布隆過(guò)濾器分布式布隆過(guò)濾器實(shí)現(xiàn)方案代碼地址

前言

本文將以C#語(yǔ)言來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的布隆過(guò)濾器，為簡(jiǎn)化說(shuō)明，設(shè)計(jì)得很簡(jiǎn)單，僅供學(xué)習(xí)使用。

感謝@時(shí)總百忙之中的指導(dǎo)。

布隆過(guò)濾器簡(jiǎn)介

布隆過(guò)濾器（Bloomfilter）是一種特殊的HashTable，能夠以較小的存儲(chǔ)空間較快地判斷出數(shù)據(jù)是否存在。常用于允許一定誤判率的數(shù)據(jù)過(guò)濾及防止緩存擊穿及等場(chǎng)景。

相較于.NET中的HashSet這樣傳統(tǒng)的HashTable，存在以下的優(yōu)劣勢(shì)。

優(yōu)勢(shì)：

占用的存儲(chǔ)空間較小。不需要像HashSet一樣存儲(chǔ)Key的原始數(shù)據(jù)。

劣勢(shì)：

存在誤判率，過(guò)濾器認(rèn)為不存在的數(shù)據(jù)一定不存在，但是認(rèn)為存在的數(shù)據(jù)不一定真的存在。這個(gè)和布隆過(guò)濾器的實(shí)現(xiàn)方式有關(guān)。不支持?jǐn)?shù)據(jù)的刪除，下文會(huì)講為什么不支持刪除。

數(shù)據(jù)的存儲(chǔ)

布隆過(guò)濾器的數(shù)據(jù)保存在位圖（Bitmap）上。Bitmap簡(jiǎn)而言之是二進(jìn)制位（bit）的數(shù)組。HashTable保存每個(gè)元素的位置，我們稱之為桶（bucket），Bitmap上的每一位就是布隆過(guò)濾器的bucket。

布隆過(guò)濾器的每一個(gè)bucket只能存儲(chǔ)0或1。數(shù)據(jù)插入時(shí)，布隆過(guò)濾器會(huì)通過(guò)Hash函數(shù)計(jì)算出插入的key對(duì)應(yīng)的bucket，并將該bucket設(shè)置為1。

查詢時(shí)，再次根據(jù)Hash函數(shù)計(jì)算出key對(duì)應(yīng)的bucket，如果bucket的值是1，則認(rèn)為key存在。

Hash沖突的解決方案

布隆過(guò)濾器使用了Hash函數(shù)，自然也逃不過(guò)Hash沖突的問(wèn)題。對(duì)布隆過(guò)濾器而言，發(fā)生Hash沖突也就意味著會(huì)發(fā)生誤判。

傳統(tǒng)Hash算法解決Hash沖突的方式有開放定址法、鏈表法等。而布隆過(guò)濾器解決Hash沖突的方式比較特殊，它使用了多個(gè)Hash函數(shù)來(lái)解決沖突問(wèn)題。

下圖中插入布隆過(guò)濾器的Bar和Baz經(jīng)過(guò)Hash2計(jì)算出的位置是同一個(gè)，但Hash3計(jì)算出的位置是不一樣的，Bar和Baz得以區(qū)分。

即使布隆過(guò)濾器使用了這種方式來(lái)解決Hash沖突，沖突的可能性依舊存在，如下圖所示：

由于布隆過(guò)濾器不保留插入的Key的原始值，Hash沖突是無(wú)法避免的。我們只能通過(guò)增加Hash函數(shù)的數(shù)量來(lái)減少?zèng)_突的概率，也就是減少誤判率。

假設(shè)布隆過(guò)濾器有m個(gè)bucket，包含k個(gè)哈希函數(shù)，已經(jīng)插入了n個(gè)key。經(jīng)數(shù)學(xué)推導(dǎo)可得誤判率的公式如下：

具體推斷過(guò)程可參考/wiki/Bloom_filter。

布隆過(guò)濾器的誤判概率大致和已經(jīng)插入的key的數(shù)量n成正比，和hash函數(shù)數(shù)量k、bucket數(shù)m成反比。為了減少誤判率，我們可以增加m或增加k，增加m意味著過(guò)濾器占用存儲(chǔ)空間會(huì)增加，增加k則意味著插入和查詢時(shí)的效率會(huì)降低。

為什么布隆過(guò)濾器不支持刪除

布隆過(guò)濾器通過(guò)多個(gè)Hash函數(shù)來(lái)解決沖突的設(shè)計(jì)，也意味著多著插入元素可能會(huì)共享同樣的bucket，刪掉一個(gè)元素的同時(shí)，也會(huì)被其他元素的一部分bucket給刪掉。因此基于Bitmap實(shí)現(xiàn)的布隆過(guò)濾器是不支持刪除的。

用C#實(shí)現(xiàn)Bitmap

在實(shí)現(xiàn)布隆過(guò)濾器之前，我們首先要實(shí)現(xiàn)一個(gè)Bitmap。

在C#中，我們并不能直接用bit作為最小的數(shù)據(jù)存儲(chǔ)單元，但借助位運(yùn)算的話，我們就可以基于其他數(shù)據(jù)類型來(lái)表示，比如byte。下文用byte作為例子來(lái)描述Bitmap的實(shí)現(xiàn)，但不僅限于byte，int、long等等也是可以的。

位運(yùn)算

下面是C#中位運(yùn)算的簡(jiǎn)單介紹：

符號(hào)描述運(yùn)算規(guī)則與兩個(gè)位都為1時(shí)，結(jié)果才為1|或兩個(gè)位都為0時(shí)，結(jié)果才為0^異或兩個(gè)位相同為0，相異為1~取反0變1，1變0左移各二進(jìn)位全部左移若干位，低位補(bǔ)0右移各二進(jìn)位全部右移若干位，高位補(bǔ)0

一般來(lái)說(shuō)，我們要進(jìn)行位運(yùn)算計(jì)算的數(shù)據(jù)通常都是由多個(gè)二進(jìn)位組成的。對(duì)兩個(gè)數(shù)字使用、|、^這三個(gè)運(yùn)算符時(shí)，需要對(duì)齊兩個(gè)數(shù)字的右邊，一位位地進(jìn)行計(jì)算。

//0b代表值用二進(jìn)制表示數(shù)字

shorta=0b0111111111111001;

byteb=0b011111111;

shortc=(short)(ab);//0b0111111111111001

shortd=(short)(a|b);//0b0111111111111111

shorte=(short)(a^b);//0b0000000000000110

bytef=(byte)~b;0b011111111;

shortg=(short)(b1);//0b0000000111111111;

shorth=(short)(b1);//0b0000000001111111;

利用位運(yùn)算創(chuàng)建Bitmap

借助byte實(shí)現(xiàn)Bitmap，也就是要能夠修改和查看byte上的每一個(gè)bit的值，同時(shí)，修改要能夠?qū)崿F(xiàn)冪等。

1.指定位設(shè)置成1

按前面說(shuō)的位運(yùn)算的規(guī)則，是不能夠單獨(dú)修改bit序列中某一位的。位運(yùn)算需要從右到左一對(duì)對(duì)計(jì)算。

使用|可以實(shí)現(xiàn)這個(gè)功能。假設(shè)我們要改變從右開始下標(biāo)為3（初始位置0）的bit的值，則需要準(zhǔn)備一個(gè)該位置為1，其他位置都是0的bit序列，與要改變的bit序列進(jìn)行|運(yùn)算。

//為了將a的右邊數(shù)起第3位改成1，需要準(zhǔn)備一個(gè)b

bytea=0b010100010;

byteb=13;//0b000001000

a|=b;//0b010101010

2.指定位設(shè)置成0

和設(shè)置成1正好相反，需要準(zhǔn)備一個(gè)指定位置為0，其他位置都是1的bit序列，與要改變的bit序列進(jìn)行運(yùn)算。

bytea=0b010101010;

byteb=13;//0b000001000

b=~b;//0b111110111

a=b;//0b010100010

3.查看指定位的值

利用運(yùn)算符，只要計(jì)算結(jié)果不為0，就代表指定位置的值為1。

bytea=0b010101010;

byteb=13;//0b000001000;

a=b;//0b000001000;

了解了基本的操作之后，我們把數(shù)據(jù)存儲(chǔ)到byte數(shù)組上。

classBitmap

privatereadonlybyte[]_bytes;

privatereadonlylong_capacity;

publicBitmap(longcapacity)

_capacity=capacity;

_bytes=newbyte[_capacity/8+1];

publiclongCapacity=_capacity;

publicvoidSet(longindex)

if(index=_capacity)

thrownewIndexOutOfRangeException();

//計(jì)算出數(shù)據(jù)存在第幾個(gè)byte上

longbyteIndex=index/8;

//計(jì)算出數(shù)據(jù)存在第幾個(gè)bit上

intbitIndex=(int)(index%8);

_bytes[byteIndex]|=(byte)(1bitIndex);

publicvoidRemove(longindex)

if(index=_capacity)

thrownewIndexOutOfRangeException();

longbyteIndex=index/8;

intbitIndex=(int)(index%8);

_bytes[byteIndex]=(byte)~(1bitIndex);

publicboolGet(longindex)

if(index=_capacity)

thrownewIndexOutOfRangeException();

longbyteIndex=index/8;

intbitIndex=(int)(index%8);

return(_bytes[byteIndex](byte)(1bitIndex))!=0;

用C#實(shí)現(xiàn)布隆過(guò)濾器

有了Bitmap，我們?cè)侔袶ash函數(shù)的實(shí)現(xiàn)準(zhǔn)備好，一個(gè)簡(jiǎn)單的布隆過(guò)濾器就可以完成了。這里，我們參考guava這個(gè)java庫(kù)的實(shí)現(xiàn)。

/google/guava/blob/master/guava/src/com/google/common/hash/BloomFilter.java

MurmurHash3的使用

我們使用和guava一樣的MurmurHash3作為Hash函數(shù)的實(shí)現(xiàn)。

下面是筆者在github上找到的一個(gè)可用實(shí)現(xiàn)。

/darrenkopp/murmurhash-net

使用這個(gè)庫(kù)，我們可以將任意長(zhǎng)的byte數(shù)組轉(zhuǎn)換成128位的二進(jìn)制位，也就是16byte。

byte[]data=Guid.NewGuid().ToByteArray();

//returnsa128-bitalgorithmusing"unsafe"codewithdefaultseed

HashAlgorithmmurmur128=MurmurHash.Create128(managed:false);

byte[]hash=murmur128.ComputeHash(data);

將任意類型的key轉(zhuǎn)換為byte數(shù)組

Funnel與Sink的定義

我們需要將各種類型key轉(zhuǎn)換成MurmurHash能夠直接處理的byte數(shù)組。為此我們參考guava引入下面兩個(gè)概念：

1.Funnel：將各類數(shù)據(jù)轉(zhuǎn)換成byte數(shù)組，包括int、bool、string等built-in類型及自定義的復(fù)雜類型。

2.Sink：Funnel的核心組件，作為數(shù)據(jù)的緩沖區(qū)。Funnel在將自定義的復(fù)雜類型實(shí)例轉(zhuǎn)換成byte數(shù)組時(shí)，就需要將數(shù)據(jù)拆解分批寫入sink。

Funnel可以定義成如下的委托，接受原始值，并將其寫入sink中。

delegatevoidFunnelinT(Tfrom,ISinksink);

Sink將不同類型的數(shù)據(jù)轉(zhuǎn)換成byte數(shù)組并匯總到一起。

interfaceISink

ISinkPutByte(byteb);

ISinkPutBytes(byte[]bytes);

ISinkPutBool(boolb);

ISinkPutShort(shorts);

ISinkPutInt(inti);

ISinkPutString(strings,Encodingencoding);

ISinkPutObjectT(Tobj,FunnelTfunnel);

///...其他built-in類型，讀者可自行補(bǔ)充

簡(jiǎn)單的Funnel實(shí)現(xiàn)如下所示：

publicclassFunnels

publicstaticFunnelstringStringFunnel=(from,sink)=

sink.PutString(from,Encoding.UTF8);

publicstaticFunnelintIntFunnel=(from,sink)=

sink.PutInt(from);

自定義復(fù)雜類型的Funnel實(shí)現(xiàn)則可以數(shù)據(jù)拆解分批寫入sink。復(fù)雜類型的實(shí)例成員依舊可能是復(fù)雜類型，因此我們要在Sink上實(shí)現(xiàn)一個(gè)PutObject來(lái)提供套娃式拆解。

FunnelFoofunnelFoo=(foo,sink)=

sink.PutString(foo.A,Encoding.UTF8);

sink.PutInt(foo.B);

FunnelBarfunnelBar=(bar,barSink)=barSink.PutBool(bar.C);

sink.PutObject(foo.Bar,funnelBar);

classFoo

publicstringA{get;set;}

publicintB{get;set;}

publicBarBar{get;set;}

classBar

publicboolC{get;set;}

Sink的實(shí)現(xiàn)

Sink的核心是byte數(shù)組緩沖區(qū)的實(shí)現(xiàn)，利用ArrayPool我們可以很方便的實(shí)現(xiàn)一個(gè)ByteBuffer。

classByteBuffer:IDisposable

privatereadonlyint_capacity;

privatereadonlybyte[]_buffer;

privateint_offset;

privatebool_disposed;

publicByteBuffer(intcapacity)

_capacity=capacity;

_buffer=ArrayPoolbyte.Shared.Rent(capacity);

publicvoidPut(byteb)

CheckInsertable();

_buffer[_offset]=b;

_offset++;

publicvoidPut(byte[]bytes)

CheckInsertable();

bytes.CopyTo(_buffer.AsSpan(_offset,bytes.Length));

_offset+=bytes.Length;

publicvoidPutInt(inti)

CheckInsertable();

BinaryPrimitives.WriteInt32BigEndian(GetRemainingAsSpan(),i);

_offset+=sizeof(int);

publicvoidPutShort(shorts)

CheckInsertable();

BinaryPrimitives.WriteInt32BigEndian(GetRemainingAsSpan(),s);

_offset+=sizeof(short);

//...其他的primitivetype的實(shí)現(xiàn)

publicSpanbyteGetBuffer()=

_buffer.AsSpan(.._offset);

publicboolHasRemaining()=_offset_capacity;

publicvoidDispose()

_disposed=true;

ArrayPoolbyte.Shared.Return(_buffer);

privatevoidCheckInsertable()

if(_disposed)

thrownewObjectDisposedException(typeof(ByteBuffer).FullName);

if(_offset=_capacity)

thrownewOverflowException("Bytebufferoverflow");

privateSpanbyteGetRemainingAsSpan()=_buffer.AsSpan(_offset..);

Sink則是對(duì)ByteBuffer的進(jìn)一步封裝，來(lái)適配當(dāng)前使用場(chǎng)景。

classSink:ISink,IDisposable

privatereadonlyByteBuffer_byteBuffer;

///summary

///創(chuàng)建一個(gè)新的seecref="Sink"/實(shí)例

////summary

///paramname="expectedInputSize"預(yù)計(jì)輸入的單個(gè)元素的最大大小/param

publicSink(intexpectedInputSize)

_byteBuffer=newByteBuffer(expectedInputSize);

publicISinkPutByte(byteb)

_byteBuffer.Put(b);

returnthis;

publicISinkPutBytes(byte[]bytes)

_byteBuffer.Put(bytes);

returnthis;

publicISinkPutBool(boolb)

_byteBuffer.Put((byte)(b1:0));

returnthis;

publicISinkPutShort(shorts)

_byteBuffer.PutShort(s);

returnthis;

publicISinkPutInt(inti)

_byteBuffer.PutInt(i);

returnthis;

publicISinkPutString(strings,Encodingencoding)

_byteBuffer.Put(encoding.GetBytes(s));

returnthis;

publicISinkPutObjectT(Tobj,FunnelTfunnel)

funnel(obj,this);

returnthis;

publicbyte[]GetBytes()=_byteBuffer.GetBuffer().ToArray();

publicvoidDispose()

_byteBuffer.Dispose();

k個(gè)Hash函數(shù)與布隆過(guò)濾器實(shí)現(xiàn)

上文提到了布隆過(guò)濾器通過(guò)k個(gè)hash函數(shù)來(lái)解決hash沖突問(wèn)題。實(shí)踐中，我們可以把一次murmurhash的計(jì)算結(jié)果（16byte）拆分為兩部分并轉(zhuǎn)換為long類型（一個(gè)long是8byte）。

這兩部分結(jié)果分別保存到hash2和hash3，第k個(gè)hash函數(shù)是對(duì)hash2和hash3的重新組合。

hash(k)=hash2+(k-1)*hash3

publicclassBloomFilterT

privatereadonlyint_hashFunctions;

privatereadonlyFunnelT_funnel;

privatereadonlyint_expectedInputSize;