原譯：使用Bloom Filters

仙子注：這篇文章是半年前翻譯的，最早貼于公司内部的BBS上，并引起一些争論。Bloom Filters是一種效率較高的記憶體索引算法，它本身具有沖突性：一方面能快速測試目标成員是否存在，另一方面又不可避免的具有假命中率。如下文檔僅供參考。

由于不知道如何在這裡粘貼圖檔，是以本文中沒有包含圖檔說明，請對照原文檔來閱讀，原文檔在：http://www.perl.com/pub/a/2004/04/08/bloom_filters.html?page=1   或可email給我索取中文PDF文檔。

使用Bloom Filters

原作者：Maciej Ceglowski

April 08, 2004 

任何perl使用者都熟悉hash查詢，一個存在測試的語句可以這樣寫：

foreach my $e ( @things ) { $lookup{$e}++ }

sub check {

my ( $key ) = @_;

print "Found $key!" if exists( $lookup{ $key } );

}

雖然hash查詢很有用，但對非常大的清單，或keys自身非常大時，這種查詢可能變得不實用。當查詢hash增長得太大，通常的做法是将它移到資料庫或檔案中，隻在本地緩存裡儲存最常用的關鍵字，這樣能改善性能。

許多人不知道有一種優雅的算法，用以代替hash查詢。它是一種古老的算法，叫做Bloom filter。 Bloom filter允許你在有限的記憶體裡（你想在這塊記憶體裡存放關鍵字的完整清單），執行成員測試，這樣就能避開使用磁盤或資料庫進行查詢的性能瓶頸。也許你會認為，空間的節省是有代價的：存在着可大可小的假命中率風險，并且一旦你增加key到filter後，就不能删除它。然而在許多情形下，這些局限是可接受的，bloom filter能編制有用工具。（仙子注：例如代理伺服器軟體Squid就使用了bloom filter算法。）

例如，假如你運作了一個高流量的線上音樂存儲站點，并且如果你已知歌曲存在，就可以通過僅擷取歌曲資訊的方法，來最大程度的減少資料庫壓力。你可以在啟動時建構一個bloom filter，在試圖執行昂貴的資料庫查詢前，可以用它執行快速的成員存在測試。

use Bloom::Filter;

my $filter = Bloom::Filter->new( error_rate => 0.01, capacity => $SONG_COUNT );

open my $fh, "enormous_list_of_titles.txt" or die "Failed to open: $!";

while (<$fh>) {

chomp;

$filter->add( $_ );

}

sub lookup_song {

my ( $title ) = @_;

return unless $filter->check( $title );

return expensive_db_query( $title ) or undef;

}

在該示例裡，該測試給出假命中的幾率是1%，在假命中率情況下程式會執行昂貴的資料庫索取操作，并最終傳回空結果。盡管如此，你已避開了99%的昂貴查詢時間，僅使用了用于hash查詢的一小片記憶體。更進一步，1%假命中率的filter，每個key的存儲空間在2位元組以下。這比你執行完整的hash查詢所需的記憶體少得多。

bloom filters在Burton Bloom之後命名，Burton Bloom 1970年首先在文檔裡描述了它們，文檔名Space/time trade-offs in hash coding with allowable errors.在那些記憶體稀少的日子裡，bloom filters因其簡潔而倍受重視。事實上，最早的應用之一是拼寫檢查程式。然而，由于有少數非常明顯的特性，該算法特别适合社會軟體應用。

因為bloom filters使用單向hash來存儲資料，是以不可能在不做窮舉搜尋的情況下，重建filter裡的keys清單。甚至這點看起來并非象很有用，既然來自窮舉搜尋的假命中會覆寫掉真正的keys清單。是以bloom filters能在不向全世界廣播完整清單的情況下，共享關于已有資料的資訊。因為這個理由，它們在peer-to-peer應用中特别有用，在這個應用中大小和隐私是重要的限制。

bloom filters如何工作

bloom filter由2部分組成：1套k hash函數，1個給定長度的位向量。選擇位向量的長度，和hash函數的數量，依賴于我們想增加多少keys到設定中，以及我們能容忍的多高的假命中率。

