基于超低延遲SSD 的頁交換機制關鍵技術

王紫芮 蔣德鈞

（中國科學院計算技術研究所先進計算機系統研究中心 北京 100190）

（處理器芯片全國重點實驗室（中國科學院計算技術研究所） 北京 100190）

（中國科學院大學計算機科學與技術學院 北京 100049）

隨著內存密集型應用的廣泛興起，日益增長的數據量和對高性能應用的追求使得對內存的需求迅速增長.然而，隨著摩爾定律的放緩，內存難以獲得更高的存儲密度和更低的顆粒價格[1].因此，如何有效地進行內存擴展成為急需解決的問題.

頁交換機制是用于內存擴展的經典技術.當內存不足時，該機制通過將較少使用的內存頁面保存在存儲設備，從而達到擴展內存的目的.當應用需要訪問不在內存中的頁面時，則通過觸發缺頁異常，將在存儲設備的頁面讀入內存中的指定地址，以確保應用的正常運行.頁交換機制由內核提供，且對應用程序透明.

在過去，頁交換機制的性能受到慢速設備讀寫的限制.目前廣泛應用的固態硬盤（solid state drive，SSD）具有容量大、帶寬高的特性，讀寫延遲相比磁盤的10 ms 降低到100 μs[2].近年來，隨著3D XPoint[3]和Z-NAND[4]等非易失性存儲器（non-volatile memory，NVM）技術的發展，存儲設備和CPU 的性能差距不斷縮小.如今的超低延遲SSD（ultra-low latency SSD），例如英特爾Optane SSD[5]、三星 Z-SSD[6]等，可以提供低于10 μs 的延遲和高于6 GBps 的I/O 帶寬，相比磁盤的讀寫速度提高了1 個量級.因此，使用超低延遲SSD 為頁交換設備，可以更加高效地對數據進行訪問和操作，降低頁交換對應用整體性能的影響.

然而，隨著高速設備的發展，I/O 延遲被降低到微秒級別，設備的讀寫性能不再是限制頁交換性能的瓶頸，反而傳統上被認為是輕量級的內核軟件開銷，愈發不可忽視.頁交換機制較為復雜，涉及到內核的交換邏輯層（頁面回收與缺頁異常處理）以及I/O 棧（多隊列塊層與設備驅動層）.交換邏輯層需要完成對交換頁面的選擇并對交換緩存進行處理，而I/O 棧需要進行讀寫請求的提交和完成工作.由于目前沒有工作對現有的Linux 頁交換機制進行分析，本文希望通過實驗和分析，可以為設計高效的頁交換機制提供設計指導.

針對超低延遲SSD，學術界利用其低延遲的特點進行了I/O 棧設計，例如AIOS[7]，FlashShare[8]等.這部分工作通過降低內核塊層開銷，提升整體性能.然而，盡管現有頁交換機制和文件系統共享一部分I/O 棧，文獻[7-8]工作集中于對文件頁進行I/O 優化，而忽視頁交換時匿名頁的讀寫特征以及內核時間開銷情況，導致無法有效降低頁交換機制的軟件開銷.據我們所知，本文是利用超低延遲SSD 對頁交換機制進行優化的工作.

本文首先通過對Linux 頁交換機制源碼進行分析，分析評估頁交換內核路徑上各操作的影響.測評從頁換入和頁換出2 方面對Linux 頁交換機制進行分析，探究頁交換機制在使用超低延遲SSD 時的軟件層面的開銷特征，對頁交換過程中交換邏輯層、多隊列塊層和驅動層的延遲進行比較.基于當前Linux頁交換機制的性能特征，分析影響頁交換機制性能的因素.測試結果表明，Linux 的I/O 棧軟件開銷可達到內核總時間開銷的64%.主要原因在于發送請求時存在隊頭阻塞（head-of-line blocking）問題、I/O 合并和調度開銷，以及內核返回路徑上的中斷處理和直接內存回收開銷.

基于測試實驗結果，本文設計了基于超低延遲SSD 的頁交換機制Ultraswap.Ultraswap 在Linux I/O棧的基礎上增加了對輪詢請求的處理，并通過直接調用NVMe（non-volatile memory express）驅動的方式，降低了I/O 合并與調度開銷，從而實現了輕量級的I/O 棧.利用Ultraswap 的I/O 棧，本文對內核頁交換機制的換入與換出路徑進一步優化.在缺頁異常方面，Ultraswap 為每個CPU 分配多個請求隊列，從而混合使用輪詢和中斷請求，分離關鍵頁面、預取頁面及回收頁面，解決請求發送時的隊頭阻塞問題；在內存回收方面，考慮到處理缺頁異常的關鍵路徑上可能觸發直接內存回收，影響缺頁異常的返回，本文將直接內存回收的過程進行遷移，降低關鍵路徑上的時間開銷.

本文的主要貢獻包括4 個方面：

1） 基于超低延遲SSD 進行Linux 頁交換機制的分析和性能測評，分析內核各操作的時間占比，歸納影響頁交換機制的主要原因；

2） 設計和實現基于超低延遲SSD 的頁交換機制Ultraswap，實現輕量級的內核I/O 棧，降低頁交換的軟件開銷；

3） 提出內核頁交換機制的換入與換出路徑優化方法，優化頁交換關鍵路徑，降低內核軟件延遲；

4） 結果表明Ultraswap 在應用測試場景下相比Linux 頁交換機制能夠提升19%的平均性能，與理想化情況相比，Ultraswap 能夠將Linux 頁交換機制與理想化情況的性能差距減少95%.

