第C#實現從位圖到布隆過濾器的方法目錄前言布隆過濾器簡介數據的存儲Hash沖突的解決方案為什么布隆過濾器不支持刪除用C#實現Bitmap位運算利用位運算創建Bitmap用C#實現布隆過濾器MurmurHash3的使用將任意類型的key轉換為byte數組Funnel與Sink的定義Sink的實現k個Hash函數與布隆過濾器實現擴展帶計數器的布隆過濾器分布式布隆過濾器實現方案代碼地址

前言

本文將以C#語言來實現一個簡單的布隆過濾器，為簡化說明，設計得很簡單，僅供學習使用。

感謝@時總百忙之中的指導。

布隆過濾器簡介

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

相較于.NET中的HashSet這樣傳統的HashTable，存在以下的優劣勢。

優勢：

占用的存儲空間較小。不需要像HashSet一樣存儲Key的原始數據。

劣勢：

存在誤判率，過濾器認為不存在的數據一定不存在，但是認為存在的數據不一定真的存在。這個和布隆過濾器的實現方式有關。不支持數據的刪除，下文會講為什么不支持刪除。

數據的存儲

布隆過濾器的數據保存在位圖（Bitmap）上。Bitmap簡而言之是二進制位（bit）的數組。HashTable保存每個元素的位置，我們稱之為桶（bucket），Bitmap上的每一位就是布隆過濾器的bucket。

布隆過濾器的每一個bucket只能存儲0或1。數據插入時，布隆過濾器會通過Hash函數計算出插入的key對應的bucket，并將該bucket設置為1。

查詢時，再次根據Hash函數計算出key對應的bucket，如果bucket的值是1，則認為key存在。

Hash沖突的解決方案

布隆過濾器使用了Hash函數，自然也逃不過Hash沖突的問題。對布隆過濾器而言，發生Hash沖突也就意味著會發生誤判。

傳統Hash算法解決Hash沖突的方式有開放定址法、鏈表法等。而布隆過濾器解決Hash沖突的方式比較特殊，它使用了多個Hash函數來解決沖突問題。

下圖中插入布隆過濾器的Bar和Baz經過Hash2計算出的位置是同一個，但Hash3計算出的位置是不一樣的，Bar和Baz得以區分。

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

由于布隆過濾器不保留插入的Key的原始值，Hash沖突是無法避免的。我們只能通過增加Hash函數的數量來減少沖突的概率，也就是減少誤判率。

假設布隆過濾器有m個bucket，包含k個哈希函數，已經插入了n個key。經數學推導可得誤判率的公式如下：

具體推斷過程可參考/wiki/Bloom_filter。

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

為什么布隆過濾器不支持刪除

布隆過濾器通過多個Hash函數來解決沖突的設計，也意味著多著插入元素可能會共享同樣的bucket，刪掉一個元素的同時，也會被其他元素的一部分bucket給刪掉。因此基于Bitmap實現的布隆過濾器是不支持刪除的。

用C#實現Bitmap

在實現布隆過濾器之前，我們首先要實現一個Bitmap。

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

位運算

下面是C#中位運算的簡單介紹：

符號描述運算規則與兩個位都為1時，結果才為1|或兩個位都為0時，結果才為0^異或兩個位相同為0，相異為1~取反0變1，1變0左移各二進位全部左移若干位，低位補0右移各二進位全部右移若干位，高位補0

一般來說，我們要進行位運算計算的數據通常都是由多個二進位組成的。對兩個數字使用、|、^這三個運算符時，需要對齊兩個數字的右邊，一位位地進行計算。

//0b代表值用二進制表示數字

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;

利用位運算創建Bitmap

借助byte實現Bitmap，也就是要能夠修改和查看byte上的每一個bit的值，同時，修改要能夠實現冪等。

1.指定位設置成1

按前面說的位運算的規則，是不能夠單獨修改bit序列中某一位的。位運算需要從右到左一對對計算。

使用|可以實現這個功能。假設我們要改變從右開始下標為3（初始位置0）的bit的值，則需要準備一個該位置為1，其他位置都是0的bit序列，與要改變的bit序列進行|運算。

