# RaftDB 存储引擎文档

RaftDB 内置了一个专为 Raft 状态机设计的高性能、线程安全的嵌入式键值（KV）存储引擎。它采用了 **扁平有序数组 (Flat Sorted Array)** 作为核心内存索引，结合 **倒排索引 (Inverted Index)** 支持全文检索，并使用 **追加写日志 (Append-Only Log)** 保证数据的持久化。

## 1. 核心特性

*   **极致性能 (High Performance)**:
    *   **内存索引**: 使用基于有序数组的二分查找，读取性能极高，无指针开销。
    *   **追加写入**: 所有写操作（Put/Delete）均追加到文件末尾，充分利用磁盘顺序写带宽。
*   **高级查询能力 (Advanced Querying)**:
    *   **前缀扫描**: 得益于有序索引，支持高效的 `key like "prefix*"` 前缀范围扫描。
    *   **全文检索**: 内置倒排索引，支持 `value like "*token*"` 的模糊查询，无需全表扫描。
    *   **SQL-Like 语法**: 支持 `LIMIT`, `OFFSET` 以及复杂的组合过滤条件（例如 `key="k1" AND value like "v*"`）。
*   **数据安全与一致性 (Safety & Consistency)**:
    *   **CRC32 校验**: 每条记录都包含 CRC32 校验和，防止磁盘静默错误导致的数据损坏。
    *   **快照隔离**: 支持生成全量的一致性快照，用于 Raft 日志压缩。

## 2. 架构设计

### 2.1 核心索引：扁平有序数组 (Memory - Primary Index)

不同于传统的 B-Tree 或 Hash Map，本引擎采用了 **Flat Sorted Array** 结构：

*   **数据结构**:
    *   `keyBuf`: 一个巨大的单一 `[]byte` 缓冲，紧凑存储所有 Key 的字符串数据。
    *   `items`: 一个切片，存储轻量级的元数据结构（包含 Key 的偏移量、长度，以及 Value 在磁盘上的偏移量、CommitIndex）。
*   **优势**:
    *   **极度紧凑**: 极大地减少了内存碎片和每个 Key 的额外开销。
    *   **缓存友好**: 连续的内存布局使得 CPU 缓存命中率极高。
    *   **GC 友好**: 几乎不产生指针，大幅降低了 Go GC 的扫描压力。

### 2.2 辅助索引：全文倒排索引 (Memory - Secondary Index)

为了支持 `value like` 查询，引擎维护了一个倒排索引：
*   **映射关系**: Token (词) -> Key Set (包含该词的 Key 集合)。
*   **分词策略**: 简单的按非字母数字字符分割。
*   **查询优化**: 当查询包含 `value like` 时，查询优化器会自动通过倒排索引筛选 Key，避免昂贵的全表 Value 读取。

### 2.3 存储层 (Disk Storage)

*   **Append-Only Log**: 数据存储在 `values.data` 文件中。
    *   **写入 (Put)**: 追加 `[Header][Key][Value]`。
    *   **删除 (Delete)**: 追加一个墓碑（Tombstone）记录。
*   **元数据 (Metadata)**: `meta.state` 文件独立存储 `LastCommitIndex`，允许系统快速启动而无需重放整个日志。
*   **缓存 (Caching)**: 内置简单的 LRU 策略缓存，缓存最近读取的 Value，减少热点数据的磁盘 IO。

## 3. 一致性与持久化

### 3.1 持久性 (Durability)
*   **Sync 机制**: 引擎提供 `Sync()` 方法，调用系统调用 `fsync` 强制将 OS 页缓存刷入磁盘。
*   **Raft 集成**: Raft 在执行快照（Snapshot）前会强制调用 `Sync()`，确保在删除 Raft Log 之前，数据已经物理持久化。

### 3.2 数据完整性 (Integrity)
*   **校验和**: 每条记录写入时计算 CRC32，读取时验证。
*   **故障恢复**: 启动扫描时，如果发现文件尾部有损坏或写入不完整的记录（常见于断电崩溃），引擎会自动截断尾部脏数据，保证数据库状态的一致性。

### 3.3 快照与恢复 (Snapshot & Restore)
这是 Raft Log Compaction 的核心机制：
*   **Snapshot (快照)**: 锁定内存索引，将当前所有有效的 Key-Value 对序列化为一个紧凑的二进制流。这个流代表了某一时刻（CommitIndex）的完整状态机状态。
*   **Restore (恢复)**:
    1.  关闭当前数据库。
    2.  **Truncate (清空)** 数据文件。
    3.  从快照流中重建数据文件和内存索引。
    4.  强制刷盘。
    此过程通常用于落后太多的 Follower 节点快速追赶 Leader。

## 4. 查询语言 (Query Language)

引擎支持一种简化的 SQL 风格查询语法，用于调试和数据检查：

```sql
-- 精确查找 (Point Lookup)
key = "user:1001"

-- 前缀范围查询 (Prefix Search)
key like "user:*"

-- 全文模糊查询 (Full-Text Search, 需要开启 ValueIndex)
value like "error"

-- 组合过滤 (Complex Filtering)
key like "log:*" AND value like "*critical*"

-- 分页 (Pagination)
key like "user:*" LIMIT 10 OFFSET 20

-- 基于 Raft Index 过滤
CommitIndex > 1000
```

## 5. 配置说明

```go
// 初始化引擎时可以配置选项
// 例如：开启全文索引（会消耗更多内存）
engine, err := db.NewEngine(path, db.WithValueIndex(true))
```

## 6. 性能特征

*   **写入**: **O(1)** 磁盘追加 + **O(N)** 内存插入（数组移动）。
    *   *注*: 由于使用有序数组，插入涉及内存移动，因此该引擎更适合**读多写少**或**批量写入**的场景。
*   **读取**: **O(log N)** 内存二分查找 + **1次** 磁盘 Seek。
*   **扫描**: **O(log N)** 定位起点 + **O(M)** 顺序扫描 M 个元素。
*   **全文搜索**: **O(1)** 倒排索引查找 + **O(K)** 结果集过滤。

## 7. 局限性

*   **内存限制**: 虽然 Value 存储在磁盘，但所有 Key 和索引元数据必须能放入内存。
*   **空间回收**: 由于采用 Append-Only 模式，删除操作不会立即释放磁盘空间。空间回收依赖于 Raft 的 Snapshot/Restore 机制（Restore 会重写数据文件，从而清理垃圾数据）。