序

现在普适性较强的适合磁盘的索引结构无非就是B-tree和LSM-tree，两种结构的最本质的不同在于，一个是就地更新（B-tree）一个是非就地更新（LSM-tree）。就地更新的索引结构拥有最好的读性能(随机读与顺序读)，而随机写性能很差，无法满足现实工业中的工作负载要求。而非就地更新的索引结构LSM-tree充分发挥顺序写入的高性能特性，成为写入密集的数据系统的基础。

在开始论述wisckey带来了什么改变之前，我们先回顾一下经典LSM-tree的实现。

LevelDB实现

前文提到LSM-tree的优势在于非就地更新，它的表现形式实际上就是延迟更新，顺序写入数据。但这样做也带来了很多问题。首先同一个key可能会占据多个存储空间，简单的解决方案就是每次读取的时候都是从后往前倒序的查找数据，这样保证了拿到的数据一定是最新的，该操作的复杂度为O（n）。优化该方案的手段就是后台对数据文件进行压缩，删去过时的数据。

每次压缩的过程本质上是一次归并排序的过程(为了支持范围查询，以及空间压缩)，那么就需要找到所有分段文件中有重合范围的文件，进行合并(min_key与max_key)。并且不能合并一个正在写入的文件(假设按大小划分文件)。

为了降低读取的复杂度，第一个想法就是利用内存，将最近最新写入的kv存储在内存数据结构中，红黑树，跳表等。 那么问题是何时将此数据结构dump到磁盘?最简单的是根据其大小的区别，然而在dump之前我们不能继续向其中写入数据，因此在内存中应该存在一个活跃内存表和一个不变内存表，二者相互交替，周期性的将不变内存表dump到内存中形成一个分段文件。

但这还不够，依旧没有解决最先写入且从未更新的key要读取全量数据的问题，为解决这个问题LSM结构引入了分层设计的思想。将所有的kv文件分为c0-ck 共k+1层。c0层是直接从不变的内存表中dump下的结果。而c1-ck是发生过合并的文件。由于ci+1 是ci中具有重叠部分的文件合并的产物，因此可以说在同一层内是不存在重叠key的，因为重叠key已经在其上一层被合并了。那么只有c0层是可能存在重叠的文件的。所以当要读取磁盘上的数据时，最坏情况下只需要读取c0的所有文件以及c1-ck每一层中的一个文件即c0+k个文件即可找到key的位置，分层合并思想使得非就地更新索引在常数次的IO中读取数据。

通常c0文件定义为2M，每一级比上一级大一个数量级的文件大小。所以高层的文件难以被一次性的加载到内存，因此需要一定的磁盘索引机制。我们对每个磁盘文件进行布局设计，分为元数据块，索引块，数据块三大块。元数据块中存储布隆过滤器快速的判断这个文件中是否存在某个key，同时通过对排序索引(通常缓存在内存中)二分查找定位key所在磁盘的位置。进而加速读取的速度，我们叫这种数据文件为SSTABLE(字符串排序表)。

为了标记哪些SStable属于那一层因此要存在一个sstable的元数据管理文件，在levelDB中叫做MANIFEST文件。其中存储每一个sstable的文件名，所属的级别，最大与最小key的前缀。

作为一个DB引擎，必须保证数据库进程崩溃前后的数据一致性，常见的做法就是使用预写日志。

将所有的操作记录在一个仅追加的log文件中(称之为WAL)，所有的写入操作都要保证写入WAL成功后才能继续，因此当数据库崩溃后写入WAL的操作将被回溯，反之则被丢弃(只有写入WAL成功才会回复客户端ack)。那么从尾部重放这个WAL文件的操作即可恢复DB。

但是这个过程由于会消耗磁盘的空间因此也需要不断的进行压缩，同时如果WAL过大也会使得数据库恢复的时间增大这是不可接受的，为此我们需要支持checkpint特性。

综上我们得到了LSM Tree的实现，本质上他并非是一颗树他是一个整套算法的集合，本质上是一种思想，而非一种单一的数据结构，而对这种的一种经典实现即是LevelDB。

wisckey带来的新机遇

