TreeLine: An Update-In-Place Key-Value Store for Modern Storage
TreeLine: An Update-In-Place Key-Value Store for Modern Storage
复制标题
DOI：
10.14778/3561261.3561270
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Geoffrey X. Yu;Markos Markakis;Andreas Kipf;P. Larson;U. F. Minhas;Tim Kraska
中科院分区：
文献类型：
--
作者：
Geoffrey X. Yu;Markos Markakis;Andreas Kipf;P. Larson;U. F. Minhas;Tim Kraska
许多现代键值存储（如RocksDB）依赖于日志结构的合并树（lsm）。lsm最初是为旋转磁盘设计的，它通过只进行顺序写来优化写性能。但是这种优化是以读取为代价的：lsm必须依赖昂贵的压缩作业和Bloom过滤器——所有这些都是为了保持合理的读取性能。对于NVMe ssd，我们认为不再总是需要为了写性能而牺牲读性能。如果有足够的并行性，NVMe ssd具有相当的随机和顺序访问性能。这种变化使得就地更新设计成为lsm的可行替代方案，这种设计传统上提供了出色的读取性能。在本文中，我们利用利用数据和工作负载模式的新组件，缩小了现代ssd上日志结构设计和就地更新设计之间的差距。具体来说，我们探讨了三个关键思想：(A)高效点操作的记录缓存，(B)高性能范围扫描的页面分组，以及(C)插入预测，以减少容纳新记录的重组成本。我们通过在名为TreeLine的原型就地更新键值存储中实现这些想法来评估它们。在YCSB上，我们发现TreeLine在点工作负载上的表现分别比RocksDB和LeanStore平均高出2.20倍和2.07倍，总体上高出10.95倍和7.52倍。
Many modern key-value stores, such as RocksDB, rely on log-structured merge trees (LSMs). Originally designed for spinning disks, LSMs optimize for write performance by only making sequential writes. But this optimization comes at the cost of reads: LSMs must rely on expensive compaction jobs and Bloom filters---all to maintain reasonable read performance. For NVMe SSDs, we argue that trading off read performance for write performance is no longer always needed. With enough parallelism, NVMe SSDs have comparable random and sequential access performance. This change makes update-in-place designs, which traditionally provide excellent read performance, a viable alternative to LSMs. In this paper, we close the gap between log-structured and update-in-place designs on modern SSDs with the help of new components that take advantage of data and workload patterns. Specifically, we explore three key ideas: (A) record caching for efficient point operations, (B) page grouping for high-performance range scans, and (C) insert forecasting to reduce the reorganization costs of accommodating new records. We evaluate these ideas by implementing them in a prototype update-in-place key-value store called TreeLine. On YCSB, we find that TreeLine outperforms RocksDB and LeanStore by 2.20× and 2.07× respectively on average across the point workloads, and by up to 10.95× and 7.52× overall.