在網(wǎng)存儲系統(tǒng)研究綜述

汪 慶 李俊儒 舒繼武

（清華大學計算機科學與技術系 北京 100084）

（q-wang18@mails.tsinghua.edu.cn）

傳統(tǒng)的存儲系統(tǒng)以CPU 為中心，CPU 處理所有的存儲邏輯.然而，在如今的后摩爾時代，通用CPU的處理能力難以提升，這極大限制了傳統(tǒng)存儲系統(tǒng)的性能上限.與此同時，傳統(tǒng)存儲系統(tǒng)面臨來自上層應用和下層I/O 硬件的前所未有的壓力.一方面，全球的數(shù)據(jù)量持續(xù)增長，尤其是需要實時處理的數(shù)據(jù)：據(jù)國際數(shù)據(jù)公司預測，2025 年實時性數(shù)據(jù)將達到50 ZB[1].另一方面，I/O 硬件的性能也大幅提升：高速網(wǎng)卡的帶寬已經(jīng)超過100 Gbps，如雙端口ConnectX-6 網(wǎng)卡的聚合帶寬有400 Gbps[2]；基于NVMe（non-volatile memory express）協(xié)議的閃存盤能提供百萬級的IOPS（input/output operations per second）.當傳統(tǒng)存儲系統(tǒng)嘗試利用這些高速I/O 硬件來實時處理海量數(shù)據(jù)時，CPU 不可避免地成為了系統(tǒng)瓶頸，導致I/O 硬件資源難以被充分發(fā)揮.

近些年來，以可編程交換機和智能網(wǎng)卡為代表的可編程網(wǎng)絡設備在數(shù)據(jù)中心逐漸普及，這為緩解CPU 瓶頸、構建以數(shù)據(jù)為中心的在網(wǎng)存儲系統(tǒng)（innetwork storage systems）帶來了新的機遇.可編程交換機與智能網(wǎng)卡支持用戶自定義數(shù)據(jù)處理與轉發(fā)過程，且具有天生的位置優(yōu)勢：可編程交換機是存儲服務器之間的數(shù)據(jù)交換中樞，而智能網(wǎng)卡是存儲服務器的出入口.在網(wǎng)存儲系統(tǒng)將存儲功能分工至可編程交換機或智能網(wǎng)卡上，在網(wǎng)絡通路上處理與存儲數(shù)據(jù)，因此既能夠充分發(fā)揮現(xiàn)代網(wǎng)絡硬件低延遲、高帶寬的優(yōu)勢，又能夠減少數(shù)據(jù)的移動開銷.學術界和工業(yè)界近些年設計了大量的在網(wǎng)存儲系統(tǒng)，從不同角度加速存儲任務，獲得顯著的性能提升.

本文對在網(wǎng)存儲系統(tǒng)進行綜述，主要貢獻有3 個方面：

1）從可編程網(wǎng)絡設備的硬件特性出發(fā)，總結了構建高性能在網(wǎng)存儲系統(tǒng)面臨的兩大挑戰(zhàn)：網(wǎng)絡硬件和存儲軟件如何高效分工，以及在網(wǎng)存儲系統(tǒng)如何容錯.此外，歸納了在硬件和軟件層次針對這些挑戰(zhàn)的現(xiàn)有解決方法.

2）根據(jù)可編程網(wǎng)絡設備執(zhí)行的任務，對現(xiàn)有的在網(wǎng)系統(tǒng)進行分類，包括在網(wǎng)數(shù)據(jù)緩存系統(tǒng)、在網(wǎng)數(shù)據(jù)協(xié)調(diào)系統(tǒng)、在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)以及在網(wǎng)數(shù)據(jù)聚合系統(tǒng).針對每類在網(wǎng)存儲系統(tǒng)，以具體例子分析其對應的設計難點以及軟件技術.

3）對在網(wǎng)存儲系統(tǒng)進行了展望，指出了研究人員未來需要著重對交換機與網(wǎng)卡協(xié)同、多租戶、安全以及自動卸載4 個方向進行深入探索，才能使得在網(wǎng)存儲系統(tǒng)被廣泛部署.

1 背景介紹

在網(wǎng)存儲系統(tǒng)目前主要使用可編程交換機與智能網(wǎng)卡進行存儲功能的加速，下面分別介紹它們的硬件結構以及性能特征.

1.1 可編程交換機

與功能固定的傳統(tǒng)交換機不同，可編程交換機支持用戶自定義網(wǎng)絡協(xié)議以及網(wǎng)絡包的轉發(fā)邏輯.現(xiàn)有的商用可編程交換機大多基于可重配置匹配表（reconfigurable match table，RMT）的硬件架構[3]，如圖1所示.在RMT 架構下，可編程交換機具有多條入口流水線（ingress pipeline）和出口流水線（egress pipeline）；每條流水線包含多個階段（stage）.網(wǎng)絡包首先進入某個入口流水線，按照階段順序被交換機硬件部件處理，然后被轉發(fā)至某個出口流水線，最后從對應的交換機端口流出.RMT 架構的核心可編程部件是動作-匹配表（match action table），它定義了當網(wǎng)絡包滿足什么格式時（match 字段），對網(wǎng)絡包做何種操作（action 字段）：比如，用戶可創(chuàng)建基于IP 地址的轉發(fā)表，根據(jù)網(wǎng)絡包的IP 地址字段進行網(wǎng)絡包內(nèi)容的修改以及路由.此外，RMT 架構還支持有狀態(tài)的數(shù)據(jù)存儲；具體地，交換機具有數(shù)十MB 的SRAM 空間，用戶能夠通過定義長度固定的寄存器數(shù)組（register array）來使用這些SRAM 空間，并在處理網(wǎng)絡包的過程中對寄存器數(shù)組進行讀寫.

Fig.1 Hardware architecture of RMT programmable switch圖1 RMT 可編程交換機的硬件架構

可編程交換機擁有高帶寬、低延遲的性能特征.相比于服務器網(wǎng)卡，可編程交換機的聚合帶寬能高出1 個數(shù)量級：以英特爾公司的Barefoot Tofino 系列可編程交換機[4]為例，第1 代Tofino 芯片聚合帶寬可達到6.4 Tbps，支持100 Gbps 的網(wǎng)絡端口；最新一代Tofino 3 芯片聚合帶寬可達25.6 Tbps，支持400 Gbps的網(wǎng)絡端口.可編程交換機能夠線速（line rate）轉發(fā)網(wǎng)絡包，因此其流水線內(nèi)處理邏輯的復雜度具有上限，比如不支持循環(huán)操作.

1.2 智能網(wǎng)卡

智能網(wǎng)卡是具有可編程芯片的網(wǎng)卡，用戶可自定義網(wǎng)絡包的處理過程，并可靈活地卸載通用CPU的任務.按照數(shù)據(jù)通路模式，智能網(wǎng)卡可以被分為onpath 和off-path 這2 類：在on-path 智能網(wǎng)卡中，可編程芯片位于網(wǎng)絡包收發(fā)路徑上，即每個網(wǎng)絡包都需要經(jīng)過可編程芯片處理；而在off-path 智能網(wǎng)卡中，可編程芯片在網(wǎng)絡包收發(fā)路徑之外，存在額外的交換部件來控制網(wǎng)絡包是否被送往可編程芯片.onpath 智能網(wǎng)卡由于數(shù)據(jù)通路更短，網(wǎng)絡包處理延遲比off-path 智能網(wǎng)低；然而，on-path 網(wǎng)卡通常更難以編程.

現(xiàn)有智能網(wǎng)卡配備的可編程芯片主要分為4 種：ARM CPU、網(wǎng)絡處理器（network processor，NP）、專用集成電路（application specific integrated circuit，ASIC）以及現(xiàn)場可編程門陣列（field-programmable gate array，F(xiàn)PGA），它們在性能、易用性和表達能力方面各有優(yōu)劣，如表1 所示.

Table 1 Comparison Among Four Types of SmartNICs表1 4 種智能網(wǎng)卡的對比

