許 可 李彥彪 謝高崗 張大方

1（湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082）

2（中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心 北京 100083）

3（中國科學(xué)院大學(xué) 北京 100089）

路由查找轉(zhuǎn)發(fā)是網(wǎng)絡(luò)基礎(chǔ)功能.在傳統(tǒng)的TCP/IP架構(gòu)中，路由查找轉(zhuǎn)發(fā)的核心操作是IP 查找[1-7].在信息中心網(wǎng)絡(luò)（information centric networking,ICN）中，路由查找轉(zhuǎn)發(fā)的核心操作是數(shù)據(jù)名查找[8-10]；在內(nèi)容分發(fā)網(wǎng)絡(luò)（content delivery network,CDN）中，基于內(nèi)容路由也需要路由查找轉(zhuǎn)發(fā)，其核心操作也是數(shù)據(jù)名查找[11-14].此外，在5G 核心網(wǎng)用戶平面功能（user plane function,UPF）網(wǎng)元轉(zhuǎn)發(fā)數(shù)據(jù)包的過程中需提取應(yīng)用層的業(yè)務(wù)標(biāo)識（URL）進(jìn)行策略規(guī)則匹配，其本質(zhì)也可視為數(shù)據(jù)名查找.由此可見，數(shù)據(jù)名查找是眾多網(wǎng)絡(luò)功能的核心操作.其中，數(shù)據(jù)名采用層次化結(jié)構(gòu)，由多個字符串組件組成.在查找時根據(jù)業(yè)務(wù)需求執(zhí)行組件級的精確匹配、前綴匹配或者最長前綴匹配.其中，最長前綴匹配挑戰(zhàn)最大，且最長前綴匹配方法微調(diào)后可直接用于精確匹配和前綴匹配，因此本文主要研究組件級的最長前綴匹配，并在后續(xù)闡述中以此作為數(shù)據(jù)包查找的內(nèi)涵.

現(xiàn)有數(shù)據(jù)名查找方法大致分為2 大類，分別是基于前綴樹（trie）的方法和基于Hash（包括布隆過濾器）的方法.基于前綴樹的方法將長短不一的數(shù)據(jù)名維護(hù)為1 棵前綴樹[15-20]，因大量數(shù)據(jù)名具有相同前綴，可共享存儲節(jié)點(diǎn)提高存儲效率，但更新和查找性能相對較差.基于Hash 的方法將數(shù)據(jù)名按照組件長度分組，每組維護(hù)1 張Hash 表[21-24].基于哈希表的方法的查找和更新性能較高，還可進(jìn)一步借助二分搜索[22]和貪心搜索[23]等優(yōu)化策略來提速，但為降低沖突或維護(hù)額外指示信息導(dǎo)致的存儲開銷一般較大.因此，現(xiàn)有方法都會結(jié)合Hash 表和布隆過濾器[25-31]來壓縮存儲，但卻會因布隆過濾器的假陽性問題導(dǎo)致二分Hash 探測過程中的頻繁回溯.

本文提出一種混合計數(shù)布隆過濾器以及以此為基礎(chǔ)的二分?jǐn)?shù)據(jù)名查找方法.本文的主要貢獻(xiàn)有3 個方面：

1）基于數(shù)據(jù)名前綴和前綴標(biāo)記的稀疏分布特點(diǎn)，提出一種混合計數(shù)布隆過濾器（hybrid couting Bloom filter，HyCBF）同時維護(hù)真實(shí)前綴和前綴標(biāo)記的數(shù)量.此外，為每條記錄維護(hù)1 個特征比特位圖以降低假陽性，減少二分探測過程中的回溯.

2）基于HyCBF 提出了一種新型的二分?jǐn)?shù)據(jù)名查找方法，即HyCBF 輔助的二分搜索（HyCBF-assisted binary search，HyBS），利用HyCBF 所提供的查找指示信息，減少Hash 表探測.此外，還設(shè)計了一種自底向上的更新策略顯著降低更新開銷.實(shí)驗(yàn)結(jié)果表明，HyBS 相比已有方法具有更快的查找和更新速度，存儲開銷也更低.

3）基于向量化數(shù)據(jù)包處理（vector packet processing，VPP）平臺實(shí)現(xiàn)了以HyBS 構(gòu)建查找轉(zhuǎn)發(fā)插件的數(shù)據(jù)包轉(zhuǎn)發(fā)系統(tǒng)，并開展了系統(tǒng)性能測試.結(jié)果表明，HyBS具有構(gòu)建高通量、可擴(kuò)展數(shù)據(jù)名查找引擎的潛力.

1 相關(guān)工作

本節(jié)將介紹基于二分搜索的數(shù)據(jù)名查找方法的基本原理，以及現(xiàn)有方法所面臨的關(guān)鍵問題.

數(shù)據(jù)名規(guī)則集通常由若干個組件數(shù)量不同的前綴組成，而對于待查詢的數(shù)據(jù)名，需要在其中找出能夠與之匹配且組件數(shù)量最多的前綴.針對這一問題，順序探測法是一種較為直接的解決辦法——將所有前綴插入Hash 表，而待匹配的數(shù)據(jù)名則在Hash 表上進(jìn)行不斷地迭代查詢.初始化時取整個數(shù)據(jù)名作為查詢目標(biāo)，后續(xù)每次迭代時都減少1 個末尾組件，直到發(fā)現(xiàn)第1 個匹配成功的前綴后返回結(jié)果，或最終查找失敗.

順序探測的時間復(fù)雜度為O（n），其中n為組件數(shù)量，而有學(xué)者采用二分搜索法將復(fù)雜度降為O（logn）級別.在早期解決IP 查找中的最長前綴匹配問題時，已有學(xué)者引入了二分搜索法[7].而在數(shù)據(jù)名查找問題中，亦有學(xué)者使用二分搜索法提升查找性能[22-23,29-31].然而，二分搜索雖然可以降低查找的復(fù)雜度，但卻可能出現(xiàn)查找錯誤.查找程序在二分搜索樹（binary search tree，BST）上某個節(jié)點(diǎn)匹配成功后會轉(zhuǎn)向右子節(jié)點(diǎn)繼續(xù)查找，但匹配失敗后如果直接轉(zhuǎn)向左子節(jié)點(diǎn)，則可能導(dǎo)致查找結(jié)果錯誤，因?yàn)楫?dāng)前節(jié)點(diǎn)匹配失敗并不意味著右子樹中不存在可匹配的前綴.因此，搜索樹上除了葉子節(jié)點(diǎn)以外的節(jié)點(diǎn)，在保存前綴的同時，還要為其右子樹中保存的每個前綴維護(hù)1 個前綴標(biāo)記（后文簡稱標(biāo)記）[22]，以便查找程序在匹配失敗后選擇正確的后續(xù)節(jié)點(diǎn).標(biāo)記在形式上和普通前綴并無差異，只是不附帶任何轉(zhuǎn)發(fā)信息，因此可以將其作為一種特殊前綴插入到搜索樹節(jié)點(diǎn)的Hash 表中.但是，當(dāng)大量標(biāo)記插入到Hash 表中，不僅會導(dǎo)致Hash 表的存儲開銷增長，還會降低其查找速度.考慮到標(biāo)記并不附帶任何轉(zhuǎn)發(fā)信息，查找程序只需檢查其存在與否，因此有學(xué)者采用布隆過濾器來保存標(biāo)記[29-31].布隆過濾器作為一種數(shù)據(jù)成員檢查（即檢查數(shù)據(jù)是否在某個集合中）的數(shù)據(jù)結(jié)構(gòu)，適用于存儲標(biāo)記，但其依然存在2 大問題：1）布隆過濾器需要多次Hash 計算，處理時間較長.對此，有的學(xué)者通過減少Hash 計算次數(shù)或采用并行計算的方式，大幅度降低了布隆過濾器處理時間[31-34].2）布隆過濾器最主要的問題是存在假陽性，可能會出現(xiàn)錯誤的檢查結(jié)果，因此需要引入回溯操作，但會導(dǎo)致查找性能下降.

