数据库之日志结构存储

不可变存储结构不允许对现有文件进行修改:表只写一次，不会再修改。相反，新记录被追加到新文件中，为了找到最终值(或推断其缺失)，必须从多个文件中重新构建记录。相反，可变存储结构在适当位置修改磁盘上的记录。

不可变数据结构经常在函数式编程语言中使用，并且由于其安全特性而变得越来越流行:一旦创建了不可变结构，它就不会改变，它的所有引用都可以并发访问，它的完整性是由它不能被修改这一事实所保证的。

在高层上，在存储结构内部和外部如何处理数据是有严格区别的。在内部，不可变文件可以保存多个副本，较新的副本会覆盖较旧的副本，而可变文件通常只保存最近的值。在访问时，处理不可变文件，协调冗余副本，并将最近的副本返回给客户端。

我们使用B-Tree作为可变结构的典型例子，使用Log-Structured Merge tree (LSM tree)作为不可变结构的例子。不可变LSM树使用仅追加存储和合并协调，而B-Tree在磁盘上定位数据记录，并在文件中的原始偏移量上更新页面。

In-place update存储结构优化读性能:在磁盘上定位数据后，可以将记录返回给客户端。这是以写性能为代价的:要就地更新数据记录，首先必须将其定位在磁盘上。另一方面，仅追加存储为写性能进行了优化。写不必找到磁盘上的记录来覆盖它们。然而，这是以读取为代价的，读取必须检索多个数据记录版本并对它们进行协调。

由于可变B- Tree采用的结构和构造方法，在读、写和维护期间的大多数I/O操作都是随机的。每个写操作首先需要找到保存数据记录的页面，然后才能修改它。B-Tree需要对已经写入的记录进行节点拆分和合并。一段时间后，B-Tree页面可能需要维护。页面的大小是固定的，并且为将来的写保留了一些可用空间。另一个问题是，即使只修改了页面中的一个单元格，也必须重写整个页面。

有一些替代方法可以帮助缓解这些问题，使一些I/O操作按顺序进行，并避免在修改期间重写页面。其中一种方法是使用不可变结构，在本文中，将重点关注LSM树:它们是如何构建的，它们的属性是什么，以及它们与B-Tree的不同之处。

LSM Trees

在讨论B-Tree时，我们得出的结论是，空间开销和写扩展可以通过使用缓冲来提高。通常，有两种方法可以在不同的存储结构中应用缓冲:延迟对磁盘数据库页的写入，以及使写入操作顺序。

LSM Tree是最流行的不可变磁盘存储结构之一，它使用缓冲和仅追加存储来实现顺序写操作。LSM树是磁盘数据库结构的一种变体，类似于b树，其中节点被完全占用，为顺序磁盘访问进行了优化。日志结构的合并树的名称来自日志结构的文件系统，这些文件系统将所有修改写入磁盘上的日志类文件。

LSM树延迟内存数据库表中的数据文件写入和缓冲区更改。然后，通过将更改的内容写入不可变磁盘文件，传播这些更改。在文件完全持久化之前，所有数据记录都可以在内存中访问。

保持数据文件不可变有利于顺序写:数据在磁盘上一次性写入，文件只追加。可变结构可以在单次传递中预分配块(例如，索引顺序访问方法(ISAM) )，但后续访问仍然需要随机读和写。不可变结构允许我们按顺序排列数据记录，以防止碎片。此外，不可变文件具有更高的密度:我们不会为将要稍后写入的数据记录保留任何额外的空间，或者当更新的记录比最初写入的记录需要更多的空间时。

由于文件是不可变的，所以插入、更新和删除操作不需要定位磁盘上的数据记录，这极大地提高了写性能和吞吐量。相反，允许重复内容，并在读取期间解决冲突。LSM树对于写比读更常见的应用程序特别有用，在现代数据密集型系统中，如果数据量和接收速率不断增长，经常会出现这种情况。

读和写在设计上没有交集，因此可以在不需要段锁的情况下读写磁盘上的数据，这大大简化了并发访问。相反，可变结构使用分层锁和闩锁来确保磁盘上的数据结构完整性，并允许多个并发读取器，但要求写入器拥有独占的子树所有权。基于lsm的存储引擎使用数据和索引文件的线性化内存视图，并且只需要保护对管理它们的结构的并发访问。

LSM Tree结构

