可加速最長前綴匹配的布隆過濾查找方案*

王 乾，喬廬峰，陳慶華

（陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210001）

0 引言

近年來IPv4 地址逐漸被耗盡，無類域間路由（CIDR）被提出用來緩解地址耗盡的問題，CIDR要求路由器搜索可變長度的地址前綴，以便找到與IP 目的地址相匹配的最長前綴[1]。這種占用大量計(jì)算資源的任務(wù)（通常稱為IP 查找）通常是高性能路由器的性能瓶頸。盡管基于LPM 的算法已取得重大進(jìn)展，但大多數(shù)商用路由器設(shè)計(jì)人員還是使用三態(tài)內(nèi)容可尋址存儲(chǔ)器（TCAM）設(shè)備，以與光鏈路速度保持同步，盡管其尺寸，成本和功耗比高速DDR 存儲(chǔ)器更大。使用外部存儲(chǔ)器時(shí)的查找速度通常被訪問片外存儲(chǔ)器次數(shù)限制。使用共享內(nèi)存的方案只能順序執(zhí)行查找而使用獨(dú)立內(nèi)存的方案可以并行查找。一些算法通過流水線掩蓋相關(guān)的內(nèi)存訪問，每個(gè)階段訪問一個(gè)獨(dú)立的內(nèi)存[2]。但是，這很快成為昂貴的選擇。