具體而言，基于ARM CPU 的智能網(wǎng)卡表達能力強且易于編程，這是因為ARM CPU 是通用處理器，且可以直接利用現(xiàn)有的工具鏈生態(tài)（如編程語言和編譯器）.但ARM CPU 的性能比較差，針對網(wǎng)絡包的處理能力遠不如相同頻率下的x86 架構CPU；例如，英偉達BlueField 2 智能網(wǎng)卡[5]具有8 顆ARMv8 A72 CPU 核心，運行頻率為2.0 GHz.根據(jù)我們的測試，當運行基于RDMA 的用戶態(tài)測試程序，發(fā)送/接收尺寸為64 B 的網(wǎng)絡包時，使用這8 顆ARM 核心處理網(wǎng)絡包的吞吐量只有8 顆2.2 GHz 英特爾Xeon CPU 核心的1/2.基于NP 的智能網(wǎng)卡包含大量專為網(wǎng)絡處理設計的可編程網(wǎng)絡處理核心，相比于ARM CPU，它的網(wǎng)絡處理延遲更低且并發(fā)度更高：比如Netronome的Agilio CX 網(wǎng)卡[6]具有60 個NP 核心，并且每個NP核心上能同時運行8 個獨立的硬件線程.盡管性能很高，基于NP 的智能網(wǎng)卡編程難度要高于ARM CPU，且某些處理邏輯無法表達.基于ASIC 的智能網(wǎng)卡通過高速芯片進行網(wǎng)絡處理，同時針對網(wǎng)絡、存儲、虛擬化等任務提供一定程度的可編程接口；例如英偉達ConnectX 系列智能網(wǎng)卡[7]支持上層應用自定義網(wǎng)絡流表規(guī)則.基于FPGA 的智能網(wǎng)卡直接使用FPGA處理網(wǎng)絡包，F(xiàn)PGA 性能高且表達能力強，但FPGA編程門檻比較高，典型的代表有英偉達的Innova 智能網(wǎng)卡[8]系列.更多關于智能網(wǎng)卡的介紹可參見文獻[9].值得注意的是，相比于文獻[9]，本文側重智能網(wǎng)卡和可編程交換機在存儲系統(tǒng)中的應用與加速.

2 在網(wǎng)存儲系統(tǒng)的設計挑戰(zhàn)

可編程交換機與智能網(wǎng)卡為存儲系統(tǒng)的設計帶來了巨大機遇，但同時構建高性能的在網(wǎng)絡存儲系統(tǒng)也面臨著諸多挑戰(zhàn)，其中最主要的有：1）網(wǎng)絡硬件和存儲軟件如何高效分工；2）在網(wǎng)存儲系統(tǒng)如何容錯.下面依次闡述.

2.1 網(wǎng)絡硬件和存儲軟件的分工

可編程網(wǎng)絡設備的表達能力受限，不如通用CPU.首先，它們的計算能力受限，以可編程交換機為例，為了保證線速，用戶能夠定義的操作步驟有限，不支持循環(huán)和浮點數(shù)計算，而且所有的操作必須要被表達成動作-匹配表的模式；此外，在可編程交換機中，具有依賴的操作必須被擺放在不同的流水線階段中，而流水線的總階段數(shù)有限，這進一步限制了用戶能夠表達的邏輯.其次，可編程網(wǎng)絡設備的可用內(nèi)存小：可編程交換機只具有數(shù)十MB 左右的SRAM，而智能網(wǎng)卡的內(nèi)存空間也一般不超過16 GB；此外，在可編程交換機中，SRAM 在不同流水線和不同階段之間無法被共享，導致內(nèi)存空間無法被充分利用.

但另一方面，存儲系統(tǒng)具有大量復雜邏輯.比如存儲系統(tǒng)中的分布式協(xié)議（如共識協(xié)議、分布式提交協(xié)議）需要服務器之間進行多次網(wǎng)絡消息的交互，流程復雜；存儲系統(tǒng)中的崩潰一致性機制需要對存儲介質(zhì)進行多個步驟的更新操作，保證系統(tǒng)在崩潰之后能夠恢復到一致性的狀態(tài).此外，存儲系統(tǒng)使用大量內(nèi)存空間維護狀態(tài)，比如文件系統(tǒng)需要幾十GB 甚至更大空間的頁緩存用于加速文件訪問性能.如何緩解受限的可編程網(wǎng)絡設備表達能力與復雜的存儲系統(tǒng)邏輯之間的矛盾，進行網(wǎng)絡硬件和存儲軟件之間高效分工是在網(wǎng)存儲系統(tǒng)面臨的一大挑戰(zhàn).

目前的研究工作主要通過存儲軟件抽象和網(wǎng)絡硬件擴展2 個方面應對這一挑戰(zhàn).在存儲軟件抽象方面，考慮到可編程網(wǎng)絡設備的資源受限，現(xiàn)有研究工作通常不會將存儲系統(tǒng)的所有功能全部卸載至可編程網(wǎng)絡設備上，而是對存儲系統(tǒng)功能進行細粒度地抽象劃分，將加速效果最佳的部分實現(xiàn)在可編程網(wǎng)絡設備中，而其他部分仍由存儲軟件實現(xiàn).比如，分布式共享內(nèi)存系統(tǒng)Concordia[10]將并發(fā)控制（讀寫鎖的管理）卸載至可編程交換機，與此相關的元數(shù)據(jù)所占空間較小但對系統(tǒng)性能影響大.

在網(wǎng)絡硬件擴展方面，存在一系列研究工作提升可編程網(wǎng)絡設備的表達能力，可具體分為3 類，如表2 所示.

Table 2 Summary of Switch Expressiveness Optimizations表2 交換機表達能力優(yōu)化方案總結

為了提高可編程交換機的內(nèi)存利用率，思科公司的研究者對RMT 架構進行擴展，提出了解耦的可重配置匹配表（disaggregated reconfigurable match table）架構[11]，將內(nèi)存從交換機流水線移動至中心化的資源池中，使得不同的流水線階段可以共享內(nèi)存資源；進一步地，普渡大學的研究者提出MP5 可編程交換機架構[12]，允許用戶邏輯能夠同時利用多個流水線中的內(nèi)存資源；此外，卡內(nèi)基梅隆大學的研究者提出TEA 架構[13]，支持可編程交換機通過RDMA 網(wǎng)絡協(xié)議訪問服務器集群中的DRAM 資源，以擴充數(shù)據(jù)存儲空間.為了提高可編程交換機的計算能力，伊利諾伊大學厄巴納-香檳分校的研究者提出一種適用于交換機高效處理的浮點數(shù)表示方法FPISA[14]，并為此擴展了RMT 架構.為了擴充可編程交換機的執(zhí)行語義，麻省理工學院的研究者提出網(wǎng)絡包事務（packet transactions）的抽象[15]，為可編程交換機中的部分執(zhí)行邏輯片段提供原子性保證.

2.2 在網(wǎng)存儲系統(tǒng)的容錯

在網(wǎng)存儲系統(tǒng)引入了可編程網(wǎng)絡設備，這不可避免地擴大了系統(tǒng)的故障域（failure domain）.具體而言，在傳統(tǒng)存儲系統(tǒng)中，系統(tǒng)狀態(tài)僅存儲在服務器內(nèi)存和外存中；而對于在網(wǎng)存儲系統(tǒng)，除了服務器內(nèi)存和外存，系統(tǒng)狀態(tài)還會存留在智能網(wǎng)卡的DRAM 和可編程交換機的SRAM 中.當網(wǎng)卡和交換機發(fā)生崩潰時，它們存儲的數(shù)據(jù)將會丟失，如何讓系統(tǒng)容忍這種新型故障是在網(wǎng)存儲系統(tǒng)的另一大設計挑戰(zhàn).

目前的研究工作主要從軟件設計和硬件支持2方面應對這一挑戰(zhàn).在軟件設計方面，現(xiàn)有在網(wǎng)存儲系統(tǒng)盡量只在可編程網(wǎng)絡設備中存儲軟狀態(tài)（soft state），即可以從別處（如后端服務器）恢復的狀態(tài).例如，NetCache[16]在可編程交換機中緩存熱點的鍵值數(shù)據(jù)，而這些數(shù)據(jù)均在后端分布式鍵值服務器中有最新的版本，因此可編程交換機的崩潰不會導致任何鍵值數(shù)據(jù)的丟失；R2P2[17]在可編程交換機中維護每臺服務器的隊列長度信息，該信息丟失后可以通過詢問服務器來重構.

在硬件支持方面，主要的相關研究工作有弗吉尼亞大學提出的PMNet[18]和卡內(nèi)基梅隆大學提出的RedPlane[19].PMNet 將持久性內(nèi)存用于可編程網(wǎng)絡設備，以替代智能網(wǎng)卡的DRAM 和可編程交換機的SRAM；因此，可編程網(wǎng)絡設備可以通過持久性地存儲數(shù)據(jù)來容忍掉電等異常事件.此外，PMNet 設計了一種新型的數(shù)據(jù)更新協(xié)議，如圖2 所示：當可編程交換機收到客戶端發(fā)送的數(shù)據(jù)更新請求時，將內(nèi)容記錄在交換機的持久性日志區(qū)，然后便可提前返回完成消息給客戶端，而服務器異步地處理數(shù)據(jù)更新請求；通過該協(xié)議，客戶端的請求延遲可以減半.RedPlane 則采用數(shù)據(jù)復制的方式進行可編程網(wǎng)絡設備的容錯：在RedPlane 系統(tǒng)中，當可編程交換機需要修改內(nèi)存狀態(tài)時，它會生成包含修改數(shù)據(jù)的復制請求，并發(fā)送至多臺服務器；這些服務器將修改數(shù)據(jù)存儲到本地的DRAM 中，以此容忍可編程交換機的崩潰.

