OSDI 22 - ListDB 阅读笔记

[kyle-ip]

本文是 ListDB: Union of Write-Ahead Logs and Persistent SkipLists for Incremental Checkpointing on Persistent Memory 的阅读笔记。笔者过往没有多少论文阅读与分享的经验，限于个人能力本文也没有多少新鲜的观点输出，主要是学习笔记与核心内容的翻译，权当抛砖引玉。
论文附带实现代码见 DICL/listdb，后续会整理出一些相关的背景资料，提供给大家做参考。

TL; DR

论文发布于 2022 USENIX OSDI，其介绍了一种为 NVMM 实现写优化的 K-V 存储系统。

首先在摘要部分交代了技术背景：

DRAM 和 NVMM 之间存在延迟，DRAM 容量也有限。基于 LSM-tree 的 K-V 存储系统写操作普遍会存在停顿。

为此 ListDB 贡献了三项技术来解决这个问题：

• 可字节寻址的索引统一日志（Index-Unified Logging）：将 WAL 增量转换为 SkipList。
• 编织跳表（Braided SkipList）：一种 NUMA-aware 的跳表，可有效减少 NUMA 效应。
• 拉链压缩（Zipper Compaction）：其在下移 LSM-tree 时不会复制 K-V 对象（字节寻址），而本地合并 SkipList，不阻塞并发读。

最终达到的效果是写吞吐量比 PACTree 高 1.6 倍，比 RocksDB（Intel Pmem based）高 25 倍。

这篇论文需要对 LSM-tree、SkipList、WAL、计算机存储架构要有一定了解。

在本文中有简单介绍，另外也可以参考文末提供的资料。

介绍

一些 K-V 存储系统在定位检索大数据集时结合 NVMM 特征的采用高效的持久化索引结构。

比如混合 DRAM + NVMM：由 DRAM 负责检索可发挥其性能优势、避免 NVMM 短板。

但作者质疑这种方案提高性能的可行性：

• DRAM 容量小，当数据集索引较大或 DRAM 被其它进程共享，需要进行大量内存交换（Swapping），降低索引性能。
• DRAM 索引在崩溃后需要重建，周期性的 Checkpoint 可减少恢复时间，但又会由于阻塞并发写而导致更高的写延迟。

如果单独使用 NVMM，虽然性能比基于磁盘的 K-V 竞品要高，但比 DRAM 索引低。

这是因为 NVMM 性能比 DRAM 差（更高的延迟、更低的带宽，以及 NUMA 效应和更大的数据访问粒度，256-byte XPLine）。

ListDB 是一种写优化的 LSM-tree 存储，其实现：

• 快速刷写缓冲：统一 WAL 和 SkipList（IUL，即 Index-Unified Logging），将 K-V 对象作为日志条目写入 NVMM。利用 NVMM 可字节寻址的特性，将日志惰性转换为 SkipList，减少日志和 MemTable 刷写开销。使 MemTable 刷写吞吐量高于 DRAM 索引的写吞吐量，避免写停顿。
• 降低 NUMA 效应：在 Braided SkipList 中，上层指针只会指向同一个 NUMA 节点上的跳表节点，可通过有效减少访问远程 NUMA 节点的次数而降低开销。
• 结合本地归并排序的快速压缩：压缩时把两个跳表本地归并排序，不阻塞读操作。通过避免数据复制缓解写放大问题，且减少了跳表数量，可更快速有效地提高读操作与恢复性能。

研究表明 ListDB 写性能比最新的、基于 NVMM 的 K-V 存储性能更高；读性能则依赖于传统缓存技术。

在这里 NVMM 发挥的是 PM（Persistent Memory）的作用，同时具备字节寻址与持久化能力（不同的工作模式），在存储架构中位于 DRAM 与 SSD 之间。

笔者认为本文 Introduction 部分比较重要，因此做了较为详尽的翻译。

而在后续章节关于背景与设计动机、设计思路、方案对比的内容将会精简描述。

背景与设计动机

混合 DRAM + NVMM K-V 存储

基于 NVMM 的索引在持久化时会使用 内存屏障 指令避免缓存污染、确保失败时的原子性和一致性，因此性能受损较大。

