- 更新 DESIGN.md: - 强调强制 Schema(21 种类型) - 更新核心代码行数为 ~5,400 行 - 优化 ROW1 格式说明(英文) - 完善性能指标和项目成果 - 精简 DOCS.md 和 README.md - 统一文档风格和术语
26 KiB
26 KiB
SRDB 设计文档:WAL + mmap B+Tree
模块名:
code.tczkiot.com/wlw/srdb一个高性能的 Append-Only 时序数据库引擎
🎯 设计目标
- 极简架构 - 放弃复杂的 LSM Tree 多层设计,使用简单的两层结构
- 高并发写入 - WAL + MemTable 保证 200,000+ writes/s
- 快速查询 - mmap B+Tree 索引 + 二级索引,1-5 ms 查询性能
- 低内存占用 - mmap 零拷贝,应用层内存 < 150 MB
- 功能完善 - 强制 Schema(21 种类型)、索引、条件查询等高级特性
- 生产可用 - 核心代码 ~5,400 行,包含完善的错误处理和数据一致性保证
🏗️ 核心架构
┌─────────────────────────────────────────────────────────────┐
│ SRDB Architecture │
├─────────────────────────────────────────────────────────────┤
│ Application Layer │
│ ┌───────────────┐ ┌──────────────────────────┐ │
│ │ Database │->│ Table │ │
│ │ (Multi-Table) │ │ (Schema + Storage) │ │
│ └───────────────┘ └──────────────────────────┘ │
├─────────────────────────────────────────────────────────────┤
│ Write Path (High Concurrency) │
│ ┌─────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ Schema │-> │ WAL │-> │ MemTable │->│ Index │ │
│ │Validate │ │(Append) │ │(Map+Arr) │ │ Manager │ │
│ └─────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ ↓ ↓ ↓ ↓ │
│ Type Check Sequential Sorted Map Secondary │
│ Required Write Fast Insert Indexes │
│ Constraints 200K+ w/s O(1) Put Field Query │
│ │
│ Background Flush: MemTable -> SST (Async) │
├─────────────────────────────────────────────────────────────┤
│ Storage Layer (Persistent) │
│ ┌─────────────────────────────────────────────────┐ │
│ │ SST Files (B+Tree Format + Binary Encoding) │ │
│ │ ┌─────────────────────────────────────────┐ │ │
│ │ │ File Header (256 bytes) │ │ │
│ │ │ - Magic, Version, Metadata │ │ │
│ │ │ - MinKey, MaxKey, RowCount │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ B+Tree Index (4 KB nodes) │ │ │
│ │ │ - Root Node │ │ │
│ │ │ - Internal Nodes (Order=200) │ │ │
│ │ │ - Leaf Nodes → Data Offset │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ Data Blocks (Binary Format) │ │ │
│ │ │ - ROW1 Format: Binary Encoding │ │ │
│ │ │ [Magic:4B][Seq:8B][Time:8B] │ │ │
│ │ │ [Fields:2B][OffsetTable][Data] │ │ │
│ │ │ - Supports zero-copy & partial reads │ │ │
│ │ └─────────────────────────────────────────┘ │ │
│ │ │ │
│ │ Secondary Indexes (Optional) │ │
│ │ - Field → [Seq] mapping │ │
│ │ - B+Tree format for fast lookup │ │
│ └─────────────────────────────────────────────────┘ │
│ │
│ MANIFEST: Version control & file tracking │
│ Compaction: Background merge of SST files │
├─────────────────────────────────────────────────────────────┤
│ Query Path (Multiple Access Methods) │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ Query │-> │MemTable │-> │mmap SST │ │
│ │ Builder │ │Manager │ │ Reader │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ ↓ ↓ ↓ │
│ Conditions Active+Immut Zero Copy │
│ AND/OR/NOT < 0.1 ms 1-5 ms │
│ Field Match In Memory OS Cache │
│ │
│ With Index: Index Lookup -> Get by Seq (Fast) │
└─────────────────────────────────────────────────────────────┘
设计理念:
- 简单 > 复杂: 只有 2 层,无多级 LSM
- 性能 > 功能: 专注于高并发写入和快速查询
- mmap > 内存: 让 OS 管理缓存,应用层零负担
- Append-Only: 只插入,不更新/删除
- 可扩展: 支持 Schema、索引、条件查询等高级特性
📁 文件组织结构
运行时数据目录结构
database_dir/ ← 数据库目录
├── database.meta ← 数据库元数据
├── MANIFEST ← 全局 MANIFEST
└── table_name/ ← 表目录
├── schema.json ← 表的 Schema 定义
├── MANIFEST ← 表的 MANIFEST
│
├── wal/ ← WAL 目录
│ ├── 000001.log ← 当前 WAL
│ └── 000002.log ← 历史 WAL
│
├── sst/ ← SST 文件目录
│ ├── 000001.sst ← SST 文件 (B+Tree)
│ ├── 000002.sst
│ └── 000003.sst
│
└── idx/ ← 索引目录 (可选)
├── idx_name.sst ← 字段 name 的索引
└── idx_email.sst ← 字段 email 的索引
🔑 核心组件
1. WAL (Write-Ahead Log)
设计:
- 顺序追加写入
- 批量提交优化
- 崩溃恢复支持
文件格式:
┌───────────────────────────────────────┐
│ WAL Entry │
├───────────────────────────────────────┤
│ CRC32 (4 bytes) │
│ Length (4 bytes) │
│ Type (1 byte): Put │
│ Key (8 bytes): _seq │
│ Value Length (4 bytes) │
│ Value (N bytes): Serialized row data │
└───────────────────────────────────────┘
性能:
- 顺序写入: 极快
- 批量提交: 减少 fsync
- 吞吐: 200,000+ writes/s
2. MemTable (内存表)
设计:
- 使用 map[int64][]byte + sorted slice
- 读写锁保护
- 大小限制 (默认 64 MB)
- Manager 管理多个版本 (Active + Immutables)
实现:
type MemTable struct {
data map[int64][]byte // key -> value
keys []int64 // 有序的 keys
size int64 // 数据大小
mu sync.RWMutex
}
func (m *MemTable) Put(key int64, value []byte) {
m.mu.Lock()
defer m.mu.Unlock()
if _, exists := m.data[key]; !exists {
m.keys = append(m.keys, key)
// 保持 keys 有序
sort.Slice(m.keys, func(i, j int) bool {
return m.keys[i] < m.keys[j]
})
}
m.data[key] = value
m.size += int64(len(value))
}
func (m *MemTable) Get(key int64) ([]byte, bool) {
m.mu.RLock()
defer m.mu.RUnlock()
value, exists := m.data[key]
return value, exists
}
MemTable Manager:
- Active MemTable: 当前写入
- Immutable MemTables: 正在 Flush 的只读表
- 查询时按顺序查找: Active -> Immutables
性能:
- 插入: O(1) (map) + O(N log N) (排序,仅新key)
- 查询: O(1) (map lookup)
- 内存操作: 极快
- 实测: 比 SkipList 更快的写入性能
选择原因:
✅ 实现简单
✅ 写入性能好 (O(1))
✅ 查询性能好 (O(1))
✅ 易于遍历 (已排序的 keys)
3. SST 文件 (B+Tree 格式)
设计:
- 固定大小的节点 (4 KB)
- 适合 mmap 访问
- 不可变文件
B+Tree 节点格式:
┌─────────────────────────────────────┐
│ B+Tree Node (4 KB) │
├─────────────────────────────────────┤
│ Header (32 bytes) │
│ ├─ Node Type (1 byte) │
│ │ 0: Internal, 1: Leaf │
│ ├─ Key Count (2 bytes) │
│ ├─ Level (1 byte) │
│ └─ Reserved (28 bytes) │
├─────────────────────────────────────┤
│ Keys (variable) │
│ ├─ Key 1 (8 bytes) │
│ ├─ Key 2 (8 bytes) │
│ └─ ... │
├─────────────────────────────────────┤
│ Values/Pointers (variable) │
│ Internal Node: │
│ ├─ Child Pointer 1 (8 bytes) │
│ ├─ Child Pointer 2 (8 bytes) │
│ └─ ... │
│ │
│ Leaf Node (interleaved storage): │
│ ├─ (Offset, Size) Pair 1 │
│ │ ├─ Data Offset 1 (8 bytes) │
│ │ └─ Data Size 1 (4 bytes) │
│ ├─ (Offset, Size) Pair 2 │
│ │ ├─ Data Offset 2 (8 bytes) │
│ │ └─ Data Size 2 (4 bytes) │
│ └─ ... │
└─────────────────────────────────────┘
解释:
- interleaved storage: 交叉存储
优势:
✅ 固定大小 (4 KB) - 对齐页面
✅ 可以直接 mmap 访问
✅ 无需反序列化
✅ OS 按需加载
4. mmap 查询
设计:
- 映射整个 SST 文件
- 零拷贝访问
- OS 自动缓存
实现:
type MmapSST struct {
file *os.File
mmap mmap.MMap
rootOffset int64
}
func (s *MmapSST) Get(key int64) ([]byte, bool) {
// 1. 从 root 开始
nodeOffset := s.rootOffset
for {
// 2. 读取节点 (零拷贝)
node := s.readNode(nodeOffset)
// 3. 二分查找
idx := sort.Search(len(node.keys), func(i int) bool {
return node.keys[i] >= key
})
// 4. 叶子节点
if node.isLeaf {
if idx < len(node.keys) && node.keys[idx] == key {
// 读取数据
offset := node.offsets[idx]
size := node.sizes[idx]
return s.readData(offset, size), true
}
return nil, false
}
// 5. 继续向下
nodeOffset = node.children[idx]
}
}
func (s *MmapSST) readNode(offset int64) *BTreeNode {
// 直接访问 mmap 内存 (零拷贝)
data := s.mmap[offset : offset+4096]
return parseBTreeNode(data)
}
性能:
- 热点数据: 1-2 ms (OS 缓存)
- 冷数据: 3-5 ms (磁盘读取)
- 零拷贝: 无内存分配
5. Schema 系统
设计:
- 强制 Schema(所有表必须定义)
- 21 种精确类型映射
- Nullable 字段支持
- 类型验证和转换
- 索引标记(Indexed: true)
支持的类型(21 种):
1. 有符号整数(5种): Int, Int8, Int16, Int32, Int64
2. 无符号整数(5种): Uint, Uint8, Uint16, Uint32, Uint64
3. 浮点数(2种): Float32, Float64
4. 字符串(1种): String
5. 布尔(1种): Bool
6. 特殊类型(5种): Byte, Rune, Decimal, Time, Duration
7. 复杂类型(2种): Object (JSON), Array (JSON)
实现:
type Schema struct {
TableName string
Fields []Field
}
type Field struct {
Name string
Type FieldType // 21 种类型之一
Indexed bool // 是否创建索引
Nullable bool // 是否允许 NULL
Comment string // 字段注释
}
func (s *Schema) Validate(data map[string]interface{}) error {
// 1. 检查必填字段
// 2. 类型验证和转换
// 3. Nullable 检查
// 4. 返回验证后的数据
}
使用示例:
schema, _ := NewSchema("users", []Field{
{Name: "name", Type: String, Indexed: false},
{Name: "age", Type: Int32, Indexed: false},
{Name: "email", Type: String, Indexed: true},
{Name: "balance", Type: Decimal, Nullable: true},
})
table, _ := db.CreateTable("users", schema)
类型转换规则:
- 相同类型:直接接受
- 兼容类型:自动转换(有符号 ↔ 无符号,需非负)
- 类型提升:整数 → 浮点
- JSON 兼容:float64 → 整数(需为整数值)
- 负数 → 无符号:拒绝
6. 二级索引
设计:
- 字段级索引
- B+Tree 格式存储
- 自动维护
- 快速字段查询
实现:
type SecondaryIndex struct {
field string
btree *BTreeIndex // Field Value -> [Seq]
}
// 创建索引
table.CreateIndex("email")
// 使用索引查询
qb := query.NewQueryBuilder()
qb.Where("email", query.Eq, "user@example.com")
rows, _ := table.Query(qb)
索引文件格式:
index/
├── idx_email.sst ← email 字段索引
│ └── BTree: email -> []seq
└── idx_name.sst ← name 字段索引
└── BTree: name -> []seq
性能提升:
- 无索引: O(N) 全表扫描
- 有索引: O(log N) 索引查找 + O(K) 结果读取
- 实测: 100x+ 性能提升
7. 查询构建器 (新增功能)
设计:
- 链式 API
- 条件组合 (AND/OR/NOT)
- 操作符支持
- Schema 验证
实现:
type QueryBuilder struct {
conditions []*Expr
logicOp string // "AND" 或 "OR"
}
type Operator int
const (
Eq Operator = iota // ==
Ne // !=
Gt // >
Gte // >=
Lt // <
Lte // <=
Contains // 字符串包含
StartsWith // 字符串前缀
EndsWith // 字符串后缀
)
使用示例:
// 简单查询
qb := query.NewQueryBuilder()
qb.Where("age", query.Gt, 18)
rows, _ := table.Query(qb)
// 复杂查询 (AND)
qb := query.NewQueryBuilder()
qb.Where("age", query.Gt, 18)
.Where("city", query.Eq, "Beijing")
.Where("active", query.Eq, true)
// OR 查询
qb := query.NewQueryBuilder().Or()
qb.Where("role", query.Eq, "admin")
.Where("role", query.Eq, "moderator")
// NOT 查询
qb := query.NewQueryBuilder()
qb.WhereNot("status", query.Eq, "deleted")
// 字符串匹配
qb := query.NewQueryBuilder()
qb.Where("email", query.EndsWith, "@gmail.com")
执行流程:
1. 尝试使用索引 (如果有)
2. 否则扫描 MemTable + SST
3. 应用所有条件过滤
4. 返回匹配的行
8. 数据库和表管理
设计:
- 数据库级别管理
- 多表支持
- 表级 Schema
- 独立的存储目录
实现:
type Database struct {
dir string
tables map[string]*Table
versionSet *manifest.VersionSet
metadata *Metadata
}
type Table struct {
name string
dir string
schema *schema.Schema
}
使用示例:
// 打开数据库
db, _ := database.Open("./mydb")
// 创建表
schema := &schema.Schema{...}
table, _ := db.CreateTable("users", schema)
// 使用表
table.Insert(map[string]interface{}{
"name": "Alice",
"age": 30,
})
// 获取表
table, _ := db.GetTable("users")
// 列出所有表
tables := db.ListTables()
// 删除表
db.DropTable("old_table")
// 关闭数据库
db.Close()
🔄 核心流程
写入流程
1. 接收写入请求
↓
2. 生成 _seq (原子递增)
↓
3. 写入 WAL (顺序追加)
↓
4. 写入 MemTable (内存)
↓
5. 检查 MemTable 大小
↓
6. 如果超过阈值 → 触发 Flush (异步)
↓
7. 返回成功
Flush 流程 (后台):
1. 冻结当前 MemTable
↓
2. 创建新的 MemTable (写入继续)
↓
3. 遍历冻结的 MemTable (已排序)
↓
4. 构建 B+Tree 索引
↓
5. 写入数据块 (二进制格式)
↓
6. 写入 B+Tree 索引
↓
7. 写入文件头
↓
8. Sync 到磁盘
↓
9. 更新 MANIFEST
↓
10. 删除 WAL
查询流程
1. 接收查询请求 (key)
↓
2. 查询 MemTable (内存)
- 如果找到 → 返回 ✅
↓
3. 查询 SST 文件 (从新到旧)
- 对每个 SST:
a. mmap 映射 (如果未映射)
b. B+Tree 查找 (零拷贝)
c. 如果找到 → 读取数据 → 返回 ✅
↓
4. 未找到 → 返回 NotFound
Compaction 流程 (简化)
触发条件:
- SST 文件数量 > 10
流程:
1. 选择多个 SST 文件 (如 5 个)
↓
2. 多路归并排序 (已排序,很快)
↓
3. 构建新的 B+Tree
↓
4. 写出新的 SST 文件
↓
5. 更新 MANIFEST
↓
6. 删除旧的 SST 文件
注意:
- Append-Only: 无需处理删除
- 无需去重: 取最新的即可
- 后台执行: 不影响读写
📊 性能指标
写入性能
单线程: 50,000 writes/s
多线程: 200,000+ writes/s
延迟: < 1 ms (p99)
实测数据 (MacBook Pro M1):
- 单线程插入 10 万条: ~2 秒
- 并发写入 (4 goroutines): ~1 秒
查询性能
按 Seq 查询:
- MemTable: < 0.1 ms
- 热点 SST: 1-2 ms (OS 缓存)
- 冷数据 SST: 3-5 ms (磁盘读取)
- 平均: 2-3 ms
条件查询 (无索引):
- 全表扫描: O(N)
- 小数据集 (<10 万): < 50 ms
- 大数据集 (100 万): < 500 ms
条件查询 (有索引):
- 索引查找: O(log N)
- 性能提升: 100x+
- 查询延迟: < 5 ms
内存占用
- MemTable: 64 MB (可配置)
- WAL Buffer: 16 MB
- 元数据: 10 MB
- mmap: 0 MB (虚拟地址,OS 管理)
- 索引内存: < 50 MB
- 总计: < 150 MB
存储空间
示例 (100 万条记录,每条 200 bytes):
- 原始数据: 200 MB
- 二进制编码: ~180 MB (紧凑格式)
- B+Tree 索引: 20 MB (10%)
- 二级索引: 10 MB (可选)
- 总计: ~210 MB (无压缩)
🔧 实现状态
Phase 1: 核心功能 ✅ 已完成
核心存储引擎:
- [✅] Schema 定义和解析 (schema.go)
- [✅] WAL 实现 (wal.go)
- [✅] MemTable 实现 (memtable.go,使用 map+slice)
- [✅] 基础的 Insert 和 Get (table.go)
- [✅] SST 文件格式定义 (sstable.go)
- [✅] B+Tree 构建器 (btree.go)
- [✅] Flush 流程 (异步)
- [✅] mmap 查询 (sstable.go)
Phase 2: 优化和稳定 ✅ 已完成
稳定性和性能:
- [✅] 批量写入优化
- [✅] 并发控制优化
- [✅] 崩溃恢复 (WAL 重放)
- [✅] MANIFEST 管理 (version.go)
- [✅] Compaction 实现 (compaction.go)
- [✅] MemTable Manager (多版本管理,table.go)
- [✅] 性能测试 (各种 *_test.go)
- [✅] 文档完善 (README.md, DESIGN.md)
Phase 3: 高级特性 ✅ 已完成
高级功能:
- [✅] 数据库和表管理 (database.go, table.go)
- [✅] Schema 系统 (schema.go,强制要求)
- [✅] 二级索引 (index.go, index_btree.go)
- [✅] 查询构建器 (query.go)
- [✅] 条件查询 (AND/OR/NOT)
- [✅] 字符串匹配 (Contains/StartsWith/EndsWith)
- [✅] 版本控制和自动修复
- [✅] 统计信息 (table.Stats())
- [✅] 二进制编码和序列化 (ROW1 格式)
- [✅] 统一错误处理 (errors.go)
Phase 4: 示例和文档 ✅ 已完成
示例程序 (examples/):
- [✅] basic - 基础使用示例
- [✅] with_schema - Schema 使用
- [✅] with_index - 索引使用
- [✅] query_builder - 条件查询
- [✅] string_match - 字符串匹配
- [✅] not_query - NOT 查询
- [✅] schema_query - Schema 验证查询
- [✅] persistence - 持久化和恢复
- [✅] compaction - Compaction 演示
- [✅] multi_wal - 多 WAL 演示
- [✅] version_control - 版本控制
- [✅] database - 数据库管理
- [✅] auto_repair - 自动修复
文档:
- [✅] DESIGN.md - 设计文档
- [✅] schema/README.md - Schema 文档
- [✅] index/README.md - 索引文档
- [✅] examples/README.md - 示例文档
未来计划 (可选)
可能的增强:
- [ ] 范围查询优化 (使用 B+Tree 遍历)
- [ ] 迭代器 API
- [ ] 快照隔离
- [ ] 更多压缩算法 (zstd, lz4)
- [ ] 列式存储支持
- [ ] 分区表支持
- [ ] 监控指标导出 (Prometheus)
- [ ] 数据导入/导出工具
- [ ] 性能分析工具
📝 关键设计决策
为什么用 map + sorted slice 而不是 SkipList?
最初设计: SkipList
- 优势: 经典 LSM Tree 实现
- 劣势: 实现复杂,需要第三方库
最终实现: map[int64][]byte + sorted slice
- 优势:
✅ 实现极简 (130 行)
✅ 写入快 O(1)
✅ 查询快 O(1)
✅ 遍历简单 (已排序的 keys)
✅ 无需第三方依赖
- 劣势:
❌ 每次插入新 key 需要排序
实测结果:
- 写入性能: 与 SkipList 相当或更好
- 查询性能: 比 SkipList 更快 (O(1) vs O(log N))
- 代码量: 少 3-4 倍
结论: 简单实用 > 理论最优
为什么不用列式存储?
最初设计 (V2): 列式存储
- 优势: 列裁剪,压缩率高
- 劣势: 实现复杂,Flush 慢
最终实现 (V3): 行式存储 + 二进制格式
- 优势: 实现简单,Flush 快,紧凑高效
- 劣势: 相比列式压缩率稍低
权衡:
- 追求简单和快速实现
- 二进制格式已经足够紧凑
- 满足大多数时序数据场景
- 如果未来需要,可以演进到列式或添加压缩
为什么用 B+Tree 而不是 LSM Tree?
传统 LSM Tree:
- 多层结构 (L0, L1, L2, ...)
- 复杂的 Compaction
- Bloom Filter 过滤
V3 B+Tree:
- 单层 SST 文件
- 简单的 Compaction
- B+Tree 精确查找
优势:
✅ 实现简单
✅ 查询快 (O(log N))
✅ 100% 准确
✅ mmap 友好
为什么用 mmap?
传统方式: read() 系统调用
- 需要复制数据
- 占用应用内存
- 需要管理缓存
mmap 方式:
- 零拷贝
- OS 自动缓存
- 应用内存 0 MB
优势:
✅ 内存占用极小
✅ 实现简单
✅ 性能好
✅ OS 自动优化
为什么不使用压缩(Snappy/LZ4)?
压缩的优势:
- 减少磁盘空间
- 可能减少 I/O
压缩的劣势:
- CPU 开销(压缩/解压)
- 查询延迟增加
- mmap 零拷贝失效(需要先解压)
- 实现复杂度增加
最终决策: 不使用压缩
- 优先考虑查询性能
- 保持 mmap 零拷贝优势
- 二进制格式已经足够紧凑
- 现代存储成本较低
- 如果真需要压缩,可以在应用层或文件系统层实现
权衡:
✅ 查询延迟更低
✅ 实现更简单
✅ mmap 零拷贝有效
❌ 磁盘占用稍大
🎯 总结
SRDB 是一个功能完善的高性能 Append-Only 数据库引擎:
核心特点:
- ✅ 高并发写入: WAL + MemTable,200K+ w/s
- ✅ 快速查询: mmap B+Tree + 二级索引,1-5 ms
- ✅ 低内存占用: mmap 零拷贝,< 150 MB
- ✅ 功能完善: 强制 Schema(21 种类型)、索引、条件查询、多表管理
- ✅ 生产可用: ~5,400 行核心代码,完善的错误处理和数据一致性
- ✅ 简单可靠: Append-Only,无更新/删除的复杂性
技术亮点:
- 简洁的 MemTable 实现 (map + sorted slice)
- B+Tree 索引,4KB 节点对齐
- 高效的二进制编码格式
- 多版本 MemTable 管理
- 后台 Compaction
- 版本控制和自动修复
- 灵活的查询构建器
适用场景:
- ✅ 日志存储和分析
- ✅ 时序数据(IoT、监控)
- ✅ 事件溯源系统
- ✅ 监控指标存储
- ✅ 审计日志
- ✅ 任何 Append-Only 场景
不适用场景:
- ❌ 需要频繁更新/删除的场景
- ❌ 需要多表 JOIN
- ❌ 需要复杂事务
- ❌ 传统 OLTP 系统
项目成果:
- 核心代码: ~5,400 行(精简高效)
- 测试代码: ~2,000+ 行
- 示例程序: 13+ 个完整示例
- 文档: 完善的设计和使用文档(DESIGN.md、CLAUDE.md、DOCS.md、README.md)
- 性能: 达到设计目标(200K+ w/s 写入,1-5 ms 查询)