LSM树由较小的内存数据库组件和较大的磁盘数据库组件组成。要在磁盘上写出不可变的文件内容，必须首先在内存中缓冲它们并对它们的内容进行排序。

内存数据库组件(通常称为memtable)是可变的:它缓冲数据记录并作为读写操作的目标。当Memtable的大小增长到一个可配置的阈值时，Memtable内容将被持久化到磁盘上。Memtable更新不会导致磁盘访问，也没有相关的I/O成本。为了保证数据记录的持久性，需要一个单独的预写日志文件。在向客户端确认操作之前，数据记录被附加到日志中并提交到内存中。

缓冲是在内存中完成的:所有读和写操作都应用于内存数据库表，该表维护一个允许并发访问的排序数据结构，通常是某种形式的内存中排序树，或任何可以提供类似性能特征的数据结构。

磁盘数据库组件是通过将内存中缓冲的内容刷新到磁盘来构建的。磁盘数据库组件仅用于读取:缓存的内容被持久化，文件永远不会被修改。这允许我们从简单操作的角度来考虑:对内存中的表进行写操作，对基于磁盘和内存的表进行读操作，合并操作和文件删除操作。

Two-component LSM Tree

我们区分了双组分LSM树和多组分LSM树。双组件LSM树只有一个磁盘组件，由不可变的段组成。这里的磁盘组件组织为B-Tree，具有100%的节点占用和只读页面。

内存数据库树内容将部分刷新到磁盘上。在刷新期间，对于每个刷新的内存子树，我们在磁盘上找到相应的子树，并将内存数据库段和磁盘数据库子树的合并内容写到磁盘上的新段中。合并前的内存树和磁盘树如图1所示。

在刷新子树之后，被替换的内存数据库子树和磁盘数据库子树将被丢弃，并替换为它们的合并结果，从磁盘数据库树的现有部分可以寻址。图2显示了合并过程的结果，合并过程已经写入到磁盘的新位置，并附加到树的其余部分。

合并可以通过推进迭代器来实现，迭代器可以同步读取磁盘上的叶子节点和内存树中的内容。由于两个源都已排序，为了生成一个已排序的合并结果，我们只需要知道merge过程的每一步中两个迭代器的当前值。

当实现子树合并和刷新时，我们必须确保:

1. 一旦flush进程开始，所有新的写操作都必须转到新的memtable。
2. 在子树刷新期间，磁盘数据库子树和刷新内存数据库子树都必须保持读取的可访问性。
3. 刷新之后，必须以原子方式执行合并内容的发布，以及丢弃未合并的数据库在磁盘和内存中的内容。

Multicomponent LSM Trees

多组件LSM树，它有不止一个磁盘数据库表。在这种情况下，在一次运行中刷新整个memtable内容。

很明显，在多次刷新之后，我们最终会得到多个磁盘数据库表，它们的数量只会随着时间的推移而增长。由于我们并不总是确切地知道哪些表保存了所需的数据记录，所以我们可能必须访问多个文件来定位搜索的数据。

必须从多个来源而不是一个来源读可能会很昂贵。为了缓解这个问题并将表的数量保持在最小，会触发一个称为压缩的定期合并过程。压缩选择几个表，读取它们的内容，合并它们，并将合并后的结果写入新的合并文件。旧表与合并后的新表同时被丢弃。

多组件LSM Tree数据生命周期如图3所示。数据首先在内存数据库组件中进行缓冲。当它变得太大时，它的内容会刷新到磁盘上，以创建磁盘数据库表。之后，将多个表合并在一起以创建更大的表。

In-memory tables

Memtable刷新可以周期性触发，也可以通过使用大小阈值触发。在可以刷新memtable之前，必须对它进行切换:分配一个新的memtable，它成为所有新写的目标，同时旧的memtable移动到刷新状态。这两个步骤必须以原子方式执行。刷新memtable在其内容被完全刷新之前，仍可用于读取。在此之后，旧的memtable将被丢弃，取而代之的是一个新写入的磁盘数据库表，该表可以用于读取。

在图4中，可以看到LSM树的组件，它们之间的关系，以及实现它们之间转换的操作:

• Current memtable

  接收写，服务读。

• Flushing memtable

  用于读取。

• On-disk flush target

  不参与阅读，因为内容不完整。

