基于LSM的Key-Value数据库实现WAL篇

  上篇文章简单的实现了基于LSM数据库的初步版本，在该版本中如数据写入到内存表后但还未持久化到SSTable排序字符串表，此时正好程序崩溃，内存表中暂未持久化的数据将会丢失。

引入WAL

  为了解决上述问题，将引入数据库中常用于解决类似问题的方法：WAL（Write Ahead Log）预写式日志——在计算机科学中，WAL（预写式日志）是数据库系统提供原子性和持久性的一系列技术；也就是说WAL用于保证数据操作的原子性和持久性；
  不同组件、数据库所使用的WAL实现也有所差异，MySQL、Sqlite、Postgresql、Etcd、Hbase、Zookeeper等都有自己的WAL机制实现；

  在MySQL中是通过Redo、Undo日志实现WAL，当MySQL崩溃后重启时，可以通过Redo重做日志对尚未持久化的操作进行Redo，Undo为撤销操作，MySQL崩溃后可时系统恢复一致的状态；
  在etcd中数据目录下有子目录：wal与snap，两个目录都是WAL机制所产生的；
  1、wal目录存放的数据是记录整个数据库变化过程，数据修改前都需先写WAL文件；
  2、Snap目录存放的是当etcd的wal文件过多是所生成的数据快照文件；

LSMDB的WAL机制实现

一、数据写入

  写入数据时先往WAL文件写入再将数据写入内存表，当内存表数据达到某个阈值进行数据持久化后，将WAL文件清空，此WAL只存储尚未持久化的数据；代码如下：

   /**
设置键值
  */
func (l *LSMStore) Set(key string, value string) {
    var cmd = &SetCommand{Command{1}, key, value}
    //写入wal
    writer := bufio.NewWriter(l.walFile)
    cmdBytes, _ := json2.Marshal(cmd)
    cmdLen, _ := IntToBytes(len(cmdBytes), 4)
    writer.Write(cmdLen)
    writer.Write(cmdBytes)
    err := writer.Flush()
    if err != nil {
        return
    }
    //写入内存表
    l.memoryTable.Put(key, cmd)
    if l.memoryTable.Size() > storeThreshold {
        l.switchTable()
        l.toSSTable()
    }
}

  与之前的区别只在于先写wal文件再写内存表，在switchTable方法中切换内存表的同时切换新旧WAL文件，用于保证与持久化内存表机制是一致的。持久化删除上一步所切换出来的WAL文件；

二、数据恢复

  程序每次启动时都会检查是否有WAL文件存在，如存在WAL则说明程序上一次时异常关闭退出，此时将加载WAL文件，并将WAL数据还原到内存表中；
在还原数据到内存表时还需检查内存表数据是否达到预设的阈值，超过则将其写入到持久化磁盘文件当中；

  上次留下的四大坑，此处填了一个坑，还有三大坑待解决：
  1、索引问题
  2、SSTable合并问题
  3、单机版本问题；