Step 1

题目摘要引言

Title

Yaurus: Lightweight Parallel Logging for In-Memory Database Management

轻量级并行日志记录内存数据库管理系统

Abstract

现有的单流日志记录方案（single-stream Logging）不适合内存数据库管理系统 (DBMS)，因为单日志通常是性能瓶颈。 为了克服这个问题，我们提出了 Taurus，一种使用多个日志流的高效并行日志记录方案，并且兼容数据和命令日志记录。 Taurus 使用日志序列号 (log sequence numbers LSNs) 向量跟踪和编码事务依赖性。 这些向量确保在日志记录中完全捕获依赖关系并在恢复中正确强制执行。 我们对内存 DBMS 的实验评估表明，与单流数据记录和命令记录相比，Taurus 的并行记录分别实现了高达 9.9 倍和 2.9 倍的加速。 它还使 DBMS 的恢复速度分别比这些基线数据和命令记录快 22.9 倍和 75.6 倍。 我们还将 Taurus 与两种最先进的并行日志记录方案进行了比较，结果表明 DBMS 在 NVMe 驱动器上实现了高达 2.8 倍的性能提升，在 HDD 上实现了 9.2 倍的性能提升。

Introduction

事务与奔溃一致性

数据库管理系统 (DBMS) 保证即使系统崩溃，事务对数据库的修改也能持续存在。 强制执行持久性的最常见方法是预写日志（write-ahead-Logging WAL），其中每个事务在提交之前将其更改顺序写入持久性存储设备（例如 HDD、SSD、NVM）。 随着现代多核硬件并行性的提高和高吞吐量内存式 DBMS 的上升趋势，顺序日志记录（sequential logging）引起的可扩展性瓶颈是繁重的，激发了对并行解决方案的需求。

然而，执行并行日志记录并非易事，因为系统必须确保事务的正确恢复顺序。 尽管这在顺序日志中很简单，因为 LSN（日志文件中事务记录的位置）明确定义了事务的顺序，但在没有中央 LSN 的情况下有效恢复分布在多个日志中的事务并不容易。 并行日志记录方案必须跨多个日志维护事务的顺序信息才能正确恢复

回顾历史上的多个并行日志和恢复协议

文献 [16, 35, 37, 44] 中有几个并行的测井和恢复协议。 然而，这些先前的设计在其范围 scope 和适用性 applicability 方面受到限制。 一些算法只支持并行数据日志而不支持并行命令日志 [14, 35, 44]； 有些只能并行化恢复过程，而不能并行化日志记录过程 [8, 30]； 一些协议假设使用 NVM 硬件，但不适用于传统存储设备 [3, 4, 6, 10, 15, 21, 22, 36]。 因此，先前提出的方法对于不同操作环境中的现代 DBMS 来说是不够的

引出 Taurus

为了克服这些限制，我们提出了 Taurus，一种并行执行日至记录和恢复的轻量级协议，支持数据和命令日志记录，并与多种并发控制方案兼容。 Taurus 通过跟踪事务间的依赖关系来实现这一点。 恢复算法使用此信息来确定事务的顺序。 Taurus 将依赖关系编码为 LSN 向量，我们将其定义为 LSN 向量 (LV)。 LSN 向量的灵感来自向量时钟，以在消息传递系统中强制执行偏序 [11, 27]。 为了减少维护 LV 的开销，Taurus 根据观察到 DBMS 可以恢复没有任何顺序依赖关系的事务来压缩向量

性能评价

我们将 Taurus 的性能与串行日志记录方案（有和没有 RAID-0 设置）和最先进的并行日志记录方案（即 Silo-R [35, 44] 和 Plover [45]）进行比较 在 YCSB 和 TPC-C 基准测试中。 我们对 8 个 NVMe SSD 的评估表明，具有数据记录的 Taurus 在运行时优于串行数据记录 9.9 倍，具有命令记录的 Taurus 优于串行命令记录的 2.9 倍。 在恢复期间，具有数据记录和命令记录的 Taurus 分别比串行基线快 22.9 倍和 75.6 倍。 带数据记录的 Taurus 与其他并行方案的性能相匹配，带命令记录的 Taurus 在运行时和恢复时的速度提高了 2.8 倍。 对 8 个 HDD 的另一项评估表明，具有命令日志记录的 Taurus 在日志记录和恢复方面分别比这些并行算法快 9.2 倍和 6.4 倍

Contribution

• 我们提出了支持命令记录和数据记录的 Taurus 并行方案。 我们在扩展版本 [39] 中正式证明了正确性和活性。
• 我们提出了优化建议，以减少 Taurus 维护的依赖信息和扩展的内存占用，以支持多种并发控制算法。
• 我们根据顺序和并行日志记录方案评估 Taurus，并展示其优势和通用性。
• 我们在 https://github.com/yuxiamit/DBx1000_logging 开源 Taurus 和评估脚本。

基本理论概况

Background

Serial Logging

Coventional Way

协议保证：ordering invariant，如果\(T2\) 依赖\(T1\)，那么 DBMS 会在\(T1\) 写入磁盘后写入\(T2\)

恢复过程，DBMS 读取 log 并顺序执行每一个事务直至遇到不完整记录，或者文件文件结尾。

通常，有两类日志记录方案。 第一个是数据日志 data logging，其中日志记录包含事务对数据库所做的物理修改。 恢复过程将这些更改重新应用到数据库。 另一个类别，命令日志 command logging [26]，通过仅记录高级命令（比如调用存储过程）来减少日志数据量。 这些命令的日志记录通常小于物理更改。 恢复过程涉及更多计算，因为所有事务都被重新执行。 如果磁盘带宽是瓶颈，命令日志记录可以大大优于数据日志记录

尽管串行日志本质上是顺序的，但可以通过使用充当单个存储设备的 RAID 磁盘来提高其性能 [31]。 如果 DBMS 使用数据记录 [33, 35, 44]，串行记录也可以支持并行恢复。 但是区分串行日志记录和并行日志记录的基本属性是它依赖于尊重事务之间所有数据依赖性的单个日志流。 在具有许多 CPU 内核的现代内存 DBMS 上，这样的单个日志流是可扩展性瓶颈 [35]。 由于缓存一致性流量，竞争单个原子 LSN 计数器会抑制性能

Parallel Logging Challenges

Modern Way but Challenging

并行日志允许事务写入多个日志流（例如，每个磁盘一个流），从而避免串行日志的可扩展性瓶颈，以满足内存 DBMS 的高吞吐量需求。

多个流抑制了交易的固有自然顺序。 因此，需要其他机制来跟踪和强制执行这些事务之间的排序。

举例，T2 T1 比高兴，T2 Read-After-Write 依赖 T1 但是 T2 先写好 T1 未写好，Crash，DBMS 必须意识到这种依赖。

主要面临的挑战：

• 挑战 1：When to Commit a Transaction
• 挑战 2：Whether to Recover a Transaction
• 挑战 3：Determine the Recovery Order

结论部分

回答基本问题

1. 类别

2. 内容

3. 正确性

4. 创新点

5. 清晰度

阅读选择

继续阅读

Step 2

细读笔记

Taurus Parallel Logging

3.1 LSN Vector

形式化描述及其定义

Logging Operations

日志记录过程

Recovering Operations

恢复过程

Supporting Index Operations

Optimizations and Extensions

主要的方法：LV Compression,Vectorization，以及支持拓展：OCC，拓展，多版本 MVCC（Multi-Versioning）

问题记录

未读（且值得读）文献记录

Step 3

思路复现

证明与推理复现

实验验证复现