论文阅读-WiscKey:SSD友好的KV分离存储引擎

背景

基于LSM-Tree的存储引擎

Log-Structed Merge-Tree (a.k.a. LSM-Tree)是当下常用的一种基于磁盘的存储引擎。与Hash索引和B-Tree同为数据库核心的数据结构。

LSM-Tree的优势在于:

  1. 无需将所有的Key索引在内存中。可以通过分级查找的方式,查询到特定KV在磁盘中的偏移量
  2. 数据写入与合并使用顺序追加写,最大程度的利用磁盘的顺序写性能
  3. 对于数据写入,会使用batch方式写入磁盘
  4. 支持范围查询

LSM-Tree的劣势在于:

  1. 读放大与写放大
  2. 无法对单条数据加锁(事务支持)

现在常用的LevelDB和RocksDB,都是基于LSM-Tree的存储引擎。

LSM-Tree-Architecture

WiscKey主要解决的问题

LSM-Tree在性能上面的瓶颈主要在于读写的放大。简单说来,假设你的磁盘最大带宽为4GB/s,读写放大倍数为10,那么在应用层的有效吞吐量(Goodput)最多只能达到400MB/s。并且,对于一些大数据集,读写放大的值有可能会非常大(大于100)。

那么是什么原因导致的读写放大呢?我们下面分开讨论。

读放大

我们重温一下LSM-Tree的查询机制:

  1. 首先在mutable memtable中进行查找
  2. 然后在immutable memtable中进行查找
  3. 最后在不同的LSM-Tree层级中的SST file中进行查找

对于1和2 …

more ...