Fig.2 Data update protocol of PMNet圖2 PMNet 的數(shù)據(jù)更新協(xié)議

3 在網(wǎng)存儲系統(tǒng)的分類與研究進展

基于可編程網(wǎng)絡設備的在網(wǎng)存儲系統(tǒng)支持在數(shù)據(jù)傳輸路徑上執(zhí)行存儲任務，顛覆了傳統(tǒng)以CPU 為核心的存儲系統(tǒng)架構思想.根據(jù)可編程網(wǎng)絡設備執(zhí)行的任務，我們將在網(wǎng)存儲系統(tǒng)分為4 類：在網(wǎng)數(shù)據(jù)緩存系統(tǒng)、在網(wǎng)數(shù)據(jù)協(xié)調(diào)系統(tǒng)、在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)以及在網(wǎng)數(shù)據(jù)聚合系統(tǒng).本節(jié)將依次介紹這4 類在網(wǎng)存儲系統(tǒng)，并詳細分析典型的系統(tǒng)實例.表3 對這4類系統(tǒng)在多方面進行了對比.

Table 3 Comparison of Four Types of In-Network Storage Systems表3 4 種在網(wǎng)存儲系統(tǒng)的對比

3.1 在網(wǎng)數(shù)據(jù)緩存系統(tǒng)

在網(wǎng)數(shù)據(jù)緩存系統(tǒng)利用可編程交換機和智能網(wǎng)卡的內(nèi)存空間，在網(wǎng)絡上進行數(shù)據(jù)的緩存或存儲，以提供高吞吐量、低延遲的數(shù)據(jù)訪問.本節(jié)將著重介紹基于可編程交換機的NetCache[16]系統(tǒng)，以及基于智能網(wǎng)卡的KV-Direct[20]系統(tǒng).

NetCache 由約翰霍普金斯大學提出，用于解決傳統(tǒng)分布式內(nèi)存鍵值系統(tǒng)的負載不均衡問題.分布式內(nèi)存鍵值系統(tǒng)將鍵值數(shù)據(jù)以某種規(guī)則分散在多臺服務器的內(nèi)存中，具有較好的水平擴展能力.然而，現(xiàn)實世界中的負載往往是傾斜的，即少量熱點的鍵值對（key-value pairs）會被頻繁地訪問，這會導致整個分布式內(nèi)存鍵值系統(tǒng)負載不均衡：某些服務器承受了大量的請求，處于過載狀態(tài)；而其他服務器處理的請求較少，處于空閑狀態(tài).負載不均衡嚴重影響系統(tǒng)性能：過載的服務器限制了整個系統(tǒng)的總吞吐量，并導致對熱點鍵值對的訪問會經(jīng)歷較高的延遲.為此，NetCache 利用可編程交換機緩存熱點鍵值對，用于過濾對應的讀請求，使得后臺服務器處于負載均衡的狀態(tài).

圖3 展示了NetCache 的架構.NetCache 系統(tǒng)由4個組件構成：1）存儲服務器，將鍵值數(shù)據(jù)存儲在DRAM中；2）客戶端服務器，用于發(fā)送鍵值請求，包括查詢（Get）、更新（Put）和刪除（Del）；3）可編程交換機，緩存熱點鍵值對以服務Get 操作，并進行熱點鍵值數(shù)據(jù)的統(tǒng)計；4）交換機控制器，用于向交換機中添加或刪除鍵值對.后端存儲服務器、可編程交換機以及交換機控制器位于同一個機架中，因此所有的客戶端請求均會流經(jīng)該交換機.

Fig.3 Architecture of NetCache圖3 NetCache 的架構

在NetCache 系統(tǒng)中，交換機與后端存儲服務器協(xié)同處理客戶端請求.當交換機接收到客戶端發(fā)送的Get 請求時，會先查詢本地的鍵值緩存；若緩存命中，則將對應的值返回給客戶端；若不命中，Get 請求會被路由至請求中指定的存儲服務器，然后存儲服務器查詢本地DRAM，返回對應的值至客戶端.

當交換機接收到客戶端發(fā)送的Put 或Del 請求時，也會查詢本地緩存；若緩存命中，則將該鍵值對標記為無效，確保未來的Get 操作不會讀到過期的數(shù)據(jù).然后，請求會被路由至對應的存儲服務器，存儲服務器更新或刪除對應鍵值對，并回復客戶端.同時，若該鍵值對屬于交換機的緩存，存儲服務器會異步地發(fā)送更新請求至交換機，交換機更新緩存中的該鍵值對內(nèi)容，并標記為有效.

NetCache 通過動作-匹配表和寄存器數(shù)組在交換機中構建了鍵值對的緩存結構.具體地，NetCache 維護了一張查詢表，每個條目對應一個鍵值對：其中的match 字段是鍵，action 部分會產(chǎn)生出一份位圖結構和下標.位圖結構用于定位值被存儲在哪些流水線階段的寄存器數(shù)組中，下標用于定位值在寄存器數(shù)組中的哪個元素中.通過這種組織方式，NetCache 可以支持變長的值；但對于鍵，由于其存儲在match 字段中，只能是定長的.由于交換機SRAM 空間有限，NetCache 緩存在交換機中的鍵值對數(shù)量很少（64 000）；但這已經(jīng)能達到良好的負載均衡效果，這得益于之前的研究結論[24]：在傾斜的負載下，只需要將N× lbN份最頻繁被訪問的鍵值對緩存住，就能夠保證后端的負載均衡，其中N是后端存儲服務器的數(shù)目.

NetCache 也將熱點統(tǒng)計功能實現(xiàn)在交換機中.具體地，NetCache 利用寄存器數(shù)組構建了一個計數(shù)器數(shù)組和一個計數(shù)-最小略圖（count-min sketch）[25].其中計數(shù)器數(shù)組用于統(tǒng)計每份被緩存的鍵值對的訪問次數(shù)；計數(shù)-最小略圖用于近似統(tǒng)計未被緩存的鍵值對的訪問次數(shù).當某一鍵值對的訪問次數(shù)到達某一閾值時，交換機將其報告給交換機控制器.交換機控制器向交換機的查詢表中插入對應的條目.為防止交換機將某一熱點鍵值對重復地向控制器報告，NetCache 在交換機中構建了一個布隆過濾器[26]，用于近似記錄哪些鍵值對已向控制器報告.

得益于交換機的極高聚合帶寬，NetCache 在Get操作密集的傾斜負載下能提高系統(tǒng)吞吐量1 個數(shù)量級.但NetCache 只支持單個機架，具有擴展性問題；后續(xù)工作DistCache[27]通過獨立緩存分配和2 次隨機選擇策略將NetCache 擴展到大規(guī)模集群.此外，除了負載均衡場景，研究者們設計了高可靠的鍵值存儲系統(tǒng)NetChain[28].NetChain 通過鏈式復制協(xié)議（Chain Replication Protocol）[29]將每份鍵值對存儲在多臺交換機的SRAM 上，存儲方式與NetCache 類似.表4 對NetCache，DistCache，NetChain 這3 個基于可編程交換機的緩存系統(tǒng)進行了總結對比.

KV-Direct 系統(tǒng)由微軟研究院提出，它將內(nèi)存鍵值系統(tǒng)的功能卸載至基于FPGA 的智能網(wǎng)卡上.隨著網(wǎng)絡帶寬的持續(xù)提升，服務器端CPU 變成鍵值系統(tǒng)的主要性能瓶頸：從吞吐量上看，單個CPU 核心處理鍵值操作的上限低于8 MOPS；從延遲上看，CPU 的軟件調(diào)度和排隊經(jīng)常導致較大的延遲波動.因此，KV-Direct的目標是通過高性能FPGA 智能網(wǎng)卡完全消除鍵值訪問路徑上的服務器CPU 的介入.在KV-Direct 中，鍵值數(shù)據(jù)被存儲在CPU 的DRAM 中，智能網(wǎng)卡通過DMA操作訪問CPU DRAM.KV-Direct 重新設計了高效的索引結構、執(zhí)行引擎以及緩存機制，以充分釋放FPGA 的硬件性能.

