数据库有很多种（截至 2023 年 4 月有 897 个）。面对如此多的数据库，很难知道该选择什么！但有一个有趣的现象，互联网集体决定新应用程序的默认选择。在 2000 年代，传统观点选择 MySQL 是因为像 Google 和 Facebook 这样的新兴科技明星都在使用它。然后在 2010 年代，它是 MongoDB，因为非持久 non-durable writes 写入使其成为“具有可扩展性和敏捷性的 Web-Scale”。在过去五年中，PostgreSQL 已成为互联网上的宠儿 DBMS。并且有充分的理由！它可靠、功能丰富、可扩展，并且非常适合大多数操作工作负载。
尽管 OtterTune 非常喜欢 PostgreSQL，但它的某些方面并不是很好。因此，我们不想像其他人一样再写一篇博客文章来宣扬每个人最喜欢的大象主题(postgresql logo是一个大象) DBMS 的强大功能，而是想讨论一件很糟糕的事情：PostgreSQL 如何实现多版本并发控制 (MVCC)。我们在卡内基梅隆大学的研究以及在 Amazon RDS 上优化 PostgreSQL 数据库实例的经验表明，其 MVCC 实现相对于其他广泛使用的关系 DBMS（包括 MySQL、Oracle 和 Microsoft SQL Server）中最差的。是的，亚马逊的 PostgreSQL Aurora 仍然存在这些问题。
在本文中，我们将深入探讨 MVCC：它是什么、PostgreSQL 是如何实现的，以及为什么它很糟糕。 OtterTune 的目标是减少您对数据库的担忧，因此我们对解决这个问题进行了很多思考。我们将在下周的后续文章中介绍 OtterTune 针对 RDS 和 Aurora 数据库自动管理 PostgreSQL MVCC 问题的解决方案。
什么是多版本并发控制？
DBMS 中 MVCC 的目标是允许多个查询同时读取和写入数据库，而不会在可能的情况下相互干扰。 MVCC 的基本思想是 DBMS 永远不会覆盖现有的行。相反，对于每个（逻辑）行，DBMS 维护多个（物理）版本。当应用程序执行查询时，DBMS 根据某些版本号排序（例如创建时间戳）确定要检索哪个版本来满足请求。这种方法的好处是多个查询可以读取旧版本的行，而不会被另一个更新它的操作阻止。当 DBMS 启动该查询的事务时，查询会观察数据库的快照（快照隔离）。这种方法消除了显式记录锁record locks的需要，显式记录锁会在写入者修改同一项目时阻止读取者访问数据。
David Reed 1978 年获得麻省理工学院博士学位，学界认为他的论文“分布式数据库系统中的并发控制”是第一篇描述 MVCC 的出版物。 MVCC 的第一个商业 DBMS 实现是 20 世纪 80 年代的 InterBase。从那时起，过去二十年中创建的几乎所有支持事务的新 DBMS 都实现了 MVCC。
系统工程师在构建支持 MVCC 的 DBMS 时必须做出多项设计决策。从较高的层面来看，它可以归结为以下几点：
- 如何存储对现有行的更新。
- 如何在运行时查找查询的正确行版本。
- 如何删除不再可见的过期版本。
这些决定并不相互排斥。就 PostgreSQL 而言，正是他们在 20 世纪 80 年代决定处理第一个问题的方式导致了我们今天仍然需要处理的另外两个问题。
在下面讨论中，我们将使用以下包含电影信息的表 作为示例。表中的每一行都包含电影名称、发行年份、导演和作为主键的唯一 ID，以及电影名称和导演的辅助索引。以下是创建该表的 DDL 命令：
CREATE TABLE movies (
id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
name VARCHAR(256) NOT NULL,
year SMALLINT NOT NULL,
director VARCHAR(128)
);
CREATE INDEX idx_name ON movies (name);
CREATE INDEX idx_director ON movies (director);
该表包含一个主索引 ( movies_pkey ) 和两个B+Tree辅助索引 ( idx_name 、 idx_director )。
PostgreSQL的多版本并发控制
正如 Stonebraker 1987 年的系统设计文档中所讨论的那样，PostgreSQL 从一开始就是为了支持多版本而设计的。 PostgreSQL MVCC 方案的核心思想看似简单：当sql更新表中的现有行时，DBMS 会复制该行并将更改应用于此新版本，而不是覆盖原始行。我们将这种方法称为 仅附加(append-only) 版本存储方案。但正如我们现在所描述的，这种方法对系统的其余部分有一些重要的影响。
Multi-Versioned Storage 多版本存储
PostgreSQL 将所有 行版本 存储在同一存储空间的表中。要更新现有元组，DBMS 首先从表中获取新行版本的空槽。然后，它将当前版本的行内容复制到新版本，并将修改应用于新分配的版本槽中的行。您可以在下面的示例中看到这个过程，当应用程序对电影数据库执行更新查询以将“Shaolin and Wu Tang”的发行年份从 1985 年更改为 1983 年时：
当 UPDATE 语句更改表中的元组时，PostgreSQL 会复制该元组的原始版本，然后将更改应用到新版本。在此示例中，表页 #1 中没有更多空间，因此 PostgreSQL 在表页 #2 中创建新版本。
现在，两个物理版本代表同一逻辑行，DBMS 需要记录这些版本的沿袭历史，以便知道将来如何找到它们。 MVCC DBMS 通过单链表创建版本链来实现这一点。版本链仅朝一个方向延伸，以减少存储和维护开销。这意味着 DBMS 必须决定使用什么顺序：最新到最旧 (newest-to-oldest，N2O) 顺序或最旧到最新 (oldest-to-newest，O2N)。对于 N2O 顺序，每个元组版本都指向其先前版本，并且版本链的头部始终是最新版本。对于O2N顺序，每个元组版本都指向其新版本，而头部是最旧的元组版本。 O2N 方法避免了 DBMS 在每次修改元组时更新索引以指向更新版本的元组。但是，DBMS 在查询处理过程中可能需要更长的时间才能找到最新版本，可能会遍历很长的版本链。大多数 DBMS（包括 Oracle 和 MySQL）都实现了 N2O。但 PostgreSQL 在使用 O2N 方面是独一无二的（除了 Microsoft 用于 SQL Server 的内存 OLTP 引擎）。
下一个问题是 PostgreSQL 如何确定为这些 版本指针 记录什么。 PostgreSQL 中每一行的标头包含下一个版本的元组 id 字段 (t_tcid)（如果是最新版本，则包含其自己的元组 id）。因此，如下一个示例所示，当查询请求行的最新版本时，DBMS 会遍历索引，找到最旧的版本，然后跟踪指针，直到找到所需的版本。
SELECT 查询遍历 索引 以查找 匹配请求的电影名称的元组。索引条目 指向元组的 最旧版本，这意味着 PostgreSQL 遵循原始版本中嵌入的版本链来查找新版本。
PostgreSQL 开发人员很早就意识到其 MVCC 方案存在两个问题。首先，每次更新时复制整个元组的新副本是昂贵的。其次，遍历整个版本链只是为了找到最新版本（这是大多数查询想要的）是浪费的。当然，还存在清理旧版本的问题，我们将在下面介绍。
为了避免遍历整个版本链，PostgreSQL 为行的 每个物理版本 在表的索引中添加一个条目。这意味着如果逻辑行有五个物理版本，则索引中该元组将有（最多）五个条目！在下面的示例中，我们看到 idx_name 索引包含位于不同页面上的每个“Shaolin and Wu Tang”行的条目。这样就可以直接访问元组的最新版本，而无需遍历长版本链。
在此示例中，索引包含“Shaolin and Wu Tang”元组的多个条目（每个版本一个）。现在，PostgreSQL 使用索引来查找最新版本，然后立即从表页#2 中检索它，而无需遍历从表页#1 开始遍历版本链。
PostgreSQL 尝试通过在与 旧版本相同的磁盘页面（块）中创建新副本来减少磁盘 I/O，从而避免安装多个索引条目并在多个页面上存储相关版本。这种优化称为仅堆元组 (heap-only tuple (HOT)) 更新。如果更新不修改 表索引 引用的任何列，并且新版本与旧版本存储在 同一 数据页上（如果该页中有空间），那么 DBMS 将使用 HOT 方法。现在在我们的示例中，更新后索引仍然指向旧版本，并且查询通过遍历版本链来检索最新版本。在正常操作期间，PostgreSQL 通过删除旧版本来修剪版本链来进一步优化此过程。
版本清除(Version Vacuum )
我们已经确定，只要应用程序更新行，PostgreSQL 就会创建行的副本。下一个问题是系统如何删除旧版本（称为“死元组”）。 20 世纪 80 年代的 PostgreSQL 原始版本并没有删除死元组。这个想法是，保留所有旧版本允许应用程序执行“时间旅行”查询来检查特定时间点的数据库（例如，在数据库状态运行 SELECT 查询）于上周末存在）。但从不删除死元组意味着如果应用程序删除元组，表的大小永远不会缩小。这也意味着频繁更新的元组的版本链较长，这会减慢查询速度，除非 PostgreSQL 添加了索引条目，允许查询快速跳转到正确的版本，而不是遍历版本链。但现在，这意味着索引更大，速度更慢，并增加了额外的内存压力。希望您现在能够理解为什么所有这些问题都是相互关联的。
为了克服这些问题，PostgreSQL 使用 真空(vacuum)过程 来清理表中的死元组。真空对自上次运行以来修改的表页执行顺序扫描并查找过期版本。如果某个版本对任何活动事务都不可见，则 DBMS 会认为该版本“已过期”。这意味着当前没有事务正在访问该版本，未来的事务将使用最新的“实时”版本。因此，删除过期版本并回收空间以供重用是安全的。
PostgreSQL 根据其配置设置定期自动执行此清理过程 (autovacuum)。除了影响所有表的vacuum频率的全局设置之外，PostgreSQL还提供了在表级别配置autovacuum的灵活性，以微调特定表的过程。用户还可以通过 VACUUM SQL命令手动触发vacuum以优化数据库性能。
为什么 PostgreSQL 的 MVCC 是最差的
我们会直言不讳：如果有人今天要构建一个新的 MVCC DBMS，他们不应该像 PostgreSQL 那样做（例如，带有 autovacuum 的append-only存储）。在我们 2018 年的 VLDB 论文（又名“关于 MVCC 的最佳论文”）中，我们没有发现另一个 DBMS 以 PostgreSQL 的方式执行 MVCC。它的设计是 20 世纪 80 年代的遗物，在 20 世纪 90 年代log-structured系统模式激增之前。
我们来谈谈 PostgreSQL 的 MVCC 出现的四个问题。我们还将讨论为什么其他 MVCC DBMS（如 Oracle 和 MySQL）可以避免这些问题。
问题#1：版本复制
使用 MVCC 中的append-only存储方案，如果查询更新元组，DBMS 会将其所有列复制到新版本中。无论查询更新单个列还是所有列，都会发生这种复制。正如您可以想象的那样，仅附加 MVCC 会导致大量数据重复并增加存储需求。这种方法意味着 PostgreSQL 比其他 DBMS 需要更多的内存和磁盘存储来存储数据库，这意味着查询速度更慢，云成本更高。
MySQL 和 Oracle 不是为新版本复制整个元组，而是在新版本和当前版本之间存储一个紧凑的增量（可以将其视为 git diff）。使用增量意味着，如果查询仅更新具有 1000 列的表的元组中的单个列，则 DBMS 仅存储包含对该列的更改的增量记录。另一方面，PostgreSQL 创建一个新版本，其中包含查询更改的一列和其他 999 个未更改的列。我们将忽略 TOAST 属性，因为 PostgreSQL 以 不同的方式处理它们。
有人尝试使 PostgreSQL 的版本存储实现现代化。 EnterpriseDB于2013年启动了zheap项目，以取代append-only存储引擎以使用增量版本。不幸的是，最后一次官方更新是在 2021 年，据我们所知，这项努力已经失败。
问题#2：表膨胀
PostgreSQL 中的过期版本（即死元组）也比增量版本占用更多的空间。尽管 PostgreSQL 的 autovacuum 最终会删除这些死元组，但写入繁重的工作负载可能会导致它们累积的速度快于清理的速度，从而导致数据库持续增长。 DBMS 必须在查询执行期间将死元组加载到内存中，因为系统将死元组与页中的活元组混合在一起。不受限制的膨胀会导致 DBMS 在表扫描期间产生更多的 IOPS 并消耗更多的内存，从而降低查询性能。此外，由死元组引起的不准确的优化器统计信息可能会导致糟糕的查询计划。
假设我们的 电影表 有 1000 万个活动元组和 4000 万个死亡元组，使得表中 80% 的数据成为过时数据。还假设该表的列数比我们显示的多得多，并且每个元组的平均大小为 1KB。在这种情况下，活动元组占用 10GB 存储空间，而死元组占用约 40GB 存储空间；表的总大小为 50GB。当查询对此表执行全表扫描时，PostgreSQL 必须从磁盘检索所有 50GB 并将其存储在内存中，即使其中大部分已过时。尽管Postgres有一个保护机制来避免顺序扫描污染其缓冲池缓存，但它无助于防止IO成本。
即使您确保 PostgreSQL 的 autovacuum 定期运行并且能够跟上您的工作负载（这并不总是容易做到，请参见下文），autovacuum 也无法回收存储空间。 autovacuum 仅删除死元组并重新定位每个页内的活动元组，但不会从磁盘回收空页。
当 DBMS 由于缺少任何元组而截断最后一页时，其他页仍保留在磁盘上。在上面的示例中，即使 PostgreSQL 从 movie 表中删除了 40GB 的死元组，它仍然保留了操作系统分配的 50GB 存储空间（或者，在 RDS 的情况下，从 Amazon 分配）。要回收并返回此类未使用的空间，必须使用 VACUUM FULL 或 pg_repack 扩展将整个表重写到不浪费存储的新空间。如果不考虑对生产数据库的性能影响，运行这些操作中的任何一个都不是一件容易的事。它们是资源密集型且耗时的操作，会降低查询性能。下图显示了 VACUUM 和 VACUUM FULL 的工作原理。
通过 PostgreSQL 的常规 VACUUM 操作，DBMS 仅从每个表页中删除死元组，并重新组织它以将所有活动元组放在页的末尾。使用 VACUUM FULL，PostgreSQL 会从每个页面中删除死元组，将剩余的活动元组合并并压缩到新页面（表第 #3 页），然后删除不需要的页面（表第 #1 / #2 页）。
问题#3：二级索引维护
对元组的单次更新需要 PostgreSQL 更新该表的所有索引。更新所有索引是必要的，因为 PostgreSQL 在主索引和辅助索引中都使用版本的确切物理位置。除非 DBMS 将新版本存储在与先前版本相同的页面中（热更新），否则系统会对每次更新执行此操作。
回到我们的 UPDATE 查询示例，PostgreSQL 通过像以前一样将原始版本复制到新页面来创建新版本。但它还会在表的主键索引 ( movies_pkey ) 和两个辅助索引 ( idx_director 、 idx_name ) 中插入指向新版本的条目。
使用非 HOT 更新的 PostgreSQL 索引维护操作示例。 DBMS 在表第 #2 页中创建元组的新版本，然后在所有表的索引中插入指向该版本的新条目。
PostgreSQL 需要在每次更新时修改表的所有索引，这会对性能产生一些影响。显然，这会使更新查询变慢，因为系统必须做更多的工作。 DBMS 需要额外的 I/O 来遍历每个索引并插入新条目。访问索引会在索引和 DBMS 的内部数据结构（例如缓冲池的页表）中引入锁/闩锁争用。同样，PostgreSQL 会对表的所有索引执行此维护工作，即使查询永远不会使用它们（顺便说一下，OtterTune 会自动查找数据库中未使用的索引）。这些额外的读写操作在根据 IOPS 向用户收费的 DBMS（例如 Amazon Aurora）中是有问题的。
如上所述，如果 PostgreSQL 可以执行热写入，其中新版本与当前版本位于同一页上，则可以避免每次更新索引。我们对 OtterTune 客户的 PostgreSQL 数据库的分析表明，平均大约 46% 的更新使用 HOT 优化。尽管这是一个令人印象深刻的数字，但这仍然意味着超过 50% 的更新要付出这种代价。
有很多用户在 PostgreSQL MVCC 实现的这一方面遇到困难的例子。最著名的证明是 Uber 2016 年关于他们为何从 Postgres 转向 MySQL 的博客文章。他们的写入繁重的工作负载在具有许多二级索引的表上遇到了严重的性能问题。
Oracle和MySQL在MVCC实现中不存在这个问题，因为它们的二级索引不存储新版本的物理地址。相反，它们存储一个逻辑标识符（例如，元组 ID、主键），然后 DBMS 使用该标识符来查找当前版本的物理地址。现在，这可能会使二级索引读取速度变慢，因为 DBMS 必须解析逻辑标识符，但这些 DBMS 在其 MVCC 实现中具有其他优势，可以减少开销。
旁注：Uber 的博客文章 中有关 PostgreSQL 版本存储的错误。具体来说，PostgreSQL 中的每个元组都存储一个指向新版本的指针，而不是之前的版本，如博客中所述。这会导致 O2N 版本链排序，而不是 Uber 错误声明的 N2O 版本链。
问题#4：真空管理
PostgreSQL 的性能在很大程度上依赖于 autovacuum 删除过时数据和回收空间的有效性（这就是为什么 OtterTune 在您第一次连接数据库时立即检查 autovacuum 的健康状态）。无论您运行的是 RDS、Aurora 还是 Aurora Serverless，都没有关系； PostgreSQL 的所有变体都有相同的 autovacuum 问题。
但由于其复杂性，确保 PostgreSQL 的 autovacuum 尽可能最佳地运行是很困难的。 PostgreSQL 用于调整 autovacuum 的默认设置并不适合所有表，尤其是大型表。例如，配置旋钮的默认设置是 20%，该旋钮控制在 autovacuum 启动之前 PostgreSQL 必须更新的表的百分比 (autovacuum_vacuum_scale_factor)。此阈值意味着，如果表有 1 亿个元组，则 DBMS 不会触发 autovacuum，直到查询更新至少 2000 万个元组。因此，PostgreSQL 可能不必要地在表中长时间保留大量死元组（从而产生 IO 和内存成本）。
PostgreSQL 中 autovacuum 的另一个问题是它可能会被长时间运行的事务阻塞，这可能会导致更多死元组和过时统计信息的积累。未能及时清理过期版本会导致许多性能问题，导致更多长时间运行的事务阻塞自动清理过程。这变成了一个恶性循环，需要人类通过终止长时间运行的事务来手动干预。
考虑下图，该图显示了 OtterTune 客户数据库中两周内死元组的数量：
PostgreSQL Amazon RDS 数据库中一段时间内失效元组的数量。
图表中的锯齿图案显示 autovacuum 大约每天执行一次主要清理工作。例如，2 月 14 日，DBMS 清理了 320 万个死元组。该图实际上是一个不健康的 PostgreSQL 数据库的示例。该图表清楚地显示了死亡元组数量的上升趋势，因为自动清理无法跟上。
在 OtterTune，我们经常在客户的数据库中看到这个问题。一个 PostgreSQL RDS 实例由于批量插入后的过时统计信息而导致查询长时间运行。此查询阻止了 autovacuum 更新统计信息，从而导致更多长时间运行的查询。 OtterTune 的自动运行状况检查发现了问题，但管理员仍然必须手动终止查询并在批量插入后运行 ANALYZE。好消息是，长查询的执行时间从 52 分钟缩短到了 34 秒。
结束语
在构建 DBMS 时，总是需要做出一些艰难的设计决策。这些决策将导致任何 DBMS 在不同的工作负载上表现不同。对于 Uber 特定的写入密集型工作负载，PostgreSQL 由于 MVCC 导致的索引写入放大是他们改用 MySQL 的原因。但请不要误解我们的谩骂意味着我们认为你不应该使用 PostgreSQL。尽管它的 MVCC 实现方式是错误的，但 PostgreSQL 仍然是我们最喜欢的 DBMS。热爱某件事就是愿意克服它的缺陷（参见丹·萨维奇的《入场的代价》）。
那么如何解决 PostgreSQL 的怪癖呢？好吧，您可以花费大量的时间和精力自己进行调整。祝你好运。
我们将在下一篇文章中详细介绍我们可以做什么。
