raft/db/db.md

RaftDB Storage Engine Documentation

RaftDB 内置了一个高性能、线程安全的嵌入式键值存储引擎。该引擎专为 Raft 状态机设计，经过深度优化，采用 Radix Tree（基数树）作为核心索引结构。

1. 核心特性

• 极速读写 (Blazing Fast): 基于 Radix Tree 的内存索引，支持数十万 QPS 的读写。
• 高级查询 (Advanced Query): 支持前缀搜索、范围扫描，以及 LIMIT/OFFSET 下推优化。
• 空间复用 (Disk Reuse): 内置 Best-Fit 策略的 FreeList，自动回收磁盘空间。
• 热点缓存 (Hot Cache): 内置 LRU-style 缓存，加速热点数据读取。
• 全文本支持 (Full Text): 基础的倒排索引架构（可扩展）。

2. 架构设计 (Architecture)

2.1 核心索引: Radix Tree (Memory)

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

• 优势:
  • 有序性: 天然支持 Key 的字典序遍历，无需排序。
  • 前缀压缩: 节省大量内存，特别适合 Key 具有公共前缀的场景（如 user.1, user.2）。
  • 范围查询: WalkPrefix 操作复杂度仅为 O(K)，与总数据量无关。

2.2 存储层 (Storage Layer)

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

2.3 查询引擎 (Query Engine)

• Early Termination: 支持 LIMIT 下推。一旦扫描满足数量，立即停止 IO 和遍历。
• Lazy Loading: 仅在必要时（如过滤 Value 或返回结果）才从磁盘读取 Value。

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

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

3.1 综合吞吐量 (Throughput)

操作类型	数量	耗时	QPS (Ops/sec)	提升幅度 (vs Hash版)
Insert	100,000	~0.23s	~436,000	9x
Update	10,000	~0.04s	~250,000	2.5x
Insert (Reuse)	5,000	~0.01s	~471,000	25x
Delete	10,000	~0.03s	~382,000	持平

3.2 查询性能 (Query Performance)

查询类型	QPS (Ops/sec)	说明
Point Lookup	~238,000	精确查询 key="..."。受限于 Radix 深度，略低于 Hash 但依然极快。
Meta Query	~80,000	前缀查询 key like "prefix*"。利用 Radix Tree 极速定位子树。提升 33 倍。
Limit Query	~290,000	分页查询 LIMIT 10。利用 Early Termination 立即返回。
Full Query	~26	全表扫描 value like "*..."。受限于单线程 IO 扫描 (优化空间所在)。

4. 使用说明

4.1 初始化

import "db"

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

4.2 查询与分页

// 极速前缀分页查询
// 引擎会自动识别 "user.*" 前缀，在 Radix Tree 上定位，并只扫描前 20 条
results, _ := e.Query(`key like "user.*" LIMIT 20`)

5. 优化路线图 (Roadmap)

目前的版本在 Key 操作上已经达到了极致。下一步的优化方向：

1. 并发 Radix Tree: 引入 ART (Adaptive Radix Tree) 或实现并发安全的 Radix Tree (CoW 或 Fine-grained locks) 以支持更高的并发读。
2. 全文索引集成: 将 FullTextIndex 深度集成到 Query 流程中，解决 value like 查询慢的问题。