王紫芮 蔣德鈞

（中國(guó)科學(xué)院計(jì)算技術(shù)研究所先進(jìn)計(jì)算機(jī)系統(tǒng)研究中心 北京 100190）

（處理器芯片全國(guó)重點(diǎn)實(shí)驗(yàn)室（中國(guó)科學(xué)院計(jì)算技術(shù)研究所） 北京 100190）

（中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 北京 100049）

隨著內(nèi)存密集型應(yīng)用的廣泛興起，日益增長(zhǎng)的數(shù)據(jù)量和對(duì)高性能應(yīng)用的追求使得對(duì)內(nèi)存的需求迅速增長(zhǎng).然而，隨著摩爾定律的放緩，內(nèi)存難以獲得更高的存儲(chǔ)密度和更低的顆粒價(jià)格[1].因此，如何有效地進(jìn)行內(nèi)存擴(kuò)展成為急需解決的問(wèn)題.

頁(yè)交換機(jī)制是用于內(nèi)存擴(kuò)展的經(jīng)典技術(shù).當(dāng)內(nèi)存不足時(shí)，該機(jī)制通過(guò)將較少使用的內(nèi)存頁(yè)面保存在存儲(chǔ)設(shè)備，從而達(dá)到擴(kuò)展內(nèi)存的目的.當(dāng)應(yīng)用需要訪(fǎng)問(wèn)不在內(nèi)存中的頁(yè)面時(shí)，則通過(guò)觸發(fā)缺頁(yè)異常，將在存儲(chǔ)設(shè)備的頁(yè)面讀入內(nèi)存中的指定地址，以確保應(yīng)用的正常運(yùn)行.頁(yè)交換機(jī)制由內(nèi)核提供，且對(duì)應(yīng)用程序透明.

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

然而，隨著高速設(shè)備的發(fā)展，I/O 延遲被降低到微秒級(jí)別，設(shè)備的讀寫(xiě)性能不再是限制頁(yè)交換性能的瓶頸，反而傳統(tǒng)上被認(rèn)為是輕量級(jí)的內(nèi)核軟件開(kāi)銷(xiāo)，愈發(fā)不可忽視.頁(yè)交換機(jī)制較為復(fù)雜，涉及到內(nèi)核的交換邏輯層（頁(yè)面回收與缺頁(yè)異常處理）以及I/O 棧（多隊(duì)列塊層與設(shè)備驅(qū)動(dòng)層）.交換邏輯層需要完成對(duì)交換頁(yè)面的選擇并對(duì)交換緩存進(jìn)行處理，而I/O 棧需要進(jìn)行讀寫(xiě)請(qǐng)求的提交和完成工作.由于目前沒(méi)有工作對(duì)現(xiàn)有的Linux 頁(yè)交換機(jī)制進(jìn)行分析，本文希望通過(guò)實(shí)驗(yàn)和分析，可以為設(shè)計(jì)高效的頁(yè)交換機(jī)制提供設(shè)計(jì)指導(dǎo).

針對(duì)超低延遲SSD，學(xué)術(shù)界利用其低延遲的特點(diǎn)進(jìn)行了I/O 棧設(shè)計(jì)，例如AIOS[7]，F(xiàn)lashShare[8]等.這部分工作通過(guò)降低內(nèi)核塊層開(kāi)銷(xiāo)，提升整體性能.然而，盡管現(xiàn)有頁(yè)交換機(jī)制和文件系統(tǒng)共享一部分I/O 棧，文獻(xiàn)[7-8]工作集中于對(duì)文件頁(yè)進(jìn)行I/O 優(yōu)化，而忽視頁(yè)交換時(shí)匿名頁(yè)的讀寫(xiě)特征以及內(nèi)核時(shí)間開(kāi)銷(xiāo)情況，導(dǎo)致無(wú)法有效降低頁(yè)交換機(jī)制的軟件開(kāi)銷(xiāo).據(jù)我們所知，本文是利用超低延遲SSD 對(duì)頁(yè)交換機(jī)制進(jìn)行優(yōu)化的工作.

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

基于測(cè)試實(shí)驗(yàn)結(jié)果，本文設(shè)計(jì)了基于超低延遲SSD 的頁(yè)交換機(jī)制Ultraswap.Ultraswap 在Linux I/O棧的基礎(chǔ)上增加了對(duì)輪詢(xún)請(qǐng)求的處理，并通過(guò)直接調(diào)用NVMe（non-volatile memory express）驅(qū)動(dòng)的方式，降低了I/O 合并與調(diào)度開(kāi)銷(xiāo)，從而實(shí)現(xiàn)了輕量級(jí)的I/O 棧.利用Ultraswap 的I/O 棧，本文對(duì)內(nèi)核頁(yè)交換機(jī)制的換入與換出路徑進(jìn)一步優(yōu)化.在缺頁(yè)異常方面，Ultraswap 為每個(gè)CPU 分配多個(gè)請(qǐng)求隊(duì)列，從而混合使用輪詢(xún)和中斷請(qǐng)求，分離關(guān)鍵頁(yè)面、預(yù)取頁(yè)面及回收頁(yè)面，解決請(qǐng)求發(fā)送時(shí)的隊(duì)頭阻塞問(wèn)題；在內(nèi)存回收方面，考慮到處理缺頁(yè)異常的關(guān)鍵路徑上可能觸發(fā)直接內(nèi)存回收，影響缺頁(yè)異常的返回，本文將直接內(nèi)存回收的過(guò)程進(jìn)行遷移，降低關(guān)鍵路徑上的時(shí)間開(kāi)銷(xiāo).

本文的主要貢獻(xiàn)包括4 個(gè)方面：

1） 基于超低延遲SSD 進(jìn)行Linux 頁(yè)交換機(jī)制的分析和性能測(cè)評(píng)，分析內(nèi)核各操作的時(shí)間占比，歸納影響頁(yè)交換機(jī)制的主要原因；

2） 設(shè)計(jì)和實(shí)現(xiàn)基于超低延遲SSD 的頁(yè)交換機(jī)制Ultraswap，實(shí)現(xiàn)輕量級(jí)的內(nèi)核I/O 棧，降低頁(yè)交換的軟件開(kāi)銷(xiāo)；

3） 提出內(nèi)核頁(yè)交換機(jī)制的換入與換出路徑優(yōu)化方法，優(yōu)化頁(yè)交換關(guān)鍵路徑，降低內(nèi)核軟件延遲；

4） 結(jié)果表明Ultraswap 在應(yīng)用測(cè)試場(chǎng)景下相比Linux 頁(yè)交換機(jī)制能夠提升19%的平均性能，與理想化情況相比，Ultraswap 能夠?qū)inux 頁(yè)交換機(jī)制與理想化情況的性能差距減少95%.

1 相關(guān)工作

本節(jié)主要介紹目前業(yè)界對(duì)于頁(yè)交換機(jī)制和超低延遲SSD 的相關(guān)工作.在頁(yè)交換機(jī)制部分，主要介紹學(xué)術(shù)界在使用不同存儲(chǔ)設(shè)備，例如遠(yuǎn)程直接內(nèi)存訪(fǎng)問(wèn)（remote direct memory access，RDMA）[9]、硬盤(pán)的情況下，針對(duì)頁(yè)交換機(jī)制的軟件層開(kāi)銷(xiāo)進(jìn)行的優(yōu)化工作，包括預(yù)取算法、I/O 棧優(yōu)化等；在超低延遲SSD部分，將介紹部分超低延遲SSD 的性能參數(shù)，以及基于超低延遲SSD 進(jìn)行的內(nèi)核軟件優(yōu)化工作.

1.1 頁(yè)交換機(jī)制