在索引結構方面，KV-Direct 構建了高效的鏈式哈希索引.索引由固定數(shù)目的哈希桶構成；每個桶中存有若干哈希槽；哈希槽主要包含鍵值對的地址.當插入新的鍵值對時，若對應的哈希桶滿了，網(wǎng)卡則會分配新的哈希桶鏈接至原有哈希桶尾部，形成鏈式結構.由于智能網(wǎng)卡與CPU DRAM 之間為PCIe 連接，帶寬有限，且存在幾百納秒的延遲，該鏈式哈希索引做出了3 個設計以減少DMA 次數(shù)：1）每個哈希槽中內(nèi)嵌了鍵的部分哈希值，在查詢鍵值對時，網(wǎng)卡會首先進行比對，當不匹配時，則不需要讀取CPU DRAM中的鍵值對.2）尺寸較小的鍵值對（如10 B）直接被存儲在哈希桶中，避免了一次DMA 訪問.3）KVDirect 為尺寸較大的鍵值對和哈希桶設計了專門的分配器；分配器的主要邏輯運行在CPU 上，但分配器中的空閑空間元數(shù)據(jù)被緩存在網(wǎng)卡里，因此，大部分的空間分配和釋放無需網(wǎng)卡執(zhí)行DMA 操作.

在執(zhí)行引擎方面，KV-Direct 通過亂序執(zhí)行保證系統(tǒng)在并發(fā)語義正確的同時達到極致的吞吐量.具體地，網(wǎng)卡在FPGA 中維護了保留站（reservation station），用于追蹤所有正在執(zhí)行的鍵值操作.保留站將哈希沖突的鍵值操作集合維護成隊列結構，網(wǎng)卡按隊列順序執(zhí)行這些操作，以保證并發(fā)執(zhí)行的正確性.這種基于哈希沖突的方式避免了保留站進行鍵的比較，極大節(jié)省了FPGA 上的物理資源；但會引入偽沖突，即某些鍵不同的鍵值操作會被序列化執(zhí)行.此外，保留站會緩存鍵值操作產(chǎn)生的最新值，用于支持數(shù)據(jù)轉發(fā)（data forwarding），提高執(zhí)行效率和減少DMA 操作次數(shù).

在緩存機制方面，KV-Direct 將部分數(shù)據(jù)緩存在智能網(wǎng)卡中的DRAM 空間（網(wǎng)卡DRAM）.由于網(wǎng)卡DRAM 的帶寬較低（十幾GBps），傳統(tǒng)的緩存方法會導致整個系統(tǒng)性能受限于網(wǎng)卡DRAM 帶寬.為此，KV-Direct 設計了負載調(diào)度器，保證系統(tǒng)能夠同時利用網(wǎng)卡DRAM 和PCIe 的帶寬.具體地，整個CPU DRAM空間被劃分成可緩存部分和不可緩存部分.對可緩存部分的訪問會執(zhí)行緩存邏輯，即相關數(shù)據(jù)會被緩存在網(wǎng)卡DRAM 中，當緩存命中時會消耗網(wǎng)卡DRAM帶寬但保存了PCIe 帶寬.對于不可緩存部分，網(wǎng)卡對其所有訪問需要DMA 操作，只消耗PCIe 帶寬.通過調(diào)整2 部分CPU DRAM 空間的比例，KV-Direct 使得整個系統(tǒng)可利用的帶寬最大.KV-Direct 系統(tǒng)使用一張網(wǎng)卡就能達到180 MOPS 的吞吐率，并且尾延遲低于10 μs；同時，相比于基于CPU 的鍵值系統(tǒng)，KV-Direct僅使用1/3 的功耗.KV-Direct 的不足也很明顯：未考慮分布式場景以及系統(tǒng)容錯.

除了KV-Direct，復旦大學還提出了基于智能網(wǎng)卡卸載的分布式內(nèi)存鍵值系統(tǒng)SKV[30]，其利用智能網(wǎng)卡中的ARM CPU 執(zhí)行系統(tǒng)的錯誤檢測和副本操作.

3.2 在網(wǎng)數(shù)據(jù)協(xié)調(diào)系統(tǒng)

分布式存儲系統(tǒng)由多臺存儲服務器構成，并運行分布式協(xié)議進行服務器之間的協(xié)調(diào)（比如分布式緩存一致性與分布式事務）.傳統(tǒng)的分布式協(xié)調(diào)方式消耗大量網(wǎng)絡流量和服務器CPU 資源，效率低下.而在網(wǎng)數(shù)據(jù)協(xié)調(diào)系統(tǒng)將分布式協(xié)議卸載至可編程網(wǎng)絡設備上；得益于可編程交換機和智能網(wǎng)卡在網(wǎng)絡路徑上的優(yōu)勢，在網(wǎng)數(shù)據(jù)協(xié)調(diào)系統(tǒng)能夠極大地提高分布式存儲系統(tǒng)的性能.本節(jié)將著重介紹分布式緩存一致性和分布式事務處理相關的研究工作.

1）分布式緩存一致性

分布式共享內(nèi)存系統(tǒng)Concordia[10]由清華大學提出，利用可編程交換機加速緩存一致性協(xié)議.基于高速網(wǎng)絡（如RDMA）的分布式共享內(nèi)存系統(tǒng)能支持圖計算等大規(guī)模內(nèi)存計算應用.盡管目前網(wǎng)絡帶寬很高（如100 Gbps），但仍低于本地內(nèi)存的訪問，且網(wǎng)絡延遲遠高于內(nèi)存延遲.因此，在分布式共享內(nèi)存系統(tǒng)中，為了減少數(shù)據(jù)的遠程訪問，每臺服務器一般具有本地緩存.如何保證不同服務器緩存之間的一致性是個極具挑戰(zhàn)的問題，而現(xiàn)有的緩存一致性協(xié)議需要服務器之間進行昂貴的分布式協(xié)調(diào)，極大地降低了系統(tǒng)在數(shù)據(jù)共享時的性能：基于目錄的緩存一致性協(xié)議引入多次網(wǎng)絡往返，且當熱點數(shù)據(jù)存在時，服務器會成為系統(tǒng)瓶頸；基于廣播的緩存一致性協(xié)議會導致網(wǎng)絡和CPU 資源的消耗，這是由于每次緩存一致性請求需要被廣播到所有的服務器處理.Concordia利用可編程交換機在網(wǎng)絡中樞上的位置優(yōu)勢，設計了高效的在網(wǎng)分布式緩存一致性協(xié)議.圖4 展示了其架構.

Concordia 是機架級別的分布式共享內(nèi)存系統(tǒng)，主要由內(nèi)存節(jié)點和可編程交換機2 個組件構成.內(nèi)存節(jié)點是普通的服務器，它們將自己的DRAM 空間分為了2 部分：全局共享內(nèi)存以及本地緩存.所有內(nèi)存節(jié)點的全局共享內(nèi)存一起構成了全局地址空間，可以被共享讀寫；內(nèi)存節(jié)點的本地緩存用于緩存最近訪問的全局內(nèi)存，由此減少網(wǎng)絡訪問開銷.可編程交換機記錄了緩存塊的信息，并執(zhí)行緩存一致性邏輯.具體地，如圖4 所示，針對每份緩存塊，可編程交換機通過寄存器數(shù)組記錄了相關元數(shù)據(jù)，包括：①緩存塊的標簽（tag），即對應的全局內(nèi)存地址的高位，用于唯一標識該緩存塊和索引其他的元數(shù)據(jù)；②讀寫鎖，用于序列化沖突的緩存一致性請求，比如2 個內(nèi)存節(jié)點對同一份緩存塊進行寫操作；③狀態(tài)，用于描述該緩存塊所處的狀態(tài)，如未共享的（unshared）、共享的（shared）或者被修改的（modified）；④節(jié)點列表，即持有該緩存塊的內(nèi)存節(jié)點的集合.利用這些元數(shù)據(jù)，Concordia 在交換機中高效地處理緩存一致性請求.

