OSDI'22 ListDB

語言: CN / TW / HK

OSDI'22 ListDB: Union of Write-Ahead Logs and Persistent SkipLists for Incremental Checkpointing on Persistent Memory

太長不看

貢獻

    • 避免了 WAL 和資料雙寫的問題,類似於 TRIAD 的邏輯,資料即日誌
    • 設計了一個 NUMA 友好點的跳錶,就是儘可能現在本地 NUMA 節點上操作,最差才會訪問到跳錶的最底層,跨 NUMA
    • 拉鍊壓縮,Zipper Compaction,利用位元組定址,資料不用移動,改指標就行,本質是跳錶的合併

Abstract

  • 由於 DRAM 和非易失性主存(NVMM)之間的延遲差異以及 DRAM 的有限容量,傳入的寫操作經常在基於 LSM 樹的鍵值儲存中停頓 stal。本文提出了一種為 NVMM 進行寫優化的鍵值儲存 ListDB,以克服 DRAM 和 NVMM 寫延遲之間的差距,從而解決寫停頓問題。L
  • istDB 的貢獻包括三種新的技術:
    • (i) 位元組定址的 IndexUnified Logging,它增量地將預寫日誌轉換為 SkipList;
    • (ii) Braided SkipList,一個簡單的 NUMA-aware SkipList,它有效地減少了 NVMM 的 NUMA 影響;
    • (iii) Zipper Compaction,它不復制鍵值物件向下移動 LSM 樹 levels,但是通過就地合併 SkipList 而不阻塞併發讀取。
  • 通過使用這三種技術,ListDB 使後臺壓縮足夠快,足以解決臭名昭著的寫停頓問題,並顯示出比 PACTree 和 Intel Pmem-RocksDB 分別高 1.6 倍和 25 倍的寫吞吐量。

Introduction

  • NVM 延遲和 DRAM 相當,非易失,位元組定址,以記憶體匯流排速度來操作。
  • NVM 中大資料集的定位和檢索往往採用一個高效的持久化索引結構,並考慮 NVM 的器件特徵。
  • 針對 NVM 設計的索引結構,比如 FAST and FAIR, CCEH, PACTree,提供比基於磁碟的同類產品高數量級的效能。效能仍然低於 DRAM 索引。
    • 因為 NVM 比 DRAM 效能要差,更高的延遲,更低的頻寬,NUMA 效應更敏感,以及需要更大的資料訪問粒度(256B XPLine).
  • 混和 DRAM+NVM 索引以及鍵值儲存,目的是為了發揮 DRAM 的優勢,避免 NVM 的短板,所以把索引的複雜度給丟給了 DRAM。在這項工作中,我們質疑這種忽略位元組定址性、將整個索引儲存在 DRAM 中、僅將 NVMM 用作日誌空間的混合方法是否可取,因為它有兩個主要限制:
    • DRAM 容量比較小,如果資料集索引比較大,或者 DRAM 空間和其他程序共享,導致 DRAM 需要進行記憶體 Swapping,索引效能就會受到影響
    • 易失的 DRAM 索引需要故障恢復之後重建,恢復時間很關鍵。週期性做 checkpoint 可以節省恢復時間,但是導致更高的寫延遲,因為會阻塞併發寫入
  • 作者提出了一個非同步增量 checkpoint 機制,後臺合併小的、高效能的 DRAM 索引到一個永續性索引來加速資料恢復。ListDB 是一個寫優化的 LSM 鍵值儲存,實現了類似於 DRAM 索引的效能,並通過把 DRAM 索引刷回到 NVM 的方式來避免 DRAM 索引無限增長,同時實現了類似於 DRAM 索引的高效能。ListDB 緩衝了批量的插入到一個小的 DRAM 索引中,並執行後臺壓縮任務來增量地 Checkpointing 對於 NVMM 的緩衝寫入,而不需要進行資料拷貝。ListDB 將日誌條目重組為 SkipList,而不是將整個 volatile 索引重新整理到 NVMM。同時,這樣的 SkipLists 就地合併,減少了 NUMA 影響,而不會阻塞併發的讀查詢。
  • 三個關鍵技術:
    • 快速寫緩衝刷回:ListDB 統一了 WAL 和跳錶,使用 Index-Unified Logging (IUL),ListDB 只將每個鍵值物件作為日誌條目寫入 NVMM 一次。利用 NVMM 的位元組可定址性,IUL 以一種惰性的方式將日誌條目轉換為 SkipList 元素,這掩蓋了日誌記錄和 MemTable flush 開銷。因此,它使MemTable flush 吞吐量高於 DRAM 索引的寫吞吐量,從而解決了寫停頓問題。
    • 減小 NUMA 效應:通過使上層指標只指向同一個 NUMA 節點上的 SkipList 元素,Braided SkipList 有效地減少了遠端 NUMA 節點訪問的數量
    • 就地合併排序的快速 Compaction:Zippers Compaction 合併兩個 Skiplist,不會阻塞讀取操作。通過避免複製,Zipper Compaction 緩解了寫放大的問題,並快速有效地減少 SkipLists 的數量,以提高讀和恢復效能
  • 效能研究表明,ListDB 的寫效能優於最先進的基於 NVMM 的鍵值儲存。對於讀效能,ListDB 依賴於經典的快取技術。