綜上所述，布隆過濾器雖適用于保存二分搜索法所需的標(biāo)記，但需要降低假陽性率以避免出現(xiàn)頻繁的回溯操作.第2 節(jié)將詳細(xì)介紹我們的方法.

2 混合計數(shù)布隆過濾器輔助的二分?jǐn)?shù)據(jù)名查找

本節(jié)將詳細(xì)介紹混合計數(shù)布隆過濾器輔助的二分?jǐn)?shù)據(jù)名查找方法，即HyBS.本節(jié)將首先通過一個具體示例介紹本文工作的研究動機(jī)，即布隆過濾器假陽性所帶來的回溯操作對查找性能的影響，并引出我們的方法.

2.1 研究動機(jī)

基于二分搜索的數(shù)據(jù)名查找方法需要構(gòu)建二分搜索樹，每個節(jié)點(diǎn)包含1 張Hash 表，其中保存著特定長度的前綴和標(biāo)記.使用布隆過濾器可以優(yōu)化標(biāo)記的存儲效率和查詢性能，如圖1 所示的二分搜索樹上的每個非葉子節(jié)點(diǎn)都包含1 張Hash 表和1 個布隆過濾器；而葉子節(jié)點(diǎn)不保存標(biāo)記，僅包含1 張Hash 表.所有前綴在插入對應(yīng)Hash 表中之后，需要在某些特定節(jié)點(diǎn)上的布隆過濾器中插入標(biāo)記，例如Hash 表-5 上的前 綴（即/e/t/g/h/i 和/k/c/t/f/g）需要在Hash 表-4 所關(guān)聯(lián)的布隆過濾器上插入標(biāo)記（即/e/t/g/h 和/k/c/t/f，其對應(yīng)的布隆過濾器探測位置數(shù)值均被設(shè)置為1）.假設(shè)待查詢數(shù)據(jù)名為/a/b/c/e/f，根據(jù)二分搜索原則，查找程序首先在Hash 表-4 上進(jìn)行匹配，發(fā)現(xiàn)匹配失敗后執(zhí)行布隆過濾器檢查，而檢查結(jié)果顯示為陽性（即方框中所示，/a/b/c/e 所對應(yīng)的探測位置數(shù)值均為1，而實(shí)際上/a/b/c/e 并未被插入到布隆過濾器中，因此結(jié)果為假陽性），因此查找程序轉(zhuǎn)向Hash 表-6.查找程序在Hash 表-6 上匹配失敗，并且由于Hash 表-7 并未保存任何前綴規(guī)則，因此Hash 表-6所關(guān)聯(lián)的布隆過濾器為空，查找程序轉(zhuǎn)向Hash 表-5.查找程序在Hash 表-5 上同樣匹配失敗，并且Hash 表-5 已經(jīng)位于搜索樹的葉子節(jié)點(diǎn)，此時為保證查找的正確性，需要回溯到Hash 表-2 上進(jìn)行匹配.最后，查找程序在Hash 表-3 上找到正確的最長前綴/a/b/c.綜上，查找程序在經(jīng)過5 次節(jié)點(diǎn)匹配（即節(jié)點(diǎn)4,6,5,2,3）后找到了正確結(jié)果.如果Hash 表-4 所關(guān)聯(lián)的布隆過濾器沒有給出假陽性結(jié)果，則僅需3 次節(jié)點(diǎn)匹配（即節(jié)點(diǎn)4,2,3）.因此，降低布隆過濾器假陽性率有助于提升二分搜索的整體性能.為此，我們提出混合計數(shù)布隆過濾器HyCBF，并以此為基礎(chǔ)提出新型二分?jǐn)?shù)據(jù)名查找方法HyBS.

Fig.1 Backtrack caused by the false positive of Bloom filter圖 1 因布隆過濾器假陽性導(dǎo)致的回溯

2.2 二分搜索整體架構(gòu)

假設(shè)規(guī)則集中的數(shù)據(jù)名長度范圍為1～7 組件，HyBS 的二分搜索整體架構(gòu)則如圖2 所示.從二分搜索樹的角度看來，所有的葉子節(jié)點(diǎn)（即節(jié)點(diǎn)1,3,5,7）保存了1 張Hash 表和1 個前綴計數(shù)布隆過濾器（prefix counting Bloom filter,P-CBF），該布隆過濾器用于保存Hash 表中的前綴，以此避免不必要的Hash 表查找.所有的內(nèi)部節(jié)點(diǎn)（即節(jié)點(diǎn)2,4,6）除P-CBF 和Hash 表之外，還包含1 個額外的標(biāo)記計數(shù)布隆過濾器（marker counting Bloom filter,M-CBF），用于保存標(biāo)記.

Fig.2 The overall binary search architecture of HyBS圖 2 HyBS 二分搜索整體架構(gòu)

在每個內(nèi)部節(jié)點(diǎn)上，我們將前綴和標(biāo)記分開保存在不同的布隆過濾器中，這樣做的好處是：在保留了基本過濾器功能的同時，還獲得了更細(xì)粒度的檢查結(jié)果，即可以清楚地獲知前綴和標(biāo)記各自的檢查結(jié)果.如果布隆過濾器僅保留標(biāo)記信息[30-31]，那么想要獲知是否存在可能匹配的前綴，依然需要查找Hash 表.如果布隆過濾器同時保存標(biāo)記和前綴，當(dāng)檢查結(jié)果為陰性時，可以直接避免任何Hash 查找.但一旦檢查結(jié)果為陽性，由于無法區(qū)分是前綴陽性還是標(biāo)記陽性，需要進(jìn)一步到Hash 表中查找[31]，如果標(biāo)記是陽性而前綴是陰性，這時實(shí)際上不必執(zhí)行Hash 表查找.如果前綴和標(biāo)記分別存儲于2 個不同的布隆過濾器中，我們不僅可以知道檢查結(jié)果是否為陽性，還可以獲得陽性檢查結(jié)果的具體類型（即，僅前綴陽性、僅標(biāo)記陽性或者二者皆為陽性）.

2.3 混合計數(shù)布隆過濾器

由圖2 可知，所有的葉子節(jié)點(diǎn)均不包含標(biāo)記，因此僅需普通CBF 即可，在此我們不做討論.每個內(nèi)部節(jié)點(diǎn)均關(guān)聯(lián)著1 個HyCBF，其結(jié)構(gòu)如圖3 所示，包括1 個HyCBF，以及1 個用于降低布隆過濾器假陽性的特征比特位圖（feature bitmap,FB）數(shù)組.HyCBF 的設(shè)計核心思想是將P-CBF 和M-CBF 合并在一起，即HyCBF 中每個counter（即計數(shù)器）實(shí)際上由2 個counter組成.2 個布隆過濾器邏輯上需要單獨(dú)執(zhí)行Hash 計算獲得探測位置，會導(dǎo)致Hash計算次數(shù)翻倍，而實(shí)際上可以避免出現(xiàn)這個問題.具體而言，當(dāng)P-CBF 和M-CBF的長度分別確定后，取其中的最大值作為HyCBF 的長度.對于同一個數(shù)據(jù)名，其在P-CBF 和M-CBF 上3個探測位置的索引相同，并不需要額外的Hash 計算，并且這種方式使得一次內(nèi)存操作即可把P-CBF 和M-CBF的探測位置數(shù)據(jù)都載入CPU 緩存中.因此，HyCBF雖然在邏輯上維護(hù)了2 個布隆過濾器，而實(shí)際計算時并不需要額外的Hash 計算和訪存操作.對于如圖2的二分搜索樹結(jié)構(gòu)，某個內(nèi)部節(jié)點(diǎn)上的標(biāo)記數(shù)量等于其所有右子節(jié)點(diǎn)上的前綴數(shù)量之和，因此HyCBF的長度通常取M-CBF 的長度.對于布隆過濾器而言，數(shù)據(jù)總量和探測位置數(shù)量不變時，長度越長意味著假陽性率越低，因此在HyCBF 中，P-CBF 的假陽性率會因?yàn)殚L度增長而出現(xiàn)降低，M-CBF 的假陽性率則保持不變，二者不會出現(xiàn)假陽性率高于設(shè)定閾值的情況.布隆過濾器的長度通常會根據(jù)給定的假陽性率閾值和需要插入的數(shù)據(jù)量計算得出.假設(shè)布隆過濾器的假陽性率閾值為F，數(shù)據(jù)集的大小為n，布隆過濾器探測位置數(shù)量（即Hash 函數(shù)數(shù)量）為k，則布隆過濾器所需長度m的計算公式為