内存屏障：即 memory fence，用于确保访存指令间的相对顺序（可见性），在 Go、Java 等高级语言的内存模型中很常见。

过往的解决思路：

• NVTree、FPTree（B+tree 变种）在 DRAM 存储内部节点，在 NVMM 存储叶子节点。崩溃时内部节点通过叶子节点重建。
• FlatStore：NVMM 仅用作 K-V 对象顺序插入的日志空间，而索引存储在 DRAM。崩溃时从日志重建索引。定期在 NVMM 创建 Checkpoint 减小恢复开销。

但是生成 Checkpoint 相当于产生快照，会阻塞写入，有较大的高尾延迟。

LSM-tree

生成 Checkpoint 更好的方法是 异步、增量 地生成，即只处理当前 Checkpoint 与上一个 Checkpoint 之间的差异。

LSM-tree（Log-Structured Merge Tree）是一种经典的索引实现，随着时间推移不断整合 Checkpoint 数据。

介绍一下 LSM-tree，这是一种以顺序追加写提高吞吐量、基于合并和压缩排序文件的存储结构。

• 写操作：将数据写入 DRAM 的 MemTable（key 有序，可使用跳表、平衡树实现），大于某阈值则写入文件的 SSTable，此时原 MemTable 改为 Immutable，创建新 MemTable 处理写操作。
• 崩溃恢复：程序崩溃时 DRAM 中未持久化数据会丢失，因此在写入 MemTable 前写入预写日志（WAL），每次写入时追加到该日志，用于崩溃后恢复（数据 flush 到磁盘后日志即可丢弃）。
• 读操作：查找顺序是 MemTable -> 最新的 SSTable 段 -> 次新的 SSTable 段 ... 以此类推遍历重叠的 SSTable。
• 合并压缩：随着 MemTable 和 SSTable 重叠的部分越来越多，后台线程会周期性执行归并排序，并丢弃已被覆盖或删除的，形成一个大的有序数组。

在传统 LSM-tree 实现中压缩操作是会阻塞写操作的，客户端写入需要等待压缩完成以及有新的空间容纳 MemTable，即发生写停顿，是论文中强调解决的问题。

多层压缩与两层压缩

传统压缩是基于数据复制的，这允许并发读取 SSTable、同时写入新的 SSTable。由于需要复制相同的对象到新 SSTable，存在较大的 写放大（研究表明可高达 40，即一个 K-V 对象被复制 40 次）。

如果使用分层压缩，当层次数量很大则会加剧写放大（level 限制了每层 SSTable 数量，且避免单层数据重叠）。

NVMM 支持字节寻址，可使用单层持久化索引代替多层：比如 SLM-DB 是一层 MemTable、一层 B+ tree，缓冲了多个 K-V 对象后插入一个更大的持久性索引。多次写操作只需遍历一次大索引，而写吞吐量更高。

这种设计的主要问题是 MemTable 归并排序并写入一个很大的持久性索引，由于 NVMM 延迟较高，数据量会影响易失性索引合并到持久化索引的性能。

从 Flush 中解耦归并排序

为了缓解上面的问题，LevelDB 和 RocksDB 引入一个中间 buffer。

利用这个 L0 buffer 可以把 flush 与归并排序分离开，MemTable 可以更快地 flush 到 NVMM，其中 flush 操作的吞吐量可与数据库大小分离。

但这种设计也存在问题：导致了更多重叠的 SSTable，降低了写性能。

K-V 对象写入存储共发生两次：WAL + MemTable 的 flush。

解决方法：

• TRIAD：把 commit log 当作未排序的 L0 SSTable，为每个 L0 SSTable 维护一个保存 K-V 对象 offset 的索引，从而减少了 I/O。
• 每个 MemTable flush 时创建索引，然后 fsync 持久化（开销较大）。

由于 L0 SSTable 之间高度重叠、且很快就合并到 L1 SSTables，似乎没有必要为每个 L0 SSTable 单独维护一个索引文件。

这里参考《DDIA》，总结一下 LSM-tree 的特点（补充与 B-tree 的对比）：

	LSM-tree	B-tree
