WiscKey: 在 SSD 感知存储中将键与值分离
作者
Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H.
Arpaci-Dusseau, University of Wisconsin—Madison
摘要
我们提出了 Wisckey,一种基于 LSM Tree 的持久键值存储，具有面向性能的数据分布，
其将键与值分离，以最小化读写放大。Wisckey 的设计是为固态硬盘高度优化的，其利用
了固态硬盘的顺序和随机性能特征。我们通过微基准测试和 YCSB 工作负载展示了
WiscKey 的优势。Microbenchmark 结果显示，在加载数据库方面，WiscKey 比 LevelDB
快 2.5 到 111 倍，且具有明显更好的尾部延迟，在随机查找方面快 1.6 到 14 倍。在所有
六个 YCSB 工作负载中，WiscKey 都比 LevelDB 和 RocksDB 快。
1. 介绍
当前 key-value 的数据库应用广泛，如谷歌的 levelDB，Facebook 的 RocksDB。
他们都应用了一个数据结构，LSM-Tree（Log Structured Merge Tree），使他们代表了
目前最好水平。
先来介绍一个不同的数据结构——B-Tree。B 树可以理解为二叉平衡树的多叉版本，每一
次更新可能需要平衡，带来多次随机查找，因此不适合固态或机械硬盘。
再来介绍一下 LSM 树。LSM 树将多个键值对合并，保存一定量后，顺序写入到磁盘中。
后台为了加速查询，则不断的排序，将键值对从磁盘里读取，排序，再写入，因此会带来
50 倍以上的读写放大。
当下的 LSM 不适合固态硬盘 SSDs（Solid-state Storage Devices）。如果用固态硬盘来替
换机械硬盘，虽然性能提升了，但是会降低 90%的吞吐，增加 10 倍以上的写负载，导致
其性能无法充分发挥，原因如下：
1. 固态硬盘的连续读写速度和随机读写速度没有机械硬盘那么差别大。因此 LSM
优化的批量连续写入可能会不必要的浪费带宽。
2. 固态硬盘有很大程度的内部并行性，LSM 需要小心设计以驾驭其并行性
3. 固态硬盘重复写入会导致设备损耗，LSM 带来的写放大会加速设备老化
WiscKey 优化了 LSM 树，将键值对储存分离，也就是排序和垃圾回收这两个过
程分开。这样能够减少排序时不必要的值移动，进而减小读写放大的倍数。此外这
样还能减少 LSM 树大小，减少读次数的同时，在查询时有更好的缓存。
但是也带来了一些挑战，他这样解决：