Fig.3 Structure of HyCBF圖 3 混合計數(shù)布隆過濾器結(jié)構(gòu)

HyCBF 中的元素為固定大小的counter（計數(shù)器），為保證不會出現(xiàn)counter 數(shù)值溢出的情況，需要讓counter 維持一定的位寬度（bit width）.如圖3 所示，PCBF 和M-CBF 的counter 分別為P-Cnt（prefix counter）和M-Cnt（marker counter）.經(jīng)實(shí)驗(yàn)測試，2 個counter 的長度分別為8b 和24b 就足以保證在處理百萬規(guī)模的規(guī)則時不會出現(xiàn)counter 數(shù)值溢出，因此HyCBF 的counter 總的位寬度為32b.越靠近根節(jié)點(diǎn)，HyCBF 所保存的標(biāo)記就越多，其內(nèi)存占用也就越大，但是在二分搜索這一特殊場景下，HyCBF 的存儲開銷實(shí)際上可以比理論值更低.

對于某個內(nèi)節(jié)點(diǎn)，由于M-CBF 中保存著該節(jié)點(diǎn)的右子樹中所有前綴的標(biāo)記，會導(dǎo)致HyCBF 的長度較長，因此存儲開銷也較大.但是，這其中實(shí)際上存在大量重復(fù)標(biāo)記.假設(shè)規(guī)則集中包含/a/b/c/d/e,/a/b/c/d/f 和/a/b/c/d/g/h 這樣3 個前綴數(shù)據(jù)名，在圖2所示的二分搜索結(jié)構(gòu)中，這3 個前綴均需要在節(jié)點(diǎn)4上插入標(biāo)記/a/b/c/d，我們稱之為共享標(biāo)記.維護(hù)冗余的共享標(biāo)記是為了確保查找的正確性，假如為所有的標(biāo)記進(jìn)行去重處理，將導(dǎo)致HyCBF 無法支持刪除操作.重復(fù)插入標(biāo)記會導(dǎo)致單節(jié)點(diǎn)的標(biāo)記數(shù)量增大，根據(jù)式（1），理論上會導(dǎo)致M-CBF 的長度增長，進(jìn)而使得HyCBF 長度增長.而事實(shí)上，面對由共享標(biāo)記帶來的標(biāo)記數(shù)量增長，只要HyCBF 中的counter 具有足夠的比特位寬就不會出現(xiàn)數(shù)值溢出，即使HyCBF 的長度不變，假陽性率也不會增長.為證明這一結(jié)論，我們將計數(shù)布隆過濾器和標(biāo)準(zhǔn)布隆過濾器進(jìn)行對比分析.二者的區(qū)別在于對更新的支持，在進(jìn)行數(shù)據(jù)成員檢查時二者的用法沒有區(qū)別——當(dāng)某個數(shù)據(jù)的所有探測位置的數(shù)值（即計數(shù)布隆過濾器中的單個counter，以及標(biāo)準(zhǔn)布隆過濾器中的單個比特位）均不等于0，我們認(rèn)為該數(shù)據(jù)存在數(shù)據(jù)集中.因此，當(dāng)執(zhí)行數(shù)據(jù)成員檢查時，計數(shù)布隆過濾器可以等價為標(biāo)準(zhǔn)布隆過濾器，其中計數(shù)布隆過濾器中的“非零”counter 和“零”counter 分別對應(yīng)于標(biāo)準(zhǔn)布隆過濾器中的1 比特位和0 比特位.當(dāng)計數(shù)布隆過濾器插入重復(fù)數(shù)據(jù)時，只要沒有發(fā)生counter 數(shù)值溢出，這些探測位置的counter 數(shù)值就始終不等于0，對應(yīng)的標(biāo)準(zhǔn)布隆過濾器就不會有任何變化.綜上所述，當(dāng)存在重復(fù)數(shù)據(jù)時，不能采用傳統(tǒng)計算方式推算所需的布隆過濾器長度，而是要剔除其中的重復(fù)數(shù)據(jù)后進(jìn)行計算，否則會導(dǎo)致布隆過濾器的長度出現(xiàn)冗余，使得真實(shí)的假陽性率低于我們設(shè)定的閾值，我們將在實(shí)驗(yàn)部分驗(yàn)證這一推論.

除了存儲開銷以外，傳統(tǒng)布隆過濾器需要多次Hash 計算以獲得探測位置的索引，帶來額外的開銷.我們從文獻(xiàn)[32-33]獲得啟發(fā)，采用“一次Hash”方法最大限度地減少Hash 計算的次數(shù).此外，受商過濾器[35]的啟發(fā)，僅計算一次Hash 值，并將其與布隆過濾器長度進(jìn)行除法運(yùn)算，將所得到的商和余數(shù)作為Hash種子，通過迭代計算的方式獲得探測位置的索引.此外，前綴的Hash 值等于組成該前綴的每個組件的Hash 值之和，已經(jīng)計算過的組件其Hash 值可以復(fù)用，這樣每個數(shù)據(jù)名需要執(zhí)行的Hash 計算次數(shù)至多等于其組件數(shù)量.假設(shè)布隆過濾器長度為M，每個數(shù)據(jù)名有k個探測位置，給定數(shù)據(jù)名的Hash 值為h，h與布隆過濾器長度進(jìn)行除法運(yùn)算后，其商為Q（h），余數(shù)則為R（h），則第i個探測位置的索引sloti為

此外，當(dāng)經(jīng)過布隆過濾器處理后，如果需要執(zhí)行Hash 表查找，我們還可以繼續(xù)復(fù)用布隆過濾器檢查過程中的計算結(jié)果，這樣可以把單節(jié)點(diǎn)上需要進(jìn)行的Hash 計算次數(shù)降到最低.假設(shè)Hash 表長度為H，那么Hash 表索引index的計算公式為

2.4 特征比特位圖優(yōu)化

除了存儲開銷和Hash 計算時間開銷以外，HyCBF所面臨的另一大問題就是假陽性問題，本節(jié)將介紹我們?yōu)榇硕O(shè)計的方法——特征比特位圖.正如2.1節(jié)所述，較高的布隆過濾器假陽性率會引入頻繁的回溯操作，進(jìn)而導(dǎo)致查找性能下降.為此，我們在設(shè)計HyCBF 時，為每個counter 關(guān)聯(lián)了1 個特征比特位圖，并以此顯著降低了布隆過濾器的假陽性率.假設(shè)布隆過濾器在進(jìn)行數(shù)據(jù)成員檢查時需要探測3 個位置，則每個位置需要關(guān)聯(lián)3 個特征比特位圖.圖4 中BF（Bloom filter）表示布隆過濾器，F(xiàn)B0,FB1,FB2則表示3 個特征比特位圖數(shù)組，其中每個數(shù)組元素都是1個特征比特位圖，并與BF對應(yīng)位置相關(guān)聯(lián).當(dāng)檢查某個數(shù)據(jù)是否存在于數(shù)據(jù)集中時，通過Hash 計算得出3 個探測位置，并檢查這3 個探測位置的數(shù)值是否均為1.圖4 展示的2 個場景中，Data0的探測位置數(shù)值均為1，但Data0并沒有被插入到布隆過濾器中，因此2 個場景中Data0的檢查結(jié)果均為假陽性.對于圖4（a）所示的場景1 而言，布隆過濾器中已插入2 個數(shù)據(jù)Data1和Data2，二者的探測位置剛好包含了Data0的3 個探測位置.因此，Data0的檢查結(jié)果為假陽性.如圖4（b）所示的場景2 較為特殊，因?yàn)樵谠搱鼍跋拢珼ata0對應(yīng)的3 個探測位置數(shù)值是被同一個數(shù)據(jù)置為1（即Data3）.這種情況下，Data0的檢查結(jié)果依然是假陽性.為了更好地理解場景2 的假陽性，這里引入探測位置層級的概念.層級表示探測位置的先后順序.假設(shè)索引號從0 開始，并從左到右遞增，在對Data0進(jìn)行探測時，探測位置的先后順序是BF[0]，BF[1]，BF[4]，因此對Data0而言這3 個探測位置的層級分別是0,1,2.而對于Data3而言，探測位置的先后順序則為BF[1]，BF[0]，BF[4].其中，BF[0]和BF[1]在插入Data0和Data3時具有不同的層級，因此Data0的3 個探測位置雖然均為1，且這3 個探測位置被同一個數(shù)據(jù)置1（即Data3），但檢查結(jié)果依然是假陽性.

