大規模數據流統計中冷熱流替換策略優化*

喬冠杰，呂高鋒，譚 靖，莫露莎

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

隨著網絡的發展，流量規模的不斷增大，對大規模流量進行統計變得十分重要，早期的網絡管理功能，如流量統計，是固化在相應的網絡設備中的，基于端口對交換機或路由器連接不同網絡的流量進行統計。隨著網絡的發展，這種方式已經不能滿足網絡管理的需求。

網絡可視化應運而生，對網絡的實時監控越來越重要。網絡就像公路，需要實時掌握主干道信息，了解每條路是否堵塞，了解車流密度等等。車輛就相當于網絡中的流量，只有掌握道路信息，才能更好地調度交通，保證道路暢通。網絡也是一樣，只有實時去監測流量，才能了解網絡狀態，進行流量調度、擁塞控制[1]和異常檢測等等。

為了應對大規模的流量統計[2]，各種測量結構相繼產生，一種典型的網絡測量結構是Sketch[3]。Sketch是一種基于哈希的緊湊的數據結構，通過哈希減少流量的存儲空間，同時可以對流量進行統計。針對不同流量統計的問題，基于Sketch的統計算法不斷發生改變，流量統計中一個典型問題是對top-k流[4]進行統計，本質是將大象流[5]和老鼠流[6]進行分離，實現對大象流的精確統計，同時對老鼠流實現粗略統計。Elastic Sketch[7]便是將老鼠流和大象流分離進行統計的典型。使用重部存儲大象流，輕部存儲老鼠流，實現大象流和老鼠流的分離。

但是，Elastic Sketch在計數器更新時也存在問題，在Elastic Sketch的替換策略中，當負投票和正投票比值大于一個閾值時，就會發生替換。如果這時來的一條流是冷流，則會把冷流插入到重部中去，并將標志位設置為true，此時便會將冷流誤判為熱流存到重部中。本文對這個問題進行了優化，解決了冷流被誤判存入重部的問題。同時，針對被替換入重部的流不一定是最大流的問題，提出了一種基于最大值的替換策略，保證了重部中永遠記錄最大的流。

2 相關研究

網絡流主要根據五元組、包的大小來分類。在網絡中存在各種各樣的數據包，如果按照五元組或者包的大小分類的分類方法，對每一類數據包都分配一個計數器來存儲其數值，雖然測量結果準確，但是需要很大的空間來存放計數器。所以，研究人員采用哈希方法計算流的哈希值，根據哈希值的范圍來確定所需的存儲空間大小，各種數據包根據所得到的哈希值進行分類，可以在極大程度上減少存儲空間。

2.1 典型的Sketch結構

2.1.1 Count-Min Sketch

一種典型的方法是使用Sketch數據結構，其代表是Count-Min Sketch，如圖1所示。由于使用哈希函數產生哈希值可能會發生沖突[8,9]，多個不同種類數據包可能會哈希到同一個桶內，這個桶的計數值就會偏大，為了減少哈希值沖突引起的誤差，研究人員設計了Count-Min Sketch。它通過設置多個哈希函數，用二維地址空間進行存儲，數據包經過多個不同哈希函數的哈希后，得到對應的哈希值，這些哈希值有可能產生沖突，即不同種類的數據包可能在同一個哈希函數哈希之后有相同的哈希值，則根據哈希值來確定的數據包出現的次數則會偏大，所以建立多個哈希函數，取這其中最小的哈希值，這個值最接近實際數據包的數據。

Figure 1 Count-Min Sketch structure圖1 Count-Min Sketch結構

在高速網絡流量下[10,11]，很難做到把所有信息都準確地記錄下來，而且會消耗大量存儲資源，計算開銷也很大，不能滿足實時性。并且在很多情況下，并不需要十分準確的數據，而是只需要滿足一定條件下的估計值。如果只設置了一個哈希函數，大量的數據流就會哈希到同一個桶中，產生沖突，誤差就會很大，而通過設置多個不同的哈希函數，取其中最小的哈希值會減少誤差，但也要合理地選取哈希函數數量，選取太多哈希函數顯然會加大計算開銷。

