RaftDB 存储引擎文档

RaftDB 内置了一个专为 Raft 状态机设计的高性能、线程安全的嵌入式键值（KV）存储引擎。它采用了 扁平有序数组 (Flat Sorted Array) 作为核心内存索引，结合 倒排索引 (Inverted Index) 支持全文检索，并使用 追加写日志 (Append-Only Log) 保证数据的持久化。

1. 核心特性

极致性能 (High Performance):
- 内存索引: 使用基于有序数组的二分查找，读取性能极高，无指针开销。
- 追加写入: 所有写操作（Put/Delete）均追加到文件末尾，充分利用磁盘顺序写带宽。
高级查询能力 (Advanced Querying):
- 前缀扫描: 得益于有序索引，支持高效的 key like "prefix*" 前缀范围扫描。
- 全文检索: 内置倒排索引，支持 value like "*token*" 的模糊查询，无需全表扫描。
- SQL-Like 语法: 支持 LIMIT, OFFSET 以及复杂的组合过滤条件（例如 key="k1" AND value like "v*"）。
数据安全与一致性 (Safety & Consistency):
- CRC32 校验: 每条记录都包含 CRC32 校验和，防止磁盘静默错误导致的数据损坏。
- 快照隔离: 支持生成全量的一致性快照，用于 Raft 日志压缩。

2. 架构设计

2.1 核心索引：扁平有序数组 (Memory - Primary Index)

不同于传统的 B-Tree 或 Hash Map，本引擎采用了 Flat Sorted Array 结构：

数据结构:
- keyBuf: 一个巨大的单一 []byte 缓冲，紧凑存储所有 Key 的字符串数据。
- items: 一个切片，存储轻量级的元数据结构（包含 Key 的偏移量、长度，以及 Value 在磁盘上的偏移量、CommitIndex）。
优势:
- 极度紧凑: 极大地减少了内存碎片和每个 Key 的额外开销。
- 缓存友好: 连续的内存布局使得 CPU 缓存命中率极高。
- GC 友好: 几乎不产生指针，大幅降低了 Go GC 的扫描压力。

2.2 辅助索引：全文倒排索引 (Memory - Secondary Index)

为了支持 value like 查询，引擎维护了一个倒排索引：

映射关系: Token (词) -> Key Set (包含该词的 Key 集合)。
分词策略: 简单的按非字母数字字符分割。
查询优化: 当查询包含 value like 时，查询优化器会自动通过倒排索引筛选 Key，避免昂贵的全表 Value 读取。

2.3 存储层 (Disk Storage)

Append-Only Log: 数据存储在 values.data 文件中。
- 写入 (Put): 追加 [Header][Key][Value]。
- 删除 (Delete): 追加一个墓碑（Tombstone）记录。
元数据 (Metadata): meta.state 文件独立存储 LastCommitIndex，允许系统快速启动而无需重放整个日志。
缓存 (Caching): 内置简单的 LRU 策略缓存，缓存最近读取的 Value，减少热点数据的磁盘 IO。

3. 一致性与持久化

3.1 持久性 (Durability)

Sync 机制: 引擎提供 Sync() 方法，调用系统调用 fsync 强制将 OS 页缓存刷入磁盘。
Raft 集成: Raft 在执行快照（Snapshot）前会强制调用 Sync()，确保在删除 Raft Log 之前，数据已经物理持久化。

3.2 数据完整性 (Integrity)

校验和: 每条记录写入时计算 CRC32，读取时验证。
故障恢复: 启动扫描时，如果发现文件尾部有损坏或写入不完整的记录（常见于断电崩溃），引擎会自动截断尾部脏数据，保证数据库状态的一致性。

3.3 快照与恢复 (Snapshot & Restore)

这是 Raft Log Compaction 的核心机制：

Snapshot (快照): 锁定内存索引，将当前所有有效的 Key-Value 对序列化为一个紧凑的二进制流。这个流代表了某一时刻（CommitIndex）的完整状态机状态。
Restore (恢复):
1. 关闭当前数据库。
2. Truncate (清空) 数据文件。
3. 从快照流中重建数据文件和内存索引。
4. 强制刷盘。此过程通常用于落后太多的 Follower 节点快速追赶 Leader。

4. 查询语言 (Query Language)

引擎支持一种简化的 SQL 风格查询语法，用于调试和数据检查：

-- 精确查找 (Point Lookup)
key = "user:1001"

-- 前缀范围查询 (Prefix Search)
key like "user:*"

-- 全文模糊查询 (Full-Text Search, 需要开启 ValueIndex)
value like "error"

-- 组合过滤 (Complex Filtering)
key like "log:*" AND value like "*critical*"

-- 分页 (Pagination)
key like "user:*" LIMIT 10 OFFSET 20

-- 基于 Raft Index 过滤
CommitIndex > 1000

5. 配置说明

// 初始化引擎时可以配置选项
// 例如：开启全文索引（会消耗更多内存）
engine, err := db.NewEngine(path, db.WithValueIndex(true))

6. 性能特征

写入: O(1) 磁盘追加 + O(N) 内存插入（数组移动）。
- 注: 由于使用有序数组，插入涉及内存移动，因此该引擎更适合读多写少或批量写入的场景。
读取: O(log N) 内存二分查找 + 1次磁盘 Seek。
扫描: O(log N) 定位起点 + O(M) 顺序扫描 M 个元素。
全文搜索: O(1) 倒排索引查找 + O(K) 结果集过滤。

7. 局限性

内存限制: 虽然 Value 存储在磁盘，但所有 Key 和索引元数据必须能放入内存。
空间回收: 由于采用 Append-Only 模式，删除操作不会立即释放磁盘空间。空间回收依赖于 Raft 的 Snapshot/Restore 机制（Restore 会重写数据文件，从而清理垃圾数据）。

db.md 5.6 KB Түүх Анхны өгөгдөл