為了滿(mǎn)足用戶(hù)的需求，或者滿(mǎn)足內(nèi)存密集型應(yīng)用程序的需求，內(nèi)核會(huì)將較少使用的內(nèi)存頁(yè)面換出到存儲(chǔ)設(shè)備，這相當(dāng)于提供更多的內(nèi)存，這種機(jī)制稱(chēng)為頁(yè)交換機(jī)制.當(dāng)內(nèi)存不足時(shí)，內(nèi)核會(huì)掃描頁(yè)面鏈表，選擇較少使用的匿名頁(yè)面，將其寫(xiě)到存儲(chǔ)設(shè)備上的交換分區(qū).當(dāng)需要使用該頁(yè)面時(shí)，觸發(fā)缺頁(yè)異常，根據(jù)換出時(shí)的信息記錄，發(fā)送讀請(qǐng)求將該頁(yè)面從存儲(chǔ)設(shè)備讀入內(nèi)存.

在使用不同存儲(chǔ)設(shè)備的情況下，頁(yè)交換機(jī)制的上層軟件交換邏輯（例如頁(yè)面回收算法、頁(yè)面預(yù)取算法）相同，而讀寫(xiě)請(qǐng)求在經(jīng)過(guò)多隊(duì)列塊層之后會(huì)通過(guò)不同的驅(qū)動(dòng)發(fā)送到設(shè)備，例如發(fā)送到NVMe SSD 上的讀寫(xiě)請(qǐng)求需要使用NVMe 驅(qū)動(dòng)接口函數(shù)，而發(fā)送到遠(yuǎn)端內(nèi)存的讀寫(xiě)請(qǐng)求使用RDMA 接口函數(shù).根據(jù)存儲(chǔ)設(shè)備的不同，本文將使用硬盤(pán)作為交換分區(qū)的頁(yè)交換機(jī)制稱(chēng)為本地頁(yè)交換機(jī)制，使用遠(yuǎn)端內(nèi)存作為交換分區(qū)的頁(yè)交換機(jī)制稱(chēng)為遠(yuǎn)端頁(yè)交換機(jī)制.

1）本地頁(yè)交換機(jī)制.頁(yè)交換機(jī)制已經(jīng)被研究了很多年.與磁盤(pán)相比，SSD 的性能有極大的提升，基于SSD 的頁(yè)交換機(jī)制已成為解決內(nèi)存擴(kuò)展問(wèn)題的主流方案.FlashVM[10]利用閃存的特性，對(duì)內(nèi)核的頁(yè)交換機(jī)制實(shí)現(xiàn)整體優(yōu)化.在頁(yè)換入路徑上，利用閃存相對(duì)磁盤(pán)更低的尋道時(shí)間，F(xiàn)lashVM 使用步幅預(yù)取以最大限度地減少不需要的頁(yè)面內(nèi)存污染.在頁(yè)換出路徑上，F(xiàn)lashVM 以比Linux 更精細(xì)的粒度限制頁(yè)面回寫(xiě)速率，從而更好地實(shí)現(xiàn)頁(yè)面從內(nèi)存到閃存的擁塞控制.SPAN[11]提出重新構(gòu)建系統(tǒng)執(zhí)行分頁(yè)和預(yù)讀的機(jī)制，利用NVM 設(shè)備提供的高并行度和高性能，將觸發(fā)缺頁(yè)異常的關(guān)鍵頁(yè)面與預(yù)取的頁(yè)面分開(kāi)，將預(yù)取任務(wù)分配給單獨(dú)的線(xiàn)程處理，從而降低關(guān)鍵路徑上的等待時(shí)延.此外，SPAN 提出了一種復(fù)雜的算法來(lái)預(yù)測(cè)預(yù)取頁(yè)面的未來(lái)訪(fǎng)問(wèn)情況，從而減少?gòu)腘VM設(shè)備中預(yù)取的無(wú)用頁(yè)面數(shù)量.

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

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

Table 1 Comparative Analysis of Swapping Mechanism in Related Works表1 頁(yè)交換機(jī)制相關(guān)工作對(duì)比

1.2 超低延遲SSD

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

隨著Z-NAND，3D XPoint 等新型存儲(chǔ)技術(shù)的出現(xiàn)，新一代的超低延遲SSD，例如三星Z-SSD 和英特爾Optane SSD，將4 KB 大小的隨機(jī)讀延遲從10 ms降低至10 μs，與內(nèi)存的性能差距從10 萬(wàn)倍降低至100倍，進(jìn)一步縮小了內(nèi)存和外存之間的性能差距.以英特爾Optane SSD 為例，3D XPoint 技術(shù)是英特爾和美光科技聯(lián)合開(kāi)發(fā)的一種非易失性存儲(chǔ)器技術(shù)，Optane SSD的控制器能夠?qū)蝹€(gè)4 KB 的I/O 分布在多個(gè)3D XPoint內(nèi)存通道上，從而同時(shí)利用多個(gè)內(nèi)存芯片處理單個(gè)I/O.Optane SSD 的第一代產(chǎn)品為P4800x，可以分別提供2 400 MBps 的順序讀取速度和2 000 MBps 的順序?qū)懭胨俣?在隨機(jī)讀寫(xiě)方面，P4800x 提供550kIOPS的順序讀取性能和500kIOPS 的隨機(jī)寫(xiě)入性能.

近年來(lái)，業(yè)界在利用超低延遲NVMe 設(shè)備消除塊層I/O 延遲方面進(jìn)行了一些工作.這些工作分別通過(guò)軟件[7-8,16-18]和硬件[19-20]層面的優(yōu)化來(lái)降低I/O 訪(fǎng)問(wèn)延遲和優(yōu)化I/O 調(diào)度.AIOS[7]在超低延遲SSD 的基礎(chǔ)上提出了異步I/O 棧的概念，將I/O 路徑中的同步操作用異步操作取代，以便將與I/O 有關(guān)的CPU 操作與設(shè)備I/O 同時(shí)進(jìn)行.FlashShare[8]進(jìn)行了整體的跨堆棧設(shè)計(jì)，使得應(yīng)用能夠直接利用超低延遲SSD 設(shè)備的低延遲優(yōu)勢(shì)，并滿(mǎn)足應(yīng)用的不同服務(wù)級(jí)別要求.FlashShare 通過(guò)對(duì)存儲(chǔ)軟件棧的數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展，將應(yīng)用的屬性傳遞給從內(nèi)核到SSD 固件的所有層，從而實(shí)現(xiàn)I/O 請(qǐng)求從提交到執(zhí)行，再到完成的所有過(guò)程優(yōu)化.Harris 等人[16]的工作系統(tǒng)地利用超低延遲存儲(chǔ)設(shè)備研究了所有可用的Linux I/O 完成機(jī)制，包括中斷、輪詢(xún)和混合輪詢(xún)機(jī)制.Whitaker 等人[17]的工作對(duì)I/O 調(diào)度程序進(jìn)行研究，對(duì)使用超低延遲SSD 情況下I/O 調(diào)度的性能和能效進(jìn)行評(píng)估.

本節(jié)先后對(duì)近年來(lái)學(xué)術(shù)界針對(duì)頁(yè)交換機(jī)制和超低延遲SSD 的優(yōu)化工作進(jìn)行了介紹.現(xiàn)有的頁(yè)交換機(jī)制針對(duì)SSD 和遠(yuǎn)端內(nèi)存的I/O 特性進(jìn)行軟件層面的優(yōu)化，而針對(duì)使用超低延遲SSD 的單機(jī)場(chǎng)景下的頁(yè)交換機(jī)制存在研究空白.對(duì)于使用超低延遲SSD的工作，這類(lèi)工作主要針對(duì)文件系統(tǒng)的I/O 操作進(jìn)行優(yōu)化，而對(duì)于頁(yè)交換操作缺乏針對(duì)性.本文首先針對(duì)超低延遲SSD 的特性?xún)?yōu)化Linux 頁(yè)交換機(jī)制，實(shí)現(xiàn)開(kāi)銷(xiāo)更低的頁(yè)交換機(jī)制Ultraswap，包括實(shí)現(xiàn)輕量級(jí)的I/O 棧以及更為優(yōu)化的交換路徑.

