raft/db/db.md

RaftDB Storage Engine Documentation

RaftDB 内置了一个高性能、线程安全的嵌入式键值存储引擎。该引擎专为 Raft 状态机设计，经过深度优化，采用 Flat Sorted Array (有序扁平数组) 作为核心索引结构，并结合了 倒排索引 (Inverted Index) 以支持极速全文/模糊检索。

1. 核心特性

• 极速读写 (Blazing Fast):
  • Point Lookup: ~23万 QPS (基于 Binary Search 的内存索引)。
  • Insert/Update: ~40-56万 QPS (Append-only Log + FreeList)。
• 高级查询 (Advanced Query):
  • Prefix/Range: 基于有序数组的二分查找 + 顺序扫描，内存局部性极佳。
  • Full Text Search: 针对 value like 查询引入倒排索引，性能提升 20倍。
  • Limit Pushdown: 查询执行器支持 LIMIT/OFFSET 下推，扫描满足即停止。
• 空间复用 (Disk Reuse): 内置 Best-Fit 策略的 FreeList，自动回收磁盘空间，无需手动 Compaction。
• 热点缓存 (Hot Cache): 内置 LRU-style 缓存，减少 Syscall。

2. 架构设计 (Architecture)

2.1 核心索引: Flat Sorted Array (Memory)

摒弃了传统的 Hash Map 或 Tree 结构，采用极致内存优化的 Flat Sorted Array。

• 设计:
  • Key Buffer: 所有 Key 紧凑存储在一个 []byte 大数组中，无 Go String Header 开销。
  • Item Slice: 索引项仅存储 Offset(4B) + Len(2B) + Metadata，并在内存中保持有序。
• 优势:
  • 零指针开销: 消除海量指针和对象头，大幅降低 GC 压力。
  • 内存极致紧凑: 索引条目仅占 ~24 字节/Key，百万级 Key 仅需几十 MB。
  • 缓存友好: 数组结构对 CPU Cache 极其友好。
  • 范围查询: 二分查找定位起点，顺序扫描后续数据，天然支持 Range Scan。

2.2 辅助索引: Inverted Index (Memory)

针对 value like "*token*" 等模糊查询场景，引擎维护了一个轻量级的倒排索引 (Token -> Keys)。

• 查询优化: 当检测到查询包含特定 Token 时，查询规划器会跳过全表扫描，直接通过倒排索引定位 Candidate Keys。

2.3 存储层 (Storage Layer)

• Append-only Log: 数据追加写入，保证崩溃恢复能力。
• In-Place Update: 尝试原地更新（若空间足够），减少碎片。
• FreeList: 维护空闲槽位，优先复用。
• Page Cache: 简单的内存缓存层，减少系统调用。

3. 安全性与一致性评估 (Safety & Consistency Analysis)

3.1 数据持久性 (Durability)

• 当前机制: 使用 WriteAt 写入操作系统 Page Cache。
• 风险: 高。目前默认未开启 fsync。若发生操作系统崩溃或断电，最近写入的数据（尚未刷盘部分）将会丢失。
  • 注: 进程级崩溃（Panic/Kill）是安全的，因为 OS 仍掌管 Page Cache。
• 快照安全性增强: 为了解决日志压缩带来的风险，系统在 生成快照前强制调用 Sync()。这确保了在 Raft 删除旧日志之前，对应的数据一定已经物理持久化。
• 建议: 在关键业务场景下，应在写入后显式调用 Sync()，但这会显著降低写入吞吐量（从 40w QPS 降至磁盘 IOPS 极限）。

3.2 数据完整性 (Integrity)

• 当前机制: 引入了 CRC32 Checksum 校验每个 Record (Header + Data)。
• 恢复策略: 启动时 Scan 会验证 CRC。
• 风险: 中。
  • 若日志尾部写入不完整（Partial Write），Scan 会自动截断丢弃，保证一致性。
  • 若日志中间发生比特翻转（Bit Rot），Scan 会在错误处停止，导致该点之后的所有数据不可见。这是一种“宁缺毋滥”的牺牲可用性保一致性的策略。

3.3 数据一致性 (Consistency)

• 索引与存储: 内存索引在启动时完全通过磁盘日志重构，保证了强一致性。
• 并发可见性:
  • Set 操作通过互斥锁串行化，保证了写入线性一致。
  • 读写并发: Query 并不阻塞 Set 的日志写入，但在读取索引时持有 RLock。这可能导致短暂的“幻读”或可见性延迟，但不会导致数据错乱。
  • 风险: 极低。符合最终一致性模型。

3.4 并发模型瓶颈