• Flushed tables

  一旦已刷新的memtable被丢弃，就可用于读取。

• Compacting tables

  目前正在合并磁盘数据库表。

• Compacted tables

  从刷新或其他压缩表创建。

数据已经在内存中进行了排序，因此可以通过将内存数据库的内容依次写入磁盘来创建磁盘数据库表。在刷新期间，刷新的memtable和当前的memtable都可以读取。

在memtable完全刷新之前，其内容的唯一磁盘数据库版本存储在预写日志中。当memtable内容在磁盘上被完全刷新时，可以对日志进行修剪，并且可以丢弃用于保存已刷新memtable的操作的log部分。

Updates and Deletes

在LSM树中，插入、更新和删除操作不需要定位磁盘上的数据记录。相反，冗余记录在读取过程中被调和。

从memtable中删除数据记录是不够的，因为其他磁盘或内存常驻表可能保存相同键的数据记录。如果我们只是通过从memtable中删除项来实现删除，那么最终的删除要么没有影响，要么会恢复以前的值。

让我们考虑一个例子，刷新的磁盘数据库表包含与键k1
关联的数据记录v1
, memtable保存它的新值v2
:

Disk Table        Memtable
| k1 | v1 |       | k1 | v2 |

如果只是从memtable中删除v2
并刷新它，实际上就启用了v1
，因为它成为了与该键相关联的唯一值:

Disk Table        Memtable
| k1 | v1 |       ∅

因此，需要显式地记录删除。这可以通过插入一个特殊的删除条目来实现，该条目指示删除与特定密钥相关联的数据记录:

Disk Table        Memtable
| k1 | v1 |       | k1 | <tombstone> |

有时，删除一个连续的键而不是单个键可能是有用的。这可以使用谓词删除来完成，它的工作方式是将一个删除条目附加到一个根据常规记录排序规则进行排序的谓词。在协调期间，将跳过与谓词匹配的数据记录，而不返回给客户端。

谓词可以采用DELETE FROM table WHERE key ≥ "k2" AND key < "k4"
，并且可以接收任何范围匹配器。Apache Cassandra实现了这种方法，并将其称为range tombstones。一个range tombstones涵盖了一系列的键，而不仅仅是一个单一的键。

在使用range tombstone时，必须仔细考虑解析规则，因为范围和磁盘数据库表边界存在重叠。例如，下面的组合将从最终结果中隐藏与k2
和k3
相关的数据记录:

Disk Table 1      Disk Table 2
| k1 | v1 |       | k2 | <start_tombstone_inclusive> |
| k2 | v2 |       | k4 | <end_tombstone_exclusive>   |
| k3 | v3 |
| k4 | v4 |

LSM Tree Lookups

LSM树由多个组件组成。在查找过程中，通常会访问多个组件，因此必须对它们的内容进行合并和协调，然后才能将它们返回给客户机。为了更好地理解合并过程，让我们看看在合并过程中表是如何迭代的，以及冲突的记录是如何组合的。

Merge-Iteration

由于磁盘数据库表的内容是排序的，所以我们可以使用多路归并排序算法。例如，我们有三个源:两个磁盘数据库表和一个memtable。通常，存储引擎提供游标或迭代器来浏览文件内容。该游标保存上次使用的数据记录的偏移量，可以检查迭代是否已经完成，并可用于检索下一个数据记录。

多路合并排序使用优先级队列，如min-heap，最多可保存N
个元素(其中N
是迭代器的数量)，它对其内容进行排序，并准备返回下一个行内最小的元素。每个迭代器的头被放入队列中。队列头的元素是所有迭代器中最小的。

当最小的元素从队列中移除时，将检查与之关联的迭代器，以查找下一个值，然后将该值放入队列，并重新排序以保持队列的顺序。

由于所有迭代器内容都已排序，因此从包含所有迭代器头的前一个最小值的迭代器中重新插入一个值也会保留不变式，即队列仍然保存所有迭代器的最小元素。当一个迭代器耗尽时，算法继续执行，而不重新插入下一个迭代器头。算法继续执行，直到满足查询条件或耗尽所有迭代器。

图5显示了刚才描述的合并过程的示意图:头元素被放置到优先队列中。优先级队列中的元素返回给输出迭代器。结果输出是排序的。