當可用帶寬很小時，發送大Sketch將導致長延遲并影響用戶流量。問題是如何使Sketch尺寸小于可用帶寬，尤其是當網絡不能正常工作時。一個解決方案是為相同的網絡流量構建不同大小的Sketch。例如，構建2個SketchS1和S2，其內存大小為M和M/2，在可用帶寬很小時可以將S2發送到收集器。更好的解決方案是僅構建S1，并將其快速壓縮為一半。

2.1.2 Elastic Sketch

(1)Elastic Sketch數據結構。

Elastic Sketch是將冷流與熱流分離的典型結構。由于數據量十分龐大，記錄下所有數據流的IP是十分困難的，而且這也將消耗大量的內存資源，而遠端服務器受限于部署環境，很難提供如此龐大的內存資源。對于所研究的某些任務，這些冷流并不必考慮，因而將熱流與冷流分離，并在后續任務中丟棄冷流，只考慮熱流會明顯節省內存資源和傳輸帶寬。

文獻[7]提出將存儲空間劃分為2個部分，分別是重部和輕部，其中重部存儲熱流，輕部存儲冷流，如圖2所示。

Figure 2 Separate hot flow and cold flow圖2 分離熱流與冷流

重部劃分為N個桶，每個桶存儲4個字段，(key，vote+，flag，vote-)，分別是流ID、正投票、flag標志和負投票。其中流ID標識一條流，正投票記錄屬于此流的數據包數量，負投票記錄不屬于此流的數據包數量，flag標志表示輕部是否可能包含此流的正投票。當一條流數據f到來時，提取它的流ID，并調用mmh3哈希函數，得到哈希值h(f)(modN)的值value，根據value的值將流f與重部對應索引的桶中流F匹配。

Elastic Sketch將冷流和熱流分離，實現了對熱流較為精確的統計，對冷流的粗略統計，是一種經典的對熱流進行統計的結構，但也存在著一些問題，將在第3節進行詳細說明。

(2)準確度分析。

①重部沒有錯誤：對于標志為F(False)的流，記錄的正投票是沒有錯誤的流量大小;對于標志為T(True)的流，記錄的正投票是流量大小的一部分,仍然沒有錯誤，而另一部分記錄在錯誤的輕部下。

②輕部不記錄流量ID，只記錄冷流量的大小，因此可以使用許多小型計數器(例如8位計數器)，而傳統Sketch需要使用幾個大型計數器(例如32位計數器)以適應熱流動。因此，本文的輕部可以非常準確。總之，熱和冷的精確度都很高。在最壞的情況下熱碰撞使準確性降低：當2個或更多的熱流被映射到同一個桶中時，一些熱流被驅逐到輕部和可能會使一些冷流量顯著高估。

(3)基于組相連的熱碰撞優化。

熱碰撞的解決方案是：讓重部中的每個桶存儲多個流量，它允許在一個桶中記錄幾個熱流，因此熱碰撞率顯著下降。本文采用這種算法來降低熱碰撞率。

如果流f1替換流F，將流F驅逐到輕部，那么認定f1為熱流。假設大量的流f2到來，將流f1驅逐到輕部，然而f1是熱流，它被驅逐到輕部，被認定為了冷流，這就是熱碰撞。

為了解決這個問題，文獻[7]中提出了優化方案，將原本每個桶只存儲一條流擴大為存儲多條流，如圖3所示。

Figure 3 Optimization scheme of hot flow collision圖3 熱流碰撞優化方案