1 相關工作

本節主要介紹目前業界對于頁交換機制和超低延遲SSD 的相關工作.在頁交換機制部分，主要介紹學術界在使用不同存儲設備，例如遠程直接內存訪問（remote direct memory access，RDMA）[9]、硬盤的情況下，針對頁交換機制的軟件層開銷進行的優化工作，包括預取算法、I/O 棧優化等；在超低延遲SSD部分，將介紹部分超低延遲SSD 的性能參數，以及基于超低延遲SSD 進行的內核軟件優化工作.

1.1 頁交換機制

為了滿足用戶的需求，或者滿足內存密集型應用程序的需求，內核會將較少使用的內存頁面換出到存儲設備，這相當于提供更多的內存，這種機制稱為頁交換機制.當內存不足時，內核會掃描頁面鏈表，選擇較少使用的匿名頁面，將其寫到存儲設備上的交換分區.當需要使用該頁面時，觸發缺頁異常，根據換出時的信息記錄，發送讀請求將該頁面從存儲設備讀入內存.

在使用不同存儲設備的情況下，頁交換機制的上層軟件交換邏輯（例如頁面回收算法、頁面預取算法）相同，而讀寫請求在經過多隊列塊層之后會通過不同的驅動發送到設備，例如發送到NVMe SSD 上的讀寫請求需要使用NVMe 驅動接口函數，而發送到遠端內存的讀寫請求使用RDMA 接口函數.根據存儲設備的不同，本文將使用硬盤作為交換分區的頁交換機制稱為本地頁交換機制，使用遠端內存作為交換分區的頁交換機制稱為遠端頁交換機制.

1）本地頁交換機制.頁交換機制已經被研究了很多年.與磁盤相比，SSD 的性能有極大的提升，基于SSD 的頁交換機制已成為解決內存擴展問題的主流方案.FlashVM[10]利用閃存的特性，對內核的頁交換機制實現整體優化.在頁換入路徑上，利用閃存相對磁盤更低的尋道時間，FlashVM 使用步幅預取以最大限度地減少不需要的頁面內存污染.在頁換出路徑上，FlashVM 以比Linux 更精細的粒度限制頁面回寫速率，從而更好地實現頁面從內存到閃存的擁塞控制.SPAN[11]提出重新構建系統執行分頁和預讀的機制，利用NVM 設備提供的高并行度和高性能，將觸發缺頁異常的關鍵頁面與預取的頁面分開，將預取任務分配給單獨的線程處理，從而降低關鍵路徑上的等待時延.此外，SPAN 提出了一種復雜的算法來預測預取頁面的未來訪問情況，從而減少從NVM設備中預取的無用頁面數量.

2）遠端頁交換機制.在RDMA 網絡和新興硬件的支持下，可以利用集群內的空閑資源，以改善和平衡資源利用率.為了實現內存分解，文獻[12-15]探索了使用遠端內存而不是本地SSD 進行頁交換，但遠端內存的性能通常受到網絡速度和CPU 開銷的限制.Infiniswap[12]是一種專為RDMA 網絡設計的遠端內存分頁系統.Infiniswap 將每臺計算機的交換空間劃分為多個slabs 并將它們分布在多臺機器的遠端內存中，通過負載均衡收集空閑內存供應用程序使用.Fastswap[13]也是為RDMA 網絡設計的遠端內存分頁系統，其通過在關鍵路徑上區分關鍵頁面和預取頁面來防止隊頭阻塞.此外，Fastswap 不采用塊I/O 操作，而是以頁粒度和類似內存（RAM-like）的方式訪問遠端內存.Leap[14]是一種基于RDMA 的在線預取解決方案，可以最大限度地減少關鍵路徑中的遠端內存訪問總數.Canvas[15]是一個重新設計的交換系統，它完全隔離了遠端內存應用程序的交換路徑，允許每個應用程序擁有其專用交換分區、交換緩存、預取程序和 RDMA 帶寬.

基于本地頁交換機制的工作主要利用內核提供的塊層接口，對頁交換過程中的交換邏輯部分，包括預取和頁面回收流程進行優化.基于遠端頁交換機制的工作主要關注于集群內的空閑資源改善和平衡資源利用率.表1 將Ultraswap 與文獻[10-15]所述的工作進行對比，本文利用超低延遲SSD，在較新版本的內核上進行頁交換機制的優化，希望通過分析頁交換過程中交換邏輯層、多隊列塊層和驅動層各部分的延遲情況，進一步降低頁交換機制的軟件開銷，從而提升應用的整體性能.

Table 1 Comparative Analysis of Swapping Mechanism in Related Works表1 頁交換機制相關工作對比

1.2 超低延遲SSD

在過去的幾十年中，各種工作研究了如何采用新的數據存儲技術，包括相變存儲器（phase-change memory，PCM）、自旋轉移扭矩磁性隨機存儲器（spintransfer torque RAM，STT-RAM）和可變電阻式存儲器（resistive RAM，ReRAM）等，以建立快速的非易失性存儲器.

隨著Z-NAND，3D XPoint 等新型存儲技術的出現，新一代的超低延遲SSD，例如三星Z-SSD 和英特爾Optane SSD，將4 KB 大小的隨機讀延遲從10 ms降低至10 μs，與內存的性能差距從10 萬倍降低至100倍，進一步縮小了內存和外存之間的性能差距.以英特爾Optane SSD 為例，3D XPoint 技術是英特爾和美光科技聯合開發的一種非易失性存儲器技術，Optane SSD的控制器能夠將單個4 KB 的I/O 分布在多個3D XPoint內存通道上，從而同時利用多個內存芯片處理單個I/O.Optane SSD 的第一代產品為P4800x，可以分別提供2 400 MBps 的順序讀取速度和2 000 MBps 的順序寫入速度.在隨機讀寫方面，P4800x 提供550kIOPS的順序讀取性能和500kIOPS 的隨機寫入性能.

