第二部分端節點算法學第二部分端節點算法學端節點算法學端節點算法學：建立高速服務器的一組系統性技術，是網絡算法學在端節點（尤其是服務器）上的運用節點間通信已成為大數據分析、深度學習等應用的主要瓶頸之一隨著網絡功能虛擬化的提出，將來數據中心絕大部分的網絡設備都會在通用服務器上實現端節點算法學研究如何減少以下開銷：數據拷貝（chapter5）控制轉移（chapter6）定時器（chapter7）解復用（chapter8）其它一般性協議處理任務（chapter9）端節點算法學端節點算法學：第五章拷貝數據第五章拷貝數據消除不必要的拷貝（P1）網絡報文在收發和處理的過程中，通常會被拷貝多次計算機中的數據拷貝消耗兩個寶貴的資源：內存帶寬：如果處理一個報文涉及k次拷貝，系統吞吐量可能降至1/k內存：如果一個報文在內存中被保存k份，有效內存容量降至1/k本章關注如何消除不必要的拷貝：一個拷貝如果不是由硬件要求的，該拷貝是不必要的本章還將討論其它影響內存使用效率的操作消除不必要的拷貝（P1）網絡報文在收發和處理的過程中，通常會5.1為什么要拷貝數據應用場景：用戶向web服務器請求一個靜態文件服務器從磁盤讀出文件，發送到網絡上兩個內核子系統：文件子系統網絡子系統5.1為什么要拷貝數據應用場景：一個簡單的故事直觀上，這是一個簡單的故事：web應用程序通過一個系統調用（讀文件），將文件從磁盤讀入到它的緩沖區中構造一個HTTP響應頭，通過一個系統調用（寫套接字），將響應頭和緩沖區內容交給網絡子系統網絡子系統將數據劃分成適當大小的塊，加上各層協議頭，交給網絡驅動程序一個簡單的故事直觀上，這是一個簡單的故事：一個真實的故事Copy1：硬盤

文件緩沖區（內核空間）Copy2：文件緩沖區

應用緩沖區（用戶空間）Copy3：應用緩沖區

套接字緩沖區（內核空間）Copy4：套接字緩沖區

