千萬(wàn)別！

非常多人這樣說(shuō)，也包括我。

Linux內(nèi)核早就把HASH路由表去掉了。如今就僅僅剩下TRIE了，只是我還是希望就這兩種數(shù)據(jù)結(jié)構(gòu)展開(kāi)一些形而上的討論。

1.hash和trie/radix

hash和tire事實(shí)上是能夠統(tǒng)一在一起的。具有同樣hash值的多個(gè)項(xiàng)具有一個(gè)共同的特征，這個(gè)特征怎么提取呢？無(wú)疑這就是hash函數(shù)的工作。而trie樹(shù)(或者radix樹(shù)，管它呢)的一棵子樹(shù)也有共同的特征，這個(gè)特征怎么提取呢？無(wú)疑這就是該子樹(shù)根節(jié)點(diǎn)的父節(jié)點(diǎn)指示的某些bits在這棵子樹(shù)的每個(gè)節(jié)點(diǎn)都具有同樣的值。

?????? 實(shí)際上，trie樹(shù)就是hash的一種特殊形式，其hash函數(shù)為：取某些bits

trie_hash(value, level) {return value & level.bits; }
那么。這么看來(lái)，子樹(shù)的全部節(jié)點(diǎn)都應(yīng)處在一個(gè)“沖突鏈表”里面了...trie樹(shù)的做法就是“再次hash”，hash函數(shù)隨之改變。變成取level.bits更低的某些bits了。如此看來(lái)。hash路由表解決海量路由項(xiàng)情況下沖突鏈表變長(zhǎng)的方案就是再次hash了，hash函數(shù)變成什么呢？我們后面再談。

2.TCAM的hash

TCAM在非常多地方被用到，它用來(lái)依據(jù)內(nèi)容查索引，常被用于路由查詢。CPU Cache查詢等，以CPU Cache為例。輸入TCAM的內(nèi)容就是一個(gè)內(nèi)存地址，而輸出的結(jié)果是一個(gè)索引。cache匹配的過(guò)程就是取到索引指示的cache line，然后比較輸入內(nèi)容(地址)和該cache line指示的地址是否一致。一致就是命中。
?????? 那么TCAM中最核心的過(guò)程就是依據(jù)地址得到索引的過(guò)程，一般的做法就是hash，由于硬連線實(shí)現(xiàn)，hash函數(shù)絕對(duì)不能有太多的計(jì)算。因此一般的做法就是“取地址某些bits”，比方取4到7位一共4位，將一個(gè)32位(32位系統(tǒng)，物理地址索引cache為例為例)的慢速物理內(nèi)存地址映射到4位高速cache索引。形成一個(gè)金字塔存儲(chǔ)結(jié)構(gòu)。32位到4位的映射，丟失了的28位會(huì)形成非常大可能性的沖突，而這個(gè)就是時(shí)間局部性和空間局部性來(lái)盡力彌補(bǔ)了，了解列維飛行的應(yīng)該知道局部性的偉大含義，它構(gòu)建了我們整個(gè)人類文明。
?????? 最簡(jiǎn)單的hash函數(shù)就是取模，實(shí)際上也是“取某些bits”，它更加特殊，它是“取最低N bits"。

3.hash和trie樹(shù)的統(tǒng)一

trie樹(shù)實(shí)際上是從高位到低位逐步hash的過(guò)程構(gòu)建的，其hash函數(shù)就是”取某些bits“。

4.查字典的樣例-查英文和查漢字

我們小學(xué)的時(shí)候查字典一般分為音序查法和部首查法，它就形象能體現(xiàn)hash和trie的不同。

