background

通过 fragmented lsm (FLSM) 降低写放大. 适配到了 HyperLevelDB 修改为 pebblesDB. 显著降低 2.4-3x 写放大. 增加了 6.7x 写吞吐量. 并将 FLSM 作为 mongdb/HyperDex 的底层存储引擎 (IO吞吐量显著增加).

note: 较大的写放大 会导致 负载过高. 同时 IO竞争 降低在线延迟

结合了 SkipList + LSM, 以及 parallel seeks, aggressive seek-based compaction, and sstable-level bloom filters, 但是不擅长 range

design

FLSM’s compaction simply appends a new sstable fragment to the next level. guards: 将 key range 划分成 多个不相交的 单元. 每个level 包含多个 guards. level0 不包含 guards 打破了 a level 每个 sstable key 不接连的 约定, 也就是说, 相同的key 可以在 a level 的多个 sstable.

compaction 流程: ??? guards 选择? guard possibility: 按照比例读取, 就像 skiplist 一样. 但是 compaction 过程中 sstable 分区会导致IO放大.

guard 是如何工作的呢? add 和 delete 都是先存储在 uncommitted guards 的内存结构中, 在 compaction 的时候会存储下来.  compaction 过程中, delete 会迁移 level(i)  相邻的分区 或者 level(i+1)的 child guard. delete 会递归到 最高的 level. IO路径:

  • Get: 先搜索guard, 在搜索相关的 sstable
  • Range: 通过 merge sort
  • Put: 类似 lsm, 不过 compaction 基于 partitioned sstable 级别
  • Update/Delete: update seq num 或者 添加flag
  • compaction: ？ 按照 guard, level(i) 会归并到 level(i+1) 上的 sstables. 再看看. 不同guard 的compaction互不影响, 因此可以并行

调优

flsm 的性能取决于 每个 guard sstable 的数量. 设置参数 max_sstables_per_guard 限制, 超过了就comapct guard 到下一层. =1 就和 lsm 一样

分析

渐进分析不懂

pebbledb

range性能差, 通过 parallel seek 和 seek-based conpaction 优化.

  • get: 相比 flsm, 增加了 sstable-level bloom filters 避免无意义的读
  • range: 二叉搜索优化, 需要更详细的设计
  • delete: 插入一个 delete flag 的value

guard 的生成: 基于 hash(key) 的 最后几个bit

从论文的较大, IM/monitor 数据还是适合 rocksdb.

性能

从压测统计的数据上看, pebbledb 在延迟 方面并不占优, 写放大按照预期降低了, 随机写 和 更新性能也不错, 顺序性能明显下降(lsm可以直接移动, pebble 仍然需要 guard-based partition), seek + next 也是很低.  更新吞吐量不错, 得益于 partition的压缩策略

ps: 每一层的 sstable 的 key range 因为存在 重叠, range 性能严重下降

参考