第三章實(shí)現(xiàn)原則

1、標(biāo)題頁(yè)本章介紹作者歸納的 15 條實(shí)現(xiàn)原則。這些實(shí)現(xiàn)原則是從比較成功的協(xié)議實(shí) 現(xiàn)中歸納出來(lái)的。 其實(shí)許多實(shí)現(xiàn)者已經(jīng)有意無(wú)意地使用了這些原則， 本章只是更 清楚地將它們表達(dá)出來(lái)，以使實(shí)現(xiàn)者可以更加主動(dòng)地去運(yùn)用它們。3.1 運(yùn)用實(shí)現(xiàn)原則的例子：更新 TCAM下面用一個(gè)例子來(lái)說(shuō)明為什么要使用原則。使用 TCAM 進(jìn)行 IP 地址查找圖 3.4是 TCAM 用于 IP 地址查找的例子。 IP 地址前綴是長(zhǎng)度為 32比特的三 態(tài)字符串，通配符都在字符串的尾部。我們稍微改變一下表示法，使得* 表示任意數(shù)量的通配符。按照 TCAM 的工作原理以及最長(zhǎng)前綴匹配的要求， TCAM 中的地址前綴必 須按照前綴長(zhǎng)度

2、從大到小的順序排列。路由表是動(dòng)態(tài)變化的，如何在 TCAM 中添加或刪除一條地址前綴，與此同 時(shí)仍然保持前綴長(zhǎng)度從大到小的排列順序？假定在圖3.4的TCAM中需要添加一條新的前綴11*。假定TCAM是向上擴(kuò) 展空間的，最樸素的方法是在長(zhǎng)度為 2的前綴表項(xiàng)中插入前綴 11*，比如插在前 綴 0*的前面，為此，需將前綴 10*至前綴 010001*整體向上移動(dòng)一個(gè)位置。對(duì)于 包含大量路由表項(xiàng)的路由器來(lái)說(shuō)，這種更新的速度太慢了。有沒(méi)有快一點(diǎn)的方法呢？我們?cè)賮?lái)看一下圖 3.4的前綴排列方法：長(zhǎng)度相同 的前綴排列在一起， 按照從長(zhǎng)到短的順序排列， 相同長(zhǎng)度的前綴還按照大小進(jìn)行 了排序。事實(shí)上，相同長(zhǎng)度前綴

3、的順序?qū)τ?TCAM 執(zhí)行最長(zhǎng)前綴匹配不是必須的， 因?yàn)橐粋€(gè) IP 地址不可能同時(shí)匹配兩個(gè)相同長(zhǎng)度的前綴。我們只需要按照前綴長(zhǎng) 度進(jìn)行排序，并不需要相同長(zhǎng)度前綴之間排序， 因此這是一個(gè)可以利用的自由度。理解并利用自由度（ 1 ）利用該自由度，我們可將 11*插入到 00*和 111*之間。當(dāng)然，如果為此將 111* 及以上前綴向上移動(dòng)一個(gè)位置， 則不會(huì)有多大優(yōu)化的效果。 我們的想法是將 111* 移出，將 11*插入 1 1 1 *的位置，然后再為 111*尋找一個(gè)插入位置。 盡管這個(gè)問(wèn)題 和原來(lái)的差不多，仍然要向 TCAM 中插入一條前綴，但是問(wèn)題的規(guī)?？s小了一 點(diǎn)。理解并利用自由度（ 2）

4、我們可以將這個(gè)方法推廣：。顯然我們可以采用遞歸的思想來(lái)設(shè)計(jì)一個(gè) 算法。使用算法技術(shù) 采用遞歸實(shí)現(xiàn)的時(shí)候展開(kāi)遞歸：。如果每一種長(zhǎng)度的前綴都有（即最壞情況），需要（32-i）次訪(fǎng)存。對(duì)于較小 的i，訪(fǎng)存次數(shù)接近32。這個(gè)算法已經(jīng)比樸素的算法好了很多，但是不是最好了 呢？還能減小最壞情況下的訪(fǎng)存次數(shù)嗎？（想一想）我們?cè)賮?lái)看這張圖，這張圖假設(shè)空閑空間在 TCAM 的頂部，實(shí)際上空閑空 間可以放在 TCAM 的任何地方，因此空閑空間的位置也是一個(gè)設(shè)計(jì)自由度。進(jìn)一步利用自由度利用這個(gè)自由度，可以將空閑空間放在中間，比如放在長(zhǎng)度為 16 的前綴項(xiàng) 后面，這時(shí)最壞情況下的訪(fǎng)存次數(shù)可以減少一半。當(dāng)然，空閑空間的