Background and Motivation

Hybrid DRAM+NVMM Key-Value Store

  • 基於 NVMM 的索引常常因為需要使用 memory fence 的相關指令來保證 cacheline 持久化,引入了較大的開銷。為了避免這,NVTree 和 FPTree 在 DRAM 上儲存內部節點,在 NVM 上儲存葉子節點,內部節點在系統故障之後可以恢復出來,但是可以從持久的葉子節點中重建。基於此,對於內部節點的寫入不需要保證 failure-atomic
  • FlatStore 採用了一種相當激進的方法,即 NVMM 僅用作日誌空間,其中鍵值物件以插入順序而不是鍵順序新增,而索引駐留在 DRAM 中。因此,FlatStore 必須在系統崩潰後從持久的日誌條目重建一個不穩定的索引。為了減輕昂貴的恢復開銷,FlatStore 建議定期在 NVMM 上 checkpoint DRAM索引。然而,一個簡單的同步檢查點(如FlatStore)在阻塞寫入時獲取全域性快照,導致不可接受的高尾延遲。

LSM

  • 更好的方法是非同步增量 checkpoint,它只 checkpoints 當前檢查點和最後一個檢查點狀態之間的差異。Log Structured Merge (LSM)樹是一個經典的索引,它隨著時間的推移合併檢查點資料 [10, 17, 20, 33, 36, 48, 54].

基本操作

  • 寫過程不做介紹
  • LSM 讀比較慢,但是 LSM 比 B+tree 應用更廣泛,因為讀效能可以通過快取很有效提升

Side Effect of Write Buffer: Write Stall

  • 寫 buffer 處理寫入很快,但是在 LSM 裡有一些人工調控限制了寫 Buffer,導致很高的延遲。即 compaction 比較慢的時候會阻塞前臺的 imm 刷回。相似的,如果 SST 沒有很快被合併排序,重疊的 SST 也會增加,讀效能下降。大部分 LSM 會阻塞客戶端的寫入,直到 compaction 完成以及有空間容納新的 memtable。這就是寫停頓,如果寫停頓出現,這時候插入吞吐就受到持久儲存效能的限制,而沒法從 DRAM 中獲益