写吞吐量	写放大较小，MemTable 随机写（DRAM）、 SSTable 顺序写。	写入时需要写 WAL 和树的页（可能分裂）。即使该页中只有数字节更改，也要写整个页。 一些存储引擎甚至覆盖相同的页两次，以避免在崩溃时出现部分更新的页。
读取效率	较慢，在不同的压缩阶段检查多个数据结构。 当段数量过多（来不及归并排序压缩），读时扫描量大，效率会降低。	快
压缩支持	顺序写入且定期重写 SSTable 消除碎片，更好地支持压缩，文件比 B-tree 小。	面向页存储，页被分裂出现碎片会导致某些空间无法使用。
响应延迟	压缩有时会干扰读写。增量压缩不影响并发访问，但磁盘并发资源有限，压缩操作容易导致读写等待、提高响应时间。	更具确定性
磁盘带宽	带宽被写入线程和压缩线程共享。数据量越大、被挤占的磁盘带宽越多。 压缩需要根据写入吞吐量配置。如果压缩无法匹配写入速率，未合并段不断增加、直到磁盘空间不足（同时影响读）。 如写入效率不受限制，需要额外的监控处理这种情况。
副本数量	可能在不同的段中具有相同键的多个副本。	每个键都唯一对应于索引中的某个位置
事务隔离	不支持	通过键范围上的锁支持
范围查询	效率较低 （因此区别于传统以平衡树实现，论文中使用的是跳表，表现更好）	支持

NUMA 效应

相比起 DRAM，NVMM 带宽更低、对 NUMA 效应更敏感。

由于不规则的缓存访问机制和 NUMA 效应影响下，FAST and FAIR B+ tree、CCEH 这些持久化索引的 多线程扩展性 不太好。

笔者的理解是缓存在多线程访问时频繁失效、以及跨 NUMA 节点的内存访问效率低，因此通过更多线程来扩展访问性能效果不理想。

缓解 NUMA 效应的方法：

• 基于哈希分片的委派（Delegation with hash-based sharding）：给指定 worker 线程分配某个范围的 key，客户端线程和 worker 线程通信使用消息传递来委派操作（消息传递存在开销，因此委派性能不是最优的）。
• 节点副本（Node Replication）：实现 NUMA 感知的共享日志，用于对跨 NUMA 节点复制的数据结构重放相同的操作，即消耗内存来跨 NUMA 节点复制相同的数据，跨节点通信性能会随 NUMA 节点数量增加而下降。

简单解释一下 NUMA：这是一种内存架构，多处理器被划分到不同 Node 上，Node 拥有自己的本地内存空间。同一个 Node 内部的内存空间可进一步分为不同的内存域（Zone）：直接内存访问区（DMA）、普通内存区（NORMAL）、伪内存区（MOVABLE）等。

每个处理器访问自己的内存空间的效率会比访问其他处理器的内存空间、共享的内存空间更高。

       Node Memory                Node Memory
    +---------------+          +---------------+ 
    | ZONE_DMA      |          | ZONE_DMA      | 
    +---------------+          +---------------+
    | ZONE_DMA32    |          | ZONE_DMA32    |   
    +---------------+          +---------------+
    | ZONE_NORMAL   |          | ZONE_NORMAL   |   
    +---------------+          +---------------+
    | ZONE_MOVABLE  |          | ZONE_MOVABLE  |     
 +--+---------------+--+    +--+---------------+--+
 |  | ZONE_DEVICE   |  |    |  | ZONE_DEVICE   |  |
 |  +---------------+  |    |  +---------------+  |
 | +---+---+           |    | +---+---+           |
 | | 0 | 1 |   Node 0  |    | | 0 | 1 |   Node 1  |
 | +---+---+           |    | +---+---+           |
 | | 2 | 3 |           |    | | 2 | 3 |           |
 | +---+---+           |    | +---+---+           |
 +---------------------+    +---------------------+

ListDB 设计

三层架构

即 Volatile MemTables、L0 Persistent MemTables、L1 Persistent MemTables（PMTable）。