近年來，業界在利用超低延遲NVMe 設備消除塊層I/O 延遲方面進行了一些工作.這些工作分別通過軟件[7-8,16-18]和硬件[19-20]層面的優化來降低I/O 訪問延遲和優化I/O 調度.AIOS[7]在超低延遲SSD 的基礎上提出了異步I/O 棧的概念，將I/O 路徑中的同步操作用異步操作取代，以便將與I/O 有關的CPU 操作與設備I/O 同時進行.FlashShare[8]進行了整體的跨堆棧設計，使得應用能夠直接利用超低延遲SSD 設備的低延遲優勢，并滿足應用的不同服務級別要求.FlashShare 通過對存儲軟件棧的數據結構進行擴展，將應用的屬性傳遞給從內核到SSD 固件的所有層，從而實現I/O 請求從提交到執行，再到完成的所有過程優化.Harris 等人[16]的工作系統地利用超低延遲存儲設備研究了所有可用的Linux I/O 完成機制，包括中斷、輪詢和混合輪詢機制.Whitaker 等人[17]的工作對I/O 調度程序進行研究，對使用超低延遲SSD 情況下I/O 調度的性能和能效進行評估.

本節先后對近年來學術界針對頁交換機制和超低延遲SSD 的優化工作進行了介紹.現有的頁交換機制針對SSD 和遠端內存的I/O 特性進行軟件層面的優化，而針對使用超低延遲SSD 的單機場景下的頁交換機制存在研究空白.對于使用超低延遲SSD的工作，這類工作主要針對文件系統的I/O 操作進行優化，而對于頁交換操作缺乏針對性.本文首先針對超低延遲SSD 的特性優化Linux 頁交換機制，實現開銷更低的頁交換機制Ultraswap，包括實現輕量級的I/O 棧以及更為優化的交換路徑.

2 頁交換機制分析

本節將首先介紹頁交換機制的整體流程，然后分別對頁交換機制的頁換入路徑與頁換出路徑進行分析并給出測試結果.

圖1 為頁交換機制整體架構圖，頁交換機制由多層組成，包括交換邏輯層、多隊列塊層以及設備驅動層.交換邏輯層提供頁換入與頁換出過程中，頁面選擇算法的實現以及對交換緩存的處理；多隊列塊層提供操作系統級別的塊請求/響應管理和I/O 合并與調度機制；設備驅動層負責處理設備上I/O 請求的提交和完成.

圖1 頁交換機制整體架構圖Fig.1 Overview of the swapping mechanism frame diagram

2.1 頁換入路徑

當應用訪問到不在內存中的頁面時，會觸發缺頁異常，從用戶態進入內核態.此時只有從交換分區中將該頁面取回內存后，才能返回用戶態繼續執行.算法1 描述了頁換入算法的整體流程.

算法1.頁換入算法.

① functiondo_swap_page（）

②page←查找交換緩存；

③ if（交換緩存中不存在頁面）

④page←swapin_readahead（）；

⑤ end if

⑥ 為頁面生成頁表項；

⑦ 添加頁面反向映射關系；

⑧ end function

⑨ functionswapin_readahead（）

⑩ra_info←獲得需要換入的頁面范圍；

? 開啟塊層蓄流機制；

? for（每一個ra_info中的頁面page）

?page_allocated←為page分配交換緩存并判斷是否成功；

? if（page_allocated==true）

?swap_readpage（page）；

? end if

? end for

? 結束塊層蓄流機制；

? 將page插入頁面鏈表；

? end function

? functionswap_readpage（page）

?bio←生成塊層頁面I/O 信息，記錄回調函數為end_read_func；

?submit_bio(bio)；

? end function

1）交換邏輯層.當觸發缺頁異常，內存需要進行頁換入時，內核會調用函數do_swap_page進行處理.該函數會首先在交換緩存中對觸發缺頁異常的關鍵頁進行查詢（算法1 的行②）.交換緩存是另一種形式的頁面緩存，用于在選擇頁面的操作和實際執行頁面I/O 的機制之間充當緩沖者.對頁換入過程而言，當一個存在多對映射的頁面被讀入內存，該頁面將被保存在交換緩存中.當需要該頁面的另一個映射觸發缺頁異常，內核可以直接利用交換緩存中的頁面與該應用的頁表建立映射，而不需要從設備再一次讀入該頁面，從而減少設備I/O 的次數.當所有需要該頁面的頁表建立對應映射之后，交換緩存釋放該頁面.

如果交換緩存中沒有找到對應頁面，內核會調用函數swapin_readahead向設備發送讀請求.為了減少發生缺頁異常的次數，內核將發生缺頁異常的關鍵頁面附近的頁面一并取回，即進行預取操作.對于使用SSD 的情況，由于SSD 比磁盤擁有更好的隨機讀性能，Linux 內核中將取回與關鍵頁的物理地址臨近的幾個頁面，而非在設備上連續的幾個頁面.在設備完成頁面的讀請求之后，內核為取回的缺頁創建頁表項及反向映射，完成缺頁異常（算法1 的行⑥⑦）.

水解大麻籽蛋白富含精氨酸、天冬氨酸等，這在其他水解蛋白質原料中是少見的，可用作護膚品的保濕劑、營養劑和調理劑，也可用作頭發調理劑。

