論文鏈接：https://www.usenix.org/system/files/fast23-shen.pdf

開源代碼：https://github.com/dmemsys/FUSEE

一作作者暫時(shí)看起來還是特別有名，且沒找到個(gè)人主頁啥的

簡介

分布式內(nèi)存鍵值（key-value，KV）存儲正在采用分離式內(nèi)存（disaggregated memory，DM）架構(gòu)來實(shí)現(xiàn)更高的資源利用率。然而，現(xiàn)有的 DM 上的 KV 存儲采用的是半分離（semi-disaggregated）設(shè)計(jì)，即將 KV 存儲在 DM 上，但另外使用單體元數(shù)據(jù)服務(wù)器（monolithic metadata servers）來管理元數(shù)據(jù)，因此元數(shù)據(jù)服務(wù)器上依然存在資源效率低的問題。為了解決這個(gè)問題，該文提出了 FUSEE，一種完全內(nèi)存分離式（fully memory-disaggregated）的 KV 存儲，來分離式的管理元數(shù)據(jù)。FUSEE 在內(nèi)存節(jié)點(diǎn)上復(fù)制元數(shù)據(jù)（索引和內(nèi)存管理信息），直接在 client 上進(jìn)行管理，并在 DM 架構(gòu)下處理復(fù)雜的故障。為了可擴(kuò)展地在 client 上復(fù)制索引，F(xiàn)USEE 提出了一個(gè) client 中心的復(fù)制協(xié)議，允許 client 同時(shí)訪問和修改復(fù)制的索引。為了有效地管理分散化內(nèi)存，F(xiàn)USEE 采用了兩級內(nèi)存管理方案，將內(nèi)存管理職責(zé)分配給 client 和內(nèi)存節(jié)點(diǎn)。最后，為了處理 client 故障下的元數(shù)據(jù)損壞，F(xiàn)USEE利用嵌入式操作日志方案以低的日志維護(hù)開銷修復(fù)元數(shù)據(jù)。用微基準(zhǔn)測試和 YCSB 混合基準(zhǔn)測試對 FUSEE 進(jìn)行評估，實(shí)驗(yàn)結(jié)果表明，F(xiàn)USEE 比 DM 上的最先進(jìn)的 KV 存儲性能高 4.5 倍，且資源消耗更少。

（先噴起來，不排除個(gè)人見識水平有限，眼光不足，看了好幾篇分離式內(nèi)存架構(gòu)下的 KV 設(shè)計(jì)了，第一次看到 client （client）這個(gè)稱呼，關(guān)鍵順著看下來，一開始還不好猜這個(gè) client 涵蓋哪些東西，文字迷惑性高得一批，最后在噴，這里為了好理解，個(gè)人認(rèn)為可以先將 client 理解為運(yùn)行在計(jì)算節(jié)點(diǎn)上的程序，能發(fā)出并執(zhí)行如 KV ?操作等任務(wù) ）

先放前面，通俗點(diǎn)，這篇文章針對的是 ATC 20 的 Disaggregating persistent memory and controlling them remotely: An exploration of passive disaggregated key- value stores. （這篇文章好歹剛開始是用 client/compute nodes 來方便理解 client）

背景動(dòng)機(jī)挑戰(zhàn)

分離式內(nèi)存架構(gòu)

DM 將單體服務(wù)器（monolithic servers）的 CPU 和內(nèi)存分為兩個(gè)獨(dú)立的硬件資源池，包含計(jì)算節(jié)點(diǎn)（compute nodes，CNs）和內(nèi)存節(jié)點(diǎn)（memory nodes，MNs）。CNs 擁有豐富的 CPU core 和少量內(nèi)存作為本地緩存。MNs 托管各種內(nèi)存介質(zhì)，例如 DRAM 和持久性內(nèi)存，具有較弱的計(jì)算能力。CNs 中的 CPU 使用快速的遠(yuǎn)程訪問互連技術(shù)，例如單邊 RDMA 等直接訪問 MNs 中的內(nèi)存。

分離式內(nèi)存下的 KV 存儲