• 都是相同的 SkipList（其中 PMTable 从 WAL 转换而成，拥有额外的结构），支持字节寻址的本地归并排序，可避免写放大问题。
• MemTable 被 flush 到 NVMM L0 缓冲而不进行归并排序，使 flush 吞吐量与下一级索引解耦。
• MemTables 在 L0 PMTable 中累积，通过压缩合并到较大的 L1 PMTable 中。
• 使用 MANIFEST 元数据对象管理多个 PMTable（指向每个跳表头部）。

索引统一日志（Index-Unified Logging）

笔者认为这是最重要的设计，因此以较长的篇幅、尝试把这个过程描述清楚。

索引统一日志（Index-Unified Logging, IUL）指的是以 跳表 分配和写入日志（WAL 的结构也统一为跳表）。

使用 IUL，MemTable 刷写到 NVMM 时，MemTable 中的 K-V 对象已保存在 NVMM 中的 commit log 中，无需复制 K-V 对象。

图中的 Entry 既是 WAL 日志项也是（L0 PMTable）跳表元素，IUL Entry 的结构：

• 头部（8 bytes）
  • op code（操作类型，比如创建或删除一条记录）
  • LSN（log sequence number）
  • 高度（跳表的概念）
• 变量长度 key，即 key 及其长度
• 对齐填充
• 跳表指针

统一为以上的结构后，K-V 对象实际写入 NVMM 只发生一次。

复用日志和跳表元素

• 写 MemTable 和日志：在 MemTable 插入 K-V 对象时，对象与元数据（operation code、log sequence number 等）对应的日志项被写入并持久化到 NVMM，跳表指针初始化为 NULL。
• 压缩：压缩线程刷写 MemTable 时（DRAM -> NVMM），日志项转换为跳表元素，日志项的 K-V 对象即被重用。
• MemTable -> PMTable：跳表元素所需的 key 顺序信息（日志项中没有）以指针形式维护在 MemTable 中。在日志项转化为 L0 PMTable 时，MemTable 元素地址通过 offset 转换成 NVMM 地址，IUL 日志项直接转换为跳表元素。
• 更新 MANIFEST：使新的 L0 PMTable 生效，同时让 Immutable MemTable 失效。

这里简单讲解一下上图发生的事：

1. 客户端线程按顺序往 MemTable 写入 key 为 503、912、3 的三条记录，每个客户端线程在提交前会将对象及其元数据、NULL 指针写入日志中持久化。
2. 后台线程把 MemTable 标记为 Immutable，并创建一个新的 Mutable MemTable。
3. 一个客户端线程再插入 key 为 716、217 的两条记录。
4. 后台线程刷写 Immutable MemTable（包含 3、512、912 三个 key），此时日志项会转换为一个跳表，把：
   1. 每个 MemTable 元素的指针简单转换为日志项的 IUL offset。
   2. 日志项中的 NULL 指针替换为 IUL offset。
5. 和前面的描述一样，从 L0 PMTable 到 L1 PMTable 需要进行归并排序。

顺便给出文中的伪代码描述：

// 1. (PUT) insert K-V object into MemTable:
// the object and its metadata are persisted as log entry and NVMM.
// and the SkipList pointers initialized to NULL.
mutex.lock();
iul_entry <- iul_tail;
iul_entry.LSN <- GetNextLSN();                   // log sequence number 
iul_entry.height <- RandomHeight();              // 跳表元素的 height 
iul_tail <- iul_tail + sizeof(kvObject) + height * 8 + 8;
mutex.unlock();
iul_entry.op_code <- OP_INSERT;                 // 操作类型 (insert, delete) 
iul_entry.kvObject <- kvObject;
iul_entry.next[0..height] <- NULL;              // 初始化指针为 NULL 
pmem_persist(iul_entry, sizeof(iul_entry));     // 调用 clwb（即 cacheline write back，写回缓存行）
memTable.Insert((SkipListElement)iul_entry);    // 插入跳表


