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

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

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

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

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

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

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

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

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

数据写入

SSTable

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

leveldb里有MemTable,Immutable Memtable,SSTable三个结构来实现这个功能。数据的写入是先写入memtable,等到其存储内容的容量达到阈值时(默认为4MB),便将其转换成一个不可修改的memtable,与此同时创建一个新的memtable,供用户继续进行读写操作。这个不可写的memtable也称为immutable,随后会写入磁盘,称之为sstable. memtable的底层是skip table实现的。但是这种临时存储内容,实在灭必要引入一个额外的结果,所以直接才有内置的orderd_map来实现,它底层是红黑树。

SSTable,它是Sorted Strings Table的缩写,顾名思义,它是有序的。但是光有序也是无法高效查找的,还必须定长,然后才能二分法查找。但是定长有两种思路。

  1. 每条记录定长
  2. 每页(page)定长,但一页可以包含不同数量的记录。

最终我选择了第二种方案,定长4k,因为方便利用磁盘块。

Page

在查询的时候,我们先用二分法定位到page,然后遍历page找到对应的row,或者返回不存在标记,但是为了加快查询效率,我们还是做了简单的索引,再sstable的头部4k的索引头,我们存了布隆过滤器和一点关键点的offset,用以加快查询速度,如下图所示

SSTABLE

索引头是一个固定大小的内存空间,假设固定大小为K,那么会先存起始结束key,然后存2等分点,4等分点,8等分点....的key和offset,直到将K大小的空间占满为止,目的是为了缩小二分法的查找范围。每次io读取都是一个page,减少读取次数明显可以提高性能。

注意,本文中的sstable,并不等同于leveldb的sstable,

Compaction

sstable内部的数据是有序的,除开level0以外的level也是整体有序的,查找的过程是memtable -> immutable memtable -> L0 -> L1 -> L2 ....

需要注意的是,l0是无序的,所以L0的每个文件都需要查找,其他level的文件因为是整体有序,所以直接定位到对应的文件,然后查找一次即可(在布隆过滤器没有判否的情况下)。

当L0的文件数量达到阈值时,触发L0和L1的合并。通常必须将所有L0的文件合并到L1中,因为L0的文件的key是有交叠的(overlapping)。

所有非零的levle 都有指定的大小,我们进行compaction 的目的就是使数据大小维持target_size 之下。

但是sstale之间是无序的。每个level的sstable都有一个编号,编号越大数据越新。在查询的时候,会从低level编号最大的查找,如果找不到会继续搜寻下一个sstable, 如果本层未归档的sstale都没找到,则会进入下一个level未归档的sstable查找,直到最后一个level的唯一一个sstable,如果也没找到,则表明数据不存在。这额也说明了,lsm结果存在读放大。

每个level的文件都是整体有序的,因为文件内部的key是有序的。为了确定一个key的位置,我们 先根据每个文件的start/end key对所有文件进行二分查找来确定哪些文件可能包含key。 再通过二分查找在候选的文件中定位key的准确位置,这是一次对一个level上所有文件的二分查找的过程。

所有非零的levle 都有指定的大小,我们进行compaction 的目的就是使数据大小维持target_size 之下,数据的大小经常会呈指数级增长,

如rockesdb的wiki所述 Leveled-Compaction

leveldb https://leveldb-handbook.readthedocs.io/zh/latest/compaction.html

数据存储

数据的存储分为索引存储数据存储, 如下图所示,分别为索引和数据。

我们每次新增,修改,删除都是一条新的记录(row), 都会分配一个唯一的row_id,每条数据有一个主键_id, 主键是判断一条记录唯一性的依据。如果一个主键对应了多条row,则取row_id最大的那条记录。

每个bucket都有一套schema,它定义了每个字段的编号field_id和类型。所以我们有了bucket_idfield_id就可以判断字段的类型了,对于integer类型的字段,它可以直接用DIS来存储,对于字符串类型,需要在字符串内容前面先存字符串的长度。

DIS是dynamic integer string的缩写,表示动态数字字符串,其说明可以参考这里BytesSteam

数据查询/遍历

比如我们查询bucket_id=1, _id=2的记录,我们先换算成key的前缀范围 00000001 00000001 00000000 - 00000001 00000001 11111111 ,因为一条记录可能有多个row,所以我们可能查出多条记录,然后取row_id最大的那条记录。后面的flag是删除标记,如果flag=1, 则表明该记录已经删除,返回数据不存在。在找到row_id后,就可以根据row_id精确查找出完整的数据了。

对于主键,是不可变的。但是对于普通的字段,比如_id=1的那条记录,可能开始name="abc",然后改成了name="efg", 那么索引区查询name="abc"和name="efg"都可以查到一条记录,这两条记录有一个相同的_id,这个时候还需要回表,即我们根据 这个_id查出完整的数据,然后根据数据里这个字段的当前值,舍弃不符合条件的记录。

数据修改/删除

数据的修改和删除本质都是一样的,都是插入一条新的数据(称之为row),不同的是,删除的数据,对应的flag为一个特殊的标记符。

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

其他

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

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

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