2 頁(yè)交換機(jī)制分析

本節(jié)將首先介紹頁(yè)交換機(jī)制的整體流程，然后分別對(duì)頁(yè)交換機(jī)制的頁(yè)換入路徑與頁(yè)換出路徑進(jìn)行分析并給出測(cè)試結(jié)果.

圖1 為頁(yè)交換機(jī)制整體架構(gòu)圖，頁(yè)交換機(jī)制由多層組成，包括交換邏輯層、多隊(duì)列塊層以及設(shè)備驅(qū)動(dòng)層.交換邏輯層提供頁(yè)換入與頁(yè)換出過(guò)程中，頁(yè)面選擇算法的實(shí)現(xiàn)以及對(duì)交換緩存的處理；多隊(duì)列塊層提供操作系統(tǒng)級(jí)別的塊請(qǐng)求/響應(yīng)管理和I/O 合并與調(diào)度機(jī)制；設(shè)備驅(qū)動(dòng)層負(fù)責(zé)處理設(shè)備上I/O 請(qǐng)求的提交和完成.

圖1 頁(yè)交換機(jī)制整體架構(gòu)圖Fig.1 Overview of the swapping mechanism frame diagram

2.1 頁(yè)換入路徑

當(dāng)應(yīng)用訪(fǎng)問(wèn)到不在內(nèi)存中的頁(yè)面時(shí)，會(huì)觸發(fā)缺頁(yè)異常，從用戶(hù)態(tài)進(jìn)入內(nèi)核態(tài).此時(shí)只有從交換分區(qū)中將該頁(yè)面取回內(nèi)存后，才能返回用戶(hù)態(tài)繼續(xù)執(zhí)行.算法1 描述了頁(yè)換入算法的整體流程.

算法1.頁(yè)換入算法.

① functiondo_swap_page（）

②page←查找交換緩存；

③ if（交換緩存中不存在頁(yè)面）

④page←swapin_readahead（）；

⑤ end if

⑥ 為頁(yè)面生成頁(yè)表項(xiàng)；

⑦ 添加頁(yè)面反向映射關(guān)系；

⑧ end function

⑨ functionswapin_readahead（）

⑩ra_info←獲得需要換入的頁(yè)面范圍；

? 開(kāi)啟塊層蓄流機(jī)制；

? for（每一個(gè)ra_info中的頁(yè)面page）

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

? if（page_allocated==true）

?swap_readpage（page）；

? end if

? end for

? 結(jié)束塊層蓄流機(jī)制；

? 將page插入頁(yè)面鏈表；

? end function

? functionswap_readpage（page）

?bio←生成塊層頁(yè)面I/O 信息，記錄回調(diào)函數(shù)為end_read_func；

?submit_bio(bio)；

? end function

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

如果交換緩存中沒(méi)有找到對(duì)應(yīng)頁(yè)面，內(nèi)核會(huì)調(diào)用函數(shù)swapin_readahead向設(shè)備發(fā)送讀請(qǐng)求.為了減少發(fā)生缺頁(yè)異常的次數(shù)，內(nèi)核將發(fā)生缺頁(yè)異常的關(guān)鍵頁(yè)面附近的頁(yè)面一并取回，即進(jìn)行預(yù)取操作.對(duì)于使用SSD 的情況，由于SSD 比磁盤(pán)擁有更好的隨機(jī)讀性能，Linux 內(nèi)核中將取回與關(guān)鍵頁(yè)的物理地址臨近的幾個(gè)頁(yè)面，而非在設(shè)備上連續(xù)的幾個(gè)頁(yè)面.在設(shè)備完成頁(yè)面的讀請(qǐng)求之后，內(nèi)核為取回的缺頁(yè)創(chuàng)建頁(yè)表項(xiàng)及反向映射，完成缺頁(yè)異常（算法1 的行⑥⑦）.

水解大麻籽蛋白富含精氨酸、天冬氨酸等，這在其他水解蛋白質(zhì)原料中是少見(jiàn)的，可用作護(hù)膚品的保濕劑、營(yíng)養(yǎng)劑和調(diào)理劑，也可用作頭發(fā)調(diào)理劑。

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

2）多隊(duì)列塊層.內(nèi)核通過(guò)調(diào)用函數(shù)swap_readpage向設(shè)備發(fā)送每個(gè)頁(yè)面的讀請(qǐng)求.對(duì)每個(gè)頁(yè)面，內(nèi)核為該頁(yè)面生成一個(gè)bio結(jié)構(gòu)體，記錄該讀操作完成后的回調(diào)函數(shù)end_read_func，調(diào)用函數(shù)submit_bio將該頁(yè)面的讀請(qǐng)求發(fā)送到Linux 的塊層.

圖2 表示向多隊(duì)列塊層和NVMe 驅(qū)動(dòng)發(fā)送I/O請(qǐng)求的處理流程.在塊層中，函數(shù)submit_bio提交的bio結(jié)構(gòu)體會(huì)被轉(zhuǎn)換為request結(jié)構(gòu)體，并將request結(jié)構(gòu)體插入每個(gè)核對(duì)應(yīng)的請(qǐng)求隊(duì)列中，在隊(duì)列中執(zhí)行I/O 合并和調(diào)度操作.request結(jié)構(gòu)體依次通過(guò)每個(gè)核對(duì)應(yīng)的軟件隊(duì)列和硬件隊(duì)列，進(jìn)入設(shè)備驅(qū)動(dòng)層.

圖2 多隊(duì)列塊層及NVMe 驅(qū)動(dòng)圖Fig.2 Diagram of multi-queue block layer & NVMe driver

I/O 合并和調(diào)度操作是將符合條件的多個(gè)I/O 請(qǐng)求合并成單個(gè)I/O 請(qǐng)求進(jìn)行處理.在Linux 內(nèi)核中，在從bio結(jié)構(gòu)體到向驅(qū)動(dòng)發(fā)送command的過(guò)程中，主要會(huì)發(fā)生2 次I/O 合并，分別為蓄流過(guò)程和調(diào)度過(guò)程.

每個(gè)進(jìn)程都有一個(gè)蓄流隊(duì)列.如果進(jìn)程向通用塊層發(fā)送I/O 請(qǐng)求前開(kāi)啟了蓄流功能，請(qǐng)求會(huì)被保存在隊(duì)列中進(jìn)行合并，直到泄流開(kāi)啟，請(qǐng)求才會(huì)被發(fā)送到下層的調(diào)度器中.蓄流過(guò)程的另外一個(gè)功能是生成request結(jié)構(gòu)體.當(dāng)進(jìn)程發(fā)送一個(gè)bio結(jié)構(gòu)體，會(huì)首先嘗試將bio結(jié)構(gòu)體合并進(jìn)蓄流隊(duì)列里的request結(jié)構(gòu)體，如果無(wú)法合并，則生成一個(gè)新的request結(jié)構(gòu)體.在泄流的過(guò)程中，請(qǐng)求會(huì)被發(fā)送到下層調(diào)度算法的隊(duì)列中，實(shí)現(xiàn)進(jìn)一步合并.電梯調(diào)度算法的主要目的是將request結(jié)構(gòu)體對(duì)硬件的訪(fǎng)問(wèn)順序化，并發(fā)送到下層的驅(qū)動(dòng)層執(zhí)行I/O 請(qǐng)求.