在函數swapin_readahead中，內核會首先獲取包含關鍵頁地址的一個地址范圍，即需要取回的所有頁面范圍.對于這個地址范圍內的每一個頁面，內核首先查找該頁面是否已經存在交換緩存中.若不存在，則為該頁面分配頁框并發送讀請求（算法1 的行?～?）.在所有頁面的請求發送完成后，將頁面加入到對應的頁面鏈表，使得取回的頁面能真正地被內核管理.

2）多隊列塊層.內核通過調用函數swap_readpage向設備發送每個頁面的讀請求.對每個頁面，內核為該頁面生成一個bio結構體，記錄該讀操作完成后的回調函數end_read_func，調用函數submit_bio將該頁面的讀請求發送到Linux 的塊層.

圖2 表示向多隊列塊層和NVMe 驅動發送I/O請求的處理流程.在塊層中，函數submit_bio提交的bio結構體會被轉換為request結構體，并將request結構體插入每個核對應的請求隊列中，在隊列中執行I/O 合并和調度操作.request結構體依次通過每個核對應的軟件隊列和硬件隊列，進入設備驅動層.

圖2 多隊列塊層及NVMe 驅動圖Fig.2 Diagram of multi-queue block layer & NVMe driver

I/O 合并和調度操作是將符合條件的多個I/O 請求合并成單個I/O 請求進行處理.在Linux 內核中，在從bio結構體到向驅動發送command的過程中，主要會發生2 次I/O 合并，分別為蓄流過程和調度過程.

每個進程都有一個蓄流隊列.如果進程向通用塊層發送I/O 請求前開啟了蓄流功能，請求會被保存在隊列中進行合并，直到泄流開啟，請求才會被發送到下層的調度器中.蓄流過程的另外一個功能是生成request結構體.當進程發送一個bio結構體，會首先嘗試將bio結構體合并進蓄流隊列里的request結構體，如果無法合并，則生成一個新的request結構體.在泄流的過程中，請求會被發送到下層調度算法的隊列中，實現進一步合并.電梯調度算法的主要目的是將request結構體對硬件的訪問順序化，并發送到下層的驅動層執行I/O 請求.

3）設備驅動層.在硬件隊列，內核使用函數nvme_queue_rq將請求分配給設備驅動層.每個NVMe 隊列都由一個提交隊列和一個完成隊列成對組成.每個request結構體在提交的過程中，會被轉變成command結構體發送到提交隊列，進行設備I/O.完成I/O 請求的服務后，NVMe 控制器通過向主機發送消息信號中斷（message signaled interrupts，MSI）來通知內核數據傳輸完成.

2.2 頁換出路徑

當內存不足的時候，內核需要進行頁面回收，從而釋放頁幀，使得有空閑的內存可以被使用.頁面回收過程需要確定哪些頁可以從內存換出且對內核性能影響較小.

頁面回收過程主要在2 種情況下觸發：1）如果進行內存分配時沒有足夠的空閑內存，立即觸發內存回收；2）內核存在周期性回收內存機制，對系統內存進行周期性檢查.在頁交換過程中，缺頁異常同樣會涉及內存分配，因此在完成頁換入的關鍵路徑上，內核會對空閑內存的剩余情況進行檢查.如果此時空閑內存剩余不足，則觸發直接頁面回收.

在觸發頁面回收之后，需要選擇內存中的頁面進行回收.在每個內存節點，內核采用最近最少使用（least recently used，LRU）鏈表指向物理內存頁面.根據局部性原理，頁面鏈表假定最近最少使用的頁面在較短的時間內不會頻繁使用，因而可以選出需要回收的頁面.內核會對鏈表進行掃描，刷新活躍鏈表和不活躍鏈表.內核通過掃描不活躍鏈表，主要進行2個操作：為可以回收的頁面發送寫請求和釋放寫請求完成的頁面.算法2 展示了頁換出算法的整體流程.

算法2.頁換出算法.

① functionshrink_page_list（頁面鏈表）

② while（頁面鏈表非空）

③page←獲得頁面鏈表中的1 個頁面；

④ if（頁面不在交換緩存中）

⑤ 分配頁面交換槽位；

⑥ 解除頁面映射；

⑦swap_writepage（page）；

⑧ end if

⑨ if（頁面完成回寫）

⑩ 直接釋放頁面；

? end if

? end while

? end function

? functionswap_writepage（page）

?bio←生成塊層頁面I/O 信息，記錄回調函數end_write_func；

?submit_bio（bio）；

? end function

對于鏈表中的頁面，如果沒有被保存在交換緩存中，則需要對該頁進行回收操作（算法2 的行④～⑥）.內核會為該頁面分配交換分區的空閑槽位，并將其加入交換緩存.函數add_to_swap根據交換分區的槽位位圖，為換出頁選擇一個空閑槽位，并將交換分區和槽位信息保存在該頁面的結構體中，便于頁換入時查找頁面.內核在將頁面放入交換緩存且為該頁面分配槽位之后，會解除該頁面與用戶空間的映射并調用函數swap_writepage向塊層發送寫請求.

掃描匿名頁表的第2 個目的是回收頁框（算法2的行⑨～?）.對于沒有回寫完成的頁面，內核會繼續將其保留在不活躍鏈表中.對于已經回寫完成的頁面，內核將釋放頁框，釋放該頁面的鎖，完成頁面回收流程.

在函數swap_writepage中，與頁換入機制類似，內核首先為需要進行I/O 的頁面分配bio結構體，調用函數submit_bio將其向Linux 的塊層發送.頁換出機制在塊層和設備驅動層的操作與頁換入機制相同.