網卡TCP程序還需要掃描一遍數據，計算TCP檢查和一個真實的故事Copy1：資源消耗情況拷貝和TCP檢查和計算：每個字需要穿過內存總線7~9次！不同內存區域之間的拷貝（copy2，copy3）：每個字都要通過內存總線讀一次和寫一次計算TCP檢查和：每個字都要通過內存總線讀一次涉及外設的拷貝（copy1，copy4）：如果由CPU做拷貝（PIO）：每個字都要通過內存總線讀一次和寫一次如果由設備做拷貝（DMA）：每個字只需通過內存總線讀一次或寫一次涉及外設的拷貝都需要消耗I/O總線帶寬資源消耗情況拷貝和TCP檢查和計算：每個字需要穿過內存總線7對服務器吞吐量的影響在上面的例子中：Web服務器吞吐量不超過T/7，T為內存速度和內存總線速度中的較小值有效的文件緩沖區大小僅為總容量的1/3多余的拷貝在兩個方面損害了服務器的性能：由于使用了過多的總線和內存帶寬，服務器的運行速度遠遠低于總線速度由于使用了過多的內存，服務器不得不更多地從磁盤而不是主存讀文件如果請求動態內容，還要增加一次拷貝（CGI程序web服務器）對服務器吞吐量的影響在上面的例子中：請求動態內容Step6：CGI程序將構造好的網頁文件，通過進程間通信機制傳給web服務器程序，涉及一次拷貝請求動態內容Step6：CGI程序將構造好的網頁文件，通5.2消除copy4為什么需要copy4？簡單的解釋：適配器內存和內核存儲空間不在同一個硬件上但是，這個理由并不充分！5.2消除copy4為什么需要copy4？消除Copy4在一個內存映射的體系結構中，設備寄存器被映射到一塊內存區域，CPU通過讀寫這塊內存區域與設備通信理論上，內存可以位于總線上的任何地方，包括在適配器中消除copy4的解決方案：利用網絡適配器中已有的存儲空間（P4，利用系統組件），以及內核存儲空間放置的自由度（P13，利用自由度），將套接字緩沖區放在網絡適配器中應用緩沖區的內容直接拷貝到網絡適配器的內存中消除Copy4在一個內存映射的體系結構中，如何計算TCP檢查和？如何計算TCP檢查和？如何計算檢查和？Witless方法（P2c，共享開銷）：CPU執行拷貝，當讀入每個字時，捎帶計算檢查和致命的問題：接收的時候，當發現檢查和出錯時數據包已被寫入應用緩沖區，與TCP語義不符（所以該方法從未被實施）Afterburner適配器（TCPoffloadingengine）：數據傳輸由網卡通過DMA完成，檢查和也由網卡計算TCP連接的管理（建立、關閉等）仍由主CPU完成，僅將建立好的TCP連接移交給網絡適配器問題：網絡適配器需要很大的內存空間和較強的處理器來支持大量的TCP連接，網卡成本可能較高如何計算檢查和？Witless方法（P2c，共享開銷）：5.3消除Copy3為什么需要copy3？應用和內核使用不同的虛擬地址空間（不是必要的）SocketAPI使用拷貝語義，應用和內核之間需通過拷貝解除耦合（必要的）如果拷貝不能避免，那么能否減小拷貝的開銷呢？5.3消除Copy3為什么需要copy3？寫時拷貝（copy-on-write）當應用程序對內核執行一個寫時拷貝時，OS將內核緩沖區映射到應用緩沖區的物理內存頁上當應用程序試圖修改其緩沖區時，內核進行真正的拷貝有些操作系統提供寫時拷貝，很多情況下可以避免真正的拷貝寫時拷貝（copy-on-write）當應用程序對內核執行一寫時拷貝的實現舉例：假定進程P1的虛擬頁X映射到物理頁L上，需要復制X的內容到進程P2的虛擬頁Y當P1對X進行寫時拷貝時：內核修改P2的頁表，令Y指向物理頁L將X表項的COW保護位置位當P1試圖寫頁X時：硬件讀X的COW位，發現置位，產生一個異常操作系統將物理頁L拷貝到物理頁L’，清除X的COW位，令X指向L’，Y繼續指向L

寫時拷貝的實現舉例：寫時拷貝的實現（續）對于不提供寫時拷貝功能的操作系統（如UNIX和Windows），也可以基于虛擬內存實現類似的功能：可以通過修改頁表避免物理拷貝需要找到一種替代COW位的保護機制寫時拷貝的實現（續）對于不提供寫時拷貝功能的操作系統（如UN5.4優化頁面重映射對頁面重映射過于簡單的看法：只需修改P2的頁表（一次寫操作），令VP8指向存放包的物理頁，所有工作就結束了