5、數(shù)量也可以是一個(gè)自由度，可以進(jìn)一步減少最壞情況下的 訪(fǎng)存次數(shù)。除了空閑空間的位置及數(shù)量之外，還有沒(méi)有可以利用的自由度了呢？提示： 長(zhǎng)的前綴是否一定要出現(xiàn)在短的前綴之前？比如，010*能否放在 111001*之前？完全可以，因?yàn)椴豢赡苡幸粋€(gè)地址會(huì)同時(shí)匹配這兩項(xiàng)。一個(gè)更復(fù)雜的自由度是，“如果i>j，那么長(zhǎng)度為i的前綴必須出現(xiàn)在長(zhǎng)度為 j 的前綴之前”，這是一個(gè)充分條件，但不是必要的。一個(gè)不那么嚴(yán)格的要求是，“如果兩個(gè)前綴P和Q可能匹配同一個(gè)地址，且 P比Q長(zhǎng)，那么P必須出現(xiàn)在 Q 之前”。這樣修改規(guī)范后，可以進(jìn)一步減少最壞情況下的訪(fǎng)存次數(shù)。缺點(diǎn)是提 高了復(fù)雜度。盡管以這么復(fù)雜的方法來(lái)減少訪(fǎng)存

6、次數(shù)有點(diǎn)不劃算， 但它指出了一個(gè)重要的 原則，即放寬要求。 我們經(jīng)常將一個(gè)大的問(wèn)題劃分為較小的子問(wèn)題， 然后將子問(wèn) 題及相關(guān)的規(guī)范交由相關(guān)人員去解決。比如， TCAM 的硬件設(shè)計(jì)人員可能將更 新問(wèn)題交給寫(xiě)微代碼的人去完成， 要求將長(zhǎng)的前綴放在短前綴的前面。 但是這個(gè) 規(guī)范可能不是解決原始問(wèn)題的唯一方法，改變規(guī)范（ P3 放寬要求）可能產(chǎn)生更 有效的解決方案。 當(dāng)然，這需要有具有好奇心和自信的設(shè)計(jì)人員， 他理解整個(gè)大 問(wèn)題，并且足夠勇敢來(lái)提出危險(xiǎn)的問(wèn)題。這個(gè)例子其實(shí)是告訴我們，要去尋找和利用自由度來(lái)優(yōu)化實(shí)現(xiàn)。3.2 算法 vs 算法學(xué)如果認(rèn)為這個(gè)例子基本上是算法層面上的，不要求系統(tǒng)思維，那么下面

7、再舉 一個(gè)例子來(lái)說(shuō)明算法與算法學(xué)的差異。舉例：安全物證問(wèn)題假設(shè)一個(gè)入侵檢測(cè)系統(tǒng)通過(guò)統(tǒng)計(jì)流量來(lái)檢測(cè)異常節(jié)點(diǎn)， 比如在一個(gè)測(cè)量周期 內(nèi)發(fā)現(xiàn)一個(gè)節(jié)點(diǎn)向網(wǎng)絡(luò)中的不同機(jī)器發(fā)送了 10 萬(wàn)個(gè)包，就確定這個(gè)節(jié)點(diǎn)在進(jìn)行 端口掃描攻擊。 當(dāng)判定某個(gè)節(jié)點(diǎn)為攻擊源時(shí)， 要將該節(jié)點(diǎn)在測(cè)量周期內(nèi)發(fā)送的包 寫(xiě)入安全物證日志，供管理員進(jìn)一步分析。如何檢測(cè)攻擊不是我們要討論的，我們關(guān)心的是當(dāng)判定某個(gè)節(jié)點(diǎn)為攻擊源 時(shí)，如何得到它已經(jīng)發(fā)送過(guò)的那些包。解決方案為實(shí)現(xiàn)此目的，我們維護(hù)一個(gè)包隊(duì)列，當(dāng)一個(gè)數(shù)據(jù)包被轉(zhuǎn)發(fā)時(shí)，路由器將該 包放入隊(duì)頭。為限制隊(duì)列的長(zhǎng)度（路由器的內(nèi)存是有限的） ，當(dāng)隊(duì)列滿(mǎn)時(shí)，刪除 隊(duì)尾的包。該方案的主要困難是，當(dāng)

8、檢測(cè)到一個(gè)可疑流時(shí)，該流已經(jīng)有大量的數(shù)據(jù)包在 隊(duì)列中了， 并且和大量其它的包混在一起。 如何高效地從隊(duì)列中找到屬于可疑流 的所有包？最相素的方法是順序搜索隊(duì)列， 這顯然非常低效。 我們一般會(huì)采用什么方法， 快速找到流 F 的數(shù)據(jù)包呢？教科書(shū)上的算法教科書(shū)上的算法會(huì)構(gòu)造某個(gè)索引結(jié)構(gòu)來(lái)快速搜索流 ID 。比如，我們可以維護(hù) 一個(gè)流ID的哈希表。但是該算法仍有問(wèn)題。它需要額外的空間來(lái)維護(hù)哈希表和指針列表，而對(duì)于 高速實(shí)現(xiàn)來(lái)說(shuō)存儲(chǔ)空間是非常寶貴的。 它還增加了包處理的復(fù)雜度， 需要維護(hù)哈 希表。這個(gè)算法的問(wèn)題在哪里？就是我們潛意識(shí)里假設(shè)每一個(gè)流都有可能是可疑 流，因此，每一個(gè)包到來(lái)時(shí)都將其分到相應(yīng)的流

