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 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

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

参考文献

[1]. Redesigning LSMs for Nonvolatile Memory with NoveLSM. https://www.usenix.org/conference/a