2.3 頁交換機制測試

結合2.1 節對頁換入路徑與2.2 節對頁換出路徑的描述，表2 對頁換入路徑的操作進行整理，并對每個操作的內核時間占比進行統計.

Table 2 Performance Analysis of Swapping Mechanism in Read Path表2 頁換入機制性能分析

表2 的測試結果表明，在使用超低延遲SSD 的情況下，頁換入路徑上多隊列塊層的時間可達到整體內核時間的64%，是設備延遲的5.2 倍.表3 對頁換出路徑的操作進行分析.測試結果表明，頁換出路徑上多隊列塊層的內核時間占比達到56.9%，是設備I/O延遲的5.0 倍.以執行kmeans 應用為例，該應用使用sklearn 庫對1 500 萬個樣本進行分類.在全內存的情況下，應用執行完成的時間為238 s.當可使用內存為所需內存的60%時，應用執行完成的時間增加至527 s，增加的時間即為執行頁交換機制的時間.其中，塊層所占時間為162 s，占頁交換機制執行時間的56%.

對于頁換入路徑，主要問題在于Linux 頁交換機制的隊頭阻塞問題、缺頁異常的關鍵路徑上的中斷處理過程，以及I/O 合并和調度機制導致內核軟件開銷過大.

首先，內核根據需要預取的頁面數量（Linux 中默認預取8 頁），將整個內核空間地址按照特定的聚集（cluster）進行劃分.當確認預取頁面范圍時，內核根據關鍵頁面的虛擬地址，選擇包含該頁面的cluster，將該cluster 中的頁面按照地址從小到大的順序發送讀請求.然而，這產生了一個問題，觸發缺頁異常的關鍵頁面可能在這個cluster 的任何位置.與此同時，現在Linux 中的多隊列塊層為每個CPU 只提供了1個隊列[21]，關鍵頁的請求可能排在預取頁的請求之后，產生隊頭阻塞問題，因而缺頁的讀請求可能需要等待幾十微秒才會被發送[13].

其次，現在Linux 中的多隊列塊層為每個CPU提供一個中斷隊列，即當I/O 完成后會發送中斷信號來通知I/O 完成.因為缺頁異常返回前需要保證關鍵頁的I/O 完成，因此中斷會發生在缺頁異常的關鍵路徑上，為缺頁異常的整體過程增加了13%～26%內核時間開銷.

此外，內核會將每個頁面的讀請求加入到蓄流隊列.在所有頁面的請求發出之后，再集中泄流到驅動隊列.多隊列塊層的合并操作雖然可以減少I/O 操作的總數，但是合并過程需要消耗許多CPU 周期來搜索軟件隊列，進一步延長了關鍵頁讀請求的等待時間開銷.

與頁換入路徑類似，頁換出機制在塊層同樣值得優化.然而，由于頁換出路徑部分并不需要區分關鍵頁面與其他頁面.因此，我們可以考慮去除I/O 合并和調度機制，實現更輕量級的寫請求.值得一提的是，在觸發缺頁異常的頁面需要進行內存分配時，會對空閑內存的情況進行檢查.如果空閑內存不足，內核會進行直接頁面回收，影響缺頁異常的返回，延長應用的等待時間.

3 Ultraswap 設計

本節介紹基于超低延遲SSD 開發的內核頁交換機制Ultraswap，該機制包括一個輕量級的I/O 棧，該I/O 棧將Linux 中的塊層進一步簡化，進而降低頁交換機制的軟件開銷.此外，本節還將介紹Ultraswap 對于交換路徑的優化工作.圖3 展示了Ultraswap 的整體設計圖.

圖3 Ultraswap 整體設計圖Fig.3 Overview design drawing of Ultraswap

Ultraswap 主要進行2 方面改進：

1） 在I/O 棧部分，首先取消了I/O 合并和調度機制.讀請求會被直接發送到驅動層進行設備I/O，從而降低請求的等待時間.其次，考慮到Linux 塊層的隊頭阻塞問題，Ultraswap 的I/O 棧實現了對中斷和輪詢請求的處理.一方面，中斷與輪詢請求使用2 個不同的隊列，可以避免隊頭阻塞問題.另一方面，考慮到中斷對關鍵路徑的影響，使用輪詢請求的方式可以降低關鍵路徑上的中斷開銷.

2） 在交換路徑部分主要進行了2 部分優化.首先，在頁換入過程中，區分觸發缺頁異常的關鍵頁面與預取頁面，使用輪詢請求處理關鍵頁面，并優先發送關鍵頁面的讀請求.另一方面，增加對關鍵路徑上直接內存回收的處理.考慮到內存不足時直接內存回收的處理會影響缺頁異常的完成，將直接內存回收提交給一個專門的CPU 進行處理，從而降低應用的等待時間.

3.1 I/O 棧設計

在Linux 頁交換機制中，所有頁的讀寫請求都會通過多隊列塊層被放入當前CPU 對應的中斷隊列.對Ultraswap 而言，想要實現輕量級的I/O 棧，首先需要解決Linux 中的I/O 合并和調度問題，其次需要實現對輪詢請求的支持.

圖4 展示了Ultraswap 的I/O 棧中對請求的發送流程圖.圖4 箭頭①為Linux 的通用塊層的流程.當頁交換機制希望提交I/O 請求時，會先構造bio結構體.bio結構體會首先與隊列中已有的request結構體進行合并，如果不能合并則生成新的request結構體.隊列中的request結構體經過調度之后，被放入當前CPU 的軟件隊列和硬件隊列.之后，request結構體轉變為command結構體放入對應NVMe 中斷隊列，進行設備I/O.

