【ATC 2018】Redesigning LSMs for NVM

2019-12-24 17:36:06

1. 背景

阅读USENIX ATC 2018 《Redesigning LSMs for Nonvolatile Memory with NoveLSM 》[1] 笔记

Non-volatile memories（NVM）特点（例如 Intel 的 3DXPoint 技术）

随机 read/write latency 很低
throughput 高（higher bandwidth）
byte-addressability，支持按字节随机访问

（near-DRAM read latency, 50x-100x faster writes, and 5x higher bandwidth compared to SSDs，几种硬件性能的如下图，不过没有包含 NVME SSD）

新的硬件，新的挑战也是新的机会，事实上现在已经有 NVM 设备可以直接插上去当内存用了，因此论文作者重新设计了 LSM-tree，被称为 NoveLSM

2. 现状

传统 LSM-tree 存在的问题

传统的 LSM-tree （例如 LevelDB，如上图），维护了多种内存和磁盘结构，内存中是 sstable，盘中是 sstable；write，将数据先写入内存，然后在批量写入盘中；read，将 sstable 读到内存中；这样存在序列化和反序列化的开销
传统的 LSM-tree 因为内存有限（而当前 NVM 的容量已经可以很大了），所以内存 memtable 会再到达一定的大小之后刷到盘中变成 sstable，后面又对 sstable 分 level，Compaction 等，造成 read/write amplification
传统的 NVM LSM 通过增加 NVM 层，如下图，会增加层数，从而增加坏情况下 read 的 latency

3. NoveLSM

3.1. 思路

思路

设计了一种具有持久性（persistent）的 nvm-based 的 memtable
这种 persistent NVM memtables 可以直接 update，自那么然能够减少序列化和反序列化，以及 Compaction 的 write amplification；除此之外，直接在 NVM memtable 中 update，避免了写 log，恢复直接恢复 NVM 中的 memtable，使得恢复的速度更快
optimistic parallel reads：设计一种优化的并发 read 来并发的访问不同 level 的数据（因为 non-volatile memories 不仅 latency 很低，而且带宽很高，所以可以支持很好的并发）

3.2. 动机

动机

当然是现在的方案直接用在 NVM 设备上性能提升并不大，没有充分发挥 NVM 的性能：

although NVM hardware provides 100x faster read and write compared to SSD, LevelDB’s sequential and random insert latency (for 5 GB/sec bandwidth) reduce by just 7x and 4x, respectively; the sequential and random read (fetch) latency reduces by less than 50%. The results show that current LSMs do not fully exploit the hardware benefits of NVM and suffer from significant software overheads. We next decipher the sources of these overheads.

论文作者还分析了 leveldb read/write 各个阶段的 latency 分布，如下图：

降低 read/write latency，提高 throughput

3.3. 实现

方案

Addressing (De)serialization Cost

如上图 (a) 就是 NoveLSM 的基本结果，既然 NVM 能具有持久性且能 byte-addressability，那么直接重新设计 memtable 的 skiplist ，我们知道通常的 skiplist 都是一些节点加上一些指针，指针都是虚拟地址，作者这里很巧妙，将 NVM 通过 map file 的形式，map 一段到 memory 中，使用 offset （相对 root node 的 offset）来代替 memory 的虚拟地址，这样来实现 NVM 设备的 skiplist，如下图：

实际上在普通的盘中也可以这么做，但是普通盘没有 byte-addressability 的能力，性能肯定会很差。

Reducing Compaction Cost

刚开始，分别创建一个 DRAM 的 memtable 和 NVM 的 memtable，这个时候，DRAM 的 memtable 是 active 的，接收写入，然后当 DRAM memtable 到达一定的大小之后，转变成 immutable memtable，后台线程负责将其刷到 sstable，然后 NVM memtable 转变为 active，新的写入直接 update NVM memtable，，当 NVM 到达一定的大小之后，也会转变成 immutable memeable，但是考虑由于 NVM 设备很大，那么 NVM memtable 也可以很大，可以有足够的时间，让 DRAM immutable 和 NVM immutable 在后端刷入 sstable。

Reducing Logging Cost （In-place commits ）

如上图，write 写 DRAM 的 memtable 的时候，需要些 log，但是直接 update NVM memtable 的时候不需要些 log，貌似 NVM 支持直接的事务 update（不知道这个性能怎么样？？？），所以可以不用写 log，可以减少回放日志的时间。Intel 有专门的 https://github.com/pmem/pmdk

Supporting Read Parallelism

就是让多个线程并发的去不同的 level 读，这里需要注意 read 的正确，需要以低 level 的数据为准。感觉用处不大，实现上，负责度和线程开销估计不小

4. 总结

其实通篇下来，大贡献就是设计了一个 *persistent NVM-base memtable，后性能好像表现并不是很好，在小写的情况，性能还不如 Rocksdb，感觉不知道是不是 NVM memtable 的 no log 事务写性能不是很好。

感觉要是我来设计，现在 NVM 设备其实已经很大，干脆全部数据放在 NVM 中，其基本结构如下：

write journal：放在 NVM 中，append 写，写 DRAM memtable 的时候需先写 log，因为即使 NVM，seq write 还是相对 random write 有优势，所以，日志和内存都保留
DRAM memtable：DRAM memtable 达到一定的大小之后，转变成 DRAM immutable，后台线程 Compaction 到 NVM memtable 中，在创建一个新 DRAM memtable 接受写入，如果后内存容量不够的情况，就会直接写入到 NVM memtable，知道内存被释放之后，再重新又回到写 DRAM memtable
NVM memtable：就一个，支持直接更新
这样反而简单，也没有 Compaction 回收数据产生 I/O 放大，差的性能就是内存用完，退化为 NVM memtable update 的性能

Notes

水平和时间有限，论文很多细节没看那么细，难免有错误和理解不到位的地方，欢迎指出和交流~