可串行化

关于 PostgreSQL 9.1 新版本中 SERIALIZABLE 事务隔离级别的 SSI 实现的信息。

概述

使用真正的可串行化事务，如果你能证明事务在没有并发事务的情况下能执行正确，那么在任何可串行化事务组合中事务都能执行正确，或者会回滚至串行化失败。

本文档面向在 PostgreSQL 中实现此功能所使用的技术。对于面向应用程序程序员和数据库管理员的信息，请参阅 SSI Wiki 页面。我们发表在 VLDB 2012^[5] 的论文 PostgreSQL 中的可串行化快照隔离中提供了另一个关于 SSI 的说明以及 PostgreSQL 的实现如何与先前的成果有所不同。

可串行化和快照事务隔离级别

对于拥有众多程序员在一个复杂架构中积极进行开发的店铺而言，可序列化的事务隔离非常具有吸引力，因为它以最短的人工时间保证数据完整性——如果一个事务在单独运行时（在任何其他事务之前或之后）始终可以证明其正确，它将始终在任何并发可序列化事务组合中都能正确运行。当与其他事务发生冲突会导致数据库内不一致的状态或数据的不一致视图时，可序列化事务将阻塞或回滚以防止异常。SQL 标准为因该原因导致事务回滚时生成的错误提供特定的 SQLSTATE，以便可以自动重试事务。

在 9.1 版本之前，PostgreSQL 并未支持完整的可序列化隔离级别。对可序列化事务隔离的请求实际上提供了快照隔离。这有众所周知的不一致性，它可以在并发事务期间允许数据损坏或数据的不一致视图；尽管这些不一致性仅在并发事务集合内存在特定模式的读写依赖关系时才发生。在存在这些模式的地方，可以通过通过明确编程的锁或其他不必要的数据库写入引入冲突来防止这些不一致。快照隔离受欢迎是因为性能优于可序列化隔离，并且它确实提供的完整性保证允许在许多环境中避免或通过合理的工作量管理不一致性。

可序列化的隔离实施策略

数十年来已在许多数据库产品中公布和使用实施完全可序列化隔离的技术。曾使用过的主要技术是严格两阶段锁定 (S2PL)，该技术通过阻塞针对已由并发事务读取的数据的写入，以及阻塞针对已由并发事务写入的数据的任何访问（读取或写入）来操作。阻塞图中的一个循环表示死锁，需要回滚。在高争用工作负载下 S2PL 中的阻塞和死锁可能令人望而生畏，损害吞吐量和响应时间。

一种实现 MVCC 数据库中完全可串行化隔离的新技术在 2008 年的文献中首次出现^[1]^[2]。该技术称为可串行快照隔离 (SSI)，它具有快照隔离的许多优点。具体来说，读取不会阻塞任何内容，写操作也不会阻塞读取。从本质上讲，它会运行快照隔离，但会监视事务之间的读写冲突，以识别事务图中的危险结构，表明一组并发事务可能会产生异常，然后回滚事务以确保不会出现异常。它会产生一些误报（其中一个事务被回滚，即使不会出现异常），但绝不会让异常发生。在两个已知的原型实现中，对于许多工作负载的性能（即使需要重新启动已回滚的事务）都非常接近快照隔离，并且通常远好于 S2PL 实现。

明显的顺序执行

了解快照异常何时可能发生，以及可视化上述可串行化实现之间的差异的一种方法是，在可串行化事务隔离级别上执行事务时，需要让结果与事务的某种顺序（一次一个）执行保持一致^[4]。在每个中如何确定该顺序？

在 S2PL 中，每个事务会锁定它访问的任何数据。它会一直持有这些锁直到提交，从而阻止其他事务在这期间对同一数据进行冲突访问。可能需要回滚某些事务以防止死锁。但成功的事务可以始终视为已按顺序发生，即按它们提交的顺序。