每個桶中存儲多條流，但是每個桶中的流共用一個負投票計數器，當一條流f到來時，將它哈希到其中一個桶中，如果桶沒有滿，將流插入到桶中；如果桶滿了，并且與桶中某一條流ID匹配，則這條流對應的vote+加1，如果都不匹配，那么將共用的負投票計數器加1。流f到來時，考慮是否驅逐桶中的某條流，將負投票vote-與桶中流對應最小正投票(vote+)min的比值與閾值λ作比較，如果vote-/(vote+)min<λ，則將流f驅逐到輕部，否則取出輕部中f的計數，其余操作與前一種方案相同。由于每次驅逐桶中流時，只會驅逐每個桶中正投票計數最小的，因此減少了熱流被驅逐的可能性。

2.2 Sketch應用

基于Sketch構建測量解決方案：Sketch可用于許多測量任務，例如Heavy Hitter檢測[12]、流量變化檢測[13]和流量大小分布估計。例如，要計算通過端口80訪問Web服務器的唯一源的數量，可以簡單地根據端口80過濾流量，然后使用位圖來計算唯一源地址的數量。另一個例子是Heavy Hitter檢測，這對于數據中心的流量工程很重要。為了識別 Heavy Hitter，首先使用Count-Min Sketch來維護每個流的計數；然后，在可逆Sketch中識別哈希到重計數器的潛在流量，并使用Count-Min Sketch驗證它們的實際計數。

Sketch在進行數據處理之前，首先要根據研究內容挑選合適的測量數據包，比如為了計算具有相同內容的冗余數據包的數量，可以將數據包主體散列，而不是每次都存儲和比較整個數據包主體。對某些特定的流進行研究時，分類具有重要作用，例如，如果來自IP地址192.168.1.1的流量太多，可以過濾192.168.1.1/32的數據包，即使用一個計數器用于統計來自特定IP的流量，另一個計數器用于統計來自子網192.168.1.0/24的剩余流量。對于流分類，可以指定與流字段上的數據包匹配的通配符規則，并允許流字段中的某些位為通配位。例如，規則可以匹配源IP前綴192.168.1.0/24上的數據包，其中低8位是通配位。

3 冷熱流替換策略優化

3.1 替換問題及原因分析

在Elastic Sketch中，重部的替換策略是當負投票與正投票的比值大于一個閾值時，新來的流會替換重部中保存的流，未考慮新流大小。如果新流是一條冷流，這條冷流會因為替換策略被存入重部，并將標志位設置為T，這樣會導致冷流占據重部，影響熱流的測量精度；另一方面，這種替換策略還可能會導致替換頻繁發生，當這條冷流因為替換策略要發生替換時，又來一條冷流，那么這時新的冷流又被記錄在重部，導致了替換的頻繁發生，并且熱流得不到記錄。現有的替換策略無法確保存入重部的是一條絕對大流，只要滿足替換條件，剛來的流就會替換重部中的流，但無法保證這條流一定比之前的流大。

造成冷熱流替換的原因：

(1)單條冷流數量較少，但冷流總量很多；

(2)存儲熱流的空間有限，發生熱碰撞。

替換策略設計的原則：

(1)防止冷流被誤判為熱流進入重部；

(2)提高發生替換時的閾值，超過一定值再發生替換；

(3)增大重部的存儲空間，減少重部熱碰撞。

針對上述問題本文在3.2節提出了關于替換的優化策略，保證了冷流在頻率較低的情況下不會替換重部中的熱流。3.3節提出了基于最大值替換策略，對熱流進行精確統計的同時，將最大流候選保存在countmax中，保證了發生替換后重部中存放的一定是最大的流，同時解決了冷流頻繁進入重部的問題。

3.2 優化1 基于歷史值的冷熱替換策略

在Elastic Sketch中，流F是存儲在重部中的流，一條流f插入的過程分為以下4種情況：

(1)如果桶是空的，直接在桶中插入(f,1,F,0)；

(2)如果f=F，那么直接將vote+加1；

(3)如果f≠F，首先設定閾值λ，如果vote-/vote+<λ，那么將流f驅逐到輕部，vote-加1；

(4)如果f≠F，并且vote-/vote+≥λ，將桶中字段設置為(f,1,T,0)，將F驅逐到輕部。