這里通過一個例子描述Concordia 系統(tǒng)中的緩存一致性請求執(zhí)行流程.標簽為0x12b 的緩存塊的元數(shù)據(jù)如圖4 所示，它的狀態(tài)為共享的，被內(nèi)存節(jié)點1 和節(jié)點3 緩存在本地；此外，讀寫鎖字段為空，代表當前不存在針對該緩存塊的一致性操作.當節(jié)點2 需要寫該緩存塊對應的全局地址時，會發(fā)現(xiàn)本地緩存缺失，因此產(chǎn)生一個寫缺失（write miss）請求發(fā)送至可編程交換機；該請求中會捎帶標簽0x12b.當可編程交換機接收到該請求時，首先通過標簽查詢到該緩存塊的其他元數(shù)據(jù).然后，可編程交換機嘗試獲得對應的寫鎖，若失敗，則返回錯誤消息給節(jié)點2，節(jié)點2將進行請求重試.若持鎖成功，可編程交換機根據(jù)請求類型（即write miss）和緩存塊狀態(tài)（即shared）做出相應的動作，在這個例子中就是將一致性請求多播至節(jié)點列表對應的服務器（即內(nèi)存節(jié)點1 和節(jié)點3）.當內(nèi)存節(jié)點1 和節(jié)點3 收到一致性請求時，會將本地持有的緩存塊無效化，然后發(fā)送回復給節(jié)點2.此外，其中1 個節(jié)點（節(jié)點1 或者節(jié)點3）會將該緩存塊的內(nèi)容也發(fā)送至節(jié)點2，這由交換機隨機挑選.當節(jié)點2 收到所有的回復時，將緩存塊數(shù)據(jù)存放在本地緩存中，便可繼續(xù)進行對全局地址空間的讀寫操作.節(jié)點2 會發(fā)送異步的解鎖請求給交換機，請求中會捎帶標簽0x12b.當交換機接收到該解鎖請求時，則會釋放該緩存塊的鎖，并修改對應元數(shù)據(jù)：狀態(tài)修改為modified，節(jié)點列表修改為{2}.從該例子可以看出，Concordia 的在網(wǎng)緩存一致性協(xié)議在數(shù)據(jù)讀寫的關鍵路徑上只需1 次網(wǎng)絡往返，且不會像廣播協(xié)議一樣引入額外的網(wǎng)絡和CPU 資源的消耗.

為了解決可編程交換機內(nèi)存空間小的問題，Concordia 提出動態(tài)地將緩存塊的一致性管理權限在交換機與內(nèi)存節(jié)點之間遷移.具體地，交換機只管理活躍緩存塊的緩存一致性；對于很少觸發(fā)緩存一致性協(xié)議的緩存塊，它們的一致性由內(nèi)存節(jié)點管理退化成傳統(tǒng)的基于目錄的協(xié)議.為了保證遷移過程中整個系統(tǒng)的并發(fā)正確性，Concordia 設計了細粒度的遷移協(xié)議，每次遷移只會阻塞對一份緩存塊的訪問.

除了Concordia，還有一些研究工作也利用可編程交換機保證不同服務器的數(shù)據(jù)之間的一致性.華盛頓大學提出了分布式對象系統(tǒng)Pegasus[31]以解決負載不均衡問題；與NetCache 使用緩存的方式不同，Pegasus 將熱點的對象復制至多臺服務器，以均攤相應的訪問.在Pegasus 系統(tǒng)中，可編程交換機記錄熱點對象所在的服務器列表，當發(fā)生寫請求時更新列表，以保證后續(xù)的讀操作能獲得最新數(shù)據(jù).此外，耶魯大學提出的Mind[32]系統(tǒng)針對的是分離式內(nèi)存場景，即多個計算節(jié)點訪問遠程內(nèi)存池，并將數(shù)據(jù)緩存至本地.Mind 利用可編程交換機保證不同計算節(jié)點的緩存之間處于一致的狀態(tài).此外，約翰霍普金斯大學提出NetLock[33]，通過交換機實現(xiàn)高性能的鎖管理器，用于上層應用保證數(shù)據(jù)一致性.NetLock 將鎖資源存儲在交換機的內(nèi)存中，因此相比于傳統(tǒng)基于服務器的設計，能夠提高吞吐量1 個數(shù)量級；NetLock 在交換機中為鎖請求維護了隊列結構，以保證能夠公平地服務沖突的鎖請求，降低上層應用的尾延遲.表5對上述在網(wǎng)緩存一致性系統(tǒng)進行了總結對比.

Table 5 Comparison of In-Network Cache Coherence Systems表5 在網(wǎng)緩存一致性系統(tǒng)對比

2）分布式事務處理

分布式事務系統(tǒng)將數(shù)據(jù)劃分在不同服務器中，并通過分布式并發(fā)控制和提交協(xié)議提供事務語義.這些協(xié)議存在很高的協(xié)調(diào)開銷，包括網(wǎng)絡通信、CPU 排隊等，而這些開銷位于事務提交的關鍵路徑上，會導致高延遲和高沖突，嚴重降低系統(tǒng)性能.因此，研究人員利用可編程網(wǎng)絡設備的處理能力和得天獨厚的位置卸載事務系統(tǒng)中的協(xié)調(diào)操作，減少網(wǎng)絡往返和CPU 消耗.本節(jié)介紹基于可編程交換機的Eris[34]和SwitchTx[21]系統(tǒng)，以及基于智能網(wǎng)卡的Xenic[35]系統(tǒng).

華盛頓大學提出了基于在網(wǎng)排序的分布式事務系統(tǒng)Eris[34]，通過將序號向量生成器卸載到可編程交換機中，為無依賴事務（independent transactions）[36]指定序號向量，僅需1 次網(wǎng)絡通信即可完成無依賴事務，因此顯著減少了分布式事務的協(xié)調(diào)開銷.在Eris系統(tǒng)中，數(shù)據(jù)被分散至多個數(shù)據(jù)分區(qū)，每個數(shù)據(jù)分區(qū)由多臺存儲數(shù)據(jù)副本的存儲服務器組成.序號向量中的1 個序號對應1 個數(shù)據(jù)分區(qū).圖5 展示了Eris 系統(tǒng)中無依賴事務的提交流程：

在Eris 系統(tǒng)中，客戶端將事務請求發(fā)送給可編程交換機，可編程交換機根據(jù)事務涉及的數(shù)據(jù)分區(qū)為其生成序號向量，同時將事務請求廣播至所有涉及到的數(shù)據(jù)分區(qū)；數(shù)據(jù)分區(qū)中的存儲服務器按照序號順序執(zhí)行請求.交換機生成的序號向量為無依賴事務建立一個可線性化的執(zhí)行順序，而不需要額外的網(wǎng)絡協(xié)調(diào).為支持通用事務（比如讀寫集未知），Eris 將其分解為多個無依賴事務.Eris 存在著擴展性受限的問題：當系統(tǒng)規(guī)模擴大時中心化的序號向量生成器會成為性能瓶頸，限制系統(tǒng)的總吞吐量.

清華大學提出了可擴展的在網(wǎng)分布式事務系統(tǒng)SwitchTx[21]，將分布式事務協(xié)調(diào)過程抽象為多次“收集-分發(fā)”操作的組合，并將這些操作卸載到集群中的多個可編程交換機中.相較于Eris 系統(tǒng)，SwitchTx 系統(tǒng)避免了單點瓶頸問題.圖6 展示了SwitchTx 系統(tǒng)的組件構成以及事務處理流程.

Fig.6 Transaction processing workflow of SwitchTx圖6 SwitchTx 的事務處理流程

SwitchTx 系統(tǒng)由4 個組件構成：①客戶端服務器，用于發(fā)起事務并完成事務的執(zhí)行；②存儲服務器，將數(shù)據(jù)存儲在DRAM 中并維護數(shù)據(jù)的版本和鎖信息；③備份服務器，存儲數(shù)據(jù)的備份以提供系統(tǒng)容錯能力；④可編程交換機，完成事務提交過程多個存儲服務器和備份服務器之間的協(xié)調(diào).

SwitchTx 系統(tǒng)將樂觀并發(fā)控制協(xié)議[37]和主從備份副本協(xié)議的協(xié)調(diào)任務卸載到交換機.SwitchTx 中的事務提交可以分為5 個階段，包括執(zhí)行階段、持鎖階段、版本檢查階段、提交從副本階段以及提交主副本階段.這些階段是依次進行的，其中的協(xié)調(diào)任務是同步來自當前階段的參與者的結果，并使事務進入下一個階段.SwitchTx 通過在交換機中設計“收集-分發(fā)”原語完成協(xié)調(diào)任務，即通過“收集”步驟統(tǒng)計當前階段的執(zhí)行結果，通過“分發(fā)”步驟使事務進入下一階段.以從持鎖階段到版本檢查階段的協(xié)調(diào)任務為例，當交換機收集到所有寫參與者的包含持鎖成功信息的網(wǎng)絡包，它將向所有讀參與者廣播版本檢查的請求.