Fig.4 The feature bitmap圖 4 特征比特位圖

布隆過濾器不支持“鍵-值”查詢，對此有學(xué)者提出了一種新型布隆過濾器NBF[36].NBF 將數(shù)據(jù)的編碼信息嵌入到對應(yīng)的探測位置中，具體方法是在插入數(shù)據(jù)時，將數(shù)值編碼以按位或（OR）運(yùn)算的形式插入到探測位置.而查詢時，則將各個探測位置上的數(shù)值編碼以按位與（AND）運(yùn)算的方式聚合在一起，以此過濾掉其他數(shù)據(jù)嵌入的數(shù)值編碼（原文稱之為“噪聲”），并獲得所查詢數(shù)據(jù)的數(shù)值編碼.受此啟發(fā)，通過在布隆過濾器上每個位置關(guān)聯(lián)1 個數(shù)值編碼（即特征比特位圖），可以降低布隆過濾器的假陽性率.具體而言，當(dāng)針對某個數(shù)據(jù)執(zhí)行成員檢查時，我們在檢查各探測位置數(shù)值的同時，將對應(yīng)的特征比特位圖也取出并進(jìn)行按位與運(yùn)算，通過驗(yàn)證計算結(jié)果是否為0 來判斷是否出現(xiàn)了假陽性.利用特征比特位圖，我們加強(qiáng)了布隆過濾器的檢查條件：不僅要求每個探測位置的數(shù)值非零，還要求每個探測位置上“嵌入”了相同的特征比特位圖.針對某個具體數(shù)據(jù)，即使其對應(yīng)的每個探測位置數(shù)值均為1，只要特征比特位圖的與運(yùn)算結(jié)果為0，其檢查結(jié)果仍然為陰性.

針對圖4 所示的場景1，Data1的特征比特位圖是0010,Data2的特征比特位圖則是1000.這2 個數(shù)據(jù)插入布隆過濾器后，各探測位置的特征比特位圖也需要嵌入到對應(yīng)的特征比特位圖數(shù)組中.當(dāng)處理Data0時，在確定探測位置之后，查找程序?qū)⒏魑恢蒙蠈?yīng)層級的特征比特位圖（即虛線框選定的特征比特位圖）提取出來，分別為0010,0010,1000.最后，利用提取出來的特征比特位圖執(zhí)行按位與運(yùn)算，得出計算結(jié)果為0000.因此我們得到針對Data0的陰性檢查結(jié)果，場景1 中的假陽性問題可以得到規(guī)避.場景2 不同于場景1，需要將特征比特位圖結(jié)合層級信息做出判斷.場景2 中，Data3的特征比特位圖是0001，并且根據(jù)每個探測位置的層級，這些特征比特位圖將被嵌入到對應(yīng)的位置.例如，對Data3而言，BF[0]層級為1，因此將0001 嵌入BF[0]所關(guān)聯(lián)的1 號特征比特位圖FB1[0]中.在獲得Data0的探測位置后，根據(jù)探測位置的層級提取出對應(yīng)的特征比特位圖（虛線框選中的特征比特位圖），即0000,0000,0001.最后，和場景1 的處理方式相同，將提取出來的所有特征比特位圖按位與運(yùn)算得出的計算結(jié)果為0000，因此針對場景2 中的假陽性問題，可以利用附帶層級信息的特征比特位圖來解決.

圖4 所示的特征比特位圖從形式上比較直觀地描述了其工作原理，但在具體實(shí)現(xiàn)時，這種方法會帶來較大的存儲開銷.假設(shè)每個插入布隆過濾器的數(shù)據(jù)需要訪問n個探測位置，而布隆過濾器的長度為m，則圖4 中特征比特位圖數(shù)量為m×n個.通過按位或運(yùn)算將圖4 所示的每個探測位置對應(yīng)的3 個特征比特位圖合并在一起，這樣可以將n個特征比特位圖數(shù)組減少到1 個.此外，受SBF[37]中移位操作的啟發(fā)，我們將層級信息通過移位操作的方式嵌入特征比特位圖中，避免了合并時丟失掉層級信息.圖5 展示的特征比特位圖結(jié)構(gòu)和圖4 中場景1 一致，不同之處在于通過引入移位操作將多個特征比特位圖數(shù)組合并為1 個.當(dāng)確定數(shù)據(jù)名Name的3 個探測位置后，我們在嵌入特征比特位圖時，以對應(yīng)位置的層級數(shù)值作為移位的偏移量，將特征比特位圖嵌入到偏移后的FB數(shù)組位置上.同樣地，在對Name執(zhí)行成員檢查時，得出所有的探測位置后，依然需要將層級數(shù)值作為偏移提取出對應(yīng)位置的比特位圖，即圖5 中灰色填充的特征比特位圖.觀察圖5 可以發(fā)現(xiàn)，如果我們提取出Name（即相當(dāng)于圖4 場景1 中的Data0）所對應(yīng)的特征比特位圖（即0010,1010,1000）并執(zhí)行按位與運(yùn)算，計算結(jié)果依然是0，特征比特位圖依然可以發(fā)揮作用.同時，由于偏移操作的引入，特征比特位圖附帶的層級信息也得到了保存.相比于圖4 中的結(jié)構(gòu)需要m×n個特征比特位圖，圖5 僅需m＋n-1 個特征比特位圖.

Fig.5 The implementation of feature bitmap圖 5 特征比特位圖的實(shí)現(xiàn)

綜上所述，特征比特位圖可以有效地降低布隆過濾器的假陽性率.在HyBS 中，每個數(shù)據(jù)名的特征比特位圖為8b，并且有且僅有1 個比特位數(shù)值是1.因此，形式上看來特征比特位圖中大部分比特位數(shù)值為0，因此在檢查階段的按位與運(yùn)算時，我們能有更大的概率過濾掉由其他數(shù)據(jù)插入時嵌入的“噪聲”（即數(shù)值為1 的比特位），以確保特征比特位圖計算的準(zhǔn)確性.在HyBS 中，我們在計算數(shù)據(jù)名的特征比特位圖時所采用的方式是：將數(shù)據(jù)名的字符長度除以1 個常量閾值，然后我們用計算結(jié)果作為偏移，將1 個初始化為全0 的特征比特位圖中的對應(yīng)比特位翻轉(zhuǎn)為1，并以此作為該數(shù)據(jù)名的特征比特位圖.特征比特位圖的計算方式是個開放性問題，HyBS 的計算方式則是經(jīng)實(shí)驗(yàn)測試獲得.

2.5 查 找

介紹完HyBS 的核心數(shù)據(jù)結(jié)構(gòu)HyCBF 之后，本節(jié)將介紹如何在二分搜索中有效地使用它.在采用HyCBF 這樣一種雙布隆過濾器設(shè)計之后，二分搜索樹上每個節(jié)點(diǎn)的處理邏輯如圖6 所示.由于葉子節(jié)點(diǎn)的處理過程和傳統(tǒng)的基于過濾器的Hash 表查找（即，布隆過濾器做初步篩選，Hash 表完成前綴匹配）方法并無差異，在此不做介紹，圖6 僅展示包含了HyCBF的內(nèi)部節(jié)點(diǎn)的處理過程.