如下圖 Clover（ATC20 的那篇文章）采用半分離設(shè)計(jì)，將數(shù)據(jù)和元數(shù)據(jù)分離，以降低所有權(quán)成本并防止數(shù)據(jù)節(jié)點(diǎn)的計(jì)算能力成為性能瓶頸。Clover 用額外的單體元數(shù)據(jù)服務(wù)器來管理元數(shù)據(jù)，包括內(nèi)存管理信息（memory management information，MMI）和哈希索引。對于搜索請求， client 從元數(shù)據(jù)服務(wù)器查找 KV 對的地址，然后使用 RDMA_READ 操作從 MNs 中獲取數(shù)據(jù)。對于插入和更新請求， client 通過 RPC 從元數(shù)據(jù)服務(wù)器分配內(nèi)存塊，使用 RDMA_WRITE 操作將 KV 對寫入 MNs，并通過 RPC 更新元數(shù)據(jù)服務(wù)器上的哈希索引。為防止 client 的頻繁請求壓垮元數(shù)據(jù)服務(wù)器， client 一次分配一個(gè)批次的內(nèi)存塊，并在本地緩存哈希索引。

然而，Clover 的半分離式設(shè)計(jì)由于基于單體服務(wù)器來管理元數(shù)據(jù)，無法充分利用 DM 架構(gòu)的資源效率。一方面，單體式元數(shù)據(jù)服務(wù)器消耗額外的資源，包括 CPU、內(nèi)存和 RNIC。另一方面，由于元數(shù)據(jù)管理的 CPU 密集型特性，必須保留和分配許多計(jì)算和內(nèi)存資源給 Clover 的元數(shù)據(jù)服務(wù)器才能實(shí)現(xiàn)良好的性能。

為了解決 Clover 存在的問題，F(xiàn)USEE 采用了完全的內(nèi)存分離式設(shè)計(jì)，使 client 能夠直接訪問和修改哈希索引，并在 MN 上管理內(nèi)存空間，如上圖 b。

挑戰(zhàn)

Client-Centric Index Replication

挑戰(zhàn)一。

在完全內(nèi)存分離的情況下實(shí)現(xiàn)線性化復(fù)制哈希索引（或者說備份）的關(guān)鍵挑戰(zhàn)來自于 DM 的 client 中心計(jì)算（client-centric computation）性質(zhì)。

第一，現(xiàn)有的方法都是 server 中心（server-centric）性質(zhì)，數(shù)據(jù)副本由管理數(shù)據(jù)的 CPU 進(jìn)行獨(dú)占式訪問和修改，很依賴 server 端的 CPU。挑戰(zhàn)在于，在完全內(nèi)存分離的情況下，沒有這樣的管理 CPU，因?yàn)樗?client 都使用單邊 RDMA 直接訪問和修改哈希索引。（個(gè)人理解就是不好照搬之前的方法，不好管理，說的云里霧里的）

第二，簡單地采用共識協(xié)議或遠(yuǎn)程鎖定等方法會導(dǎo)致請求序列化的性能問題。

Remote Memory Allocation

挑戰(zhàn)二。

DM 的關(guān)鍵挑戰(zhàn)在于在哪里執(zhí)行內(nèi)存管理計(jì)算。若將內(nèi)存管理元數(shù)據(jù)存儲在 MNs 上，并允許 client 通過直接修改MNs 上的元數(shù)據(jù)來分配內(nèi)存空間，但是內(nèi)存管理元數(shù)據(jù)由所有 client 共享，會存在同步問題，因此該方法會因?yàn)樵?DM 上昂貴且復(fù)雜的遠(yuǎn)程同步過程，使得內(nèi)存分配延遲升高。若將所有內(nèi)存管理元數(shù)據(jù)讓計(jì)算能力弱的 MNs 處理，MNs 的內(nèi)存端計(jì)算能力可能無法承擔(dān)來自 client 的頻繁的細(xì)粒度 KV 分配請求。

Metadata Corruption

挑戰(zhàn)三。

崩潰的 client 可能會危及整個(gè) KV 存儲系統(tǒng)的正確性。首先，崩潰的 client 可能會使索引處于部分修改的狀態(tài)，其他正常 client 可能無法訪問數(shù)據(jù)，甚至使用已經(jīng)損壞的索引訪問錯(cuò)誤的數(shù)據(jù)。其次，崩潰的 client 可能會分配內(nèi)存空間，但不使用它們，導(dǎo)致嚴(yán)重的內(nèi)存泄漏。為了確保 KV 存儲的正確性，在 client 故障時(shí)必須修復(fù)損壞的元數(shù)據(jù)。