為了簡(jiǎn)便，我以英文單詞查法和漢字部首查法為例。
?????? 英文單詞是嚴(yán)格一維度順序排列的，且僅有26個(gè)字母組成。因此它能夠依照trie樹(shù)的方式查詢，比方what。who，where，前兩個(gè)字符都是wh，因此說(shuō)它們具有這么一個(gè)共同特征。假設(shè)將取這個(gè)共同特征作為hash函數(shù)，那么在aaa。cc，sahidad。fwfwew，what，qwert，azsx，who。eee，ooo，where中查詢who，what。who，where將形成沖突鏈表，可是一步運(yùn)算大大降低了匹配的數(shù)量，從11個(gè)減為3個(gè)，然后再進(jìn)一步hash，依照字母順序可知at，wre。o這個(gè)順序，直接取第三個(gè)孩子節(jié)點(diǎn)。因此英語(yǔ)詞典的查詢方式非常簡(jiǎn)便。就是一個(gè)不斷hash定位的過(guò)程。hash函數(shù)就是”取某些連續(xù)字符“。
?????? 我們?cè)倏纯礉h字部首查詢法。它是一個(gè)典型的計(jì)算型hash函數(shù)的不斷hash的過(guò)程。比方在楊。林，棵，馬，牛，豬，過(guò)。皮這幾個(gè)字中查”林“字，由于漢字不是一維結(jié)構(gòu)而是二維結(jié)構(gòu)。它的構(gòu)成是筆畫(huà)。不是排序的，因此”取某些字符“的方式全然失效(從哪個(gè)方向開(kāi)始取？...怎么算一個(gè)字符？...)，因此就須要又一次構(gòu)造hash函數(shù)了。長(zhǎng)期的歷史形成的漢子具有某種象形的意義。通過(guò)觀察。我們發(fā)現(xiàn)”木“字旁是一個(gè)特征，這個(gè)計(jì)算過(guò)程，也就是hash函數(shù)運(yùn)行過(guò)程是我們的大腦來(lái)完畢的。假設(shè)說(shuō)”取某些字符“更加適用于硬件實(shí)現(xiàn)，那么發(fā)現(xiàn)偏旁部首則更加適合軟件實(shí)現(xiàn)，從中我們也能夠分析出中國(guó)人和西方人的思維之差別。繼續(xù)往下說(shuō)。發(fā)現(xiàn)”木字旁“之后。楊。林，棵形成了沖突鏈表，但大大降低了匹配候選字的數(shù)量。不想遍歷的話。須要再次hash，新華字典設(shè)計(jì)了筆畫(huà)數(shù)這個(gè)再hash函數(shù)，”林“字除了偏旁之外還剩下4筆畫(huà)。于是定位到了”林“。假設(shè)還沖突，那就須要遍歷了，由于商務(wù)印書(shū)館可能想不出什么hash函數(shù)了(我不知道這樣的漢字部首查字法是誰(shuí)發(fā)明的，就當(dāng)是出版社的杰作吧...)。

反過(guò)來(lái)看英文查法。總是能夠終于確定性定位，由于它的不斷hash的hash函數(shù)是”取連續(xù)字符“，加之單詞長(zhǎng)度有限且一維排列順序遞進(jìn)。總是能夠到最后一個(gè)字符的。

?????? 看出差別了嗎？看出trie樹(shù)查詢和hash查詢的差別了嗎？

5.hash路由表和trie路由表

對(duì)于hash路由表查詢而言，最長(zhǎng)前綴匹配邏輯并沒(méi)有包括在hash過(guò)程中，它來(lái)自于一種冒險(xiǎn)行為，前提是對(duì)hash函數(shù)的足夠自信。hash路由表查找直接從32位前綴hash表開(kāi)始。逐步回歸到0位前綴hash表，期望在這個(gè)過(guò)程中能高速得到第一個(gè)結(jié)果，這第一個(gè)匹配結(jié)果就是終于結(jié)果。
?????? 對(duì)于trie路由表查詢而言，最長(zhǎng)前綴匹配邏輯包括在不斷再hash的邏輯中。它匹配的是最后一個(gè)結(jié)果而不是第一個(gè)，由于”順序取某些bits“不斷hash的過(guò)程。最后匹配到的顯然是最精確的。這是和hash路由查詢的本質(zhì)差別。trie查詢沒(méi)有冒險(xiǎn)行為，它不須要冒遍歷超長(zhǎng)沖突鏈表之險(xiǎn)，由于老老實(shí)實(shí)地運(yùn)行順序取bits這個(gè)過(guò)程總能將查詢過(guò)程引到目的地。

6.海量路由項(xiàng)的情況

Linux之所以用了那么久hash路由表組織，是由于它足夠了。

由于在大部分時(shí)間。路由表項(xiàng)數(shù)量是不多的。即便是遍歷也不會(huì)有太大的開(kāi)銷，而hash的計(jì)算會(huì)大大降低遍歷的開(kāi)銷，所謂的冒險(xiǎn)最壞情況就是遍歷整個(gè)路由項(xiàng)，這不是為題。可是一旦遍歷整個(gè)路由表的全部路由項(xiàng)真的成了一個(gè)大風(fēng)險(xiǎn)的時(shí)候。或者說(shuō)即使遍歷一半也吃不消的時(shí)候，用hash就不明智了。

