RaftDB Storage Engine Documentation

RaftDB 内置了一个高性能、线程安全的嵌入式键值存储引擎。该引擎专为 Raft 状态机设计，支持高并发读写、倒排索引查询以及磁盘空间复用。

1. 核心特性

高并发 (High Concurrency): 采用分片锁 (Striped Locking) 和原子操作，支持数万 QPS 的并行读写。
数据安全 (Data Safety): Key 级锁确保同一 Key 的读写操作原子性，避免脏读和写冲突。
磁盘复用 (Disk Reuse): 内置 Best-Fit 策略的 FreeList，自动回收并重用被删除或更新产生的空闲磁盘空间。
倒排索引 (Inverted Index): 支持对 Key 和 Value 的自动分词索引，支持复杂的 SQL 风格查询。
崩溃一致性 (Crash Consistency): 优化的写入顺序（Write New -> Update Index -> Mark Old Deleted），确保数据不丢失。

2. 架构设计

2.1 存储布局 (Storage Layout)

数据存储在单个 append-only 文件中 (values.data)，但支持空间复用。

物理格式:

[Header][Data]

Header (9 bytes):
- Flag (1 byte): 0x01 (Valid) 或 0x00 (Deleted)
- Capacity (4 bytes): 该槽位分配的总大小（包含 Data），用于复用。
- Length (4 bytes): 实际数据长度。
Data: 实际存储的 Key/Value 数据。

2.2 内存索引 (In-Memory Index)

为了减少锁竞争，核心数据结构均采用了分片设计 (Sharding)。

IndexShards (16 Shards):
- 存储 KeyID -> {FileOffset, CommitIndex} 的映射。
- 读写请求根据 KeyHash 分发到不同分片，互不干扰。
KeyMap (16 Shards):
- 维护 String Key <-> uint32 KeyID 的双向映射。
- 减少内存占用（索引中使用 uint32 替代 string），并加速比较。
InvertedIndex (16 Shards):
- 维护 Token -> []KeyID 的倒排表。
- 支持 LIKE 和全文匹配查询。

2.3 锁机制 (Locking Strategy)

Key Locks (1024 Striped Locks):
- 针对特定 Key 的操作（Get/Set）必须先获取该 Key 对应的 Hash 锁。
- 保证了同一 Key 的强一致性。
Shard Locks:
- 仅在访问 Index 映射表时短暂持有，IO 操作在 Index 锁之外进行。
Atomic Offset:
- 文件追加写操作使用 atomic.AddInt64，无需全局锁。

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

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

3.1 吞吐量 (Throughput)

操作类型	数量	耗时	QPS (Ops/sec)	说明
Insert	100,000	~2.07s	~48,300	批量写入，完全并行
Update	10,000	~0.09s	~106,000	混合原地更新与追加写
Insert (Reuse)	5,000	~0.27s	~18,200	复用旧空间，无需文件增长
Delete	10,000	~0.02s	~403,800	标记删除，极快

3.2 磁盘空间复用验证

初始写入 (100k items): DB Size 3.91 MB
更新后 (10k updates): DB Size 4.33 MB (仅少量增长，部分原地更新)
删除后 (10k deletes): DB Size 4.61 MB (文件大小不变，产生空洞)
复用写入 (5k reuse): DB Size 4.61 MB (完全复用空洞，文件大小零增长)

结论: FreeList 机制有效工作，长时间运行后数据库文件大小将趋于稳定，不会无限膨胀。

3.3 数据完整性验证

并发写安全: 100% 通过。多线程更新同一 Key 也是安全的。
数据一致性: 100% 通过。全量扫描验证所有 Key 的值均为预期最新值。

4. 使用说明

4.1 初始化

import "db"

// 初始化引擎，指定数据目录
e, err := db.NewEngine("./my_data")
if err != nil {
    panic(err)
}
defer e.Close()

4.2 基本读写

// 写入数据 (Key, Value, CommitIndex)
err := e.Set("user.1001", "{\"name\":\"Alice\"}", 1)

// 读取数据
val, found := e.Get("user.1001")
if found {
    fmt.Println("Value:", val)
}

4.3 高级查询 (SQL-like)

支持对 Key、Value 和 CommitIndex 进行查询。

// 查询所有 name 包含 "Alice" 且 CommitIndex > 0 的记录
results, err := e.Query(`value like "*Alice*" commit_index > 0`)

for _, row := range results {
    fmt.Printf("Key: %s, Val: %s\n", row.Key, row.Value)
}

5. 改进与优化历史

初始版本: 全局互斥锁，性能瓶颈明显 (~15k QPS)。
V1 优化: 引入 KeyMap 和 Index 分片，去除文件 IO 全局锁，使用 pwrite/pread。QPS 提升至 ~49k。
V2 安全加固: 引入 StripedLock (Key级锁) 解决并发写冲突和脏读问题。在保证安全的前提下，Update/Delete 性能进一步提升至 100k+ QPS。

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