EuroSys'22 p2KVS

語言: CN / TW / HK

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工作負載下仍然存在瓶頸。

相關工作

  • 以前的研究表明潛在的瓶頸主要表現在 logging (SIGMOD’18 FASTER),索引(FloDB)以及 Compaction(SILK,LDC,WiscKey)階段。
  • 大量的現有 KVs 研究
    • 提出了新的全域性資料結構來代替 LSM(SplinterDB,SLM-DB,KVell)
    • 提出了局部優化
      • 快取:LightKV,SplitKV,NoveLSM,SCM LSM,MatrixKV
      • 日誌:FASTER,SpanDB
      • 併發索引:No Hot Spot Non-blocking Skip List,Asynchronized Concurrency,UniKV:
      • Compaction:PebblesDB,LSM-trie
    • 工業界也有利用硬體優勢來進行優化,比如批量寫入,併發跳錶,多執行緒壓縮
    • 帶有多個例項的KVS分片機制廣泛用於公共資料庫實踐,以利用例項間的並行性
      • HBase
      • The RocksDB Experience
      • Column Families of RocksDB
      • RocksDB tuning guide
      • Nova-LSM
      • DocDB
  • 現有的工作不能全面有效地解釋和解決高效能硬體的效能可擴充套件性差。

理論分析

  • 前臺任務首先寫 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