BCDB

基于bitcask的持久化键值存储数据库

一个用 Go 语言从零实现的轻量级 KV 存储引擎，适合学习数据库内部原理

---

简介

BCDB 是一个持久化键值存储数据库。本项目展示了如何从零开始实现一个具备完整功能的 KV 存储引擎，包含以下核心特性：

• 持久化存储：数据写入后可跨程序启动恢复
• 高效索引：支持 BTree、ART（自适应基数树）和 B+Tree 索引
• 批量事务：支持原子性的批量写入操作
• 数据合并：自动清理过期数据，回收存储空间
• Redis 兼容：提供 Redis 协议兼容的服务端
• HTTP API：提供 HTTP 接口方便访问

本项目适合用于学习数据库内部原理，不推荐用于生产环境。

---

功能特性

功能模块	说明
数据持久化	基于 WAL（写前日志）的持久化机制，数据不丢失
索引结构	支持 BTree（度=32）、ART 自适应基数树、B+Tree 持久化索引
批量操作	支持事务性的批量写入，原子性保证
数据合并	多文件合并清理过期数据，自动回收空间
并发控制	读写锁保护，支持高并发读写
数据迭代	支持前缀过滤、正反向遍历
Redis 协议	兼容部分 Redis 命令（SET/GET）
HTTP 接口	提供 RESTful API 访问数据库

---

快速开始

安装

# 克隆项目
git clone https://github.com/Ailoc/bcdb.git
cd bcdb

# 下载依赖
go mod download

基本使用

package main

import (
    "bcdb"
    "fmt"
)

func main() {
    // 1. 打开数据库
    opts := bcdb.DefaultOptions
    opts.DirPath = "./data"  // 数据存储目录
    db, err := bcdb.Open(opts)
    if err != nil {
        panic(err)
    }
    defer db.Close()

    // 2. 写入数据
    err = db.Put([]byte("name"), []byte("bcdb"))
    if err != nil {
        panic(err)
    }

    // 3. 读取数据
    val, err := db.Get([]byte("name"))
    if err != nil {
        panic(err)
    }
    fmt.Println(string(val)) // 输出: bcdb

    // 4. 删除数据
    err = db.Delete([]byte("name"))
    if err != nil {
        panic(err)
    }
}

运行示例

# 运行基本示例
go run examples/use.go

# 启动 Redis 兼容服务（监听 127.0.0.1:6380）
go run redis/cmd/server.go

# 启动 HTTP 服务（监听 :8888）
go run http/main.go

Redis 客户端测试

# 使用 redis-cli 连接
redis-cli -p 6380

# 执行命令
127.0.0.1:6380> SET hello world
OK
127.0.0.1:6380> GET hello
"world"

---

核心实现

架构设计

BCDB 采用经典的 LSM 树分层架构：

┌─────────────────────────────────────────────────────┐
│                    内存索引层                        │
│  ┌─────────┐  ┌─────────┐  ┌─────────┐              │
│  │  BTree  │  │   ART   │  │ B+Tree  │  Key→Pos    │
│  └─────────┘  └─────────┘  └─────────┘              │
└─────────────────────────────────────────────────────┘
                         ↓ 查询
┌─────────────────────────────────────────────────────┐
│                    磁盘文件层                        │
│  ┌────────────┐         ┌────────────┐              │
│  │ ActiveFile │  ────→  │ OlderFiles │              │
│  │ (可写)     │         │ (只读)     │              │
│  └────────────┘         └────────────┘              │
└─────────────────────────────────────────────────────┘

写入流程

1. 创建 LogRecord（包含 CRC 校验）
        ↓
2. 编码为二进制格式
        ↓
3. 追加写入到活跃数据文件（顺序 I/O）
        ↓
4. 更新内存索引（Key → {Fid, Offset, Size}）
        ↓
5. 可选：同步到磁盘

读取流程

1. 查询内存索引获取数据位置（O(log n)）
        ↓
2. 根据 Fid 定位到具体数据文件
        ↓
