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

## 5. 使用说明

### 5.1 初始化

```go
import "db"

// 默认模式 (Key Only Index)
e, err := db.NewEngine("./my_data")
if err != nil { panic(err) }
defer e.Close()

// 若需支持 value like 全文检索:
// e, err := db.NewEngine("./my_data", db.WithValueIndex(true))
```

### 5.2 查询示例

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

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