第二部分端節(jié)點(diǎn)算法學(xué)

1、第二部分 端節(jié)點(diǎn)算法學(xué),端節(jié)點(diǎn)算法學(xué),端節(jié)點(diǎn)算法學(xué)：網(wǎng)絡(luò)算法學(xué)在端節(jié)點(diǎn)（尤其是服務(wù)器）上的運(yùn)用，是建立高速服務(wù)器的一組系統(tǒng)性技術(shù)隨著網(wǎng)絡(luò)功能虛擬化的提出，將來(lái)數(shù)據(jù)中心中絕大部分的網(wǎng)絡(luò)設(shè)備都會(huì)在通用服務(wù)器上實(shí)現(xiàn)端節(jié)點(diǎn)算法學(xué)研究如何減少以下開(kāi)銷(xiāo)：數(shù)據(jù)拷貝（chapter 5）控制轉(zhuǎn)移（chapter 6）定時(shí)器（chapter 7）解復(fù)用（chapter 8）其它一般性協(xié)議處理任務(wù) （chapter 9）,第五章 拷貝數(shù)

2、據(jù),消除不必要的拷貝（P1）,網(wǎng)絡(luò)報(bào)文在收發(fā)和處理的過(guò)程中，通常會(huì)被拷貝多次計(jì)算機(jī)中的數(shù)據(jù)拷貝消耗兩個(gè)寶貴的資源：內(nèi)存帶寬：如果處理一個(gè)報(bào)文涉及k次拷貝，系統(tǒng)吞吐量可能降至1/k內(nèi)存：如果一個(gè)報(bào)文在內(nèi)存中被保存k份，有效內(nèi)存容量降至1/k本章關(guān)注如何消除不必要的拷貝：一個(gè)拷貝如果不是由硬件要求的，該拷貝是不必要的本章還將討論其它需要對(duì)數(shù)據(jù)包載荷進(jìn)行的操作,5.1 為什么要拷貝數(shù)據(jù),應(yīng)用場(chǎng)景：用戶(hù)向web服務(wù)器請(qǐng)求一個(gè)靜態(tài)文

3、件服務(wù)器從磁盤(pán)讀出文件，發(fā)送到網(wǎng)絡(luò)上兩個(gè)內(nèi)核子系統(tǒng)：文件子系統(tǒng)網(wǎng)絡(luò)子系統(tǒng),一個(gè)簡(jiǎn)單的故事,直觀上，這是一個(gè)簡(jiǎn)單的故事：web應(yīng)用程序通過(guò)一個(gè)系統(tǒng)調(diào)用（讀文件），將文件從磁盤(pán)讀入到它的緩沖區(qū)中構(gòu)造一個(gè)HTTP響應(yīng)頭，通過(guò)一個(gè)系統(tǒng)調(diào)用（寫(xiě)套接字），將響應(yīng)頭和緩沖區(qū)內(nèi)容交給網(wǎng)絡(luò)子系統(tǒng)網(wǎng)絡(luò)子系統(tǒng)將數(shù)據(jù)劃分成適當(dāng)大小的塊，加上各層協(xié)議頭，交給網(wǎng)絡(luò)驅(qū)動(dòng)程序,一個(gè)真實(shí)的故事,Copy 1：硬盤(pán)?文件緩沖區(qū)（內(nèi)核空間）Copy 2：

4、文件緩沖區(qū)?應(yīng)用緩沖區(qū) （用戶(hù)空間）Copy 3：應(yīng)用緩沖區(qū)?套接字緩沖區(qū)（內(nèi)核空間）Copy 4：套接字緩沖區(qū)?網(wǎng)卡TCP程序還需要掃描一遍數(shù)據(jù)，計(jì)算TCP檢查和,資源消耗情況,拷貝和TCP檢查和計(jì)算：每個(gè)字需要穿過(guò)內(nèi)存總線(xiàn)7~9次！不同內(nèi)存區(qū)域之間的拷貝（copy 2，copy 3）：每個(gè)字都要通過(guò)內(nèi)存總線(xiàn)讀一次和寫(xiě)一次計(jì)算TCP檢查和：每個(gè)字都要通過(guò)內(nèi)存總線(xiàn)讀一次涉及外設(shè)的拷貝（copy 1，copy 4）：

5、如果由CPU做拷貝（PIO）：每個(gè)字都要通過(guò)內(nèi)存總線(xiàn)讀一次和寫(xiě)一次如果由設(shè)備做拷貝（DMA）：每個(gè)字只需通過(guò)內(nèi)存總線(xiàn)讀一次或?qū)懸淮紊婕巴庠O(shè)的拷貝都需要消耗I/O總線(xiàn)帶寬,對(duì)服務(wù)器吞吐量的影響,在上面的例子中：Web服務(wù)器吞吐量不超過(guò)T/7，T為內(nèi)存速度和內(nèi)存總線(xiàn)速度中的較小值有效的文件緩沖區(qū)大小僅為總?cè)萘康?/3多余的拷貝在兩個(gè)方面損害了服務(wù)器的性能：由于使用了過(guò)多的總線(xiàn)和內(nèi)存帶寬，服務(wù)器的運(yùn)行速度遠(yuǎn)遠(yuǎn)低于總線(xiàn)速度由于使