在合并迭代期间，我们可能会遇到同一个键的多个数据记录。从优先队列和迭代器不变性中，我们知道，如果每个迭代器只保存每个键的单个数据记录，并且队列中有多个针对同一键的记录，那么这些数据记录一定来自不同的迭代器。

作为输入数据，我们在两个磁盘上的表上有迭代器:

Iterator 1:         Iterator 2:
{k2: v1} {k4: v2}   {k1: v3} {k2: v4} {k3: v5}

优先级队列由迭代器头填充:

Iterator 1:         Iterator 2:         Priority queue:
{k4: v2}            {k2: v4} {k3: v5}   {k1: v3} {k2: v1}

Key k1
是队列中最小的键，并被附加到结果中。因为它来自Interator 2
，所以我们用它重新填充队列:

Iterator 1:         Iterator 2:         Priority queue:      Merged Result:
{k4: v2}            {k3: v5}            {k2: v1} {k2: v4}    {k1: v3}

现在，队列中有两条k2
键的记录。由于上述的不变性，我们可以确定在任何迭代器中都没有其他具有相同键的记录。将同键记录合并并附加到合并结果中。

队列被两个迭代器的数据填充:

Iterator 1:         Iterator 2:         Priority queue:      Merged Result:
{}                  {}                  {k3: v5} {k4: v2}    {k1: v3} {k2: v4}

由于所有迭代器现在都是空的，我们将剩余的队列内容附加到输出:

Merged Result:
  {k1: v3} {k2: v4} {k3: v5} {k4: v2}

总之，创建组合迭代器必须重复以下步骤:

1. 首先，用每个迭代器的第一个项填充队列。
2. 从队列中取最小的元素(头)。
3. 从相应的迭代器重新填充队列，除非该迭代器已耗尽。

就复杂性而言，合并迭代器与合并排序集合相同。它有O(N)
内存开销，其中N
是迭代器的数量。一个排序的迭代器头集合以O(log N)
进行维护。

Reconciliation

合并迭代只是为了合并来自多个数据源的数据而必须做的一个方面。另一个重要方面是与相同键相关联的数据记录的协调和冲突解决。

不同的表可能保存相同键的数据记录，比如更新和删除，它们的内容必须协调一致。前面示例中的优先队列实现必须能够允许与同一键关联的多个值并触发协调。

为了协调数据记录，我们需要了解其中哪个优先。数据记录保存了所需的元数据，比如时间戳。为了建立来自多个来源的项目之间的顺序，并找出哪个是最近的，我们可以比较它们的时间戳。

由时间戳更高的记录所隐藏的记录不会返回给客户端，也不会在压缩期间写入。

Maintenance in LSM Trees

与可变的B-Tree类似，LSM树也需要维护。这些过程的性质很大程度上受到算法保留的不变性的影响。

在B-Tree中，维护过程收集未引用的单元格并对页面进行碎片整理，回收被删除和隐藏的记录所占用的空间。在LSM树中，磁盘数据库表的数量在不断增长，但可以通过触发周期性压缩来减少。

压缩选择多个磁盘数据库表，使用前面提到的合并和协调算法遍历它们的全部内容，并将结果写入新创建的表中。

由于磁盘数据库的表内容是排序的，而且由于合并排序的工作方式，压缩有一个理论上的内存使用上限，因为它应该只在内存中保存迭代器头。所有表内容都按顺序使用，合并后的数据也按顺序写出来。由于额外的优化，这些细节可能在实现之间有所不同。

压缩表在压缩过程结束之前对读都是可用的，这意味着在压缩期间，需要在磁盘上有足够的可用空间来写入压缩表。

在任何给定的时间，系统中都可以执行多个压缩。然而，这些并发压缩通常在非交叉的表集上工作。压缩编写器既可以将多个表合并为一个表，也可以将一个表划分为多个表。

Leveled compaction

压缩为优化提供了多种机会，并且有许多不同的压缩策略。一种经常实现的压缩策略称为水平压缩。

水平压缩将磁盘数据库表划分为不同的级别。每一层的表都有目标大小，每一层都有相应的索引号(标识符)。

Level-0表是通过刷新memtable内容创建的。Level-0的表可能包含重叠的关键字范围。一旦Level-0上的表数量达到阈值，就会合并它们的内容，为Level-1创建新的表。