當(dāng)處理數(shù)據(jù)名Name時，首先在M-CBF 和PCBF 上分別執(zhí)行標(biāo)記和前綴檢查.根據(jù)檢查結(jié)果的不同，可分為4 種情況：

Fig.6 Process of single node in BST圖 6 二分搜索樹單節(jié)點(diǎn)處理過程

1）P-CBF 陰性，M-CBF 陰性.這種情況表明該節(jié)點(diǎn)沒有任何能與Name匹配的前綴和標(biāo)記，因此下一節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn).

2）P-CBF 陰性，M-CBF 陽性.這種情況說明該節(jié)點(diǎn)沒有能與Name匹配的前綴，因此不必進(jìn)行Hash表查找.但標(biāo)記的檢查結(jié)果為陽性，表示右子節(jié)點(diǎn)中可能保存有Name的前綴，因此下一跳節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn).

3）P-CBF 陽性，M-CBF 陰性.這種情況說明當(dāng)前節(jié)點(diǎn)可能保存著與Name匹配的前綴，因此需要進(jìn)行Hash 表查找.同時M-CBF 為陰性表示Name在右子節(jié)點(diǎn)中不可能存在更長的前綴.由于布隆過濾器不存在假陰性，因此如果Hash 表查找成功，則查找到的前綴即為Name的最長前綴，可以直接返回查找結(jié)果.否則，下一跳節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn).

4）P-CBF 陽性，M-CBF 陽性.這種情況表示需要進(jìn)行Hash 表查找.同時，因?yàn)闃?biāo)記的檢查結(jié)果為陽性，無論查找成功還是失敗，下一跳節(jié)點(diǎn)均會被設(shè)置為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn).當(dāng)Hash 查找失敗時，不做任何處理立即轉(zhuǎn)向右子節(jié)點(diǎn)；當(dāng)Hash 查找成功時，我們將查找到的前綴作為當(dāng)前階段的最長匹配前綴，并轉(zhuǎn)向右子節(jié)點(diǎn).

綜上所述，在這4 種情況中，情況3 和情況4（即當(dāng)P-CBF 檢查結(jié)果為陽性時）需要進(jìn)行Hash 表查找.而如果將前綴和標(biāo)記不作區(qū)分地存入同一個布隆過濾器中，情況2 也需要進(jìn)行Hash 表查找，因?yàn)檫@種方式無法區(qū)分陽性的檢查結(jié)果是源自前綴還是標(biāo)記.同時，得益于HyCBF 的設(shè)計，2 個邏輯上獨(dú)立的布隆過濾器在實(shí)際查找過程中并不會帶來額外的時間和存儲開銷.

2.6 “自底向上”更新

更新性能同樣是數(shù)據(jù)名查找方法的重要性能指標(biāo).通常，在執(zhí)行更新之前需要進(jìn)行查找操作以確定需要更新的具體節(jié)點(diǎn)位置.在最長前綴匹配這一場景下，二分搜索的目的在于探測可能的前綴長度，這在查找時必不可少，因?yàn)闊o法事先確定數(shù)據(jù)名在該數(shù)據(jù)集中的最長前綴的長度.而對于規(guī)則的更新操作，其附帶的數(shù)據(jù)名長度就決定了它最終會被插入到如圖2 所示的查找結(jié)構(gòu)中的哪個節(jié)點(diǎn)上.此外，前綴所對應(yīng)的標(biāo)記也需要更新.具體而言，從更新節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上，我們需要在所有的右子節(jié)點(diǎn)的父節(jié)點(diǎn)上更新標(biāo)記信息，我們稱這些節(jié)點(diǎn)為標(biāo)記節(jié)點(diǎn).當(dāng)如圖2 的查找結(jié)構(gòu)確定后，每個節(jié)點(diǎn)的標(biāo)記節(jié)點(diǎn)事實(shí)上也已經(jīng)確定.例如，節(jié)點(diǎn)7 的標(biāo)記節(jié)點(diǎn)為節(jié)點(diǎn)4 和節(jié)點(diǎn)6.因此在每個節(jié)點(diǎn)上維護(hù)1 個比特位圖，即標(biāo)記節(jié)點(diǎn)位圖，并以此記錄某個節(jié)點(diǎn)的標(biāo)記節(jié)點(diǎn)信息.例如圖7 中節(jié)點(diǎn)7 的標(biāo)記節(jié)點(diǎn)位圖為00101000，表示節(jié)點(diǎn)7 的標(biāo)記節(jié)點(diǎn)為節(jié)點(diǎn)4 和節(jié)點(diǎn)6.

Fig.7 The "bottom to up" update圖 7 “自底向上” 更新

在這樣一種設(shè)計思路下，HyBS 的更新操作可以分為如圖7 所示的2 個步驟：1）根據(jù)規(guī)則中附帶的前綴的長度確定待更新規(guī)則位于哪個節(jié)點(diǎn)，并在該節(jié)點(diǎn)的Hash 表中執(zhí)行相應(yīng)的更新操作；2）根據(jù)節(jié)點(diǎn)附帶的標(biāo)記節(jié)點(diǎn)位圖確定所有的標(biāo)記節(jié)點(diǎn)，更新所有標(biāo)記節(jié)點(diǎn)上的標(biāo)記信息.因此，規(guī)則更新時至多需要訪問1 個節(jié)點(diǎn)的Hash 表.同時，步驟2 的計算過程中會復(fù)用步驟1 中所得出的計算結(jié)果（即組件的Hash 值），進(jìn)一步減少時間開銷.

2.7 系統(tǒng)實(shí)現(xiàn)和優(yōu)化

本節(jié)將介紹如何將HyBS 部署到真實(shí)的軟件包處理平臺VPP 中，以及結(jié)合VPP 批處理特性所采用的優(yōu)化設(shè)計.目前主流的軟件包處理平臺有OVS（open vswitch）[38]和VPP[39].OVS 采用元組空間搜索（tuple space search,TSS）算法實(shí)現(xiàn)流表查詢，并且目前大部分商用智能網(wǎng)卡都支持OVS 硬件卸載加速[40]，因此OVS 被廣泛應(yīng)用于構(gòu)建高性能網(wǎng)絡(luò)I/O系統(tǒng).但是OVS 為OpenFlow 協(xié)議進(jìn)行了深度定制設(shè)計，因此難以在其基礎(chǔ)之上實(shí)現(xiàn)基于數(shù)據(jù)名查找的轉(zhuǎn)發(fā)引擎.而VPP 作為一種支持用戶開發(fā)自定義協(xié)議的包處理平臺，可以滿足HyBS 的部署需求.在VPP 中，各個網(wǎng)絡(luò)功能以節(jié)點(diǎn)的形式部署，而各個節(jié)點(diǎn)可以通過編程控制進(jìn)行靈活的編排，以此實(shí)現(xiàn)自定義的數(shù)據(jù)包處理流程.除了支持自定義配置節(jié)點(diǎn)連接關(guān)系，VPP 還支持以插件的形式將用戶自定義的包處理代碼打包成節(jié)點(diǎn)嵌入到的包處理節(jié)點(diǎn)圖中.因此，我們將HyBS 以插件的形式嵌入到數(shù)據(jù)包處理節(jié)點(diǎn)圖中.如圖8 所示，整個包處理框架包括3 個節(jié)點(diǎn)：接收節(jié)點(diǎn)負(fù)責(zé)采用數(shù)據(jù)面開發(fā)套件（data plane development kit，DPDK）[41]從網(wǎng)卡接收數(shù)據(jù)包；轉(zhuǎn)發(fā)節(jié)點(diǎn)則是嵌入了HyBS 的包處理節(jié)點(diǎn)，負(fù)責(zé)接收來自接收節(jié)點(diǎn)的數(shù)據(jù)包并執(zhí)行數(shù)據(jù)名查找；發(fā)送節(jié)點(diǎn)則將處理后的數(shù)據(jù)包采用DPDK 由指定端口轉(zhuǎn)發(fā)出去.VPP 在啟用HyBS 插件時，可以通過命令行接口指定規(guī)則文件的路徑，后臺會進(jìn)行查找結(jié)構(gòu)的構(gòu)建，而在后續(xù)的數(shù)據(jù)包處理階段，所有CPU 會共享這一份查找結(jié)構(gòu).