多層和雙層壓縮

  • 基於拷貝的 Compaction 允許併發的讀查詢訪問舊的 SST,同時建立新的 SSTs。但是基於拷貝的 Compaction 要求重複拷貝相同的物件到新的 SSTs。一個鍵值對被拷貝到一個新檔案的次數即為寫放大,現有研究估計可能高達 40。如果使用 leveled compaction 的話,寫放大會尤其嚴重,而且會有大量的 levels。因為 leveled compaction 限制了每層的 SSTables 數量,並且避免了單層裡的資料重疊。
  • 因為 NVM 位元組定址,因此可以考慮使用單層的持久化索引來替代多層 SSTs。SLM-DB 就使用了兩層,一層 Memtable 和一個在 NVM 上的單層的 B+tree,使用兩層設計,Memtable 緩衝了多個 KV 鍵值對然後插入到一個大的永續性索引,例如,對於多次寫操作只遍歷一次大型持久索引,並且它比單個持久索引產生更高的寫吞吐量

解耦歸併排序和 Flush

  • 雙層設計的主要問題是永續性索引的大小影響合併易失索引到永續性索引的效能,也就無法讓寫效能獨立於 NVMM 效能。因為 Memtable 不再是 flush 到底層,而是歸併排序到大的慢的永續性索引。因為 NVMM 有更高的延遲,歸併排序吞吐遠低於易失索引的插入吞吐,特別是永續性索引比較大的時候
  • 為了緩解這個問題,大多數鍵值儲存採用了一箇中間持久化 buffer level L0。即執行 flush 而不進行歸併排序,下圖展示了一個三層設計,通過分離歸併排序和 flush,Memtable 可以刷回到 NVMM 更快,flush 的吞吐也就和資料庫的大小獨立開來
  • 該設計的一個缺點就是導致了更多的重疊 SSTs,影響了查詢效能。鑑於其較差的索引效能,中間持久緩衝區級別似乎與預寫日誌沒有太大區別。另外,鍵值資料通常寫到儲存上至少兩次,一次 WAL,一次 Memtable flush
  • TRIAD, WiscKey, FlatStore 避免了重複寫入。
    • TRIAD 直接把 commit log 當作未排序的 L0 SST,為了高效檢索 L0,TRIAD 為每個 L0 SST 維護了一個小的索引。索引不儲存鍵值,只按鍵順序儲存每個物件的偏移。雖然 TRIAD 減少了 I/O,但每個 Memtable 刷回建立一個索引檔案,然後呼叫開銷較大的 fsync 來持久化。然而,考慮到 L0 SSTables 之間的高度重疊,以及 L0 SSTables 將很快合併到 L1 SSTables 的事實,是否應該以非常高的成本為每個 L0 SSTable 建立和持久化一個單獨的索引檔案是值得懷疑的

NUMA Effects

  • 相比於 DRAM,NVM 因為其更低的頻寬對 NUMA 效應更敏感。也就是因為這,CCEH, FAST and FAIR 這些索引的擴充套件性就比較一般,由於非常規的cacheline 訪問和 NUMA 效應
  • 有研究建議限制每個 Socket 的寫執行緒為 4-6 個執行緒。
    • SIGMOD’21 Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads.
  • Nap 通過在 NVMM 常駐索引上覆蓋一個 DRAM 索引來隱藏 NUMA 效果,這樣 DRAM 索引就可以吸收遠端 NUMA 節點訪問。但是,儲存在NVMM中的資料已經在記憶體地址空間中,而且 NVMM 的延遲與 DRAM 相當。因此,使用 DRAM 作為 NVMM 上的快速快取層並在 DRAM 和 NVMM 之間來回複製資料可能會造成浪費。例如,EXT4-DAX 和 NOVA 等 NVMM 檔案系統不使用頁面快取,而是直接訪問 NVMM
  • 緩解 DRAM 上的 NUMA 效應有很多種方法,包括 基於雜湊分片的 Delegation 和 Node Replication
    • Delegation:指定的 worker 執行緒分配給一個具體的鍵範圍,負責其所有操作。因此客戶端執行緒需要和 worker 執行緒通訊並使用訊息傳遞來委派操作。因為訊息傳遞的開銷,Delegation 執行的效能不是最優的,特別是對於索引操作這樣的輕量級任務
    • Node Replication:實現了一個 NUMA 感知的共享日誌,它用於對跨 NUMA 節點複製的資料結構重放相同的操作。但是,這將消耗記憶體來跨多個 NUMA 節點複製相同的資料結構。此外,由於 NUMA 節點數量增加,跨節點通訊導致效能下降。考慮到 Optane DCPMM 的頻寬遠低於DRAM,複製會加劇低頻寬問題