// 2. (Flush Immutable MemTable) convert WAL to L0 PMTable: 
// the addresses of MemTable elements are simply translated into NVMM addresses
element <- memTable.head[0].next[0];            // MemTable 最小的元素
while element != NULL do
    L0_element <- element.iul_address; 
    lookup_cache.Insert(L0_element);
    for layer <- 0; layer < element.height; layer++ do
        L0_element.next[layer] <- element.next[layer].iul_address;
        /* no need to persist */
    end for 
end while
new_L0.iul_address <- memTable.head[0].next[0].iul_address; 
new_L0.next <- MANIFEST.L0List().GetFront(); 
MANIFEST.L0List().PushFront(new_L0);            // CAS 
freeMemTable(memTable);

由于 K-V 对象已经被持久化到日志中，把跳表指针写入日志项时无需（执行 clflush 指令来完成）持久化，可利用 CPU 缓存替换机制实现数据的批量刷写：不仅推迟了 read-modify-write 的问题，还避免了后台压缩线程受到 read-modify-write 问题以及 NVMM 高延迟写的影响。

Checkpointing

当日志项被转换为 L0 PMTable 元素，此时还不能保证 L0 PMTable 已完成持久化。

因为在新 L0 PMTable 中，更新的指针可能还保留在 CPU 缓存中，如果此时系统崩溃可能会丢失，但指针对于保证数据的一致性不是必需的。

只有当更新指针显式调用 clflush 指令时，WAL 日志空间和 PMTable 之间的边界才会移动。

在作者的实现中，Checkpoint 即通过后台线程为 L0 PMTable 批量地保存缓存块。

当 PMTable 被设置 Checkpoint，就能通过移动日志空间边界来减少崩溃时要恢复的日志项数量。

虽然 Checkpoint 可以缩短崩溃恢复的时间，由于调用 clflush 开销太大，ListDB 会尽量推迟 Checkpoint。

Clflush 指令即串行地将指定的缓存块写回 PMTable，并淘汰缓存。

不过即使 L0 PMTable 没有被持久化也不会影响崩溃时的一致性，因为可当作日志来恢复，顺序也可以重建。

所谓「惰性」、「分组」的操作（Lazy Group Checkpointing），就是对多个 L0 PMTable 分组处理，批量地把缓存持久化；并通过降低 Checkpoint 频率来缩短刷写时间。但随着日志变大，恢复速度也会变慢，因此这也是在 写吞吐量（压缩时间）与恢复时间之间权衡。

下文中提到基于 Zipper Compaction 来持久化指针的速度非常快，以至于可减少 L0 PMTable 的增长。（即使 IUL 没有持久化 L0 PMTable）将 L0 PMTable 合并到 L1 PMTable 时，压缩持久化指针的速度很快，而且 IUL 恢复时间比同步的 Checkpoints 短很多，因此可减少 L0 PMTable。

NUMA 效应与跳表

对于跳表而言，每层链表都是最底层链表的有序子集，而根据概率选出上层指针不会影响查询结果，因此上层链表只需要是底层链表的子集。

Braided SkipList 是一种特殊的跳表，可用于减小 NUMA 效应：

跳表每个元素的上层指针指向同一个 NUMA 节点中、更大 key 的元素。与传统实现相比，Braided SkipList 可有效减少 NUMA 节点内存访问次数（减少到 1/N）。

拉链压缩（Zipper Compaction）

论文中采用新的压缩方式，是解决写停顿问题的关键。

原压缩的 Scan 和 Merge 两个过程非常复杂，原文中有详细描述，限于篇幅就不在此处展开了。

（其实是我也还没看...= =）

通过修改指针来归并排序 L0 PMTable 和 L1 PMTable，不阻塞并发读；而本地操作则避免写放大，从而提升压缩的吞吐量。

• 定义分片：L1 PMTable 中一个高度最大的元素到下一个高度最大的元素之间不相交的键范围。
• 要将 L0 PMTable 元素合并到 L1 PMTable，压缩线程需要获得分片上的锁。
• 而拉链压缩分为两个阶段：从头到尾的扫描 和 从尾到头的合并。为保证搜索结果正确，且不阻塞并发读，L0 PMTable 元素由尾到头被合并到 L1 PMTable 中，同时并发读取操作从头到尾遍历。

无锁搜索（Lock-Free Search）

