EuroSys'22 p2KVS

語言: CN / TW / HK

時間 2022-07-13 10:00:27 分佈式和存儲的那些事

主題: RocksDB SSD

Abstract

通過將速度較慢的硬盤驅動器(hdd)替換為速度更快的固態硬盤驅動器(ssd)來提高鍵值存儲(KVS)性能的嘗試一直未能達到ssd和hdd之間的巨大速度差距所暗示的性能提升，特別是對於小KV項目。我們通過實驗和整體探索了現有基於lsm樹的 kvs 運行在具有多核處理器和快速ssd的強大現代硬件上性能低下的根本原因。我們的發現表明，在單線程和多線程執行環境下，全局預寫日誌(WAL)和索引更新(MemTable)可能成為與常見的lsm樹壓縮瓶頸一樣基本和嚴重的瓶頸
為了充分利用成熟KVS和底層高性能硬件的性能潛力，我們提出了一種可移植的二維KVS並行化框架，稱為p2KVS。在水平的kvs -instance維度上，p2KVS將一個全局KV空間劃分為一組獨立的子空間，每個子空間由一個LSM-tree實例和一個固定在一個專用核上的專用工作線程來維護，從而消除了共享數據結構上的結構性競爭。在垂直的intra-KVS-instance維度上，p2KVS將用户線程從kvs -worker中分離出來，並在每個worker上提供基於運行時隊列的機會批處理機制，從而提高了進程效率。由於p2KVS被設計和實現為一個用户空間請求調度器，將WAL、MemTables和lsm樹作為黑盒來查看，因此它是非侵入性的，具有高度的可移植性。在微觀和宏觀基準測試下，p2KVS比最先進的RocksDB提高了4.6×寫和5.4×讀的速度。

Introduction

動機測試

SSD 相比於 HDD 有更高的 IO 帶寬 10x，更高的 IOPS x100。圖1a表明，儘管RocksDB在高級 SSD 上的讀性能提高了2個數量級，但它在ssd和hdd之間的 寫性能幾乎沒有變化 。
最近的研究[19,36]和我們的實驗結果一致表明， 較小KV對的寫工作負載會使系統的主機 CPU 核過載，而不是受到系統IO帶寬的瓶頸 。

然而，提高處理能力的一種幼稚的方法是通過調用更多的用户線程來充分利用多核CPU的能力。圖1b 顯示，即使有8個用户線程，對於順序PUT、隨機PUT和UPDATE的寫工作負載，每秒查詢(QPS)性能也只分別提高了40%、150%和160%，遠遠沒有達到理想的線性擴展。但是，與單線程情況相比，在寫工作負載下，從基於hdd的系統到基於ssd的系統，三個8線程情況的性能提高不到10%，除了更新操作情況提高了40%。這意味着，RocksDB的設計初衷是充分利用優質SSD，最大限度地提高QPS[22]，但在小型KV工作負載下仍然存在瓶頸。

理論分析

前台任務首先寫 WAL，然後執行寫索引，然後後台任務執行 compaction。
為了幫助理解成熟的kvs在快速的ssd和強大的處理器上性能低下的根本原因，我們使用經過良好優化的RocksDB進行了一系列實驗(詳見第3節)。結果提供了三個揭示性的發現。

首先，對於單個用户線程，日誌記錄或索引都可能造成嚴重的計算瓶頸，嚴重限制隨機的小型寫操作的性能。只有當日志記錄和索引不再是瓶頸時，LSM-tree壓縮才會成為存儲瓶頸。
其次，增加用户線程的數量會產生一些邊際效益，因為共享日誌和索引結構上的爭用非常多，用户線程越多，爭用就越嚴重。
第三，具有多個實例的KVS分片機制仍然受到多個用户線程爭用的影響，以及低效的日誌記錄和索引

本文貢獻

為了克服現有 KVs 的缺陷，提出了可移植的二維並行 KVS 框架來高效利用成熟的生產環境中的 KVs 實現和底層的高性能硬件。

首先，水平維度，採用了一個調度方案來協調多個工作線程，每個線程專門綁定核心，維護自己的單獨的 WAL 日誌，Memtable，以及 LSM tree，來減小共享數據結構上的爭用
其次，垂直層面，設計了一個全局的 KV 訪問層來把用户線程和 KVs 工作線程區分開，訪問層應用策略把進來的請求分發到工作隊列中，進行負載均衡
第三，在每個worker中提出了一種基於運行時隊列的機會批處理機制。對於隊列中未完成的寫請求，OBM 合併它們以分攤 kv 處理和日誌記錄的開銷。對於未完成的讀請求，OBM 調用現有的 multiget 功能，提高處理效率。

