【LSM-Tree】WAL + MemTable：崩溃了也不丢数据
💡
原文中文，约18100字，阅读约需43分钟。
📝
内容提要
本文介绍了WAL（Write-Ahead Log）和MemTable的实现，解决了数据持久性问题。WAL通过先写日志再写内存，确保崩溃后数据可恢复。MemTable使用跳表结构，支持高效的插入和查找。文章讨论了WAL的记录格式、分片策略及崩溃恢复的正确性，确保数据在系统崩溃时不会丢失。
🎯
关键要点
- WAL（Write-Ahead Log）通过先写日志再写内存，确保数据持久性，避免崩溃后数据丢失。
- WAL记录格式包括CRC32校验、长度、类型和数据，确保恢复时的正确性和速度。
- MemTable使用跳表结构，支持高效的插入和查找，具有并发友好和实现简单的优点。
- 在MemTable中，用户键被编码为InternalKey，包含序列号和类型，以支持版本控制。
- 崩溃恢复流程通过读取WAL文件，逐条解析记录并重放到新MemTable，确保数据完整性。
- WAL和MemTable的写入路径满足持久性、顺序性和恢复完整性三个不变式，确保数据安全。
❓
延伸问答
WAL（Write-Ahead Log）是如何确保数据持久性的？
WAL通过先将数据写入日志文件，再写入内存中的MemTable，确保在崩溃后可以从日志中恢复数据。
MemTable使用什么数据结构，为什么选择它？
MemTable使用跳表结构，因为它支持高效的插入和查找，并且实现简单且并发友好。
WAL的记录格式包含哪些字段？
WAL的记录格式包括CRC32校验、长度、类型和数据，确保恢复时的正确性和速度。
崩溃恢复的流程是怎样的？
崩溃恢复流程包括打开WAL文件，按块读取记录，校验CRC，重放有效记录到新MemTable。
WAL和MemTable的写入路径满足哪些不变式？
WAL和MemTable的写入路径满足持久性、顺序性和恢复完整性三个不变式，确保数据安全。
如何处理WAL中的分片记录？
分片记录通过读取FIRST、MIDDLE和LAST类型的记录进行拼装，确保完整性。
➡️