9、中。這樣，一旦某個(gè)流被認(rèn)定是 可疑流，立即就可以得到屬于該流的所有數(shù)據(jù)包。但事實(shí)上，可疑流只是少數(shù)， 這里面我們做了許多無(wú)用的處理， 將屬于正常流的包也都組織在哈希表中了。 比 如，10萬(wàn)個(gè)流中只有一個(gè)流是異常的，但我們將 10 萬(wàn)個(gè)流的包都做了歸類(lèi)，這 是顯而易見(jiàn)的浪費(fèi)。那么我們?cè)趺纯梢员苊庾鰺o(wú)用功呢？聯(lián)想到我們前面舉過(guò)的例子 （檢測(cè)異常URL）,我們可以采用推遲計(jì)算來(lái)解決這個(gè)問(wèn)題。系統(tǒng)的解決方案 基本思想：將判斷一個(gè)包是否屬于可疑流這件事情，拖到不得不做（發(fā)現(xiàn)可 疑流，且包將移出隊(duì)列）時(shí)再去做。什么時(shí)候不得不做？（ 1）發(fā)現(xiàn)了可疑流；（2）數(shù)據(jù)包將移出隊(duì)列令路由器轉(zhuǎn)發(fā)包時(shí)統(tǒng)計(jì)每個(gè)流（節(jié)點(diǎn)）

10、發(fā)送的包數(shù)。當(dāng)流 F 發(fā)送的包數(shù)超過(guò)一個(gè)閾值（如10萬(wàn)）時(shí)，將流F添加到可疑節(jié)點(diǎn)列表中。當(dāng)可疑節(jié)點(diǎn)列表非空 且隊(duì)列滿(mǎn)時(shí)， 每當(dāng)往隊(duì)列中添加一個(gè)包， 就從隊(duì)尾中移出一個(gè)包， 判斷該包是否 屬于F。若屬于F,將該包（或指針）拷貝到物證日志中；若否，將該包丟棄。該方案不需要維護(hù)哈希表和指針列表，節(jié)省了大量的存儲(chǔ)空間和計(jì)算開(kāi)銷(xiāo)。3.3 十五條設(shè)計(jì)原則第一章的例子（設(shè)計(jì)一個(gè)檢測(cè)異常 URL 的芯片）和前面這兩個(gè)例子給了我 們有關(guān)網(wǎng)絡(luò)算法學(xué)的一些初步體驗(yàn)， 下面介紹作者歸納的 15條原則，這 15條原 則我們會(huì)不斷地使用。這 15 條原則可以分為三類(lèi)：1）系統(tǒng)原則：第 1-5 條原則利用了系統(tǒng)思想，它將系

11、統(tǒng)看成是由子系統(tǒng)構(gòu) 成，而不是一個(gè)黑盒子。2）兼顧模塊化和效率：第 6-10 條原則允許保留復(fù)雜系統(tǒng)的模塊化，與此同 時(shí)給出提高性能的方法。3）加速：第 11-15 條原則提出了加速某個(gè)關(guān)鍵功能的技術(shù)（僅考慮該功能 本身）。每條原則會(huì)用一個(gè)例子來(lái)說(shuō)明，具體細(xì)節(jié)將在后續(xù)章節(jié)中討論。P1:避免常見(jiàn)情形中的明顯浪費(fèi)在一個(gè)系統(tǒng)中，在一些特殊的操作序列中可能存在資源浪費(fèi)。如果這些模式 經(jīng)常出現(xiàn)，就有必要去除這個(gè)浪費(fèi)，這樣可以從整體上降低系統(tǒng)的開(kāi)銷(xiāo)。編譯器的例子:消除重復(fù)的子表達(dá)式。經(jīng)典的網(wǎng)絡(luò)例子:操作系統(tǒng)和用戶(hù)空間之間多次數(shù)據(jù)包拷貝（第五章介紹） 。 這條原則看起來(lái)容易做起來(lái)難，最難的是如何發(fā)現(xiàn)明顯的浪

12、費(fèi)。這里，每一 步操作孤立地來(lái)看沒(méi)有浪費(fèi)， 是由于特殊的操作序列導(dǎo)致了浪費(fèi)。 顯然，暴露的 上下文越大，越可能發(fā)現(xiàn)產(chǎn)生浪費(fèi)的操作序列，因而這里需要系統(tǒng)思維。P3:放寬系統(tǒng)要求當(dāng)一個(gè)系統(tǒng)從上到下進(jìn)行設(shè)計(jì)時(shí)，先將功能在子系統(tǒng)間劃分。在確定了子系 統(tǒng)的需求和接口后， 再設(shè)計(jì)每一個(gè)子系統(tǒng)。 當(dāng)遇到實(shí)現(xiàn)困難時(shí)， 有些方面的要求 要改變。如圖 3.8所示，一個(gè)系統(tǒng)由兩個(gè)子系統(tǒng)組成，子系統(tǒng) 2 對(duì)子系統(tǒng) 1 的實(shí)現(xiàn)要 求稱(chēng)為規(guī)范S。如果子系統(tǒng)1實(shí)現(xiàn)困難，有時(shí)可以降低對(duì)其的實(shí)現(xiàn)要求，要求子 系統(tǒng) 1 遵循較為寬松的規(guī)范 W。在第 1 章的例子中，由于設(shè)計(jì)除法電路（ subsystem 1）比較復(fù)雜，改用移位

