# 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 查询性能。 |

## 6. 快照与恢复 (Snapshot & Restore)

### 6.1 设计理念
本数据库引擎本身被设计为一个**实时的持久化状态机**。
*   **实时快照**: 数据库文件 (`values.data`) 加上内存索引，随时代表了某个 `LastCommitIndex` 处的一致性快照。
*   **日志无关性**: Raft 日志可以安全地被压缩或删除，只要数据库中已经持久化了对应的 `CommitIndex`。
*   **增量同步**: 正常的同步流程是 Raft 异步地将日志 Apply 到数据库。
*   **全量同步**: 当新节点加入或落后太多（日志已被清理）时，通过 `Snapshot` 接口生成全量数据镜像。

### 6.2 Snapshot 机制
```go
// 生成全量快照二进制流
data, err := e.Snapshot()
```
*   **过程**: 锁定内存索引，并发遍历所有 Key，从磁盘或缓存读取 Value，序列化为紧凑的二进制流。
*   **格式**: `[Count U64] + [Record...]`
    *   Record: `[KeyLen U16][Key][ValLen U32][Value][CommitIndex U64]`

### 6.3 Restore 机制
```go
// 从快照恢复状态
err := e.Restore(data)
```
*   **过程**:
    1.  **Stop-the-World**: 锁定写入，关闭当前存储文件。
    2.  **Truncate**: **直接清空**当前数据文件 (`values.data`) 和元数据文件 (`meta.state`)。
    3.  **Rebuild**: 按照快照流顺序，重新生成新的 Append-Only Log 文件，并重建内存索引。
    4.  **Sync**: 强制刷盘，更新 `LastCommitIndex` 到最新状态。
*   **场景**: 仅在节点数据严重滞后（Raft Log 已被截断）或数据损坏时触发。

### 6.4 容灾与安全性
*   **独立元数据**: 引入 `meta.state` 文件专门记录 `LastCommitIndex`，不再依赖全盘扫描，实现**秒级重启**。
*   **幂等性写入**: 内部维护 `LastCommitIndex`，自动忽略已 Apply 的 Raft Log，防止重放攻击或重复写入。
*   **Crash Recovery**:
    *   **Meta 优先**: 启动时读取 `meta.state`。
    *   **Scan 兜底**: 若 Meta 损坏，自动扫描数据文件尾部修正 `LastCommitIndex`。
    *   **Truncate 保护**: 扫描过程中若发现 CRC 错误或截断，自动丢弃尾部脏数据，保证一致性。