（X）5.4優化頁面重映射對頁面重映射過于簡單的看法：（X）頁面重映射的開銷修改多級頁表：實際映射可能要求修改多級頁表，當頁表不在內存中時要調入，并修改目錄頁要求鎖操作：修改頁表前要請求鎖，修改后要釋放鎖刷新TLB：新的地址映射寫入頁表時，相關TLB表項要清除或修正在目標域中分配虛擬內存：系統要在目標進程中找到一個空閑的頁表表項鎖住物理頁：為防止頁被換出，必須鎖住物理頁以上開銷在多處理器系統中會被放大頁面重映射雖然只需常數時間，但這個常數因子非常大結論：如果只是簡單地使用頁表重映射來避免拷貝，結果可能不像預期的那么好頁面重映射的開銷修改多級頁表：在目標域中分配虛擬內存：結論：Fbufs（fastbuffers）基本觀察：如果一個應用正在發送大量的數據包，那么一個包緩沖區可能會被重用多次方法一：提前分配好需要的包緩沖區，并計算好所有的頁面映射信息（P2a），發送時重復使用這些包緩沖區方法二：數據傳輸開始時分配包緩沖區并計算頁面映射，然后將其緩存起來（P11a），消除后續包的頁面映射開銷基本思想：映射一次，重復使用Fbufs（fastbuffers）基本觀察：為應用分配一組固定的物理頁為避免內核空間和用戶空間之間的拷貝，將一組物理頁P1、P2、……、Pk同時映射給內核和應用來使用數據包經過的一系列處理程序構成一個有序的安全域序列，定義為一條路徑為隔離不同的應用，為每一條路徑預留固定的一組物理頁，數據包到達時立即確定其所屬的路徑（提前解復用）為應用分配一組固定的物理頁為避免內核空間和用戶空間之間的拷貝在路徑上傳遞包緩沖區描述符對于每條路徑，適配器有一個空閑緩沖區鏈表：適配器把數據包寫入一個空閑緩沖區，將緩沖區描述符傳給接收路徑上的下一個進程最后一個進程將用完的緩沖區交還給第一個進程，緩沖區重新回到空閑緩沖區鏈表在路徑上傳遞包緩沖區描述符對于每條路徑，適配器有一個空閑緩沖實現單向路徑有序的安全域序列是一條單向路徑：規定第一個進程是writer，其余進程是reader（為了提供一定的保護級別）給第一個進程的頁表表項設置寫允許位，給其它進程的頁表表項設置只讀位實現單向路徑有序的安全域序列是一條單向路徑：映射到同一個物理頁的虛擬頁號應相同在進程間傳遞緩沖區描述符的問題：理論上，各個進程映射到同一個物理頁上的虛擬頁號可能不同解決方法：規定：映射到同一個物理頁的虛擬頁號必須相同實現：所有進程的虛擬內存中一定數量的起始頁預留為fbuf頁映射到同一個物理頁的虛擬頁號應相同在進程間傳遞緩沖區描述符的收包處理過程P1進程：從freefbufs隊列取一個緩沖區描述符將數據包寫入緩沖區將緩沖區描述符寫入writtenfbufs隊列P2進程從writtenfbufs隊列取緩沖區描述符從相應緩沖區讀數據將緩沖區描述符寫回freefbufs隊列收包處理過程P1進程：如何添加包頭？在發送路徑上，每一個安全域都要給數據包加上一個包頭然而，為了實現保護，每條路徑只允許一個writer，其余為reader問題：怎么允許其它安全域添加包頭呢？如何添加包頭？在發送路徑上，每一個安全域都要給數據包加上一個定義數據包為聚合數據結構將數據包定義為一個帶有指針的聚合數據結構，每個指針指向一個fbuf給數據包添加包頭，就是將一個fbuf添加到聚合數據結構中定義數據包為聚合數據結構將數據包定義為一個帶有指針的聚合數據Fbufs總結Fbufs運用了虛擬內存映射的思想，通過在大量數據包之間分攤頁面映射開銷而做得更高效：包緩沖區映射一次，重復使用很多次消除了一般情形中的頁表更新有人擴展了Fbufs思想，并實現在SunSolaris操作系統中IntelDPDK也運用了“一次映射，重復使用”的思想Fbufs總結Fbufs運用了虛擬內存映射的思想，通過在大量應用如何使用Fbufs？大量已有的應用軟件是根據拷貝語義的socketAPI寫的:應用執行了write()系統調用后，就可以重用包緩沖區，甚至釋放包緩沖區了采用fbufs后：在包緩沖區被其它進程使用完之前，應用不允許寫或釋放包緩沖區應用如何使用Fbufs？大量已有的應用軟件是根據拷貝語義的s解決方案：修改應用API解決方法：API不再保持拷貝語義應用在寫緩沖區之前必須進行判斷安全的實現方法：當一個fbuf從應用傳遞到內核后，內核翻轉一個寫允許比特，歸還fbuf時再重新設置該位若應用在不允許寫的情況下做寫操作，會產生一個異常，提示出錯，但不影響其它進程解決方案：修改應用API解決方法：已有的網絡應用軟件必須重寫嗎？方法一：給已有的API增加新的系統調用，要求高性能的應用使用新的系統調用進行重寫方法二：用新的擴展實現一個公共的I/O庫，鏈接到該庫的應用不需要修改，就可以得到性能提升

