【ATC 2018】Closing Performance Gap BetweenDRAM&NVM

來自專欄分散式，存儲筆記5 人贊了文章

原題目：Closing the Performance Gap Between Volatile and Persistent Key-Value Stores Using Cross Referencing Logs

文章概況：

這篇文章主要研究基於 Persistent Memory（PM，持久內存）的高性能 key-value 存儲。

1. Motivation

傳統的 key-value 存儲方案主要分為兩種，（1）用作 cache，存放在 DRAM（內存） 中，以 memcached 和 redis 為代表；（2）用作持久化存儲，以 LSM-tree 方案為代表，大家所熟知的有 Leveldb 和 Rocksdb 。隨著當前 Persistent Memory (PM) （其實也就是 NVM 設備，例如 Intel/Micron』s 3D XPoint）技術的發展，PM 設備已經擁有僅次於 DRAM 的 latency 和吞吐，且具有持久化存儲和 byteaddressable 的能力。而傳統 key-value 存儲方案並不完全適用於 PM 設備：傳統方案（1）並不能直接遷移到 PM 設備上；方案（2）由於讀寫放大的因素，其實不能充分的發揮 PM 設備的性能，因為 PM 設備的順序讀寫和隨機讀寫性能相差並不大。

這篇論文的作者主要動機就是設計基於 PM 設備的高性能 key-value 存儲，使其儘可能的接近 DRAM 的性能，也就是 closing the gap between DRAM with PM for key-value store。因為相比 DRAM，PM 設備具有持久化的能力，而且 latency 和 throughput 和 DRAM 非常接近， 如果能夠將 PM 設備上的 key-value 存儲優化到 latency 和 throughput 足夠接近 DRAM，那將是一件很美妙的事情。

但是 DRAM 和 PM 之間存在一定的 gap， 如下圖，給出了幾組 key-value 存儲在DRAM 和 PM 設備的表現：

從上圖我們不難發現：

  1. 隨著 write 的比例增多，DRAM 和 PM 的 latency 差距越來越大，從 write 比例 0% 到15%，latency 的 gap 也從 2X 增加到了 4X;
  2. DRAM 在多線程的情況 latency 表現平穩，而 PM 設備隨著線程的增加 latency 顯著上升;

由上圖的分析不難得知，key-vale 存儲在 DRAM 和 PM 上的 gap 就是 write 性能較差，而且擴展性不好，也就是在多線程的表現下，性能下降很快，不能充分利用現在多核 CPU 的優勢。

2. Innovation

作者給出了一個名為 Bullet 的 key-value 方案，使用 DRAM 作為 Cache，PM 負責持久化 key-value 和 log 數據，其核心的貢獻在於使用多個 log 來銜接 DRAM 和 PM，從而實現了 PM 上的 key-value store 在多線程環境下具有良好的 Scalability，而且為了解決多 log 的 Consistency Apply 的問題（就是 log apply 到 PM 上的 key-value 數據中），創新的使用了一種 cross-referencing logs (CRLs) 技術。

3. Implementation

3.1. Bullet architecture

首先看看 Bullet 的架構，如上圖，Bullet 分為 front-end 和 back-end:

  • front-end 將 kv 寫入 DRAM hash table 中，為了保證數據落盤，還要寫 log，log 是在 PM 設備上，front-end 有多個 log writers 線程（DRAM 中的 hash table 相當於就是一個 read/write Cache，因為畢竟 DRAM 相比於 PM 還是在性能上有優勢的）
  • back-end 在 PM 上：有一個 hash table 負責持久化 key-value 數據；多個 log 文件。後端也會有多個 log gleaners 線程，負責將 Op log entry applied 到 PM 上的 hash table 中

3.2. CRLs