與多實例KVS配置不同，p2KVS顯式地消除了實例上用户線程之間的潛在爭用，同時利用批處理機制來提高效率
本文的目標是構建一個在 RocksDB 上的基於線程的並行框架，充分利用硬件特徵同時保留它們現有的功能和內部設計，因此本文的方案是互不干擾的且非侵入式的。
貢獻

我們通過實驗和整體分析並確定了運行在快速ssd和多核處理器上的kvs伸縮性差的根本原因。
我們提出了p2KVS，一個可移植的二維KVS並行化框架，以統一有效地利用KVS實例之間和實例內部的內部並行性。我們進一步設計了一個基於隊列的機會批處理機制，以提高每個工人的處理效率。
我們分別在RocksDB、LevelDB和WiredTiger的[49]上實現了p2KVS原型，並在流行的宏基準和微基準下進行了大量的實驗來評估它。與目前最先進的基於lsm樹的RocksDB和PebblesDB相比，p2KVS對小型kv的寫速度可達4.6x，讀速度可達5.4x。它還優於最先進的基於非lsm樹的KVell。

Background

LSM 不做介紹

RocksDB 併發優化

作為一個經過良好優化的基於生產級 LSM 樹的KVS, RocksDB 通過利用硬件並行性實現了許多優化和配置，以提高其QPS性能。RocksDB中的併發寫進程示例如圖 3 所示。關鍵併發性優化如下：

Group Logging

當多個用户線程併發提交了寫請求，RocksDB 將其組織成為一個組，其中一個線程被選中作為 leader 負責聚合該組內的其他線程的日誌項，然後一次寫入日誌文件，其他線程也就是所謂的 follower，掛起直到日誌文件寫入完成，減少了實際的日誌 I/O，因此提升了 I/O 效率。

併發 Memtable

RocksDB 支持併發跳錶索引，提升 Memtable 的插入的 QPS 約 2x，像 Group Logging，在更新全局元數據時，會同步一組併發更新MemTable的用户線程

Pipelined Write

RocksDB 把不同組的日誌和索引更新步驟流水線化了來減小阻塞
基於 LSM 的 KVs 一般提供了請求批處理操作，也就是 WriteBatch，允許用户執行多個寫類型的請求，RocksDB 將所有請求的日誌記錄操作合併到一個WriteBatch中，就像組日誌記錄機制一樣。

Root Causes of Poor Scalability

單線程

五組實驗，128B KV，10M 條，順序和隨機寫，隨機 UPDATE，順序和隨機讀，分別在 HDD/SATA SSD/NVMe SSD 上測試。
寫性能沒變化，讀性能倒是有很大提升

單線程寫性能表現較差，讀性能較好
8 線程寫性能表現類似

下圖展示了一個用户線程插入小 KV 對應的隨時間變化的性能，順序和隨機。CPU-core 利用率為 100% 的線程分別只佔用 SSD IO 全帶寬的 1/6 和 1/20。連續的隨機寫操作會觸發相應的後台線程執行週期性的刷新和壓縮，這些線程會消耗大約 25% 的 CPU-core 利用率。

現象： 無論是隨機寫還是順序寫，無論是小 KV 還是大 KV，都遠低於 SSD 的實際帶寬

順序寫的帶寬低於隨機寫，小KV 的帶寬低於大 KV
隨機寫大 KV 的吞吐相對最接近設備帶寬

原因： 無論是隨機寫還是順序寫，無論是小 KV 還是大 KV，前台線程 CPU 都接近滿載

除了大 KV 隨機寫以外，CPU 基本都是滿載

現象： 隨機寫因為受到 Compaction 的影響會有較大的性能波動

小 KV 隨機寫，後台線程大約需要使用 25% 的 CPU，前台線程 100%
大 KV 隨機寫，後台線程大約需要使用 60% 的 CPU，前台線程 70%

現象： 大 KV 相比於小 KV 性能表現相對更好

原因：小 KV 的 CPU 滿載的現象更嚴重，因為常常小 KV 意味着更多的數據條數，軟件棧上的執行的請求數更多