設(shè)計(jì)

如下圖，F(xiàn)USEE 由client、MNs 和一個(gè) master 組成。client 提供 SEARCH，INSERT，DELETE 和 UPDATE 接口來使得應(yīng)用程序訪問 KV 對。MNs 存儲復(fù)制的內(nèi)存管理信息（memory management information，MMI）、哈希索引和 KV 對。master 是一個(gè)集群管理進(jìn)程，僅負(fù)責(zé)初始化 client 和 MNs，并在 client 和 MNs 故障時(shí)恢復(fù)數(shù)據(jù)。

RACE Hashing

ATC 20 中 One-sided rdma-conscious extendible hashing for disaggregated memory 的哈希。

如下圖，該文使用的是一種單邊 RDMA 友好的哈希索引 RACE hashing，它包含多個(gè) 8 字節(jié)的 slot，每個(gè) slot 存儲一個(gè)指向 KV 對地址的指針，一個(gè) 8 位指紋（fingerprint，F(xiàn)p）即鍵的哈希值的一部分，以及 KV 對的長度（Len）。對于 SEARCH 請求，client 先根據(jù)目標(biāo)鍵的哈希值讀取哈希索引的 slot，然后根據(jù) slot 中的指針讀取 MN 上的 KV 對。對于 UPDATE，INSERT 和 DELETE 請求，先將 KV 對寫入 MN，然后使用 RDMA_CAS 操作原子地修改哈希索引中相應(yīng)的 slot 中的指針（先寫真實(shí)的數(shù)據(jù)，再替換指針）。

The SNAPSHOT Replication Protocol

解決挑戰(zhàn)一。

為了有效地維護(hù)復(fù)制哈希索引中 slot 的強(qiáng)一致性，F(xiàn)USEE 提出了 SNAPSHOT 復(fù)制協(xié)議，這是一種 client 為中心的復(fù)制協(xié)議。

在完全內(nèi)存分離的情況下有效地實(shí)現(xiàn)線性化有兩個(gè)主要的挑戰(zhàn)。第一個(gè)是如何使得 reader 在讀寫沖突期間避免讀取不完整的狀態(tài)。第二個(gè)是如何在不昂貴地對所有沖突請求進(jìn)行序列化的情況下解決寫-寫沖突（how to resolve writewrite conflicts without expensively serializing all conflicting requests）。

對于讀取數(shù)據(jù)的操作，之前的 RACE hash 已經(jīng)提過，寫入數(shù)據(jù)是先將真實(shí)的 KV 數(shù)據(jù)寫入，再去用 RDMA 原子操作替換 slot 中的值，讀取時(shí)先用 RDMA READ 操作讀取 slot，因?yàn)樵硬僮鞯脑有?，讀取 slot 不會讀到不完整的狀態(tài)，之后再根據(jù) slot 中的信息讀取真實(shí)的數(shù)據(jù)，而真實(shí)的數(shù)據(jù)是在 slot 更新前寫入的，所以也不會出現(xiàn)數(shù)據(jù)不完整的情況。所以讀取數(shù)據(jù)沒啥問題。

對于寫沖突的處理，原文描述有點(diǎn)多，這里就以下圖為例子。首先有一個(gè)主 slot 和 3 個(gè)備份， client 1 和 2 同時(shí)準(zhǔn)備更改 slot（真實(shí)數(shù)據(jù)先寫完了），client 1 想將 A 寫成 B，client 2 想將 A 寫成 C。

第 1 步，client 們先讀取主 slot 的值，這里是 A。

第 2 步，client 們先用廣播的 RDMA CAS 操作試圖去操作備份 slot 中的值（這里如果 slot 中是 A，就將 A 改為想寫的值），因?yàn)?CAS 操作的原子性，舊值只能被更改一次，client 1 將 A 改了 B，client 2 就無法改為 C 了，這里從 AAA 改為了 BBC。因?yàn)?CAS 操作會返回操作時(shí) slot 中的值，所以每個(gè) client 可以根據(jù)返回值推測出最后的結(jié)果（只有返回值是期待值 A，才會替換為自己想寫的值）， 所以如 client 1 可以根據(jù)返回值 AAC 推測出更改后的值為 BBC。