本文提出了將布隆過濾器用于最長前綴匹配的一種查找方案。布隆過濾器是一種有效的數(shù)據(jù)結(jié)構(gòu)通常用于有效的精確匹配。然而由于過濾器中使用了哈希算法所以可能會(huì)產(chǎn)生誤報(bào)，誤報(bào)的概率取決于存儲(chǔ)在過濾器中的條目數(shù)，過濾器的大小以及用于探查過濾器的哈希函數(shù)的數(shù)量。我們的方案將一個(gè)布隆過濾器與一個(gè)唯一的長度相關(guān)聯(lián)，搜索時(shí)使用輸入IP 對所有布隆過濾器并行執(zhí)行成員資格查詢，此步驟得到匹配前綴長度的向量，其中某些長度可能因?yàn)檎`報(bào)產(chǎn)生錯(cuò)誤。按照向量中最長匹配到向量中最短匹配的順序探查與每個(gè)前綴長度相對應(yīng)的哈希表，在找到匹配項(xiàng)或搜索到向量中表示的所有長度時(shí)終止[3]。本方案的關(guān)鍵特征在于對于更長的地址長度或轉(zhuǎn)發(fā)表中其他唯一的地址前綴長度而言，由每次查找所依賴的內(nèi)存訪問次數(shù)決定的性能可以保持恒定。

1 布隆過濾器

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，用于簡潔地表示一組消息。首先使用集合中的每個(gè)消息對過濾器進(jìn)行編程，然后查詢以確定特定消息的成員身份。它是由B.H.Bloom 在1970 年提出的[4]，廣泛用于Web 緩存，入侵檢測和基于內(nèi)容的路由[5]等不同目的。我們在本小節(jié)中解釋布隆過濾器的理論。

布隆過濾器本質(zhì)上是一個(gè)長度的位向量（在本文中我們用Vector 表示），用于有效表示一組消息。給定一組帶有成員的消息X，將對布隆過濾器進(jìn)行編程，如下所示。對于每個(gè)消息xi，k個(gè)哈希函數(shù)hi(),…,hk()，將得到k個(gè)在1 到m之間的值。這些值中的每一個(gè)都尋址向量中的單個(gè)位并將其設(shè)置為1。請注意，如果其中一個(gè)哈希值尋址的是已設(shè)置為1的位，則該位不會(huì)更改。以下偽代碼描述了將消息添加到Bloom 過濾器。

算法1 Old_BFAdd

1）for(i=1 to k)

2）Vector[hi(x)]=1

在過濾器中查詢給定消息的集合成員身份類似于編程過程。給定消息，使用與添加時(shí)相同的哈希函數(shù)計(jì)算哈希值。檢查與哈希值相對應(yīng)的位置處比特位是否為1。如果這些位至少有一個(gè)0 則該消息沒有成員資格。如果發(fā)現(xiàn)所有位均為1，則認(rèn)為該消息具有一定概率屬于該集合。如果發(fā)現(xiàn)所有位均為1 且不是的成員，則為假陽性。以下偽代碼描述了查詢過程。

算法2 BFQuery

1）for(i=1 to k)

2）if (Vector[hi(x)]=0)return false

3）return true

假陽性的產(chǎn)生由于以下原因：Vector 中的位可以由任意成員設(shè)置，而哈希算法會(huì)有沖突的產(chǎn)生，不同的成員通過哈希算法可能映射到Vector 中的同一個(gè)位置。因此，即使成員對應(yīng)的位為1 并不意味著集合中存在該消息，可能是其他消息因?yàn)楣_突將該位置1。但是，如果有為0 的比特位則該成員必定存在不存在于集合中，因?yàn)槿绻蓡T存在則對布隆過濾器進(jìn)行編程時(shí)會(huì)將所有位都設(shè)置為1。

布隆過濾器的誤報(bào)概率推導(dǎo)過程如下：假設(shè)我們使用的哈希函數(shù)分布均勻，通過哈希函數(shù)將具有m比特向量其中一個(gè)比特設(shè)置為1 的概率為1/m。則未設(shè)置為1 的概率為1-(1/m)，n個(gè)成員都沒有將該位設(shè)置為1 的概率為1-(1/m)n。因?yàn)槊總€(gè)成員會(huì)使用k個(gè)哈希函數(shù)將k個(gè)位置設(shè)置為1 所以該概率變?yōu)?1-(1/m))kn。因此該位被設(shè)置為1 的概率為(1-(1-(1/m))kn)。如果要判定一個(gè)成員存在集合中那么需要將k位設(shè)置為1，設(shè)該概率為f，則f的表達(dá)式如式（1）所示。

當(dāng)m足夠大時(shí)f簡化為如式（2）所示。

對于給定的m和n，可以改變k的值達(dá)到最低的誤報(bào)概率，當(dāng)k值如下時(shí)誤報(bào)概率最?。?/p>

此時(shí)誤報(bào)概率為式（4）所示。

2 并行可刪除布隆過濾器

基礎(chǔ)的布隆過濾器將k個(gè)哈希函數(shù)映射到同一個(gè)向量中如圖1（a）所示，而使用硬件實(shí)現(xiàn)時(shí)無法使用數(shù)組結(jié)構(gòu)，通常使用RAM 來實(shí)現(xiàn)，因此k個(gè)函數(shù)就需要訪問k次RAM，對存儲(chǔ)器的多次訪問會(huì)成為性能瓶頸。為了解決多次訪問的問題我們提出了改進(jìn)的基礎(chǔ)方案如圖1（b）,此方案使用了2個(gè)向量和2 個(gè)哈希函數(shù)，每個(gè)哈希函數(shù)對應(yīng)一個(gè)向量，這樣過濾的時(shí)候可以同時(shí)訪問兩個(gè)向量獲取兩個(gè)哈希位對應(yīng)的值，只需要訪問一次內(nèi)存就能得到過濾結(jié)果。在圖2 中可以看到隨著成員的增加哈希函數(shù)的概率呈指數(shù)增長，因此當(dāng)存儲(chǔ)一定表項(xiàng)時(shí)基礎(chǔ)的方案中因?yàn)楣_突將無法添加成員資格，因此我們提出了改進(jìn)的基礎(chǔ)方案如圖1（c）,在該方案中我們用雙口RAM 來實(shí)現(xiàn)向量，雙口RAM 有a,b 口可以同時(shí)讀取數(shù)據(jù)。同時(shí)使用了四個(gè)哈希函數(shù)h1,h2,h3 和h4，h1 和h2 分別在兩個(gè)向量的a 口讀取數(shù)據(jù)，h3 和h4 分別在兩個(gè)向量b 口讀取數(shù)據(jù)。添加成員資格時(shí)當(dāng)h1 和h2 對應(yīng)的位置不全為0 可以使用h3 和h4 進(jìn)行探測，如果h3 和h4 對應(yīng)位置全為0 則將h3 和h4 對應(yīng)的位置設(shè)置為1。此時(shí)添加IP 的偽代碼如下：

算法3BFAdd

布隆過濾器的另一個(gè)致命缺點(diǎn)是不能刪除成員資格[6]。刪除成員資格時(shí)會(huì)將成員對應(yīng)的哈希位設(shè)置為0，如果有其他成員的哈希值也映射到該位置則其他成員的資格也會(huì)被刪除，查表時(shí)會(huì)造成丟包這是我們不能接受的。

在我們的方案中產(chǎn)生無法刪除成員的原因只有一個(gè)，其他成員將待刪除成員的剩余為0 的位置全部設(shè)置為1 也就是待刪除成員h1,h2,h3 和h4 對應(yīng)的位置全部為1，此時(shí)我們無法確定是將h1,h2 對應(yīng)的位置設(shè)置為0 還是將h3,h4 對應(yīng)的位置設(shè)置為0。為解決該問題我們設(shè)置了一塊FIFO 來存儲(chǔ)無法刪除的成員，每過一定時(shí)鐘周期就在FIFO 中讀出一個(gè)成員重新進(jìn)行刪除，如果無法刪除就將該成員重新寫入到FIFO 中。如此循環(huán)的目的是為了等待產(chǎn)生沖突的其他成員被刪除。

以添加15,17 和36 的成員資格為例，表1 中為其對應(yīng)的哈希值，當(dāng)添加36 的成員資格時(shí)h1 和h2對應(yīng)的位置都為1，所以將h3 和h4 對應(yīng)的位置設(shè)置為1。添加完成后過濾器為圖3（a）。添加完成后刪除36 成員資格時(shí)四個(gè)哈希探針對應(yīng)的位置都為1 此時(shí)將36 寫入到FIFO 中，繼續(xù)刪除15 成員資格，刪除后如圖3（b），如果此時(shí)在在FIFO 中讀出36 則可刪除成功。

圖1 布隆過濾器結(jié)構(gòu)

圖2 哈希沖突概率

圖3 過濾器刪除過程

3 系統(tǒng)配置

每次查找所需的內(nèi)存訪問數(shù)通常是查找算法的性能瓶頸。隨著半導(dǎo)體技術(shù)的發(fā)展，高端FPGA 的系統(tǒng)頻率可以達(dá)到300MHz,能夠進(jìn)行大規(guī)模并行運(yùn)算，并且片內(nèi)有數(shù)Mb 的RAM 可以使用。我們的方案基于FPGA 實(shí)現(xiàn)搭配外部DDR 每次查找基本只需要一次片外DDR 訪問。

以IPv4 為例，查找最長匹配前綴的簡單方法是使用哈希表，將每個(gè)長度的前綴都分配一個(gè)哈希表，表內(nèi)存儲(chǔ)前綴和對應(yīng)的下一跳信息。進(jìn)行路由查找時(shí)從前綴長度最長的哈希表進(jìn)行查找，依次查找前綴長度更短的哈希表，當(dāng)找到匹配的前綴時(shí)停止查找返回對應(yīng)的下一跳信息。為了便于討論我們假設(shè)哈希表內(nèi)沒有沖突，查找哈希表時(shí)只需要一次存儲(chǔ)器訪問。這種方法最壞情況下需要訪問32 次片外DDR。但是我們通過使用FPGA 片內(nèi)的并行布隆過濾器將查找范圍縮小到有限的幾張哈希表內(nèi)，因此可以將訪問次數(shù)降低到幾乎單次。

我們的系統(tǒng)配置如圖4 所示。我們將相同長度的前綴集中為一個(gè)集合，并將該集合存儲(chǔ)在布隆過濾器中。我們將布隆過濾器存儲(chǔ)在FPGA 的片內(nèi)RAM 中以便并行操作，每個(gè)過濾器對應(yīng)一個(gè)單獨(dú)的前綴長度。在查詢哈希表之前我們先將IP 送到32 個(gè)布隆過濾器中進(jìn)行過濾。注意，布隆過濾會(huì)產(chǎn)生假陽性但絕不會(huì)產(chǎn)生假陰性，假陽性的后果是我們浪費(fèi)了內(nèi)存訪問次數(shù)，并不會(huì)造成錯(cuò)誤的最長前綴匹配。如果過濾結(jié)果為假陽性，那么對應(yīng)的哈希表內(nèi)我們將會(huì)匹配失敗繼續(xù)匹配其他哈希表。假陽性是無法避免的我們只能盡力降低過濾器的假陽性概率。

由于我們將布隆過濾器全部存儲(chǔ)在FPGA片內(nèi)，所以我們可以對32 個(gè)過濾器同時(shí)進(jìn)行匹配。在我們的實(shí)驗(yàn)中需要3 個(gè)時(shí)鐘周期得到匹配結(jié)果，

其中讀取RAM 就需要花費(fèi)兩個(gè)時(shí)鐘周期。過濾結(jié)束后會(huì)得到32 比特的匹配向量。我們使用優(yōu)先級(jí)編碼器對過濾得到的向量進(jìn)行優(yōu)先級(jí)編碼然后從長到短的查找對應(yīng)哈希表以找到最長的匹配前綴。以下偽代碼描述了對IP 地址I 的查找過程。

算法4 LOOKUP(I)

1）for (j=32 to 1)

2）MatchVector[j]=BFQueryj(Ij)

3）for(j=32 to 1)

4）if(MatchVector[j]==1)

5）{prefix,NextHop}=HashTableLookupj(Ij)

6）if(prefix=Ij)return{prefix,NextHop}

7）return {NULL,DefaultHop}

在上面的偽代碼中Ij表示I 的高j 比特，BFQuery 表示查詢該前綴長度的布隆過濾器的過程。第1-2 行的代碼在FPGA 中并行實(shí)現(xiàn)。

圖4 系統(tǒng)配置

4 性能分析

在第2 節(jié)中我們已經(jīng)得出布隆過濾器的誤報(bào)概率公式（3），首先說明使用變量的意義，mi為每個(gè)過濾器占用的存儲(chǔ)資源，ni為每個(gè)過濾器中的前綴數(shù)量，M為分配給布隆過濾器的存儲(chǔ)資源總量，N為系統(tǒng)支持的前綴數(shù)量。假設(shè)每個(gè)布隆過濾器的概率都相等則得到以式（5）：

這說明

因此給定濾波器的誤報(bào)概率可以表示為：

因此當(dāng)所有過濾器的誤報(bào)概率相等時(shí)，系統(tǒng)性能就與前綴分布無關(guān)，對于IPv4 每次查詢的平均哈希探測次數(shù)可表示為：

圖5 中為不同前綴數(shù)量下布隆過濾器占用內(nèi)存與片外DDR 訪問次數(shù)的關(guān)系，可以看到為過濾器分配2 Mb 內(nèi)存時(shí)對于100000 條前綴，平均探測次數(shù)接近1 次。

圖5 過濾器大小與訪問DDR 次數(shù)關(guān)系

仿真時(shí)我們使用Modelsim 10.6d 和Vivado2018.1，芯片選擇xc7vx690ttfg。我們使用實(shí)際IPv4 的BGP表來構(gòu)造轉(zhuǎn)發(fā)表。為了說明輸入地址對DDR 訪問次數(shù)的影響，我們從完全隨機(jī)的IP 地址逐漸過渡到轉(zhuǎn)發(fā)表中存在的地址，每次測試使用10 萬個(gè)IP地址。實(shí)驗(yàn)結(jié)果表明使用完全隨機(jī)的地址時(shí)布隆過濾器均不會(huì)產(chǎn)生誤報(bào)，隨著轉(zhuǎn)發(fā)表中存在的地址增多，DDR 訪問次數(shù)會(huì)逐漸上升，當(dāng)流量中的IP 地址全部來自轉(zhuǎn)發(fā)表時(shí)達(dá)到最大的訪問次數(shù)。表1 為使用5 個(gè)數(shù)據(jù)庫中的流量進(jìn)行測試時(shí)的理論值和實(shí)際觀測值?？梢钥吹綄?shí)際觀測值與理論值接近，平均誤報(bào)率幾乎為1。使用800MHz 的DDR3 搭配200MHz的FPGA芯片實(shí)現(xiàn)時(shí)每秒可實(shí)現(xiàn)30M次查詢。

表1 M=2Mb 6 個(gè)IPv4BGP 表的平均哈希探測次數(shù)

5 結(jié)語

我們通過使用布隆過濾算法將查找范圍精確定位到少量哈希表內(nèi)，降低了LPM 算法的平均訪問存儲(chǔ)器次數(shù)。為了進(jìn)一步優(yōu)化性能，我們將布隆過濾器改為雙向量的結(jié)構(gòu)使其適合硬件實(shí)現(xiàn)可以并行過濾降低了查找延遲提高了端口吞吐率。性能分析和仿真實(shí)驗(yàn)表明，該方案平均訪問片外存儲(chǔ)器次數(shù)小于兩次，幾乎接近一次。

使用200MHz 的FPGA 芯片搭配頻率為800MHz 的DDR3 實(shí)現(xiàn)可提供每秒30M 次的查詢。盡管仍低于TCAM 但是TCAM 的每位存儲(chǔ)的功耗比DDR 高10 倍，并且隨著半導(dǎo)體技術(shù)的發(fā)展DDR 和FPGA 的頻率會(huì)逐漸提升，該方案可以移植到性能更高的平臺(tái)以達(dá)到更快的查找速度。