Design

Three-Level Architecture

  • 三層:Memable,L0,L1 Persistent Memtables (PMTables)
    • Memtable 和 PMTables 本質上是相同的跳錶,但是 PMTable 有額外的元資料,因為是從 WAL 轉換過來的
    • ListDB使用 SkipList 作為所有級別的核心資料結構,因為它支援位元組可定址的就地合併排序,並避免了寫放大問題[21,41,53]
  • ListDB 在 NVMM 中使用一箇中間持久緩衝區級別 L0 。對於 L0,MemTable 被 flush 到 NVMM 而不需要進行合併排序,這使得 flush 吞吐量與下一級持久索引大小無關。L0 積累的 MemTables (L0 PMTables)通過壓縮逐漸合併到較大的 L1 PMTable 中。為了管理多個 PMTables, ListDB使用一個名為MANIFEST的元資料物件指向每個 SkipList 的開頭。

Index-Unified Logging

  • 目標就是將 Memtable 刷回到 NVMM 不需要拷貝簡直物件

Conversion of IUL into SkipList

  • Index-Unified Logging (IUL) 通過按照跳錶元素的形式來分配和寫入日誌項,實現 WAL 和跳錶的統一。圖 4 展示了其中 Entry 的結構,同時作為日誌項和跳錶元素。當插入一個鍵值對到 Memtable,其物件和元資料(operation 以及 LSN)是已知的,對應的日誌項被寫入和持久化到 NVMM 上,對應的跳錶指標初始化為 NULL。之後,一個 Compaction 執行緒把對應的 Memtable 刷回的時候,日誌項被轉換成跳錶元素,重用日誌項中對應的鍵值
  • 但是跳錶元素需要額外的資訊,即鍵的順序資訊,該資訊以跳錶指標維護在 Memtable 中。當把日誌轉換成 PMTable 的時候,相應的 Memtable 元素的地址被簡單的轉換成 NVMM 的地址(通過偏移量轉換)。跳錶指標轉換成 NVMM 地址之後,IUL 中的項也就變成了跳錶元素
  • 最後更新 MANIFEST 來讓新的 L0 PMTable 生效,並讓 Immutable Memtable 在一個 failure-atomic 事務中失效。

MemTable Flush without clflush

  • 跳錶指標寫入到日誌項時不需要 clflush,因為本身寫入的只是順序,不是資料,順序完全可以恢復出來。
  • 不需要顯示 flush 也就是說利用 CPU 自己的快取機制來管理資料的刷回,也就實現了對於相同 XPLine 的寫入可以被緩衝,8B 小寫也就不會轉換成 256B 的 RMW,不僅延後了 RMW,也避免了後臺 Compaction 執行緒受到 RMW 帶來的延遲影響

Walk-Through Example

  • 流程如上圖 5 所示,假設插入的資料順序為 503,921,3。每個客戶端執行緒在它提交之前持久化物件、元資料和 NULL 指標到日誌。然後後臺執行緒標記 Memtable 為 immutable 並建立一個新的 Memtable。客戶端執行緒再插入了 716 和 217。
  • 後臺 Compaction 執行緒刷回 Immutable Memtable,把相應的 Memtable 元素指標轉換成 IUL 偏移量,然後替換掉對應的指標,從而成為跳錶。

