LSM存储技术：一项综合调查
需积分: 3 158 浏览量
更新于2024-07-16
收藏 719KB PDF 举报
"LSM-survey.pdf 是一篇关于LSM（日志结构合并树）存储技术的调查论文，全面概述了存储工程师需要了解的所有LSM相关技术，强烈推荐阅读。"
LSM（Log-Structured Merge-tree）是一种广泛应用于现代NoSQL系统存储层的数据结构。它的设计目标是优化磁盘I/O性能，尤其适用于写密集型工作负载。近年来，随着NoSQL数据库的普及，对LSM树的研究和优化成为了数据库和操作系统社区关注的重点。
这篇由Chen Luo和Michael J. Carey等人撰写的预印本论文对LSM树的相关研究进行了详尽的调查，旨在让读者了解LSM存储技术的最新进展。论文首先介绍了LSM树的基本概念和工作原理：数据以日志形式写入，定期合并以减少随机读取的开销，从而提高读写效率。
论文构建了一个通用的分类体系，将现有的LSM树文献分为多个类别，可能包括但不限于以下几类：
1. **LSM树的结构优化**：这部分研究可能涉及如何改进LSM树的层级结构，例如减少合并操作的频率，或者调整内存和磁盘之间的数据分布，以实现更高效的数据访问。
2. **压缩与编码**：为了减少存储空间和I/O操作，LSM树可能采用不同的数据压缩和编码技术。这部分可能涵盖了最新的压缩算法和其对性能的影响。
3. **缓存策略**：LSM树的性能往往依赖于内存缓存的管理。论文可能会讨论如何优化缓存策略，如使用LRU（Least Recently Used）或LFU（Least Frequently Used）策略，以及最近的智能缓存算法。
4. **并发控制与多线程**：在多核处理器环境中，如何并行化LSM树的操作以提高性能是关键问题。这部分可能涵盖并发插入、读取和合并操作的优化方法。
5. **故障恢复与持久性**：LSM树如何保证在系统崩溃或断电后能够正确恢复，以及如何在不影响性能的情况下实现数据持久化，也是研究的重点。
6. **实时分析与查询优化**：对于支持分析查询的LSM树，如何优化查询性能，减少延迟，同时保持高吞吐量，是另一个挑战。
7. **可扩展性和分布式LSM**：随着数据量的增长，如何设计可扩展的LSM树架构，以及在分布式系统中部署和管理LSM树，也是研究的重要方向。
通过这篇论文，读者可以系统地了解LSM树的最新研究成果，为设计、实现或优化存储系统提供理论依据。对于数据库和存储领域的从业者，它是一份非常有价值的学习资料。
4 Chen Luo, Michael J. Carey
Bloom filter and then proceed to search its B
+
-tree only
if its associated Bloom filter reports a positive answer. Al-
ternatively, a Bloom filter can be built for each leaf page
of a disk component. In this design, a point lookup query
can first search the non-leaf pages of a B
+
-tree to locate the
leaf page, where the non-leaf pages are assumed to be small
enough to be cached, and then check the associated Bloom
filter before fetching the leaf page to reduce disk I/Os. Note
that the false positives reported by a Bloom filter do not im-
pact the correctness of a query, but a query may waste some
I/O searching for non-existent keys. The false positive rate
of a Bloom filter can be computed as (1 − e
−kn/m
)
k
, where k
is the number of hash functions, n is the number of keys, and
m is the total number of bits [18]. Furthermore, the optimal
number of hash functions that minimizes the false positive
rate is k =
m
n
ln2. In practice, most systems typically use 10
bits/key as a default configuration, which gives a 1% false
positive rate. Since Bloom filters are very small and can of-
ten be cached in memory, the number of disk I/Os for point
lookups is greatly reduced by their use.
Partitioning. Another commonly adopted optimization
is to range-partition the disk components of LSM-trees into
multiple (usually fixed-size) small partitions. To minimize
the potential confusion caused by different terminologies,
we use the term SSTable to denote such a partition, following
the terminology from LevelDB [4]. This optimization has
several advantages. First, partitioning breaks a large com-
ponent merge operation into multiple smaller ones, bound-
ing the processing time of each merge operation as well as
the temporary disk space needed to create new components.
Moreover, partitioning can optimize for workloads with se-
quentially created keys or skewed updates by only merging
components with overlapping key ranges. For sequentially
created keys, essentially no merge is performed since there
are no components with overlapping key ranges. For skewed
updates, the merge frequency of the components with cold
update ranges can be greatly reduced. It should be noted that
the original LSM-tree [52] automatically takes advantage of
partitioning because of its rolling merges. However, due to
the implementation complexity of its rolling merges, today’s
LSM-tree implementations typically opt for actual physical
partitioning rather than rolling merges.
An early proposal that applied partitioning to LSM-trees
is the partitioned exponential file (PE-file) [38]. A PE-file
contains multiple partitions, where each partition can be log-
ically viewed as a separate LSM-tree. A partition can be
further split into two partitions when it becomes too large.
However, this design enforces strict key range boundaries
among partitions, which reduces the flexibility of merges.
We now discuss the partitioning optimization used in
today’s LSM-tree implementations. It should be noted that
partitioning is orthogonal to merge policies; both leveling
and tiering (as well as other emerging merge policies) can
level 0
level 1
level 2
0-100
0-30 34-70 71-99
0-15 16-32 35-50 51-70 72-95
0-10 11-19
20-32
SSTable
Merging SSTable
New SSTable
34-70 71-99
35-50 51-70 72-95
level 1
level 2
Before Merge
After Merge
0-100
level 0
0-100
0-100
Fig. 4: Partitioned leveling merge policy
be adapted to support partitioning. To the best of our knowl-
edge, only the partitioned leveling policy has been fully im-
plemented by industrial LSM-based storage systems, such
as LevelDB [4] and RocksDB [6]. Some recent papers [12,
50,58,76,79] have proposed various forms of a partitioned
tiering merge policy to achieve better write performance
4
.
In the partitioned leveling merge policy, pioneered by
LevelDB [4], the disk component at each level is range-
partitioned into multiple fixed-size SSTables, as shown in
Figure 4. Each SSTable is labeled with its key range in the
figure. Note that the disk components at level 0 are not par-
titioned since they are directly flushed from memory. This
design can also help the system to absorb write bursts since
it can tolerate multiple unpartitioned components at level 0.
To merge an SSTable from level L into level L +1, all of its
overlapping SSTables at level L + 1 are selected, and these
SSTables are merged with it to produce new SSTables still at
level L + 1. For example, in the figure, the SSTable labeled
0-30 at level 1 is merged with the SSTables labeled 0-15 and
16-32 at level 2. This merge operation produces new SSTa-
bles labeled 0-10, 11-19, and 20-32 at level 2, and the old
SSTables will then be garbage-collected. Different policies
can be used to select which SSTable to merge next at each
level. For example, LevelDB uses a round-robin policy (to
minimize the total write cost).
The partitioning optimization can also be applied to the
tiering merge policy. However, one major issue in doing so
is that each level can contain multiple SSTables with over-
lapping key ranges. These SSTables must be ordered prop-
erly based on their recency to ensure correctness. Two pos-
sible schemes can be used to organize the SSTables at each
level, namely vertical grouping and horizontal grouping. In
both schemes, the SSTables at each level are organized into
groups. The vertical grouping scheme groups SSTables with
overlapping key ranges together so that the groups have dis-
joint key ranges. Thus, it can be viewed as an extension
4
RocksDB supports a limited form of a partitioned tiering merge
policy to bound the maximum size of each SSTable due to its internal
restrictions. However, the disk space may still be doubled temporarily
during large merges.
剩余25页未读，继续阅读
2022-01-13 上传
2020-07-06 上传
2019-09-15 上传
2019-09-15 上传
caifengzhu
- 粉丝: 0
- 资源: 6
我的内容管理
展开
最新资源
- 构建基于Django和Stripe的SaaS应用教程
- Symfony2框架打造的RESTful问答系统icare-server
- 蓝桥杯Python试题解析与答案题库
- Go语言实现NWA到WAV文件格式转换工具
- 基于Django的医患管理系统应用
- Jenkins工作流插件开发指南：支持Workflow Python模块
- Java红酒网站项目源码解析与系统开源介绍
- Underworld Exporter资产定义文件详解
- Java版Crash Bandicoot资源库：逆向工程与源码分享
- Spring Boot Starter 自动IP计数功能实现指南
- 我的世界牛顿物理学模组深入解析
- STM32单片机工程创建详解与模板应用
- GDG堪萨斯城代码实验室：离子与火力基地示例应用
- Android Capstone项目：实现Potlatch服务器与OAuth2.0认证
- Cbit类：简化计算封装与异步任务处理
- Java8兼容的FullContact API Java客户端库介绍
