一種表項數據存儲方法及查詢方法與流程
2024-04-16 15:26:05
1.本發明屬於數據存儲及查詢技術領域，尤其涉及一種表項數據存儲方法及查詢方法。
背景技術：
2.隨著網際網路的急劇擴展，網絡規模呈現多樣性，動態性、大流量，高並發等諸多特點。在高速網絡快速發展的同時，對網絡數據通信系統的數據處理能力和效率提出了更高的要求。目前各類科研院所及信息通信廠商在設計數據通信系統時均考慮了網絡流量的多樣性和大容量問題。多樣性體現了業務的種類繁多，大容量則衡量系統處理數據的性能。在規模達到百萬級數據表項的應用場景下，數據通信系統在大容量表項中實現特定轉發表的快速查找具有一定的難度。目前能同時滿足大容量、高實時等擴展要求的系統比較少見，核心原因在於缺少一種新的數據存儲和查找方法。
3.目前常見的高速大容量數據通信系統更多是採用軟硬體結合的架構，軟體處理較為複雜的數據重構和深度計算，硬體提供模型化的高速報文流水線處理和轉發。常見的是採用四層架構，包括管理層、控制層、軟體轉發、硬體轉發層。管理層、控制層、軟體轉發層均採用純軟體實現，硬體轉發層通常使用專用轉發晶片或者fpga設計。但在大容量存儲轉發方面依然存在一些缺陷，一是對軟硬體架構的數據通信系統採用二維的hash存儲方法，硬體平臺需要根據hash衝突大小擴展有限的衝突深度，有限的衝突深度無法解決特殊情況下衝突過大導致的存儲失敗問題；二是在大容量存儲場景下，資源分配均按照最大衝突深度分配，造成大量存儲資源浪費；三是二維的hash存儲方法無法在有限的內存空間中充分利用現有空閒內存，內存利用率較低；四是多維hash存儲無法像一維線性存儲進行存儲單元的高效提取，導致多維hash存儲的表項存取效率低。
技術實現要素：
4.本發明的目的在於，為克服現有技術缺陷，提供了一種表項數據存儲方法及查詢方法,為數據通信系統提供了在存儲資源受限條件下的數據存儲和快速查找機制。
5.本發明目的通過下述技術方案來實現：
6.一種表項數據存儲方法，其特徵在於，所述方法包括：
7.通過預設哈希算法將表項的特徵數據進行散列，生成所述表項數據的存儲單元地址；
8.通過所述預設哈希算法將存儲空間壓縮至預設範圍；
9.將所述特徵數據輸入所述預設哈希算法的結果作為壓縮後的存儲空間單元編號；
10.將表項數據按存儲單元地址存儲在所述壓縮後的存儲空間中對應的存儲單元。
11.進一步的，所述方法還包括：
12.若存儲某一表項數據時，存儲單元地址對應的存儲單元已被佔用時，對所述表項數據進行移位另存儲。
13.進一步的，所述表項數據的欄位結構包括控制欄位和表項實體，所述控制欄位包括是否佔用、計算欄位、另存儲欄位、前驅欄位和後驅欄位，所述計算欄位為存儲單元地址。
14.進一步的，所述對所述表項數據進行移位另存儲具體包括：
15.按照內存地址增大方向查找下一個未佔用的存儲單元作為另存儲地址，所述表項數據的前驅欄位和後驅欄位均按照實際前驅和後驅的位置進行更新賦值。
16.進一步的，若有新的表項數據經過所述預設哈希算法散列後命中被另存儲表項佔據的存儲單元，則所述另存儲表項繼續移位另存儲並將所述新的表項數據存儲在所述存儲單元。
17.進一步的，所述特徵數據包括五元組信息。
18.進一步的，所述特徵數據包括五元組信息中的96bit信息。
19.另一方面，本發明還提供了一種表項數據查詢方法，所述方法用於查詢前述方法存儲的數據，所述方法包括：
20.響應於接收到的報文，提取所述報文的特徵數據，通過所述預設哈希算法對所述特徵數據進行壓縮，計算所述報文的存儲單元；
21.根據所述報文的存儲單元對表項進行精確匹配；
22.當表項精確匹配成功，則完成報文轉發。
23.進一步的，所述根據所述報文的存儲單元對表項進行精確匹配具體包括：
24.提取存儲單元並判斷所述報文的存儲單元是否有效，有效則進行精確匹配，無效則將所述報文丟棄或上傳cpu；
25.若所述精確匹配失敗則進一步判斷所述報文的後驅欄位是否有值，有值則提取所述後驅欄位存儲單元並進行精確匹配，無效則將所述報文丟棄或上傳cpu。
26.進一步的，所述提取存儲單元並判斷所述報文的存儲單元是否有效包括一次提取多個存儲單元判斷所述報文的存儲單元是否有效。
27.本發明的有益效果在於：
28.(1)本發明解決數據通信系統中大容量數據衝突碰撞後的數據移位存儲問題，通過表項特徵數據採用特定hash算法計算hash值，提出衝突情況下的表項移位存儲方法，實現衝突規避。
29.(2)本發明針對固定規格的表項數據，可以合理壓縮並調優，滿足實際情況下的衝突要求，平衡資源和效率的關係，從而固定有限的存儲空間資源。
30.(3)將數據表項通過hash算法映射到唯一的存儲單元，衝突情況下採用線性一維存儲方法，將衝突表項向內存地址增大方向依次存儲，綜合利用存儲資源。數據轉發通過提取線性存儲的多個存儲單元進行依次匹配，在有限的衝突深度下，依靠表項特殊關鍵欄位輔助查找，最終到達存儲資源和查找效率的平衡。
附圖說明
31.圖1是本發明實施例提供的存儲方法及查詢方法軟硬體架構示意圖；
32.圖2是本發明實施例表項壓縮方法示意圖；
33.圖3是本發明實施例表項存儲單元欄位結構示意圖；
34.圖4是本發明實施例表項線性存儲和衝突規避示意圖；
35.圖5是本發明實施例表項數據查詢方法流程示意圖。
具體實施方式
36.以下通過特定的具體實例說明本發明的實施方式，本領域技術人員可由本說明書所揭露的內容輕易地了解本發明的其他優點與功效。本發明還可以通過另外不同的具體實施方式加以實施或應用，本說明書中的各項細節也可以基於不同觀點與應用，在沒有背離本發明的精神下進行各種修飾或改變。需說明的是，在不衝突的情況下，以下實施例及實施例中的特徵可以相互組合。
37.基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
38.傳統方法在大容量存儲轉發方面依然存在一些缺陷，一是對軟硬體架構的數據通信系統採用二維的hash存儲方法，硬體平臺需要根據hash衝突大小擴展有限的衝突深度，有限的衝突深度無法解決特殊情況下衝突過大導致的存儲失敗問題；二是在大容量存儲場景下，資源分配均按照最大衝突深度分配，造成大量存儲資源浪費；三是二維的hash存儲方法無法在有限的內存空間中充分利用現有空閒內存，內存利用率較低；四是多維hash存儲無法像一維線性存儲進行存儲單元的高效提取，導致多維hash存儲的表項存取效率低。
39.為了解決上述技術問題，提出了本發明一種表項數據存儲方法及查詢方法的下述各個實施例。
40.實施例1
41.本實施例是以軟硬體架構的數據通信系統為基礎，該系統分為表項計算控制單元和表項快速查找單元。參照圖1，如圖1所示是本實施例提供的存儲方法及查詢方法軟硬體架構示意圖。其中，表項快速查找單元採用硬體fpga構建，包括表項分發控制器、會話存儲單元、表項查詢引擎等單元。本實施例以該數據通信系統為基礎闡述大容量數據表項在控制面和轉發麵的存儲和查詢過程。表項計算控制單元的表項存儲計算將會話核心或路由核心產生的大容量表項經過hash計算，採用一維線性存儲方法，規避hash衝突，實現大容量數據表項的存儲，該存儲方式精確映射到硬體轉發平面，硬體轉發平面依靠提取衝突數據區的存儲單元，同時逐項比對數據表項實現高速業務流量的轉發。
42.軟體平臺中表項存儲計算單元根據特定hash算法將表項特徵數據進行散列，生成可映射於一維存儲空間的序列號，該序列號將作為該表項的存儲單元入口地址。若要實現表項唯一映射於一維存儲空間，則可以實現表項的精確匹配和命中，但實際情況下hash存在衝突，衝突的表項不再開闢動態空間掛接在其理論的存儲單元入口之後，而是依次向其存儲單元序列號遞增方向尋找未存儲單元進行表項移位另存儲。硬體平臺的表項存儲，在硬體基礎地址上偏移序列號進行存儲，存儲的相對順序依然與軟體層保持一致。
43.具體地，本實施例提供的表項數據存儲方法如下：
44.以會話類表項為例，為完成100萬條表項的高效存儲和快速查詢，其關鍵特徵數據為五元組信息，提取其中關鍵信息96bit作為特徵數據k，理論上是在2
96
+1存儲空間x(i)(x代表一段未壓縮的連續存儲空間，i為該空間中存儲單元編號，取值範圍：0≤i≤2
96
)中覆蓋100萬條會話表項。通過特定的hash函數將存儲空間x(i)壓縮到大於100萬並遠小於2
96
大小的空間y(j)(y代表一段經過壓縮的連續存儲空間，j為該空間中存儲單元編號，取值範圍：0
≤j《2
96
)中。將特徵數據k作為輸入，hash(k)為壓縮後的結果w，w的取值為0≤w《2m(m《96)，該值將作為y存儲空間的存儲單元編號。
45.m的取值經過隨機數仿真實驗，當存儲100萬條會話表項，在m＝24(則w的取值為0≤w≤2
24
)，hash函數使用xor算法或murmurhash算法時，隨機hash衝突碰撞的概率維持在相同水平，概率範圍為4％～5％，證明100萬條會話表經過hash算法壓縮後有約95％-96％的表項條目可以在y存儲空間中無衝突存儲並可單次精確命中，約4％-5％表項條目可經過一次或多次查詢，最多5次可精確匹配，該情況較好地兼顧了資源和效率的需求。參照圖2，如圖2所示是本實施例表項壓縮方法示意圖。
46.本實施例針對會話樣本衝突提出了一種移位另存儲方法。
47.具體地，某表項數據的特徵數據k經過hash計算後得到壓縮值w，將該表項存放到y存儲空間的y(w)存儲單元中。參照圖3，如圖3所示是本實施例表項存儲單元欄位結構示意圖。當該存儲單元的佔用標誌為未佔用(標誌n標識)時，將該表項按照圖3所示格式存儲於y空間的y(w)存儲單元。此時，存儲單元中y(w)欄位為該表項的理論存儲位置，另存儲y(l)欄位(當理論存儲位置被佔用時需要存儲到其他位置，稱為另存儲)與計算y(w)欄位相同，前驅y(p)欄位(與自己具有相同理論存儲值y(w)的前一個存儲單元)和後驅y(n)欄位(與自己具有相同理論存儲值y(w)的後一個存儲單元)為無效值；當該存儲單元的佔用標誌為已佔用(標誌y標識)，即產生hash衝突，無需動態開闢新的內存單元進行表項存儲，只需按照內存地址增大方向查找下一個存儲單元佔用標誌為n的區域，該存儲單元的y(w)欄位為hash計算值即理論存儲位置，另存儲y(l)欄位為新佔用標誌為n的存儲單元位置，前驅y(p)欄位和後驅y(n)欄位均按照實際前驅後驅的位置進行更新賦值，因為該計算涉及表項數據重構和前後移位存儲，存儲計算過程均由軟體層表項存儲計算單元完成，並在表項更新時將所有變化的表項一次全部更新到硬體平臺的fpga中完成表項刷新。
48.參照圖4，如圖4所示是本實施例表項線性存儲和衝突規避示意圖。當三條表項通過hash均命中到y(1)存儲單元時，第二條衝突表項存放y(2)區，第三條衝突表項因為y(3)存儲單元被佔用，則存儲到下一個未佔用的y(4)存儲單元。同理，當有四條表項通過hash均命中到y(6)存儲單元時，若y(6)～y(9)存儲單元均未佔用，則依次存儲。
49.當新的一條表項經過hash命中y(7)存儲單元時，但y(7)存儲單元已被hash為y(6)的衝突表項佔用，此時，佔用y(7)存儲單元的hash為y(6)的表項及其後續的hash為y(6)的表項需要依次往後移位另存儲，讓出y(7)存儲單元供本次插入的實際hash值為y(7)表項存儲。存儲算法為：y(w)位置如果未被佔用則可以存儲hash為y(x)的表項。但當需要存儲hash為y(w)表項時，若y(w)位置被hash為非y(w)表項佔用，則y(w)位置上的hash為非y(w)表項及其後續衝突表項均需要移位另存儲。
50.本實施例一維hash存儲方法與現有的二維hash存儲方法相比，在內存耗費方面將節約(w+1)*n(w為hash(k)壓縮結果最大值，n為衝突深度)個存儲單元。
51.本實施例針對固定規格的表項數據，可以合理壓縮並調優，滿足實際情況下的衝突要求，平衡資源和效率的關係，從而固定有限的存儲空間資源。將數據表項通過hash算法映射到唯一的存儲單元，衝突情況下採用線性一維存儲方法，將衝突表項向內存地址增大方向依次存儲，綜合利用存儲資源。數據轉發通過提取線性存儲的多個存儲單元進行依次匹配，在有限的衝突深度下，依靠表項特殊關鍵欄位輔助查找，最終到達存儲資源和查找效
率的平衡。
52.本實施例中大容量表項在有限的存儲空間中結合hash方法實現線性存儲，數據樣本特徵值經過特定hash將理論存儲空間壓縮，減少存儲資源耗費，不同數據樣本因hash造成的衝突採用向內存地址增大方向依次移位存儲，但本屬於某存儲單元的表項不應該被非該存儲單元存儲的表項所佔用，整個線性存儲過程中遵循某表項無衝突情況下的存儲是確定性的原則。
53.本實施例存儲單元中除了表項數據區域外，添加表項控制欄位，包括單元佔用標誌、理論計算y(w)、另存儲y(l)、前驅y(p)、後驅y(n)等信息。移位存儲算法中表項的增加、刪除依靠控制欄位快速完成存儲空間中具有關聯關係的表項更新，同時在硬體轉發層面指導表項的精確匹配過程。
54.實施例2
55.本實施例提供了一種表項數據查詢方法，用以查詢以前述實施例提供的存儲方法所存儲的表項數據。
56.參照圖5，如圖所示是本實施例表項數據查詢方法流程示意圖。
57.網絡流量報文進入數據通信系統後，在硬體平臺的fpga中首先進行報文的五元組信息提取，通過hash函數將特徵數據進行壓縮，計算出該報文匹配的表項存儲單元y(w)，從dram中一次讀取n個存儲單元，n需要根據實際的衝突規模確定，讀取n個存儲單元有以下原因，一是因為本專利採用的是地址增大方向的一維線性存儲方法，y(w)為起始的存儲單元可能存在多個衝突的hash表項，針對於y(2
24
)存儲空間存儲100萬會話表項依然是均勻分布且稀疏的，一次讀取n個存儲單元有利於將相關衝突表項全部取出用於精確比對。二是硬體進行一次dram數據獲取存在系統時鐘開銷t，一次n個存儲單元的讀取比多次1個存儲單元讀取更為高效。
58.提取了n個存儲單元後，首先判定y(w)存儲單元是否有效(有效則佔用標誌為y，無效則佔用標誌為n)，有效則進行精確匹配，無效則丟棄/上cpu。在y(w)有效情況下進行精確匹配，匹配失敗則進一步判斷該表項的y(n)欄位是否有值，有值則提取y(n)存儲單元並進行精確匹配，無效則丟棄/上cpu，直到判斷某y(x)的y(n)無效時，則完成所有表項的判斷。該過程中一旦表項精確匹配，則完成報文轉發。依據本文的隨機數仿真實驗，在存儲100萬條表項的條件下，約4％-5％表項條目可經過一次或多次查詢實現精確匹配，最多5次可實現精確匹配。
59.本實施例在提取報文特徵數據後並通過hash壓縮，可以直接定位數據的存儲單元起始位置，且在單次提取的線性衝突存儲單元中，可以依靠控制欄位在較小的衝突深度下完成精確匹配。
60.按照前述實施例列舉的會話表項示例，最大5次則可完成精確匹配，具體的衝突深度需要根據實際的樣本數據規格和資源效率等需求擬定。
61.本實施例線性存儲的查錶速度比非線性存儲查錶速度節約最大t*n(t為一次dram內存提取的時鐘開銷，n為衝突深度)個時間單元。
62.以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明的保護範圍之內。