bloom filter中所有的hash函數被配置過，其範圍比對位向量的長度。例如，假如向量是200位長，hash函數傳回的值就在1到200之間。在filter裡使用高品質的hash函數相當重要，它保證輸出等分在所有可能值上－－hash函數裡的“熱點”會增加假命中率。（仙子注：所謂“熱點”是指結果過分頻繁的分布在某些值上。）

要将某個key輸入bloom filer中，我們在每個k hash函數裡周遊它，并将結果作為在位向量裡的offsets，并打開我們在該offsets上找到的任何位。假如該位已經設定，我們繼續保留其打開。還沒有在bloom filter裡關閉位的機制。

在本示例裡，讓我們看看某個bloom filter，它有3個hash函數，并且位向量的長度是14。我們用空格和星号來表示位向量，以便于觀察。你也許想到，空的bloom filter以所有的位關閉為開始，如圖1所示。

圖1：空的bloom filter

現在我們将字元apples增加到filter中去。為了做到這點，我們以apples為參數來運作每個hash函數，并采集輸出：

hash1("apples") = 3

hash2("apples") = 12

hash3("apples") = 11

然後我們打開在向量裡相應位置的位－－在這裡就是位3，11，和12，如圖2所示。

圖2：激活了3位的bloom filter

為了增加另1個key，例如plums，我們重複hash運算過程：

hash1("plums") = 11

hash2("plums") = 1

hash3("plums") = 8

再次打開向量裡相應的位，如圖3裡的高亮度顯示。

圖3：增加了第2個key的bloom filter

注意位置11的位已被打開－－在前面的步驟裡，當我們增加apples時已設定了它。位11現在有雙重義務，存儲apples和plums兩者的資訊。當增加更多的keys時，它也會存儲其他keys的資訊。這種交疊讓bloom filters如此緊湊－－任何位同時編碼多個keys。這種交疊也意味着你永不能從filter裡取出key，因為你不能保證你所關閉的位沒有攜載其他keys的資訊。假如我們試圖執行反運算過程來從filter裡删除apples，就會不經意的關閉編碼plums的1個位。從bloom filter裡剝離key的唯一方法是重建filter，剔除無用key。

檢查是否某個key已經存在于filter的過程，非常類似于增加新key。我們在所有的hash函數裡周遊key，然後檢查是否在那些offsets上的位都是打開的。假如任何一位關閉，我們知道該key肯定不存在于filter中。假如所有位都打開，我們知道該key可能存在。

我說“可能”是因為存在一種情況，該key是個假命中。例如，假如我們用字元mango來測試filter，看看會發生什麼情況。我們運作mango周遊hash函數：

hash1("mango") = 8

hash2("mango") = 3

hash3("mango") = 12

然後檢查在那些offsets上的位，如圖4所示。

圖4：bloom filter的假命中

所有在位置3，8，和12的位都是打開的，故filter會報告mango是有效key。

當然，mango并非有效key－－我們建構的filter僅包含apples和plums。事實是mango的offsets非常巧合的指向了已激活的位。這就找到了1個假命中－－某個key看起來位于filter中，但實際不是。

正如你想的一樣，假命中率依賴于位向量的長度和存儲在filter裡的keys的數量。位向量越寬闊，我們檢查的所有k位被打開的可能性越小，除非該key确實存在于filter中。在hash函數的數量和假命中率之間的關系更敏感。假如使用的hash函數太少，在keys之間的差别就很少；但假如使用hash函數太多，filter會過于密集，增加了沖突的可能性。可以使用如下公式來計算任何filter的假命中率：

c = ( 1 - e(-kn/m) )k

這裡c是假命中率，k是hash函數的數量，n是filter裡keys的數量，m是filter的位長。

當使用bloom filters時，我們先要有個意識，期待假命中率多大；也應該有個粗糙的想法，關于多少keys要增加到filter裡。我們需要一些方法來驗證需要多大的位向量，以保證假命中率不會超出我們的限制。下列方程式會從錯誤率和keys數量求出向量長度：

m = -kn / ( ln( 1 - c ^ 1/k ) )

請注意另1個自由變量：k，hash函數的數量。可以用微積分來得出k的最小值，但有個偷懶的方法來做它：