3）設(shè)備驅(qū)動(dòng)層.在硬件隊(duì)列，內(nèi)核使用函數(shù)nvme_queue_rq將請(qǐng)求分配給設(shè)備驅(qū)動(dòng)層.每個(gè)NVMe 隊(duì)列都由一個(gè)提交隊(duì)列和一個(gè)完成隊(duì)列成對(duì)組成.每個(gè)request結(jié)構(gòu)體在提交的過(guò)程中，會(huì)被轉(zhuǎn)變成command結(jié)構(gòu)體發(fā)送到提交隊(duì)列，進(jìn)行設(shè)備I/O.完成I/O 請(qǐng)求的服務(wù)后，NVMe 控制器通過(guò)向主機(jī)發(fā)送消息信號(hào)中斷（message signaled interrupts，MSI）來(lái)通知內(nèi)核數(shù)據(jù)傳輸完成.

2.2 頁(yè)換出路徑

當(dāng)內(nèi)存不足的時(shí)候，內(nèi)核需要進(jìn)行頁(yè)面回收，從而釋放頁(yè)幀，使得有空閑的內(nèi)存可以被使用.頁(yè)面回收過(guò)程需要確定哪些頁(yè)可以從內(nèi)存換出且對(duì)內(nèi)核性能影響較小.

頁(yè)面回收過(guò)程主要在2 種情況下觸發(fā)：1）如果進(jìn)行內(nèi)存分配時(shí)沒(méi)有足夠的空閑內(nèi)存，立即觸發(fā)內(nèi)存回收；2）內(nèi)核存在周期性回收內(nèi)存機(jī)制，對(duì)系統(tǒng)內(nèi)存進(jìn)行周期性檢查.在頁(yè)交換過(guò)程中，缺頁(yè)異常同樣會(huì)涉及內(nèi)存分配，因此在完成頁(yè)換入的關(guān)鍵路徑上，內(nèi)核會(huì)對(duì)空閑內(nèi)存的剩余情況進(jìn)行檢查.如果此時(shí)空閑內(nèi)存剩余不足，則觸發(fā)直接頁(yè)面回收.

在觸發(fā)頁(yè)面回收之后，需要選擇內(nèi)存中的頁(yè)面進(jìn)行回收.在每個(gè)內(nèi)存節(jié)點(diǎn)，內(nèi)核采用最近最少使用（least recently used，LRU）鏈表指向物理內(nèi)存頁(yè)面.根據(jù)局部性原理，頁(yè)面鏈表假定最近最少使用的頁(yè)面在較短的時(shí)間內(nèi)不會(huì)頻繁使用，因而可以選出需要回收的頁(yè)面.內(nèi)核會(huì)對(duì)鏈表進(jìn)行掃描，刷新活躍鏈表和不活躍鏈表.內(nèi)核通過(guò)掃描不活躍鏈表，主要進(jìn)行2個(gè)操作：為可以回收的頁(yè)面發(fā)送寫(xiě)請(qǐng)求和釋放寫(xiě)請(qǐng)求完成的頁(yè)面.算法2 展示了頁(yè)換出算法的整體流程.

算法2.頁(yè)換出算法.

① functionshrink_page_list（頁(yè)面鏈表）

② while（頁(yè)面鏈表非空）

③page←獲得頁(yè)面鏈表中的1 個(gè)頁(yè)面；

④ if（頁(yè)面不在交換緩存中）

⑤ 分配頁(yè)面交換槽位；

⑥ 解除頁(yè)面映射；

⑦swap_writepage（page）；

⑧ end if

⑨ if（頁(yè)面完成回寫(xiě)）

⑩ 直接釋放頁(yè)面；

? end if

? end while

? end function

? functionswap_writepage（page）

?bio←生成塊層頁(yè)面I/O 信息，記錄回調(diào)函數(shù)end_write_func；

?submit_bio（bio）；

? end function

對(duì)于鏈表中的頁(yè)面，如果沒(méi)有被保存在交換緩存中，則需要對(duì)該頁(yè)進(jìn)行回收操作（算法2 的行④～⑥）.內(nèi)核會(huì)為該頁(yè)面分配交換分區(qū)的空閑槽位，并將其加入交換緩存.函數(shù)add_to_swap根據(jù)交換分區(qū)的槽位位圖，為換出頁(yè)選擇一個(gè)空閑槽位，并將交換分區(qū)和槽位信息保存在該頁(yè)面的結(jié)構(gòu)體中，便于頁(yè)換入時(shí)查找頁(yè)面.內(nèi)核在將頁(yè)面放入交換緩存且為該頁(yè)面分配槽位之后，會(huì)解除該頁(yè)面與用戶(hù)空間的映射并調(diào)用函數(shù)swap_writepage向塊層發(fā)送寫(xiě)請(qǐng)求.

掃描匿名頁(yè)表的第2 個(gè)目的是回收頁(yè)框（算法2的行⑨～?）.對(duì)于沒(méi)有回寫(xiě)完成的頁(yè)面，內(nèi)核會(huì)繼續(xù)將其保留在不活躍鏈表中.對(duì)于已經(jīng)回寫(xiě)完成的頁(yè)面，內(nèi)核將釋放頁(yè)框，釋放該頁(yè)面的鎖，完成頁(yè)面回收流程.

在函數(shù)swap_writepage中，與頁(yè)換入機(jī)制類(lèi)似，內(nèi)核首先為需要進(jìn)行I/O 的頁(yè)面分配bio結(jié)構(gòu)體，調(diào)用函數(shù)submit_bio將其向Linux 的塊層發(fā)送.頁(yè)換出機(jī)制在塊層和設(shè)備驅(qū)動(dòng)層的操作與頁(yè)換入機(jī)制相同.

2.3 頁(yè)交換機(jī)制測(cè)試

結(jié)合2.1 節(jié)對(duì)頁(yè)換入路徑與2.2 節(jié)對(duì)頁(yè)換出路徑的描述，表2 對(duì)頁(yè)換入路徑的操作進(jìn)行整理，并對(duì)每個(gè)操作的內(nèi)核時(shí)間占比進(jìn)行統(tǒng)計(jì).

Table 2 Performance Analysis of Swapping Mechanism in Read Path表2 頁(yè)換入機(jī)制性能分析

表2 的測(cè)試結(jié)果表明，在使用超低延遲SSD 的情況下，頁(yè)換入路徑上多隊(duì)列塊層的時(shí)間可達(dá)到整體內(nèi)核時(shí)間的64%，是設(shè)備延遲的5.2 倍.表3 對(duì)頁(yè)換出路徑的操作進(jìn)行分析.測(cè)試結(jié)果表明，頁(yè)換出路徑上多隊(duì)列塊層的內(nèi)核時(shí)間占比達(dá)到56.9%，是設(shè)備I/O延遲的5.0 倍.以執(zhí)行kmeans 應(yīng)用為例，該應(yīng)用使用sklearn 庫(kù)對(duì)1 500 萬(wàn)個(gè)樣本進(jìn)行分類(lèi).在全內(nèi)存的情況下，應(yīng)用執(zhí)行完成的時(shí)間為238 s.當(dāng)可使用內(nèi)存為所需內(nèi)存的60%時(shí)，應(yīng)用執(zhí)行完成的時(shí)間增加至527 s，增加的時(shí)間即為執(zhí)行頁(yè)交換機(jī)制的時(shí)間.其中，塊層所占時(shí)間為162 s，占頁(yè)交換機(jī)制執(zhí)行時(shí)間的56%.