實踐表明，將應用移植到類fbuf的API，對應用所做的修改不大，且是局部的，因此fbufs方案是可行的已有的網絡應用軟件必須重寫嗎？方法一：5.5使用RDMA避免拷貝在web服務器的例子中：Web服務器接收請求，將文件傳輸到網絡上Web服務器作為接收端并不需要保存請求消息現考慮在兩個計算機之間傳輸一個大文件，接收端需要保存收到的數據包為減少拷貝，接收端采用以下方式之一收包：采用fbufs采用TOE網卡5.5使用RDMA避免拷貝在web服務器的例子中：方法一：采用fbufs收包包到達網卡后，被拷貝到一個包緩沖區中包緩沖區描述符在路徑上傳遞，各安全域處理包應用程序將數據拷貝到應用緩沖區，釋放包緩沖區（這里需要一次拷貝）方法一：采用fbufs收包包到達網卡后，被拷貝到一個包緩沖區方法二：采用TOE網卡收包包到達網卡后，被送入套接字緩沖區進行協議處理和重組DMA控制器將數據送入應用緩沖區，向CPU發出中斷驅動程序通知應用接收數據應用拷貝數據到文件緩沖區，將應用緩沖區歸還給網卡（這里需要一次拷貝）方法二：采用TOE網卡收包包到達網卡后，被送入套接字緩沖區進直接內存訪問（DMA）在上述兩種方法中，CPU要參與數據傳輸，且數據到達目的計算機的內存后還要拷貝一次我們知道，使用DMA在外設和內存之間傳輸數據，不需要CPU的參與：CPU設置DMA（給出數據的存放地址、長度等）DMA控制器完成數據傳輸DMA控制器通過中斷通知CPU傳輸完成受DMA的啟發，能否在兩臺計算機的內存之間直接傳輸數據，而不需要CPU參與？直接內存訪問（DMA）在上述兩種方法中，CPU要參與數據傳輸遠程直接內存訪問（RDMA）RDMA的愿景：數據在兩臺計算機的主存之間直接傳輸，不需要CPU參與到數據傳輸的過程中兩個網絡適配器協作地從一個主存讀數據，然后寫入另一個主存遠程直接內存訪問（RDMA）RDMA的愿景：RDMA需要解決的問題除了需要網卡執行協議處理外，RDMA還需解決兩個問題：接收端適配器如何知道應將數據放在哪兒？（不能求助CPU）如何保證安全？（發送進程不能隨意寫目標終端的內存）RDMA需要解決的問題除了需要網卡執行協議處理外，RDMA還VAX集群的RDMARDMA在VAX集群中已經被使用：VAX系統的核心是一個140Mb/s的網絡（稱為ComputerInterconnect，CL），使用一個以太網風格的協議用戶可以將許多VAX計算機和網絡硬盤連接到CLRDMA的需求背景：在遠程硬盤和VAX機的內存之間有效傳輸大量數據要求包含文件數據的包在進入目的適配器之后，直接到達它的存放位置VAX集群的RDMARDMA在VAX集群中已經被使用：接收端適配器應將數據放在哪兒？接收端應用鎖住一些物理頁，用作文件傳輸的目標存儲區域（其呈現出來的邏輯視圖是由地址連續的虛擬頁組成的一個緩沖區），緩沖區ID被發送給發送端應用發送端應用將緩沖區ID及包存放的偏移量，隨同數據包一起發送到接收端（P10，傳遞線索）接收端適配器根據緩沖區ID和偏移量，將數據包內容存放到指定的位置（一步到位）接收端適配器應將數據放在哪兒？接收端應用鎖住一些物理頁，用作如何保證目標存儲區域的安全？允許將一個攜帶緩沖區ID的網絡包直接寫入內存，是一個明顯的安全隱患為降低安全風險，緩沖區ID中包含一個難以猜測的隨機串（防止偽造）VAX集群只在本集群內部可信的計算機之間使用RDMA傳遞數據如何保證目標存儲區域的安全？允許將一個攜帶緩沖區ID的網絡包RDMA的應用存儲區域網（StorageAreaNetwork，SAN）：一種后端網絡，將大量計算機和網絡硬盤連接在一起目前有好幾種這樣的技術，都使用了RDMA的思想，如FiberChannel（FC）、iSCSI、Infiniband等數據中心支持高性能分布式計算：大數據分析（MapReduce框架）深度學習（TensorFlow、Caffe等）RDMA的應用存儲區域網（StorageAreaNetw5.6把避免拷貝技術擴展到文件系統為提高響應速度，Copy1是必要的考慮消除copy25.6把避免拷貝技術擴展到文件系統為提高響應速度，Copy5.6.1共享內存方法類UNIX操作系統提供一個系統調用mmap()，允許應用（如web服務器）將一個文件映射到自己的虛擬地址空間。概念上，當一個文件被映射到一個應用的地址空間，這個應用就好像在自己的內存中緩存了這份文件。當然，這個緩存的文件只是一組映射。如果Web程序將文件映射到自己的地址空間，則它和文件cache訪問的是同一組物理頁（免除了拷貝）。5.6.1共享內存方法類UNIX操作系統提供一個系統調用舉例：FlashWeb服務器Web應用程序將經常用到的文件映射到自己的內存空間受到可分配給文件頁的物理頁數量及頁表映射的限制，FlashWeb服務器只能緩存和映射最近常用的文件事實上，FlashWeb服務器只是緩存了一些文件分片（通常是文件的頭幾個分片），并使用LRU策略將最近一段時間未用的文件unmap舉例：FlashWeb服務器Web應用程序將經常用到的文件FlashWeb尚未解決的問題FlashWeb不能避免web服務器與CGI進程之間的拷貝文件緩存只能緩存靜態內容，動態網頁要由CGI程序生成CGI程序生成的動態內容通過UNIX管道傳給web服務器；典型地，管道要在兩個地址空間之間拷貝內容到目前為止，我們的方案都沒有涉及TCP檢查和一個被訪問多次的文件，文件分片都相同，但TCP檢查和未被緩存FlashWeb尚未解決的問題FlashWeb不能避免由fbufs和mmap()想到的問題fbufs可以消除copy3mmap()可以消除copy2Q：能否將fbufs和mmap()結合起來使用，同時消除copy2和copy3？由fbufs和mmap()想到的問題fbufs可以消可以結合fbufs和mmap嗎？如果采用fbufs：所有進程的虛擬內存中一定數量的起始頁預留為fbuf頁應用進程的應用緩沖區不能使用這些頁如果應用將文件映射到其虛擬地址空間的一個緩沖區：這個緩沖區不能用fbuf發送，必須要有一次物理拷貝！當用mmap消除copy2時，copy3不能避免！可以結合fbufs和mmap嗎？如果采用fbufs：5.6.2IO-LiteIO-Lite將fbufs推廣至包含文件系統，從而不必使用mmapIO-Lite可以一攬子解決前面所有的問題：同時消除copy2和copy3消除CGI程序和web服務器之間的拷貝緩存傳送過的數據塊的檢查和5.6.2IO-LiteIO-Lite將fbufsIO-Lite的主要思想IO-Lite借用了fbufs的主要思想：為同一條路徑上的進程映射相同的物理頁，實現只讀共享推遲創建路徑的緩沖區使用緩沖區聚合以允許添加包頭IO-Lite的主要思想IO-Lite借用了fbufsIO-Lite響應Get請求IO-Lite響應Get請求IO-Lite響應Get請求的步驟當文件第一次從磁盤讀入文件系統的高速緩存時，文件頁被保存為IO-Litebuffer當應用通過一個系統調用讀文件時，創建一個緩沖區聚合體，指針指向IO-Litebuffer當應用發送文件給TCP時，網絡子系統得到一個指向相同IO-Lite頁的指針應用將常用文件的HTTP響應頭維護在一個高速緩存中IO-Lite給每個緩沖區分配一個編號，TCP模塊維護一個以緩沖區編號為索引的檢查和高速緩存<緩沖區ID，檢查和>IO-Lite響應Get請求的步驟當文件第一次從磁盤讀實現零拷貝的管道IO-Lite也可以用來實現一個消除了拷貝的改良型管道程序（傳遞IO-Litebuffer的指針而不是拷貝）將改良后的管道應用到CGI程序和web服務器之間，可以消除冗余的拷貝IO-Lite已經在UNIX中實現了實現零拷貝的管道IO-Lite也可以用來實現一個消除了拷貝的5.6.3使用I/O拼接避免文件系統拷貝I/O拼接的基本思想：引入一個新的系統調用sendfile()，允許內核將讀文件的調用和向網絡發送消息的調用合并文件到socket傳輸的傳統方法需兩次系統調用： read(file,tem_buf,len); write(socket,tmp_buf,len);使用sendfile()傳輸文件到socket： sendfile(socket,file,len);5.6.3使用I/O拼接避免文件系統拷貝I/O拼接的基本內核2.1版本的sendfile實現調用sendfile()時：文件數據先被拷貝到內核中的文件緩沖區（copy1）然后從文件緩沖區拷貝到內核中的socket緩沖區（合并copy2和copy3）最后從socket緩沖區拷貝到適配器（copy4）與read/write方式相比，減少了一次拷貝內核2.1版本的sendfile實現調用sendfile()內核版本2.4之后的sendfile實現調用sendfile()時：文件數據先被拷貝到內核中的文件緩沖區（copy1）將記錄數據位置和長度的信息保存到socket緩沖區數據通過DMA通道直接發送到適配器（copy4）消除了copy2和copy3基于sendfile的機制不能推廣到與CGI程序通信Sendfile()已用于Apache、Nginx、Lighttpd等web服務器中內核版本2.4之后的sendfile實現調用sendfile5.8擴展到數據操作之外消除數據拷貝是為了避免冗余的數據讀/寫操作，以減少對內存和內存總線的壓力除拷貝外，對內存總線使用效率影響較大的因素還有Cache5.8擴展到數據操作之外消除數據拷貝是為了避免冗余的數據5.8.1有效使用I-cache處理器包含一個或多個數據cache（d-cache），以及一個或多個指令cache（I-cache）：一般而言，包數據幾乎不能從d-cache獲得好處處理數據包需要的狀態可以從d-cache獲益處理數據包的程序代碼可以從I-cache獲益數據、狀態、代碼都可能競爭內存帶寬，相比而言，代碼對內存帶寬的競爭更嚴重：以太網上最大的數據包為1.5KB處理一個包需要的狀態一般較小，比如一個連接表項1995年NetBSDTCP協議棧代碼34KB（不包括應用協議代碼）I-cache容量很小，數據包處理代碼不可能都在I-cache中！5.8.1有效使用I-cache處理器包含一個或多個數I-Cache的實現特點（1）大多數處理器使用直接映射的I-cache：內存地址的低位比特用來檢索I-cache條目如果高位比特匹配，直接從I-cache返回內容若不匹配，進行一個內存訪問，用新的內容替換原來的條目對于32KB的I-cache，內存地址最低15位相同的指令被映射到cache的同一位置問題一：被映射到I-cache同一位置的代碼會被輪流替換出去，即使它們都是經常使用的代碼。I-Cache的實現特點（1）大多數處理器使用直接映射的I-I-Cache的實現特點（2）每一個I-cache條目包含多條指令，可以看成是一個代碼塊：當取一條指令時，同一個代碼塊中的全部指令都會被讀入（基于空間局部性假設做的優化）問題二：不常用的代碼會被讀入I-cache，如果它與常用代碼在一個塊中。I-Cache的實現特點（2）每一個I-cache條目包含多舉例許多網絡代碼包含錯誤檢查，比如： ifconditionTdoX,elsedoZ雖然Z幾乎從不被執行，但是編譯器通常會將Z的代碼緊跟在X的后面如果X和Z位于同一個指令塊中，取經常使用的代碼X，會把不經常使用的代碼Z也取進來，浪費了內存帶寬和cache空間舉例許多網絡代碼包含錯誤檢查，比如：問題與解決方案以上兩個結果和我們對于cache的一般預期不同：經常使用的代碼不一定在cache中：由一個不完美的映射函數引起不常使用的代碼可能被經常調入cache：由cache對空間局部性的優化引起如何解決以上問題？重新組織代碼，將經常使用的代碼連續放置問題與解決方案以上兩個結果和我們對于cache的一般預期不同重新組織代碼如果工作集超過了I-cache的大小，第一個問題仍會出現，但會減少，而第二個問題能夠得到很大程度的緩解代碼布局的基本思想：通過優化代碼在內存中的位置，減少代碼的換入換出重新組織代碼如果工作集超過了I-cache的大小，第一個問題新的問題處理包的協議代碼肯