关于数据库:从零实现一个-kv-存储引擎

写这篇文章的目标，是为了帮忙更多的人了解 rosedb，我会从零开始实现一个简略的蕴含 PUT、GET、DELETE 操作的 k-v 存储引擎，你能够将其看做是一个繁难版本的 rosedb，就叫它 minidb 吧（mini 版本的 rosedb）。

无论你是 Go 语言初学者，还是想进阶 Go 语言，或者是对 k-v 存储感兴趣，都能够尝试本人入手实现一下，我置信肯定会对你帮忙很大的。

说到存储，其实解决的一个外围问题就是，怎么存放数据，怎么取出数据。在计算机的世界里，这个问题会更加的多样化。

计算机当中有内存和磁盘，内存是易失性的，掉电之后存储的数据全副失落，所以，如果想要零碎解体再重启之后仍然失常应用，就不得不将数据存储在非易失性介质当中，最常见的便是磁盘。

所以，针对一个单机版的 k-v，咱们须要设计数据在内存中应该怎么寄存，在磁盘中应该怎么寄存。

当然，曾经有很多优良的前辈们去探索过了，并且曾经有了经典的总结，次要将数据存储的模型分为了两类：B+ 树和 LSM 树。

本文的重点不是讲这两种模型，所以只做简略介绍。

B+ 树

B+ 树由二叉查找树演变而来，通过减少每层节点的数量，来升高树的高度，适配磁盘的页，尽量减少磁盘 IO 操作。

B+ 树查问性能比较稳定，在写入或更新时，会查找并定位到磁盘中的地位并进行原地操作，留神这里是随机 IO，并且大量的插入或删除还有可能触发页决裂和合并，写入性能个别，因而 B+ 树适宜读多写少的场景。

LSM 树

LSM Tree（Log Structured Merge Tree，日志构造合并树）其实并不是一种具体的树类型的数据结构，而只是一种数据存储的模型，它的核心思想基于一个事实：程序 IO 远快于随机 IO。

和 B+ 树不同，在 LSM 中，数据的插入、更新、删除都会被记录成一条日志，而后追加写入到磁盘文件当中，这样所有的操作都是程序 IO。

LSM 比拟实用于写多读少的场景。

看了后面的两种根底存储模型，置信你曾经对如何存取数据有了根本的理解，而 minidb 基于一种更加简略的存储构造，总体上它和 LSM 比拟相似。

我先不间接水灵灵的讲这个模型的概念，而是通过一个简略的例子来看一下 minidb 当中数据 PUT、GET、DELETE 的流程，借此让你了解这个简略的存储模型。

PUT

咱们须要存储一条数据，别离是 key 和 value，首先，为预防数据失落，咱们会将这个 key 和 value 封装成一条记录（这里把这条记录叫做 Entry），追加到磁盘文件当中。Entry 的外面的内容，大抵是 key、value、key 的大小、value 的大小、写入的工夫。

所以磁盘文件的构造非常简单，就是多个 Entry 的汇合。

磁盘更新完了，再更新内存，内存当中能够抉择一个简略的数据结构，比方哈希表。哈希表的 key 对应寄存的是 Entry 在磁盘中的地位，便于查找时进行获取。

这样，在 minidb 当中，一次数据存储的流程就完了，只有两个步骤：一次磁盘记录的追加，一次内存当中的索引更新。

GET

再来看 GET 获取数据，首先在内存当中的哈希表查找到 key 对应的索引信息，这其中蕴含了 value 存储在磁盘文件当中的地位，而后间接依据这个地位，到磁盘当中去取出 value 就能够了。

DEL

而后是删除操作，这里并不会定位到原记录进行删除，而还是将删除的操作封装成 Entry，追加到磁盘文件当中，只是这里须要标识一下 Entry 的类型是删除。

而后在内存当中的哈希表删除对应的 key 的索引信息，这样删除操作便实现了。

能够看到，不论是插入、查问、删除，都只有两个步骤：一次内存中的索引更新，一次磁盘文件的记录追加。所以无论数据规模如何，minidb 的写入性能非常稳固。

Merge

最初再来看一个比拟重要的操作，后面说到，磁盘文件的记录是始终在追加写入的，这样会导致文件容量也始终在减少。并且对于同一个 key，可能会在文件中存在多条 Entry（回忆一下，更新或删除 key 内容也会追加记录），那么在数据文件当中，其实存在冗余的 Entry 数据。

举一个简略的例子，比方针对 key A，先后设置其 value 为 10、20、30，那么磁盘文件中就有三条记录：

此时 A 的最新值是 30，那么其实前两条记录曾经是有效的了。

针对这种状况，咱们须要定期合并数据文件，清理有效的 Entry 数据，这个过程个别叫做 merge。

merge 的思路也很简略，须要取出原数据文件的所有 Entry，将无效的 Entry 从新写入到一个新建的临时文件中，最初将原数据文件删除，临时文件就是新的数据文件了。

这就是 minidb 底层的数据存储模型，它的名字叫做 bitcask，当然 rosedb 采纳的也是这种模型。它实质上属于类 LSM 的模型，核心思想是利用程序 IO 来晋升写性能，只不过在实现上，比 LSM 简略多了。