Checkpointing L0 PMTable

  • 雖然日誌條目現在被轉換為 L0 PMTable 元素,但是日誌空間和 L0 PMTable 空間之間的邊界(如圖6(a)中的粗虛線所示)沒有移動,因為它不能保證新的 L0 PMTable 的指標是持久的。只有對更新的指標顯示呼叫了 clflush 指令才會移動邊界,在我們的實現中,後臺執行緒批量地持久化 L0 PMTables 的髒cachelines。此操作稱為 checkpointing。圖6(b)顯示了指標顯式持久化後的NVMM佈局。一旦PMTable被 checkpointing,就可以移動日誌空間的邊界以減少需要恢復的日誌條目的數量,如圖6(b)所示。

Lazy Group Checkpointing

  • Checkpointing 目的是為了減少恢復時間。但是 ListDB 儘可能推遲 Checkpointing,因為呼叫 clflush 開銷太大了,即便 L0 PMTables 沒有被持久化,也不會影響崩潰一致性,因為會被當作日誌來恢復。其順序也可以重建
  • 作者實現中,多個 L0 PMTables 被分組,髒的 cachelines 批量進行持久化。也就是所謂的 lazy group checkpointing。本身就是在日誌大小、恢復時間以及 flush 吞吐量方面做妥協。checkpointing 越頻繁,flush 越慢,日誌大小越小,恢復越快。
  • Zipper compaction 持久化指標很快,可以避免 L0 的表數量太多。即使 IUL 不持久化任何 L0 PMTable,當將 L0 PMTable 合併到 L1 PMTable 時,Zipper 壓縮持久化指標的速度很快,而且 IUL 的恢復時間比同步檢查點要短得多

NUMA Effects for SkipList

  • ListDB 採用了 NUMA 感知的資料結構,與委託和節點複製相比,該結構在最小化 NUMA 互連爭用方面更具可伸縮性和有效性

NUMA-aware Braided SkipList

  • 跳錶的一個特點:每一層的 list 必然是最底層 list 的有序子集。上層的指標是概率選擇出來的,不影響查詢的正確性。但是, 上層不需要是下一層的子列表,只要是底層的子列表即可 。即使搜尋沒有找到更接近上層搜尋鍵的鍵,搜尋也會回到更低的層,最終搜尋到包含所有有序鍵的底層。
  • Braided SkipList 就是利用這個特點來減小 NUMA 效應。上層指標忽略遠端 NUMA 節點中的 SkipList 元素;例如,每個元素的上層指標指向同一個NUMA 節點中具有更大鍵的元素。與 NUMA-oblivious 傳統的 SkipList 相比,Braided SkipList 把遠端記憶體訪問次數減少到 1/N,其中 N 是 NUMA 節點的數目
  • 如下例子,為了便於顯示,NUMA節點 1 中的上層顛倒了。
    • NUMA 0 上的元素 3 指向了相同 NUMA 節點的元素 7,但是沒有指向 NUMA 1 上的元素 5(原始的跳錶就會指向 5)。
    • 儘管如上維護指標,查詢還是正確的。
      • 比如在 NUMA 0 上的執行緒查詢 5。首先找到 3 和 9,因為 9 更大,向下移動找到 3 和 7,繼續下移,找到了 3 和 4。因為 5 大於 4,那麼繼續下移動,這時候檢查 4 的下一個指標。也就找到了 NUMA 1 上的 5
  • 在作者的 Braided SkipList 實現中,NUMA ID 被嵌入到 64 位虛擬地址的額外 16 位中,類似於 pointer swizzling 的操作,這樣它就可以使用 8 位元組的原子指令,而不是較重的 PMDK 事務。為了直接引用,Braided SkipList 通過 masking 額外的 16 位來恢復 SkipList 元素的虛擬記憶體地址。