對(duì)于頁(yè)換入路徑，主要問(wèn)題在于Linux 頁(yè)交換機(jī)制的隊(duì)頭阻塞問(wèn)題、缺頁(yè)異常的關(guān)鍵路徑上的中斷處理過(guò)程，以及I/O 合并和調(diào)度機(jī)制導(dǎo)致內(nèi)核軟件開(kāi)銷(xiāo)過(guò)大.

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

其次，現(xiàn)在Linux 中的多隊(duì)列塊層為每個(gè)CPU提供一個(gè)中斷隊(duì)列，即當(dāng)I/O 完成后會(huì)發(fā)送中斷信號(hào)來(lái)通知I/O 完成.因?yàn)槿表?yè)異常返回前需要保證關(guān)鍵頁(yè)的I/O 完成，因此中斷會(huì)發(fā)生在缺頁(yè)異常的關(guān)鍵路徑上，為缺頁(yè)異常的整體過(guò)程增加了13%～26%內(nèi)核時(shí)間開(kāi)銷(xiāo).

此外，內(nèi)核會(huì)將每個(gè)頁(yè)面的讀請(qǐng)求加入到蓄流隊(duì)列.在所有頁(yè)面的請(qǐng)求發(fā)出之后，再集中泄流到驅(qū)動(dòng)隊(duì)列.多隊(duì)列塊層的合并操作雖然可以減少I(mǎi)/O 操作的總數(shù)，但是合并過(guò)程需要消耗許多CPU 周期來(lái)搜索軟件隊(duì)列，進(jìn)一步延長(zhǎng)了關(guān)鍵頁(yè)讀請(qǐng)求的等待時(shí)間開(kāi)銷(xiāo).

與頁(yè)換入路徑類(lèi)似，頁(yè)換出機(jī)制在塊層同樣值得優(yōu)化.然而，由于頁(yè)換出路徑部分并不需要區(qū)分關(guān)鍵頁(yè)面與其他頁(yè)面.因此，我們可以考慮去除I/O 合并和調(diào)度機(jī)制，實(shí)現(xiàn)更輕量級(jí)的寫(xiě)請(qǐng)求.值得一提的是，在觸發(fā)缺頁(yè)異常的頁(yè)面需要進(jìn)行內(nèi)存分配時(shí)，會(huì)對(duì)空閑內(nèi)存的情況進(jìn)行檢查.如果空閑內(nèi)存不足，內(nèi)核會(huì)進(jìn)行直接頁(yè)面回收，影響缺頁(yè)異常的返回，延長(zhǎng)應(yīng)用的等待時(shí)間.

3 Ultraswap 設(shè)計(jì)

本節(jié)介紹基于超低延遲SSD 開(kāi)發(fā)的內(nèi)核頁(yè)交換機(jī)制Ultraswap，該機(jī)制包括一個(gè)輕量級(jí)的I/O 棧，該I/O 棧將Linux 中的塊層進(jìn)一步簡(jiǎn)化，進(jìn)而降低頁(yè)交換機(jī)制的軟件開(kāi)銷(xiāo).此外，本節(jié)還將介紹Ultraswap 對(duì)于交換路徑的優(yōu)化工作.圖3 展示了Ultraswap 的整體設(shè)計(jì)圖.

圖3 Ultraswap 整體設(shè)計(jì)圖Fig.3 Overview design drawing of Ultraswap

Ultraswap 主要進(jìn)行2 方面改進(jìn)：

1） 在I/O 棧部分，首先取消了I/O 合并和調(diào)度機(jī)制.讀請(qǐng)求會(huì)被直接發(fā)送到驅(qū)動(dòng)層進(jìn)行設(shè)備I/O，從而降低請(qǐng)求的等待時(shí)間.其次，考慮到Linux 塊層的隊(duì)頭阻塞問(wèn)題，Ultraswap 的I/O 棧實(shí)現(xiàn)了對(duì)中斷和輪詢(xún)請(qǐng)求的處理.一方面，中斷與輪詢(xún)請(qǐng)求使用2 個(gè)不同的隊(duì)列，可以避免隊(duì)頭阻塞問(wèn)題.另一方面，考慮到中斷對(duì)關(guān)鍵路徑的影響，使用輪詢(xún)請(qǐng)求的方式可以降低關(guān)鍵路徑上的中斷開(kāi)銷(xiāo).

2） 在交換路徑部分主要進(jìn)行了2 部分優(yōu)化.首先，在頁(yè)換入過(guò)程中，區(qū)分觸發(fā)缺頁(yè)異常的關(guān)鍵頁(yè)面與預(yù)取頁(yè)面，使用輪詢(xún)請(qǐng)求處理關(guān)鍵頁(yè)面，并優(yōu)先發(fā)送關(guān)鍵頁(yè)面的讀請(qǐng)求.另一方面，增加對(duì)關(guān)鍵路徑上直接內(nèi)存回收的處理.考慮到內(nèi)存不足時(shí)直接內(nèi)存回收的處理會(huì)影響缺頁(yè)異常的完成，將直接內(nèi)存回收提交給一個(gè)專(zhuān)門(mén)的CPU 進(jìn)行處理，從而降低應(yīng)用的等待時(shí)間.

3.1 I/O 棧設(shè)計(jì)

在Linux 頁(yè)交換機(jī)制中，所有頁(yè)的讀寫(xiě)請(qǐng)求都會(huì)通過(guò)多隊(duì)列塊層被放入當(dāng)前CPU 對(duì)應(yīng)的中斷隊(duì)列.對(duì)Ultraswap 而言，想要實(shí)現(xiàn)輕量級(jí)的I/O 棧，首先需要解決Linux 中的I/O 合并和調(diào)度問(wèn)題，其次需要實(shí)現(xiàn)對(duì)輪詢(xún)請(qǐng)求的支持.

圖4 展示了Ultraswap 的I/O 棧中對(duì)請(qǐng)求的發(fā)送流程圖.圖4 箭頭①為L(zhǎng)inux 的通用塊層的流程.當(dāng)頁(yè)交換機(jī)制希望提交I/O 請(qǐng)求時(shí)，會(huì)先構(gòu)造bio結(jié)構(gòu)體.bio結(jié)構(gòu)體會(huì)首先與隊(duì)列中已有的request結(jié)構(gòu)體進(jìn)行合并，如果不能合并則生成新的request結(jié)構(gòu)體.隊(duì)列中的request結(jié)構(gòu)體經(jīng)過(guò)調(diào)度之后，被放入當(dāng)前CPU 的軟件隊(duì)列和硬件隊(duì)列.之后，request結(jié)構(gòu)體轉(zhuǎn)變?yōu)閏ommand結(jié)構(gòu)體放入對(duì)應(yīng)NVMe 中斷隊(duì)列，進(jìn)行設(shè)備I/O.

圖4 Ultraswap 請(qǐng)求發(fā)送流程圖Fig.4 Overview of request sending in Ultraswap

由于利用超低延遲SSD 進(jìn)行存儲(chǔ)的I/O 調(diào)度程序要么無(wú)濟(jì)于事，要么顯著增加請(qǐng)求延遲，同時(shí)還會(huì)對(duì)吞吐量和能效產(chǎn)生負(fù)面影響[16].因此，我們考慮直接由bio結(jié)構(gòu)體構(gòu)造request結(jié)構(gòu)體，并最終直接構(gòu)造command結(jié)構(gòu)體放入驅(qū)動(dòng)隊(duì)列，進(jìn)行設(shè)備I/O，從而盡可能地減少內(nèi)核軟件開(kāi)銷(xiāo)（圖4 箭頭②）.