SwitchTx 將“收集-分發(fā)”原語擴展到多個交換機，這得益于SwitchTx 中的協(xié)調(diào)是去中心化的，即不同的事務可以使用不同的交換機來執(zhí)行“收集-分發(fā)”操作.具體地，SwitchTx 為每個事務選擇一組交換機來執(zhí)行“收集-分發(fā)”操作，多個交換機和服務器構成樹形的拓撲結構，其中最高層交換機為樹的根，其余交換機為中間節(jié)點，存儲服務器、備份服務器和客戶端為葉子節(jié)點.在“收集”步驟中，非根交換機從其子節(jié)點（交換機或服務器）收集消息，并將結果發(fā)送到其父節(jié)點.當根節(jié)點交換機收集到足夠數(shù)目的消息時，則開始執(zhí)行“分發(fā)”步驟，即將請求廣播給對應事務階段的參與者.在“分發(fā)”步驟中，消息沿著樹結構從根節(jié)點多播到葉子節(jié)點.

SwitchTx 只需在可編程交換機中為每個“收集-分發(fā)”操作實現(xiàn)一個計數(shù)器，即用寄存器數(shù)組記錄“收集”步驟中已收集到的網(wǎng)絡包數(shù)量，因此對交換機存儲空間的占用小.當可編程交換機接收到網(wǎng)絡包時，根據(jù)其包頭中標記的事務編號取出對應的計數(shù)器，增加計數(shù)器數(shù)值并與網(wǎng)絡包攜帶的閾值信息對比.若計數(shù)器數(shù)值小于閾值，交換機丟棄網(wǎng)絡包；若計數(shù)器數(shù)值等于閾值，交換機開始“分發(fā)”步驟，并重置計數(shù)器.其中計數(shù)器以事務編號為索引存儲在哈希表中.

此外，華盛頓大學提出了分布式事務系統(tǒng)Xenic[35]，利用基于ARM CPU 的on-path 智能網(wǎng)卡進行2 方面的卸載：事務的協(xié)調(diào)任務以及數(shù)據(jù)并發(fā)索引.具體地，Xenic 在客戶端網(wǎng)卡存儲事務的臨時狀態(tài)，完成事務協(xié)調(diào)任務，減少協(xié)調(diào)過程中的通信時延.Xenic 的服務端網(wǎng)卡利用網(wǎng)卡內(nèi)存存儲熱點數(shù)據(jù)以及鎖信息，消除遠程數(shù)據(jù)訪問的PCIe 開銷；同時利用智能網(wǎng)卡的ARM CPU 處理復雜數(shù)據(jù)訪問，以減少服務端CPU開銷.Xenic 設計了智能網(wǎng)卡內(nèi)存與主機內(nèi)存協(xié)同的Robin hood 哈希索引結構[38]，減少網(wǎng)卡處理遠程數(shù)據(jù)訪問請求時的DMA 次數(shù).事務執(zhí)行過程中的副本操作也完全由網(wǎng)卡執(zhí)行，這進一步降低了主機CPU的消耗.除了事務系統(tǒng)，一些分布式文件系統(tǒng)也將副本操作卸載至智能網(wǎng)卡：比如LineFS[39]將包括數(shù)據(jù)副本的文件系統(tǒng)后臺操作卸載至基于ARM CPU 的off-path 智能網(wǎng)卡，由此釋放客戶端的CPU 資源，減少文件系統(tǒng)與計算任務之間的干擾.表6 對上述在網(wǎng)分布式事務系統(tǒng)進行了總結對比.

Table 6 Comparison of In-Network Transaction Systems表6 在網(wǎng)事務系統(tǒng)對比

3.3 在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)

分布式存儲系統(tǒng)的服務器數(shù)目不斷增加，且每臺服務器中的CPU 核心數(shù)目也在持續(xù)增長.這些趨勢導致了2 個關鍵問題：多CPU 核心并發(fā)處理請求容易產(chǎn)生資源沖突；服務器或CPU 核心之間存在負載不均衡.在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)利用可編程交換機和智能網(wǎng)卡的中心化位置優(yōu)勢，在網(wǎng)絡上進行數(shù)據(jù)訪問請求的調(diào)度，旨在減少多核并發(fā)的資源競爭開銷，或保證服務器以及CPU 核心之間的負載均衡.本節(jié)將著重介紹針對多核并發(fā)的AlNiCo 系統(tǒng)[22]，以及針對負載均衡的R2P2 系統(tǒng)[17].

1）針對多核并發(fā)的在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)

在單機內(nèi)存事務存儲系統(tǒng)中，系統(tǒng)接收來自網(wǎng)絡的事務請求并將它們分派給工作線程.由于事務請求包括對多份數(shù)據(jù)的讀/寫操作，工作線程需要使用并發(fā)控制協(xié)議來執(zhí)行事務，以保證事務的隔離性.但是，當存在沖突的2 個事務并發(fā)執(zhí)行時，事務會被中止或阻塞.中止會導致事務重試，阻塞可能會級聯(lián)阻塞更多事務，中止和阻塞均會導致系統(tǒng)性能下降.因此事務系統(tǒng)需要通過合理的調(diào)度模塊將沖突的事務調(diào)度到相同的工作線程，來最小化并發(fā)事務之間的沖突.現(xiàn)有基于軟件的調(diào)度算法包括靜態(tài)數(shù)據(jù)劃分和基于圖劃分，靜態(tài)數(shù)據(jù)劃分無法處理動態(tài)負載，而基于圖劃分的方法需要對請求做批處理，即積攢大量請求后處理，引入額外的延遲.

清華大學提出了在網(wǎng)事務請求調(diào)度系統(tǒng)AlNiCo，將智能網(wǎng)卡與事務軟件協(xié)同設計，利用智能網(wǎng)卡低延遲地執(zhí)行調(diào)度算法，并通過軟件反饋機制根據(jù)負載變化更新調(diào)度算法.圖7 展示了AlNiCo 的整體架構：客戶端通過網(wǎng)絡連接到服務端的智能網(wǎng)卡并發(fā)送事務請求；智能網(wǎng)卡上的FPGA 執(zhí)行調(diào)度算法選擇合適的工作線程分發(fā)請求；工作線程在執(zhí)行事務請求的同時統(tǒng)計負載信息，用于定期更新調(diào)度算法的參數(shù).

Fig.7 Architecture of AlNiCo圖7 AlNiCo 的架構

AlNiCo 將調(diào)度信息分為3 種類型：1）請求信息，即請求訪問的數(shù)據(jù)和對應的訪問方式（讀或?qū)懀?）工作線程信息，即每個工作線程上正在執(zhí)行或?qū)⒁獔?zhí)行的事務；3）全局狀態(tài)信息，包括數(shù)據(jù)熱點等工作負載特征.AlNiCo 系統(tǒng)將這3 種調(diào)度信息編碼為向量，并將調(diào)度算法設計為向量計算，以此來充分發(fā)揮網(wǎng)卡上FPGA 的計算加速能力.具體地，AlNiCo 系統(tǒng)用特征向量表示請求信息，向量中每個特征代表一個數(shù)據(jù)分區(qū)是否被訪問和如何被訪問（讀/寫）；工作線程信息用該線程正在執(zhí)行/排隊的事務的特征向量的合集表示；AlNiCo 將數(shù)據(jù)熱點信息表示為特征向量中每個特征的權重.基于上述編碼方法，AlNiCo 設計了沖突感知的調(diào)度算法，利用FPGA 高效地比較事務的特征向量與工作線程的特征向量之間的相似程度（越相似則代表兩者沖突越大），為事務選擇最可能產(chǎn)生沖突的工作線程.

AlNiCo 在Mellanox Innova-2 網(wǎng)卡[7]上實現(xiàn)了通用的可調(diào)度的遠程過程調(diào)用（remote procedure call，RPC）框架.Innova-2 是一款基于FPGA 的off-path 智能網(wǎng)卡.AlNiCo 的RPC 框架不僅可以用于實現(xiàn)事務請求調(diào)度算法，而且可以用于其他基于請求內(nèi)容調(diào)度的應用場景.圖8 展示了AlNiCo 系統(tǒng)的RPC 框架：

Fig.8 RPC framework of AlNiCo圖8 AlNiCo 的RPC 框架