Zipper Compaction

  • Zipper Compaction 通過只修改指標來歸併排序 L0 和 L1 的 PMTables,不會阻塞併發的讀。就地歸併排序避免了寫放大,提升了 Compaction 吞吐
  • 基於跳錶的特性,部分研究提出了無鎖的跳錶。基於 Java 的 ConcurrentSkipListMap 在實踐中表現良好。經典的無鎖跳錶避免對多個 Writers 加鎖。相反,ListDB 不會併發寫入。唯一的 writers 是 Compaction 執行緒,ListDB 會協調這些執行緒避免寫寫衝突。對於並行性,多個壓縮執行緒寫入不相交的分片。一個分片是 L1 PMTable 中一個高度最大的元素到下一個高度最大的元素之間的一個不相交的鍵範圍。為了將 L0 元素合併到 L1 中,壓縮執行緒必須獲得對應分片上的鎖。
  • Zipper Compaction 分為兩階段:
    • 從頭到尾的 scan
    • 從尾到頭的 merge
  • 為了保證正確的搜尋結果而不阻塞併發讀,L0 PMTable 元素由尾到頭被合併到 L1 PMTable 中,同時併發讀取操作從頭到尾遍歷它們。

Scan Phase

  • 在前向掃描階段,壓縮執行緒從頭到尾遍歷 L0 和 L1 PMTable,並確定每個 L0 PMTable 元素應該插入 L1 PMTable 中的什麼位置。但是,在這個階段,它不會對 PMTables 進行任何更改,而是將必要的指標更新推送到堆疊上。後向合併階段彈出堆疊以應用並持久化 L1 PMTable 中的更新。
  • 掃描階段沿著 L0 PMTable 的底層。對於每個 L0 元素,它會搜尋 L1 PMTable,以找到插入 L0 元素的位置。為此,它跟蹤每層中小於當前搜尋鍵 (L0元素) 的最右邊的元素,以避免重複遍歷 L1 PMTable。因為兩個 PMTable 中的鍵都是排序的,所以 L0 PMTable 中的下一個較大的鍵可以重用前面最右邊的元素,並回溯到最右邊的最頂層元素進行下一次搜尋。因此,掃描階段的複雜度為 O(n0 + logn1),其中 n0 和 n1 分別為 L0 和 L1 PMTables 的大小。
  • 對於支援 NUMA 的 Braided SkipList, Zipper 壓縮需要一個最右的二維陣列 [numa_id][layer] 來保持每一層中最右的元素數量與 Braided SkipList 的 NUMA 節點數量相同。但是,請注意,Braided SkipList 元素不需要比傳統的 SkipList 元素更多的指標,因為它在 8 位元組地址中嵌入了 NUMA 節點 ID。
  • 下圖 a 展示了一個例子:假設所有跳錶元素都在一個 NUMA 節點
    • L0 的元素 A 需要放置到 L1 的第一個位置。因此 L1 頭結點的 H0 和 H1 就是當前最右的指標,需要為 A 的合併來更新。壓棧
      • A0 和 A1 需要指向 B。但是該資訊沒有壓棧 ,因為 B 是由當前已經壓入堆疊的最右邊的元素(L1.H0, L1.H1)指向的。每個 L0 元素被插入到兩個 L1 元素之間,每層中只有前一個(即最右邊的)元素需要被推入堆疊,因為從前一個元素中可以找到下一個元素。
    • 接下來,掃描階段訪問 L0 中的第二個元素D,並搜尋L1。插入D需要更新B2、C1和C0。同樣,它們被壓入堆疊。
    • 最後,它訪問L0中的最後一個元素E,並搜尋L1。注意L1 PMTable沒有改變,當前最右邊的指標仍然是B2、C1和C0。因此,掃描階段將C1和C0推入堆疊,使它們指向E。

Merge Phase

  • 合併階段將指標更新從尾部應用到頭部。當壓縮執行緒從棧中彈出一個更新 $X_N$ → $Y$ 的指標時,將 Y 元素中的第 N 層指標更新為 $X_N$ 的當前值,然後將$X_N$ 設定為 Y 的地址。
  • 如上圖所示:
    • Compaction 執行緒出棧 C0→E
      • 圖8b,因為 C0 當前指向了 F0,所以合併的時候就需要把 E0 指向 F0。但是 E1 這時候沒有指向,但無傷大雅,不影響查詢的正確性。
      • 圖8c,把 C0 指向 E0,好結束
    • 出棧 C1→E
      • 圖 8d,設定 E1 指向原來 C1 指向的位置 F1,然後讓 C1 指向 E1
    • 後續操作同理
  • Zipper 壓縮假定 8 位元組指標更新是原子的。為了保證指標更新 failure-atomic,它使用記憶體 fence 和 cacheline 重新整理指令立即持久化每個底層更新。在最後一步中,壓縮執行緒從 MANIFEST 物件中刪除 L0 PMTable 的頭元素,從而完成壓縮。