13、代替除法，也就是放寬了子系統(tǒng)1的實(shí)現(xiàn)規(guī)范（S->W）:子系統(tǒng)1只需實(shí)現(xiàn)移位 操作而不是任意的除法操作。其代價(jià)是子系統(tǒng) 2 必須遵循更強(qiáng)的特性（ P->Q）： 門(mén)限須用 2 的冪次表示，而不是一個(gè)任意的浮點(diǎn)數(shù)。P3a：犧牲確定性換時(shí)間超級(jí)節(jié)點(diǎn)的檢測(cè)：確定性的方法是統(tǒng)計(jì)以每一個(gè)節(jié)點(diǎn)作為源（或目的）的數(shù) 據(jù)包數(shù)量，這需要檢查每個(gè)包的源地址（或目的地址）進(jìn)行統(tǒng)計(jì)，這在高速網(wǎng)絡(luò) 中是做不到的。 隨機(jī)化方法是每隔一定數(shù)量的包統(tǒng)計(jì)一次， 雖然不能保證百分之 百正確，但在很大概率上是正確的。P3b:犧牲精度換時(shí)間圖像壓縮是一種很耗時(shí)的操作，對(duì)于實(shí)時(shí)視頻要求壓縮速度很快。離散余弦 變換可將信號(hào)能量集

14、中在少數(shù)幾個(gè)變換系數(shù)上， 然后只需對(duì)主要的變換系數(shù)進(jìn)行 量化編碼，達(dá)到快速壓縮的目的。但是圖像質(zhì)量（精度）會(huì)受到一些影響。P3c：在空間中移動(dòng)計(jì)算在空間中移動(dòng)計(jì)算是指將計(jì)算從一個(gè)子系統(tǒng)移動(dòng)到另一個(gè)子系統(tǒng) （注意和前 兩條原則的不同）。比如，數(shù)據(jù)包分片會(huì)影響路由器的吞吐量， IPv6 將分片的功 能從路由器移到了源節(jié)點(diǎn)。為此，源節(jié)點(diǎn)主動(dòng)探測(cè)端到端路徑上的 MTU ，確定 合適的分組大小， 路由器不再提供分片的功能。 這樣就簡(jiǎn)化了路由器的實(shí)現(xiàn)。 當(dāng) 然，這里的移動(dòng)已經(jīng)超出了一個(gè)網(wǎng)絡(luò)設(shè)備的限制， 是在整個(gè)網(wǎng)絡(luò)中的移動(dòng) （如果 將網(wǎng)絡(luò)看成一個(gè)系統(tǒng)，則路由器、主機(jī)就是子系統(tǒng)） 。P4:利用系統(tǒng)組件系統(tǒng)設(shè)

15、計(jì)采用黑盒視圖，就是將系統(tǒng)分解為若干子系統(tǒng)，然后獨(dú)立地設(shè)計(jì)每 一個(gè)子系統(tǒng)， 而不去關(guān)心其它子系統(tǒng)的內(nèi)部細(xì)節(jié)。 盡管這種自頂向下的方法具有 很好的模塊化， 但實(shí)際上，性能關(guān)鍵的組件在構(gòu)建時(shí)通常部分地采用 “自底向上” 的方法構(gòu)建。比如，要在一個(gè)硬件上設(shè)計(jì)算法，通常要讓算法適應(yīng)硬件的特性， 而不是讓硬件來(lái)適應(yīng)算法。P4b:用空間換速度一個(gè)顯而易見(jiàn)的技術(shù)是用較大的空間來(lái)減少計(jì)算時(shí)間， 比如將函數(shù)計(jì)算變?yōu)?查表。一個(gè)不那么顯而易見(jiàn)的技術(shù)是用較小的空間來(lái)提高速度。比如，把一個(gè)很大 的數(shù)據(jù)結(jié)構(gòu)壓縮到可以放入cache,或者大部分可以放入cache，可以極大地提升 系統(tǒng)速度。當(dāng)一個(gè)表的規(guī)模很大時(shí)，該技術(shù)特別

16、有效。有人可能會(huì)問(wèn)，空間和時(shí)間都節(jié)省了，怎么會(huì)有這樣的好事？事實(shí)上，計(jì)算 復(fù)雜度是增加的。比如，訪(fǎng)問(wèn)壓縮的數(shù)據(jù)結(jié)構(gòu)，其處理復(fù)雜度是提高的。但由于 現(xiàn)代處理器的計(jì)算速度比訪(fǎng)存速度快得多得多，在多核處理器上這個(gè)差距更大。 在這種情況下， 適當(dāng)增加計(jì)算復(fù)雜度并不會(huì)使處理器成為瓶頸， 卻因?yàn)樘嵘嗽L(fǎng) 存速度使得系統(tǒng)整體性能得到提升。 這是實(shí)踐中用得很多的一種優(yōu)化技術(shù)。 這也 啟示我們， 在優(yōu)化系統(tǒng)時(shí)一定要搞清楚瓶頸在什么地方， 如果計(jì)算不是瓶頸， 那么減少計(jì)算并不能提高系統(tǒng)速度如果 P4 原則使用過(guò)度，系統(tǒng)的模塊化將受到損害。為此，需要注意兩個(gè)問(wèn) 題：（1）如果我們利用其它系統(tǒng)特性只是為了提高性能，那