//為了將a的右邊數起第3位改成1，需要準備一個b

bytea=0b010100010;

byteb=13;//0b000001000

a|=b;//0b010101010

2.指定位設置成0

和設置成1正好相反，需要準備一個指定位置為0，其他位置都是1的bit序列，與要改變的bit序列進行運算。

bytea=0b010101010;

byteb=13;//0b000001000

b=~b;//0b111110111

a=b;//0b010100010

3.查看指定位的值

利用運算符，只要計算結果不為0，就代表指定位置的值為1。

bytea=0b010101010;

byteb=13;//0b000001000;

a=b;//0b000001000;

了解了基本的操作之后，我們把數據存儲到byte數組上。

classBitmap

privatereadonlybyte[]_bytes;

privatereadonlylong_capacity;

publicBitmap(longcapacity)

_capacity=capacity;

_bytes=newbyte[_capacity/8+1];

publiclongCapacity=_capacity;

publicvoidSet(longindex)

if(index=_capacity)

thrownewIndexOutOfRangeException();

//計算出數據存在第幾個byte上

longbyteIndex=index/8;

//計算出數據存在第幾個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#實現布隆過濾器

有了Bitmap，我們再把Hash函數的實現準備好，一個簡單的布隆過濾器就可以完成了。這里，我們參考guava這個java庫的實現。

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

MurmurHash3的使用

我們使用和guava一樣的MurmurHash3作為Hash函數的實現。

下面是筆者在github上找到的一個可用實現。

/darrenkopp/murmurhash-net

使用這個庫，我們可以將任意長的byte數組轉換成128位的二進制位，也就是16byte。

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

//returnsa128-bitalgorithmusing"unsafe"codewithdefaultseed

HashAlgorithmmurmur128=MurmurHash.Create128(managed:false);

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

將任意類型的key轉換為byte數組

Funnel與Sink的定義

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

1.Funnel：將各類數據轉換成byte數組，包括int、bool、string等built-in類型及自定義的復雜類型。

2.Sink：Funnel的核心組件，作為數據的緩沖區。Funnel在將自定義的復雜類型實例轉換成byte數組時，就需要將數據拆解分批寫入sink。

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

delegatevoidFunnelinT(Tfrom,ISinksink);

Sink將不同類型的數據轉換成byte數組并匯總到一起。

interfaceISink

ISinkPutByte(byteb);

ISinkPutBytes(byte[]bytes);

ISinkPutBool(boolb);

ISinkPutShort(shorts);

ISinkPutInt(inti);

ISinkPutString(strings,Encodingencoding);

ISinkPutObjectT(Tobj,FunnelTfunnel);

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

簡單的Funnel實現如下所示：

publicclassFunnels

publicstaticFunnelstringStringFunnel=(from,sink)=

sink.PutString(from,Encoding.UTF8);

publicstaticFunnelintIntFunnel=(from,sink)=

sink.PutInt(from);

自定義復雜類型的Funnel實現則可以數據拆解分批寫入sink。復雜類型的實例成員依舊可能是復雜類型，因此我們要在Sink上實現一個PutObject來提供套娃式拆解。

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的實現

Sink的核心是byte數組緩沖區的實現，利用ArrayPool我們可以很方便的實現一個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的實現

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則是對ByteBuffer的進一步封裝，來適配當前使用場景。

classSink:ISink,IDisposable

privatereadonlyByteBuffer_byteBuffer;

///summary

///創建一個新的seecref="Sink"/實例

////summary

///paramname="expectedInputSize"預計輸入的單個元素的最大大小/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個Hash函數與布隆過濾器實現

上文提到了布隆過濾器通過k個hash函數來解決hash沖突問題。實踐中，我們可以把一次murmurhash的計算結果（16byte）拆分為兩部分并轉換為long類型（一個long是8byte）。

這兩部分結果分別保存到hash2和hash3，第k個hash函數是對hash2和hash3的重新組合。

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

publicclassBloomFilterT

privatereadonlyint_hashFunctions;

privatereadonlyFunnelT_funnel;

privatereadonlyint_expectedInputSize;