當 CPU-core 利用率約70%的用户線程連續插入隨機大KV對(即1KB)時，後台線程的週期性 compaction 操作僅消耗23% IO帶寬和60% CPU-core利用率，如圖4b所示。
以往的研究大多認為LSMtree壓縮是嚴重影響整體性能的主要因素，因為LSMtree壓縮具有寫停頓和寫放大的高IO強度[1,3,18,41,43,46,50,54]。 事實上，使用小型KV對的寫工作負載會使 CPU 核過載，但IO帶寬利用不足，而使用大型KV對的寫工作負載則恰恰相反

ForestDB，TRIAD，Dostoevsky，WiscKey，SifrDB，PebblesDB，LSM-trie，MatrixKV

多線程

多核處理器和基於NVMe的ssd分別具有足夠的計算能力和高並行度的IO能力。自然，利用強大的硬件增加用户線程的數量可以提高KVS的總體吞吐量。另外，在實踐中，數據庫從業者也可以簡單地在高級硬件上配置多個獨立的KVS實例，以提高整體性能。在此分析中，我們考慮由多個用户線程訪問的單實例和多實例兩種情況。每個KVS實例都有自己獨立的日誌文件、MemTable和LSM-tree。
下圖 a 所示為擴展性，在所有並行優化的單實例情況下，寫QPS的伸縮性仍然很差，在32個用户線程時只能獲得微薄的 3x加速。它的吞吐量在24個線程時達到峯值，而在此之後進一步擴展則顯示收益遞減。與單實例情況相比，多實例情況提升80%的高吞吐量和更好的可伸縮性，其吞吐量峯值低於16個線程/實例。

現象： 單實例，24線程達到峯值，綁核之後效果更好，多實例提升明顯，且伸縮性更好，但 16 線程達到峯值

結論：使用多實例帶來的擴展性更好，綁核也能讓擴展性變好

圖 b 則表明 compaction 不再是瓶頸。至少不是主要的瓶頸，即便是多線程情況下。在 16 線程時達到峯值，只有 1/5 的 SSD I/O 帶寬，其中 compaction 佔據的帶寬也不足總的 3/4。和單用户線程類似，前台用户線程的利用率接近 100%，後台線程消耗的 CPU 利用率相對較低。

現象： 單實例，多線程寫操作的 I/O 帶寬遠小於實際的設備帶寬，其中 Compaction 開銷很小，不是主要開銷。

結論：隨着併發增加，Compaction 佔據的開銷比例變化不大，即併發條件下，Compaction 不是瓶頸

現象：單實例，多線程寫操作對應的前台線程 CPU 滿載，後台線程隨着併發數的增加 CPU 開銷變大，但是也還沒有到 CPU 極限。

結論：隨着併發增加，主要瓶頸是來自於前台線程的 CPU 滿載

圖 a 還表明了綁核能帶來 10%-15% 的性能收益，因為不需要切換 CPU

處理時間

下圖展示了不同線程在單個實例下的延遲分解，寫流程分成五個步驟，WAL，Memtable，WAL Lock，Mmetable Lock and Others.

WAL 代表寫前日誌的執行時間，包括 I/O 時間和其他（編碼日誌記錄，計算校驗和，以及添加到寫日誌的 memory buffer）
Memtable 代表插入鍵值對到 Memtable，超過 90% 都是更新跳錶索引信息
WAL Lock 表示與組日誌機制相關的鎖開銷，包括領導線程執行 WAL 時其他用户線程的鎖獲取時間，以及領導線程通知其他線程完成 WAL 執行的時間。
Memtable Lock 代表同一組線程併發寫 MemTable 時的線程同步時間
其他代表其他軟件開銷

鎖開銷：隨着寫入器數量的增加，WAL 和 MemTable 的 CPU 週期百分比從單個線程時的 90% 下降到 32 個線程時的16.3%，而總鎖開銷(即WAL鎖和MemTable 鎖)從幾乎為零增加到 81.4%。更多的寫入器會對共享數據結構(如日誌和MemTable)引入更嚴重的爭用。特別是，只有 8 個線程的 WAL-lock 佔用了一半以上的延遲。 根據 Amdahl 定律，在小型KV對的高併發工作負載下，對特定日誌和索引結構的優化不再有效，因為序列化瓶頸佔延遲的較大比例 。
造成高鎖開銷的主要原因有三個。首先，