Level-1上的表和具有更高索引的所有级别上的表的键范围不重叠，因此Level-0的表必须在压缩期间进行分区，分成范围，并与包含相应键范围的表合并。或者，压缩可以包括所有的Level-0和Level-1表，以及输出分区的Level-1表。

具有较高索引级别上的压缩从范围重叠的两个连续级别中选择表，并在较高级别上生成新表。图6示意了如何在各级之间迁移数据。压缩Level-1和Level-2表的过程将在Level-2上生成一个新表。根据表的分区方式，可以从一个级别中选择多个表进行压缩。

在不同的表中保持不同的键范围可以减少读取期间访问的表数量。这是通过检查表元数据并过滤掉范围不包含搜索键的表来实现的。

每个级别都有表大小和表的最大数目的限制。一旦Level-1或任何级别上索引更高的表的数量达到阈值，当前级别的表就会与下一级别的表合并，这些表拥有重叠的键范围。

级别之间的大小呈指数级增长:每一级别上的表都比上一级别上的表大。这样，最新的数据总是在索引最低的那一层，而较旧的数据则逐渐迁移到较高的那一层。

Size-tiered compaction

另一种流行的压缩策略称Size-tiered compaction。在Size-tiered压缩中，不是根据级别对磁盘数据库表进行分组，而是按大小分组:小表与小表分组，大表与大表分组。

Level-0保存从memtable刷新或由压缩过程创建的最小表。当表被压缩时，合并后的表被写入到拥有相应大小的表的级别。这个过程继续递归地增加级别，压缩和提升较大的表到更高的级别，并将较小的表降级到更低的级别。

还有其他常见实现的压缩策略可以针对不同的工作负载进行优化。例如，Apache Cassandra还实现了时间窗口压缩策略，这对于设置了生存时间的记录的时间序列工作负载特别有用。

时间窗口压缩策略将写入时间戳考虑在内，并允许删除保存已过期时间范围内数据的整个文件，而无需压缩和重写其内容。

读、写、空间放大

在实现最佳压缩策略时，必须考虑多个因素。一种方法是回收重复记录占用的空间，减少空间开销，这将导致不断重写表导致更高的写放大。另一种方法是避免连续地重写数据，这将增加读放大(在读过程中协调与相同键相关联的数据记录的开销)和空间放大(因为冗余记录会保留更长的时间)。

总之，当以不可变的方式将数据存储在磁盘上时，面临三个问题:

• Read amplification

  由于需要处理多个表来检索数据而产生的。

• Write amplification

  是由于压缩过程中不断重写造成的。

• Space amplification

  因存储与同一键相关联的多条记录而产生。

RUM Conjecture

一种流行的存储结构成本模型考虑了三个因素:读取、更新和内存开销。它被称为RUM Conjecture。

RUM Conjecture指出，减少其中两个开销不可避免地会导致第三个开销变得更糟，而优化只能以牺牲三个参数中的一个为代价。我们可以根据这三个参数比较不同的存储引擎，以了解它们优化哪些，以及这可能意味着哪些潜在的折衷。

理想的解决方案应该提供最低的读成本，同时保持较低的内存和写开销，但在现实中，这是无法实现的，我们需要权衡。

B-Tree读取最优化，对B-Tree的写操作需要定位磁盘上的记录，随后对同一页的写操作可能需要多次更新磁盘上的页。为将来的更新和删除保留额外的空间会增加空间开销。

LSM树不需要在写入期间将记录定位到磁盘上，也不为将来的写入预留额外的空间。存储冗余记录仍然会带来一些空间开销。在默认配置中，读取开销更大，因为必须访问多个表才能返回完整的结果。

这个成本模型并不完美，因为它没有考虑其他重要的指标，如延迟、访问模式、实现复杂性、维护开销和硬件相关的细节。对分布式数据库很重要的高级概念，如一致性影响和复制开销，也没有考虑。然而，这个模型可以作为第一近似和经验法则，因为它有助于理解存储引擎提供的内容。

Sorted String Tables

磁盘数据库表通常使用排序字符串表(SSTables)实现。顾名思义，SSTables中的数据记录是按照关键顺序进行排序和布局的。SSTables通常由两部分组成:索引文件和数据文件。索引文件使用一些允许对数查找(如B-Tree)或常量时间查找(如散列表)的结构实现。