使用快照隔离时，读取永远不会阻塞写，反之亦然，因此可能实现更高的并发性。事务看上去的执行顺序是由比 S2PL 更微妙的东西决定的：读写依赖关系。如果一个事务读取数据，则它看上去在写其正在读取的数据的事务之后执行。同样，如果它更新数据，则它看上去在写前一个版本的事务之后执行。我们将这些依赖关系称为“wr-依赖关系”和“ww-依赖关系”，它们与提交顺序相一致，因为第一个事务必须在第二个事务开始之前提交。但是，两个*并发*事务之间也可能存在依赖关系，即当一个事务在另一个事务获取其快照时正在运行。当一个事务尝试读取不可见数据时，就会发生这些“rw-冲突”，因为写该数据（或稍后写该数据）的事务是并发的。读取事务看上去先执行，而不考虑事务开始或提交的实际顺序，因为它看到的是该数据库状态处于另一个事务将其保留之前。

当在依赖关系图中创建循环时，就会发生异常：当一条依赖关系或一系列依赖关系导致事务 A 看起来在事务 B 之前执行，而另一组依赖关系导致 B 在 A 之前出现。如果是这种情况，那么结果与事务的任何串行执行都不一致。

SSI 算法

PostgreSQL 中的可串行化事务是使用可串行化快照隔离 (SSI) 实现的，该隔离是基于凯希尔等人的工作。从根本上讲，这允许快照隔离以与以前相同的方式运行，同时监视可能产生序列化异常的条件。

SSI 基于一项观察^[2]，即每个快照隔离异常都对应于包含两个相邻 rw 冲突边的“危险结构”的循环

T_in ----_rw---> T_pivot ----_rw---> T_out

SSI 监控此危险结构，并在需要时回滚事务以防止出现任何异常。这意味着它只需要跟踪并发事务之间的 rw 冲突，而不必跟踪 wr 和 ww 依赖关系。这也意味着存在误报风险，因为并非每个危险结构都对应于实际序列化失败。

PostgreSQL 实现使用了两种其他优化

T_out 必须在循环中的任何其他事务之前提交（请参阅[2]中定理 2.1 的证明）。当 T_out 在 T_pivot 和 T_in 之前提交时，我们才回滚一个事务。
如果 T_in 是只读的，则只有在 T_out 在 T_in 获取快照之前提交时才会出现异常。此优化是原始的。证明
- 因为存在一个循环，所以一定有一些事务 T₀ 在串行顺序中先于 T_in。（T₀ 可能与 T_out 相同）。
- T₀ 和 T_in 之间的依赖关系不能是 rw 冲突，因为 T_in 是只读的，所以它一定是 ww 或 wr 依赖关系。只有当 T₀ 在 T_in 开始之前提交时，才会发生这种依赖关系。
- 因为 T_out 必须在循环中的任何其他事务之前提交，所以它必须在 T₀ 提交之前提交 - 从而 T_in 开始之前提交。

PostgreSQL 实现

PostgreSQL 对 SSI 的实现的显著方面包括