RocksDB 的組日誌策略由 leader 進行日誌寫入序列化的操作，並掛起follower;
第二，組中的線程越多，用於解鎖 follwer 線程的 CPU 時間就越多;
最後，將多個線程插入到MemTable中會帶來同步開銷。

現象： 單實例，隨着線程數增加，延遲也不斷增加，其中加鎖操作帶來的開銷比例也不斷增加

原因： 因為涉及到跳錶併發寫的同步操作，以及 Group Logging 的同步操作，線程數增加，爭用越大，延遲越高

Multi-threading, a Double-edged Sword

如上所示的實驗結果表明，多線程在利用並行性方面的優勢可以被線程之間在共享數據結構(如日誌和索引)上的爭用所抵消。因此，應該找到一個謹慎的權衡，以達到最佳的整體結果。考慮到這一點，接下來，我們將研究多線程對日誌記錄和索引這兩個關鍵瓶頸的影響。我們實驗分析了128字節KV工作負載下WAL進程單實例和MemTable進程多實例的性能，如圖8所示

WAL

如圖6所示, WAL 的平均延遲降低從一個用户線程 2.1微妙到在 32 個用户線程 0.8 微妙。這是因為分組日誌策略將來自不同線程的小日誌收集到更大的IOs中，從而提高了IO效率。
為了演示批處理機制對寫性能的影響，我們在將幾個128字節的鍵值對批處理為 256 字節到 16KB 大小的WriteBatch請求時，測量了WAL的帶寬和CPU使用情況，如圖7所示。 在RocksDB的默認配置中，啟用了RocksDB的異步日誌記錄方式，以消除每次小IO後由於fsync引起的寫放大 。結果表明， 請求級批處理機制不僅可以通過IO大小提高SSD的帶寬利用率，還可以通過IO棧中軟件開銷的減少有效降低CPU負載
現象： 更大的 writebatch，更高的 I/O 帶寬利用，更高的性能，更低的 CPU 利用率

原因：因為更大的 batch，節省更多的小 I/O 造成的寫放大，因為 I/O 更大，也減小了 I/O 棧上的軟件開銷，CPU 開銷也就降低
結論：使用 Batch 機制有利於改進性能，並提升 I/O 帶寬利用，降低 CPU 開銷

圖8a顯示，使用批處理的單實例情況下，如果有32個線程，QPS提高了 2x，而多實例情況下，如果有4個線程，QPS的峯值超過 2.5x QPS。底層SSD中有限的IO並行性在很大程度上決定了多實例情況下日誌記錄線程的最佳數量

Index

不同於上面的記錄過程中，總體吞吐量MemTable索引更新過程中的尺度在單實例和多實例的情況下，如圖8 b所示
雖然更新的延遲 MemTable 增加從單個線程2.9微妙到 32 線程的 5.7 微妙。而且，多實例的情況明顯優於單實例的情況。具體來説，在圖8b中，前者在32 線程時吞吐量增益達到 10.5xQPS，而後者在 32 線程時僅提高了 3.7xQPS。這種性能差距主要源於同步開銷和後者中共享併發 skiplist 的收益遞減。這表明，儘管併發的 MemTable 允許多個線程並行地插入到 skiplist 中， 但其可伸縮性是有限的 。
綜上所述，單實例和多實例情況在使用高性能硬件部署到當前KVS架構時，都顯示出了各自在可伸縮性方面的優勢和劣勢。

對於 WAL日誌瓶頸 ，雖然單實例情況可以通過利用批處理機制而始終受益於線程伸縮，但多實例情況可以獲得更高的日誌吞吐量性能，但實例間的並行性有限。
另一方面，在多實例情況下總體索引更新性能比在單實例情況下更好，因為在前者中沒有 鎖爭用。
此外，由於WAL和MemTable位於同一個KVS寫關鍵路徑上，在進程流中，前者位於後者之前，因此總體吞吐量受到兩個進程中較慢進程的限制。這些觀察和分析表明，充分利用底層高性能硬件的KVS處理體系結構的設計應該全面考慮實例間和實例內並行性、日誌記錄和索引之間以及計算和存儲開銷之間的相互作用和權衡

現象： 單實例多線程以及啟用 batch 能夠帶來寫日誌的性能提升，但不如多實例。多實例下 WAL 性能也會受到器件本身的並行性的影響

結論：只使用 batch 的單實例多線程方案雖然能帶來 WAL 的性能提升，但不如多實例
實例內的並行性是不夠的，還需要考慮實例間的並行性。