6、用了過(guò)多的內(nèi)存，服務(wù)器不得不大量地從磁盤(pán)而不是主存讀文件如果請(qǐng)求動(dòng)態(tài)內(nèi)容，還要增加一次拷貝（CGI程序?web服務(wù)器）,請(qǐng)求動(dòng)態(tài)內(nèi)容,Step 6：CGI 程序?qū)?gòu)造好的網(wǎng)頁(yè)文件，通過(guò)進(jìn)程間通信機(jī)制傳給web服務(wù)器程序，涉及一次拷貝,5.2 消除copy 4,為什么需要copy 4？簡(jiǎn)單的解釋?zhuān)哼m配器內(nèi)存和內(nèi)核存儲(chǔ)空間不在同一個(gè)硬件上但是，這個(gè)理由不充分！,消除 Copy 4,在一個(gè)內(nèi)存映射的體系結(jié)構(gòu)中，設(shè)備寄存器被映射到

7、一塊內(nèi)存區(qū)域，CPU通過(guò)讀寫(xiě)這塊內(nèi)存區(qū)域與設(shè)備通信理論上，內(nèi)存可以位于總線(xiàn)上的任何地方，包括在適配器中解決方案：利用網(wǎng)絡(luò)適配器中已有的存儲(chǔ)空間（P4，利用系統(tǒng)組件），以及內(nèi)核存儲(chǔ)空間放置的自由度（P13，利用自由度），將套接字緩沖區(qū)放在網(wǎng)絡(luò)適配器中應(yīng)用緩沖區(qū)的內(nèi)容直接拷貝到網(wǎng)絡(luò)適配器的內(nèi)存中,如何計(jì)算TCP檢查和？,如何計(jì)算檢查和？,Witless方法（P2c，共享開(kāi)銷(xiāo)）：CPU執(zhí)行拷貝，當(dāng)讀入每個(gè)字時(shí)，捎帶計(jì)算檢查和致命

8、的問(wèn)題：接收的時(shí)候，當(dāng)發(fā)現(xiàn)檢查和出錯(cuò)時(shí)數(shù)據(jù)包已被寫(xiě)入應(yīng)用緩沖區(qū)，與TCP語(yǔ)義不符（所以該方法從未被實(shí)施）Afterburner適配器（TCP offloading engine）：數(shù)據(jù)傳輸由網(wǎng)卡通過(guò)DMA完成，檢查和也由網(wǎng)卡計(jì)算TCP連接的管理（建立、關(guān)閉等）仍由主CPU完成，僅將建立好的TCP連接移交給網(wǎng)絡(luò)適配器問(wèn)題：網(wǎng)絡(luò)適配器需要很大的內(nèi)存空間和較強(qiáng)的處理器來(lái)支持大量的TCP連接，網(wǎng)卡成本可能較高,5.3 消除 Copy

9、 3,為什么需要copy 3？應(yīng)用和內(nèi)核使用不同的虛擬地址空間（不是必要的）應(yīng)用和內(nèi)核之間需要通過(guò)數(shù)據(jù)拷貝解除耦合（必要的）如果拷貝不能避免，那么能夠減小拷貝的開(kāi)銷(xiāo)嗎？,寫(xiě)時(shí)拷貝（copy-on-write）,當(dāng)應(yīng)用程序?qū)?nèi)核執(zhí)行一個(gè)寫(xiě)時(shí)拷貝時(shí)，OS將內(nèi)核緩沖區(qū)映射到應(yīng)用緩沖區(qū)的物理內(nèi)存頁(yè)上當(dāng)應(yīng)用程序試圖修改其緩沖區(qū)時(shí)，內(nèi)核進(jìn)行真正的拷貝有些操作系統(tǒng)提供寫(xiě)時(shí)拷貝，很多情況下可以避免真正的拷貝,寫(xiě)時(shí)拷貝的實(shí)現(xiàn),舉例：假定

10、進(jìn)程 P1 的虛擬頁(yè) X 映射到物理頁(yè) L上，需要復(fù)制 X的內(nèi)容到進(jìn)程 P2 的虛擬頁(yè) Y當(dāng)P1對(duì) X 進(jìn)行寫(xiě)時(shí)拷貝時(shí)：內(nèi)核修改頁(yè)表，令 Y 指向物理頁(yè) L將 X 表項(xiàng)的COW保護(hù)位置位當(dāng)P1試圖寫(xiě)頁(yè)X時(shí)：硬件讀X的COW位，發(fā)現(xiàn)置位，產(chǎn)生一個(gè)異常操作系統(tǒng)將物理頁(yè) L拷貝到物理頁(yè) L’，清除 X 的COW位，令 X 指向 L’，Y 繼續(xù)指向 L,寫(xiě)時(shí)拷貝的實(shí)現(xiàn)（續(xù)）,對(duì)于不提供寫(xiě)時(shí)拷貝功能的操作系統(tǒng)（如UNIX和Window

11、s），也可以基于虛擬內(nèi)存實(shí)現(xiàn)類(lèi)似的功能：可以通過(guò)修改頁(yè)表避免物理拷貝需要找到一種替代COW位的保護(hù)機(jī)制,5.4 優(yōu)化頁(yè)面重映射,對(duì)頁(yè)面重映射過(guò)于簡(jiǎn)單的看法：只需修改P2的頁(yè)表（一次寫(xiě)操作），令VP 8指向存放包的物理頁(yè) ，所有工作就結(jié)束了,（X）,頁(yè)面重映射的開(kāi)銷(xiāo),修改多級(jí)頁(yè)表：實(shí)際映射可能要求修改多級(jí)頁(yè)表，當(dāng)頁(yè)表不在內(nèi)存中時(shí)要調(diào)入，并修改目錄頁(yè)要求鎖操作：修改頁(yè)表前后要有請(qǐng)求鎖和釋放鎖的開(kāi)銷(xiāo)刷新TLB：新的地址映射寫(xiě)入