相比傳統是只有一個 log，多個 log 會減少競爭，但同時也會帶來一致性問題，因為需要將多個 log 按順序 applied 到 back-end 的 hash-table 中才行，論文給出了一個巧妙的解決方案，它就是 cross-referencing logs (CRLs) ，其大致的思路就是在每個 Op log entry 中會記錄其前一個有依賴關係的 log entry 的指針，所謂的有依賴關係，就是操作同一個 key 的 Op log entry 就是有依賴關係，它們 apply 的時候必須按照嚴格的寫入順序 apply。

下面來詳細的分析 CRLs 核心結構：

  • Op log entry ：主要關心幾個欄位就可以了

  • op code ： 什麼 op 類型，update/delete
  • applied ： 是否被 applied，也就是是否已經後拷貝到 back-end PM 上的 hash table 中了
  • pre ： 前一個依賴 op log entry 的指針（如果是第一個 update/delete，那麼其 pre 為 NULL）
  • lentry :

就是 Figure 3: 的下面部分，它是一個持久化的 K-V Pairs，每個 key-value 數據還會有一個 lentry Pair 對應，其記錄了這個 key-value pair 最新的 Op log entry 的位置，這樣一個新來的 Op log entry，無論是 append 到哪個 log 上，只需要讀取這個 lentry，然後存放在自己的 pre 欄位中，然後更新自己的位置為 lentry 即可。

3.3. Appending op log entry

下面來看看，CRLs 是如何 Write Op log entry 到 log 文件中的，下面給出 append 一個 Op log entry 的步驟：

  1. 根據 key-value pair 加鎖
  2. 讀取這個 key-value pair 的 lentry，並放在當前 Op log entry 的 pre 欄位中
  3. 持久化這個 Op log entry
  4. 更新當前 Op log entry 的位置到 lentry 中（注意這步是 cas 操作）
  5. unlock

從上面的步驟可以看出，相比單個 log 文件，多個 log 文件並發性將會極大提升。下面給一個圖例（三個 log 文件，front-end 的 log writer append Op log entry 到 log 文件中，back-end 的 log gleaners 將 Op log entry applied 到 back-end 的 hash table 中）：

3.4. Applying Log Records

接著來看，如何 applied 一條 Op log entry 到 PM 的 key-value （hash table）數據中

  1. 從 log 的 head 取一條 Op log entry （tail 用於 append）
  2. 然後在 lentry 中取出整個具有依賴關係的 Op log entry list
  3. 按照相反的順序 applied，並跟新 Op log entry 的 applied 欄位（因為是 pre 指向的更早的 Op log entry，applied 的時候必須按照 Op 的順序）
  4. 更新此 key-value pair 的 lentry

3.5. Optimization

3.5.1. Dynamic Worker Threads

可以根據 read/write 的比例，動態的調整 front-end log writers 線程 和 log gleaners 線程的數量，如下圖是 write-heavy workload 場景，因為在 write heavy 的場景下，由於 log 空間有限，需要多一些的 gleaner 線程儘快將 log 中的 Op log entry apply 到 PM 中 key-value hash table 中，避免阻塞 write。

3.5.2. Overwriting

在 apply Op log entry 的時候，因為是將整個有 key-value pair 的 op log entry list 都拉出來了，實際上只有最後一條被 applied 就可以了，前面的都可以直接忽略，如下圖，key 2 的前面兩個 Op log entry 就被忽略了。

不過這裡有個順序需要注意一下，保證即使出現故障也能夠一致：

  1. applied key 2 的最後一條 Op log entry
  2. 然後再按照 lentry list 的相反順序修改 Op log entry 的 applied 欄位

4. Summary

CRTLs 思路比較有意思，有些亂序 applied 的意思，感覺和 PolarFS [2] ParallelRaft 中亂序提交和亂序 apply 有著異曲同工之妙。

Notes

水平和時間有限，論文很多細節沒看那麼細，難免有錯誤和理解不到位的地方，歡迎指出和交流~

參考文獻

[1]. Closing the Performance Gap Between Volatile and Persistent Key-Value Stores Using Cross-Referencing Logs. usenix.org/conference/a

[2]. PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database. vldb.org/pvldb/vol11/p1


推薦閱讀：
查看原文 >>
相关文章