第 3 步，首先有 3 個(gè)規(guī)則。規(guī)則 1：成功修改所有備份 slot 的 client 是最后寫入者（last writer）。

規(guī)則 2：已成功修改大部分備份 slot 的 client 是最后寫入者。

規(guī)則 3：如果前兩條規(guī)則都不能確定最后寫入者，則寫入最小目標(biāo)值的 client 被認(rèn)為是最后寫入者。

總體上就是多數(shù)優(yōu)先，最后寫入者就是獲勝者，就是本次沖突最后保留和更改的值。如這里根據(jù)規(guī)則，client 1 是最后寫入者，所以 client 1 先將備份 slot 全寫為 B，再將主 slot 也改為 B，而 client 2 知道自己不是最后寫入者，它反復(fù)的讀取主 slot 的值，直到主 slot 的值被改變，即不為 A。

SNAPSHOT 保證有界的最壞情況延遲，在觸發(fā)規(guī)則 1 的情況下，需要 3 個(gè) RTT 才能完成一次 WRITE 操作。在觸發(fā)規(guī)則 2 或規(guī)則 3 的情況下，分別需要 4 或 5 個(gè)RTT。

Two-Level Memory Management

解決挑戰(zhàn)二。

該方法的關(guān)鍵思想是將以 server 為中心的內(nèi)存管理任務(wù)拆分為在 MN 和 client 上運(yùn)行的計(jì)算輕型粗粒度管理和計(jì)算密集型細(xì)粒度管理。

FUSEE 首先對多個(gè) MN 上的 48 位內(nèi)存空間進(jìn)行復(fù)制和分區(qū)，使用一致性哈希將一個(gè)區(qū)域映射到哈希環(huán)中的一個(gè)位置，然后將副本存儲在該位置之后的 r 個(gè) MN 中，并將主要區(qū)域放置在第 r 個(gè) MN 中。

下圖是 FUSEE 的兩級內(nèi)存分配。第一層是低計(jì)算要求的粗粒度 MN 端內(nèi)存塊分配，每個(gè) MN 將其本地內(nèi)存區(qū)域劃分為粗粒度的內(nèi)存塊，例如 16 MB（應(yīng)該就是下圖中一個(gè) block 16 MB 的意思吧），并在每個(gè)內(nèi)存區(qū)域之前維護(hù)一個(gè)塊分配表， 對于每個(gè)內(nèi)存塊，塊分配表記錄了它被分配給的 client 的 ID (CID)。 Client 通過向 MN 發(fā)送 ALLOC 請求來分配內(nèi)存塊，MN 收到 ALLOC 請求后，從其主內(nèi)存區(qū)域之一分配內(nèi)存塊，將 client ID 記錄在主區(qū)域和備用區(qū)域的塊分配表中，并將內(nèi)存塊的地址回復(fù)給 client。 第二層是細(xì)粒度的 client 對象分配，分配小對象來保存 KV 對。 Client 使用 slab 分配器來管理從 MN 分配的塊，slab 分配器將內(nèi)存塊拆分為不同大小級別的對象，然后從適合它的最小尺寸類中分配一個(gè) KV 對（大致就是每個(gè)塊內(nèi)又被分為了各種大小固定且一致的 object，要存 KV 的時(shí)候選個(gè)合適大小的空閑 object）。

為了使 client 高效回收釋放的內(nèi)存對象，F(xiàn)USEE 在每個(gè)內(nèi)存塊之前存儲了一個(gè)空閑位圖，其中每個(gè)位表示一個(gè)對象在內(nèi)存塊中的分配狀態(tài)。分配塊時(shí)，空閑位圖被初始化為全零。釋放對象時(shí)，client 使用 RDMA_FAA 操作將空閑位圖中的相應(yīng)位設(shè)置為 1。通過讀取空閑位圖，client 可以很容易地知道自己的內(nèi)存塊中被釋放的對象，并在本地回收它們。FUSEE 使用后臺線程以批處理的方式周期性釋放和回收內(nèi)存對象，避免在 KV 訪問的關(guān)鍵路徑上進(jìn)行額外的 RDMA 操作。

