RaftDB Storage Engine Documentation

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

1. 核心特性

极速读写 (Blazing Fast):
- Point Lookup: ~23万 QPS (Radix Tree 内存索引)。
- Insert/Update: ~40-56万 QPS (Append-only Log + FreeList)。
高级查询 (Advanced Query):
- Prefix/Range: 基于 Radix Tree 的结构化扫描，性能随数据量增长极慢 (O(K))。
- 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 核心索引: Radix Tree (Memory)

摒弃了传统的 Hash Map + Sharding 方案，采用单体 Radix Tree。

优势:
- 有序性: 天然支持 Key 的字典序遍历，无需排序。
- 前缀压缩: 节省大量内存，特别适合 Key 具有公共前缀的场景。
- 范围查询: WalkPrefix 操作复杂度仅为 O(K)。

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. 性能测试报告 (Benchmark Report)

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

3.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	标记删除

3.2 查询性能 (Query Performance)

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

4. 使用说明

4.1 初始化

import "db"

e, err := db.NewEngine("./my_data")
if err != nil { panic(err) }
defer e.Close()

4.2 查询示例

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

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

db.md 3.6 KB Historia Czysty