圖4 Ultraswap 請求發送流程圖Fig.4 Overview of request sending in Ultraswap

由于利用超低延遲SSD 進行存儲的I/O 調度程序要么無濟于事，要么顯著增加請求延遲，同時還會對吞吐量和能效產生負面影響[16].因此，我們考慮直接由bio結構體構造request結構體，并最終直接構造command結構體放入驅動隊列，進行設備I/O，從而盡可能地減少內核軟件開銷（圖4 箭頭②）.

事實上，對于Ultraswap 中的中斷情況，在設備I/O 完成進入中斷處理函數時，會根據完成中斷的請求找到其request結構體，并對request中的每個bio結構體調用請求處理函數.因此，在發送中斷請求的函數中，Ultraswap 需要保留bio結構體和request結構體，僅僅去掉不必要的I/O 合并和調度操作.

對于輪詢請求，則可以使用更為簡單的方式.輪詢完成的處理過程并不需要使用request結構體和bio結構體.因此，輪詢請求函數可以根據需要進行讀寫的頁面地址，直接構造command結構體向NVMe 輪詢隊列發送請求（圖4 箭頭③）.

針對上述描述，Ultraswap 的I/O 棧提供了3 種請求函數，圖5 為這3 種函數的示意圖.圖5（a）為輪詢請求.當請求發送到設備后，CPU 會一直進行輪詢，直到設備I/O 完成.圖5（b）為中斷請求處理過程，在發送請求之后，如果I/O 完成，內核會收到中斷信號并進入中斷處理過程.考慮到輪詢處理過程會大量占用CPU，因而圖5（c）將輪詢請求的發送過程和輪詢過程進行拆分，使得在發送輪詢請求后可以進行其他步驟的處理后再輪詢等待I/O 完成.

圖5 Ultraswap 接口函數示意圖Fig.5 Illustration of Ultraswap API functions

3.2 交換路徑優化設計

在處理缺頁異常的過程中，主要會碰到4 個問題：

1） 頁面的讀請求在NVMe 隊列中會按地址順序處理，由于每個CPU 只有一個隊列，這導致關鍵頁的讀請求前可能存在其他預取頁的請求，從而導致隊頭阻塞問題.

2） Linux 的頁交換機制存在I/O 合并和調度操作，導致關鍵頁的讀請求可能會被合并或調度到別的請求之后，這個問題已經在Ultraswap 的I/O 棧實現中被優化.

3） 現在的Linux 塊層隊列均為中斷隊列，在缺頁異常完成之前需要處理關鍵頁的I/O 中斷，延后了缺頁異常返回的時間.

4） 在關鍵頁處理完成之后，內核需要進行空閑內存檢查.如果空閑內存不足，需要進行直接內存回收操作，待內存回收操作結束后才會繼續執行應用.

圖6（a）展示了Linux 頁交換機制對缺頁異常的處理過程.當觸發缺頁異常，內核會按照地址順序依此發送讀請求，并在塊層進行蓄流.請求會在蓄流結束后被送到設備進行I/O.I/O 完成后，設備通過觸發中斷令CPU 對請求進行處理.如果此時空閑內存不足，Linux 還將會進行直接頁面回收.在上述步驟完成后，Linux 頁交換機制才會從內核態返回用戶態，繼續執行應用.

圖6 缺頁異常和預取流程示意圖Fig.6 Overview of page fault and prefetching process

針對上述問題，Ultraswap 的交換路徑優化設計如下：

首先，在缺頁異常的過程中，為了解決隊頭阻塞問題，Ultraswap 選擇給每個CPU 分配2 個隊列，用于分別處理關鍵頁和預取頁.同時，使用2 個隊列分別處理關鍵頁和預取頁使得Ultraswap 能夠使用不同的方法處理關鍵頁和預取頁.考慮到在缺頁異常返回前，需要保證關鍵頁的I/O 完成，且關鍵頁的I/O 完成越快越好，因此Ultraswap 使用輪詢的方式處理關鍵頁，這樣可以減少缺頁異常的關鍵路徑上中斷帶來的影響.對于預取頁，在缺頁異常過程中并不需要保證預取頁的I/O 完成，因此Ultraswap 采用中斷的方式處理預取頁的讀請求.

