CAM和TCAM是什么？

提到存儲介質(zhì)，大家應(yīng)該很容易想到RAM。相比于RAM，CAM可能就顯得有些陌生了。實際上，TCAM對于交換芯片非常重要。比如了解OpenFlow的人都知道流表，最典型的流表都是用TCAM來做的。TCAM，主要用于快速查找ACL、路由等表項。

它到底是個什么東西，起到什么樣的作用呢？接下來我們慢慢聊。

TIP：

OpenFlow，一種網(wǎng)絡(luò)通信協(xié)議，屬于數(shù)據(jù)鏈路層，能夠控制網(wǎng)上交換器或路由器的轉(zhuǎn)發(fā)平面（forwarding plane），借此改變網(wǎng)絡(luò)數(shù)據(jù)包所走的網(wǎng)絡(luò)路徑。

什么是CAM？

CAM是Content Addressable Memory的縮寫，即“內(nèi)容尋址存儲器”的意思，它是在傳統(tǒng)的存儲技術(shù)的基礎(chǔ)上實現(xiàn)的聯(lián)想記憶存儲器，關(guān)于CAM的基本操作有三種：

1)寫操作：輸入地址和數(shù)據(jù)，將數(shù)據(jù)寫到指定的地址上，寫入速度與RAM相同；

2)讀操作：輸入地址，返回該地址上的數(shù)據(jù)，讀取速度與RAM相同；

3)查找操作：輸入待查數(shù)據(jù)，返回該數(shù)據(jù)被存儲的地址。這也是CAM的最主要用途，它能夠從巨大的數(shù)據(jù)庫中進(jìn)行快速查找，并且返回最佳的匹配地址，最快查找速度能達(dá)到每秒一億次以上。

CAM和RAM有何區(qū)別？

相對于CAM，我們可能更加熟悉RAM。SRAM、DRAM大家可能或多或少有所接觸。

如果想了解更多關(guān)于存儲相關(guān)的內(nèi)容，可以查看我們的往期文章：

科普：什么是OTP？什么是MTP？

科普：RAM和ROM有什么區(qū)別？

言歸正傳，在本文中，我們不再花費太多筆墨去闡釋RAM相關(guān)內(nèi)容。我們將重點放在CAM上。

那么，RAM與CAM，有什么區(qū)別呢？舉個例子。

一個表（table）被放在RAM中以便進(jìn)行高速操作，提供一個地址并從表中獲取與該地址相匹配的數(shù)據(jù)。然而，使用RAM進(jìn)行查找可能需要多個周期來完成，它的速度不是很理想。

因此，CAM應(yīng)運而生。在原理上，它反其道而行之，數(shù)據(jù)被當(dāng)作搜索其所在地址的鑰匙。根據(jù)CAM設(shè)計的性質(zhì)，搜索是并行的，這意味著查找可以在一個周期內(nèi)完成。這使得CAM更適合做數(shù)據(jù)表的查找，它的速度更快。

與具有簡單存儲單元的靜態(tài) RAM (SRAM) 不同，全并行 CAM 中的每個單獨的存儲位都必須具有與自身相關(guān)的比對電路，以檢測存儲位和輸入位之間的匹配情況。此外，在使用 CAM 時，必須將數(shù)據(jù)字中每個單元的匹配輸出組合起來，才能產(chǎn)生完整的數(shù)據(jù)字匹配信號。

因而在搜索層面，CAM具有性能優(yōu)勢，而代價則是需要更大的面積和更高的功耗。

CAM的分類

我們通常使用兩種不同類型的CAM，分別為BCAM（Binary CAM）和TCAM（Ternary CAM）。

BCAM，顧名思義，是指數(shù)據(jù)為二進(jìn)制狀態(tài)，即0或1，數(shù)據(jù)搜索必須完全匹配。它適用于具有唯一條目的數(shù)據(jù)查詢，如MAC地址查詢。

而TCAM是Ternary Content Addressable Memory的縮寫，即“三態(tài)內(nèi)容尋址存儲器”的意思，它是從CAM的基礎(chǔ)上發(fā)展而來的。

