[發(fā)明專利]鍵值搜索方法、鍵值搜索裝置及芯片

有效

• 申請?zhí)枺?/td>: 201310334728.3
• 申請日: 2013-08-02
• 公開（公告）號: CN103399920B
• 公開（公告）日: 2017-04-26
• 發(fā)明（設(shè)計）人: 熊冰;張建杰
• 申請（專利權(quán)）人: 蘇州雄立科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京弘權(quán)知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11363
• 代理人: 陳蕾,許偉群

技術(shù)領(lǐng)域

本發(fā)明涉及計算機(jī)領(lǐng)域，尤其涉及鍵值搜索方法、鍵值搜索裝置及芯片。

背景技術(shù)

計算機(jī)對數(shù)據(jù)進(jìn)行處理的過程中，經(jīng)常需要根據(jù)數(shù)據(jù)中的某些關(guān)鍵信息來決定如何對該數(shù)據(jù)進(jìn)行處理，這些關(guān)鍵信息通常被稱為數(shù)據(jù)鍵值。例如，在網(wǎng)絡(luò)安全控制設(shè)備中，系統(tǒng)根據(jù)輸入數(shù)據(jù)包中某些關(guān)鍵字段的內(nèi)容，來對數(shù)據(jù)包進(jìn)行不同的分類、轉(zhuǎn)發(fā)、過濾等操作。由于數(shù)據(jù)鍵值的取值范圍較大，各種字段的組合種類較多，在實際應(yīng)用中，通常將這些數(shù)據(jù)鍵值及與之對應(yīng)的操作處理方式預(yù)先存儲起來，當(dāng)計算機(jī)接收到一個輸入數(shù)據(jù)時，首先從數(shù)據(jù)中取出數(shù)據(jù)鍵值，然后根據(jù)數(shù)據(jù)鍵值在預(yù)先存儲的內(nèi)容中進(jìn)行搜索，當(dāng)搜索到與數(shù)據(jù)鍵值內(nèi)容匹配的操作處理方式時，根據(jù)該操作處理方式對輸入數(shù)據(jù)進(jìn)行操作處理。

現(xiàn)有技術(shù)中通常使用三值內(nèi)容尋址鍵值存儲器（TCAM，TERNARY CONTENT ADDRESSABLE MEMORY)來進(jìn)行數(shù)據(jù)鍵值信息的存儲和搜索。在TCAM中，每一個位（BIT）電路用于存儲和查找一個數(shù)據(jù)鍵值，每一個位（BIT）電路包括了三個單元：數(shù)據(jù)單元（D，DATA），標(biāo)記單元（M，MASK）和比較單元（C，COMPARATOR)，使得每個BIT需要16個晶體管。在進(jìn)行搜索時，TCAM啟動所有存儲條目中的所有位（BIT）電路，一次完成全部搜索過程。

由于TCAM存儲單元的電路復(fù)雜，會導(dǎo)致數(shù)據(jù)鍵值存儲容量較大時，TCAM面積大，功耗大，電源噪聲大，使得現(xiàn)有數(shù)據(jù)鍵值信息的存儲鍵值搜索裝置不能滿足網(wǎng)絡(luò)設(shè)備的大容量、高速搜索的需求。

發(fā)明內(nèi)容

本發(fā)明實施例提供了鍵值搜索方法、鍵值搜索裝置及芯片，以解決現(xiàn)有數(shù)據(jù)鍵值信息的存儲鍵值搜索裝置不能滿足網(wǎng)絡(luò)設(shè)備的大容量、高速搜索的需求的問題。

第一方面，本發(fā)明實施例提供了一種鍵值搜索方法，該方法包括：

接收待搜索鍵值；采用與每一個鍵值存儲器對應(yīng)的預(yù)設(shè)哈希映射算法，將所述待搜索鍵值轉(zhuǎn)換為獲取地址空間；根據(jù)所述獲取地址空間，從每一個鍵值存儲器中獲取一個數(shù)據(jù)鍵值作為備選鍵值；選取與待搜索鍵值匹配的一個備選鍵值作為確定鍵值。

結(jié)合第一方面，在第一種可能的實現(xiàn)方式中，所述采用與每一個鍵值存儲器對應(yīng)的預(yù)設(shè)哈希映射算法，將所述待搜索鍵值轉(zhuǎn)換為獲取地址空間，具體為：

采用與每一個鍵值存儲器唯一對應(yīng)的哈希映射算法，將所述待搜索鍵值轉(zhuǎn)換為每一個鍵值存儲器的獲取地址空間。

結(jié)合第一方面及第一方面第一種可能的實現(xiàn)方式，在第二種可能的實現(xiàn)方式中，在所述接收待搜索鍵值之前，還包括：

接收待存儲鍵值；確定所述待存儲鍵值所屬的鍵值保存存儲器，所述鍵值保存存儲器為所述鍵值存儲器其中之一；使用與所述鍵值保存存儲器對應(yīng)的哈希映射算法，將待儲存鍵值轉(zhuǎn)換為保存地址空間；將所述待存儲鍵值保存至所述鍵值保存存儲器上所述保存地址空間；所述接收待搜索鍵值，具體為：在將所述待存儲鍵值保存至與所述分組對應(yīng)的鍵值存儲器的所述保存地址空間之后，接收待搜索鍵值。

結(jié)合第一方面、第一方面第一種可能的實現(xiàn)方式及第一方面第二種可能的實現(xiàn)方式，在第三種可能的實現(xiàn)方式中，所述鍵值存儲器為靜態(tài)隨機(jī)存儲器（SRAM，STATIC RANDOM ACCESS MEMORY）或動態(tài)隨機(jī)存取存儲器（DRAM，DYNAMIC RANDOM ACCESS MEMORY）。

第二方面，本發(fā)明實施例還提供了一種鍵值搜索裝置，所述裝置包括：

接收單元，用于接收待搜索鍵值；轉(zhuǎn)換單元，用于采用與每一個鍵值存儲器對應(yīng)的預(yù)設(shè)哈希映射算法，將所述接收單元接收到的所述待搜索鍵值轉(zhuǎn)換為獲取地址空間；獲取單元，用于根據(jù)所述轉(zhuǎn)換單元獲取到的所述獲取地址空間，從每一個鍵值存儲器中獲取一個數(shù)據(jù)鍵值作為備選鍵值；確定單元，用于選取與所述獲取單元獲取到的所述待搜索鍵值匹配的一個備選鍵值作為確定鍵值。

結(jié)合第二方面，在第一種可能的實現(xiàn)方式中，所述轉(zhuǎn)換單元，具體用于采用與每一個鍵值存儲器唯一對應(yīng)的哈希映射算法，將所述接收單元接收到的所述待搜索鍵值轉(zhuǎn)換為每一個鍵值存儲器的獲取地址空間。

結(jié)合第二方面及第二方面第一種可能的實現(xiàn)方式，在第二種可能的實現(xiàn)方式中，所述鍵值搜索裝置還包括：