其次，通過修改內核，本文對關鍵頁和預取頁進行分別處理.當進入函數swapin_readahead時，會首先發送關鍵頁的輪詢請求至設備的NVMe 驅動隊列.接下來對于所有需要預取的頁面，內核會依次發送對應該頁面的中斷請求.當發送完中斷請求之后，內核會進行輪詢操作，等待關鍵頁的I/O 完成，如圖6(b）所示.通過先發送關鍵頁的讀請求，我們可以在設備讀入關鍵頁的同時，進行預取頁的頁框分配和發送預取頁的讀請求，從而可以充分利用設備的I/O 時間.事實上，在我們的實驗中發現，絕大多數輪詢請求的I/O 在發送完成預取請求之后已經完成，因此對CPU 開銷的影響可以忽略不計.

對于頁面回收過程中Ultraswap I/O 棧請求函數的選擇，由于內核可以將I/O 未完成的頁面重新加入頁面鏈表，選擇將上一次頁面回收過程中被加入頁面鏈表的頁框釋放，并不需要等待本次回收頁面的I/O 完成.因此，對于回收頁面，Ultraswap 同樣采用中斷的方式發送請求.

此外，在缺頁異常的處理過程中讀取頁面后，內核會檢查內存是否超過內存水位線.如果有多余的頁面，頁面將被直接回收.直接內存回收發生在缺頁異常的上下文中，造成相當一部分的時間開銷.因此本文將直接頁面回收過程指定給一個專門的CPU.當內存不足時，內核會喚醒指定CPU 來處理頁面回收，從而當前CPU 可以返回用戶態繼續執行應用.本文設置的內存水位線為內存限制的70%.如果使用的內存超過了內存限制，則會直接在關鍵路徑上實現內存回收，而不進行遷移.圖6（b）展示了Ultraswap 對缺頁異常優化后的處理過程.當觸發缺頁異常，內核首先會將關鍵頁的輪詢請求直接發送到設備的輪詢隊列.接下來，內核會依次將預取頁的請求發送到設備的中斷隊列.當預取頁的請求發送完成，內核會對輪詢隊列進行輪詢操作，直到關鍵頁的請求完成.隨后，如果空閑內存不足，Ultraswap 會調用另一個CPU進行頁面回收操作.在上述步驟完成后，Ultraswap 即可從內核態返回用戶態，繼續應用的執行.

4 測評與分析

本節對Ultraswap進行性能測評.首先測試Ultraswap的I/O 接口函數性能，然后對Ultraswap 進行應用場景測試.近年來，一些工作[12–15]利用新型高速設備提出頁交換機制的優化，這些工作主要是利用RDMA技術，但是沒有工作針對超低延遲SSD 進行優化.考慮到RDMA 與超低延遲SSD 使用的I/O 棧差異較大，因此本文選擇與Linux 頁交換機制進行比較.最后針對在缺頁異常和內存回收方面提出的優化方法進行評測，評估其有效性.

4.1 測試環境

本文測試使用1 臺帶有英特爾Optane SSD 的服務器進行頁交換機制性能測試，其硬件指標如表4所示.

Table 4 Test Environment for Swapping Mechanism表4 頁交換機制測試環境

為了更靈活地控制內存使用以及觸發頁交換機制，本文使用了Linux 控制組（control groups, cgroups）.cgroups 可以用來限制和控制一個進程組的資源，包括CPU、內存和設備I/O 等.本文使用cgroups 對測試過程中可使用的物理內存進行限制，超過物理內存的部分會通過頁交換機制被放入交換分區.

4.2 讀寫性能測試

本節主要對Ultraswap 的I/O 棧接口函數進行性能測試，并將其與Linux 中的頁交換讀寫函數進行比較.此外，利用fronswap 接口，本文還實現了以DRAM為存儲設備的I/O 棧，該I/O 棧通過直接進行memcpy操作將頁面交換到內存中不被cgroups 限制的另一塊區域.這種方式將I/O 需要的軟硬件開銷降至最低，因此本文將以DRAM 為存儲設備的頁交換方式作為頁交換的理想化情況并進行測試.

本節分3 步對Ultraswap（輪詢）、Ultraswap（中斷）和DRAM 這3 種I/O 棧進行讀寫測試.1）分配一個100 MB 的char 類型數組，利用cgroups 工具將可使用的物理內存限制到50 MB.2）對這個數組的每一項先寫入一遍字符，觸發頁換出過程.3）遍歷數組的每一項，觸發頁換入過程并進行正確性驗證.該測試均在單線程環境下完成，統計每部分操作的延遲.

圖7 展示了在3 種I/O 棧中發送讀/寫請求的延遲.測試結果表明，在單線程環境下，2 種Ultraswap的輪詢請求處理過程相比Linux 在讀/寫操作上分別提升了78%和72%.原因在于Ultraswap 發送輪詢請求的過程中可以完全繞過塊層，直接通過NVMe 驅動向設備發送I/O 請求.此外，當CPU 輪詢到請求完成時，可以直接調用請求完成處理函數，減少了中斷和上下文切換帶來的時間開銷.2 種Ultraswap 的中斷請求處理過程相比Linux 在讀/寫上僅提升了18%和13%.原因在于：一方面，Ultraswap 僅對發送中斷請求的部分進行優化；另一方面，雖然Ultraswap 在發送請求的過程中減少了Linux 塊層中的I/O 合并和調度操作，但是為了保證中斷處理，仍然需要分配bio和request結構體，造成額外開銷.

圖7 讀寫性能測試結果Fig.7 Results of read and write performance

4.3 應用負載測試

本節對4.2 節中3 種I/O 棧進行性能測試.測試包括5 個應用，分別為quicksort，kmeans，tensorflow，pagerank，linpack.quicksort 應用使用C++標準庫對 8 GB 的整數進行快速排序；kmeans 應用使用sklearn 庫對1 500 萬個樣本進行分類；tensorflow 應用對用于基準測試的inception 樣例進行計算；pagerank 應用使用包含65.5萬個節點和750 萬條邊的數據集進行測試；linpack 應用是一個線性代數性能基準測試，使用英特爾提供的二進制文件.表5 展示這5 個應用需要使用的內存和核數.

Table 5 Basic Information of Application表5 應用基本情況

根據應用需要的內存上限，將可使用的內存比例限制到100%，80%，60%，40%，20%，記錄應用執行完成的時間，多次執行并計算平均時間.當可使用的內存比例為100%時，應用不觸發頁交換機制.則當對內存比例進行限制，增加的應用完成時間可以認為是頁交換機制的執行時間.本文將可使用內存比例為100%的應用平均執行時間作為基準時間，對不同內存比例下的應用執行時間進行標準化處理.

圖8 展示3 種I/O 棧的應用測試結果，當可使用內存比例為100%時應用不觸發頁交換機制，我們將此時的應用執行時間標注在圖上.測試結果表明，在5 種應用上Ultraswap 均表現出較好的頁交換性能.quicksort，kmeans，tensorflow，pagerank，linpack 應用的平均性能提升為9%，19%，10%，13%，15%.當可使用內存比例為20% 時，這5 個應用可達到15%，33%，22%，18%，19% 的性能提升.與理想化情況相比，Ultraswap 將Linux 頁交換機制與理想情況的差距縮小至5%，25%，18%，22%，40%，這得益于Ultraswap的I/O 棧和交換路徑優化設計.

圖8 應用性能測試結果Fig.8 Results of application performance tests

4.4 優化有效性測試

4.4.1 缺頁異常優化測試

Ultraswap 中對觸發缺頁異常的關鍵頁面使用輪詢請求，對預取頁面和回收頁面使用中斷請求.本節對使用純中斷Ultraswap-interrupt-only 和純輪詢請求Ultraswap-poll-only 的2 種I/O 棧進行性能測試，并與Ultraswap 的優化方案進行比較，以說明Ultraswap 在缺頁異常方面優化的合理性和有效性.

圖9 的測試結果表明，與Ultraswap 相比，在quicksort，kmeans，tensorflow，pagerank，linpack 應用上Ultraswap-interrupt-only 的時間分別增加了2%，2%，2%，7%，4%，主要原因在于輪詢請求減少了關鍵路徑上的中斷處理和上下文切換時間，且CPU 處理完請求后即可返回應用.

圖9 Ultraswap 缺頁異常優化結果Fig.9 Optimization results of Ultraswap for page fault handling

Ultraswap-poll-only 的應用性能則更差，在quicksort，kmeans，tensorflow，pagerank，linpack 應用的時間分別增加了6%，35%，7%，20%，33%.與受內存限制影響較小的應用quicksort 和tensorflow 相比，受內存限制影響較大的應用kmeans，pagerank，linpack 受到純輪詢的I/O 棧影響更為明顯.本文認為主要原因在于內核的內存回收機制更傾向于使用異步操作而不是同步操作.首先，在內存回收過程中，如果是異步操作，那么在寫請求發送完成后，頁面會在不活躍頁面鏈表上掛起；等到第2 次進入內存回收過程時，如果該頁面的I/O 請求已經完成，則內存可以直接被回收，因而頁面鏈表上始終存在等待請求完成的頁面.而對于同步操作，頁面鏈表上的每個可以回收的頁面會在發送寫請求后，等待設備I/O 完成并且釋放頁框，因而在內存回收之后不活躍頁面鏈表上的頁面大量減少，從而會從活躍鏈表遷移更多的頁面進入不活躍鏈表.總而言之，純輪詢的I/O 棧會導致更多的頁面交換，從表6 可以看出，在linpack 應用執行過程中，Ultraswap-poll-only 相比Ultraswap 會觸發1.15 倍的缺頁異常次數.

Table 6 Number of Page Faults in Linpack with Ultraswap’s I/O Stack表6 Ultraswap I/O 棧在Linpack 應用中觸發缺頁異常次數

4.4.2 內存回收優化測試

本節測試Ultraswap 中對內存回收路徑的優化效果.本測試將應用的可使用內存比例設置為50%，對遷移直接頁面回收過程前后的內核時間占比進行記錄和統計，從而評估對內存回收路徑的優化效果.表7顯示，優化頁面回收路徑可以顯著減少內核時間，使內核時間減少多達35.3%.

Table 7 Performance of Memory Reclaimation Optimization表7 內存回收優化性能s

5 總 結

頁交換機制是用于內存擴展的經典技術，該機制通過將較少使用的內存頁面保存在存儲設備，從而達到擴展內存的目的.過去頁交換機制一直受限于慢速磁盤的讀寫速度，因而無法廣泛應用.近年來，隨著超低延遲SSD 的快速發展，頁交換機制可以利用其低延遲的讀寫特性來改善頁交換效率.

本文首先對Linux 頁交換機制的頁換入和頁換出路徑進行分析和評測.測試結果表明，在使用超低延遲SSD 的情況下，Linux 塊層和設備驅動層的軟件開銷可達到內核時間開銷的64%.主要原因在于塊層中存在隊頭阻塞、I/O 合并和調度開銷，以及關鍵路徑上的中斷時間開銷問題.同時，當觸發缺頁異常需要分配內存空間時，如果當前內核的空閑內存不足，會觸發直接內存回收，同樣會在缺頁異常的關鍵路徑上造成額外的時間開銷.

基于上述問題，本文設計了內核頁交換機制Ultraswap.Ultraswap 通過直接使用NVMe 驅動、避免I/O合并和調度的方式實現了輕量級的I/O 棧，能夠處理讀寫函數的輪詢和中斷請求.在內核方面，Ultraswap從缺頁異常和內存回收2 個方面進行優化，通過拆分請求隊列，混合使用輪詢和中斷請求、轉移直接內存回收的方式，降低關鍵路徑上的時間開銷.

本文將Ultraswap 與Linux 頁交換機制進行對比來比較性能，結果表明Ultraswap 在應用測試場景下相比Linux 能夠提升19%的平均性能；與理想化情況相比，Ultraswap 能夠將Linux 與理想化情況的性能差距減少95%.

作者貢獻聲明：王紫芮提出文章思路、方案設計并撰寫論文；蔣德鈞提出指導意見并修改論文.