[發明專利]數據存儲方法、查找方法及裝置

有效

• 申請號: 201210048605.9
• 申請日: 2012-02-28
• 公開（公告）號: CN102622434A
• 公開（公告）日: 2012-08-01
• 發明（設計）人: 劉恒;楊俊杰
• 申請（專利權）人: 成都市華為賽門鐵克科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

本申請要求于2011年12月31日提交中國專利局、申請號201110459396.2、發明名稱為“數據存儲方法、查找方法及裝置”的中國專利申請的優先權，其全部內容通過引用結合在本申請中。

技術領域

本發明實施例涉及計算機技術，尤其涉及一種數據存儲方法、數據查找方法及裝置。

背景技術

三態內容可尋址存儲器(Ternary?Content?Addressable?Memory，TCAM)中每一個bit的狀態可以是“0”或“1”，或者是第三種狀態“don’t?care”，所以稱為“三態”。這個特點使TCAM具有對所查找數據的位域具有篩選功能，TCAM表內所有條目都可以并行訪問，例如，如果TCAM有100條表項，能一次對這100條表項進行對比操作，相對與普通的輪詢查找方法，提高了查找的速度。然而，TCAM成本比較高，存儲空間的單位價格高于普通的SRAM，耗能也遠遠高于SRAM。

TCAM所使用的特定key長度主要有以下四種標準位寬：80bit，160bit，320bit和640bit。現有方法的TCAM表項下發過程是根據待存儲的key值位寬選擇需要用到的標準位寬，選擇標準是選擇大于待存儲的key值位寬的最小標準位寬。例如，待存儲的key值是170bit，則選擇320bit的標準位寬進行下發。并將待存儲的key值對應的關聯數據下發到該key值的Index為偏移地址的DDR?DRAM地址中。

然而，在實際應用中，TCAM的key值長度因業務的需要各有不同，很難達到以上標準位寬。例如：報文的key值長度為330bit，超過了320bit，需要使用標準位寬為640bit的表項來存儲，多出的640bit-330bit＝310bit用mask碼表示，該表項浪費了310bit空間。因此，非標準位寬的key值存在浪費TCAM表項空間的問題。

發明內容

本發明實施例提供一種數據存儲方法、數據查找方法及裝置，用以解決TCAM中非標準位寬的關鍵字key值浪費空間的缺陷。

一方面，本發明實施例提供一種數據存儲方法，包括：

獲取待存儲到TCAM的關鍵字，并獲取所述關鍵字的位寬；

從TCAM的所有標準位寬中，選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬；

若所述第一標準位寬大于等于所述關鍵字的位寬，將所述關鍵字存儲到TCAM中存儲位寬等于所述第一標準位寬的空間中，獲取所述關鍵字的存儲地址，并將所述關鍵字的存儲地址作為所述關鍵字在TCAM中的索引值；

若所述第一標準位寬小于所述關鍵字的位寬，將所述關鍵字切割成兩個關鍵字，分別為第一關鍵字和第二關鍵字；將所述第一關鍵字存儲到TCAM中存儲位寬等于所述第一標準位寬的空間中，獲取所述第一關鍵字的存儲地址作為所述第一關鍵字在TCAM中的索引值，所述第一標準位寬等于所述第一關鍵字的位寬；將所述第二關鍵字存儲到TCAM中存儲位寬等于第二標準位寬的空間中，獲取所述第一關鍵字的存儲地址作為所述第二關鍵字在TCAM中的索引值，所述第二標準位寬大于等于所述第二關鍵字的位寬且與所述第二關鍵字的位寬的差值最小；通過將所述第一關鍵字在TCAM中的索引值和所述第二關鍵字在TCAM的中索引值進行組合變換獲得所述關鍵字在TCAM中的索引值，其中，所述組合變換使得所述關鍵字在TCAM中的索引值與其它關鍵字在TCAM的索引值不產生沖突；

將所述關鍵字對應的關聯數據存儲于存儲器中，所述關聯數據在所述存儲器中的存儲地址與所述關鍵字在TCAM的索引值對應，所述關聯數據中包含有所述關鍵字的報文的處理信息。

另一方面，本發明實施例提供一種數據查找方法，包括：

從報文中提取出待查找的關鍵字，并獲取所述關鍵字的位寬；

從TCAM的所有標準位寬中選擇與所述關鍵字的位寬的差值最小的標準位寬為第一標準位寬；

若所述第一標準位寬大于等于所述關鍵字的位寬，在TCAM中位寬等于第一標準位寬的空間中查找所述關鍵字，獲取所述關鍵字的存儲地址并將所述關鍵字的存儲地址作為所述關鍵字在TCAM中的索引值；