术语 SSTable 和 LSM Tree 之间有什么区别

Question

这两个术语可以互换使用吗？

我已经阅读了 SSTable 的工作原理，通常，文章只是开始提到 LSM Tree。然而，它们似乎是一回事。

什么时候应该使用一个术语而不是另一个术语？

Answer 1

排序字符串 Table (SSTable) 是一个 key/value 基于字符串对的文件，按键排序。

然而，LSM Tree 不同：

In computer science, the log-structured merge-tree (or LSM tree) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data. LSM trees, like other search trees, maintain key-value pairs. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches.

https://en.wikipedia.org/wiki/Log-structured_merge-tree

Answer 2

在第 1 节和 2.2.1 的 LSM-based storage techniques: a survey 论文中有很好的解释

LSM-tree由一些内存组件和一些磁盘组件组成。基本上 SSTable 只是 LSM-tree 磁盘组件的一个实现。

SSTable 由上述论文解释：

An SSTable (Sorted String Table) contains a list of data blocks and an index block; a data block stores key-value pairs ordered by keys, and the index block stores the key ranges of all data blocks.

Answer 3

实际上，LSM 树这个术语是由 Patrick O'Neil 的论文正式提出的 The Log-Structured Merge-Tree (LSM-Tree) 这是发表于 1996 年

术语 SSTable 是由 Google 的 Bigtable: A Distributed Storage System for Structured Data 在 2006 年创造的

从概念上讲，SSTable 是为基于（主要）存储引擎（例如：Lucene）的 LSM 树提供索引的东西。这不是关于差异，而是关于学术界的概念如何可能存在很长时间但后来以某种方式命名。通读以上两篇论文会告诉你很多。

Answer 4

可能对 SSTables 和 LSM-Trees 最好的解释之一是 Martin Kleppmann in his "Designing Data-Intensive Applications" 一本书。这些数据结构在第 3 章“存储和检索”第 69 到 79 页中进行了解释。这本书真的很棒，我会推荐整本书！

不耐烦的可以在下面找到我的主题概要

一切都始于一个非常愚蠢的 key-value 数据库，仅实现了两个 Bash 函数：

db_set () {
    echo "," >> database
}

db_get () {
   grep "^," database | sed -e "s/^,//" | tail -n 1
}

想法是将数据存储在 CSV-like 文件中：

$ source database.sh

$ db_set 1 'Anakin Skywalker'
$ db_set 2 'Luke Skywalker'
$ db_set 1 'Darth Vader'

$ cat database
1,Anakin Skywalker
2,Luke Skywalker
1,Darth Vader

$ db_get 1
Darth Vader

请注意，键 1 的第一个值被后续写入覆盖。

该数据库的写入性能相当不错：db_set只是将数据追加到一个文件中，一般速度很快。但是读取效率低下，尤其是在巨大的数据集上：db_get 扫描整个文件。因此，写入是 O(1)，读取是 O(n)。

接下来介绍指数。索引是从数据本身导出的数据结构。维护索引总是会产生额外的成本，因此，索引总是会降低写入性能，同时提高读取性能。

哈希索引是最简单的索引之一。这个索引只不过是一个字典，保存数据库中记录的字节偏移量。继续前面的示例，假设每个字符都是一个字节，哈希索引将如下所示：

每当您将数据写入数据库时，您也会更新索引。当您想要读取给定键的值时，您可以快速查找数据库文件中的偏移量。有了偏移量，您可以使用“查找”操作直接跳转到数据位置。根据特定的索引实现，您可能期望读取和写入的对数复杂度。

接下来，Martin 将讨论存储效率。将数据附加到数据库文件会很快耗尽磁盘 space。您拥有的不同键越少——这个 append-only 存储引擎的效率就越低。这个问题的解决方案是压缩：

当数据库文件增长到一定大小时，您将停止追加它，创建一个新文件（称为段）并将所有写入重定向到这个新文件。