Lock-Free Search

  • Zipper 壓縮不會違反併發搜尋的正確性,也就是說,一個讀執行緒不會在不獲取鎖的情況下錯過它的目標 SkipList 元素。這是因為讀執行緒從頭到尾、從L0到L1訪問PMTables,而壓縮執行緒則從尾到頭合併它們。在 Zipper 壓縮期間,每個元素都保證是指向至少一個 head( 即肯定是能追溯到的 )。考慮圖 8 所示的示例,它顯示了一個原子儲存指令序列如何合併兩個示例 skiplist。即使併發讀執行緒以圖 8 所示的任何狀態訪問 PMTables,它也會返回正確的結果。
  • 即使在壓縮執行緒修改 SkipLists 的過程中讀取執行緒掛起,該演算法仍然是正確的。例如,假設讀取在訪問 L0 元素時掛起。當它恢復時,元素可能已經合併到 L1 中。當讀執行緒醒來時,如果沒有找到搜尋鍵,它將繼續遍歷到尾部。一旦到達尾部,它就結束了 L0,並開始搜尋 L1,L0 的元素已經合併到 L1 中。因此,讀執行緒可能會多次訪問相同的元素,但它永遠不會錯過它正在搜尋的元素。多次訪問可能會影響搜尋效能。為了避免這種情況,如果讀操作檢測到當前元素的級別是 L1,它將停止搜尋 L0。

Updates and Deletes

  • LSM 樹中的更新會重複相同的鍵,因為寫操作會緩衝到 MemTables 中,並逐漸重新整理到最後一層。 ListDB 不會主動刪除 L1 中的舊版本 。相反,當壓縮執行緒掃描 L0 和 L1 級別以進行 Zipper 壓縮時,它將標記 L1 中的舊版本過時。類似地,ListDB 中的刪除並不會物理地刪除物件,而是將一個 key-delete 物件插入到 MemTable 中。如果 LSM 樹從 MemTables 或 L0 PMTables 中物理刪除金鑰的最新版本,則舊版本的金鑰將恢復使用。Zipper 壓縮將較新的鍵值或鍵刪除物件放在其對應的舊物件之前。因此,讀查詢總是在舊物件之前訪問最近的物件,從而返回正確的搜尋結果。

Fragmentation and Garbage Collection

  • 通過使用 libpmemobj庫,ListDB為PMDK的故障原子事務中的多個 IUL 條目分配和釋放一個記憶體塊(例如,8 MB),從而可以減少對昂貴的PMDK事務的呼叫數量。如果一個記憶體塊中的所有元素都被標記為過時或刪除,則 ListDB 將釋放該記憶體塊。注意,ListDB 不會重新定位 SkipList 元素以進行垃圾收集。為了解決持久的碎片問題,壓縮執行緒可以執行基於 CoW 的垃圾收集。作者把這個優化留給以後的工作。
  • 無鎖資料結構的記憶體管理是一個困難的問題,因為沒有簡單的方法來檢測被釋放的記憶體空間是否仍然被併發讀取訪問。ListDB 使用簡單的基於 epoch 的回收;ListDB 不會立即釋放記憶體塊,但會等待足夠長的時間,讓短期的讀查詢完成對釋放記憶體塊的訪問。如果記憶體塊中的所有物件都被廢棄或刪除,後臺垃圾收集執行緒會定期檢查並回收記憶體塊。對於過時的物件,垃圾收集執行緒檢查其新版本的 LSN。如果它也足夠老,它認為過時的物件沒有被任何讀取訪問,從 L1 PMTable 中刪除它們,並物理地釋放記憶體塊。