12、頁(yè)表時(shí)，相關(guān)TLB表項(xiàng)要清除或修正,在目標(biāo)域中分配虛擬內(nèi)存：系統(tǒng)要在目標(biāo)進(jìn)程中找到一個(gè)空閑的頁(yè)表表項(xiàng)鎖住物理頁(yè)：為防止頁(yè)被換出，必須鎖住物理頁(yè)以上開(kāi)銷(xiāo)在多處理器系統(tǒng)中會(huì)被放大頁(yè)面重映射雖然只需常數(shù)時(shí)間，但這個(gè)常數(shù)因子非常大,結(jié)論：如果只是簡(jiǎn)單地使用頁(yè)表重映射來(lái)避免拷貝，結(jié)果可能不像預(yù)期的那么好,Fbufs（fast buffers）,基本觀察：如果一個(gè)應(yīng)用正在發(fā)送大量的數(shù)據(jù)包，那么一個(gè)包緩沖區(qū)可能會(huì)被重用多次方法一：提

13、前分配好需要的包緩沖區(qū)，并計(jì)算好所有的頁(yè)面映射信息（P2a），發(fā)送時(shí)重復(fù)使用這些包緩沖區(qū)方法二：數(shù)據(jù)傳輸開(kāi)始時(shí)分配包緩沖區(qū)并計(jì)算頁(yè)面映射，然后將其緩存起來(lái)（P11a），消除后續(xù)包的頁(yè)面映射開(kāi)銷(xiāo)基本思想：映射一次，重復(fù)使用,為應(yīng)用分配一組固定的物理頁(yè),為避免內(nèi)核空間和用戶(hù)空間之間的拷貝，將一組物理頁(yè)P(yáng)1、P2、……、Pk 同時(shí)映射給內(nèi)核和應(yīng)用來(lái)使用數(shù)據(jù)包經(jīng)過(guò)的一系列處理程序構(gòu)成一個(gè)有序的安全域序列，定義為一條路徑為每一條路徑預(yù)留

14、固定的一組物理頁(yè)，數(shù)據(jù)包到達(dá)時(shí)立即確定其所屬的路徑（提前解復(fù)用）,在路徑上傳遞包緩沖區(qū)描述符,對(duì)于每條路徑，適配器有一個(gè)空閑緩沖區(qū)鏈表：適配器把數(shù)據(jù)包寫(xiě)入一個(gè)空閑緩沖區(qū)，將緩沖區(qū)描述符傳給接收路徑上的下一個(gè)進(jìn)程最后一個(gè)進(jìn)程將用完的緩沖區(qū)交還給第一個(gè)進(jìn)程，緩沖區(qū)重新回到空閑緩沖區(qū)鏈表,實(shí)現(xiàn)單向路徑,有序的安全域序列是一條單向路徑：規(guī)定第一個(gè)進(jìn)程是writer，其余進(jìn)程是reader（為了提供一定的保護(hù)級(jí)別）給第一個(gè)進(jìn)程的頁(yè)表表項(xiàng)設(shè)

15、置寫(xiě)允許位，給其它進(jìn)程的頁(yè)表表項(xiàng)設(shè)置只讀位,映射到同一個(gè)物理頁(yè)的虛擬頁(yè)號(hào)應(yīng)相同,在進(jìn)程間傳遞緩沖區(qū)描述符的問(wèn)題：理論上，各個(gè)進(jìn)程映射到同一個(gè)物理頁(yè)上的虛擬頁(yè)號(hào)可能不同解決方法：規(guī)定：映射到同一個(gè)物理頁(yè)的虛擬頁(yè)號(hào)必須相同實(shí)現(xiàn)：所有進(jìn)程的虛擬內(nèi)存中一定數(shù)量的起始頁(yè)預(yù)留為 fbuf 頁(yè),收包處理過(guò)程,P1從free fbufs隊(duì)列取一個(gè)空閑緩沖區(qū)，寫(xiě)入數(shù)據(jù)包，將緩沖區(qū)的描述符寫(xiě)入written fbufs隊(duì)列P2從written

16、 fbufs隊(duì)列取包緩沖區(qū)描述符，讀相應(yīng)的包緩沖區(qū)P2將釋放的包緩沖區(qū)描述符寫(xiě)回free fbufs隊(duì)列,如何添加包頭？,在發(fā)送路徑上，每一個(gè)安全域都要給數(shù)據(jù)包加上一個(gè)包頭然而，為了實(shí)現(xiàn)保護(hù)，每條路徑只允許一個(gè)writer，其余為reader問(wèn)題：怎么允許其它安全域添加包頭呢？,定義數(shù)據(jù)包為聚合數(shù)據(jù)結(jié)構(gòu),將數(shù)據(jù)包定義為一個(gè)帶有指針的聚合數(shù)據(jù)結(jié)構(gòu)，每個(gè)指針指向一個(gè)fbuf給數(shù)據(jù)包添加包頭，就是將一個(gè)fbuf添加到聚合數(shù)據(jù)結(jié)構(gòu)中

17、,Fbufs總結(jié),Fbufs運(yùn)用了虛擬內(nèi)存映射的思想，通過(guò)在大量數(shù)據(jù)包之間分?jǐn)傢?yè)面映射開(kāi)銷(xiāo)而做得更高效：包緩沖區(qū)映射一次，重復(fù)使用很多次消除了一般情形中的頁(yè)表更新有人擴(kuò)展了Fbufs思想，并實(shí)現(xiàn)在Sun Solaris操作系統(tǒng)中Intel DPDK也運(yùn)用了“一次映射，重復(fù)使用”的思想,應(yīng)用如何使用Fbufs？,大量已有的應(yīng)用軟件是根據(jù)拷貝語(yǔ)義的socket API寫(xiě)的:應(yīng)用執(zhí)行了write()系統(tǒng)調(diào)用后，就可以重用包緩沖區(qū)，

