vLSM: Low tail latency and I/O amplification in LSM-based KV stores

本文介绍了基于LSM的键值存储（KV存储）在现代数据基础设施中的重要性，但它们受到高尾延迟的影响，尾延迟高达数秒，使它们对用户面向应用程序不太有吸引力。本文引入了压实链的概念，并分析了它们如何影响尾延迟。然后，我们展示了现代设计通过交换I/O扩大或需要大量内存来降低尾延迟。基于我们的分析，我们提出了vLSM，这是一种新的KV存储设计，可以显著提高尾延迟而不影响内存或I/O扩大。vLSM通过使用小SST和消除现代系统中L0所需的层次压实来减少（a）压实链宽度，并通过在L1中使用比典型增长因子更大的重叠感知SST来减少（b）压实链长度。我们在RocksDB中实现了vLSM，并使用db_bench和YCSB进行了评估。我们的评估突出了内存需求、I/O扩大和尾延迟之间的潜在权衡，以及vLSM相对于当前方法的优势。vLSM将写入的P99尾延迟提高了4.8倍，将读取的P99尾延迟提高了12.5倍，将累积写入停顿减少了60％，同时在相同的内存预算下稍微提高了I/O扩大。

本论文旨在解决LSM-based key-value (KV) stores存在的高尾延迟问题，提出了一种新的KV store设计vLSM，旨在显著改善尾延迟而不影响内存或I/O放大。

vLSM通过使用小的SSTs和消除现代系统中L0所需的分层压实来减少压实链宽度，并通过在L1中使用大于典型增长因子的重叠感知SST来减少压实链长度。

论文实现了vLSM，并使用db_bench和YCSB进行了评估。结果表明，vLSM在不影响内存或I/O放大的情况下，将写入的P99尾延迟提高了最多4.8倍，读取的P99尾延迟提高了最多12.5倍，同时将累计写入停顿减少了最多60%。

最近的相关研究包括：《The Design and Implementation of Modern Column-Oriented Database Systems》、《Efficiently Compiling Efficient Query Plans for Modern Hardware》、《The Case for Learned Index Structures》等。