段是不可变的，因为它们从不用于附加任何新数据。修改段的唯一方法是将其内容写入新文件，可能在两者之间进行一些转换。

因此，压缩会为每个键创建仅包含最新记录的新段。此步骤的另一个可能的增强功能是将多个片段合并为一个片段。当然，压缩和合并可以在后台完成。旧段被扔掉了。

每个段，包括正在写入的段，都有自己的索引。因此，当您想要查找给定键的值时，您可以按时间倒序搜索这些索引：从最近到最旧。

到目前为止，我们的数据结构具有以下优点：

✔️ 顺序写入通常比随机写入快
✔️ 单写进程容易控制并发
✔️ 崩溃恢复很容易实现：只需顺序读取所有段，并将偏移量存储在 in-memory 索引
✔️ 合并和压缩有助于避免数据碎片化

但是，也有一些限制：

❗ 如果段很大而且很多
，崩溃恢复可能是 time-consuming ❗ 哈希索引必须适合内存。实施 on-disk 哈希表要困难得多
❗ 范围查询（BETWEEN）几乎是不可能的

现在，有了这个背景，让我们转到 SSTables 和 LSM-trees。顺便说一下，这些缩写的意思是“排序字符串表”和“Log-Structured 合并树”。

SSTables 与我们之前看到的“数据库”非常相似。唯一的改进是我们要求段中的记录按键排序。这似乎破坏了使用 append-only 写入的能力，但这就是 LSM-Trees 的用途。待会见！

SSTables 比我们以前的那些简单的段有一些优势：

✔️ 由于记录为 pre-sorted，因此合并段更有效。您所要做的就是在每次迭代中比较段“头部”并选择最低的一个。如果多个段包含相同的键，则来自最近段的值将获胜。这个 compact & merge 过程也持有键的排序。

✔️ 键排序后，您不再需要索引中的每个键。如果已知键 B 位于键 A 和 C 之间的某处，您可以进行扫描。这也意味着范围查询是可能的！

最后一个问题是：你如何获得按键排序的数据？

我ea，由 Patrick O'Neil 等人描述。在他们的 "The Log-Structured Merge-Tree (LSM-Tree)", is simple: there are in-memory data structures, such as red-black trees or AVL-trees, that are good at sorting data. So, you split writes into two stages. First, you write the data into the in-memory balanced tree. Second, you flush that tree on the disk. Actually, there may be more than two stages, with deeper ones being bigger and "slower" then the upper (as ).

写入时，将其添加到 in-memory 平衡树，称为 memtable。
当内存表变大时，它会被刷新到磁盘。已经排序好了，自然就创建了一个SSTable段。
同时，写入由新的内存表处理。
读取首先在 memtable 中查找，然后在段中，从最近的到最旧的开始。
如前所述，分段会不时在后台压缩和合并。

该方案并不完美，它可能会突然崩溃：作为 in-memory 数据结构的 memtable 丢失了。这个问题可以通过维护另一个基本上复制内存表内容的 append-only 文件来解决。数据库只需要在崩溃后读取它到 re-create 内存表。

就是这样！请注意，上面描述的简单 append-only 存储的所有问题现在都已解决：

✔️ 崩溃时只有一个文件可以读取：内存表备份
✔️ 索引可以是稀疏的，因此更容易适应 RAM
✔️ 现在可以进行范围查询

TLDR：SSTable 是 key-sorted append-only key-value 存储。 LSM-tree 是一种基于平衡树的分层数据结构，它允许 SSTable 存在而不会同时被排序和 append-only 的争议。

恭喜，您已经读完了这篇长文！如果您喜欢这个解释，请确保不仅要为这个 post 投票，还要为 the Martin's answers here 中的一些投票。记住：所有学分都归于他！

术语 SSTable 和 LSM Tree 之间有什么区别

What is the differences between the term SSTable and LSM Tree

database

indexing

lsm-tree