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

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

前言

本文將以C#語言來實現(xiàn)一個簡單的布隆過濾器，為簡化說明，設(shè)計得很簡單，僅供學(xué)習(xí)使用。

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

布隆過濾器簡介

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

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

優(yōu)勢：

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

劣勢：

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

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

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

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

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

Hash沖突的解決方案

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

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

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

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

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

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

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

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

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

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

用C#實現(xiàn)Bitmap

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

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

位運算

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

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

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

//0b代表值用二進制表示數(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;

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

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

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

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

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

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

bytea=0b010100010;

byteb=13;//0b000001000

a|=b;//0b010101010

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

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

bytea=0b010101010;

byteb=13;//0b000001000

b=~b;//0b111110111

a=b;//0b010100010

3.查看指定位的值

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

bytea=0b010101010;

byteb=13;//0b000001000;

a=b;//0b000001000;

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

classBitmap

privatereadonlybyte[]_bytes;

privatereadonlylong_capacity;

publicBitmap(longcapacity)

_capacity=capacity;

_bytes=newbyte[_capacity/8+1];

publiclongCapacity=_capacity;

publicvoidSet(longindex)

if(index=_capacity)

thrownewIndexOutOfRangeException();

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

longbyteIndex=index/8;

//計算出數(shù)據(jù)存在第幾個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#實現(xiàn)布隆過濾器

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

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

MurmurHash3的使用

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

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

/darrenkopp/murmurhash-net

使用這個庫，我們可以將任意長的byte數(shù)組轉(zhuǎn)換成128位的二進制位，也就是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引入下面兩個概念：

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

2.Sink：Funnel的核心組件，作為數(shù)據(jù)的緩沖區(qū)。Funnel在將自定義的復(fù)雜類型實例轉(zhuǎn)換成byte數(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類型，讀者可自行補充

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

publicclassFunnels

publicstaticFunnelstringStringFunnel=(from,sink)=

sink.PutString(from,Encoding.UTF8);

publicstaticFunnelintIntFunnel=(from,sink)=

sink.PutInt(from);

自定義復(fù)雜類型的Funnel實現(xiàn)則可以數(shù)據(jù)拆解分批寫入sink。復(fù)雜類型的實例成員依舊可能是復(fù)雜類型，因此我們要在Sink上實現(xiàn)一個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的實現(xiàn)

Sink的核心是byte數(shù)組緩沖區(qū)的實現(xiàn)，利用ArrayPool我們可以很方便的實現(xiàn)一個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的實現(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則是對ByteBuffer的進一步封裝，來適配當(dāng)前使用場景。

classSink:ISink,IDisposable

privatereadonlyByteBuffer_byteBuffer;

///summary

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

////summary

///paramname="expectedInputSize"預(yù)計輸入的單個元素的最大大小/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函數(shù)與布隆過濾器實現(xiàn)

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

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

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

publicclassBloomFilterT

privatereadonlyint_hashFunctions;

privatereadonlyFunnelT_funnel;

privatereadonlyint_expectedInputSize;