現象： 單實例多線程以及啟用 batch 能夠帶來寫 Memtable 的性能提升，但不如多實例。多實例優勢更明顯

結論：只使用 batch 的單實例多線程方案雖然能帶來 Index 的性能提升，但不如多實例

Design and Implementation

在前幾節中，我們深入的實驗分析促使我們提出了一個可移植的二維並行KVS框架，稱為p2KVS，以有效地利用成熟的產品KVS實現(如RocksDB)和現代硬件的力量。p2KVS採用了以下三方面的設計方法。

利用實例間並行性，在多個KVS實例之間進行水平鍵空間分區。p2KVS採用多個KVS-worker線程，每個線程綁定在不同的核上。每個worker運行一個KVS實例，帶有自己獨立的WAL日誌、MemTable和LSM-tree，從而避免共享數據結構上的爭用
使用全局KV訪問層公開實例內部並行性。p2KVS設計了一個全局KV訪問層，將用户線程和kvs工作線程分開。接入層將來自應用程序的所有KV請求策略性地分配到worker隊列，在有限數量的worker之間實現負載均衡。
使用基於隊列的機會批處理來緩解日誌記錄和索引瓶頸。p2KVS在每個worker中提供了一種基於運行時隊列的機會批處理機制，以分攤kv處理和日誌記錄的開銷。

Arch

垂直維度多了一個訪問層，水平維度維護了一組工作線程，每個線程跑一個 LSM 實例，且有自己的請求隊列，綁定核心。

每個 用户線程 處理分配給自己的請求。

每個用户線程只根據分配策略將請求提交到相應 worker 的請求隊列中 (1)，
然後掛起自己而不會進一步消耗 CPU (2)

工作線程

批量處理入隊請求【1】
在對應的 KV 實例中執行【2】
請求處理結束【3】
掛起的擁有線程將被通知返回（3）

請注意，請求處理會消耗worker的CPU資源。RocksDB中的主要和次要的壓縮操作是由屬於KVS實例的後台線程執行的。這些實例內並行性優化依賴於KVS實例的實現，而p2KVS與它們完全兼容

p2kv維護一個全局標準KV接口，如PUT、GET、DELETE、SCAN等，並期望對上層應用程序完全透明。但是，它將KV請求重定向到內部分片的KVS實例，提供了實例間的並行性。請注意，雖然數據庫和應用程序通常利用用户特定的語義(例如，RocksDB[20]的列語義)來為底層的多個KVS實例分配鍵值對，但p2KVS為上層應用程序提供了標準的KV接口，而沒有額外的語義。此外,p2KVS還擴展了異步寫接口(例如, ( , , ))), 一個用户線程不會被正在處理請求阻塞。

Balanced Request Allocation

為了公平分配和調度，本文用了簡單的基於取模的哈希函數來實現，對鍵 Hash 然後取模對應的 worker 數，的到線程 ID 。worker 數的設定是根據測試的硬件的並行性來設定的，根據原文的硬件測試結果設置為了 8。基於哈希分區的優勢：負載均衡，最小的開銷，沒有讀放大（分區之間沒有鍵重疊）
增加 worker 數或者調整哈希函數可能導致重新構建 KV 實例，可以考慮採用一致性哈希。我們的實驗結果表明，即使在使用Zipfian分佈的高度傾斜的工作負載下，散列函數仍然可以使熱請求均勻地分佈在各個分區上。由於實例之間存在不平衡的可能性，例如，大多數熱請求偶爾會被散列到某個worker上，p2KVS 在單個實例下被降級為 RocksDB。此外，p2KVS 可以配置適當的分區策略，以很好地匹配工作負載的訪問模式，例如使用多個獨立的散列函數（DistCache）或動態鍵範圍（NovaLSM）
注意，這個鍵範圍分區相當於用多個互斥子鍵範圍擴展全局 lsm 樹中每一層的容量。因此，分區可以在一定程度上減少 compaction 導致的寫放大，因為多個實例增加了LSM-tree的寬度，同時降低了它的深度

Opportunistic Request Batching