Fig.8 The system implementation of HyBS in VPP圖 8 VPP 中的HyBS 系統(tǒng)實(shí)現(xiàn)

VPP 利用批處理策略顯著提高了CPU 指令緩存（instruction cache,I-Cache）的命中率，但是卻沒有針對數(shù)據(jù)緩存（data cache,D-Cache）做優(yōu)化設(shè)計.而HyBS利用組預(yù)讀策略，可以提升查找程序?qū)?shù)據(jù)緩存的利用效率.我們以HyBS 中的布隆過濾器處理為例.布隆過濾器探測通?？梢苑譃? 個步驟，即Hash 計算、內(nèi)存訪問和探測（即數(shù)值檢查）.當(dāng)處理某個數(shù)據(jù)包時，首先提取其附帶的數(shù)據(jù)名，根據(jù)Hash 計算得出布隆過濾器探測位置的索引，然后對該位置發(fā)起內(nèi)存訪問請求以獲得該位置的計數(shù)器數(shù)值，最后檢查計數(shù)器的數(shù)值.圖9 展示了處理3 個數(shù)據(jù)包時的布隆過濾器探測階段的時間分布，其中不同的方塊對應(yīng)著不同操作的時間開銷.為簡化展示內(nèi)容，我們設(shè)定布隆過濾器探測位置僅為1 個.如圖9 所示，時間線以上的部分展示的是沒有采用組預(yù)讀策略時的時間開銷情況，當(dāng)?shù)? 個數(shù)據(jù)名完成Hash 計算獲得探測位置的索引后，查找程序發(fā)起對該探測位置的訪問，此時該探測位置的數(shù)據(jù)并沒有被載入CPU 的數(shù)據(jù)緩存之中，即發(fā)生一次緩存未命中，會導(dǎo)致CPU 出現(xiàn)停頓，直到數(shù)據(jù)被完整地載入緩存.Hash 計算使得數(shù)據(jù)包的探測位置具有較大隨機(jī)性，因此數(shù)據(jù)局部性較差，極端情況下每個數(shù)據(jù)名的內(nèi)存訪問請求都會觸發(fā)CPU 停頓.時間線以下的部分則是采用組預(yù)讀策略時的時間開銷情況.現(xiàn)代CPU 支持對內(nèi)存進(jìn)行預(yù)讀操作，即當(dāng)發(fā)生緩存未命中時，CPU 依然需要將數(shù)據(jù)從主存載入緩存中，但不會導(dǎo)致CPU 停頓，因此CPU 在數(shù)據(jù)載入緩存期間可以進(jìn)行其他計算.從時間線以下的部分可以看出，當(dāng)?shù)? 個數(shù)據(jù)名完成Hash 計算并獲得探測位置索引之后，查找程序?qū)υ撐恢冒l(fā)起預(yù)讀請求，這時數(shù)據(jù)將開始從主存載入緩存中，此時CPU 無需等待該操作完成，而是繼續(xù)針對第2 個數(shù)據(jù)名執(zhí)行Hash 計算，并同樣根據(jù)計算結(jié)果發(fā)起預(yù)讀操作，最后處理第3 個數(shù)據(jù)名.當(dāng)所有的數(shù)據(jù)名都完成Hash 計算之后，再執(zhí)行對應(yīng)位置的探測操作.由于Hash 計算和緩存加載可以同時進(jìn)行，這2部分的時間開銷可以重疊在一起.雖然組預(yù)讀并不會使得緩存未命中的次數(shù)減少，但通過時間片重疊，數(shù)據(jù)載入緩存的時間開銷被“隱藏”起來.

Fig.9 Group-prefetching strategy圖 9 組預(yù)讀策略

需要注意的是，圖9 中我們假設(shè)Hash 計算、內(nèi)存訪問和探測的時間開銷相同（即三者的時間片長度相同），但實(shí)際情況中訪存的時間開銷可能會比Hash 計算大很多.在極端情況下，當(dāng)數(shù)據(jù)載入緩存的時間開銷遠(yuǎn)大于Hash 計算的時間開銷時，有可能針對3 個數(shù)據(jù)名的Hash 計算全部完成后，依然需要等待較長時間直到最后1 個探測位置數(shù)據(jù)載入緩存.這種情況下，CPU 可能仍然需要停頓較長時間，進(jìn)而弱化了組預(yù)讀的優(yōu)化效果.因此，不同CPU 的緩存載入時間和CPU 計算時間的比值不同，所表現(xiàn)出來的組預(yù)讀優(yōu)化效果也不同.但是，和普通的數(shù)據(jù)包處理策略相比，基于組預(yù)讀的批處理策略依然能降低查找的整體時間開銷.

3 性能評估

本節(jié)通過將HyBS 與2 個基于不同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)名查找方法進(jìn)行對比，以評估HyBS 的綜合性能表現(xiàn).對比方法為CBS[29]和Nametrie[20]，二者分別基于布隆過濾器和二分搜索（即，和HyBS 同屬一類方法），以及前綴樹.由于目前不存在真實(shí)數(shù)據(jù)名的數(shù)據(jù)集，通常使用URL 數(shù)據(jù).我們采用從Reddit 論壇評論中收集的URL 數(shù)據(jù)[42].對于每個URL，我們用其中的特殊符號作為分隔符將URL 分隔成多個組件，以此將URL 轉(zhuǎn)換成數(shù)據(jù)名.本文生成了不同規(guī)模的6個規(guī)則集，其中每個規(guī)則集的規(guī)則數(shù)量如表1 所示.

Table 1 Number of Rules of Different Rule Sets表 1 不同規(guī)則集中的規(guī)則數(shù)量

為了驗(yàn)證HyBS 在不同CPU 下的性能表現(xiàn)，我們分別在2 臺配備了不同CPU（即Intel 處理器和AMD 處理器）的服務(wù)器上進(jìn)行了性能測試，分別為ServerIntel和ServerAMD.2 臺服務(wù)器的具體配置如表2所示.為了盡量避免受到系統(tǒng)進(jìn)程調(diào)度的干擾，在測試時利用Linux 的CPU 核心隔離功能，將查找程序調(diào)度到被隔離的CPU 核心.考慮到HyBS 和CBS 中都需要進(jìn)行Hash 計算，統(tǒng)一采用了MurmurHash[43]，并且均采用鏈表法來解決Hash 沖突.

3.1 存儲開銷

存儲開銷是一項和CPU 無關(guān)的性能指標(biāo)，因此該實(shí)驗(yàn)不區(qū)分CPU 型號.我們發(fā)現(xiàn)，當(dāng)規(guī)則集規(guī)模較大時，對于HyBS 和CBS 這樣采用布隆過濾器保存標(biāo)記和前綴的方法，其主要存儲開銷來源于布隆過濾器而非Hash 表，因此對布隆過濾器的存儲優(yōu)化對于整體存儲開銷的降低是有重要意義的.

Table 2 Configuration of Servers表 2 服務(wù)器的配置

如果僅從數(shù)據(jù)結(jié)構(gòu)設(shè)計的角度看，HyBS 中每個HyCBF 都配備了1 個長度幾乎相等的特征比特位圖數(shù)組，盡管特征比特位圖數(shù)組中每個數(shù)組元素的大?。?B）僅為HyCBF（即4B）的1/4，但這部分的存儲開銷依然是不可忽略的.但是，正如2.3 節(jié)所述，HyCBF 中長度通常取決于M-CBF 的長度，而特征比特位圖數(shù)組的長度在考慮去除“共享標(biāo)記”的影響下，事實(shí)上相比理論值會小很多，因此HyBS 的整體存儲開銷相比已有方法依然是很有優(yōu)勢的.圖10 展示了3 種數(shù)據(jù)名查找方法在采用不同規(guī)則集時的存儲開銷.如圖10 所示，隨著規(guī)則集規(guī)模的增大，HyBS 的存儲開銷從49.5 MB 增長到279MB，始終小于CBS和Nametrie.和CBS 相比，HyBS 能降低25.8%～30.2%的內(nèi)存開銷，而相比于Nametire 則可降低22.5%～26%的內(nèi)存開銷.