sub calculate_shortest_filter_length {

my ( $num_keys, $error_rate ) = @_;

my $lowest_m;

my $best_k = 1;

foreach my $k ( 1..100 ) {

my $m = (-1 * $k * $num_keys) / 

( log( 1 - ($error_rate ** (1/$k))));

if ( !defined $lowest_m or ($m < $lowest_m) ) {

$lowest_m = $m;

$best_k   = $k;

}

}

return ( $lowest_m, $best_k );

}

為了給你直覺的感覺，關于錯誤率和keys數量如何影響bloom filters的存儲size，表1列出了一些在不同的容量/錯誤率組合下的向量size。

ErrorRate   Keys   RequiredSize   Bytes/Key 

1%           1K       1.87 K         1.9 

0.1%         1K       2.80 K         2.9 

0.01%        1K       3.74 K         3.7 

0.01%       10K       37.4 K         3.7 

0.01%      100K        374 K         3.7 

0.01%        1M       3.74 M         3.7 

0.001%       1M       4.68 M         4.7 

0.0001%      1M       5.61 M         5.7 

在Perl裡建構bloom filter

為了建構1個工作bloom filter，我們需要1套良好的hash函數。這些容易解決－－在CPAN上有幾個優秀的hash算法可用。對我們的目的來說，較好的選擇是Digest::SHA1，它是強度加密的hash，用C實作速度很快。通過對不同值的輸出清單進行排序，我們能使用該子產品來建立任意數量的hash函數。如下是建構唯一hash函數清單的子函數：

use Digest::SHA1 qw/sha1/;

sub make_hashing_functions {

my ( $count ) = @_;

my @functions;

for my $salt (1..$count ) {

push @functions, sub { sha1( $salt, $_[0] ) };

}

return @functions;

}

為了能夠使用這些hash函數，我們必須找到1個方法來控制其範圍。Digest::SHA1傳回令人為難的過長160位hash輸出，這僅在向量長度為2的160次方時有用，而這種情況實在罕見。我們結合使用位chopping和division來将輸出削減到可用大小。

如下子函數取某個key，運作它周遊hash函數清單，并傳回1個長度（$FILTER_LENGTH）的位掩碼：

sub make_bitmask {

my ( $key ) = @_;

my $mask    = pack( "b*", '0' x $FILTER_LENGTH);

foreach my $hash_function ( @functions ){ 

my $hash       = $hash_function->($key);

my $chopped    = unpack("N", $hash );

my $bit_offset = $result % $FILTER_LENGTH;

vec( $mask, $bit_offset, 1 ) = 1;       

}

return $mask;

}

讓我們逐行分析上述代碼：

my $mask = pack( "b*", '0' x $FILTER_LENGTH);

我們以使用perl的pack操作來建立零位向量開始，它是$FILTER_LENGTH長。pack取2個參數，1個模型和1個值。b模型告訴pack将值解釋為bits，*指“重複任意多需要的次數”，跟正規表達式類似。perl實際上會補充位向量的長度為8的倍數，但我們将忽視這些多餘位。

有1個空的位向量在手中，我們準備開始運作key周遊hash函數：

my $hash = $hash_function->($key);

my $chopped = unpack("N", $hash );

我們儲存首個32位輸出，并丢棄剩下的。這點可讓我們不必要求BigInt支援。第2行做實際的位chopping。模型裡的N告訴unpack以網絡位元組順序來解包32位整數。因為未在模型裡提供任何量詞，unpack僅解包1個整數，然後終止。

假如你對位chopping過度狂熱，你可以将hash分割成5個32位的片斷，并對它們一起執行OR運算，将所有資訊儲存在原始hash裡：

my $chopped = pack( "N", 0 );

my @pieces  =  map { pack( "N", $_ ) } unpack("N*", $hash );

$chopped    = $_ ^ $chopped foreach @pieces;

但這樣作可能殺傷力過度。

現在我們有了來自hash函數的32位整數輸出的清單，下一步必須做的是，裁減它們的大小，以使其位于（1..$FILTER_LENGTH）範圍内。

