从零实现 KV 存储—内存和磁盘设计

bitcask 的内存和磁盘设计基本上遵循了论文中的描述，只是在一些细节中略有不同，保持论文中设计的简洁高效，所以总体就分为了两个部分，一是内存中的数据如何存放，二是磁盘中的数据如何组织。

内存设计

首先是内存，在内存当中，我们需要一种支持高效插入、读取、删除数据的结构，并且如果需要数据高效遍历的话，我们最好是选择天然支持有序的一种结构。所以说常见的选择有 BTree、跳表、红黑树等。我们可以先选择常用的 BTree 结构，当然我们可以不用自己去完整实现一遍 BTree 的所有细节，因为我们应该更加专注于存储引擎的设计而不是某个数据结构的实现。如果有现成的轮子，则可以直接拿来使用，google 的 Github Repo 下开源了一个 BTree 的库，有很多知名的项目都在使用，质量是非常有保证的，可以放心引用。项目地址：https://github.com/google/btree 而对于 Rust 则更加简单，标准库中自带了 BTreeMap 的实现，我们直接引用即可。 https://doc.rust-lang.org/stable/std/collections/struct.BTreeMap.html 内存中的数据结构设计应该还需要注意一个点，前面细读论文的文章中，我也说了，bitcask 的内存数据结构的选择比较多样化，我们可以根据自己的需求来设计。所以我们可以提供一个通用的抽象接口，可以接入不同的数据结构，这样可以在设计上更加的灵活。如果想要接入一个新的数据结构，只需要实现我们抽象接口中的方法即可。通用接口的定义大致如下：


// Indexer 通用索引接口
type Indexer interface {
        Put(key []byte, pos *data.LogRecordPos) bool
        Get(key []byte) *data.LogRecordPos
        Delete(key []byte) bool
}

之后会以自适应基数树（Adaptive Radix Tree）和跳表（SkipList）作为另一个内存索引，来展示如何支持多种内存索引结构，这样你可以根据自己的需要去实现其他的数据结构。

磁盘设计

内存设计完了，再来看看磁盘。我们可以将标准文件操作 API 例如 read、write、close 等方法进行简单的封装，然后数据在磁盘上的读写可以使用这些标准的文件 API，我们可以加一个目录 fio，专门存放关于文件 IO 操作相关的代码。目前我们只支持标准的系统文件 IO，但是如果后面有其他的 IO 类型，例如 MMap 内存映射，或者自己写一层文件 IO 系统，都可以进行接入。因此我们可以定义一个 IOManager 接口，将 IO 操作的接口进行抽象，方便接入不同的 IO 类型。


type IOManager interface {
        Read([]byte, int64) (int, error)
        Write([]byte) (int, error)
        Sync() error
        Close() error
}

然后对于数据文件的操作，例如新增、删除数据文件，从文件中读取记录，可以增加一个目录 data 来存放，表示数据文件、数据项等内容。内存和磁盘都设计好之后，我们的 bitcask KV 存储引擎的架构就很清晰了，如下图：

可以看到我们的 bitcask 存储引擎总体来说是很简单的，架构比较简洁，但是在实现的过程当中，还是有很多的细节需要处理，后续章节将进入我们的数据读写流程等实践部分。