Fig.10 Memory consumption圖 10 存儲開銷

3.2 組預(yù)讀的影響

Fig.11 The effect of group-prefetching圖 11 組預(yù)讀的影響

正如2.7 節(jié)系統(tǒng)實(shí)現(xiàn)部分所述，在數(shù)據(jù)包批處理場景下，使用組預(yù)讀策略可以做到隱藏內(nèi)存訪問的時間開銷，從而降低整體時間開銷.為更加量化地驗(yàn)證組預(yù)讀策略的有效性，我們對比了HyBS 在開啟和關(guān)閉組預(yù)讀策略時的查找速度，規(guī)則集則是采用最小的Rules_0，實(shí)驗(yàn)結(jié)果如圖11 所示.我們分別在ServerAMD和SeverIntel上進(jìn)行了該測試，以驗(yàn)證不同CPU 平臺上組預(yù)讀策略的效果.柱形圖按照不同的內(nèi)存訪問策略分為2 組，分別對應(yīng)著開啟組預(yù)讀的測試組，以及關(guān)閉組預(yù)讀的測試組，其中單位為百萬數(shù)據(jù)名每秒（million names per second，MNPS）.ServerAMD的測試結(jié)果顯示，開啟組預(yù)讀可以帶來1.8 倍的性能提升，而ServerIntel的測試結(jié)果則顯示開啟組預(yù)讀帶來的性能提升僅有15%.盡管測試結(jié)果表明組預(yù)讀的確可以帶來性能提升，但是不同的CPU平臺上提升程度卻差異很大.同時我們發(fā)現(xiàn)，SeverIntel的CPU 緩存相比ServerAMD的更大，因此問題顯然不在于緩存大小.對此，我們的分析是：正如2.7 節(jié)最后所述，內(nèi)存訪問的時延可能會比CPU 計算時延（包括Hash 計算和計數(shù)器探測的時延）高很多，甚至?xí)霈F(xiàn)Hash 計算結(jié)束時第1 個數(shù)據(jù)名的數(shù)據(jù)依然沒有被完全載入CPU 緩存中，因此CPU 依然需要等待數(shù)據(jù)載入操作完成.如果2 種時延差異過大，則隱藏的時延無法使整體時延明顯降低.要使得組預(yù)讀帶來明顯的性能提升，較為理想的情況是內(nèi)存訪問時延和CPU 計算時延差異不大.因此，我們的推論是：ServerAMD的內(nèi)存訪問時延和CPU 計算的時延差異相比于ServerIntel要小很多，因此帶來的性能提升也明顯很多.后續(xù)的實(shí)驗(yàn)中，HyBS 均啟用了組預(yù)讀策略.

3.3 特征比特位圖的影響

采用特征比特位圖可以大幅度降低HyCBF 的假陽性率，進(jìn)而減少因假陽性引發(fā)的回溯操作.為了更加量化地分析特征比特位圖的影響，我們比較了HyBS 在啟用和關(guān)閉特征比特位圖時的回溯操作次數(shù)變化情況，并以CBS 中的回溯次數(shù)作為參考對比.實(shí)驗(yàn)所用的測試集以規(guī)則集中的數(shù)據(jù)名前綴為基礎(chǔ)生成，以其中最長數(shù)據(jù)名的組件數(shù)量為長度閾值（我們使用的測試集中最長數(shù)據(jù)名的組件數(shù)量為7）.當(dāng)測試集中某個數(shù)據(jù)名長度小于閾值時，我們在該數(shù)據(jù)名后面填充足夠多的隨機(jī)組件，使其長度達(dá)到閾值設(shè)定的長度，在這種極端情況下回溯操作的次數(shù)理論上將達(dá)到最大值.我們將布隆過濾器的假陽性率閾值設(shè)置為0.15%，Hash 函數(shù)的數(shù)量設(shè)置為3，以此計算得出布隆過濾器的長度.其中，HyBS 在計算時去除了重復(fù)的“共享標(biāo)記”.

實(shí)驗(yàn)結(jié)果如圖12 所示.未啟用特征比特位圖的HyBS（即HyBS 對應(yīng)的測試結(jié)果）在不同的數(shù)據(jù)集上，觸發(fā)了762～4 391 次回溯操作，在總查找次數(shù)中的占比為0.143%～0.152%，可以發(fā)現(xiàn)這個數(shù)值和我們設(shè)置的最大假陽性閾值0.15%相接近.這正好驗(yàn)證了2.3節(jié)中的推論：在計算計數(shù)布隆過濾器長度時，雖然有必要重復(fù)插入“共享標(biāo)記”，但在計算時應(yīng)當(dāng)避免重復(fù)計算它們，這樣才能得到準(zhǔn)確的計算結(jié)果，避免假陽性率出現(xiàn)冗余.CBS 則沒有考慮“共享標(biāo)記”的情況，測試結(jié)果顯示其觸發(fā)回溯的查找次數(shù)占比在0.01%～0.026%，相比設(shè)置的假陽性閾值低很多.重復(fù)插入“共享標(biāo)記”并不會導(dǎo)致假陽性率超過閾值，相反，假陽性率會進(jìn)一步下降，但這樣的低假陽性率是冗余的，并且是以更大的存儲開銷為代價的.啟用了特征比特位圖后的HyBS（即HyBS-FB 對應(yīng)的測試結(jié)果）觸發(fā)回溯操作的查找次數(shù)占比僅為0.003%～0.004%，相比未啟用特征比特位圖的HyBS 減少了99.48%～99.95%的回溯操作，相比CBS 則減少了91.84%～99.69%的回溯操作.根據(jù)圖12 的實(shí)驗(yàn)結(jié)果可知，在引入特征比特位圖后，即使考慮到“共享標(biāo)記”對假陽性率的影響，HyBS 的布隆過濾器（即HyCBF）大小依然有壓縮空間.在后續(xù)實(shí)驗(yàn)中，HyBS 均啟用了特征比特位圖.

Fig.12 The amount of backtracks圖 12 回溯次數(shù)

3.4 查找速度

3.1～3.3節(jié)的測試結(jié)果顯示，HyBS 所采用的優(yōu)化技術(shù)在壓縮存儲和提升查找效率方面效果明顯.為了評估HyBS 的整體查找性能，我們針對理想情況和極端情況在ServerAMD和ServerIntel上進(jìn)行了查找測試.首先測試了最理想情況下的性能表現(xiàn)，此時所有測試集中的數(shù)據(jù)名和對應(yīng)規(guī)則集中的數(shù)據(jù)名完全一致，因此觸發(fā)回溯操作的可能性最小.ServerAMD的測試結(jié)果如圖13（a）所示，HyBS 的查找最高可達(dá)5.29 MNPS，是CBS 的查找速度的2.2～3 倍，相比Nametrie 則可加速5.1～8 倍.圖13（b）展示了ServerIntel的測試結(jié)果，受限于較低的主頻，以及2.7 節(jié)中對組預(yù)讀策略的分析，Intel 處理器上HyBS 的性能表現(xiàn)比AMD 處理器上的差很多，最大能到2.21 MNPS，相比CBS 加速比能達(dá)到1.2～1.5 倍，相比Nametrie 則可達(dá)2.3～3.5 倍.

Fig.13 The lookup speed on ideal case圖 13 理想情況下的查找速度