18、甚至釋放包緩沖區(qū)了采用fbufs后：在包緩沖區(qū)被其它進(jìn)程使用完之前，應(yīng)用不允許寫(xiě)或釋放包緩沖區(qū),解決方案：修改應(yīng)用API,解決方法：API 不再保持拷貝語(yǔ)義應(yīng)用在寫(xiě)緩沖區(qū)之前必須進(jìn)行判斷安全的實(shí)現(xiàn)方法：當(dāng)一個(gè)fbuf從應(yīng)用傳遞到內(nèi)核后，內(nèi)核翻轉(zhuǎn)一個(gè)寫(xiě)允許比特，歸還fbuf時(shí)再重新設(shè)置該位若應(yīng)用在不允許寫(xiě)的情況下做寫(xiě)操作，會(huì)產(chǎn)生一個(gè)異常，應(yīng)用崩潰，但不影響其它進(jìn)程,已有的網(wǎng)絡(luò)應(yīng)用軟件必須重寫(xiě)嗎？,方法一：給已有的 AP

19、I 增加新的系統(tǒng)調(diào)用，要求高性能的應(yīng)用使用新的系統(tǒng)調(diào)用進(jìn)行重寫(xiě)方法二：用新的擴(kuò)展實(shí)現(xiàn)一個(gè)公共的I/O庫(kù)，鏈接到該庫(kù)的應(yīng)用不需要修改，就可以得到性能提升 實(shí)踐表明，將應(yīng)用移植到類(lèi)fbuf的API，對(duì)應(yīng)用所做的修改不大，且是局部的,5.5 使用RDMA避免拷貝,在web服務(wù)器的例子中：Web服務(wù)器接收請(qǐng)求，將文件傳輸?shù)骄W(wǎng)絡(luò)上Web服務(wù)器作為接收端并不需要保存請(qǐng)求消息現(xiàn)考慮在兩個(gè)計(jì)算機(jī)之間傳輸一個(gè)大文件，接收端采用以下方式之一

20、收包：采用fbufs采用TOE網(wǎng)卡,采用fbufs收包,包到達(dá)網(wǎng)卡后，被拷貝到一個(gè)包緩沖區(qū)中包緩沖區(qū)描述符在路徑上傳遞，各安全域處理包應(yīng)用程序?qū)鼣?shù)據(jù)拷貝到應(yīng)用緩沖區(qū)，釋放包緩沖區(qū),采用TOE網(wǎng)卡收包,包到達(dá)網(wǎng)卡后，被送入套接字緩沖區(qū)進(jìn)行協(xié)議處理和重組DMA控制器將數(shù)據(jù)送入應(yīng)用緩沖區(qū)，向CPU發(fā)出中斷驅(qū)動(dòng)程序處理中斷，通知內(nèi)核模塊接收數(shù)據(jù)，交給應(yīng)用應(yīng)用拷貝數(shù)據(jù)到文件緩沖區(qū)，應(yīng)用緩沖區(qū)返回給網(wǎng)卡,直接內(nèi)存訪問(wèn)（DMA）,在上

21、述兩種方法中，數(shù)據(jù)到達(dá)目的計(jì)算機(jī)的內(nèi)存后還需拷貝一次，CPU參與的拷貝是開(kāi)銷(xiāo)最大的使用DMA在外設(shè)和內(nèi)存之間傳輸數(shù)據(jù)，不需要CPU的參與：CPU設(shè)置DMA（給出數(shù)據(jù)的存放地址、長(zhǎng)度等）DMA控制器完成數(shù)據(jù)傳輸DMA控制器通過(guò)中斷通知CPU傳輸完成受DMA的啟發(fā)，能否在兩臺(tái)計(jì)算機(jī)的內(nèi)存之間直接傳輸數(shù)據(jù)，而不需要CPU參與？,遠(yuǎn)程直接內(nèi)存訪問(wèn)（RDMA）,RDMA的愿景：數(shù)據(jù)在兩臺(tái)計(jì)算機(jī)的主存之間直接傳輸，不需要CPU參與到

22、數(shù)據(jù)傳輸?shù)倪^(guò)程中兩個(gè)網(wǎng)絡(luò)適配器協(xié)作地從一個(gè)主存讀數(shù)據(jù)，然后寫(xiě)入另一個(gè)主存,RDMA需要解決的問(wèn)題,除了需要網(wǎng)卡執(zhí)行TCP/IP協(xié)議外，RDMA還需解決兩個(gè)問(wèn)題：接收端適配器如何知道應(yīng)將數(shù)據(jù)放在哪兒？（不能求助CPU）如何保證安全？（發(fā)送進(jìn)程不能隨意寫(xiě)目標(biāo)終端的內(nèi)存）,VAX集群 的RDMA,RDMA在VAX集群中已經(jīng)被使用，VAX集群為可伸縮應(yīng)用（如數(shù)據(jù)庫(kù)應(yīng)用）提供計(jì)算平臺(tái)：系統(tǒng)核心是一個(gè)140Mb/s的網(wǎng)絡(luò)（稱(chēng)Computer