介绍完了底层的存储模型，就能够开始代码实现了，我将残缺的代码实现放到了我的 Github 下面，地址：

https://github.com/roseduan/minidb，

文章当中就截取局部要害的代码。

首先是关上数据库，须要先加载数据文件，而后取出文件中的 Entry 数据，还原索引状态，要害局部代码如下：

func Open(dirPath string) (*MiniDB, error) {
   // 如果数据库目录不存在，则新建一个
   if _, err := os.Stat(dirPath); os.IsNotExist(err) {if err := os.MkdirAll(dirPath, os.ModePerm); err != nil {return nil, err}
   }

   // 加载数据文件
   dbFile, err := NewDBFile(dirPath)
   if err != nil {return nil, err}

   db := &MiniDB{
      dbFile:  dbFile,
      indexes: make(map[string]int64),
      dirPath: dirPath,
   }

   // 加载索引
   db.loadIndexesFromFile(dbFile)
   return db, nil
}

再来看看 PUT 办法，流程和下面的形容一样，先更新磁盘，写入一条记录，再更新内存：

func (db *MiniDB) Put(key []byte, value []byte) (err error) {
  
   offset := db.dbFile.Offset
   // 封装成 Entry
   entry := NewEntry(key, value, PUT)
   // 追加到数据文件当中
   err = db.dbFile.Write(entry)

   // 写到内存
   db.indexes[string(key)] = offset
   return
}

GET 办法须要先从内存中取出索引信息，判断是否存在，不存在间接返回，存在的话从磁盘当中取出数据。

func (db *MiniDB) Get(key []byte) (val []byte, err error) {
   // 从内存当中取出索引信息
   offset, ok := db.indexes[string(key)]
   // key 不存在
   if !ok {return}

   // 从磁盘中读取数据
   var e *Entry
   e, err = db.dbFile.Read(offset)
   if err != nil && err != io.EOF {return}
   if e != nil {val = e.Value}
   return
}

DEL 办法和 PUT 办法相似，只是 Entry 被标识为了 DEL，而后封装成 Entry 写到文件当中：

func (db *MiniDB) Del(key []byte) (err error) {
   // 从内存当中取出索引信息
   _, ok := db.indexes[string(key)]
   // key 不存在，疏忽
   if !ok {return}

   // 封装成 Entry 并写入
   e := NewEntry(key, nil, DEL)
   err = db.dbFile.Write(e)
   if err != nil {return}

   // 删除内存中的 key
   delete(db.indexes, string(key))
   return
}

最初是重要的合并数据文件操作，流程和下面的形容一样，要害代码如下：

func (db *MiniDB) Merge() error {
   // 读取原数据文件中的 Entry
   for {e, err := db.dbFile.Read(offset)
      if err != nil {
         if err == io.EOF {break}
         return err
      }
      // 内存中的索引状态是最新的，间接比照过滤出无效的 Entry
      if off, ok := db.indexes[string(e.Key)]; ok && off == offset {validEntries = append(validEntries, e)
      }
      offset += e.GetSize()}

   if len(validEntries) > 0 {
      // 新建临时文件
      mergeDBFile, err := NewMergeDBFile(db.dirPath)
      if err != nil {return err}
      defer os.Remove(mergeDBFile.File.Name())

      // 从新写入无效的 entry
      for _, entry := range validEntries {
         writeOff := mergeDBFile.Offset
         err := mergeDBFile.Write(entry)
         if err != nil {return err}

         // 更新索引
         db.indexes[string(entry.Key)] = writeOff
      }

      // 删除旧的数据文件
      os.Remove(db.dbFile.File.Name())
      // 临时文件变更为新的数据文件
      os.Rename(mergeDBFile.File.Name(), db.dirPath+string(os.PathSeparator)+FileName)

      db.dbFile = mergeDBFile
   }
   return nil
}

除去测试文件，minidb 的外围代码只有 300 行，麻雀虽小，五脏俱全，它曾经蕴含了 bitcask 这个存储模型的次要思维，并且也是 rosedb 的底层根底。

了解了 minidb 之后，基本上就可能齐全把握 bitcask 这种存储模型，多花点工夫，置信对 rosedb 也可能熟能生巧了。

进一步，如果你对 k-v 存储这方面感兴趣，能够更加深刻的去钻研更多相干的常识，bitcask 尽管简洁易懂，然而问题也不少，rosedb 在实际的过程当中，对其进行了一些优化，但目前还是有不少的问题存在。

有的人可能比拟纳闷，bitcask 这种模型简略，是否只是一个玩具，在理论的生产环境中有利用吗？答案是必定的。

bitcask 最后源于 Riak 这个我的项目的底层存储模型，而 Riak 是一个分布式 k-v 存储，在 NoSQL 的排名中也名落孙山：

豆瓣所应用的的分布式 k-v 存储，其实也是基于 bitcask 模型，并对其进行了很多优化。目前纯正基于 bitcask 模型的 k-v 并不是很多，所以你能够多去看看 rosedb 的代码，能够提出本人的意见建议，一起欠缺这个我的项目。

最初，附上相干我的项目地址：

minidb：https://github.com/roseduan/minidb

rosedb：https://github.com/roseduan/rosedb

参考资料：

https://riak.com/assets/bitca…

https://medium.com/@arpitbhay…