Golang实现bitcask论文

2025-03-08

为什么需要存储引擎

业务开发中有很多通用数据库系统，比如MySQL、PostgreSQL。这些数据库的功能比较强大，但是资源占用较高，不适用于嵌入式的场景。在设备开发场景中，日志、缓存等模块通常有频繁的小K-V写入，传统数据库无法保证高性能。

业界内较为知名的解决方案是Goole开源的LevelDB项目。LevelDB是一个嵌入式的数据库，可以直接嵌入在程序中，无需像MySQL那样需要服务器。常用的Chrome浏览器就使用了LevelDB存储IndexedDB数据。

LevelDB设计如下：

使用LSM树存储，在写多读少的场景下表现优异;
通过内存的布隆过滤器和MemTable，在查找场景下也能取得不错的表现;

Bitcask的思想与LevelDB类型，在此之前需要先介绍LSM树的思想。

B+ Tree & LSM Tree

数据库的数据都是存放在磁盘上，而磁盘的随机读写成本远高于内存。为了最大限度减少磁盘的IO操作，MySQL使用B+树作为底层数据结构，其优点如下:

查询效率高，通过增加每层节点的数量可以降低树的高度，从而减少磁盘IO;
数据存放在叶子节点，由于B+树叶子节点通过链表连接，非常适合数据库的范围查找;
插入和删除时可以自平衡，维持较小的树高和有序结构;

B+树拥有以上有点的同时不可避免引入了插入代价大的问题，极端情况下可能每一次插入都会导致B+树结构的调整，这对于loT之类的系统而言是不可接受的。 LSM(Log-Structured Merge Tree)树通过WAL使得写效率极高，其核心思想是磁盘顺序写效率远高于随机写入：

写入时先写内存(MemTable)，并顺序追加磁盘日志(WAL, Write-Ahead-Lg);
MemTable写满后刷盘为SSTable;
多个SSTable按照策略合并以控制层数和查找代价;

bitcask模型

Entry

当使用Put和Get时，数据都被封装为Entry，Entry的大致内容如下:

+---------+-----------+-----+-----------+--------+------+
|   crc   | keyLength | key | valLength | value  | type |
+---------+-----------+-----+-----------+--------+------+

磁盘文件的结构就是多个Entry的集合:

+---------+-----------+------+-----------+--------+------+
|   crc   | keyLength | key  | valLength | value  | type |
+---------+-----------+------+-----------+--------+------+
| 0x1A2B  |     3     | foo  |     5     | hello  |  01  |
| 0x3C4D  |     4     | test |     3     | yes    |  02  |
| 0x5E6F  |     2     | id   |     4     | 1234   |  03  |
+---------+-----------+------+-----------+--------+------+

Put

在bitcask中，磁盘中写入Entry后会在内存索引中记录key对应的Entry位置，便于查找。这样一次写入操作分为两步:

追加Entry到Log
更新内存索引

Get

Get操作也比较简单，首先查找内存索引，然后根据索引中Entry的位置读取Value即可。

Del

Del操作并不会实际删除数据，而是将一条Del操作的日志追加到日志文件中，随后在内存索引中删除对应key的索引信息。

Merge

日志文件随着以上操作会一直追加，日志文件中可能会有无效数据。Merge的作用就是删除无效的Entry。 Merge时首先会取出原日志文件的所有Entry，遍历后将有效的Entry重新写入新建的MergeFile，再在Merge操作完成后删除原数据文件，是使用MergeFile替换。

可以看出使用LSM树在插入、删除和查询时都只有一次内存索引读写操作和一次磁盘文件顺序写操作，即使在较大的数据规模场景下也可以保证优异的性能。

用到的golang知识

map

map是无序的KV集合，在获取K对应的值时，如果K不存在，返回V类型的默认值。

func main() {
    m := make(map[int]string, 10)
    m[1] = "Hello" // set kv
    v := m[1]      // get v
    fmt.Println(v) // stdout -> Hello
    len := len(m)  // get length
    delete(m, 1)   // delete kv
}

sync.Pool

在高并发程序中，短时间内会创建大量的对象，此时GC的压力会很大，影响程序的性能。sync.Pool用于对象池的管理，通过复用对象减少内存重复分配的开销。

声明对象池

import (
    "sync"
)

type Student struct {
    Name string
}
var pool *sync.Pool
func initPool() {
    pool = &sync.Pool{
        New: func() interface{} {
            return new(Student)
        },
    }
}
func usePool() {
    studentA := pool.Get().(*Student) // Get的返回值是`interface{}`，所以需要转换类型
    studentA.Name = "John"
    pool.Put(studentA) // 使用完后返回给对象池
}

sync.Pool的大小是动态扩容的，高负债时可以自动伸缩，不活跃对象会被自动清理;
sync.Pool本身是多线程安全的，多个goroutine可以并发使用；
sync.Pool在使用时最好在Put前进行Reset，放置读取脏数据；

defer

defer关键字的作用是延迟执行函数，直到当前函数返回，有些类似C++中RAII的思想，是Go中常用的资源回收方式。

func autoClean() {
    buf := bufPool.Get().([]byte)
    defer bufPool.Put(buf)
    if (err != nil) {
        return // auto clean
    }
}

Golang实现

源码在Github

Tags: #Golang #Database