17、么對(duì)那些系統(tǒng)特性 的改變應(yīng)當(dāng)只影響性能，不影響正確性。（2）我們僅對(duì)確認(rèn)為是系統(tǒng)瓶頸的組件運(yùn)用該技術(shù)。 以上表明，對(duì)系統(tǒng)的優(yōu)化要有一定的度，不是越多越好。對(duì)系統(tǒng)修改越多， 可能產(chǎn)生的不可預(yù)知的相互作用就會(huì)增多， 可能會(huì)對(duì)系統(tǒng)的正確性產(chǎn)生影響， 所 以應(yīng)當(dāng)只對(duì)系統(tǒng)做最小的修改（不提倡大刀闊斧的改） 。P5:增加硬件提高性能當(dāng)所有的方法都不奏效時(shí)， 增加硬件（如使用更快的處理器、 存儲(chǔ)器、 總線(xiàn)、 鏈路等）可能是更簡(jiǎn)單和有效的方法。然而，硬件畢竟成本比較高，即使需要增 加硬件，我們也希望只增加最少的硬件。 這就要求充分挖掘軟件的潛力， 把軟件 的性能做得極至。隨著處理器的速度越來(lái)越高， 存儲(chǔ)容量越

18、來(lái)越大， 特別是多核處理器的出現(xiàn)， 我們發(fā)現(xiàn)軟件算法設(shè)計(jì)得好的話(huà)， 也是可以運(yùn)行得很快的。 因此，一種比較理想 的情況是，用軟件實(shí)現(xiàn)關(guān)鍵的算法， 然后通過(guò)處理器的升級(jí)自然獲得速度的提升。 當(dāng)然這不是一件輕而易舉的事。將功能在硬件和軟件之間劃分是一門(mén)藝術(shù)。 一般認(rèn)為， 硬件（不包括處理器） 缺乏靈活性（不容易增加新的功能） ，且設(shè)計(jì)成本高、周期長(zhǎng)，適合完成較簡(jiǎn)單 的、較固定的功能。 軟件靈活性好，可以很容易地移植到新的、 更快的處理器上， 獲得性能提升。但是動(dòng)態(tài)可重構(gòu)技術(shù)的出現(xiàn)使得這種界線(xiàn)在逐漸模糊，利用動(dòng)態(tài)可重構(gòu)FPGA 實(shí)現(xiàn)的系統(tǒng)，既有硬件的執(zhí)行速度，又有軟件的可編程性，可以執(zhí)行復(fù)雜 的功能

19、（可重構(gòu)處理器） ，設(shè)計(jì)工具的出現(xiàn)也使得硬件設(shè)計(jì)周期大大縮短了。當(dāng) 然現(xiàn)在用 FPGA 構(gòu)造系統(tǒng)還比較貴，成本可能會(huì)是一個(gè)考慮的因素?？傊?，在是否增加硬件、增加什么硬件方面，我們的決策是隨著技術(shù)的發(fā)展 而變化的。以下特殊的硬件技術(shù)通常用于網(wǎng)絡(luò) ASIC 芯片中。P6:用高效的定制例程替換低效的通用例程通用性和高性能通常是一對(duì)矛盾。通用性要求兼顧大多數(shù)情形，一般來(lái)說(shuō)就 不會(huì)針對(duì)某種情形進(jìn)行特殊設(shè)計(jì)。所以，一個(gè)“放之四海皆宜”的東西一定不是 最高效的。比如，操作系統(tǒng)的cache替換策略是LRU，將最長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)的數(shù)據(jù)記錄替換出去，這么做符合一般的程序運(yùn)行模式（局部性原理） 。然而，考慮一個(gè)查 詢(xún)

20、處理例程， 它在處理一個(gè)數(shù)據(jù)庫(kù)查詢(xún)請(qǐng)求時(shí)， 需要依次地處理一系列的數(shù)據(jù)庫(kù) 記錄。在這種情形下， 最近使用過(guò)的數(shù)據(jù)庫(kù)記錄恰恰是最不會(huì)被再次訪(fǎng)問(wèn)的， 因 此應(yīng)當(dāng)選擇這樣的記錄替換出去。 正因?yàn)槿绱耍?許多數(shù)據(jù)庫(kù)應(yīng)用都用定制的緩存 例程替換了操作系統(tǒng)的緩存例程。為避免代碼膨脹，最好只對(duì)關(guān)鍵的例程進(jìn)行定制化。P7:避免不必要的一般性 設(shè)計(jì)抽象的、一般性的子系統(tǒng)可能導(dǎo)致不必要的或者很少使用的特性。我們 可以移除一些不必要的特性來(lái)提高性能， 當(dāng)然這要求例程的使用者能夠接受該限 制。P8:不要受參考實(shí)現(xiàn)的束縛 我們實(shí)現(xiàn)一個(gè)協(xié)議或系統(tǒng)時(shí)，都要遵循相應(yīng)的規(guī)范。規(guī)范是解釋性的，主要 解釋概念、功能、流程等，并不包

