基于本地磁盘的 WAL
架构
本节将介绍基于本地磁盘的单机版 WAL（Write-Ahead Log，以下简称日志）的实现。在此实现中，日志按 region 级别进行管理。
┌────────────────────────────┐
│ HoraeDB │
│ │
│ ┌────────────────────────┐ │
│ │ WAL │ │ ┌────────────────────────┐
│ │ │ │ │ │
│ │ ...... │ │ │ File System │
│ │ │ │ │ │
│ │ ┌────────────────────┐ │ │ manage │ ┌────────────────────┐ │
Write ─────┼─┼─► Region ├─┼─┼─────────┼─► Region Dir │ │
│ │ │ │ │ │ │ │ │ │
Read ─────┼─┼─► ┌────────────┐ │ │ │ mmap │ │ ┌────────────────┐ │ │
│ │ │ │ Segment 0 ├───┼─┼─┼─────────┼─┼─► Segment File 0 │ │ │
│ │ │ └────────────┘ │ │ │ │ │ └────────────────┘ │ │
Delete ─────┼─┼─► ┌────────────┐ │ │ │ mmap │ │ ┌────────────────┐ │ │
│ │ │ │ Segment 1 ├───┼─┼─┼─────────┼─┼─► SegmenteFile 1 │ │ │
│ │ │ └────────────┘ │ │ │ │ │ └────────────────┘ │ │
│ │ │ ┌────────────┐ │ │ │ mmap │ │ ┌────────────────┐ │ │
│ │ │ │ Segment 2 ├───┼─┼─┼─────────┼─┼─► SegmenteFile 2 │ │ │
│ │ │ └────────────┘ │ │ │ │ │ └────────────────┘ │ │
│ │ │ ...... │ │ │ │ │ ...... │ │
│ │ └────────────────────┘ │ │ │ └────────────────────┘ │
│ │ ...... │ │ │ ...... │
│ └────────────────────────┘ │ └────────────────────────┘
└────────────────────────────┘
数据模型
文件路径
每个 region 都拥有一个目录，用于管理该 region 的所有 segment。目录名为 region 的 ID。每个 segment 的命名方式为 seg_<id>，ID 从 0 开始递增。
Segment 的格式
一个 region 中所有表的日志都存储在 segments 中，并按照 sequence number 从小到大排列。segment 文件的结构如下：
Segment0 Segment1
┌────────────┐ ┌────────────┐
│ Magic Num │ │ Magic Num │
├────────────┤ ├────────────┤
│ Record │ │ Record │
├────────────┤ ├────────────┤
│ Record │ │ Record │
├────────────┤ ├────────────┤ ....
│ Record │ │ Record │
├────────────┤ ├────────────┤
│ ... │ │ ... │
│ │ │ │
└────────────┘ └────────────┘
seg_0 seg_1
在内存中，每个 segment 还会存储一些额外的信息以供读写和删除操作使用：
pub struct Segment {
/// A hashmap storing both min and max sequence numbers of records within
/// this segment for each `TableId`.
table_ranges: HashMap<TableId, (SequenceNumber, SequenceNumber)>,
/// An optional vector of positions within the segment.
record_position: Vec<Position>,
...
}
日志格式
segment 中的日志格式如下：
+---------+--------+------------+--------------+--------------+-------+
| version | crc | table id | sequence num | value length | value |
| (u8) | (u32) | (u64) | (u64) | (u32) |(bytes)|
+---------+--------+------------+--------------+--------------+-------+
字段说明：
version：日志版本号。crc：用于确保数据一致性。计算从 table id 到该记录结束的 CRC 校验值。table id：表的唯一标识符。sequence num：记录的序列号。value length：value 的字节长度。value：通用日志格式中的值。
日志中不存储 region ID，因为可以通过文件路径获取该信息。
主要流程
打开 Wal
识别 Wal 目录下的所有 region 目录。
在每个 region 目录下，识别所有 segment 文件。
打开每个 segment 文件，遍历其中的所有日志，记录其中每个日志开始和结束的偏移量和每个
TableId在该 segment 中的最小和最大序列号，然后关闭文件。如果不存在 region 目录或目录下没有任何 segment 文件，则自动创建相应的目录和文件。
读日志
- 根据 segment 的元数据，确定本次读取操作涉及的所有 segment。
- 按照 id 从小到大的顺序，依次打开这些 segment，将原始字节解码为日志。
写日志
将待写入的日志序列化为字节数据，追加到 id 最大的 segment 文件中。
每个 segment 创建时预分配固定大小的 64MB，不会动态改变。当预分配的空间用完后，创建一个新的 segment，并切换到新的 segment 继续追加。
每次追加后不会立即调用 flush；默认情况下，每写入十次或在 segment 文件关闭时才执行 flush。
在内存中更新 segment 的元数据
table_ranges。
删除日志
假设需要将 id 为 table_id 的表中，序列号小于 seq_num 的日志标记为删除：
在内存中更新相关 segment 的
table_ranges字段，将该表的最小序列号更新为 seq_num + 1。如果修改后，该表在此 segment 中的最小序列号大于最大序列号，则从
table_ranges中删除该表。如果一个 segment 的
table_ranges为空，且不是 id 最大的 segment，则删除该 segment 文件。