◄ 上一步目录下一步 ►

0103: Log 存储

Log 只增加，不修改

类似文本形式的“日志”，log 只在文件末尾追加条目，而不会去修改、删除已有的条目。 Log 里的条目，记录了数据库的每次更新操作，比如一个 log 里有4条记录：

	操作	状态
0		{}
1	set k1=x	{k1=x}
2	set k2=y	{k1=x, k2=y}
3	set k1=z	{k1=z, k2=y}
4	del k2	{k1=x}

数据库启动时读取 log，按顺序执行更新操作，得到最终状态 {k1=z}。这样实现了数据库的增量更新。这是为什么要用 log 原因之一，log 还有其他用途会在后面步骤遇到。

你一定会有疑问：log 里旧的记录怎么删除呢？这个问题后续会解决：log 达到一定大小后，会合并到主要数据结构里（LSM-Tree 或 B+Tree）。

Log 记录了每次状态的变化。即使有并发的事务，只要不是分布式系统，状态的变化到了 log 上都可以串行化。所以 log 有同步数据（replication）、恢复到之前状态（undo）等作用。但是 log 是不能无限增长的，所以不能作为主要储存，而是作为辅助功能。 Log 在功能上甚至不是必要的，数据库可以基于带有 log 性质的 copy-on-write 数据结构来实现。

Log 记录

根据上面这个例子，log 里有2种记录：更新、删除。所以 Entry 里增加了一个 flag 来区分。

type Entry struct {
    key     []byte
    val     []byte
    deleted bool
}

对应的序列化格式修改为：

| key 大小 | val 大小 | 是否删除 | key 数据 | val 数据 |
|  4 bytes |  4 bytes |  1 byte  |    ...   |    ...   |

修改这2个函数：

func (ent *Entry) Encode() []byte
func (ent *Entry) Decode(r io.Reader) error

Log 文件读写

struct 定义：

type Log struct {
    FileName string
    fp       *os.File
}

func (log *Log) Open() (err error) {
    log.fp, err = os.OpenFile(log.FileName, os.O_RDWR|os.O_CREATE, 0o644)
    return err
}

func (log *Log) Close() error {
    return log.fp.Close()
}

Log 读写接口：

func (log *Log) Write(ent *Entry) error {
    _, err := log.fp.Write(ent.Encode())
    return err
}

func (log *Log) Read(ent *Entry) (eof bool, err error) {
    err = ent.Decode(log.fp)
    if err == io.EOF {
        return true, nil
    } else if err != nil {
        return false, err
    } else {
        return false, nil
    }
}

数据库启动时，循环调用 Log.Read() 直到文件末尾。之后数据库有更新时，Log.Write() 正好追加到末尾。

Log.Read() 判断是否到了文件末尾，通过 io.EOF（End Of File）。所以 Entry.Decode() 要传递 io.Reader 返回的错误。

读取 log

这个 struct 增加到 KV 里：

type KV struct {
    Log Log
    mem map[string][]byte
}

func (kv *KV) Open() error {
    if err := kv.Log.Open(); err != nil {
        return err
    }
    kv.mem = map[string][]byte{}
    // TODO
}

func (kv *KV) Close() error { return kv.Log.Close() }

实现 KV.Open() 函数，读取 log 到 KV.mem 里。要求：后面的条目覆盖前面的条目。

写入 log

修改 set, del，增加 log 写入：

func (kv *KV) Set(key []byte, val []byte) (updated bool, err error)
func (kv *KV) Del(key []byte) (deleted bool, err error)

进入 db_project/0102 目录。运行测试用例：

go test .

总结

通过 log 把增量更新落到硬盘上。但这个 log 还有一些问题：如果数据库使用中断电了，会有什么后果呢？这是下一步要考虑的问题。

◄ 上一步目录下一步 ►