wisckey将key与value分离存储，value仅存储在vlog中以仅追加的方式，而key存储在之前的lsm tree结构中。这样带来两个好处，第一不需要频繁移动vlaue的值，所以写放大减少，第二 lsm仅存储固定大小的key使得其存储占用变小，在内存中可以同时存储更多的key进而提高了缓存key的数量，间接的降低了读放大问题。

对于随机读请求，固态硬盘远高于机械硬盘，而对于范围查询，由于真正的value都存储在vLog中因此是无序的，所以进行范围查询就是需要进行随机读取(先从lsm顺序读key再逐个随机读value)，这必然造成性能的下降，传统的随机读取是串行的难以发挥固态硬盘并行随机读取的特性，因此在wisckey中根据迭代器的调用方法prev,next 来从排序好的lsm中预读取一定的key到内存中，加速随机的范围查询性能，这种预先读取是异步进行的，充分发挥固态硬盘的并行读取性能。

那么KV分离同时也带来许多问题，vLog文件会不断增大，那么就需要合并，如何合并才能保证对性能的影响最小化？同时由于移动了value的位置，LSM结构中维护的value的位置信息也要更新。数据具体如何布局？vLog日志如何拆分？wisckey崩溃后如何恢复才能保证数据的一致性呢?

数据布局

KV分离设计

  1. 在sstable文件中数据布局: <key, addr(vlogName,offset,size)>

  2. 在vlog文件中的数据布局: <keySize,valueSize,key,Value>

随机查询

  1. 先访问内存表是否命中key，如果找到地址信息判断是在内存中还是磁盘中(LRU缓存)

  2. 在内存中被缓存了value则直接返回，否则去磁盘中查找，根据vlog的名字找到具体的vlog文件

  3. 然后根据offset定位字节的首地址，根据size读取内容并返回

  4. 基于一定策略将整个vlog涉及的block缓存下来

范围查询

  1. 根据迭代器 next 还是 prev判断 是在游标之前读还是之后读，

  2. 预先读取一定的key，交由底层的线程池异步的取ssd中获取数据

  3. 将异步结果缓存在内存中 等到迭代器的调用

随机/顺序写入

  1. 将set操作先写入vlog日志中(存储key的作用之一就是既作为预写日志又作为值日志)

  2. 然后将返回的地址信息写入LSM中返回

  3. 返回写入成功

合并压缩

  1. vlog分为多个文件 其中存在一个活跃vlog文件 用于写入数据作为head地址

  2. 最先写入的的日志在最后的vlog中 存在tail地址

  3. 多个写入线程运行在head地址处追加日志

  4. 而只有一个后台线程执行垃圾收集运行在尾部

  5. 每次选择一个vlog文件的内容去lsm结构中随机查询(可并行化) 将没有失效的key重新写会到head地址处重新追加到vlog中

  6. 然后更新lsm中这些key的新地址

  7. 并释放老的vlog文件

  8. 这一过程中需要先将数据写入新的vlog文件后刷新到固态硬盘后异步更新索引

  9. 最后删除老文件 保证在此过程中进程崩溃造成数据丢失

故障恢复

  1. 在wisckey的设计中预写日志就是值日志

  2. 因此引擎进程只需要定时保存 head和tail的地址即可

  3. 数据库恢复时需要获取崩溃前最新的地址然后从tail到head将日志进行redo即可

  4. 同时为了保证一致性在查询key时要做一些必要的一致性检查

    1. 当前key如果在tail与head索引范围外则忽略

    2. 当前位置上的值具有的key与查询的key不匹配则忽略

    3. 发生上述情况时，引擎直接返回错误信息

优化与改进

写缓冲区

为减少写入的系统调研次数，多个小key的写入会被缓存在内存中汇聚在一起统一的写入lsm的sstable中，但会优先写入vlog中当作预写日志处理。

空间放大率

数据存储的实际的大小与逻辑上的大小比值用来衡量空间放大情况，对于固态硬盘来说其价格昂贵，降低空间放大率会大大的节省存储成本。

在线垃圾收集

GC过程会造成引擎的性能尖刺，通过并发的在线的分批次的进行GC操作来对前台读写性能影响。

小Value的存储

经论文的测试数据value大于4KB时其读取性能才会有极大的提升，因此可以设置一个阈值，当value大于此阈值时才进行KV分离，而再次之前使用传统lsm-tree模式。