批量写入和校验和

在上一章中，你已经构建了一个完整的基于 LSM 的存储引擎。在本周结束时，我们将实现存储引擎的一些简单但重要的优化。欢迎来到 Mini-LSM 第 2 周的零食时间！

在本章中，你将：

实现批量写入接口。
向块、SST 元数据、清单和 WAL 添加校验和。

注意：我们没有本章的单元测试。只要你通过所有之前的测试并确保校验和在你的文件格式中正确编码，就可以了。

任务 1：写入批次接口

在此任务中，我们将通过添加写入批次 API 为本周的第 3 天做准备。你需要修改：

src/lsm_storage.rs

用户提供 write_batch 以及一批要写入数据库的记录。记录是 WriteBatchRecord<T: AsRef<[u8]>>，因此它可以是 Bytes、&[u8] 或 Vec<u8>。有两种类型的记录：删除和放入。你可以以与 put 和 delete 函数相同的方式处理它们。

之后，你可以重构原始的 put 和 delete 函数以调用 write_batch。

实现此功能后，你应该通过之前章节的所有测试用例。

任务 2：块校验和

在此任务中，你需要在编码 SST 时在每个块的末尾添加块校验和。你需要修改：

src/table/builder.rs
src/table.rs

SST 的格式将更改为：

---------------------------------------------------------------------------------------------------------------------------
|                   Block Section                     |                            Meta Section                           |
---------------------------------------------------------------------------------------------------------------------------
| data block | checksum | ... | data block | checksum | metadata | meta block offset | bloom filter | bloom filter offset |
|   varlen   |    u32   |     |   varlen   |    u32   |  varlen  |         u32       |    varlen    |        u32          |
---------------------------------------------------------------------------------------------------------------------------

我们使用 crc32 作为校验和算法。你可以在构建块后使用 crc32fast::hash 为块生成校验和。

通常，当用户在存储选项中指定目标块大小时，大小应包括块内容和校验和。例如，如果目标块大小为 4096，校验和占用 4 字节，实际块内容目标大小应为 4092。然而，为了避免破坏之前的测试用例并为了简单起见，在我们的课程中，我们仍然使用目标块大小作为目标内容大小，并简单地在块末尾附加校验和。

读取块时，你应该在 read_block 中验证校验和正确生成块内容的切片。实现此功能后，你应该通过之前章节的所有测试用例。

任务 3：SST 元校验和

在此任务中，你需要为布隆过滤器和块元数据添加块校验和：

src/table.rs
src/table/bloom.rs
src/table/builder.rs

----------------------------------------------------------------------------------------------------------
|                                                Meta Section                                            |
----------------------------------------------------------------------------------------------------------
| no. of block | metadata | checksum | meta block offset | bloom filter | checksum | bloom filter offset |
|     u32      |  varlen  |    u32   |        u32        |    varlen    |    u32   |        u32          |
----------------------------------------------------------------------------------------------------------

你需要在 Bloom::encode 和 Bloom::decode 中的布隆过滤器末尾添加校验和。注意，我们的大多数 API 接受实现将写入的现有缓冲区，例如 Bloom::encode。因此，你应该在写入编码内容之前记录布隆过滤器开始的偏移量，并且只校验布隆过滤器本身而不是整个缓冲区。

之后，你可以在块元数据末尾添加校验和。你可能会发现在部分开头添加元数据长度也很有帮助，这样在解码块元数据时更容易知道在哪里停止。

任务 4：WAL 校验和

在此任务中，你需要修改：

src/wal.rs

我们将在预写日志中进行每记录校验和。为此，你有两个选择：

生成键值记录的缓冲区，并使用 crc32fast::hash 一次性计算校验和。
一次写入一个字段（例如，键长度、键切片），并使用 crc32fast::Hasher 在每个字段上增量计算校验和。

这取决于你的选择，你需要选择你自己的冒险。只要正确处理小端序/大端序，两种方法都应产生完全相同的结果。新的 WAL 编码应如下所示：

| key_len | key | value_len | value | checksum |

任务 5：清单校验和

最后，让我们在清单文件上添加校验和。清单类似于 WAL，除了之前我们不存储每个记录的长度。为了使实现更容易，我们现在在记录开头添加记录长度的头部，并在记录末尾添加校验和。

新的清单格式如下：

| len | JSON 记录 | checksum | len | JSON 记录 | checksum | len | JSON 记录 | checksum |

实现所有内容后，你应该通过所有之前的测试用例。我们在本章中没有提供新的测试用例。

测试你的理解

考虑 LSM 存储引擎只提供 write_batch 作为写入接口（而不是单个 put + delete）的情况。是否可以如下实现：有一个带有 mpsc 通道接收器的单个写入线程来获取更改，所有线程将写入批次发送到写入线程。写入线程是写入数据库的唯一点。这种实现的优缺点是什么？（如果你这样做，恭喜你得到了 BadgerDB！）
将所有块校验和一起放在 SST 文件的末尾而不是与块一起存储可以吗？为什么？

我们不提供问题的参考答案，欢迎在 Discord 社区中讨论它们。

额外任务

损坏时恢复。 如果存在校验和错误，以安全模式打开数据库，以便无法执行写入，但仍可以检索未损坏的数据。

我们非常感激你的反馈。欢迎加入我们的 Discord 社区。
发现问题？在 github.com/skyzh/mini-lsm 上创建问题/拉取请求。
mini-lsm-book © 2022-2025 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Keyboard shortcuts

一周学会 LSM