23、 Interconnect，CL），使用一個(gè)以太網(wǎng)風(fēng)格的協(xié)議用戶(hù)可以將許多VAX計(jì)算機(jī)和網(wǎng)絡(luò)硬盤(pán)連接到CLRDMA的需求背景：在遠(yuǎn)程硬盤(pán)和VAX機(jī)的內(nèi)存之間有效傳輸大量數(shù)據(jù)要求包含文件數(shù)據(jù)的包在進(jìn)入目的適配器之后，直接到達(dá)它的存放位置,傳統(tǒng)網(wǎng)絡(luò)的接收端,接收端應(yīng)用提前將一些映射好的頁(yè)放入一個(gè)隊(duì)列，交給網(wǎng)絡(luò)適配器使用到達(dá)網(wǎng)卡的數(shù)據(jù)包被依次放入這些頁(yè)中（數(shù)據(jù)包可能亂序到達(dá)）接收完數(shù)據(jù)包后，CPU做一個(gè)重映射（使得在應(yīng)用看來(lái)

24、，數(shù)據(jù)按順序存放在一個(gè)地址連續(xù)的緩沖區(qū)中）。若文件很大，重映射的開(kāi)銷(xiāo)很大。,VAX 的 RDMA 解決方案,接收端應(yīng)用鎖住一些物理頁(yè)，用作文件傳輸?shù)哪繕?biāo)存儲(chǔ)區(qū)域（其呈現(xiàn)出來(lái)的邏輯視圖是由地址連續(xù)的虛擬頁(yè)組成的一個(gè)緩沖區(qū)），緩沖區(qū)ID被發(fā)送給發(fā)送端應(yīng)用發(fā)送端應(yīng)用將緩沖區(qū)ID及包存放的偏移量，隨同數(shù)據(jù)包一起發(fā)送到接收端接收端適配器根據(jù)緩沖區(qū)ID和偏移量，將數(shù)據(jù)包內(nèi)容存放到指定的位置（不需要頁(yè)面重映射）,如何保證安全？,允許將一個(gè)攜帶

25、緩沖區(qū)ID的網(wǎng)絡(luò)包直接寫(xiě)入內(nèi)存，是一個(gè)明顯的安全隱患為降低安全風(fēng)險(xiǎn)，緩沖區(qū)ID中包含一個(gè)難以猜測(cè)的隨機(jī)串（防止偽造）VAX集群只在本集群內(nèi)部可信的計(jì)算機(jī)之間使用RDMA傳遞數(shù)據(jù),RDMA的應(yīng)用,存儲(chǔ)區(qū)域網(wǎng)（Storage Area Network，SAN）：一種后端網(wǎng)絡(luò)，將大量計(jì)算機(jī)和網(wǎng)絡(luò)硬盤(pán)連接在一起目前有好幾種這樣的技術(shù)，都使用了RDMA的思想，如Fiber Channel（FC）、iSCSI、Infiniband等數(shù)

26、據(jù)中心支持高性能分布式計(jì)算：大數(shù)據(jù)分析（MapReduce框架）深度學(xué)習(xí)（TensorFlow、Caffe等）,5.6 把避免拷貝技術(shù)擴(kuò)展到文件系統(tǒng),為提高響應(yīng)速度，Copy 1是必要的考慮消除copy 2,5.6.1 共享內(nèi)存方法,類(lèi)UNIX操作系統(tǒng)提供一個(gè)系統(tǒng)調(diào)用mmap()，允許應(yīng)用（如web服務(wù)器）將一個(gè)文件映射到自己的虛擬地址空間。概念上，當(dāng)一個(gè)文件被映射到一個(gè)應(yīng)用的地址空間，這個(gè)應(yīng)用就好像在自己的內(nèi)存中緩存了這

27、份文件。當(dāng)然，這個(gè)緩存的文件只是一組映射。如果Web程序?qū)⑽募成涞阶约旱牡刂房臻g，則它和文件cache訪問(wèn)的是同一組物理頁(yè)（免除了拷貝）。,Flash Web服務(wù)器,Web應(yīng)用程序?qū)⒔?jīng)常用到的文件映射到自己的內(nèi)存空間受到可分配給文件頁(yè)的物理頁(yè)數(shù)量及頁(yè)表映射的限制，F(xiàn)lash Web服務(wù)器只能緩存和映射最近常用的文件事實(shí)上，F(xiàn)lash Web服務(wù)器只是緩存了一些文件分片（通常是文件的頭幾個(gè)分片），并使用LRU策略將最近一段時(shí)

28、間未用的文件unmap,尚未解決的問(wèn)題,Flash Web 不能避免web服務(wù)器與CGI進(jìn)程之間的拷貝文件緩存只能緩存靜態(tài)內(nèi)容，動(dòng)態(tài)網(wǎng)頁(yè)要由CGI程序生成CGI程序生成的動(dòng)態(tài)內(nèi)容通過(guò)UNIX管道傳給web服務(wù)器；典型地，管道要在兩個(gè)地址空間之間拷貝內(nèi)容到目前為止，我們的方案都沒(méi)有涉及TCP檢查和一個(gè)被訪問(wèn)多次的文件，文件分片都相同，但TCP檢查和未被緩存需要一個(gè)從包內(nèi)容映射到檢查和的高速緩存，即 數(shù)組，a 為包內(nèi)容，f(a)