這和獅子追羚羊時(shí)的博弈相似。一個(gè)風(fēng)險(xiǎn)是一頓飯，一個(gè)風(fēng)險(xiǎn)是一條命，這是嚴(yán)格不正確稱的。所以總是看到羚羊勝利(還真不能把這個(gè)當(dāng)零和游戲，由于獅子有時(shí)真的不在乎)。
?????? 如今的問(wèn)題是，怎樣使用hash路由表并降低風(fēng)險(xiǎn)。我們先看一下Linux自己的hash函數(shù)：

static inline u32 fn_hash(__be32 key, struct fn_zone *fz) {u32 h = ntohl(key)>>(32 - fz->fz_order);h ^= (h>>20);h ^= (h>>10);h ^= (h>>5);h &= FZ_HASHMASK(fz);return h; }
可見(jiàn)它將輸入的非0項(xiàng)散列得足夠開(kāi)，可是hash的本質(zhì)就是大空間往小空間映射。沖突在所難免。

有人提出(比方我)在海量路由表項(xiàng)時(shí)將長(zhǎng)沖突鏈表組織成trie樹(shù)的形式，可是這有意義嗎？假設(shè)是一個(gè)完整的trie路由表。最長(zhǎng)32步(考慮壓縮和回溯)就能找到結(jié)果。假設(shè)採(cǎi)用hash+trie的方式，每一步的最壞結(jié)果都是32步，一共進(jìn)行32步...這樣做沒(méi)有意義。
?????? 海量路由表項(xiàng)時(shí)，hash小空間是嚴(yán)格有范圍的。能夠覺(jué)得它是固定的。平均情況非常easy通過(guò)地址空間和hash空間求得，最壞情況則是全然遍歷。平均情況假設(shè)都不能接受，難道值得為最好情況去冒險(xiǎn)嗎？因此，千萬(wàn)別用hash表存儲(chǔ)海量路由表項(xiàng)。
?????? 可是。還沒(méi)完

7.局部性利用以及DoS

32位系統(tǒng)，CPU Cache相比內(nèi)存而言非常小，怎么能夠帶來(lái)如此大的優(yōu)化？全部映射到同一個(gè)cache line的地址都是沖突的啊...這是由于CPU Cache利用了程序的時(shí)間/空間局部性，而對(duì)于路由而言。則沒(méi)有空間局部性。時(shí)間局部性能夠用于路由cache，然而用于路由表本身則有難度。路由表和CPU Cache的差別在于它是全然的。不存在被替換和老化的問(wèn)題。因此能夠把好的hash函數(shù)用于單獨(dú)的路由cache，而路由表僅僅用于路由cache不命中的情況下去匹配。

?????? 理想情況分析完了，剩下的僅僅是悲哀了。
?????? 網(wǎng)絡(luò)訪問(wèn)的時(shí)間局部性真的能夠利用嗎？盡管一個(gè)5元組的數(shù)據(jù)流通常會(huì)隨著時(shí)間持續(xù)經(jīng)過(guò)路由器，可是假設(shè)hash沖突的還有一個(gè)數(shù)據(jù)流也經(jīng)過(guò)的話，就會(huì)造成cache抖動(dòng)，在CPU Cache看來(lái)。這個(gè)問(wèn)題能夠通過(guò)控制task切換或者添加cache line唯一鍵值來(lái)解決，可是對(duì)于網(wǎng)絡(luò)訪問(wèn)，你沒(méi)法阻止不論什么一個(gè)數(shù)據(jù)包的到來(lái)，僅僅要到來(lái)就要查詢路由表，就有可能導(dǎo)致cache抖動(dòng)。更嚴(yán)重的。路由cache非常easy受到精心構(gòu)造的數(shù)據(jù)包的攻擊造成不可用，頻繁的替換或者無(wú)限的加長(zhǎng)鏈表。平添了查詢開(kāi)銷。
?????? 因此設(shè)計(jì)一個(gè)全然的轉(zhuǎn)發(fā)表而不是利用路由cache更加能提升轉(zhuǎn)發(fā)效率。

這又一次為我的DxR Pro結(jié)構(gòu)作了一個(gè)廣告。

轉(zhuǎn)載于:https://www.cnblogs.com/mfrbuaa/p/5248393.html

總結(jié)

以上是生活随笔為你收集整理的海量路由表能够使用HASH表存储吗-HASH查找和TRIE树查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。