21、括實(shí)現(xiàn)。規(guī)范應(yīng)當(dāng)使用規(guī)范語(yǔ)言來(lái)書(shū)寫(xiě)，但是 因?yàn)橐?guī)范語(yǔ)言用得不普遍，許多規(guī)范會(huì)用命令式語(yǔ)言（如 C 語(yǔ)言）給出，即參 考實(shí)現(xiàn)。這些參考實(shí)現(xiàn)給出了如何實(shí)現(xiàn)功能的代碼。這會(huì)帶來(lái)兩個(gè)副作用，一是描述過(guò)于詳細(xì)（規(guī)范應(yīng)當(dāng)只是說(shuō)明要做什么，不 應(yīng)包括怎么做），二是實(shí)現(xiàn)者可能直接將參考實(shí)現(xiàn)代碼拷貝到自己的系統(tǒng)中。但 是，參考實(shí)現(xiàn)代碼只是為了解釋概念， 并不關(guān)注效率， 因此直接使用參考實(shí)現(xiàn)會(huì) 非常低效。P9 和 P10:這里暫不舉例（沒(méi)有找到可以三言?xún)烧Z(yǔ)講清楚的例子） ，下一章結(jié)合具體的 例子再解釋。P11:優(yōu)化預(yù)期情形 盡管系統(tǒng)可能會(huì)呈現(xiàn)出很多種行為，但是大部分情況下，系統(tǒng)的行為是可預(yù) 期的。比如，一個(gè)設(shè)計(jì)良

22、好的系統(tǒng)大部分時(shí)間工作在無(wú)故障的狀態(tài)； 網(wǎng)絡(luò)中的數(shù) 據(jù)包大部分情況是按序到達(dá)的， 并且沒(méi)有出錯(cuò)。 我們有必要去優(yōu)化這些常見(jiàn)的情 形，哪怕使得非預(yù)期情形的處理變得低效。優(yōu)化常見(jiàn)情形的方法通常稱(chēng)為啟發(fā)式方法。啟發(fā)式方法一般不被理論家待 見(jiàn)，他們更傾向于那些能夠用平均指標(biāo)或最壞指標(biāo)精確量化的機(jī)制。 然而，在實(shí) 際的計(jì)算機(jī)系統(tǒng)中，啟發(fā)式方法被大量使用。 （性能才是硬道理）確定常見(jiàn)情形主要依靠設(shè)計(jì)人員的直覺(jué)， 也可以通過(guò)測(cè)量工具來(lái)發(fā)現(xiàn)。 通常， 每個(gè)數(shù)據(jù)包都要進(jìn)行的操作可視為常見(jiàn)情形。P12：增加或利用狀態(tài) 如果一個(gè)操作的代價(jià)很高，可以考慮維護(hù)額外的（冗余的）狀態(tài)來(lái)加速該操 作。數(shù)據(jù)庫(kù)中的一個(gè)典型例子是

23、使用輔助索引。比如，銀行記錄可能使用客戶(hù)的 身份證號(hào)作為主鍵進(jìn)行存儲(chǔ)和查找，但是很多時(shí)候需要根據(jù)客戶(hù)名字進(jìn)行查詢(xún)。 為了加快這種操作，需要利用客戶(hù)名字建立另外一個(gè)索引（如哈希表、B-樹(shù)）。維護(hù)額外的狀態(tài)意味著當(dāng)狀態(tài)有變化的時(shí)候，額外的狀態(tài)也要更新。有時(shí)候可以不增加新的狀態(tài)， 而是利用已有的狀態(tài)， 這種技術(shù)稱(chēng)為增量計(jì)算。 比如，在計(jì)算 IP 頭檢驗(yàn)時(shí)，頭部只有幾個(gè)域有變化，可以進(jìn)行增量計(jì)算（不需 要對(duì)所有的域計(jì)算檢查和） 。P13:優(yōu)化自由度知道哪些變量在我們的控制之下，對(duì)于我們進(jìn)行系統(tǒng)優(yōu)化是很有幫助的。我 們的問(wèn)題就變成了: 優(yōu)化這些變量以最大化性能。 在這里變量就是自由度， 就是 可以由我們