my $bit_offset = $chopped % $FILTER_LENGTH;

現在我們已轉換key為位offsets清單，這正是我們所求的。

剩下唯一要做的事情是，使用vec來設定位，vec取3個參數：向量自身，開始位置，要設定的位數量。我們能象指派給變量一樣來配置設定值給vec：

vec( $mask, $bit_offset, 1 ) = 1;

在設定了所有位後，我們以1個位掩碼來結束，位掩碼和bloom filter長度一樣。我們可以使用這個掩碼來增加key到filter中：

sub add {

my ( $key, $filter ) = @_;

my $mask = make_bitmask( $key );

$filter  = $filter | $mask;

}

或者我們使用它來檢查是否key已存在：

sub check {

my ( $key, $filter ) = @_;

my $mask  = make_bitmask( $key );

my $found = ( ( $filter & $mask ) eq $mask );

return $found;

}

注意這些是位邏輯運算符OR(|)和AND(&)，而并非通用的邏輯OR(||)和AND(&&)運算符。将這兩者混在一起，會導緻數小時的有趣調試。第1個示例将掩碼和位向量進行OR運算，打開任何未設定的位。第2個示例将掩碼和filter裡相應的位置進行比較－－假如掩碼裡所有的打開位也在filter裡打開，我們知道已找到一個比對。

一旦你克服了使用vec,pack和位邏輯運算符的難度，bloom filters實際非常簡單。http://www.perl.com/2004/04/08/examples/Filter.pm 這裡給出了Bloom::Filter子產品的完整資訊。

分布式社會網絡中的bloom filters

目前的社會網絡機制的弊端之一是，它們要求參與者洩露其聯系清單給中央伺服器，或公布它到公共Internet，這2種情況下都犧牲了大量的使用者隐私。通過交換bloom filters而不是暴露聯系清單，使用者能參與社會網絡實踐，而不用通知全世界他們的朋友是誰。編碼了某人聯系資訊的bloom filter能用來檢查它是否包含了給定的使用者名或email位址，但不能強迫要求它展示用于建構它的完整keys清單。甚至有可能将假命中率（雖然它聽起來不像好特性），轉換為有用工具。

假如我非常關注這些人，他們通過對bloom filter運作字典攻擊，來試圖對社會網絡進行反工程。我可以建構filter，它具備較高的假命中率（例如50%），然後發送filter的多個拷貝給朋友，并變換用于建構每個filter的hash函數。我的朋友收集到的filters越多，他們見到的假命中率越低。例如，在5個filters情況下，假命中率是0.5的5次方，或3%－－通過發送更多filters，還能進一步減少假命中率。

假如這些filters中的任何一個被中途截取，它會展示全部50%的假命中率。是以我能隔離隐私風險，并且一定程度上能控制其他人能多清楚的

了解我的網絡。我的朋友能較高程度的确認是否某個人位于聯系清單裡，但那些僅截取了1個或2個filters的人，幾乎不會擷取到什麼。如下是個perl函數，它對1組嘈雜的filters檢查某個key：

use Bloom::Filter;

sub check_noisy_filters {

my ( $key, @filters ) = @_;

foreach my $filter ( @filters ) {

return 0 unless $filter->check( $key );

}

return 1;

}

假如你和你的朋友同意使用相同的filter長度和hash函數設定，你也能使用位掩碼對比來估計在你們的社會網絡之間的交疊程度。在2個bloom filters裡的共享位數量會給出1個可用的距離度量。

sub shared_on_bits {

my ( $filter_1, $filter_2 ) = @_;

return unpack( "%32b*",  $filter_1 & $filter_2 )

}

另外，你能使用OR運算，結合2個有相同長度和hash函數的bloom filters來建立1個複合filter。例如，假如你參與某個小型郵件清單，并希望基于組裡每個人的位址本來建立白名單，你可以為每個參與者獨立的建立1個bloom filter，然後将filters一起進行OR運算，将結果輸入Voltron-like主清單。組裡成員不會了解到其他成員的聯系資訊，并且filter仍能展示正确的行為。

肯定還有其他針對社會網絡和分布式應用的bloom filter妙用。如下參考列出一些有用資源。