Golang如何实现事务型内存数据库
特性
MossDB是一个纯Golang编写、可嵌入的、键值型内存数据库，包含以下特性
可持久化，类似Redis AOF(Append only Log)
支持事务
支持近实时的TTL(Time to Live), 可以实现毫秒级的过期删除
前缀搜索
Watch接口，可以监听某个键值的内容变化，类似etcd的Watch
多后端存储，目前支持HashMap和RadixTree
命名由来
Moss有苔、苔花的含义，MossDB的名字来源于清代袁牧的一句诗:
苔花如米小，也学牡丹开
MossDB虽小，但五脏俱全，也支持了很多重要功能。另外，巧合的是《流浪地球2》中的超级计算机550W名字就是Moss。
架构
内存数据库虽然使用简单，实现起来却有很多细节，Golang目前也存在不少优秀的开源内存数据库，比如buntdb、go-memdb，在编写MossDB过程中也借鉴了一些它们的特性。
MossDB的架构如图：
自上往下分为：
接口层，提供API接受用户请求
核心层，实现事务、过期删除、Watch等功能
存储层，提供KV的后端存储以及增删改查
持久化层，使用AOL持久化即每次修改操作都会持久化到磁盘Log中
快速开始
MossDB可嵌入到Go程序中，可以通过go get获取
go get github.com/qingwave/mossdb
MossDB提供了易用的API，可以方便地进行数据处理，下面的示例代码展示了如何使用MossDB：
package main
import (
"log"
"github.com/qingwave/mossdb"
)
func main() {
// create db instance
db, err := mossdb.New(&mossdb.Config{})
if err != nil {
log.Fatal(err)
}
// set, get data
db.Set("key1", []byte("val1"))
log.Printf("get key1: %s", db.Get("key1"))
// transaction
db.Tx(func(tx *mossdb.Tx) error {
val1 := tx.Get("key1")
tx.Set("key2", val1)
return nil
})
}更多示例见源码
具体实现
从下往上分别介绍下MossDB如何设计与实现，以及相关的细节。
AOF持久化
AOF源于Redis提供两种持久化技术，另外一种是RDB，AOF是指在每次写操作后，将该操作序列化后追加到文件中，重启时重放文件中的对应操作，从而达到持久化的目的。其实现简单，用在MossDB是一个不错的选择，但需要注意的是AOF缺点同样明显，如果文件较大，每次重启会花费较多时间。
Redis的AOF是一种后写式日志，先写内存直接返回给用户，再写磁盘文件持久化，可以保证其高性能，但如果中途宕机会丢失数据。MossDB中的AOF采用了WAL(预写式日志)实现，先写Log再写内存，用来保证数据不会丢失，从而可以进一步实现事务。
那么采用WAL会不会影响其性能？每次必须等到落盘后才进行其他操作，WAL的每次写入会先写到内核缓冲区，这个调用很快就返回了，内核再将数据落盘。我们也可以使用fsync调用强制内核执行直接将数据写入磁盘。在MossDB中普通写操作之会不会直接调用fsync，事务写中强制开启fsync，从而平衡数据一致性与性能。
WAL的实现引用了tiwall/wal，其中封装了对Log文件的操作，可以支持批量写入。由于WAL是二进制的，必须将数据进行编码，通过varint编码实现，将数据长度插入到数据本体之前，读取时可以读取定长的数据长度，然后按长度读取数据本体。MossDB中数据格式如下：
type Record struct {
Op uint16
KeySize uint32
ValSize uint32
Timestamp uint64
TTL uint64
Key []byte
Val []byte
}对应编码后的二进制格式为:
|------------------------------------------------------------|
| Op | KeySize | ValSize | Timestamp | TTL | Key | Val |
|------------------------------------------------------------|
| 2 | 4 | 4 | 8 | 8 | []byte | []byte |
|------------------------------------------------------------|
使用binary.BigEndian.PutUint16进行编码，解码时通过binary.BigEndian.Uint16，从而依次取得生成完整的数据。
存储引擎
MossDB提供了存储接口，只要实现了此接口都可以作为其后端存储
type Store interface {
Get(key string) ([]byte, bool)
Set(key string, val []byte)
Delete(key string)
Prefix(key string) map[string][]byte
Dump() map[string][]byte
Len() int
}内置提供了HashMap与RadixTree两种方式，HashMap实现简单通过简单封装map可以快速进行查询与插入，但范围搜索性能差。RadixTree即前缀树，查询插入的时间复杂度只与Key的长度相关，而且支持范围搜索，MossDB采用Adaptive Radix Tree可以避免原生的前准树空间浪费。
由于RadixTree的特性，MossDB可以方便的进行前缀搜索，目前支持List与Watch操作。
事务实现
要实现事务必须要保证其ACID特性，MossDB的事务定义如下：
type Tx struct {
db *DB // DB实例
commits []*Record // 对于写操作生成 Record, 用来做持久化
undos []*Record // 对于写操作生成 Undo Record，用于回滚
}MossDB中一次事务的流程主要包含以下几个步骤：
首先加锁，保证其数据一致性
对于写操作，生成Commits和Undo Records，然后写入内存；读操作则直接执行
提交阶段，将Commits持久化到WAL中；若写入失败，则删除已写入数据；成功则设置数据的其他属性(TTL, Watch等)
若中间发生错误，执行回滚操作，将Undo Records的记录执行
事务完成，释放锁
Watch
由于工作中经常使用Kubernetes，对于其Watch接口印象深刻，通过Watch来充当其事件总线，保证其声明式对象的管理。Kubernetes的Watch底层由etcd实现，MossDB也实现了类似的功能。
Watch的定义如下：
type Watcher struct {
mu sync.RWMutex // 锁
watchers map[string]*SubWatcher // watchId与具体Watcher直接的映射
keys map[string]containerx.Set[string] // Watch单个key
ranges *art.Tree // 前缀Watch
queue workqueue.WorkQueue // 工作队列，存放所有事件
stop chan struct{} // 是否中止
}通过工作队列模式，任何写操作都会同步追加到队列中，如果存在单个key的监听者，则通过watchers map获取到对应列表，依次发送事件。对于前缀Watch，我们不可能记录此前缀的所有Key，这里借鉴了etcd，通过RadixTree保存前缀Key，当有新事件时，匹配Key所在的路径，如果有监听者，则进行事件通知。
调用Watch会返回一个Channel，用户只需要监听Channel即可
func Watch(db *mossdb.DB) {
key := "watch-key"
ctx, cancel := context.WithTimeout(context.Background(), 1000*time.Millisecond)
defer cancel()
// start watch key
ch := db.Watch(ctx, key)
log.Printf("start watch key %s", key)
go func() { // 模拟发送event
db.Set(key, mossdb.Val("val1"))
db.Set(key, mossdb.Val("val2"))
db.Delete(key)
time.Sleep(100 * time.Second)
db.Set(key, mossdb.Val("val3"))
}()
for {
select {
case <-ctx.Done():
log.Printf("context done")
return
case resp, ok := <-ch:
if !ok {
log.Printf("watch done")
return
}
log.Printf("receive event: %s, key: %s, new val: %s", resp.Event.Op, resp.Event.Key, resp.Event.Val)
}
}
// Output
// 2023/02/23 09:48:50 start watch key watch-key
// 2023/02/23 09:34:19 receive event: MODIFY, key: watch-key, new val: val1
// 2023/02/23 09:34:19 receive event: MODIFY, key: watch-key, new val: val2
// 2023/02/23 09:34:19 receive event: DELETE, key: watch-key, new val:
// 2023/02/23 09:34:19 context done
}