29、為檢查和；由于a太大，采用傳統(tǒng)緩存方案很低效,由 fbufs 和 mmap() 想到的問(wèn)題,fbufs可以消除 copy 3mmap()可以消除copy 2Q：能否將 fbufs 和 mmap() 結(jié)合起來(lái)使用，同時(shí)消除 copy2 和 copy3 ？,可以結(jié)合 fbufs 和 mmap 嗎？,如果采用fbufs：所有進(jìn)程的虛擬內(nèi)存中一定數(shù)量的起始頁(yè)預(yù)留為fbuf頁(yè)應(yīng)用進(jìn)程的應(yīng)用緩沖區(qū)不能被映射到這些物理頁(yè)上如果

30、應(yīng)用將文件映射到其虛擬地址空間的一個(gè)緩沖區(qū)：這個(gè)緩沖區(qū)不能用fbuf發(fā)送，必須要有一次物理拷貝！當(dāng)消除copy 2時(shí)，copy 3不能避免！,5.6.2 IO-Lite,IO-Lite 將 fbufs 推廣至包含文件系統(tǒng)，從而不必使用 mmapIO-Lite可以一攬子解決前面所有的問(wèn)題：同時(shí)消除 copy 2 和 copy 3消除CGI程序和web服務(wù)器之間的拷貝緩存?zhèn)魉瓦^(guò)的數(shù)據(jù)包的檢查和,IO-Lite 的主要思想,

31、IO-Lite 借用了 fbufs 的主要思想：為同一條路徑上的進(jìn)程映射相同的物理頁(yè)，實(shí)現(xiàn)只讀共享推遲創(chuàng)建路徑的緩沖區(qū)使用緩沖區(qū)聚合以允許添加包頭,IO-Lite 響應(yīng) Get 請(qǐng)求,IO-Lite 響應(yīng) Get 請(qǐng)求的步驟,當(dāng)文件第一次從磁盤(pán)讀入文件系統(tǒng)的高速緩存時(shí)，文件頁(yè)被保存為IO-Lite buffer當(dāng)應(yīng)用通過(guò)一個(gè)系統(tǒng)調(diào)用讀文件時(shí)，創(chuàng)建一個(gè)緩沖區(qū)聚合體，指針指向IO-Lite buffer當(dāng)應(yīng)用發(fā)送文件給TCP時(shí)，網(wǎng)

32、絡(luò)子系統(tǒng)得到一個(gè)指向相同IO-Lite頁(yè)的指針應(yīng)用將常用文件的HTTP響應(yīng)頭維護(hù)在一個(gè)高速緩存中IO-Lite給每個(gè)緩沖區(qū)分配一個(gè)編號(hào)，TCP模塊維護(hù)一個(gè)以緩沖區(qū)編號(hào)為索引的檢查和高速緩存,實(shí)現(xiàn)零拷貝的管道,IO-Lite也可以用來(lái)實(shí)現(xiàn)一個(gè)消除了拷貝的改良型管道程序（傳遞IO-Lite buffer的指針而不是拷貝）將改良后的管道應(yīng)用到CGI程序和web服務(wù)器之間，可以消除冗余的拷貝,實(shí)現(xiàn)IO-Lite,IO-Lite必須處理復(fù)

33、雜的共享模式：應(yīng)用程序、TCP程序和文件服務(wù)器等均可能有指向IO-Lite buffer的緩沖區(qū)IO-Lite必須實(shí)現(xiàn)一個(gè)復(fù)雜的替換策略：IO-Lite頁(yè)既可能是虛擬內(nèi)存頁(yè)又可能是文件頁(yè)需將標(biāo)準(zhǔn)的頁(yè)替換規(guī)則和文件緩存替換策略集成在一起找到一種干凈的方法將IO-Lite集成到OS中IO-Lite已經(jīng)在UNIX中實(shí)現(xiàn)了,5.6.3 使用I/O拼接避免文件系統(tǒng)拷貝,I/O拼接的基本思想：引入一個(gè)新的系統(tǒng)調(diào)用sendfile()

34、，允許內(nèi)核將讀文件的調(diào)用和向網(wǎng)絡(luò)發(fā)送消息的調(diào)用合并文件到socket傳輸?shù)膫鹘y(tǒng)方法需兩次系統(tǒng)調(diào)用：read (file, tem_buf, len); write (socket, tmp_buf, len); 使用sendfile()傳輸文件到socket：sendfile (socket, file, len);,內(nèi)核2.1版本的sendfile實(shí)現(xiàn),調(diào)用sendfile()時(shí)：文件數(shù)據(jù)先被拷貝到內(nèi)

35、核中的文件緩沖區(qū)（copy 1）然后從文件緩沖區(qū)拷貝到內(nèi)核中的socket緩沖區(qū)（合并copy 2和copy 3）最后從socket緩沖區(qū)拷貝到適配器（copy 4）與read/write方式相比，減少了一次拷貝,內(nèi)核版本2.4之后的sendfile實(shí)現(xiàn),調(diào)用sendfile()時(shí)：文件數(shù)據(jù)先被拷貝到內(nèi)核中的文件緩沖區(qū)（copy 1）將記錄數(shù)據(jù)位置和長(zhǎng)度的信息保存到socket緩沖區(qū)數(shù)據(jù)通過(guò)DMA通道直接發(fā)送到適配器（cop

36、y 4）消除了copy 2 和 copy 3基于sendfile的機(jī)制不能推廣到與CGI程序通信Sendfile() 已用于Apache、Nginx、Lighttpd等web服務(wù)器中,5.7 擴(kuò)展到拷貝之外,除數(shù)據(jù)拷貝外，其它涉及所有數(shù)據(jù)的操作也是高開(kāi)銷(xiāo)操作，如檢查和計(jì)算、格式轉(zhuǎn)換等：需要CPU參與需要使用內(nèi)存總線(xiàn)計(jì)算開(kāi)銷(xiāo)與數(shù)據(jù)長(zhǎng)度成正比將拷貝循環(huán)擴(kuò)展到包括檢查和計(jì)算：利用load和store之間的空周期做累加計(jì)算

