FAST23-ROLEX: A Scalable RDMA-oriented Learned Key-Value Store f
題目太長，標題又放不下了。。。
FAST23-ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems
FAST 23 的 best paper
作者的主頁 ：https://iotlpf.github.io/
論文的 GitHub ：https://github.com/iotlpf/ROLEX
論文的鏈接 ：https://www.usenix.org/system/files/fast23-li-pengfei.pdf
簡介
分離式內存（Disaggregated memory）系統(tǒng)，內存節(jié)點計算資源稀缺，計算節(jié)點通過 RDMA 訪問內存結點。該文針對有序鍵值存儲（例如基于B樹和學習索引）在該系統(tǒng)架構下性能不佳（基于樹的實現(xiàn)需要多次網(wǎng)絡往返搜索數(shù)據(jù)，基于學習索引的實現(xiàn)依賴內存節(jié)點的計算資源）的問題，設計實現(xiàn)了一種基于 RDMA 的可擴展并使用學習索引的鍵值存儲 ROLEX。ROLEX 使用重新訓練分離（retraining-decoupled）的學習索引方案，通過為學習模型添加偏差和一些數(shù)據(jù)移動約束來將模型重新訓練與數(shù)據(jù)修改操作分離?；诓僮鞣蛛x，計算節(jié)點通過通過單邊 RDMA 進行數(shù)據(jù)修改，具有高可擴展性。將模型重新訓練從數(shù)據(jù)修改的關鍵路徑中刪除，并使用內存節(jié)點中的專用計算資源異步執(zhí)行。在 YCSB 和實際工作負載上的實驗結果表明，ROLEX 在靜態(tài)工作負載上具有競爭性能，并且在動態(tài)工作負載上的性能顯著提高，最高性能是內存解聚系統(tǒng)上現(xiàn)有方案的 2.2 倍。
背景
Disaggregated Memory Systems
分離式內存系統(tǒng)將單體服務器分解為獨立的網(wǎng)絡附加組件，通過獨立擴展硬件資源，來滿足各種應用需求。不同節(jié)點通過遠程直接內存訪問（RDMA）網(wǎng)卡進行通信。RDMA 的重要特性是能通過單邊 verbs（包括 RDMA READ， WRITE，ATOMIC）使計算節(jié)點直接訪問內存節(jié)點，而不涉及遠端的 CPU。ATOMIC 操作的粒度為 8B，并且可以通過門鈴批處理完成多個 READ 和 WRITE 操作減少網(wǎng)絡延遲。此外，即使內存池中沒有強大的 CPU，每個內存節(jié)點通常包含由 FPGA 或 NIC 中的 ARM 核提供的專用計算資源，用于操作卸載。
Network-Attached Ordered KV Store
該文主要關注的是網(wǎng)絡附加（network-attached）的有序鍵值存儲，包括基于樹的索引和學習索引，這些索引保持所有數(shù)據(jù)排序并滿足范圍查詢需求。
基于樹的結構（Tree-based Structures）。基于樹的結構（如B+-樹）將數(shù)據(jù)存儲在葉節(jié)點中，并構建多級內部節(jié)點來搜索葉子節(jié)點。然而，該結構的緩存索引占用的空間比較大，本地機器無法緩存整個索引結構，必須消耗多個RTT 來搜索內部節(jié)點，使得使用單邊 RDMA 訪問遠程數(shù)據(jù)時變得低效。
學習索引（Learned Indexes）。學習型索引將搜索數(shù)據(jù)的過程視為回歸模型，通過排序的鍵（key）的近似累積分布函數(shù)（CDF）記錄來所有數(shù)據(jù)的位置。學習模型比基于樹的結構節(jié)省了 2-4 個數(shù)量級的空間，使得本地機器能夠緩存整個索引結構，避免使用多個 RTT 來搜索。先前的工作 XStore 用內存節(jié)點來處理數(shù)據(jù)修改，擴展了過時的模型到較大的預測范圍，以確保新插入的數(shù)據(jù)被包含。但是在分離式內存系統(tǒng)上，內存節(jié)點的計算資源有限，無法高效地處理密集的修改請求。新模型無法及時重訓練，而過時的模型由于模型擴展，無法保證能在一個 RTT 內搜索到遠程數(shù)據(jù)，本地緩存變得無效，隨后的數(shù)據(jù)請求通過經典的 RPC 傳輸?shù)絻却婀?jié)點，但是 RPC 需要消耗內存節(jié)點的計算資源，整體性能顯著降低。
現(xiàn)有的鍵值存儲的性能分析
FG 和 Sherman 設計了支持 RDMA 的 B-link 樹，使計算節(jié)點能夠通過單邊 RDMA verbs 修改 B-link 樹。EMT-D 是即基于 eRPC 的 Masstree，XStore-D 是之前基于學習索引的 B 樹，他們兩用來以分析基于 RPC 的 KV 存儲在分離式內存系統(tǒng)上效率低下的原因。
下圖的 a，b，c 子實驗圖分為說明了：1. 學習索引在大規(guī)模靜態(tài)工作負載上的表現(xiàn)優(yōu)于基于樹的結構；2. 在動態(tài)工作負載下，索引緩存會失效；3. 分離式系統(tǒng)需要有效的單邊 RDMA 操作。（詳細的分析看原文）
3 個挑戰(zhàn)
文章總結了有序鍵值存儲在分離式系統(tǒng)中的 3 個挑戰(zhàn)：
Limited computing resources on memory nodes. 內存節(jié)點計算資源有限。
Overloaded bandwidth for data transferring. 數(shù)據(jù)傳輸帶寬過載，具體來說，計算節(jié)點需要消耗大量網(wǎng)絡帶寬來平衡基于樹的結構（如，多級節(jié)點拆分和合并）或獲取大量數(shù)據(jù)以重新訓練學習索引的模型（由計算節(jié)點來訓練模型）。
Inconsistency issue among different nodes. 一致性問題老生常談了。
設計與實現(xiàn)
Overview
與之前的方案不同，ROLEX 不在內存節(jié)點上維護 B 樹 處理數(shù)據(jù)請求。ROLEX 在存儲數(shù)據(jù)上構建了重新訓練分離（retraining-decoupled）的學習索引，計算節(jié)點通過單邊 RDMA 操作處理數(shù)據(jù)請求。ROLEX 采用原子設計執(zhí)行索引操作，并通過具有一致性保證的分離插入和重新訓練操作異步地重新訓練模型。
下圖展示了 ROLEX 的總體架構。在內存池中，ROLEX 將所有數(shù)據(jù)存儲到固定大小的葉子節(jié)點中（一個葉子就是一個數(shù)組），并基于這些數(shù)據(jù)構建了一個基于插入和重訓練操作解耦的學習索引。對于處理動態(tài)工作負載，計算節(jié)點直接修改遠程葉子節(jié)點而無需重新訓練模型。通過添加一些偏差和數(shù)據(jù)移動約束，未重新訓練的模型能夠正確識別所有數(shù)據(jù)。為了使用單邊 RDMA 為新數(shù)據(jù)構建足夠的數(shù)據(jù)葉，提出了葉原子移位方案（leaf-atomic shift scheme），該方案還保持所有數(shù)據(jù)排序以進行范圍查詢并避免不同計算節(jié)點之間的沖突。因為內存節(jié)點獲取所有待處理的重訓練數(shù)據(jù)到計算節(jié)點來進行模型訓練會消耗大量網(wǎng)絡帶寬，且再訓練開銷主要來自數(shù)據(jù)合并和重新排序，而訓練算法的復雜度僅為 O(N)，所以 ROLEX 借助葉表（leaf table）在內存節(jié)點上異步重新訓練模型。重新訓練后，ROLEX 使用陰影重定向方案（shadow redirection scheme）更新內存池中的模型，而計算節(jié)點直到下次讀取之前不會同步重新訓練的模型。
Retraining-decoupled Learned Indexes
在動態(tài)工作負載中，學習索引的挑戰(zhàn)數(shù)據(jù)位置變動后避免學習模型數(shù)據(jù)丟失（及無法通過模型獲取數(shù)據(jù)位置）。
在動態(tài)工作負載中合并學習索引的挑戰(zhàn)在于保持所有數(shù)據(jù)排序和在插入期間避免學習模型數(shù)據(jù)丟失的高開銷。如下圖所示，紅線代表在黑點上（即訓練數(shù)據(jù)）訓練的線性回歸模型。只要數(shù)據(jù)未移出預測范圍[pred-ε，pred+ε]（即藍色塊），就可以在此預測范圍內找到所有數(shù)據(jù)，其中 ε 是預定義的最大模型誤差。當插入一些新數(shù)據(jù)后，點 a 移動到 a'，超出了預測范圍。為記錄新位置，需要逐步重新訓練模型，包括數(shù)據(jù)重排序、重訓練模型和將模型同步到所有計算節(jié)點。這時系統(tǒng)會被阻塞，直到重新訓練和同步完成，進而產生長延遲并降低整個系統(tǒng)的性能。
該文修改了訓練算法并添加了一些約束條件，以幫助非重新訓練的模型在不重新訓練的情況下始終找到所有數(shù)據(jù)，避免了頻繁重新訓練模型。
訓練算法。使用改進的 OptimalPLR 算法來訓練分段線性回歸（piecewise linear regression，PLR）模型，其中 OptimalPLR 算法已經被證明在保證較小的時間和空間復雜度（O(N)）的同時具有最小數(shù)量的 PLR 模。OptimalPLR 的關鍵思想是在訓練數(shù)據(jù)上構建多個具有 2ε 寬度的最優(yōu)平行四邊形，其中最優(yōu)平行四邊形被定義為一個垂直方向上寬度為 2ε 的平行四邊形，使得沒有訓練數(shù)據(jù)在平行四邊形之外，如上圖所示的藍色塊。為確保訓練出的模型即使在插入數(shù)據(jù)后仍能找到所有數(shù)據(jù)，在預測計算中添加偏差（表示為δ），以及添加一些數(shù)據(jù)移動的限制，改進了 OptimalPLR 算法。
如公式 1 ，優(yōu)化的平行四邊形通過保證所有數(shù)據(jù)的預測位置 f(Xi) 和真實位置 Yi 之間的距離不大于預定義的最大模型誤差（ε）來確定，而預測范圍 Prange 則是通過添加額外的 δ 來計算。因此，所有數(shù)據(jù)預測范圍的覆蓋面積大于確定的優(yōu)化平行四邊形，即圖 3 中將藍色塊擴展為黃色塊。在這種情況下，只要數(shù)據(jù)移動的位置不超過 δ，模型就不需要重新訓練。
數(shù)據(jù)移動約束。1. 在固定大小的葉內移動數(shù)據(jù)。 在訓練階段將數(shù)據(jù)存儲到固定大小的數(shù)組（稱為葉節(jié)點）中，每個葉節(jié)點最多包含 δ 個數(shù)據(jù)。 所有數(shù)據(jù)只允許在分配給它們的葉內移動。再將位置預測轉換到葉節(jié)點預測，即，學習模型通過公式 2 給出一系列可能包含數(shù)據(jù)的葉節(jié)點。因為數(shù)據(jù)移動被限制在葉節(jié)點內，所以可以通過單邊 RDMA 操作讀取 Lrange 來獲取數(shù)據(jù)。2. 同義詞葉共享（Synonym-leaf sharing）。當一個葉節(jié)點（l）內的插槽不夠時，會分配一個新的葉節(jié)點（nl）來存放更多的數(shù)據(jù)，其中 nl 與 l 使用相同的位置（即用于訓練的標簽）。該文將 nl 定義為 l 的同義詞葉子，并通過指針鏈接。同義詞葉子的數(shù)據(jù)相互移動以便于數(shù)據(jù)排序。nl 不會改變模型記錄的位置，因此學習索引仍然通過 公式 2 計算 Lrange，但是需要搜索由 Lrange 范圍內葉節(jié)點的同義詞葉子。
當一個葉子(l)的插槽不足時，我們分配一個新葉子(nl)來容納更多的數(shù)據(jù)，其中nl與l使用相同的位置（即用于訓練的標簽）共享。我們將nl定義為l的同義詞葉子，通過指針鏈接。同義詞葉子的數(shù)據(jù)相互移動以便于數(shù)據(jù)排序。由于nl不會改變模型記錄的位置，因此學習索引仍然通過方程2計算Lrange。此外，我們需要搜索由Lrange引用的同義詞葉子，因為數(shù)據(jù)可能位于預測和同義詞葉子中。
ROLEX Structure
Memory pool stores data. 所有數(shù)據(jù)被存儲在固定大小的葉節(jié)點中，所有葉子都存儲在一個 RDMA 注冊內存區(qū)域中分配的連續(xù)區(qū)域中（稱為葉節(jié)點區(qū)域）。葉子區(qū)域的結構如 Figure 2 所示，其中前兩個 8B 數(shù)據(jù)分別用于指示已分配的葉子數(shù)量（alloc_num）和葉子區(qū)域可以分配的總數(shù)（那個圖貌似看不出）。其余的葉子區(qū)域存儲大量的葉節(jié)點，每個葉節(jié)點包含 δ 個鍵值對。分配新葉節(jié)點時，使用原子操作 FAA 讀取 alloc_num 并寫入alloc_num + 1，然后將數(shù)據(jù)存儲到 alloc_num 指向的葉節(jié)點中。通過葉節(jié)點區(qū)域的起始位置加上偏移量來訪問葉節(jié)點。因為ROLEX 通過固定大小的葉子分配和回收空間，在 ROLEX 中可以有效地減輕碎片化和垃圾收集。
在存儲的葉子上會訓練多個 PLR 模型，模型之間不存在位置依賴關系，每個模型由四個部分組成，包括覆蓋的最小鍵、模型參數(shù)、葉表（leaf table，LT）和同義詞葉表（synonym leaf table，SLT），如 Figure 4 所示。LT 和 SLT 存儲葉號（即分配時的alloc_num），以訪問葉節(jié)點。通過在最小鍵上訓練上層模型（upper models）來對獲得的 PLR 模型進行索引（我猜就是還有個上層模型來確定用哪個 PLR 模型），其中上層模型不包含葉表。重復這個過程，并構建多級模型，類似于 PGM-index，由于空間消耗較小，這些模型在計算節(jié)點中被完全緩存。
Compute pool caches indexes. 新添加的計算節(jié)點通過 RNIC 識別共享的內存池，并獲取模型和葉節(jié)點區(qū)域的起始地址。新的計算節(jié)點從模型區(qū)域讀取學習模型后，根據(jù)學習模型的預測范圍高效地訪問遠程數(shù)據(jù)，其中預測范圍條目包含葉節(jié)點區(qū)域號和葉節(jié)點號。ROLEX 通過單邊 RDMA 操作在計算節(jié)點上處理各種數(shù)據(jù)請求（例如搜索、更新、插入和刪除）。
One-sided Index Operations
ROLEX 提出了一種葉原子轉換方案（leaf-atomic shift scheme），既保證了計算節(jié)點同時修改時的數(shù)據(jù)一致性，又只需要少量的的RDMA 操作。 該設計為不同的計算節(jié)點自動分配共享內存池中的寫入?yún)^(qū)域，并使每個計算節(jié)點能夠通過陳舊的索引結構訪問數(shù)據(jù)。
LT 和 SLT 的結構。 ROLEX 通過原子操作 FAA 利用葉區(qū)域中的 8B 的 alloc_num 來實現(xiàn)無鎖葉節(jié)點分配，并使用 LT 中的 8B 條目來保證一致的葉節(jié)點修改。 LT 和 SLT 的結構如上面的 Figure 4 所示。SLT 中的第一個槽位（slot_use）表示 SLT 中槽位被使用了多少，在構造新的同義詞葉時修改。LT 和 SLT 的其他槽存儲 8B 大小的條目（entries），每個條目由鎖（1 位）、葉區(qū)號（7 位）、指針（8 位）和葉號（48 位）組成。 由于只鎖定當前葉子而不是模型下的所有葉子，因此鎖是輕量級和細粒度的。使用葉區(qū)號和葉號來確定葉節(jié)點，而指針指向 SLT 的偏移量以鏈接同義詞葉節(jié)點。 例如，如 Figure 4 中，葉子 0 的指針指向 3，說明葉子 0 有一個同義詞葉節(jié)點存儲在SLT 的第 3 個位置，而這個同義詞葉子存儲在葉子區(qū)域的第 6 個位置。 LT 的大小在訓練階段確定，而 SLT 的大小固定為包含 2 的 8 次方個槽。 每個葉區(qū)域最多注冊 2 的 48 次方個葉子，而一個模型最多可以構造 (2 的 8 次方 - 1) 個同義詞葉子。
Point query. 對于給定的鍵，計算節(jié)點通過以下步驟搜索遠程數(shù)據(jù)：1. 根據(jù)公式 2 用本地學習索引預測 Lrange；2. 通過查找 LT 和 SLT 將葉節(jié)點位置轉換為物理地址，計算方式如公式 3；3. 根據(jù)物理地址通過 doorbell 批量的讀取葉節(jié)點；4. 搜索讀取的葉節(jié)點，根據(jù)值（value）指針進一步讀取值。
Range query. 和上面步驟相似。
Insert. 步驟如下：1. Fetching. ?計算節(jié)點像點查詢一樣獲取遠程葉子；2. Fine-grained locking. 計算節(jié)點根據(jù)數(shù)據(jù)順序確定要插入的葉節(jié)點，通過CAS 操作將 LT 表項的鎖位置改為 1 來鎖定。加鎖后，計算節(jié)點讀取該葉節(jié)點及其同義詞葉節(jié)點以保證數(shù)據(jù)是最新的。即使葉節(jié)點及其同義詞葉子在被鎖定之前被其他計算節(jié)點修改，向其中插入數(shù)據(jù)仍然保持所有數(shù)據(jù)排序，因為葉節(jié)點中的數(shù)據(jù)只允許在 葉節(jié)點及其同義詞葉節(jié)點內移動。3. Writing and unlocking. 計算節(jié)點按照數(shù)據(jù)順序向獲取到的葉節(jié)點中插入數(shù)據(jù)，并通過 CAS 解鎖。當獲取的葉節(jié)點沒有足夠的空槽時，計算節(jié)點會構造一個新的同義詞葉節(jié)點，如 Figure 5。
Update. 和點查詢一樣獲取遠程葉節(jié)點，當給定的鍵在其中一個獲取的葉子中時，鎖定并重新讀取相應的葉子以確保數(shù)據(jù)是最新的，最后更新鍵值項并解鎖遠程葉子。
Delete. 先像插入操作一樣獲取和鎖定遠程葉節(jié)點，如計算節(jié)點獲取葉節(jié)點 L1 及其同義詞葉節(jié)點 L5-8，當 Key 在其中一個葉節(jié)點，例如 L6，計算節(jié)點刪除 L6 中的 Key，而其他葉節(jié)點不被修改。 當刪除后 L6 變?yōu)榭諘r，計算節(jié)點通過修改葉子表的方式刪除 L6，即將 L5 鏈接到 L7。 ?計算節(jié)點將 L6 寫入內存節(jié)點并解鎖葉子。直到下一次保留時才刪除空的訓練葉子 L1，以避免預測錯誤。其他計算節(jié)點在觀察到同義詞葉節(jié)點中的數(shù)據(jù)未排序時識別出被刪除的葉子，從而進一步同步葉子表并讀取遠程數(shù)據(jù)。
Asynchronous Retraining
再訓練開銷來自數(shù)據(jù)排序和再訓練算法。ROLEX 在內存節(jié)點上異步重新訓練數(shù)據(jù)，以實現(xiàn)網(wǎng)絡消耗和計算資源利用之間的有效權衡。ROLEX 維護一個循環(huán)隊列 (CirQ) 來識別待處理的再訓練模型，并使用陰影重定向方案在不阻塞系統(tǒng)的情況下再訓練模型。 具體來說，當模型消耗了 2 的 7 次方個 SLT 槽時，計算節(jié)點在 CirQ 的末尾插入模型的指針。內存節(jié)點定期檢查 CirQ 的頭部進行再訓練，CirQ 在后臺重新訓練模型并構建新的 LT 以合并舊的 LT 和 SLT，而計算節(jié)點能并發(fā)訪問舊模型。（估計一次是訓練一個 PLR 模型）
一致性保證。如 Figure 6 顯示了當內存節(jié)點重新訓練葉節(jié)點 L1-5 時的一致性保證，其中 L5 是 L3 的同義詞葉節(jié)點。 因為是異步的重訓練，計算節(jié)點可以在重訓練的同時修改數(shù)據(jù)，當數(shù)據(jù)的位置沒有被新模型重新訓練時，這會導致不一致，例如，構造了 L5 的新同義詞葉節(jié)點 L8 和在同義詞葉子內移動數(shù)據(jù)。ROLEX 通過將未重新訓練的數(shù)據(jù)重定向到新模型的新 SLT 中來確保數(shù)據(jù)的一致性。
ROLEX 通過查看出現(xiàn)在舊 LT 或 SLT 中但未出現(xiàn)在新 LT 中的條目被識別為未重新訓練的葉節(jié)點（如 L8）。 如 Figure 6 ，重訓練后用新模型替換舊模型時，ROLEX 鎖定舊模型并將 L8 插入新 SLT，并在解鎖前將模型指針更新。類似地，通過檢查舊葉表和新葉表來識別移除的葉。
ROLEX 通過檢查之前訓練過的葉子來識別移動的數(shù)據(jù)的新位置。 如 Figure 6 ，在重訓練開始前，將每個葉節(jié)點中最左邊和最右邊的數(shù)據(jù)分別表示為 Xl 和 Xr，如 X3l 表示 L3 的最左邊數(shù)據(jù)。 重訓練時，舊模型在 L3 中插入 15，在新構造的同義詞葉節(jié)點 L9 中插入 18 和 24。問題在于確保新模型正確識別被舊模型修改的數(shù)據(jù)，包括葉節(jié)點中的訓練數(shù)據(jù)（例如，X3l 和 X3r 之間的數(shù)據(jù)）和兩個排序的葉節(jié)點之間的新數(shù)據(jù)（例如，X3r 和 X5l 之間的數(shù)據(jù)）。 根據(jù)公式 2，新模型預測 L3 中 X3l 和 X3r 之間的數(shù)據(jù)，如這里的 5 和 18 之間改變的數(shù)據(jù) 15 和 18，新模型仍然能預測到在 L3 及其同義詞葉節(jié)點中，但是 X3r 和 X5l 之間的數(shù)據(jù)（如 24）會出現(xiàn)不一致狀態(tài)，因為新模型可能會預測 24 在 L5 中而不是在 L3 的同義詞葉節(jié)點 L9 中。為避免此類錯誤，ROLEX 會檢查前一葉（即 L3，直面說過有葉節(jié)點有同義詞葉，會一起檢查）以正確識別修改后的數(shù)據(jù)。
ROLEX 不需要重新訓練或移動任何數(shù)據(jù)，因為所有數(shù)據(jù)都已在運行時按葉表排序。在重新訓練期間沒有數(shù)據(jù)丟失，因為所有葉節(jié)點要么被新模型重新訓練，要么被插入到新的 SLT 中。文章認為重訓練頻率較低，訓練模型的速度比填充同義詞葉節(jié)點的速度要快得多。 此外，ROLEX 有一個優(yōu)先級隊列來識別和訓練 SLT 幾乎要滿了的模型，以避免該模型在 SLT 中的插槽不足。
實驗
實驗相關事項
3 個計算節(jié)點和 3 和存儲節(jié)點，通過在內存結點限制只能使用一個 CPU core 來模擬計算資源有限。
Workload: YCSB; Lognormal & Normal distributions. 8B keys and values
對比對象：FG [SIGMOD19]，Sherman [SIGMOD'22]，Masstree [NSDI19]，XStore-D?[OSDI20]（本來都是有論文鏈接的，但是 b 站只能放站內鏈接。。。。。。）
YCSB 的實驗結果
不同場景的性能
可拓展性實驗
優(yōu)化措施可行性驗證
個人看法
乍一看確實以為和 XStore 很像，但 2 個工作還是很有大的差別的，是新場景下的舊系統(tǒng)表現(xiàn)出的新問題的新解決方法。學習索引了解不深，看起來文章內容確實很充實，可能個人水平問題，文章有的部分看起來描述上有點繞。zuo pengfei 在分離式內存場景下，就老的系統(tǒng)優(yōu)化配置做了好幾篇工作了，可以學著取搞搞。
按著論文章節(jié)來是不是太詳細了，又太花時間了。。。。
如有問題，歡迎批評指正?。?/strong>