如3.4節所示，對於小的寫操作，請求批處理是減少IO和CPU開銷的有效方法。此外，一些kvs(如RocksDB)對讀類型請求有很好的並行優化。這些特性有助於提高每個 worker 的整體表現。
為了提升內部並行性， 引入一個基於隊列的請求批處理調度技術，簡稱 OBM ，如下圖所示。
當工作線程處理請求時，用户線程將請求添加到請求隊列中。當worker完成一個請求的處理後，它會檢查請求隊列。 如果有兩個或更多連續的相同請求類型的傳入請求(例如，讀類型GET或寫類型PUT、UPDATE和DELETE)，它們將合併成一個批處理請求，然後作為一個整體處理 ，如算法1所示。

對於寫類型的請求，工作者將其作為WriteBatch處理。與 IO 級別的批處理(如RocksDB組日誌記錄)相比，這種請求級別的批處理更有利於減少線程同步開銷。
對於讀類型的請求，工作人員在KVS上併發查詢它們。RocksDB提供了一個multiget接口，這是一個非常優化的操作來處理內部併發的鍵搜索，我們在實現中使用這個接口來處理讀類型的批處理請求。
注意，worker 不會主動等待來捕獲傳入的請求。因此，這種批處理是機會主義的

OBM 可以通過消除同步和等待的開銷來提高高併發工作負載下的處理效率。為了防止由於非常大的批處理請求而導致的尾延遲問題，我們為每批處理的請求數設置了預定義的上限(默認為32) 。雖然 不同類型的請求也可以在一個實例中並行處理，但OBM只會連續地合併相同類型的請求，以避免在使用異步接口時由於無序讀寫請求而導致的一致性問題 。當隊列在較低的工作負載下通常為空時，該方法只是降級為KVS，而不需要批處理。
總之，p2KVS 使用 OBM 機會主義地將多個小請求聚合為一個更大的請求，這不僅減少了寫進程的軟件和日誌 IO 開銷，而且還利用了並行讀優化。與RocksDB 或其他 kvs 中的IO級批處理機制不同[SpanDB, KVell]，p2KVS避免了在底層IO層合併寫操作時引入額外的同步開銷。

Range Query

像其他使用哈希索引的 KVS 一樣，p2KVS 實現範圍查詢操作(即 range 和 SCAN )是一個挑戰，因為相鄰的鍵可能被物理分佈到不同的實例。鍵空間分區意味着一個範圍查詢必須被 fork 到對應的 worker 中，覆蓋指定的鍵範圍。幸運的是，每個分片實例使用自己的 LSM-tree 結構來保持其內部鍵的排序，有利於範圍查詢。
RANGE和SCAN之間存在語義上的差異，導致它們在p2KVS中的實現存在一些差異。RANGE 操作指定一個開始鍵和一個結束鍵，並讀出它們之間所有現有的 KV 對。不同的是，SCAN 操作指定了一個開始鍵和隨後要讀取的KV對的數量(即掃描大小)。
當底層IO帶寬足夠時，一個RANGE請求可以被分成多個子RANGE操作，由多個p2KVS實例並行執行，而無需額外的開銷。
對於SCAN操作，請求的鍵在實例中的分佈最初是未知的，因此每個KVS實例中的目標鍵的數量不是先驗確定的。

保守的方法是構造一個全局迭代器，基於每個KVS實例的迭代器，串行遍歷整個密鑰空間中的密鑰，類似RocksDB MergeIterator。
p2KVS還提供了另一種並行化方法，它首先在所有實例上使用相同的掃描大小執行SCAN操作，然後從所有返回值中過濾出請求的kv。這種方法會導致額外的讀取，可能會影響性能。
然而，實現的簡單性和易用性以及底層硬件提供的高帶寬和並行性可以合理地證明它的使用是合理的。

崩潰一致性

p2KVS 保證了與底層 KVS 實例相同級別的崩潰一致性，每個實例都可以在崩潰或失敗後通過重放自己的日誌文件來恢復。
大多數基於lsm樹的 KVS 支持基於 WriteBatch 的基本事務，其中同一個事務中的更新由一個 WriteBatch 提交。當一個包含多個實例的事務被執行時，該事務被拆分為多個並行運行在這些實例上的 writebatch，如果在崩潰前只提交了其中的一部分，就會導致一致性問題。
為了解決這個問題，p2KVS 為每個寫請求引入一個嚴格遞增的全局序列號(GSN)，以表明其唯一的全局順序。GSN 可以作為原始日誌序列號的前綴寫入KVS日誌文件。從同一個事務中分離出來的 writebatch 具有相同的 GSN 號，OBM 不會將它們與其他請求合併。
當一個實例崩潰時，p2KVS 根據崩潰實例日誌中的最大 GSN 回滾所有實例中的日誌記錄請求。為了確保系統崩潰後的恢復，當事務初始化或提交時，p2KVS 將事務的 GSN 持久化到 SSD 上，從而在崩潰後通過取消每個 KVS 實例上相應的 WriteBatch 來回滾整個事務。例如，在圖 11 中，在崩潰之前，事務A已經返回並記錄了提交，事務B已經被kvs處理但沒有提交，事務C還沒有完成。當系統恢復時，p2KVS首先刪除事務B和事務C的日誌記錄，因為事務日誌顯示最後一個提交的事務的GSN是事務A，然後對所有KVS實例執行恢復過程。我們進行了在寫數據時殺死p2KVS進程的實驗，結果表明p2KVS總是可以恢復到一致的狀態。