由于此技术基于快照隔离 (SI)，PostgreSQL 中不使用 SI 的那些区域无法使用 SSI。这包括系统表、临时表、序列、提示位重写等。SSI 不会消除这些区域中存在的异常。
任何在非 SERIALIZABLE 事务隔离级别运行的事务都不会受 SSI 影响。如果你想通过 SSI 强制执行业务规则，所有事务都应在 SERIALIZABLE 事务隔离级别下运行，且可能应将其设置为默认值。
如果所有事务都在 SERIALIZABLE 事务隔离级别下运行，则业务规则可以在触发器或应用程序代码中执行，而无需获取显式锁或使用 SELECT FOR SHARE 或 SELECT FOR UPDATE。
如果想在不借助 SSI 的其他保护（和执行这些保护相关的成本）的情况下继续使用快照隔离，则可以使用 REPEATABLE READ 事务隔离级别。此级别保留其传统行为，该行为与旧 SERIALIZABLE 实施相同，并且完全符合 REPEATABLE READ 事务隔离级别的标准要求。
如果在开始读取数据之前将不会修改永久性表的那个事务声明为 READ ONLY，则在该 SSI 实施下性能将大幅提高。
与不太严格的隔离级别相比，活动数据库事务数量越多，SSI 下的性能往往下降得越快。为保持良好性能，可能需要通过使用连接池或类似技术来限制活动事务的数目。
必须回滚以防止串行异常的任何事务都将失败，并显示 SQLSTATE 40001，其标准含义是“串行失败”。
此 SSI 实施尽力选择要取消的事务，以便对该事务的立即重试不会因与完全相同的事务发生冲突而失败。为了实现此目标，在可能引发异常的一组冲突中的其他事务之一成功提交之前，不会取消任何事务。在概念上，这类似于处理写入冲突的方式。
修改堆元组会与持有该元组、包含该元组的页面或关系的 SIREAD 锁的任何事务产生 rw 冲突。
插入新元组会与对整个关系持有 SIREAD 锁的任何事务产生 rw 冲突。它不会与页面级锁产生冲突，因为页面级锁仅用于聚合元组锁。与索引页面锁不同，它们不会锁定页面的“差距”。

当前状态

已被接受为 PostgreSQL 9.1 的一项功能！

非常感谢 Joe、Heikki、Jeff 和 Anssi 提出问题并提供建议，这对修补程序的改进功不可没！感谢 Markus 在危机关头提供 dtester，这使进步得以继续，感谢 Heikki 开发 src/test/isolation 代码，以便将 dcheck 测试移入 PostgreSQL 主测试框架。另外，还要感谢一路参与讨论的诸位。

一旦 9.1 稳定下来，应考虑为 9.2 采用一些特性，最值得注意的是与热备用集成和对 B 树之外的索引式 AM 提供细粒度支持。大多数其他建议的工作都与可能的性能改进有关，在接受之前应仔细对每一项进行基准测试。该清单的首要任务是更好地优化事实上的只读事务（未标记为只读，但实际上不会对永久数据库表进行任何写入的事务）。

开发路径

通常情况下，所采取的方法是尝试实施一种可序列化的隔离级别，该隔离级别不允许任何异常，即使它有许多误报和很差的性能，然后优化直到回滚率和整体性能处于允许实际应用的范围内。没有移除现有的隔离级别，因为并不是所有人都愿意为真正的可序列化行为付出性能代价。一个重要目标是，对于那些不使用可序列化事务隔离的人，补丁不会导致性能下降。

鸣谢

功能作者：Kevin Grittner 和 Dan R. K. Ports。

测试支持作者：Markus Wanner（大部分开发期间使用的 dtester）和 Heikki Linnakangas（与其他 PostgreSQL 回归测试一致的测试支持，以便我们拥有一个适合提交的测试套件）。

审阅者：Joe Conway（警告消除、错误查找和风格注释），Jeff Davis（总体审查并发现 GiST 支持和缺少 2PC 支持的问题），Anssi Kääriäinen（使用产品数据进行测试时发现条件索引问题和顺序扫描性能问题），YAMAMOTO Takashi（在长期而繁重的测试中发现大量错误），以及 Heikki Linnakangas（总体审查和许多有用的观察和建议，以及在提交过程中的总体改进）。

提交者：Joe Conway（初始注释和名称更改），Heikki Linnakangas（该补丁的主体和大部分后续修复），以及 Robert Haas（一些后续修复）。

感谢所有参加在线讨论并提供非在线建议和支持的人。有很多人以这种方式做出了贡献，实际上不可能生成准确的列表，但 Robert Haas 在提供有关整体开发策略的出色建议方面脱颖而出。

特别感谢 Emmanuel Cecchet 指出最初发表此技术的 ACM SIGMOD 论文^[1]，以及悉尼大学所有为开发此创新技术做出贡献的人。这使得讨论从争论如何最好地记录现有行为转向改变现有行为。

源代码管理

已在此位置设置“可序列化”git 分支