3. 根据 Offset 读取 LogRecord
        ↓
4. 解码并验证 CRC 校验和
        ↓
5. 返回 Value

数据编码格式

每个日志记录在磁盘上按以下格式编码：

+--------+----------+------------+-------------+------+------+
| CRC(4) | Type(1)  | KeySize(*) | ValueSize(*) | Key  | Value|
+--------+----------+------------+-------------+------+------+

• * 表示变长整数（varint）编码，小整数占用更少字节
• CRC 使用 IEEE 标准多项式，覆盖 Type 之后的所有数据

---

API 文档

数据库选项

type Options struct {
    DirPath         string          // 数据文件存储路径
    MaxFileSize     int64           // 单个数据文件最大大小（默认 256MB）
    SyncWrite       bool            // 是否每次写入都同步到磁盘
    BytesPerSync    uint            // 累积多少字节后同步一次
    IndexType       index.IndexType // 索引类型（BTREE/ART/BPTree）
    MMapStartup     bool            // 启动时是否使用内存映射
    DataFileMergeRatio float32      // 触发合并的回收比例
}

基本操作

// 打开数据库
func Open(options Options) (*DB, error)

// 写入键值对
func (db *DB) Put(key, value []byte) error

// 读取值
func (db *DB) Get(key []byte) ([]byte, error)

// 删除键
func (db *DB) Delete(key []byte) error

// 关闭数据库
func (db *DB) Close() error

批量操作

// 创建批量操作
func (db *DB) NewWriteBatch(opts WriteBatchOptions) *WriteBatch

// 添加写入
func (wb *WriteBatch) Put(key, value []byte) error

// 添加删除
func (wb *WriteBatch) Delete(key []byte) error

// 提交批量操作（原子性）
func (wb *WriteBatch) Commit() error

迭代器

// 创建迭代器
func (db *DB) NewIterator(opts IteratorOptions) *Iterator

// 迭代器操作
func (it *Iterator) Seek(key []byte)  // 定位到指定 key
func (it *Iterator) Next()            // 移动到下一个
func (it *Iterator) Valid() bool      // 检查是否有效
func (it *Iterator) Key() []byte      // 获取当前 key
func (it *Iterator) Value() []byte    // 获取当前 value

---

项目结构

bcdb/
├── data/           # 数据文件管理
│   ├── data_file.go    # 数据文件读写
│   └── log_record.go   # 日志记录编解码
├── index/          # 索引实现
│   ├── index.go        # 索引接口定义
│   ├── btree.go        # BTree 索引
│   ├── art.go          # ART 自适应基数树
│   └── bptree.go       # B+Tree 持久化索引
├── fio/            # 文件 IO 抽象
│   ├── io_manager.go   # IO 管理器接口
│   ├── file_io.go      # 标准 IO 实现
│   └── mmap.go         # 内存映射 IO
├── redis/          # Redis 协议兼容
│   ├── types.go        # 数据结构实现
│   ├── meta.go         # 元数据编码
│   └── cmd/            # 命令处理
├── http/           # HTTP API
│   └── main.go         # HTTP 服务
├── utils/          # 工具函数
│   ├── file.go         # 文件操作
│   └── floattobytes.go # 浮点数转换
├── batch.go        # 批量操作
├── iterator.go     # 迭代器
├── merge.go        # 数据合并
├── db.go           # 数据库核心
└── examples/       # 使用示例

---

性能特点

操作	时间复杂度	说明
Put	O(log n)	n 为索引中 key 的数量
Get	O(log n)	需要查询索引 + 一次磁盘读取
Delete	O(log n)	逻辑删除，写入墓碑记录
Iterator	O(1)	按序遍历，每次 O(1)

---

许可证

本项目采用 MIT 许可证 - 详见 LICENSE 文件

---

参考资料

• LSM Trees - Google Tech Talk
• Bitcask - Basho Technologies
• LevelDB - Google

---

如果这个项目对你有帮助，请给个 ⭐️ Star