设计一个底层kv数据存储系统的一些思路

其实在开发garuda的时候,我开始并没有准备用rocksdb,我是准备自己参考rocksdb自研一套kv文件存储系统的。

毕竟写代码过程中,对于引用我没有吃透的第三方库,我是审慎的,毕竟使用自己不熟悉的东西容易埋坑。

要实现一套kv数据存储系统,实质就是实现增删改查。影响性能的关键就是磁盘读写。所以优化点就是

  1. 尽可能减少磁盘读写
  2. 尽量顺序读写,减少随机。

国产的很多存储软件,底层都是基于rocksdb的,rocksdb是在levendb上修改而来,主要的存储数据结构就是LSM

我个人总结了一下它写入高效的核心是批量写入。而读取高效的原因是有序

下面就是我参考leveldb实现的一套简化版的存储系统.

数据写入

SSTable

单纯的文件写入数据是高效的,唯一可优化的地方就是批量写入,减少写入次数。所以我们在刷入文件之前需要在内存进行数据“积攒”.

LSM里数据会先写入memtable,memtable有最大限制(write_buffer_size)。当memtable的size达到阈值,会变成只读的memtable(immutable memtable)。后台compaction线程负责把immutable memtable dump成sstable文件。

SSTable,它是Sorted Strings Table的缩写,顾名思义,它是有序的,是按key升序(也可以降序)排列。其实memtable也是有序的,这里有个疑问:为啥memtable这个内存存储模块也要有序呢?

实际上内存有序,是为了保证实时查询的效率。我们知道绝大部分的数据是存在磁盘的,所以查询自然也是从磁盘查询。但如果只查磁盘,对于这部分暂存在内存还没刷入磁盘的数据是查不到的。因此要实现实时查询,在查询磁盘之前需要先查memtable,有序是为了保证从查询的效率,除了有序,我们也可以通过hashmap来实现高效查询。如果我们不需要实时查询,那么memtable是不需要保证时刻有序的,只需要在刷盘前排序一次即可。综合考虑,有序较方便。leveldb用的skiptable来存储imtable,但是我个人觉得没必要这么麻烦,直接用c++的std::map存就行了,本质是红黑树。

单个sstable里的数据是有序的,但是sstble之间却不是有序的,所以在查询数据的时候并不好定位查找的key在哪个sstable。无法定位自然要遍历每个sstable.为了减少遍历的文件数,leveldb弄了一个FileMetaData的数据格式单独存储一些关键信息,这些信息简单的说,就是一个bloom filter,最大key,最小key。在查询的时候,先通过他们过滤下,如果过滤判断后发现要查找的key不在该文件,那么就不用查找该sstable文件了。

leveldb的做法我个人认为有些麻烦。我决定采用header+data的结构来存储sstable。如下图:

文件头header是一个固定大小的空间,前面的4个字节存的是数据的总字节数,后面的8字节是bloom filer。剩下的补充信息,是用前面说的bytestream存储的。假设固定大小为K,那么剩下的K-12字节的内容首先存的是最大key和最小key。剩下的存的是一些关键位置的key和offset。依次存2等分点,4等分点,8等分点....的key和offset,直到将K大小的空间占满为止,目的当然是为了缩小二分法的查找范围。header的内容会保留在内存里。

数据部分是按len+record+check_sum+\0依次存储的。record是由key+\0+data存储。

Compaction

从上图看出,segment的内部是有序的,查找很方便,但是segment之间是无序的。进行查找的时候,是无法定位该key存在哪个segment里,所以查找需要遍历每个segment,这显然是很糟糕的设计。所以我们需要合并文件,将多个各自有序的文件合成一个大的有序文件,这样我们查找的时候只需要先查找未合并的少量文件和合并后的大文件即可。

leveldb通过如下的分层和合并避免了该问题:

插入和合并过程这里有详细的介绍https://zhuanlan.zhihu.com/p/46718964,但是有一点就是过程太复杂。它sstable的写入不完全是从L0开始的,而是通过计算得出的层级。查询的时候也不够高效,它从L0查起。

我对它进行了改进:

  1. 落盘固定从L0写入,层级不设置上限(实际因为磁盘大小会有上限)。
  2. 底层达到数量N,就合并成一个上一层文件。假设N为10. 现在有11个L0,那么0-9的L0文件会合并成一个L1文件。
  3. 文件异步清理,底层被合并的数据已经存在于更上层了,此文件不在需要,可以删除。

如图所示,假设N=3,底层level每满3个,就会向上合并成一个文件。图中阴影文件表示已经被合并过了,实际是可以删除的。

由此改动,会造成查询和遍历的改动,这个我们下一步再谈。

数据修改/删除

数据的修改和删除本质都是一样的,都是插入一条新的数据,不同的是,删除的数据,key对应的value为一个特殊的标记符。

根据前面数据写入规则,level越低,文件越新,里面的数据越新。所以对于相同的key,value取最新的那个。

数据查询/遍历

因为前面在compaction的的改动,所以我的方案里查询和遍历与leveldb完全不同了。

我前面的方案里因为会一直合并,所以一定会有最高level,该level有效文件数在N-1个以内。我们讲之命名为LMax.

每个有效文件(没有被高层合并过的文件)都在内存维护一个bloomFilter和start-end-key。

单个查询

  1. 先从内存memtable里查找。如果找到则直接返回。后面步骤不再进行。

  2. LMax层的所有文件和非LMax层的未合并文件查找,查找前先根据每个文件的bloom和start-end-key过滤一下,然后依次二分法查找。注意的是,查找从低leve的最新的文件查起,如果查到了,直接返回,后面不需要再进行查找了。因为level越低,文件越新,里面的数据越新。遍历

遍历

遍历其实跟单个的过程是一样的,不同的是,因为是范围获取,所以只要每个文件的start-end-key包含你的遍历范围,你都得执行一遍遍历,先找出一个小于等于start的key的offset,然后通过文件offset遍历。

其他

上述只是一个基本思路,实际上还有很多模块需要设计,比如wal,log,cache,counter,lock等。

最终我为了快速出产品,直接使用了rocksdb。

希望有一天我能把它实现出来。