我在设计底层kv数据存储系统的一些思路
其实在开发garuda的时候，我开始并没有准备用rocksdb，我是准备自己参考rocksdb自研一套kv文件存储系统的。
毕竟写代码过程中，对于引用我没有吃透的第三方库，我是审慎的，因为使用自己不熟悉的东西容易埋坑。
要实现一套kv数据存储系统，实质就是实现增删改查。影响性能的关键就是磁盘读写。所以优化点就是
- 尽可能减少磁盘读写次数。
- 尽量顺序读写，减少随机。
国产的很多存储软件，底层都是基于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的缩写，顾名思义，它是有序的。但是光有序也是无法高效查找的，还必须定长，然后才能二分法查找。但是定长有两种思路。
- 每条记录定长
- 每页(page)定长,但一页可以包含不同数量的记录。
最终我选择了第二种方案，定长4k，因为方便利用磁盘块。
在查询的时候，我们先用二分法定位到page，然后遍历page找到对应的row,或者返回不存在标记，但是为了加快查询效率，我们还是做了简单的索引,再sstable的头部4k的索引头，我们存了布隆过滤器和一点关键点的offset，用以加快查询速度，如下图所示
索引头是一个固定大小的内存空间，假设固定大小为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_id和field_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。
希望有一天我能把它实现出来。