git://git.postgresql.org/git/users/kgrittn/postgres.git

http://git.postgresql.org/git/users/kgrittn/postgres.git

ssh://[email protected]/users/kgrittn/postgres.git

http://git.postgresql.org/gitweb?p=users/kgrittn/postgres.git;a=shortlog;h=refs/heads/serializable

谓词锁

S2PL 和 SSI 都需要某种形式的谓词锁来处理读取与后来的插入或后来的更新（将数据移入所选范围）冲突的情况。PostgreSQL 没有谓词锁，因此需要将其添加进来。谓词锁的实际实现通常涉及在访问数据时针对数据获取锁，以便使用多个粒度（元组、页面、表等），并根据需要进行升级以将锁计数保持在可以在 RAM 结构内跟踪的数字。粗粒度可能会导致一些冲突的错误阳性指示。错误阳性的数量可能会受到计划选择的影响。

实现概述

将使用新的 RAM 结构，它的灵感源自用于跟踪 PostgreSQL 中的传统锁的 RAM 结构，但专门针对 SIREAD 谓词锁的需求进行定制。这些结构将引用实际在执行查询过程中访问的物理对象，以通过推理对谓词进行建模。对该主题感兴趣的任何人，都应该查阅 Hellerstein、Stonebraker 和 Hamilton 论文^[3]以及从那里引用的锁定论文和 Cahill 论文^[1]^[2]。

由于 SIREAD 锁不会阻塞，因此传统锁定技术必须修改。意向锁（锁定低级别对象之前锁定高级别对象）不适用于非阻塞“锁”（在某些方面，它更像是标志，而不是锁）。

在启动后主进程时，会预留一个可配置的共享内存量，用于跟踪谓词锁。此大小不能在不重新启动的情况下更改。

为防止资源耗尽，多个细粒度的锁可能会根据需要提升为单个更粗粒度的锁。
当同一事务已经持有一个页面或关系的 SIREAD 锁时，将忽略尝试获取一个元组的 SIREAD 锁。同样，当关系被锁定时将忽略尝试锁定一个页面，同时获取更粗粒度的锁将导致释放它所覆盖的所有更细粒度的锁。

堆锁定

基于以下内容为堆获取谓词锁

对于表扫描，将锁定整个关系。
将锁定对读取事务可见的每个已读取的元组，无论它是否满足选择条件；但如果事务已持有一个表示该行的任何元组的写锁，则不需要获取一个元组的 SIREAD 锁，因为 rw 依赖项也会创建一个执行更严格且因此将防止任何异常的 ww 依赖项。

默认索引锁定

pg_am 中出现一个新的 ampredlocks 标志，应将它设置为 false 以适用于未在内部处理谓词锁的任何索引；通过这种方式标记的索引将在索引关系级别谓词锁定。此类锁定将与任何插入索引的尝试发生冲突，但不会与删除、HOT 更新和不匹配索引 WHERE 子句（如存在）的插入冲突。这将允许在新的索引类型中以最小的初始工作量正确处理可串行化事务隔离级别；但添加谓词锁定调用并更改标记将会改善涉及可串行化事务的高竞争工作负载的性能。

索引 AM 实现

由于谓词锁仅存在于用于检测与先前读取冲突的写入，而且 heap 元组锁是为涵盖实际读取的所有 heap 元组而获取的，包括通过索引读取的那些，因此实际扫描的索引元组本身不值得关注；我们仅关心其“新邻域”——在扫描时如果它们已存在，那么稍后插入到索引中的内容将包含在扫描中。从概念上讲，我们想要锁定扫描范围内的索引条目之间的以及周围的“空白”。

正确性要求如果在插入索引后，重新执行其他事务的任何索引扫描会访问在前执行期间未访问的行，则任何插入索引的操作均会与并发串行化事务产生 rw 冲突。请注意，会使扫描覆盖的旧索引条目过期的非 HOT 更新并会为修改的行的新元组添加新条目的更新不必产生冲突，但“将”行移动到扫描中的更新必须产生冲突。虽然正确性允许误报，但出于性能的原因，应尽量减少误报。