為了評估極端情況下的性能表現(xiàn)，我們比較了這3 種方法在采用3.3 節(jié)中所描述的數(shù)據(jù)名填充方法所構(gòu)造的測試集上進(jìn)行的性能測試.ServerAMD和ServerIntel的測試結(jié)果分別如圖14（a）和圖14（b）所示.可以看出這3 種方法均出現(xiàn)了性能下降，其中HyBS 在ServerAMD和ServerIntel分別出現(xiàn)了25%和27%的性能下降，但其查找速度相比其他2 種方法依然更快.在AMD 處理器上，HyBS 的查找速度最大可達(dá)3.84 MNPS，相比CBS 和Nametrie 速度最大可加速4.1～5.6 倍.而在Intel處理器上，HyBS 的查找速度可達(dá)1.65 MNPS，相比CBS 和Nametrie 速度最大可加速2.2～2.5 倍.

3.5 更新速度

Fig.14 The lookup speed on extreme case圖 14 極端情況下的查找速度

Fig.15 The inserting speed圖 15 插入速度

對于規(guī)則更新這一重要性能指標(biāo)，我們同樣在不同CPU 上進(jìn)行了性能測試.圖15（a）和圖15（b）分別展示了這3 種方法在ServerAMD和ServerIntel上的規(guī)則插入性能.得益于“自底向上”的更新策略，HyBS相比其他2 種方法具有更快的更新速度.在AMD 處理器上的測試結(jié)果表明，HyBS 相比CBS 可加速1.3～1.5 倍，相比Nametrie 則可加速2.8～4.3 倍.而在Intel處理器上的測試結(jié)果表明，HyBS 相比CBS 可加速1.2～1.3 倍，相比Nametrie 則可加速2.9～3.9 倍.規(guī)則刪除的速度如圖16（a）和圖16（b）所示.雖然采用了相同的更新方法，但插入時需要為沖突的規(guī)則分配內(nèi)存，而刪除則僅需要釋放占用的內(nèi)存，這使得刪除操作的速度遠(yuǎn)遠(yuǎn)快于插入操作.ServerAMD的測試結(jié)果顯示，HyBS 的刪除速度可達(dá)6.26 MNPS，相比CBS 可加速2.9～3.2 倍，相比Nametrie 則可加速6.8～10.2 倍.ServerIntel的測試結(jié)果則顯示HyBS 的規(guī)則刪除速度最大可達(dá)3.57 MNPS，相比CBS 可加速2.1～2.3 倍，相比Nametrie 則可加速4.4～5.8 倍.

3.6 吞吐量和可擴(kuò)展性

為了對HyBS 進(jìn)行系統(tǒng)級的性能驗(yàn)證，我們測試了加載了HyBS 插件的VPP 的兩大性能指標(biāo)，包括吞吐量和可擴(kuò)展性.此外，作為對比，我們也在插件中實(shí)現(xiàn)了CBS 和Nametrie.如圖17 所示，測試環(huán)境由2臺互聯(lián)的ServerAMD組成，網(wǎng)卡則采用了2 塊雙100 Gbps接口的Mellanox ConnectX-5 網(wǎng)卡.為避免NUMA（nonuniform memory access）架構(gòu)[44]下遠(yuǎn)程內(nèi)存訪問帶來的額外時延，VPP 所有的CPU 都位于相同的NUMA節(jié)點(diǎn).此外，為了最大限度發(fā)揮CPU 的單核性能，我們關(guān)閉了CPU 超線程特性.一臺ServerAMD運(yùn)行加載了數(shù)據(jù)名查找插件的VPP，其中的包處理節(jié)點(diǎn)拓?fù)鋱D則如圖8 所示.在驗(yàn)證HyBS 的可擴(kuò)展性時，需要啟用多個CPU 以及多個網(wǎng)卡隊列.目前網(wǎng)卡的多隊列調(diào)度采用的是接收端負(fù)載均衡（RSS）技術(shù)，需要TCP/IP 包頭中的五元組信息，該技術(shù)無法支持基于數(shù)據(jù)名的隊列調(diào)度.因此，我們在附帶數(shù)據(jù)名的數(shù)據(jù)包前面封裝一個填充了隨機(jī)IP 地址、MAC 地址和端口信息的TCP/IP 包頭，以此實(shí)現(xiàn)數(shù)據(jù)包的多隊列調(diào)度.另一臺服務(wù)器則作為發(fā)包測試儀，從網(wǎng)卡其中一個接口（即發(fā)送接口）發(fā)送，同時監(jiān)聽另一個接口（即接收接口），以此分析VPP 在加載不同的數(shù)據(jù)名查找方法以及啟用不同數(shù)量的CPU 時的性能表現(xiàn).為適配數(shù)據(jù)名的長度，我們將數(shù)據(jù)包大小設(shè)置為512 B.實(shí)驗(yàn)結(jié)果如圖18 所示，我們統(tǒng)計了不同數(shù)據(jù)名查找方法在啟用了不同數(shù)量的CPU 時的吞吐量.為方便對比分析，我們將不做任何查找操作的“空”轉(zhuǎn)發(fā)時的吞吐量數(shù)據(jù)作為參照基準(zhǔn)，即圖18 中的Empty.在我們的測試環(huán)境下，“空”轉(zhuǎn)發(fā)的吞吐量為93.02 Gbps.當(dāng)僅啟用1 個CPU 時，HyBS 的吞吐量可達(dá)12.41 Gbps，而CBS 和Nametrie 則分別是4.44 Gbps和3.76 Gbps.觀察數(shù)據(jù)包大小和吞吐量數(shù)據(jù)可以發(fā)現(xiàn)，這3 種方法在實(shí)際系統(tǒng)中相比于3.4 節(jié)中的本地測試均出現(xiàn)了性能降低.不同于本地測試，系統(tǒng)測試中查找模塊需要和其他模塊共享計算和存儲資源，因此出現(xiàn)性能下降是符合預(yù)期的.隨著CPU 的數(shù)量增長，3 種方法的吞吐量均有所提升，其中HyBS 的增長速率最快.當(dāng)啟用8 個CPU 時，HyBS 的吞吐量已經(jīng)和“空”轉(zhuǎn)發(fā)一致.因此，在我們的測試環(huán)境下，HyBS 利用8 個CPU 核即可實(shí)現(xiàn)快速的數(shù)據(jù)名查找轉(zhuǎn)發(fā)，而對于CBS 和Nametrie 則分別需要13 個和14個CPU，相比HyBS 需要消耗更多的物理資源.因此，和已有的這2 種方法相比，HyBS 具有更高的吞吐量以及更好的可擴(kuò)展性.

Fig.16 The removal speed圖 16 刪除速度

Fig.17 The test architecture of VPP圖 17 VPP 測試架構(gòu)

Fig.18 The throughput and scalability圖 18 吞吐量和可擴(kuò)展性

4 總結(jié)

本文提出了一種混合計數(shù)布隆過濾器HyCBF和HyCBF 輔助的二分?jǐn)?shù)據(jù)名查找方法HyBS.在HyCPF 中將數(shù)據(jù)名前綴布隆過濾器和前綴標(biāo)記布隆過濾器合二為一，在不增加額外開銷的情況下為二分搜索過程提供更豐富的指向信息以實(shí)現(xiàn)加速.此外，針對二分搜索過程中的回溯問題，為HyCBF 中保存的每條記錄構(gòu)造特征比特位圖，進(jìn)一步減少查找開銷.最后，采用“自底向上”的更新策略加速增量更新.實(shí)驗(yàn)結(jié)果表明，HyBS 相比現(xiàn)有方法存儲開銷更小，回溯次數(shù)更少，更新性能更好，在不同CPU 上的查找速度都更快.基于VPP 框架進(jìn)行系統(tǒng)實(shí)現(xiàn)，可進(jìn)一步通過批處理和組預(yù)讀提高HyBS 性能，充分說明了其用于構(gòu)建高性能數(shù)據(jù)名查找引擎的潛力！

作者貢獻(xiàn)聲明：許可負(fù)責(zé)核心技術(shù)點(diǎn)的設(shè)計實(shí)現(xiàn)以及論文撰寫；李彥彪負(fù)責(zé)系統(tǒng)架構(gòu)并參與方法設(shè)計和論文撰寫；謝高崗負(fù)責(zé)實(shí)驗(yàn)方案設(shè)計；張大方指導(dǎo)本文工作開展和論文撰寫.