异地更新相较于原地更新，具有极佳的写入性能，但同时也牺牲了读取性能。
译自 How Database Storage Engines Have Evolved for Internet Scale，作者 Srinivasan Seshadri。
数据库存储引擎的设计对其性能至关重要。几十年来，SQL 和 NoSQL 数据库已经开发出各种技术来优化数据的存储和检索。
数据库存储引擎已经从早期的关系型系统发展到现代的分布式SQL和NoSQL 数据库。早期的关系型系统依赖于对记录的原地更新，而现代系统——无论是分布式关系数据库还是 NoSQL 数据库——主要使用非原地更新。“记录”一词用于指关系数据库中的元组以及 NoSQL 存储中的键值对。
随着互联网规模的用户事件以及来自传感器的自动化事件（例如，物联网）涌入数据库，现代数据库遇到了极其繁重的写入工作负载，非原地更新因此变得流行。
这两种对比鲜明的方法——原地更新和非原地更新——表明，相对于原地更新，非原地更新可以带来极佳的写入性能，但代价是牺牲读取性能。
让我们从存储引擎的分层架构概述开始。数据库存储引擎通常由三层组成：
- 块存储: 基础层，通过原始设备、文件系统或云存储提供块级访问。数据库组织这些块以实现可扩展的数据存储。
- 记录存储: 建立在块存储之上，此层将记录组织成块，从而实现表或命名空间扫描。早期的关系型系统通常原地更新记录，而较新的存储引擎则使用非原地更新。
- 访问方法: 最顶层包括主索引和辅助索引，从而实现高效的数据检索。访问方法的更新也可以是原地更新或非原地更新，我们很快就会看到。许多当前的系统对记录存储和访问方法都采用相同的方法，即原地更新或非原地更新。因此，我们将一起讨论这两层如何在更新方面进行处理。
让我们更深入地研究每一层。
核心是，块存储层将数据组织成称为块（下图 1 中的 B1 和 B2）的可管理单元。这些块充当基本存储单元，更高层将它们组织起来以满足数据库的要求。图 1 说明了一个基本的块存储系统。记录存储和访问方法建立在块存储之上。记录存储和访问方法有两大类，分别对应于更新是否原地进行。接下来我们将描述这两类下的记录存储和访问方法。
图 1：显示块 B1 和 B2 的块存储。
原地更新记录和访问方法是早期关系数据库的标准方法。下图 2 说明了此类系统中的块是如何组织和管理以提供记录存储 API 的。此类记录存储层的显著特征包括：
- 变长记录: 记录的长度经常变化，并且大小在更新期间可能会改变。为了最大限度地减少更新期间的额外IO操作，记录存储层主动管理块空间以适应块内的更新。
- 一级间接寻址: 块中的每个记录都由一个槽号标识，使记录ID (RID) 成为块ID和槽号的组合。这种间接寻址允许记录在块内自由移动而无需更改其RID。
- 槽图: 槽图跟踪块内每个记录的物理位置。它从块的开头开始增长，而记录从结尾开始增长，在两者之间留下空闲空间。这种设计允许块根据记录的大小容纳可变数量的记录，并支持在可用空间内动态调整记录的大小。
- 记录迁移: 当记录增长到超过其原始块的大小限制时，它将被移动到一个新的块，导致其RID发生变化。
图2：就地更新的记录存储，显示块的内部组织方式。
访问方法构建在记录存储之上，以有效地检索记录。它们包括：
- 主键索引: 这些索引将主键字段映射到其对应的RID。
- 二级索引: 这些索引将其他字段值（可能由多个记录共享）映射到其RID。
如果索引完全在内存中，则使用自平衡树，例如红黑树；如果索引主要在磁盘上（部分可能缓存在内存中），则使用B+树。图3显示了记录存储之上的B+树。主键索引和二级索引的条目格式（字段值和RID）相同。
图3：记录存储之上的B+树。
访问方法和记录存储的组合
在某些系统中，访问方法和记录存储层通过将数据直接嵌入B+树的叶节点中来集成。然后，叶级本质上成为一个记录存储，但现在也按索引键排序。由于这种组合，与未排序的记录存储层相比，范围查询的效率更高。但是，要使用其他键访问记录，我们仍然需要在此组合存储层之上使用访问方法（其他键上的索引）。
大多数现代存储引擎，包括分布式NoSQL和分布式SQL引擎，都使用非就地更新。在这种方法中，所有更新都附加到内存中维护的当前写入块，然后在块填满时一次性刷新到磁盘。请注意，如果此节点发生故障，则在写入到达磁盘之前数据的持久性将通过分布式数据库中的复制来缓解。块是不可变的，记录只打包和写入一次，消除了空间管理开销。如果需要，旧版本的记录将由清理过程进行垃圾回收。这有两个优点：
- 摊销IO成本: 写入块中的所有记录一起只需要一个IO，而就地更新至少需要每个记录一个IO。
- 利用顺序IO: 这些技术是在磁性硬盘驱动器 (HDD) 时代发明的，顺序IO在HDD中远优于随机IO。但即使在SSD时代，顺序IO仍然相关。这些系统的追加式特性使其适合顺序IO。
最著名和最常用的非就地更新存储引擎形式使用称为日志结构合并树 (LSM-树)的数据结构。事实上，几乎所有现代数据库存储引擎，如BigTable、Dynamo、Cassandra、LevelDB和RocksDB，都使用LSM树。CockroachDB和YugabyteDB等系统采用RocksDB的变体。
LSM树
现代LSM树实现的基础概念源于关于该概念的原始论文，以及同时开发的分步合并方法。
分级合并算法源于一个真实的、关键的需求：1996年管理AT&T网络的全部呼叫量，并记录从美国各地流入的所有呼叫详单（CDR）。那是一个复杂的电话计费计划时代——基于使用量、基于一天中的时间、基于朋友和家人等等。准确记录每个呼叫详单对于未来的计费至关重要。
然而，大量的呼叫量使当时的机器不堪重负，因此产生了将CDR立即追加到记录存储末尾的想法，然后定期“整理”以优化查找以计算账单。账单计算（读取）是批处理作业，没有实时要求，与写入操作不同。
解决上述问题的核心思想是尽可能多地在内存中累积写入，并在内存填满后将其作为级别0的有序运行写入。当有T个级别0的运行可用时，它们全部合并到级别1的更长的有序运行中。在合并过程中，如果需要，可以消除重复项。
这个将级别i的T个有序运行合并以构建级别i+1的更长运行的过程会持续尽可能多的级别，其灵感来自外部排序合并算法。这个想法与最初的LSM树提案非常相似，并且构成了所有现代基于LSM的实现的基础，包括每个级别T个组件的概念。合并过程非常适合顺序IO，写入记录的成本在多个顺序IO操作中为多个记录分摊。
然而，在最坏的情况下，读取必须检查每个级别的每个有序运行，从而导致无法就地更新的惩罚。然而，通过特定于该有序运行的索引（例如B+树）可以有效地查找有序运行中的键。这些B+树直接指向物理位置（而不是RID），因为位置保持不变。图4显示了一个具有三个级别和每个级别T=3个组件的LSM树示例。
有序运行显示为B+树以优化读取操作。请注意，叶级别表示有序运行，而上层级别是从叶级别自下而上构建的（批量加载B+树的标准方法）。在这方面，LSM树可以被认为是访问方法和面向记录的存储结构的组合。虽然排序通常发生在一个键（或多个键的组合）上，但也可能需要通过其他键进行访问的情况，这需要在LSM树之上建立辅助索引。
图4：磁盘上具有三个级别和每个级别三个组件的LSM树示例。
下表比较了早期关系型系统存储引擎与为现代存储引擎开发的存储引擎的关键特性。假设正在写入一条记录，并且正在读取一个主键值。对于早期关系型系统，我们假设在主键上存在B+树索引（叶级别是否包含实际数据或记录标识符（RID）的细节不会显著影响此讨论）。对于LSM树（最常见的现代存储引擎），假设有序运行（和B+树）基于主键。
| 特性 | 早期关系型系统 | 现代存储引擎 |
|---|---|---|
| 写入 | 每条记录至少一个随机IO | IO在许多记录的多个顺序IO操作中分摊，从而允许更高的写入吞吐量。 |
| 读取 | 从单个B+树读取的少量随机IO | 从多个B+树读取的许多随机IO |
| 空间管理 | 需要管理块内的空闲空间 | 无块级空间管理 |
| 垃圾回收 | 不需要，因为被覆盖的记录会立即丢失 | 在级别之间合并期间定期清理 |
| 空间开销 | 数据的开销最小。B+树的正常开销。 | 由于多个版本，数据开销很大。B+树没有开销，因为结构是不可变的并且可以打包。 |
存储引擎已经发展到可以处理许多数据库系统在互联网规模发展中遇到的繁重写入工作负载。LSM 树已成为解决这一繁重写入工作负载挑战的流行方法。然而，相对于早期关系系统中使用的基于 B+ 树的存储引擎，LSM 树确实牺牲了实时读取性能。在某些情况下，找到一个融合这两种理念优点的系统可能是明智的：使用就地更新以外的方式进行记录存储，以便能够继续处理繁重的写入工作负载，但对访问方法使用就地更新以最大限度地减少读取开销。
访问我们的网站，了解更多关于Aerospike 数据库的信息。