37、不增加任何額外的開(kāi)銷(xiāo),Integrated Layer Processing（ILP）,除檢查和之外，其它數(shù)據(jù)密集的操作能否都集成到拷貝循環(huán)中？整合層次處理（ILP）的主要思想：對(duì)同一個(gè)數(shù)據(jù)包進(jìn)行多種數(shù)據(jù)操作時(shí)，將這些操作整合在一個(gè)循環(huán)中，避免對(duì)包中的數(shù)據(jù)進(jìn)行多次的讀和寫(xiě)（P1）。整合層次處理會(huì)有什么問(wèn)題？,ILP面臨的問(wèn)題,問(wèn)題一：不同操作需要的信息一般來(lái)自不同的層次，將不同層次的代碼整合在一起而不犧牲模塊化特性極其困難

38、問(wèn)題二：不同操作可能需要在不同長(zhǎng)度的數(shù)據(jù)塊上以及數(shù)據(jù)包的不同部位進(jìn)行問(wèn)題三：有些操作可能是相互依賴(lài)的。比如，如果數(shù)據(jù)包的TCP檢查和驗(yàn)證失敗，就不應(yīng)當(dāng)對(duì)包進(jìn)行解密操作,ILP面臨的問(wèn)題（續(xù)）,問(wèn)題四：過(guò)分提高整合度可能降低代碼的局部性，增大指令cache的miss率，反而產(chǎn)生不良的后果結(jié)論：ILP很難實(shí)現(xiàn)（問(wèn)題1~問(wèn)題3）ILP可能性能不佳（問(wèn)題4）ILP可能完全沒(méi)有必要（若包數(shù)據(jù)需要被處理幾次，則數(shù)據(jù)很可能駐留在cac

39、he中）目前只有檢查和計(jì)算被整合在數(shù)據(jù)拷貝過(guò)程中,5.8 擴(kuò)展到數(shù)據(jù)操作之外,消除數(shù)據(jù)拷貝和整合數(shù)據(jù)操作，其技術(shù)共同點(diǎn)都是避免冗余的讀/寫(xiě)操作，以減少對(duì)內(nèi)存總線(xiàn)的壓力還有哪些因素會(huì)影響內(nèi)存總線(xiàn)的使用呢？Cache的使用效率DMA或PIO的選擇,5.8.1 有效使用 I-cache,處理器包含一個(gè)或多個(gè)數(shù)據(jù)cache，以及一個(gè)或多個(gè)指令cache：一般而言，包數(shù)據(jù)幾乎不能從 d-cache 獲得好處處理數(shù)據(jù)包需要的狀態(tài)

40、可以從d-cache 獲益處理數(shù)據(jù)包的程序代碼可以從 I-cache 獲益代碼和狀態(tài)都可能競(jìng)爭(zhēng)內(nèi)存帶寬，相比而言，代碼對(duì)內(nèi)存帶寬的競(jìng)爭(zhēng)更嚴(yán)重：處理一個(gè)包需要的狀態(tài)一般較小，比如一個(gè)連接表項(xiàng)協(xié)議棧處理的代碼大得多，而I-cache的容量一般很小高效地利用I-cache是提高性能的一個(gè)關(guān)鍵,I-Cache的實(shí)現(xiàn)特點(diǎn)（1）,大多數(shù)處理器使用直接映射的I-cache：內(nèi)存地址的低位比特用來(lái)檢索I-cache條目如果高位比特匹配，

41、直接從I-cache返回內(nèi)容若不匹配，進(jìn)行一個(gè)主存訪問(wèn)，用新的內(nèi)容替換原來(lái)的條目問(wèn)題：被映射到I-cache同一位置的代碼會(huì)被輪流替換出去，即使它們都是經(jīng)常使用的代碼。,I-Cache的實(shí)現(xiàn)特點(diǎn)（2）,每一條I-cache包含多條指令：當(dāng)取一條指令時(shí)，同一個(gè)代碼塊中的全部指令都會(huì)被讀入（基于空間局部性假設(shè)做的優(yōu)化）問(wèn)題：不常用的代碼會(huì)被讀入I-cache，如果它與常用代碼在一個(gè)塊中。,舉例,許多網(wǎng)絡(luò)代碼包含錯(cuò)誤檢查，比如：

42、if error E do X, else do Z雖然 Z 幾乎從不被執(zhí)行，但是編譯器通常會(huì)將 Z 的代碼緊跟在 X 的后面如果 X 和 Z 位于同一個(gè)指令塊中，取經(jīng)常使用的代碼 X，會(huì)把不經(jīng)常使用的代碼 Z 也取進(jìn)來(lái)，浪費(fèi)了內(nèi)存帶寬和cache空間,問(wèn)題與解決方案,指令cache沒(méi)有很好地反映時(shí)間局部性：經(jīng)常使用的代碼不一定在cache中：由一個(gè)不完美的映射函數(shù)引起不常使用的代碼可能被經(jīng)常調(diào)入cache：由cach