Look-up Cache

  • ListDB 要求讀查詢至少訪問兩個索引,即一個可變的 MemTable 和 L1 PMTable。因此,ListDB 的讀吞吐量明顯低於高度優化的持久 B+ 樹。
  • ListDB 引入了查詢快取,Flush MemTable 將每個元素雜湊到一個固定大小的靜態雜湊表中。查詢快取不會複製其中的元素,只儲存它的 NVMM 地址,因為 NVMM 中的元素已經在記憶體地址空間中,而且它的地址永遠不會改變。因此,無論 PMTable 元素出現在哪個級別,查詢快取都可以定位到 PMTable 元素。雖然 ListDB 中的壓縮執行緒經常更新 SkipList 指標,但是通過快取不可變的地址,而不是可變的內容,查詢快取可以避免頻繁的快取失效。如果一個桶發生雜湊衝突,舊的地址將被覆蓋(即FIFO替換策略)。
  • ListDB 在 DRAM 中構造一個SkipList,作為從雜湊表中移除的高元素的二級查詢快取。第二級查詢快取的目的是加速 PMTable 搜尋。即使在第二級查詢快取中沒有找到一個鍵,查詢也可以從快取中找到的最近的 PMTable 元素開始搜尋。假設讀操作查詢鍵 100,但是發現元素 85 是 L1 中最近的更小的元素。然後,從 L1 PMTable 中的 85 號元素繼續搜尋,而不是 L1 的開頭。ListDB 不使用第二級查詢快取進行 L0 搜尋,因為小的 L0 PMTables 很快被合併到 L1 中,L0元素大部分快取在查詢雜湊表中,第二級查詢快取使用 SIZE 替換策略[58],即比較高度並剔除高度較短的元素。

Recovery

  • 當 L0 和 L1 PMTables 被 Zipper 壓縮合並時,系統可能會崩潰。為了從這樣的故障中恢復,壓縮執行緒執行微日誌記錄來跟蹤哪個 L0 PMTable 被合併到L1 PMTable中。當系統重新啟動時,ListDB 檢查壓縮日誌以重做未完成的壓縮。對於重做操作,由於 L0 PMTable 尾部的許多條目可以與 L1 PMTable 共享,因此 Zipper compaction 需要檢查重複的條目。
  • ListDB的恢復演算法,與傳統LSM樹的恢復演算法類似。首先,恢復程序定位WAL的邊界,該邊界由壓縮執行緒記錄在壓縮日誌中。然後,它對日誌條目進行排序並恢復L0 PMTables。此時,系統返回到正常執行模式並開始處理客戶端查詢。L0和L1之間的壓縮將在後臺正常進行。
  • 對於查詢快取,ListDB 可以在不恢復快取的情況下處理客戶端查詢,儘管在填充快取之前搜尋效能會很差。通過避免 DRAM 快取和索引的重構,ListDB的恢復效能優於同步檢查點

Evaluation

  • 對比兩種日誌機制
  • 不同的 NUMA 效應緩解方案對比
  • 各個技術點各自的收益
  • 對比其他索引和儲存

Conclusion

  • ListDB,一個利用位元組定址的鍵值儲存,通過就地重構資料來避免資料複製,以及NVMM的高效能來減少寫放大和避免寫停滯。展示了ListDB通過非同步增量 checkpointing 和就地壓縮顯著提高了寫效能。通過它的三層結構,ListDB 在寫吞吐量方面優於最先進的持久索引和基於 NVMM 的鍵值儲存。標準的查詢快取可以幫助緩解具有多個層級的問題。在未來的工作中,作者正在探索通過引入另一個層級(即 L2 PMTable )來提高搜尋效能的可能性,重新排列 L1 PMTable 元素,利用空間區域性性和並進行垃圾收集