事實(shí)上，對(duì)于Ultraswap 中的中斷情況，在設(shè)備I/O 完成進(jìn)入中斷處理函數(shù)時(shí)，會(huì)根據(jù)完成中斷的請(qǐng)求找到其request結(jié)構(gòu)體，并對(duì)request中的每個(gè)bio結(jié)構(gòu)體調(diào)用請(qǐng)求處理函數(shù).因此，在發(fā)送中斷請(qǐng)求的函數(shù)中，Ultraswap 需要保留bio結(jié)構(gòu)體和request結(jié)構(gòu)體，僅僅去掉不必要的I/O 合并和調(diào)度操作.

對(duì)于輪詢(xún)請(qǐng)求，則可以使用更為簡(jiǎn)單的方式.輪詢(xún)完成的處理過(guò)程并不需要使用request結(jié)構(gòu)體和bio結(jié)構(gòu)體.因此，輪詢(xún)請(qǐng)求函數(shù)可以根據(jù)需要進(jìn)行讀寫(xiě)的頁(yè)面地址，直接構(gòu)造command結(jié)構(gòu)體向NVMe 輪詢(xún)隊(duì)列發(fā)送請(qǐng)求（圖4 箭頭③）.

針對(duì)上述描述，Ultraswap 的I/O 棧提供了3 種請(qǐng)求函數(shù)，圖5 為這3 種函數(shù)的示意圖.圖5（a）為輪詢(xún)請(qǐng)求.當(dāng)請(qǐng)求發(fā)送到設(shè)備后，CPU 會(huì)一直進(jìn)行輪詢(xún)，直到設(shè)備I/O 完成.圖5（b）為中斷請(qǐng)求處理過(guò)程，在發(fā)送請(qǐng)求之后，如果I/O 完成，內(nèi)核會(huì)收到中斷信號(hào)并進(jìn)入中斷處理過(guò)程.考慮到輪詢(xún)處理過(guò)程會(huì)大量占用CPU，因而圖5（c）將輪詢(xún)請(qǐng)求的發(fā)送過(guò)程和輪詢(xún)過(guò)程進(jìn)行拆分，使得在發(fā)送輪詢(xún)請(qǐng)求后可以進(jìn)行其他步驟的處理后再輪詢(xún)等待I/O 完成.

圖5 Ultraswap 接口函數(shù)示意圖Fig.5 Illustration of Ultraswap API functions

3.2 交換路徑優(yōu)化設(shè)計(jì)

在處理缺頁(yè)異常的過(guò)程中，主要會(huì)碰到4 個(gè)問(wèn)題：

1） 頁(yè)面的讀請(qǐng)求在NVMe 隊(duì)列中會(huì)按地址順序處理，由于每個(gè)CPU 只有一個(gè)隊(duì)列，這導(dǎo)致關(guān)鍵頁(yè)的讀請(qǐng)求前可能存在其他預(yù)取頁(yè)的請(qǐng)求，從而導(dǎo)致隊(duì)頭阻塞問(wèn)題.

2） Linux 的頁(yè)交換機(jī)制存在I/O 合并和調(diào)度操作，導(dǎo)致關(guān)鍵頁(yè)的讀請(qǐng)求可能會(huì)被合并或調(diào)度到別的請(qǐng)求之后，這個(gè)問(wèn)題已經(jīng)在Ultraswap 的I/O 棧實(shí)現(xiàn)中被優(yōu)化.

3） 現(xiàn)在的Linux 塊層隊(duì)列均為中斷隊(duì)列，在缺頁(yè)異常完成之前需要處理關(guān)鍵頁(yè)的I/O 中斷，延后了缺頁(yè)異常返回的時(shí)間.

4） 在關(guān)鍵頁(yè)處理完成之后，內(nèi)核需要進(jìn)行空閑內(nèi)存檢查.如果空閑內(nèi)存不足，需要進(jìn)行直接內(nèi)存回收操作，待內(nèi)存回收操作結(jié)束后才會(huì)繼續(xù)執(zhí)行應(yīng)用.

圖6（a）展示了Linux 頁(yè)交換機(jī)制對(duì)缺頁(yè)異常的處理過(guò)程.當(dāng)觸發(fā)缺頁(yè)異常，內(nèi)核會(huì)按照地址順序依此發(fā)送讀請(qǐng)求，并在塊層進(jìn)行蓄流.請(qǐng)求會(huì)在蓄流結(jié)束后被送到設(shè)備進(jìn)行I/O.I/O 完成后，設(shè)備通過(guò)觸發(fā)中斷令CPU 對(duì)請(qǐng)求進(jìn)行處理.如果此時(shí)空閑內(nèi)存不足，Linux 還將會(huì)進(jìn)行直接頁(yè)面回收.在上述步驟完成后，Linux 頁(yè)交換機(jī)制才會(huì)從內(nèi)核態(tài)返回用戶(hù)態(tài)，繼續(xù)執(zhí)行應(yīng)用.

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

針對(duì)上述問(wèn)題，Ultraswap 的交換路徑優(yōu)化設(shè)計(jì)如下：

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