24、改變的因素。使用多分支trie優(yōu)化IP地址查找就是一個(gè)例子。這里有兩個(gè)自由度：（1）不 同層的步長(zhǎng)（檢查的前綴位數(shù)）可以不同； （ 2）每一層上檢查幾個(gè)比特可以通過(guò) 動(dòng)態(tài)規(guī)劃來(lái)確定（對(duì)于給定的吞吐量，最小化內(nèi)存的需求） 。P15:利用算法技術(shù)構(gòu)造高效的數(shù)據(jù)結(jié)構(gòu)在有些情形中，高效的算法肯定可以極大地提高系統(tǒng)的性能。 但是必須注意， 在任何算法問(wèn)題成為瓶頸前，需要先運(yùn)用 P 1 P 1 4原則對(duì)系統(tǒng)進(jìn)行優(yōu)化。換句話(huà) 說(shuō)，在其它問(wèn)題沒(méi)有解決前，算法通常不是瓶頸。因此我們?cè)诳蒲袑?shí)踐中，通常 先考慮數(shù)據(jù)路徑上其它方面的優(yōu)化。 在所有其它問(wèn)題都解決后， 剩下的才是算法 問(wèn)題。經(jīng)常有學(xué)生覺(jué)得，不做算法就不算

25、做研究，做的工作就沒(méi)有技術(shù)含量。事實(shí) 上，真正的高手解決問(wèn)題往往是四兩撥千斤， 用最少的修改把問(wèn)題解決好。 比如， 通過(guò)改變幾行代碼的順序就明顯提高系統(tǒng)性能 （只是這樣的工作寫(xiě)起論文來(lái)不如 算法漂亮）。在系統(tǒng)領(lǐng)域，簡(jiǎn)潔優(yōu)雅的解決方案最受高水平會(huì)議的青睞，因?yàn)檫@ 樣的工作離實(shí)用最接近。 所以我們?cè)谧鱿到y(tǒng)優(yōu)化時(shí)， 遵循的一個(gè)原則是修改越少 越好；在達(dá)到相同效果的前提下， 方法越簡(jiǎn)單越好。 這也是操作系統(tǒng)中很少用復(fù) 雜算法的原因，太復(fù)雜的算法會(huì)影響系統(tǒng)的穩(wěn)定性和可靠性。算法方法包括使用標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)， 以及一般的算法技術(shù)， 如分治和隨機(jī)化。 然而，算法設(shè)計(jì)者必須做好這樣的心理準(zhǔn)備， 就是其設(shè)計(jì)的算法

26、可能隨著系統(tǒng)結(jié) 構(gòu)和技術(shù)的變化而被淘汰。 真正的技術(shù)突破可能來(lái)自算法思維的運(yùn)用， 而不僅僅 是重用已有的算法。3.4 一些警告在運(yùn)用原則前，必須理解重要的性能指標(biāo)，確定系統(tǒng)瓶頸。在完成改進(jìn)后， 必須通過(guò)實(shí)驗(yàn)來(lái)確認(rèn)改進(jìn)的效果。下面用兩個(gè)例子進(jìn)行說(shuō)明。案例一：減少網(wǎng)頁(yè)下載時(shí)間在圖3.8中，web客戶(hù)欲從服務(wù)器獲取內(nèi)嵌有圖像的一個(gè)網(wǎng)頁(yè)。典型地，客 戶(hù)先發(fā)送對(duì)網(wǎng)頁(yè)的GET請(qǐng)求，然后針對(duì)內(nèi)嵌的每個(gè)圖像分別發(fā)送 GET請(qǐng)求。對(duì)原則P1(消除明顯的浪費(fèi))的自然運(yùn)用是：為什么服務(wù)器不自動(dòng)將圖像和 網(wǎng)頁(yè)一起發(fā)送給客戶(hù)，而要等待客戶(hù)的請(qǐng)求呢？這應(yīng)當(dāng)可以減少網(wǎng)頁(yè)的下載延 遲。為了測(cè)試這個(gè)猜想， 作者修改了服務(wù)器軟件

27、， 令服務(wù)器自動(dòng)發(fā)送圖像給客戶(hù)， 然后測(cè)量性能。出乎意料的是，網(wǎng)頁(yè)下載延遲的改進(jìn)很微小。使用一個(gè)基于tcpdump的網(wǎng)絡(luò)分析工具，作者發(fā)現(xiàn)有兩個(gè)原因?qū)е逻@個(gè)看似 不錯(cuò)的改進(jìn)方法是個(gè)壞主意。(1) 與TCP的相互作用：web傳輸建立在TCP之上。TCP在新建立的連接 上使用慢啟動(dòng)發(fā)送數(shù)據(jù)包：首先發(fā)送一個(gè) TCP 段，在收到確認(rèn)后發(fā)送兩個(gè) TCP 段，在收到 ACK 后逐步提高發(fā)送速度。因此，即使令服務(wù)器主動(dòng)發(fā)送圖像，發(fā) 送端 TCP 也必須等待 ACK 來(lái)提高發(fā)送速度， 這和等待客戶(hù)的圖像請(qǐng)求沒(méi)有多大 的區(qū)別。(2) 與內(nèi)容緩存的相互作用：許多客戶(hù)端有緩存功能，一些常用的圖像會(huì) 緩存在本地， 因

