20

Are these two terms used interchangeably?

I have read about how SSTable works, and usually, articles just start mentioning LSM Tree. However, they seem to be the same thing.

When should I use one term over the other?

4

4 回答 4

12

在基于 LSM 的存储技术中对此进行了很好的解释：第 1 节和第 2.2.1 节中的调查论文

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

SSTable由上述论文解释：

一个SSTable（Sorted String Table）包含一个数据块列表和一个索引块；一个数据块存储按键排序的键值对，索引块存储所有数据块的键范围。

于 2020-03-03T22:21:16.513 回答
6

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

在此处输入图像描述

但是，LSM 树不同：

在计算机科学中，日志结构的合并树（或 LSM 树）是一种具有性能特征的数据结构，这使得它在为具有高插入量的文件（例如事务日志数据）提供索引访问方面具有吸引力。LSM 树与其他搜索树一样，维护键值对。LSM 树将数据保存在两个或多个独立的结构中，每个结构都针对其各自的底层存储介质进行了优化；数据在两个结构之间有效地批量同步。

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

https://upload.wikimedia.org/wikipedia/commons/f/f2/LSM_Tree.png

于 2019-09-30T14:05:41.727 回答
2

Martin Kleppmann在他的“设计数据密集型应用程序”一书中给出了对 SSTables 和 LSM-Trees 的最佳解释之一。这些数据结构在第 3 章“存储和检索”，第 69 到 79 页中进行了解释。这是一本非常棒的读物，我会推荐整本书！

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

一切都从一个非常愚蠢的键值数据库开始，它只实现了两个 Bash 函数：

db_set () {
    echo "$1,$2" >> database
}

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

这个想法是将数据存储在类似 CSV 的文件中：

$ 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 处理存储效率。将数据附加到数据库文件会很快耗尽磁盘空间。您拥有的不同键越少 - 这个仅附加存储引擎的效率就越低。这个问题的解决方案是压缩：

压实

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

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

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

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

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

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

但是，也有一些限制：

❗ 如果段很大且数量众多，崩溃恢复可能会很耗时
❗ 哈希索引必须适合内存。实现磁盘哈希表要困难
得多❗ 范围查询 ( BETWEEN) 几乎是不可能的

现在，有了这个背景，让我们转到 SSTables 和 LSM-trees。顺便说一句，这些缩写相应地表示“排序字符串表”和“日志结构合并树”。

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

与我们之前的那些简单段相比，SSTables 有一些优势：

✔️ 由于记录已预先排序，因此合并段更有效。您所要做的就是在每次迭代中比较段“头”并选择最低的一个。如果多个段包含相同的键，则最近段中的值获胜。这个紧凑和合并过程还包含键的排序。

SSTable 紧凑和合并

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

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

这个想法，由 Patrick O'Neil 等人描述。在他们的“The Log-Structured Merge-Tree (LSM-Tree)”中，很简单：内存中的数据结构，例如红黑树或 AVL 树，它们擅长对数据进行排序。因此，您将写入分为两个阶段。首先，将数据写入内存平衡树。其次，刷新磁盘上的树。实际上，可能有两个以上的阶段，较深的阶段更大并且比上层“慢”（如另一个答案所示）。

  1. 当写入发生时，您将其添加到内存平衡树中，称为 memtable。
  2. 当 memtable 变大时，它会被刷新到磁盘。它已经排序，所以它自然会创建一个 SSTable 段。
  3. 同时，写入由一个新的内存表处理。
  4. 首先在内存表中查找读取，然后在段中查找，从最近的到最旧的。
  5. 如前所述，段在后台不时被压缩和合并。

该方案并不完美，它可能会突然崩溃：作为内存数据结构的 memtable 丢失了。这个问题可以通过维护另一个基本上复制 memtable 内容的仅附加文件来解决。数据库只需要在崩溃后读取它以重新创建 memtable。

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

✔️现在在崩溃的情况下只有一个文件可以读取：memtable备份
✔️索引可能是稀疏的，因此更容易
适应RAM✔️范围查询现在是可能的

TLDR：SSTable 是键排序的仅追加键值存储。LSM-tree 是一种基于平衡树的分层数据结构，它允许 SSTables 存在而不会同时存在排序和仅追加的争议。

恭喜，你读完了这篇长篇大论！如果您喜欢这个解释，请确保不仅支持这篇文章，还支持Martin 的一些答案。请记住：所有学分都归他所有！

于 2022-02-14T01:43:42.743 回答
1

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

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

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

于 2022-01-02T17:39:49.523 回答