Embedded Operation Log

解決挑戰(zhàn)三。

大致是，如下圖，用日志來容災(zāi)和恢復(fù)。為了減少DM上的日志維護(hù)開銷，F(xiàn)USEE 用一個(gè) RDMA_WRITE 操作，將嵌入式日志條目與其對應(yīng)的 KV 對一起寫入。然后日志里有前一個(gè)對象的指針，后一個(gè)對象的指針，舊的值，CRC 驗(yàn)證位，操作碼，和 used 位。 used 位指示對象是在使用中還是空閑，在整個(gè)對象的末尾存儲 used 可以用來檢查整個(gè)對象的完整性（RDMA 的性質(zhì)來保證）。因?yàn)橛星昂髮ο蟮闹羔?，這些操作就被組織成了一個(gè)鏈表，可以方便管理日志和用于故障修復(fù)。

那么如何知道每個(gè)對象的前后指針呢？這和前面的設(shè)計(jì)有關(guān)，如下圖 b，因?yàn)橛?client 本身來管理其得到的內(nèi)存塊，對于每個(gè)大小級別，client 在本地將遠(yuǎn)程空閑對象的地址組織為一個(gè)空閑列表，然后對象總是從本地空閑列表的頭部分配，每個(gè)大小類別的分配順序是預(yù)先確定的，前后指針也就是已知的了。

Optimizations

自適應(yīng)索引緩存。 搞個(gè)閾值判斷寫入密集型和讀密集型，只有讀密集型用緩存讀數(shù)據(jù)，具體看原文。

RDMA-related optimizations. 如下圖

Failure Handling

看原文吧。

實(shí)驗(yàn)

實(shí)驗(yàn)配置

Run all experiments on 22 physical machines (5 MNs and 17 CNs) on the APT cluster of CloudLab. Each machine is equipped with an 8-core Intel Xeon E5-2450 processor, 16GB DRAM, and a 56Gbps Mellanox ConnectX3 IB RNIC. These machines are interconnected with 56Gbps Mellanox SX6036G switches.

Microbenchmark Performance

時(shí)延結(jié)果如下圖，F(xiàn)USEE 在 INSERT 和 UPDATE 上表現(xiàn)最好，因?yàn)?SNAPSHOT 復(fù)制協(xié)議限制了 RTT。FUSEE 的 SEARCH 延遲略高于 Clover，因?yàn)?FUSEE 在單個(gè) RTT 中讀取哈希索引和 KV 對，這比在 Clover 中僅讀取 KV 對慢。FUSEE 的 DELETE 延遲略高于 pDPM-Direct，因?yàn)?FUSEE 在單個(gè) RTT 中寫入日志條目并讀取哈希索引，這比 pDPM-Direct 僅讀取哈希索引慢。

吞吐結(jié)果如下：pDPM-Direct 的吞吐量受其遠(yuǎn)程鎖的限制。 Clover，但可擴(kuò)展性仍然低于 FUSEE，因?yàn)樵獢?shù)據(jù)服務(wù)器的 CPU 處理能力限制了它的吞吐量。 FUSEE 通過消除元數(shù)據(jù)服務(wù)器的計(jì)算瓶頸并有效解決與 SNAPSHOT 復(fù)制協(xié)議的沖突，提高了整體吞吐量。

YCSB Performance

還有很多，看原文。

個(gè)人看法

感覺這篇和上一篇 ROLEX 都像是針對之前的頂會中的一個(gè)工作，進(jìn)行適配或者優(yōu)化，然后都是分離式內(nèi)存系統(tǒng)下的 KV store，不過 ROLEX 側(cè)重的是 KV store 中的一個(gè)點(diǎn)，學(xué)術(shù)界的感覺濃一點(diǎn)，這篇側(cè)重整體 KV Store，功能完整性多點(diǎn)，工業(yè)界的感覺濃一點(diǎn)，設(shè)計(jì)很巧妙，但是累了不想噴了，寫的是真難看。

如有問題，歡迎批評指正~~~~