在第4種情況下，如果流f是第1次進行匹配，那么就會把冷流f插入到重部，并且將flag設置為T，這時認定f為熱流，然而流f只出現過一次，本文對此進行以下優化：

如果f≠F，并且vote-/vote+≥λ，這時從輕部取出流f的計數number，如果(number+1)/vote+≥1，那么將桶中字段設置為(f,1,T,0)，將F驅逐到輕部，否則將流f驅逐到輕部。如圖2所示，流f5插入重部，由于其中f5哈希之后是插入到重部的空處，在空處直接插入(f5,1,F,0)；流f1插入重部，哈希之后與重部中流ID字段匹配，將f1的vote+加1；流f8插入重部，哈希之后與流ID字段不匹配而且vote-/vote+小于閾值，將f3的vote-加1，將f8驅逐到輕部；流f9插入重部，哈希之后與流ID字段不匹配而且vote-/vote+大于閾值，將f4驅逐到輕部，f4所在桶更新為(f9,1,T,0)。

上述優化解決了冷流第1次進入就會替換熱流的問題，很大程度上解決了頻繁替換的問題。

輕部是一個Count-Min Sketch，本文中設置了8個計數器，對于插入到輕部中的流，如果是原始數據的流f，經過8個互不相同哈希函數哈希之后，在對應的計數器相應位置計數加1；如果是桶中的流F，那么在對應計數器的相應位置計數加上vote+的值。

3.3 優化2 基于最大值的替換策略

針對熱流碰撞問題，以及冷流會替換重部中熱流的問題，本文進一步提出了基于最大值替換策略。引入countmax表，將結構分為輕部和重部，重部每個桶包含3個位置，用于存儲熱流，每個位置分別記錄熱流ID和熱流數目。輕部包含2個獨立的哈希函數，第2個哈希函數對應一組計數器，用于存放冷流的哈希值，第1個哈希函數也對應一組計數器，用于存放第2個哈希函數對應的每組計數器值的最大值，并且第1個哈希函數對應的計數器包含一個countmax，用來存放第1個哈希函數對應所有計數器的最大值。

當流到達時，被哈希到重部的一個桶中，重部每個桶有3個位置可以存放3條熱流，若有空位置，并且流ID與桶中的流ID不同，將它插入到空位置中，并將計數器置1；若沒有空位置，流ID與桶中流ID相同，增加對應位置流的計數器；若沒有空位置，并且流ID與桶中流ID不同，將流通過hash1和hash2哈希到輕部的一個桶中。這個輕部桶只保存流的計數，之后將這個桶的計數和max進行比較，若桶計數值大于max，則將桶的計數值復制給max，再將max值與countmax進行比較；若大于countmax則將max值復制給countmax。若countmax值大于重部中某個位置的流計數，則將剛來的流與那個位置的流進行替換，用countmax的值作為這條流的計數值，被替換的流哈希到輕部中去，并用被替換的這條流的計數替代輕部中對應位置計數器的計數值。

如圖4所示，當流f23到達時，重部3個位置已滿，并且沒有流ID與其匹配，f23通過2次哈希函數到達輕部的計數器，更新計數值，并且計數值沒有大于max值，更新結束；當流f15到達時，重部3個位置已滿，并且沒有流ID與其匹配，f15通過2次哈希函數到達輕部的計數器，更新計數值，并且更新了max值和countmax值，由于countmax值沒有超過重部最小計數值，所以不發生替換，更新結束；當流f13到達時，重部3個位置已滿，并且沒有流ID與其匹配，f8經過2次哈希函數到達輕部計數器，更新后max值變為12，同時countmax值也改為12，這時，計數值大于f6流的計數值11，所以發生替換，將f6更新到輕部中，將(f13,12)插入到重部中，更新結束。

Figure 4 Replacement strategy based on maximum value and group connection圖4 基于最大值和組相連的替換策略