部分研究提出可使用无锁跳表（比如 Java ConcurrentSkipListMap）避免对多个写线程加锁。

写操作：ListDB 的写线程是压缩线程，ListDB 会协调这些线程避免写写冲突，多个压缩线程写入不相交的分片实现并行。

读操作：拉链压缩不会影响并发搜索结果的正确性，读线程不会在不获取锁的情况下错过目标元素：

• 读线程从头到尾、从 L0 PMTable 访问到 L1 PMTable，而压缩线程则是从尾到头合并。
• 拉链压缩时，每个元素都保证是指向至少一个头部，并发读线程访问 PMTable 总能返回正确结果。

在压缩线程修改跳表时，读线程会被挂起，但搜索结果仍然正确：

• 假设读取在访问 L0 PMTable 元素时挂起，在恢复时元素可能已经合并到 L1 PMTable 中。
• 读线程唤醒时如果没有找到搜索键，则继续遍历到尾部、从 L0 PMTable 到 L1 PMTable，因此读线程可能会重复访问元素，但不会错过。
• 为了避免性能受损，当读操作检测到当前元素在 L1 PMTable，则停止搜索 L0 PMTable。

更新与删除

LSM-tree 的写操作会缓冲到 MemTable 中，并逐渐刷新到最后一层 PMTable，在此过程会出现相同的 key。

ListDB 不会主动删除 L1 PMTable 中的旧版本：执行压缩时，压缩线程扫描 L0 PMTable 和 L1 PMTable，将标记 L1 PMTable 中的旧版本为过期。K-V 对象也是同理，删除时是将一个 K-D（即删除标记）插入到 MemTable 中。如果 LSM-tree 从 MemTable 或 L0 PMTable 中物理删除 key 的最新版本，则旧版本的 key 将恢复使用。

这个机制有点像 Kafka 的 Tombstone Record。

压缩时会将较新的 K-V 对象或 K-D 对象放在其对应的旧对象之前，读取总是在旧对象之前访问最近的对象来返回结果。

内存碎片与垃圾收集

当一个内存块所有元素都标记为过期或删除，则释放内存块。由于 ListDB 不会重新定位跳表元素进行垃圾收集，就需要解决内存碎片的问题（压缩线程可使用 COW 的策略，待后续优化）。

简而言之就是为多个 IUL 条目分配和释放一个内存块（比如 8MB）、减少内存分配释放（事务调用）的开销。

使用无锁数据结构，难以判断待释放的内存空间是否仍被并发读取。ListDB 采用基于 epoch 的回收策略：等待足够长的时间，让读请求完成对待释放内存块的访问。当内存块中的所有对象都过期或删除，垃圾收集线程则定期检查并回收内存块。垃圾收集线程检查过时的对象的新版本，当该版本也足够旧、可认为没有再被访问，可从 L1 PMTable 中删除，最终释放物理内存。

线性一致性（Linearizability）

定理 1：在一写多读的场景下，拉链压缩是可线性化的。

拉链压缩是可线性化的，意味着当元素由写事务插入并已提交，无论该元素是在 L0 PMTable 还是 L1 PMTable 中，读取操作始终都能找到该元素。

证明过程见原文。

查找缓存（Look-up Cache）

在 ListDB 的实现中，读请求至少要访问 Mutable MemTable 和 L1 PMTable 这两个索引，读吞吐量低于 B+tree。引入查找缓存：

• 一级缓存：MemTable 每个元素地址存放到固定大小的静态哈希表中。
  • 由于只存储 NVMM 地址（NVMM 元素保存在不会改变的内存地址中），无论元素出现在 L0 PMTable 还是 L1 PMTable 都可以找到。
  • 在压缩时压缩线程经常更新跳表指针，但由于缓存中的地址不可变，缓存不会频繁失效。
  • 当一个哈希桶发生冲突，旧的地址将被覆盖（FIFO）。
