序

比较经典的kv存储分离的实现, 将大的value存储在 vlog 文件上, lsm 只存储 (key, offset) 信息, (需要注意的是, vlog的内容也需要记录key的信息, 加快gc), 极大的降低了 lsm 在 写放大, 延长ssd的生命周期. 虽然通过vlog 无法利用顺序读的优势, 但是可以利用 多线程 + ssd 来达到顺序读取的效果. 在内部实现上, 甚至去除了 lsm 中log的模块, 并达到了一致性.

论文精读

论文开篇对比列出了 hdd/ssd lsm实现的几个问题:

  1. ssd 的 顺序IO/随机IO 的差距明显低于 hdd, 这样就显得 lsm 中大量 随机IO->顺序IO的优化显得没那么必要 (参见论文figure 3)
  2. ssd 的内部并行化程度高
  3. ssd 的不擅长重复擦除写, LSM 最差 50x 的写放大会降低 ssd 的生命周期

为此, 设计了 wisckey, 充分利用 ssd 的随机+内部并发能力, 将value存储在vlog上, 同时降低不必要的写放大

挑战

在设计wisckey, 会和 传统 lsm 设计存在很大的gap, 例如:

  • range query (scan) 的性能会受到影响, 因为 value 不再有序 (wisckey 基于ssd的内部并行度)
  • wisckey 需要额外的 gc 机制回收 invalid value的空闲空间 (gc会影响前台IO)
  • kv的崩溃一致性保证 (基于现代文件的append语意)

收益

除了 大数据的range scan 和 随机写入小值 外, 其他情况性能 都远超leveldb (WiscKey is 2.5×–111× faster than LevelDB for loading a database; for random lookups, WiscKey is 1.6×–14× faster than LevelDB)

从leveldb的角度出发, 写放大 level * ratio, 默认配置 5 * 10 = 50 倍 (有一些说法是 level * (ratio + 1)), 读放大 (index block + data block + one data block) * sst file numner, (考虑布隆过滤器不命中的场景), 在论文的配置中可以达到 336 倍.

与之对比, wisckey kv 分离, 明显降低了读、写、空间放大问题.

设计

wisckey 的设计要点:

  1. kv分离
  2. 利用ssd 的并行随机读取特性 增强 unsorted value 的能力
  3. 使用 唯一的 crash-consistency & gc 高效的管理 vlog
  4. 在不牺牲一致性的情况下, 移除了 lsm-tree log, 降低 small writes 的系统调用

IO路径

  1. insert/update: 先插入 (key, value) 到 vlog, 然后组装成 (key,(vlog-offset, value-size)) 存储到lsm.
  2. lookup: 先查询 lsm, 在读取 vlog
  3. range query(scan): lsm range scan后, 交给 后台线程读取 (论文中实现有32个线程)
  4. delete: 仅删除 lsm key, vlog 的invaid value 交给 gc 处理
  5. gc: 遍历vlog (tail->head, 分chunk批量读取), 将有效的数据追加到 head 后面, 最终释放之前的数据空间. 这里需要注意到 vlog 中的数据格式: (ksize, vsize, key, value); 为了解决 crash consistency, 每次 append vlog 都会调用 fsync, 同时持久化 （tail, tailoffset) 到 lsm.

failure

  1. crash consistency

基于现代文件系统的 append 语意 保证 vlog 的一致性. 这个时候 crash 仅仅会发生在 after insert vlog 和 before insert lsm, 这里数据的准确性 以 lsm 为准. 如果 lsm 没有, 那么数据就没有, 中间的冗余数据依赖 gc 回收. 除此之外, vlod 的 item key 也会和 lsm key 比较 进行key的校验

性能优化

  1. 为了降低 write 系统调用的负担 (尤其是 写密集型), 设计了 vlog userspace buffer 缓冲. (可能会丢失数据)
  2. 周期的持久化 (head, head-vlog-offset) 来加快 crash-recovery. 类似快照的设计了. 这样只需要在恢复的时候从 head-vlog-offset 开始读取. 基于这些措施, 移除了 lsm tree log
  3. 利用 fallocate 文件打洞的方式快速回收文件空间 (有趣的特性, 得研究下)

bench

各种数据都好于 leveldb

个人想法

比较适合做 单机的对象存储.

熟悉下 ycsb

文件打洞 感觉就是将 分配给 文件的块迅速回收掉

参考