从数据文件记录关键顺序,使用哈希索引并不阻止我们实现扫描范围,作为一个散列表只是访问定位的第一个键的范围,范围和本身可以从数据文件读取顺序而仍然范围谓词匹配。

索引组件保存键和数据项(实际数据记录所在的数据文件中的偏移量)。数据组件由连接的键值对组成。前面讨论的单元设计和数据记录格式在很大程度上适用于SSTables。这里的主要区别是，单元格是按顺序写入的，在SSTable的生命周期中不会被修改。由于索引文件保存了指向存储在数据文件中的数据记录的指针，因此在创建索引时必须知道它们的偏移量。

在压缩过程中，可以顺序读取数据文件，而不需要寻址索引组件，因为其中的数据记录已经排序。由于在压缩过程中合并的表具有相同的顺序，并且合并迭代是保留顺序的，因此合并后的表也是通过在一次运行中顺序地写入数据记录来创建的。一旦文件被完全写入，它就被认为是不可变的，并且它的磁盘驻留内容不会被修改。

Bloom Filters

LSM树中读取放大的原因是，为了完成读取操作，我们必须对多个磁盘驻留表进行寻址。发生这种情况是因为我们并不总是事先知道磁盘数据库表是否包含搜索键的数据记录。

防止表查找的一种方法是将其键范围(存储在给定表中的最小和最大键)存储在元数据中，并检查搜索的键是否属于该表的范围。这个信息是不精确的，只能告诉我们数据记录是否可以出现在表格中。为了改善这种情况，有许多方案，包括Apache Cassandra和RocksDB，都使用了一种叫做Bloom Filter的数据结构。

Bloom Filter是一种空间效率高的概率数据结构，可用于测试元素是否为集合中的成员。可以使用Bloom Filter来判断键是否在表中，或者肯定不在表中。在查询期间，将跳过Bloom Filter返回负匹配的文件。访问其余的文件以确定数据记录是否实际存在。使用与磁盘数据库表关联的Bloom Filter有助于显著减少读取期间访问的表数量。

Bloom Filter使用一个大的位数组和多个散列函数。哈希函数应用于表中记录的键，以查找位数组中的索引，位数组的位被设置为1
。在哈希函数确定的所有位置上设置为1
的位表示该键在集合中存在。在查找过程中，当在Bloom Filter中检查元素是否存在时，将再次计算该键的哈希函数，如果所有哈希函数确定的位为1
，则返回正结果，说明该项是具有一定概率的集合中的成员。如果至少有一个位是0
，我们就可以准确地说该元素不在集合中。

应用于不同键的哈希函数可以返回相同的位位置并导致哈希冲突，1
位只意味着某个哈希函数为某个键提供了这个位位置。

让我们看一个简单的例子，如图7所示。我们有一个16位数组和3个哈希函数，它们为key1
生成值3
、5
和10
。现在我们在这些位置上设置位。添加下一个键，散列函数对key2
产生5
、8
和14
的值，我们也为它们设置了位。

现在，我们试图检查key3
是否存在于集合中，散列函数会产生3
、10
和14
。由于在添加key1
和key2
时设置了所有三个位，因此我们有这样一种情况:Bloom Filter返回假阳性:key3
从未被添加到那里，但所有计算的位都被设置了。但是，由于Bloom Filter只声明元素可能在表中，所以这个结果是可以接受的。

如果我们尝试对key4
执行查找并接收5
、9
和15
的值，我们会发现只有第5
位设置了，而其他两个位没有设置。如果甚至有一个位未设置，我们就可以确定元素从未被添加到过滤器中。

Skiplist

有许多不同的数据结构用于在内存中保存已排序的数据，最近由于其简单性而越来越受欢迎的一种结构被称为skiplist。在实现方面，skiplist并不比单链列表复杂多少，它的概率复杂度保证接近于搜索树。

Skiplists不需要对插入和更新进行旋转或重定位，而是使用概率平衡。与内存中的bB-Tree相比，skiplist通常对缓存不友好，因为skiplist节点很小，并且在内存中随机分配。一些实现通过使用展开链表来改善这种情况。

skiplist由一系列不同高度的节点组成，构建了允许跳过项目范围的链接层次结构。每个节点都持有一个键，并且，与链表中的节点不同，有些节点有不止一个后续节点。一个高度为h
的节点可以从一个或多个高度相同的前一级节点连接到h
。最低一级节点可以从任意高度的节点连接到h
。

