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()，但这会显著降低写入吞吐量（从 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 查询性能。

5. 使用说明

5.1 初始化

import "db"

// 默认模式 (Key Only Index)
e, err := db.NewEngine("./my_data")
if err != nil { panic(err) }
defer e.Close()

// 若需支持 value like 全文检索:
// e, err := db.NewEngine("./my_data", db.WithValueIndex(true))

5.2 查询示例

// 1. 极速前缀分页
// 引擎在索引上定位 "user." 范围，扫描前 20 条即停止
results, _ := e.Query(`key like "user.*" LIMIT 20`)

// 2. 高性能全文检索 (需开启 Value Index)
// 引擎利用倒排索引直接定位包含 "error" 的记录，无需扫描全表
results, _ := e.Query(`value like "*error*"`)