這個“三態(tài)”，就非常有意思了。

一般的CAM存儲器中每個bit位的狀態(tài)只有兩個，“0”或“1”，而TCAM中每個bit位有三種狀態(tài)，除掉“0”和“1”外，還有一個“don’t care”狀態(tài)，也可以稱作“wildcard”，也可以表示為“X”，從中文理解，就是忽略的意思。所以稱為“三態(tài)”，它是通過掩碼來實現(xiàn)的。

正是TCAM的這個第三種狀態(tài)特征使其既能進(jìn)行精確匹配查找，又能進(jìn)行模糊匹配查找，而BCAM沒有第三種狀態(tài)，所以只能進(jìn)行精確匹配查找。

TCAM的實現(xiàn)除了有ASIC芯片外，還可以在FPGA上用IP核實現(xiàn)。

當(dāng)涉及到路由時，“don’t care”的概念在很多方面都是有用的。

例如，當(dāng)我們寫下1.1.1.0/24時，它描述了從1.1.1.0到1.1.1.255的IP地址范圍。數(shù)字24表示IP地址的前24位必須被匹配，而后8位是什么并不重要。

TIP：

路由（routing）是指分組從源到目的地時，決定端到端路徑的網(wǎng)絡(luò)范圍的進(jìn)程。路由工作在OSI參考模型第三層——網(wǎng)絡(luò)層的數(shù)據(jù)包轉(zhuǎn)發(fā)設(shè)備。路由器通過轉(zhuǎn)發(fā)數(shù)據(jù)包來實現(xiàn)網(wǎng)絡(luò)互連。

查找方式的對比：

基于SRAM的查找（傳統(tǒng)查找方式）

1、線性查找

2、二叉樹查找

3、HASH查找

基于TCAM的查找

基于硬件的實現(xiàn)，整個表空間Database在同一時刻被查詢

TCAM之所以能做到一個bit表示三個值，原因是它的一條entry其實在物理上由兩條entry組成，一條存放data，另外一條存放相應(yīng)的mask。由此可以實現(xiàn)0/1/X的表示。有了TCAM,就可以支持各種LOOKUP KEY的任何組合查找，任意地MASK掉任何不關(guān)心的字段，只有TCAM可以做這樣的事情，HASH做不到。

TCAM的查找特點

如果有多條TCAM ENTRY都能匹配上，TCAM優(yōu)先選擇INDEX最小的那一條。TCAM的查找效率與深度無關(guān)，也就是說，無論表項多大，查找速度是一樣的，這跟TCAM的硬件實現(xiàn)方式有關(guān)。命中其中一條之后，就返回index，然后根據(jù)這個index去它對應(yīng)的RAM里面查找進(jìn)一步的關(guān)聯(lián)數(shù)據(jù)。

TCAM在高端路由器中的應(yīng)用及查找過程

為什么TCAM都不會太大

TCAM可以內(nèi)置在芯片里面，也可以外掛在芯片之外，芯片通過接口去訪問。但是內(nèi)置TCAM非常占芯片面積,如果芯片內(nèi)部放了太大的TCAM會導(dǎo)致芯片成本和功耗直線上升。所以一般芯片都不會內(nèi)置太大TCAM。這就是為什么基于TCAM的流表做不大的原因。

外掛TCAM的成本和功耗一樣很大，甚至比ASIC芯片本身都貴，而且如果一個報文要訪問外部TCAM多次的話，受限于TCAM接口速率，會導(dǎo)致無法線速。所以一般交換機(jī)也都不會使用外掛TCAM。

TCAM的優(yōu)勢

1、單周期查找；

2、平均查找速度是基于SRAM算法查找的6倍；

3、最好情況下，查找速度提高128倍。

總而言之，TCAM實現(xiàn)了通用性和高速度。TCAM的最大優(yōu)勢，就是速度。

TCAM的缺點

TCAM具有速度快、實現(xiàn)簡單的優(yōu)點，但是它也有三個不足之處：