• I/O 阻塞: Query 在遍历索引时（持有 RLock）会进行磁盘 I/O (ReadValue)。
• 影响: 如果磁盘响应慢，长时间的 RLock 会阻塞所有试图获取 Lock 的 Set 操作（写阻塞）。在慢磁盘或高并发读场景下，写入延迟可能显著增加。

4. 性能测试报告 (Benchmark Report)

测试环境: macOS, 10 并发 Workers, 本地磁盘 IO。

4.1 综合吞吐量 (Throughput)

操作类型	数量	耗时	QPS (Ops/sec)	说明
Insert	100,000	~0.25s	~399,000	写入性能极强
Insert (Reuse)	5,000	~0.01s	~560,000	空间复用路径极快
Update	10,000	~0.04s	~252,000	原地更新优化生效
Delete	10,000	~0.02s	~420,000	标记删除

4.2 查询性能 (Query Performance)

查询类型	QPS (Ops/sec)	提升幅度	说明
Point Lookup	~228,000	-	基准性能，极快。
Meta Query	~78,000	2x (vs SkipList)	前缀查询 key like "prefix*"。有序数组二分查找优势。
Limit Query	~287,000	1.6x (vs SkipList)	LIMIT 下推优化，扫描极少数据即返回。
Full Scan (Val)	~581	21.5x (vs Scan)	倒排索引生效。从全表 IO 扫描变为内存索引查找。

4.3 内存占用分析 (Memory Usage)

场景	内存占用 (10w Keys)	说明
仅核心索引 (Key Only)	5.46 MB	Flat Sorted Array 生效。仅 ~55字节/Key (含Go Runtime开销)，极其紧凑。
开启全文索引 (With Value Index)	73.93 MB	倒排索引 (Token -> Keys) 占用主要内存，以空间换取 20x 查询性能。

6. 快照与恢复 (Snapshot & Restore)

6.1 设计理念

本数据库引擎本身被设计为一个实时的持久化状态机。

• 实时快照: 数据库文件 (values.data) 加上内存索引，随时代表了某个 LastCommitIndex 处的一致性快照。
• 日志无关性: Raft 日志可以安全地被压缩或删除，只要数据库中已经持久化了对应的 CommitIndex。
• 增量同步: 正常的同步流程是 Raft 异步地将日志 Apply 到数据库。
• 全量同步: 当新节点加入或落后太多（日志已被清理）时，通过 Snapshot 接口生成全量数据镜像。

6.2 Snapshot 机制

// 生成全量快照二进制流
data, err := e.Snapshot()

• 过程: 锁定内存索引，并发遍历所有 Key，从磁盘或缓存读取 Value，序列化为紧凑的二进制流。
• 格式: [Count U64] + [Record...]
  • Record: [KeyLen U16][Key][ValLen U32][Value][CommitIndex U64]

6.3 Restore 机制

// 从快照恢复状态
err := e.Restore(data)

• 过程:
  1. Stop-the-World: 锁定写入，关闭当前存储文件。
  2. Truncate: 直接清空当前数据文件 (values.data) 和元数据文件 (meta.state)。
  3. Reset Memory: 清空内存索引 (FlatIndex) 和缓存。
  4. Rebuild: 按照快照流顺序，重新生成新的 Append-Only Log 文件，并重建内存索引。
  5. Sync: 强制刷盘，更新 LastCommitIndex 到最新状态。
• 场景: 仅在节点数据严重滞后（Raft Log 已被截断）或数据损坏时触发。

6.4 容灾与安全性

• 独立元数据: 引入 meta.state 文件专门记录 LastCommitIndex，不再依赖全盘扫描，实现秒级重启。
• 幂等性写入: 内部维护 LastCommitIndex，自动忽略已 Apply 的 Raft Log，防止重放攻击或重复写入。
• Crash Recovery:
  • Meta 优先: 启动时读取 meta.state。
  • Scan 兜底: 若 Meta 损坏，自动扫描数据文件尾部修正 LastCommitIndex。
  • Truncate 保护: 扫描过程中若发现 CRC 错误或截断，自动丢弃尾部脏数据，保证一致性。
  • Raft 协同启动: 引擎提供 GetLastAppliedIndex() 接口。系统启动时，Raft 会直接读取该索引作为初始状态，跳过回放已入库的日志，实现极速启动。
• 一致性保障 (Snapshot Safety):
  • 强制同步: 快照生成接口 SnapshotProvider(minIncludeIndex) 会阻塞等待，直到 DB 的 LastAppliedIndex 至少追赶到目标索引 minIncludeIndex。
  • 强制落盘: 在返回快照数据前，引擎执行 Sync()，确保数据物理安全。
  • 原子压缩: 只有在确保数据已安全转入快照（DB 已追赶、已刷盘并成功生成快照）后，Raft 才会执行物理日志截断。这杜绝了“日志被删但数据未入库”的数据丢失风险。