可执行多个优化

仅用于查找索引插入或删除正确位置的索引扫描不必获取谓词锁。
针对唯一索引的整个密钥比较相等项的索引扫描不必获取谓词锁，只要找到与未被其他事务修改的可见元组相对应的密钥，则不存在需要涵盖的“其间或周围”空白。
只要内置外键强制继续使用其当前的“特殊技巧”来处理 MVCC 问题，则强制执行代码完成的扫描应该不需要谓词锁。
如果搜索确定在不考虑索引内容的情况下无法找到任何行，这是因为搜索条件是矛盾的（例如，x = 1 且 x = 2），则不需要谓词锁。

其他索引 AM 实现注意事项

如果 b-tree 搜索发现尚未创建根页，那么必须对索引关系进行谓词锁；否则 b-tree 搜索必须到达叶级以确定哪些元组匹配，因此谓词锁就在那里。
GiST 搜索可以确定索引的任何级别都没有匹配项，因此在 GiST 搜索期间，必须在每个索引级别都有一个谓词锁。然后，可以信任叶级上的索引插入操作向上传递到所有级别和可能存在冲突谓词锁的位置。
必须仔细查看页面分割、溢出、合并和移除的影响，以确保在这些操作期间不会“丢失”谓词锁或与可能被重复用于索引不同部分的页面一起保留谓词锁。

测试

为使此开发工作取得成功，绝对必需有某个客户端应用程序，该应用程序允许执行测试脚本，其中针对多个后端运行的语句具有特定的交错。在大多数开发期间，为此使用 Markus Wanner 的 dtester 模块。它需要 Python 和几个 Python 包（包括 Twisted）。由于软件包依赖关系和许可问题，dtester 模块不适合提交到 PostgreSQL 代码库。

Heikki Linnakangas 开发了一个基于现有回归测试代码的测试框架，该代码已提交到 src/test/isolation。它除了与其他 PostgreSQL 测试兼容之外，还运行得比 dtester 更快。它不会通过语句顺序排列漂亮地显示结果，但如果需要，可以通过过滤当前输出来添加此功能。

与许多其他提议的功能和优化一样，此领域可以从“性能测试场”中受益，这样可以将可串行化的性能与其他隔离级别更好地进行比较，并且可以确定未来增强的性能影响。

文档

创建了一个 README-SSI 文件，该文件主要摘自此 Wiki 页面。

某人拥有对维基百科的更新权限，应该更新其中的引用，这些引用将因此功能而过时

创新

PostgreSQL 的可串行化快照隔离实现与所引用的论文中描述的不同，原因有以下几个

PostgreSQL 没有现有的谓词锁定。它必须从头开始添加。
现有的内存中锁结构不适用于跟踪 SIREAD 锁。
- 用于论文原型实现的数据库产品在其 MVCC 实现中使用就地更新以及回滚日志，而 PostgreSQL 将行的旧版本保留在原位，并添加新元组来表示新位置的行。
- 在PostgreSQL中，元组级别的锁不会在RAM中处于保持状态的任何时间长度；锁信息写入涉及事务中元组。
- 在PostgreSQL中，现有锁结构具有指向内存的指针，该内存与连接相关。SIREAD锁需要持续到起始事务乃至运行此事务的连接结束时间之后。
- PostgreSQL必须能够容忍大量事务在打开一个长时间运行的事务时执行——论文中讨论的RAM中的技术不支持这一点。
不像论文中所述的原型数据库产品，PostgreSQL此前没有与快照隔离不同的真正的可序列化隔离级别。
PostgreSQL支持子事务——论文中未提及的问题。
PostgreSQL在必要之前和之后才向数据库事务分配事务编号。
PostgreSQL有用户可定义操作符的可插入数据类型，还有可插入的索引类型，并非所有这些类型都围绕支持排序的数据类型而存在。
在开发和测试期间，一些可能的优化变得明显。