• 二级缓存：为加速 L1 PMTable 搜索，在 DRAM 中构造跳表作为从哈希表中移除元素的二级缓存。
  • 使用 SIZE 替换策略，即比较高度并剔除高度较小的元素。
  • 查询时在二级缓存中没有找到 key，可从缓存中找到最近的 PMTable 元素开始搜索（不需要从头部开始）。
  • 由于较小的 L0 PMTable 很快被合并到 L1 PMTable ，L0 PMTable 大部分在哈希表中，因此不使用二级缓存搜索 L0 PMTable。

iter <- MANIFEST.GetTableIterator();
table <- iter.GetTable();                              // 获取 mutable MemTable
while table 6= NULL && table.IsPMTable() = false do
    value <- table.Search(key);                        // 查找跳表
    if value != NULL then
        return value;                                  // 找到直接返回
    end if
    table <- (++iter).GetTable();                      // immutable MemTables
end while

/* 查找 L0 Cache */
cached <- lookup_cache.Lookup(key);
if cached != NULL && cached.GetElement().key = key then
    return cached.GetElement().value;
end if

/* 查找 L0 PMTable */
while table != NULL && table.Level() = 0 do
    value <- table.Search(key);                        // 查找跳表
    if value != NULL then
        return value;                                  // 找到直接返回
    end if
    table <- (++iter).GetTable(); // L0 PMTables
end while

/* 查找 L1 PMTable */
rightmost <- second_chance_cache.Lookup(key);
value <- table.SearchFromElement(key, rightmost);
if value != NULL then
    return value;                                      // 找到直接返回
end if
return NOT_FOUND;

崩溃恢复（Recovery）

在 L0 PMTable 和 L1 PMTable 被压缩合并时系统可能会崩溃。

因此压缩线程会 记录日志（参考 Redo Log）跟踪被合并到 L1 PMTable 的 L0 PMTable。系统重新启动时 ListDB 检查压缩日志、重做未完成的压缩。在重做压缩时，由于很多 L0 PMTable 尾部的条目可与 L1 PMTable 共享，因此压缩时会检查重复的条目。

与传统 LSM-tree 相似，在崩溃恢复时，恢复线程定位（由压缩线程记录在日志中的） WAL 边界，对日志条目排序并恢复 L0 PMTable。此时系统正常执行并处理查询请求，L0 PMTable 和 L1 PMTable 之间的压缩在后台继续进行。

ListDB 可在不恢复缓存的情况下处理客户端查询（只是在重新填充缓存前性能较差）。通过避免重构 DRAM 缓存和索引，ListDB 的恢复性能优于同步 Checkpoint。

ScheduleUnfinishedZipperCompactionJob();
curr_table <- NULL;
while log_iter.Valid() do
    iul_entry <- log_iter.GetIULEntry();
    table_id <- GetTableIdByLSN(iul_entry.LSN);
    if curr_table = NULL || table_id 6= curr_table.Id() then
        curr_table <- MANIFEST.GetTableById(table_id);
        curr_table.ResetSkipListHead();
    end if
    curr_table.InsertEntry(iul_entry);    /* 插入跳表 */
    log_iter.Next();                      /* 从旧到新 */
end while

评估对比

这部分提供了完整的测试实验和数据，笔者建议直接参考原文。

其中包含两种日志机制的对比、不同方案下 NUMA 效应缓解的情况，以及每项技术带来的提升。

（我还没看...= =）

结论

本次论述了 ListDB 设计与实现的过程：这是一种利用字节寻址特性，通过本地重构数据和 NVMM 的高性能来避免数据复制，以减少写放大和写停顿的 K-V 存储系统。

ListDB 通过 异步增量 Checkpoint 和 本地复制 显著提高写性能。基于三层架构，ListDB 在写吞吐量方面表现得比目前最先进的持久性索引和基于 NVMM 的 K-V 存储系统更好；而通过查找缓存缓解了多层结构存在的问题。

作者提到在接下来的工作中将会探索搜索性能提高的方法：如通过引入 L2 PMTable，适时重排 L1 PMTable 元素以满足空间局部性和垃圾收集。

参考

• Martin Kleppmann. Designing Data-Intensive Applications. 2018.
• 周志明. 凤凰架构：构建可靠的大型分布式系统. 2021.
• Wikipedia. Skip list.
• 为什么 NUMA 会影响程序的延迟