28、此令服務(wù)器主動(dòng)發(fā)送已經(jīng)緩存在本地的圖像是對(duì)帶寬的浪費(fèi)。 如 果讓客戶(hù)發(fā)送請(qǐng)求，則客戶(hù)對(duì)于已經(jīng)緩存在本地的圖像不會(huì)發(fā)送 GET 請(qǐng)求。從這個(gè)例子我們了解到， 系統(tǒng)優(yōu)化的困難之一是系統(tǒng)的各個(gè)部分之間存在相 互作用。如果對(duì)這些相互作用沒(méi)有清楚的了解， 則優(yōu)化的效果可能達(dá)不到我們的 預(yù)期。但這里最困難的地方也就是很多時(shí)候不能清楚地理解復(fù)雜的相互作用， 這 時(shí)候?qū)嶒?yàn)驗(yàn)證就很重要了。案例二：加速基于特征的入侵檢測(cè) 許多網(wǎng)站安裝有入侵檢測(cè)系統(tǒng)，目前最流行的入侵檢測(cè)系統(tǒng)是snort。 Snort根據(jù)系統(tǒng)中安裝的一組規(guī)則來(lái)檢測(cè)攻擊。圖示為 snort的一條規(guī)則，包括如下幾 個(gè)部分：動(dòng)作：包括 pass、aler

29、t、log 三種。協(xié)議：包括 TCP、UDP、ICMP 三種。 源網(wǎng)絡(luò)：通常是除本地網(wǎng)絡(luò)之外的所有網(wǎng)絡(luò)。 源端口：本規(guī)則為 any。目的網(wǎng)絡(luò)：通常是本地網(wǎng)絡(luò) 目的端口：本規(guī)則為 80。 Msg :如果匹配該條規(guī)則，則給出該條提示。 Flags：匹配該規(guī)則的TCP包，這些標(biāo)志必須置位。 Co ntent:包載荷中包含的特征字符串，可能不止一個(gè)。 Nocase表示特征串是大小寫(xiě)無(wú)關(guān)的和防火墻的過(guò)濾規(guī)則只匹配 IP 地址、端口號(hào)、協(xié)議、 TCP 標(biāo)志位等不同，snort的規(guī)則還要匹配數(shù)據(jù)包載荷中指定的字符串。經(jīng)統(tǒng)計(jì)，84%的snort規(guī)則中包含字符串。實(shí)驗(yàn)表明，字符串匹配是 snort中開(kāi)銷(xiāo)最大的操

30、作，占整個(gè)執(zhí)行時(shí) 間的 31%。Snort 匹配規(guī)則的方法作者發(fā)現(xiàn)，匹配某個(gè)過(guò)濾器的規(guī)則數(shù)可能很多，比如匹配 80 端口的規(guī)則多 達(dá)310條（大量攻擊是利用web進(jìn)行的），逐條規(guī)則地運(yùn)用BM算法查找字符串， 開(kāi)銷(xiāo)很大。P1 原則的簡(jiǎn)單應(yīng)用作者將規(guī)則集中所有的字符串抽出來(lái)組織到一個(gè)自動(dòng)機(jī)中， 修改了 BM 算法， 使得用包內(nèi)容作為輸入，一遍掃描就能找出所有匹配的字符串（給出字符串編 號(hào)）。作者將這個(gè)新算法應(yīng)用到snort的整個(gè)規(guī)則集上，發(fā)現(xiàn)其性能為snort中算法 的50倍。然而，當(dāng)作者將這個(gè)新算法集成到snort中，并用一個(gè)包蹤跡文件（用 tcpdump從網(wǎng)絡(luò)中抓真實(shí)的包，存在文件中）進(jìn)行測(cè)試

31、時(shí)，發(fā)現(xiàn)新算法在性能上 幾乎沒(méi)有改進(jìn)！作者仔細(xì)分析后，認(rèn)為有兩個(gè)方面的原因可以解釋該問(wèn)題：（1）實(shí)驗(yàn)使用的包蹤跡文件包含了很少的 web 流量，在匹配了過(guò)濾器后只 有很少的數(shù)據(jù)包還要匹配多條規(guī)則，因此多字符串匹配在該蹤跡文件上不是瓶頸。當(dāng)作者換用僅包含 web流量的包蹤跡文件進(jìn)行測(cè)試時(shí)，性能提高非常明顯。 也就是說(shuō)，算法性能與流量模式有很大的關(guān)系，不是所有時(shí)候都有效。（2） cache的影響：多字符串查找需要使用一個(gè)數(shù)據(jù)結(jié)構(gòu)（如trie），其大小 隨字符串?dāng)?shù)量的增大而增大。 研究發(fā)現(xiàn)，當(dāng)字符串?dāng)?shù)量超過(guò) 100條時(shí)，數(shù)據(jù)結(jié)構(gòu) 已經(jīng)大到無(wú)法放入cache中，而Snort中包含的字符串?dāng)?shù)量達(dá)到幾千條。也就是 說(shuō)，算法性能還和規(guī)則集的大小有關(guān)，僅僅將單字符串匹配換成多字符串匹配， 并不能一定提高性能。教訓(xùn)：有時(shí)候聲稱(chēng)的改進(jìn)可能沒(méi)有針對(duì)真正的瓶頸（如大多數(shù)情況是單串匹 配），也可能與系統(tǒng)的其它部分有相互作用（如 c