- LSM-based Storage Techniques: A Survey.
- Wisckey-Separating Keys from Values
近些年，日志结构化合并树（LSM tree）已被广泛使用在现在nosql系统的存储层。正因为如此，已经有了大量的研究工作，数据库社区和操作系统社区，也在尝试改进LSM树的各个方面。在本文中，我们对LSM树的最新研究工作进行了综述，读者可以了解基于LSM存储的最新技术。我们讨论各类lsm各种方案的优势和权衡，并进一步调查了几个有代表性的，基于LSM的开源NoSQL系统，讨论了一些潜在的未来研究方向。
LSM-tree(Log-Structured Merged-tree) 现如今已经被广泛应用在了各个NoSQL 存储系统中，如BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB 和 AsterixDB。相比于传统的in-place updates(就地更新) 索引结构，LSM-tree 第一次写入都缓存到内存中，并通过后台的flush来顺序追加到磁盘中，也就是out-of-palce updates。 LSM-tree这样的实现方式有非常多的优点，包括写性能的提升、较高的空间利用率、简单的并发控制和异常恢复等。这些优点使LSM树可以服务于多种场景，如Facebook开发的基于LSM-tree的存储引擎 rocksdb， 被广泛应用在实时数据处理/图数据处理/流式数据处理以及 OLTP(on line transaction processing) 等多种workload。
由于LSM树在现代数据存储中的普及，研究团体已提出了对LSM树的大量改进。这些都来自数据库和操作系统社区。在本文中，我们调查了最近有关改进LSM树的研究工作，范围从具有单个LSM树的键值存储设置到具有二级索引的更通用的数据库设计。本文旨在为研究人员，从业人员和用户提供基于LSM的存储技术的最新指南。他们试图进行优化。然后，我们详细介绍了各种改进，并讨论了它们的优势和取舍。为了反映LSM树在实际系统中的使用方式，我们进一步调查了五个代表性的基于LSM的开源NoSQL系统，包括LevelDB [4]，RocksDB [6]，HBase [3]，Cassandra [1]和AsterixDB [9]。最后，作为对现有LSM树改进的分类结果，我们还确定了几个有趣的未来研究方向。
第2部分简要回顾了LSM树的历史，并介绍了当今LSM树实现的基础知识。
第3节介绍了LSM树改进的分类法，并使用该分类法对现有工作进行了调查。
第4节对一些基于LSM的代表性NoSQL系统进行了调查，重点关注其存储层。
第5节对本次调查的结果进行了反思，确定了基于LSM的存储系统上的一些问题和未来工作的机会。