基于最大值和組相連的替換策略的優勢在于將所有熱流的候選保存在了countmax中，通過3個不相關的哈希函數h1、h2、h3，將流分散在不同的位置進行存儲，很大程度上降低了哈希沖突帶來的影響，確保了一條冷流幾乎不可能更新countmax值，這樣冷流不會被記錄到重部，解決了冷流替換熱流的問題；同時，countmax表保存了h3對應的流的一個最大計數，countmax記錄了h2、h3映射區域的最大值，這樣在輕部重部發生替換的時候可以直接確定候選流計數值，避免了低頻冷流被記錄到重部中的情況。

4 實驗及結果分析

4.1 實驗平臺

基于Fast平臺進行算法測試，用戶可以選擇全定制功能開發模式，即基于平臺提供的FPGA開發接口(UM接口)和軟件開發接口(UA接口)開發自己的功能。統計模塊中的判斷模塊、重部在UM接口實現，統計模塊中的輕部在UA接口實現，為了加快實驗測試，流量感知的數據統計與分離算法在UA上實現。

4.2 統計模塊實現

統計模塊主要分為3個部分：重部、判斷模塊和輕部。重部是一個哈希表，它可以卸載到硬件實現，本文考慮實際情況，由軟件進行實現。它存儲4個字段的信息，存儲空間大小是可擴展的，只需要將原重部復制并合并，刪除其中的一半流，其中原有的h()%t轉變為h()%(2t)，比如假設原重部大小為4 KB，它劃分為4塊1 KB的存儲空間，流f1存儲位置為h(f1)%4=1,擴展后，h(f1)%8=5,則刪除原重部中的流f1。其中，h()表示一條流鍵進行哈希運算之后的結果，t表示重部計劃分的塊數。判斷模塊主要由哈希函數和判斷語句組成。輕部是Count-Min Sketch，由軟件實現。它存儲從重部中被驅逐流的計數，它共由8個計數器組成，計數器的存儲空間大小也是可變的。

mmh3哈希函數由C語言實現，是一種非加密散列函數，適用于一般的基于散列的查找。它產生一個32位或128位散列值。使用128位時，x86和x64版本不會生成相同的值，因為算法針對各自的平臺進行了優化，因而本文調用該哈希函數不會產生沖突。

4.3 誤差分析

數據量為2 000 000條流，Sketch和桶大小為32,64,128時的誤差統計結果如圖5a～圖5c所示，數據量為5 000 000條流，Sketch和桶大小為32，64,128時的誤差統計結果如圖5d～圖5f所示,數據量為10 000 000條流，Sketch和桶大小為32,64,128時的誤差統計結果如圖5g～圖5i所示。

Figure 5 Statistical results圖5 統計結果

將統計計數量與實際計數量作為誤差值，其中基礎版統計結果和優化版統計結果如圖5所示，橫坐標x表示誤差值為2x-1～2x的數據，縱坐標表示具有該誤差數據的總量，將誤差不超過2的統計認定為準確的,準確率=準確數/過濾數據種類數。

當Sketch和桶大小比較小時，結果會出現誤差，但是總體上準確率也比較高，并且在Sketch和桶大小一定時，統計數據量越大，相對準確率越高，這是由于減小了由于數據統計量小帶來的偶然誤差。

對于熱流和冷流的分離，組相連優化版本也減小了對熱碰撞以及冷流冒充熱流的誤差，并且在分離過程中數據量準確率高，丟失數據的概率比較低。隨著Sketch的增大，準確率也隨之提升，但是存儲空間也增大，因而在保證準確率的同時，取合適大小的Sketch也比較關鍵。隨著數據量的增大，準確率也隨之提升，減小了由于數據量過小帶來的偶然誤差。

5 結束語

本文針對大規模數據流統計中的典型結構Elastic Sketch中冷熱流替換策略進行優化，針對冷流第1次進入重部就替換熱流的問題進行了優化，同時提出了基于最大值和組相連的替換策略，保證了重部中存儲的都是最大的流，解決了冷流頻繁替換熱流的問題，同時大大降低了熱流碰撞的概率。相比于傳統的測量統計方法，提高了統計精度，同時減少了內存占用。