43、e對(duì)空間局部性的優(yōu)化引起如何解決以上問(wèn)題？重新組織代碼，將經(jīng)常使用的代碼連續(xù)放置,重新組織代碼,如果工作集超過(guò)了I-cache的大小，第一個(gè)問(wèn)題仍會(huì)出現(xiàn)，但會(huì)減少，而第二個(gè)問(wèn)題能夠得到很大程度的緩解代碼布局的基本思想：通過(guò)優(yōu)化代碼在內(nèi)存中的位置，使得經(jīng)常使用的代碼駐留在I-cache中,新的問(wèn)題,處理包的協(xié)議代碼肯定無(wú)法全部裝入指令cache：I-cache的容量非常有限計(jì)算機(jī)上的所有程序都要競(jìng)爭(zhēng)I-cache問(wèn)題：如果

44、每處理一個(gè)包，就要將全部的協(xié)議代碼裝入I-cache一次，效率太低！！拷貝數(shù)據(jù)包的開(kāi)銷(xiāo)和將代碼裝入I-cache的開(kāi)銷(xiāo)比起來(lái)，簡(jiǎn)直就是微不足道！,局部性驅(qū)動(dòng)的協(xié)議層處理,基本思想（若每一層協(xié)議代碼可以裝入I-cache）每個(gè)協(xié)議層一次處理多個(gè)包，分?jǐn)傃b載 I-cache的開(kāi)銷(xiāo)每一批處理的包數(shù)量越多，I-cache的使用越高效具體實(shí)現(xiàn)時(shí)，應(yīng)能動(dòng)態(tài)調(diào)整批處理的大小,軟件工程方面的考慮,代碼重新組織可以讓編譯器來(lái)做：程序員對(duì)不常使用

45、的代碼分支進(jìn)行標(biāo)注，由編譯器為I-cache重新組織代碼。局部性驅(qū)動(dòng)的協(xié)議層處理需修改層間通信方法：如果協(xié)議代碼使用一個(gè)過(guò)程調(diào)用將數(shù)據(jù)包傳遞給上（下）一層，則代碼修改為將數(shù)據(jù)包加入上（下）一層的一個(gè)包隊(duì)列中當(dāng)一個(gè)協(xié)議層被調(diào)用時(shí)，從自己的讀隊(duì)列中取數(shù)據(jù)包處理，直至隊(duì)列取空當(dāng)包緩沖區(qū)可以在不同層重用時(shí)，該策略工作很好,5.8.2 DMA還是PIO？,PIO：需要CPU參與，完成內(nèi)存-外設(shè)之間的數(shù)據(jù)傳輸需要使用內(nèi)存總線(xiàn)兩次DMA

46、:不需要CPU參與，且內(nèi)存-外設(shè)之間的數(shù)據(jù)傳輸只需要使用內(nèi)存總線(xiàn)一次DMA一定好于PIO 嗎？？,DMA or PIO？,如果將數(shù)據(jù)傳輸和數(shù)據(jù)處理結(jié)合起來(lái)看，DMA的優(yōu)勢(shì)并不是那么明顯！PIO需要CPU參與，內(nèi)存-外設(shè)的數(shù)據(jù)傳輸需要使用兩次內(nèi)存總線(xiàn)，但易于整合其它功能（如檢查和計(jì)算）DMA不需要CPU參與，內(nèi)存-外設(shè)的數(shù)據(jù)傳輸僅使用內(nèi)存總線(xiàn)一次，但不易于整合其它功能（如CPU需要讀入數(shù)據(jù)計(jì)算檢查和）,DMA和PIO都要關(guān)注d-

47、cache,PIO 和 DMA 都存在 d-Cache 失效的問(wèn)題：當(dāng)使用 PIO 或 DMA 時(shí)，數(shù)據(jù)都會(huì)進(jìn)入 d-cache如果數(shù)據(jù)馬上被處理，d-cache的使用很高效如果數(shù)據(jù)到來(lái)很久后才被使用，則是對(duì)d-cache的一種浪費(fèi)，并且會(huì)降低cache命中率使用DMA還是PIO，應(yīng)視具體情況而定,5.9 小結(jié),本章以web應(yīng)用為例介紹了優(yōu)化內(nèi)存和總線(xiàn)帶寬使用的技術(shù)，主要包括：使用適配器內(nèi)存消除 copy 4 使用fbu

48、fs消除copy 3使用mmap消除copy 2使用IO-Lite、sendfile消除 copy2 和copy 3整合拷貝和檢查和計(jì)算到一個(gè)循環(huán)中通過(guò)代碼重新布局、局部性驅(qū)動(dòng)的協(xié)議層處理優(yōu)化I-cache的使用,本章使用的技術(shù)以及主要的原則,P1原則的運(yùn)用,本章反復(fù)運(yùn)用原則P1（避免顯而易見(jiàn)的浪費(fèi)）來(lái)消除不必要的讀、寫(xiě)操作運(yùn)用這個(gè)原則的困難在于，如果不把視野盡可能放寬到整個(gè)系統(tǒng)，浪費(fèi)并不是顯而易見(jiàn)的運(yùn)用P1原則要求對(duì)整個(gè)系

49、統(tǒng)有一個(gè)概要的了解，使用簡(jiǎn)單的模型（硬件、體系結(jié)構(gòu)、操作系統(tǒng)、協(xié)議）就可以做到這一點(diǎn)系統(tǒng)技術(shù)的復(fù)雜性并不在于深度，而在于廣度 （涉及多領(lǐng)域的知識(shí)）,,作業(yè),閱讀論文“Network Stack Specialization for Performance”，介紹其中Sandstorm web server的要點(diǎn)。包括以下內(nèi)容：該論文做了什么為什么做：背景，現(xiàn)狀怎么做：主要思路，關(guān)鍵措施評(píng)估方法與效果：實(shí)驗(yàn)怎么做，與誰(shuí)比，效果怎