目前，p2KVS專注於擴展基本KVS操作的性能(例如，批寫和讀)，在不修改底層KVS代碼的情況下，確保任何單個請求在高併發下的原子性和崩潰一致性。在未來的工作中，我們將採用現有的事務優化[37,48]，並通過進一步利用KVS代碼中的功能來支持更多的事務級別。例如，p2KVS可以使用RocksDB的快照特性來實現讀提交事務隔離級別。每個worker都在WriteBatch處理之前創建一個實例的快照，其他讀請求將訪問該快照以避免髒讀。當事務提交時，快照將被刪除，事務中的更新將變得可見

Portability

p2KVS 作為一種可移植的並行化框架，可以靈活地應用於現有的 kvs。本節描述p2KVS在兩個代表性的kvs上的可移植性實現，即LevelDB(基於lsm樹)和WiredTiger(基於B+樹)。兩者都使用WAL機制和共享索引結構
因為所有kvs都有三個基本功能，即初始化、提交請求和關閉。p2KVS將自己的邏輯插入目標KVS的這三個函數中，保持相應的API和進程不變。

在初始化步驟中，p2KVS創建多個實例和目錄，在KVS的開放函數中存儲它們自己的數據。
在請求提交步驟中，用户線程調用KV請求(例如put和get)，並執行分配策略將請求插入到相應實例的隊列中。實例 worker 從請求隊列中獲取頭部請求，並調用相同的KVS API(例如put和get)來處理KV操作。如果KVS具有批處理請求的專用功能，如RocksDB的Writebatch和multiget，則可以相應地啟用OBM機制。
當p2KVS關閉時，每個worker調用KVS的close API。此外，任何worker崩潰都會導致整個系統關閉

p2KVS 的 OBM-write 功能可以在 LevelDB 上通過批寫來執行，而在 WiredTiger 上沒有批量寫。儘管LevelDB和WiredTiger沒有像multiget那樣的批讀功能，p2KVS仍然可以利用OBM併發提交多個讀請求來利用內部並行性。5.6節的實驗結果表明，p2KVS可以有效提高LevelDB的並行度，WiredTiger的讀寫速度明顯加快。

Evaluation

實驗結果具體參見原文
實驗對比了 RocksDB, KVell，以及 LevelDB。
同時也基於 WiredTiger 實現了 p2kvs，進行了對比，證明了可移植性強

Conclusion

在生產級鍵-值存儲環境中，系統管理員希望通過簡單地將慢速hdd替換為快的ssd來獲得一致的性能提升。結果往往令人失望，特別是對於普遍存在的小型KV工作負載。我們發現，在單線程和併發的寫工作負載下，KVS寫進程中的前台操作(日誌記錄和索引)可能成為嚴重的性能瓶頸。我們提出了一種並行存儲引擎 p2KVS，基於lsm樹的KVS的多個實例，以有效和高效地執行KV操作。p2KVS旨在利用這些實例之間和實例內部固有的並行性，以充分利用現代CPU、內存和存儲硬件提供的處理能力。與最先進的RocksDB相比，p2KVS的寫性能和讀性能分別提高了4.6x和5.4x

「其他文章」

EuroSys'22 p2KVS

Abstract

Introduction

動機測試

相關工作

理論分析

本文貢獻

Background

RocksDB 併發優化

Group Logging

併發 Memtable

Pipelined Write

Root Causes of Poor Scalability

處理時間

Multi-threading, a Double-edged Sword

Design and Implementation

Arch

Balanced Request Allocation

Opportunistic Request Batching

Range Query

崩潰一致性

Portability

Evaluation

Conclusion