該框架通過RDMA 實現(xiàn)服務端與客戶端之間的通信，以及通過DMA 和MMIO 實現(xiàn)FPGA 與主機之間的通信.AlNiCo 為每個RPC 請求添加固定格式的元數(shù)據(jù)，客戶端可以根據(jù)調(diào)度需求將請求信息編碼到元數(shù)據(jù)，在AlNiCo 系統(tǒng)的事務調(diào)度中，元數(shù)據(jù)為事務特征向量.該RPC 框架采用元數(shù)據(jù)與數(shù)據(jù)分離的設計，其在服務器主機內(nèi)存上維護數(shù)據(jù)緩沖區(qū)，在FPGA 上維護元數(shù)據(jù)緩沖區(qū).RPC 的處理流程為：客戶端同時發(fā)起2 個單邊RDMA 寫請求分別將RPC 數(shù)據(jù)（①）和RPC 元數(shù)據(jù)（②）發(fā)送到它們各自的緩沖區(qū).FPGA 上的調(diào)度模塊輪詢元數(shù)據(jù)緩沖區(qū)，以確定新請求的到達，之后調(diào)度模塊會執(zhí)行調(diào)度算法選擇一個工作線程.在做出調(diào)度決策之后，調(diào)度模塊通過DMA 操作向工作線程的接收完成隊列（CQ）添加條目（③），來通知被選定的工作線程.CQ 中的條目僅包含RPC 數(shù)據(jù)的地址，而不包括RPC 的元數(shù)據(jù).由于RDMA 寫操作是保證順序的，因此當工作線程讀取到新的CQ 條目（④）后，可以從RPC 數(shù)據(jù)緩沖區(qū)獲得完整的RPC 數(shù)據(jù).最后，工作線程執(zhí)行事務請求，并通過RDMA 寫操作（⑤）回復客戶端.此外，CPU 向智能網(wǎng)卡暴露了FPGA 可讀的配置緩沖區(qū)，軟件可以將調(diào)度器的新配置寫入緩沖區(qū)，F(xiàn)PGA 上的調(diào)度器定期讀取配置并更新.

2）針對負載均衡的在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)

遠程過程調(diào)用RPC 框架被廣泛應用在數(shù)據(jù)中心的存儲系統(tǒng)中，是實現(xiàn)系統(tǒng)服務等級目標（service level objective,SLO）的核心組件.隨著系統(tǒng)規(guī)模的擴大，RPC 框架為保證可擴展性，需通過調(diào)度保證多節(jié)點之間以及節(jié)點內(nèi)多核之間的負載均衡；同時，現(xiàn)代數(shù)據(jù)中心的存儲系統(tǒng)如內(nèi)存緩存的服務延遲僅為數(shù)百微秒，這就要求負載均衡調(diào)度本身具有極低延遲.

瑞士聯(lián)邦理工學院提出R2P2[17]，它是基于可編程交換機的負載均衡RPC 框架.該框架使用JBSQ（joinbounded-shortest-queue）負載均衡策略；JBSQ 的調(diào)度質(zhì)量接近單隊列模型，且實際擴展性更好.R2P2 在交換機中為每個服務器維護有限深度的隊列，深度通常取2 或3，代表該服務器未執(zhí)行完的RPC 請求數(shù)目.圖9 展示了R2P2 的系統(tǒng)架構和RPC 處理流程.

Fig.9 Architecture of R2P2圖9 R2P2 的架構

R2P2 通過以下階段處理RPC 請求：①客戶端向交換機發(fā)送RPC 請求，若RPC 請求的尺寸較大，由多個網(wǎng)絡包構成，則只需要發(fā)送1 個網(wǎng)絡包，并攜帶客戶端的信息以及該RPC 請求的唯一標識符；②可編程交換機讀取服務器的隊列信息，若存在某些服務器的隊列空閑，則選擇隊列最短的作為目標服務器，并將該RPC 請求轉發(fā)給它和并更新隊列信息；若所有服務器隊列都滿了，交換機則循環(huán)該RPC 請求，直到存在空閑隊列；③如果RPC 請求由多個網(wǎng)絡包構成，則目標服務器將發(fā)送通知消息至客戶端；④客戶端在收到通知消息后，將RPC 請求的剩余部分發(fā)送到該目標服務器，該過程完全繞過交換機中的調(diào)度邏輯；⑤目標服務器執(zhí)行完RPC 請求后，將處理結果返回給客戶端；⑥服務器向交換機發(fā)送反饋消息，通知自身當前的狀態(tài)，包括隊列空閑狀況和可用性等.

由于可編程交換機的流水線硬件架構的限制，R2P2 設計了多輪的方式選擇最短的隊列.具體地，在隊列最大深度為n的系統(tǒng)設置下，每個RPC 請求第1 次經(jīng)過交換機時，交換機進行第1 輪操作，尋找隊列長度小于等于0 的服務器（隊列長度信息被存儲在可編程交換機的寄存器數(shù)組中），若找到則確定了目標服務器；否則，該RPC 請求會再次被重新送回交換機流水線，進行第2 輪操作，尋找隊列長度小于等于1 的服務器；以此類推，若在第n輪操作時依舊找不到隊列長度小于等于n-1的服務器時，則說明所有的服務器隊列均已滿，該RPC 請求將在交換機內(nèi)循環(huán)，直到存在某個服務器的隊列長度小于n.

除了R2P2 之外，約翰霍普金斯大學還提出了Rack-Sched[40]，這是結合服務器之間調(diào)度和CPU 核心之間調(diào)度的統(tǒng)一調(diào)度框架，專為機架級別的應用設計.服務器之間的調(diào)度由可編程交換機實現(xiàn)：交換機為RPC 請求選擇目的服務器以達到服務器之間的負載均衡，與R2P2 不同，RackSched 采用樹狀歸約算法選擇最短隊列從而避免網(wǎng)絡包在交換機內(nèi)的重新傳輸.此外，可編程交換機追蹤每臺服務器上的實時負載.CPU 核心之間調(diào)度通過中心化的調(diào)度線程來實現(xiàn)，借鑒了單機調(diào)度系統(tǒng)Shinjuku[41].

上述R2P2 和RackSched 系統(tǒng)雖然支持在服務器之間進行負載均衡調(diào)度，但忽略了數(shù)據(jù)一致性，即在存儲系統(tǒng)中，某些數(shù)據(jù)的最新版本只存儲在某些服務器中，因此交換機無法對相關RPC 請求進行任意調(diào)度.Harmonia[42]和FLAIR[43]這2 個系統(tǒng)利用可編程交換支持保證數(shù)據(jù)一致性的請求調(diào)度.具體地，它們針對的場景是副本協(xié)議，1 份數(shù)據(jù)通過共識協(xié)議被冗余地存儲在不同服務器（包括1 個主副本服務器以及多個從副本服務器），交換機將客戶端的讀請求高效地調(diào)度至具有最新版本數(shù)據(jù)的服務器上.這里的主要設計難點在于交換機如何與共識協(xié)議結合，識別哪些服務器具有讀請求所需的最新數(shù)據(jù).Harmonia在可編程交換機中維護了細粒度哈希表，用于實時記錄哪些數(shù)據(jù)存在并發(fā)的寫請求，對于這些數(shù)據(jù)的讀請求只能被路由至主副本，對于其余數(shù)據(jù)的讀操作可被調(diào)度至任一從副本.FLAIR 將整個數(shù)據(jù)范圍切分成大量的分區(qū)，在交換機中記錄每個分區(qū)的穩(wěn)定狀態(tài)：當某個分區(qū)存在進行中的寫請求時，則被標記成不穩(wěn)定，對應的讀請求只能被路由至主副本；對于穩(wěn)定分區(qū)的讀請求能以負載均衡的方式被調(diào)度至某一從副本.表7 對本節(jié)涉及的在網(wǎng)數(shù)據(jù)調(diào)度系統(tǒng)進行了總結對比.

3.4 在網(wǎng)數(shù)據(jù)聚合系統(tǒng)

在網(wǎng)數(shù)據(jù)聚合系統(tǒng)主要利用可編程交換機帶寬極高且位于網(wǎng)絡中樞的特點，在交換機內(nèi)進行數(shù)據(jù)處理，以提高存儲系統(tǒng)的性能.本節(jié)主要介紹基于可編程交換機的糾刪碼系統(tǒng)NetEC[23].

NetEC 由清華大學提出，其可利用可編程交換機加速糾刪碼系統(tǒng)的數(shù)據(jù)重構性能.相比于副本機制，糾刪碼在保證相同數(shù)據(jù)可靠性的同時能夠大幅度降低存儲空間的使用.例如，在廣泛使用的里德-所羅門碼（RS 碼）[44]中，針對k份原始數(shù)據(jù)塊，能夠計算出r份校驗塊；這k份原始數(shù)據(jù)塊能夠通過這k+r份中的任意k份重構出來，因此最多能夠容忍r個錯誤.糾刪碼的主要缺陷是數(shù)據(jù)重構性能低下.假設分布式存儲系統(tǒng)使用RS（k，r）編碼，當某臺服務器崩潰后，恢復丟失的任何一份數(shù)據(jù)塊需要從k臺其他服務器讀取相應的數(shù)據(jù)塊，然后進行向量點積計算重構.此時，整個系統(tǒng)的重構速度受限于接收端網(wǎng)卡帶寬：假設網(wǎng)卡帶寬為B，恢復大小為M的數(shù)據(jù)需要的時間為k×M/B.NetEC 的基本思想是在交換機上完成糾刪碼的重構過程，由此克服接收端網(wǎng)卡的帶寬瓶頸并消除CPU 的計算開銷.圖10 展示了其架構.