1、與一般的隨機(jī)存儲器RAM 相比，單位比特的TCAM 更為昂貴，而且存儲芯片的容量相對要小一些；

2、由于TCAM 使用的是并行匹配比較方式，所以TCAM 芯片的功耗較大。查找過程所有關(guān)鍵字表項都進(jìn)行了比較，但是實際能夠匹配上的關(guān)鍵字只是幾項，因此大部分的比較操作都被浪費了；

3、 TCAM 需要保證前綴較長的關(guān)鍵字保存在前綴較短的關(guān)鍵字之前，這種關(guān)鍵字之間的順序關(guān)系使得TCAM的關(guān)鍵字更新工作變得相對復(fù)雜了。當(dāng)加入一條新的表項時，為了能夠仍然保持關(guān)鍵字間的順序關(guān)系，就需要移動一些前綴長度比新表項要長的一些表項，因此TCAM 的更新操作較為復(fù)雜。

總結(jié)下來就是：成本高、功耗大、路由更新復(fù)雜。

關(guān)于TCAM器件的應(yīng)用

TCAM器件在通信領(lǐng)域種有非常廣泛的應(yīng)用，主要有：

1、ATM Switching設(shè)備中的VCI/VPI轉(zhuǎn)發(fā)和ATM-to-MPLS or ATM-to-TCP-Flow地址映射表項的存儲和查找；

2、Ethernet Switching設(shè)備中的二層MAC地址、ARP/RARP解析和三層IP路由表項的存儲和查找；

3、Emerging Protocols and functions方面的MPLS label表項的存儲和查找；

4、Packet Classification業(yè)務(wù)中的Enforce security、Enforce departmental policies和QOS檢測表項的存儲和查找；

5、安全防護(hù)設(shè)備中的FIB/LBT、MFIB及ACL表項存儲和查找。

TCAM器件的硬件設(shè)計方式一般有三種：

關(guān)于ACL

訪問控制列表ACL（Access Control List）是由一條或多條規(guī)則組成的集合。所謂規(guī)則，是指描述報文匹配條件的判斷語句，這些條件可以是報文的源地址、目的地址、端口號等。

ACL本質(zhì)上是一種過濾器，規(guī)則是過濾器的濾芯。設(shè)備基于這些規(guī)則進(jìn)行報文匹配，可以過濾出特定的報文，并根據(jù)應(yīng)用ACL的業(yè)務(wù)模塊的處理策略來允許或阻止該報文通過。

訪問控制列表被廣泛地應(yīng)用于路由器和三層交換機(jī)，借助于訪問控制列表，可以有效地控制用戶對網(wǎng)絡(luò)的訪問，從而最大程度地保障網(wǎng)絡(luò)安全。

TIP：

報文(message)是網(wǎng)絡(luò)中交換與傳輸?shù)臄?shù)據(jù)單元，即站點一次性要發(fā)送的數(shù)據(jù)塊。報文包含了將要發(fā)送的完整的數(shù)據(jù)信息，其長短很不一致，長度不限且可變。

應(yīng)用場景

-匹配IP流量（可基于源，目的IP地址，協(xié)議類型，端口號等類型）

-在Traffic-fiter中被調(diào)用

-在NAT中被調(diào)用

-在路由策略調(diào)用

-在IPSec VPN中被調(diào)用

-在防火墻的策略部署中被調(diào)用

-在QoS中被調(diào)用

分類

目前遇到最多就是基本acl和高級acl，其他種類acl很少見。

ACL/路由表/Mac表跟TCAM的關(guān)系

普通交換機(jī)中的ACL功能必須使用TCAM，所以內(nèi)置TCAM省不掉。而對于路由，以前的芯片也都用TCAM來做（主機(jī)路由除外），所以路由表項也做不大。現(xiàn)在最新的商業(yè)芯片都已經(jīng)使用算法來支持路由了，這樣就可以使用RAM來做路由。至于Mac表，它的查找是根據(jù)Mac+Vlan進(jìn)行精確匹配，可以用Hash來做，所以跟路由一樣，都存放在RAM里面。

審核編輯 ：李倩