其次，通過(guò)修改內(nèi)核，本文對(duì)關(guān)鍵頁(yè)和預(yù)取頁(yè)進(jìn)行分別處理.當(dāng)進(jìn)入函數(shù)swapin_readahead時(shí)，會(huì)首先發(fā)送關(guān)鍵頁(yè)的輪詢(xún)請(qǐng)求至設(shè)備的NVMe 驅(qū)動(dòng)隊(duì)列.接下來(lái)對(duì)于所有需要預(yù)取的頁(yè)面，內(nèi)核會(huì)依次發(fā)送對(duì)應(yīng)該頁(yè)面的中斷請(qǐng)求.當(dāng)發(fā)送完中斷請(qǐng)求之后，內(nèi)核會(huì)進(jìn)行輪詢(xún)操作，等待關(guān)鍵頁(yè)的I/O 完成，如圖6(b）所示.通過(guò)先發(fā)送關(guān)鍵頁(yè)的讀請(qǐng)求，我們可以在設(shè)備讀入關(guān)鍵頁(yè)的同時(shí)，進(jìn)行預(yù)取頁(yè)的頁(yè)框分配和發(fā)送預(yù)取頁(yè)的讀請(qǐng)求，從而可以充分利用設(shè)備的I/O 時(shí)間.事實(shí)上，在我們的實(shí)驗(yàn)中發(fā)現(xiàn)，絕大多數(shù)輪詢(xún)請(qǐng)求的I/O 在發(fā)送完成預(yù)取請(qǐng)求之后已經(jīng)完成，因此對(duì)CPU 開(kāi)銷(xiāo)的影響可以忽略不計(jì).

對(duì)于頁(yè)面回收過(guò)程中Ultraswap I/O 棧請(qǐng)求函數(shù)的選擇，由于內(nèi)核可以將I/O 未完成的頁(yè)面重新加入頁(yè)面鏈表，選擇將上一次頁(yè)面回收過(guò)程中被加入頁(yè)面鏈表的頁(yè)框釋放，并不需要等待本次回收頁(yè)面的I/O 完成.因此，對(duì)于回收頁(yè)面，Ultraswap 同樣采用中斷的方式發(fā)送請(qǐng)求.

此外，在缺頁(yè)異常的處理過(guò)程中讀取頁(yè)面后，內(nèi)核會(huì)檢查內(nèi)存是否超過(guò)內(nèi)存水位線(xiàn).如果有多余的頁(yè)面，頁(yè)面將被直接回收.直接內(nèi)存回收發(fā)生在缺頁(yè)異常的上下文中，造成相當(dāng)一部分的時(shí)間開(kāi)銷(xiāo).因此本文將直接頁(yè)面回收過(guò)程指定給一個(gè)專(zhuān)門(mén)的CPU.當(dāng)內(nèi)存不足時(shí)，內(nèi)核會(huì)喚醒指定CPU 來(lái)處理頁(yè)面回收，從而當(dāng)前CPU 可以返回用戶(hù)態(tài)繼續(xù)執(zhí)行應(yīng)用.本文設(shè)置的內(nèi)存水位線(xiàn)為內(nèi)存限制的70%.如果使用的內(nèi)存超過(guò)了內(nèi)存限制，則會(huì)直接在關(guān)鍵路徑上實(shí)現(xiàn)內(nèi)存回收，而不進(jìn)行遷移.圖6（b）展示了Ultraswap 對(duì)缺頁(yè)異常優(yōu)化后的處理過(guò)程.當(dāng)觸發(fā)缺頁(yè)異常，內(nèi)核首先會(huì)將關(guān)鍵頁(yè)的輪詢(xún)請(qǐng)求直接發(fā)送到設(shè)備的輪詢(xún)隊(duì)列.接下來(lái)，內(nèi)核會(huì)依次將預(yù)取頁(yè)的請(qǐng)求發(fā)送到設(shè)備的中斷隊(duì)列.當(dāng)預(yù)取頁(yè)的請(qǐng)求發(fā)送完成，內(nèi)核會(huì)對(duì)輪詢(xún)隊(duì)列進(jìn)行輪詢(xún)操作，直到關(guān)鍵頁(yè)的請(qǐng)求完成.隨后，如果空閑內(nèi)存不足，Ultraswap 會(huì)調(diào)用另一個(gè)CPU進(jìn)行頁(yè)面回收操作.在上述步驟完成后，Ultraswap 即可從內(nèi)核態(tài)返回用戶(hù)態(tài)，繼續(xù)應(yīng)用的執(zhí)行.

4 測(cè)評(píng)與分析

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

4.1 測(cè)試環(huán)境

本文測(cè)試使用1 臺(tái)帶有英特爾Optane SSD 的服務(wù)器進(jìn)行頁(yè)交換機(jī)制性能測(cè)試，其硬件指標(biāo)如表4所示.

Table 4 Test Environment for Swapping Mechanism表4 頁(yè)交換機(jī)制測(cè)試環(huán)境

為了更靈活地控制內(nèi)存使用以及觸發(fā)頁(yè)交換機(jī)制，本文使用了Linux 控制組（control groups, cgroups）.cgroups 可以用來(lái)限制和控制一個(gè)進(jìn)程組的資源，包括CPU、內(nèi)存和設(shè)備I/O 等.本文使用cgroups 對(duì)測(cè)試過(guò)程中可使用的物理內(nèi)存進(jìn)行限制，超過(guò)物理內(nèi)存的部分會(huì)通過(guò)頁(yè)交換機(jī)制被放入交換分區(qū).

4.2 讀寫(xiě)性能測(cè)試

本節(jié)主要對(duì)Ultraswap 的I/O 棧接口函數(shù)進(jìn)行性能測(cè)試，并將其與Linux 中的頁(yè)交換讀寫(xiě)函數(shù)進(jìn)行比較.此外，利用fronswap 接口，本文還實(shí)現(xiàn)了以DRAM為存儲(chǔ)設(shè)備的I/O 棧，該I/O 棧通過(guò)直接進(jìn)行memcpy操作將頁(yè)面交換到內(nèi)存中不被cgroups 限制的另一塊區(qū)域.這種方式將I/O 需要的軟硬件開(kāi)銷(xiāo)降至最低，因此本文將以DRAM 為存儲(chǔ)設(shè)備的頁(yè)交換方式作為頁(yè)交換的理想化情況并進(jìn)行測(cè)試.

本節(jié)分3 步對(duì)Ultraswap（輪詢(xún)）、Ultraswap（中斷）和DRAM 這3 種I/O 棧進(jìn)行讀寫(xiě)測(cè)試.1）分配一個(gè)100 MB 的char 類(lèi)型數(shù)組，利用cgroups 工具將可使用的物理內(nèi)存限制到50 MB.2）對(duì)這個(gè)數(shù)組的每一項(xiàng)先寫(xiě)入一遍字符，觸發(fā)頁(yè)換出過(guò)程.3）遍歷數(shù)組的每一項(xiàng)，觸發(fā)頁(yè)換入過(guò)程并進(jìn)行正確性驗(yàn)證.該測(cè)試均在單線(xiàn)程環(huán)境下完成，統(tǒng)計(jì)每部分操作的延遲.

圖7 展示了在3 種I/O 棧中發(fā)送讀/寫(xiě)請(qǐng)求的延遲.測(cè)試結(jié)果表明，在單線(xiàn)程環(huán)境下，2 種Ultraswap的輪詢(xún)請(qǐng)求處理過(guò)程相比Linux 在讀/寫(xiě)操作上分別提升了78%和72%.原因在于Ultraswap 發(fā)送輪詢(xún)請(qǐng)求的過(guò)程中可以完全繞過(guò)塊層，直接通過(guò)NVMe 驅(qū)動(dòng)向設(shè)備發(fā)送I/O 請(qǐng)求.此外，當(dāng)CPU 輪詢(xún)到請(qǐng)求完成時(shí)，可以直接調(diào)用請(qǐng)求完成處理函數(shù)，減少了中斷和上下文切換帶來(lái)的時(shí)間開(kāi)銷(xiāo).2 種Ultraswap 的中斷請(qǐng)求處理過(guò)程相比Linux 在讀/寫(xiě)上僅提升了18%和13%.原因在于：一方面，Ultraswap 僅對(duì)發(fā)送中斷請(qǐng)求的部分進(jìn)行優(yōu)化；另一方面，雖然Ultraswap 在發(fā)送請(qǐng)求的過(guò)程中減少了Linux 塊層中的I/O 合并和調(diào)度操作，但是為了保證中斷處理，仍然需要分配bio和request結(jié)構(gòu)體，造成額外開(kāi)銷(xiāo).

圖7 讀寫(xiě)性能測(cè)試結(jié)果Fig.7 Results of read and write performance

4.3 應(yīng)用負(fù)載測(cè)試

本節(jié)對(duì)4.2 節(jié)中3 種I/O 棧進(jìn)行性能測(cè)試.測(cè)試包括5 個(gè)應(yīng)用，分別為quicksort，kmeans，tensorflow，pagerank，linpack.quicksort 應(yīng)用使用C++標(biāo)準(zhǔn)庫(kù)對(duì) 8 GB 的整數(shù)進(jìn)行快速排序；kmeans 應(yīng)用使用sklearn 庫(kù)對(duì)1 500 萬(wàn)個(gè)樣本進(jìn)行分類(lèi)；tensorflow 應(yīng)用對(duì)用于基準(zhǔn)測(cè)試的inception 樣例進(jìn)行計(jì)算；pagerank 應(yīng)用使用包含65.5萬(wàn)個(gè)節(jié)點(diǎn)和750 萬(wàn)條邊的數(shù)據(jù)集進(jìn)行測(cè)試；linpack 應(yīng)用是一個(gè)線(xiàn)性代數(shù)性能基準(zhǔn)測(cè)試，使用英特爾提供的二進(jìn)制文件.表5 展示這5 個(gè)應(yīng)用需要使用的內(nèi)存和核數(shù).

Table 5 Basic Information of Application表5 應(yīng)用基本情況

根據(jù)應(yīng)用需要的內(nèi)存上限，將可使用的內(nèi)存比例限制到100%，80%，60%，40%，20%，記錄應(yīng)用執(zhí)行完成的時(shí)間，多次執(zhí)行并計(jì)算平均時(shí)間.當(dāng)可使用的內(nèi)存比例為100%時(shí)，應(yīng)用不觸發(fā)頁(yè)交換機(jī)制.則當(dāng)對(duì)內(nèi)存比例進(jìn)行限制，增加的應(yīng)用完成時(shí)間可以認(rèn)為是頁(yè)交換機(jī)制的執(zhí)行時(shí)間.本文將可使用內(nèi)存比例為100%的應(yīng)用平均執(zhí)行時(shí)間作為基準(zhǔn)時(shí)間，對(duì)不同內(nèi)存比例下的應(yīng)用執(zhí)行時(shí)間進(jìn)行標(biāo)準(zhǔn)化處理.

圖8 展示3 種I/O 棧的應(yīng)用測(cè)試結(jié)果，當(dāng)可使用內(nèi)存比例為100%時(shí)應(yīng)用不觸發(fā)頁(yè)交換機(jī)制，我們將此時(shí)的應(yīng)用執(zhí)行時(shí)間標(biāo)注在圖上.測(cè)試結(jié)果表明，在5 種應(yīng)用上Ultraswap 均表現(xiàn)出較好的頁(yè)交換性能.quicksort，kmeans，tensorflow，pagerank，linpack 應(yīng)用的平均性能提升為9%，19%，10%，13%，15%.當(dāng)可使用內(nèi)存比例為20% 時(shí)，這5 個(gè)應(yīng)用可達(dá)到15%，33%，22%，18%，19% 的性能提升.與理想化情況相比，Ultraswap 將Linux 頁(yè)交換機(jī)制與理想情況的差距縮小至5%，25%，18%，22%，40%，這得益于Ultraswap的I/O 棧和交換路徑優(yōu)化設(shè)計(jì).

圖8 應(yīng)用性能測(cè)試結(jié)果Fig.8 Results of application performance tests

4.4 優(yōu)化有效性測(cè)試

4.4.1 缺頁(yè)異常優(yōu)化測(cè)試

Ultraswap 中對(duì)觸發(fā)缺頁(yè)異常的關(guān)鍵頁(yè)面使用輪詢(xún)請(qǐng)求，對(duì)預(yù)取頁(yè)面和回收頁(yè)面使用中斷請(qǐng)求.本節(jié)對(duì)使用純中斷Ultraswap-interrupt-only 和純輪詢(xún)請(qǐng)求Ultraswap-poll-only 的2 種I/O 棧進(jìn)行性能測(cè)試，并與Ultraswap 的優(yōu)化方案進(jìn)行比較，以說(shuō)明Ultraswap 在缺頁(yè)異常方面優(yōu)化的合理性和有效性.

圖9 的測(cè)試結(jié)果表明，與Ultraswap 相比，在quicksort，kmeans，tensorflow，pagerank，linpack 應(yīng)用上Ultraswap-interrupt-only 的時(shí)間分別增加了2%，2%，2%，7%，4%，主要原因在于輪詢(xún)請(qǐng)求減少了關(guān)鍵路徑上的中斷處理和上下文切換時(shí)間，且CPU 處理完請(qǐng)求后即可返回應(yīng)用.

圖9 Ultraswap 缺頁(yè)異常優(yōu)化結(jié)果Fig.9 Optimization results of Ultraswap for page fault handling

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

Table 6 Number of Page Faults in Linpack with Ultraswap’s I/O Stack表6 Ultraswap I/O 棧在Linpack 應(yīng)用中觸發(fā)缺頁(yè)異常次數(shù)

4.4.2 內(nèi)存回收優(yōu)化測(cè)試

本節(jié)測(cè)試Ultraswap 中對(duì)內(nèi)存回收路徑的優(yōu)化效果.本測(cè)試將應(yīng)用的可使用內(nèi)存比例設(shè)置為50%，對(duì)遷移直接頁(yè)面回收過(guò)程前后的內(nèi)核時(shí)間占比進(jìn)行記錄和統(tǒng)計(jì)，從而評(píng)估對(duì)內(nèi)存回收路徑的優(yōu)化效果.表7顯示，優(yōu)化頁(yè)面回收路徑可以顯著減少內(nèi)核時(shí)間，使內(nèi)核時(shí)間減少多達(dá)35.3%.

Table 7 Performance of Memory Reclaimation Optimization表7 內(nèi)存回收優(yōu)化性能s

5 總 結(jié)

頁(yè)交換機(jī)制是用于內(nèi)存擴(kuò)展的經(jīng)典技術(shù)，該機(jī)制通過(guò)將較少使用的內(nèi)存頁(yè)面保存在存儲(chǔ)設(shè)備，從而達(dá)到擴(kuò)展內(nèi)存的目的.過(guò)去頁(yè)交換機(jī)制一直受限于慢速磁盤(pán)的讀寫(xiě)速度，因而無(wú)法廣泛應(yīng)用.近年來(lái)，隨著超低延遲SSD 的快速發(fā)展，頁(yè)交換機(jī)制可以利用其低延遲的讀寫(xiě)特性來(lái)改善頁(yè)交換效率.

本文首先對(duì)Linux 頁(yè)交換機(jī)制的頁(yè)換入和頁(yè)換出路徑進(jìn)行分析和評(píng)測(cè).測(cè)試結(jié)果表明，在使用超低延遲SSD 的情況下，Linux 塊層和設(shè)備驅(qū)動(dòng)層的軟件開(kāi)銷(xiāo)可達(dá)到內(nèi)核時(shí)間開(kāi)銷(xiāo)的64%.主要原因在于塊層中存在隊(duì)頭阻塞、I/O 合并和調(diào)度開(kāi)銷(xiāo)，以及關(guān)鍵路徑上的中斷時(shí)間開(kāi)銷(xiāo)問(wèn)題.同時(shí)，當(dāng)觸發(fā)缺頁(yè)異常需要分配內(nèi)存空間時(shí)，如果當(dāng)前內(nèi)核的空閑內(nèi)存不足，會(huì)觸發(fā)直接內(nèi)存回收，同樣會(huì)在缺頁(yè)異常的關(guān)鍵路徑上造成額外的時(shí)間開(kāi)銷(xiāo).

基于上述問(wèn)題，本文設(shè)計(jì)了內(nèi)核頁(yè)交換機(jī)制Ultraswap.Ultraswap 通過(guò)直接使用NVMe 驅(qū)動(dòng)、避免I/O合并和調(diào)度的方式實(shí)現(xiàn)了輕量級(jí)的I/O 棧，能夠處理讀寫(xiě)函數(shù)的輪詢(xún)和中斷請(qǐng)求.在內(nèi)核方面，Ultraswap從缺頁(yè)異常和內(nèi)存回收2 個(gè)方面進(jìn)行優(yōu)化，通過(guò)拆分請(qǐng)求隊(duì)列，混合使用輪詢(xún)和中斷請(qǐng)求、轉(zhuǎn)移直接內(nèi)存回收的方式，降低關(guān)鍵路徑上的時(shí)間開(kāi)銷(xiāo).

本文將Ultraswap 與Linux 頁(yè)交換機(jī)制進(jìn)行對(duì)比來(lái)比較性能，結(jié)果表明Ultraswap 在應(yīng)用測(cè)試場(chǎng)景下相比Linux 能夠提升19%的平均性能；與理想化情況相比，Ultraswap 能夠?qū)inux 與理想化情況的性能差距減少95%.

作者貢獻(xiàn)聲明：王紫芮提出文章思路、方案設(shè)計(jì)并撰寫(xiě)論文；蔣德鈞提出指導(dǎo)意見(jiàn)并修改論文.