节点高度由一个随机函数决定，并在插入期间计算。具有相同高度的节点构成一个级别。关卡的数量是有上限的，以避免无限增长，最大高度是根据结构所能容纳的物品的数量来选择的。每一层的节点都呈指数级减少。

查找通过在最高级别上跟踪节点指针进行。一旦搜索遇到持有大于搜索的键的节点，它的上一级节点的链接就会被跟随。换句话说，如果搜索的键大于当前节点键，则继续向前搜索。如果搜索的关键字小于当前节点的关键字，则从上一级节点继续搜索。这个过程递归地重复，直到找到搜索的键或它的前身。

以在图8所示的skiplist中搜索“7”为例，操作步骤如下:

1. 沿着最高层的指针，找到持有键10
   的节点。
2. 因为搜索的键7
   小于10
   ，所以从头节点开始的下一层指针被跟踪，定位一个持有键5
   的节点。
3. 接着该节点上的最高级别指针，再次定位持有键10
   的节点。
4. 搜索到的键7
   小于10
   ，然后跟随持有键5
   的节点的下一级指针，找到持有搜索到的键7
   的节点。

在插入期间，使用上述算法找到插入点(持有密钥或其前身的节点)，并创建一个新节点。为了构建树状层次结构并保持平衡，节点的高度使用基于概率分布生成的随机数确定。先前节点中的指针持有的键比新创建的节点中的键小，将被链接到该节点。它们的高级指针保持不变。新创建节点中的指针被链接到每一层对应的后继节点。

在删除过程中，被删除节点的前向指针将被放置到相应级别的前一级节点。

我们可以通过实现一个线性化方案来创建skiplist的并发版本，该方案使用一个额外的全链接标志来确定节点指针是否被完全更新。这个标志可以使用比较和交换来设置。这是必需的，因为节点指针必须在多个级别上更新，才能完全恢复skiplist结构。

在使用非托管内存模型的语言中，引用计数或危险指针可以用来确保当前引用的节点在并发访问时不会被释放。这个算法是无死锁的，因为总是从更高的层次访问节点。

Disk Access

由于大多数表内容都驻留在磁盘上，而且存储设备通常允许按块方式访问数据，因此许多LSM树实现依赖页缓存来进行磁盘访问和中间缓存。“缓冲区管理”中描述的许多技术，如页面清除和固定，仍然适用于日志结构存储。

最显著的区别是内存中的内容是不可变的，因此在并发访问时不需要额外的锁或闩锁。引用计数用于确保当前访问的页面不会从内存中被逐出，并且在压缩期间删除基础文件之前完成正在进行的请求。

另一个区别是LSM树中的数据记录不一定是页面对齐的，指针可以使用绝对偏移量而不是页面id来实现寻址。在图9中，可以看到内容与磁盘块没有对齐的记录。有些记录跨越页面边界，需要在内存中加载多个页面。

Compression

LSM Tree表是不可变的，并且通常只编写一次。当按页压缩数据时，压缩的页不会按页对齐，因为它们的大小小于未压缩的页。

为了能够对压缩页面进行寻址，我们需要在编写内容时跟踪地址边界。我们可以用0填充压缩的页面，将它们与页面大小对齐，但这样就失去了压缩的好处。

为了使压缩页可寻址，我们需要一个间接层来存储压缩页的偏移量和大小。压缩块与未压缩块的对应关系如图10所示。压缩后的页面总是比原始页面小，否则压缩它们就没有意义了。

在压缩和刷新期间，压缩页会依次追加，压缩信息(原始未压缩页偏移量和实际压缩页偏移量)存储在单独的文件段中。在读取过程中，将查找压缩页偏移量及其大小，并在内存中对页进行解压缩和物化。

总结

日志结构存储无处不在:从flash转换层到文件系统和数据库系统。它通过在内存中批处理小的随机写来帮助减少写的放大。为了回收被删除的段所占用的空间，LSS定期触发垃圾回收。

LSM树借鉴了LSS的一些思想，并帮助构建以日志结构方式管理的索引结构:写在内存中批处理，在磁盘上刷新;压缩过程中会清除隐藏的数据记录。

重要的是要记住，许多软件层都使用LSS，并确保层的堆叠是最优的。或者，我们可以跳过文件系统层，直接访问硬件。

感兴趣的关注如下公众号！