与论文中所述的实现不同的部分列举如下。

为了跟踪可序列化事务及其SIREAD锁的正确信息，需要在共享内存中创建新的结构。

因为PostgreSQL对于所有可序列化事务没有与Cahill论文中设想相同的“最旧事务ID”概念，我们在可序列化事务中跟踪最旧的快照xmin，以及使用该xmin有多少个活跃事务的计数。当计数达到零时，我们找到新的最旧xmin并基于此运行清理。

PostgreSQL中的谓词锁定可能从元组级别开始，根据需要将多个细粒度锁自动转换到更粗的粒度以避免资源耗尽。将用于这些结构的内存容量设为可配置，以根据SIREAD锁粒度平衡RAM使用。

保留进程持有的锁以及带有计数的更粗覆盖锁的进程本地副本，以支持粒度提升决策，降低CPU和锁定开销。

当写入元组时通过查找谓词锁来识别冲突，在读取元组时通过查找MVCC信息来识别冲突。在两个基于RAM的锁之间没有匹配项。

因为写锁存储在堆元组中而非基于RAM的锁表中，以下内容实现了Cahill论文中所述的优化，该优化在有写锁时消除了SIREAD锁
1. 在检查堆写是否与现有谓词锁发生冲突时，会移除写入元组上的元组锁。
2. 在堆元组上获取谓词锁时，如果元组是由读取事务写入的，则我们快速返回，而不做任何事情。

我们使用 rw 冲突列表，而不是使用 conflictIn 和 conflictOut 指针，后者使用 NULL 来表示没有冲突，使用自引用来表示多个冲突或与已提交事务的冲突。利用更加完整的信息，误报减少了，且我们有足够的数据进行更为激进的清理和其他优化。
- 我们可以在冲突处枢轴出现之前避免回滚事务，除非枢轴 *外* 侧的一个事务在其他任何事务之前已提交。
- 我们可以在冲突处枢轴 *内* 侧的事务明确或隐式为 READ ONLY 的情况下，避免回滚该事务，这时在冲突处枢轴 *外* 侧的事务在 READ ONLY 事务获取其快照之前已提交。（隐式 READ ONLY 事务不会写入而是提交，即使没有明确声明为 READ ONLY 也是如此。）
- 我们可以更加积极地清理冲突、谓词锁和 SSI 事务信息。

如果没有任何 READ WRITE 事务可能导致 READ ONLY 事务成为重叠事务依赖关系的“危险结构”一部分，则允许 READ ONLY 事务“退出”SSI。

允许用户要求 READ ONLY 事务等待，直到满足在上面描述的“退出”状态中开始该事务的条件为止。我们为事务添加一个 DEFERRABLE 状态，该状态的指定方式和维护方式类似于 READ ONLY 状态。该状态对于不可序列化且为 READ ONLY 的事务无效。

当必须回滚事务时，我们从活动事务中挑选一个，以确保立即重试时不会再次与相同事务的冲突失败。

我们使用 PostgreSQL SLRU 系统来持有有关已提交旧事务的汇总信息，以限制 RAM 使用量。超过该限制之后，信息将溢出到磁盘。在最坏情况下，性能可能会下降，但应该是可以忍受的，并且无需取消事务或阻止其开始。

R&D 问题

本节记录需要更详细的审查或分析的具体问题。

WAL 文件重放。虽然使用 S2PL 的可序列化实现可以保证预写日志包含与某些可序列化事务串行执行一致的提交，但 SSI 无法提供该保证。虽然 WAL 重放并不逊色于快照隔离，但在 PITR 恢复或热备用情况下，数据库可以达到可读状态，其中一些事务会出现在其他事务之前，而如果后者事务要保持可串行动一致性则必须先于前者事务。从本质上讲，如果我们什么都不做，WAL 重放即使对于可序列化事务也将处于快照隔离。这样可以吗？如果不行，我们如何解决这个问题？