在圖10 中的例子里，交換機根據(jù)服務器B1，B2，B3中的數(shù)據(jù)進行糾刪碼的重構，重構的結果被存儲在服務器A中.B1，B2，B3將數(shù)據(jù)塊發(fā)送至可編程交換機，可編程交換機主要完成2 項任務：1）針對每個字（word），即圖10 中的xi，進行伽羅華域的乘法，將其乘以常數(shù)ai；2）將來自不同服務器的乘法結果進行求和，獲得重構的結果a1x1+a2x2+a3x3.由于交換機的硬件限制，NetEC 對這2 項任務進行了精心設計.由于交換機不支持乘法運算，NetEC 將乘法運算過程轉換為查表和加法.具體地，在NetEC 中，每個word 為16 b，對于16 b 的每個數(shù)字，可編程交換機預先存儲了對數(shù)查詢表和指數(shù)查詢表.因此，對于xi和ai相乘，交換機先通過查詢對數(shù)查詢表獲得lb（xi）的值，而lb（ai）的值是預先知道的；然后，將l b（xi）和lb（ai）相加，獲得lb（ai xi）；最后，通過查詢指數(shù)查詢表，獲得ai xi的值.對于求和操作，NetEC 設計了求和緩存結構，對于每個word，分配初始值為0 的緩存區(qū)，當計算完ai xi后，交換機將ai xi與現(xiàn)有緩存區(qū)的值相加并更新緩存區(qū).同時，交換機維護了位圖，用于記錄來自哪些服務器的word 已經(jīng)完成了乘法和求和.若所有服務器的word 都已被處理，最后的重構結果將被發(fā)送至服務器A.為了防止不同發(fā)送端的數(shù)據(jù)傳輸不同步導致交換機內(nèi)求和緩存結構空間占用過大，NetEC 復用了TCP 協(xié)議棧的功能，保證重構過程中發(fā)送端服務器在交換機中暫存的求和結果不超過TCP 接收窗口的大小.NetEC 被集成進HDFS[45]中，相比于原有糾刪重構方法，提升重構速度最高達9 倍，且完全消除了重構過程的CPU 開銷.

除了糾刪碼場景，利用可編程交換機進行數(shù)據(jù)聚合還能夠加速分布式機器學習訓練系統(tǒng).微軟研究院提出了SwitchML[46]系統(tǒng)，將機器學習訓練過程中的模型參數(shù)聚合卸載至可編程交換機.針對可編程交換機不支持浮點數(shù)計算的問題，SwitchML 設計了服務器與交換機協(xié)同設計的方法：服務器將需要聚合的浮點參數(shù)進行量化，轉換成定點數(shù)，因此交換機只需要進行定點數(shù)的聚合.此外，清華大學提出了ATP系統(tǒng)[47]，利用多臺交換機協(xié)同加速機器學習的訓練任務，且能高效支持多個訓練任務共同運行的多租戶場景；沙特阿拉伯阿卜杜拉國王科技大學提出了針對稀疏訓練任務的數(shù)據(jù)聚合系統(tǒng)OmniReduce[48]，并將部分聚合算法卸載至可編程交換機；其他工作如iSwitch[49]和Flare[50]設計了加速數(shù)據(jù)聚合的定制化交換機硬件架構，其中iSwitch 采用了FPGA 硬件，F(xiàn)lare 采用了PsPIN[51]硬件.此外，F(xiàn)lare 進一步支持用戶自定義聚合操作處理的數(shù)據(jù)類型.表8 對上述在網(wǎng)數(shù)據(jù)聚合系統(tǒng)進行了對比總結.

Table 8 Comparison of In-Network Data Aggregation Systems表8 在網(wǎng)數(shù)據(jù)聚合系統(tǒng)對比

4 總結與展望

本文首先從可編程網(wǎng)絡硬件（包括可編程交換機和智能網(wǎng)卡）的特性出發(fā)，展開分析了構建在網(wǎng)存儲系統(tǒng)面臨的挑戰(zhàn)，并對現(xiàn)有研究工作詳細地分類與剖析.現(xiàn)有研究工作利用可編程網(wǎng)絡硬件對存儲系統(tǒng)的不同模塊進行加速，包括數(shù)據(jù)緩存、協(xié)調(diào)、調(diào)度以及聚合，能夠顯著提高存儲系統(tǒng)的性能.然而，研究人員仍然需要在4 個方面進行深入探索，才能讓在網(wǎng)存儲系統(tǒng)廣泛普及到數(shù)據(jù)中心和超算中心.

1）交換機與網(wǎng)卡協(xié)同.現(xiàn)有的在網(wǎng)存儲系統(tǒng)大多孤立地使用可編程交換機或者智能網(wǎng)卡，無法做到全方位的存儲功能卸載.而未來的在網(wǎng)存儲系統(tǒng)應該是全編程的：可編程交換機和智能網(wǎng)卡協(xié)同工作、互相補充.其中可編程交換機執(zhí)行服務器之間的任務，智能網(wǎng)卡執(zhí)行服務器內(nèi)部的任務.例如，對于在網(wǎng)緩存系統(tǒng)，可利用交換機緩存全局最熱的數(shù)據(jù)，而利用智能網(wǎng)卡緩存服務器中較熱的數(shù)據(jù)，以達到整體性能的最優(yōu).當交換機與網(wǎng)卡協(xié)同設計時，存儲系統(tǒng)的故障域?qū)⑦M一步擴大，這需要引入新的高效容錯機制.

2）多租戶.當在網(wǎng)存儲系統(tǒng)被部署至云環(huán)境時，需高效地支持多租戶，即多租戶之間要進行資源的共享和隔離.具體地，多個租戶需分時復用可編程交換機和智能網(wǎng)卡的計算、內(nèi)存資源；同時，當出現(xiàn)資源競爭時，多個租戶之間需達到較好的性能隔離，不會相互影響.支持多租戶需要編譯器和網(wǎng)絡硬件體系結構的共同支持，為不同租戶卸載的存儲功能高效分配可編程網(wǎng)絡設備的硬件資源.例如，對于在網(wǎng)數(shù)據(jù)聚合系統(tǒng)，該如何分配可編程交換機的內(nèi)存空間和帶寬，以滿足多個租戶的服務等級目標.目前，已有少量研究工作利用智能網(wǎng)卡進行了存儲虛擬化的探索，例如芝加哥大學提出的LeapIO 系統(tǒng)[52].在多租戶環(huán)境下，在網(wǎng)存儲系統(tǒng)的容錯將變得愈發(fā)復雜，需考慮某個在網(wǎng)存儲系統(tǒng)的失效不會影響其他租戶系統(tǒng)的可用性.

3）安全.目前越來越多的網(wǎng)絡數(shù)據(jù)為了安全考慮被加密，此時就需要可編程交換機和智能網(wǎng)卡能夠高效地處理加密的數(shù)據(jù).在存儲系統(tǒng)軟件設計方面，我們需要首先分析清楚哪些數(shù)據(jù)需加密，比如用戶請求；哪些無需加密，比如存儲系統(tǒng)的元數(shù)據(jù).在網(wǎng)絡硬件設計方面，需要讓交換機和網(wǎng)卡支持同態(tài)加密，在加密的網(wǎng)絡數(shù)據(jù)上進行處理和計算.

4）自動卸載.從頭構建可商用的高可靠在網(wǎng)存儲系統(tǒng)極其困難，需要大量的工程代碼和測試驗證.如果能夠?qū)F(xiàn)有成熟的存儲系統(tǒng)如Memcached[53]，Ceph[54]中的某些模塊自動卸載至可編程交換機和智能網(wǎng)卡，就能既利用現(xiàn)有的系統(tǒng)代碼，又能享受到可編程網(wǎng)絡設備帶來的性能紅利.這需要研究自動卸載技術，自動分析現(xiàn)有存儲系統(tǒng)代碼并將某些模塊自動卸載至可編程網(wǎng)絡設備.這里面存在諸多技術挑戰(zhàn)，比如如何識別對哪些模塊的卸載會帶來性能收益，如何保證部分模塊被卸載后整體系統(tǒng)功能上依舊正確.

作者貢獻聲明：汪慶負責文獻的搜集整理、論文整體架構的設計和論文主要內(nèi)容的撰寫；李俊儒負責論文部分內(nèi)容的撰寫；舒繼武負責論文結構的討論和修改.