PostgreSQL是一种广为人知的关系数据库系统。我们使用Jepsen的新事务隔离检查器Elle评估PostgreSQL，发现在单个PostgreSQL实例上使用可序列化隔离执行的事务实际上是不可序列化的。在正常操作下，事务偶尔会出现G2项：涉及一组事务的异常情况，这些事务(粗略地说)相互无法观察到彼此的写入。此外，我们在PostgreSQL“Repeatable Read”下发现了频繁出现的G2-Item实例，这是通常引用的Repeatable Read形式化明确禁止的。正如Martin Kleppmann之前所报道的，这是因为PostgreSQL“可重复读取”实际上是快照隔离。由于ANSI SQL标准中讨论已久的模棱两可，这种行为是允许的，但对于熟悉相关文献的用户来说，这可能会让他们大吃一惊。我们在Serializability中发现的bug的补丁计划在8月13日的下一个小版本中发布，并且在Repeatable Read下存在G2-Item的问题可以通过文档轻松解决。这项工作是独立进行的，没有报酬，并根据杰普森道德政策进行。
PostgreSQL是一种主要的开源关系数据库，具有23年的历史和广泛的功能。虽然Jepsen的工作传统上侧重于分布式系统，但我们的工具很容易适用于传统的单节点数据库。在本报告中，我们展示了将Jepsen的生成性并发测试应用于PostgreSQL12.3的结果。
在9.1版本之前，postgresql的文档声称提供了最高可序列化能力，“就好像事务是一个接一个地串行执行，而不是并发执行(…。。Serializable模式提供了严格的保证，确保每个事务都能看到完全一致的数据库视图。“。然而，事实并非如此：PostgreSQL的“可序列化”实际上是快照隔离(SI)。
非正式地，快照隔离系统似乎以数据库的固定即时快照启动每个事务，仅反映已提交的状态。事务中执行的写入似乎在提交时自动应用，只有在拍摄快照后没有其他事务修改过相同的对象时，事务才能提交。这是不可序列化的(正如正式的快照隔离文章所明确指出的那样)：写入集不相交的事务可以在不观察彼此影响的情况下提交，这可能会导致违反应用程序级一致性。
在8.0版中，PostgreSQL的文档澄清了“事实上PostgreSQL的Serializable模式并不能从这个意义上保证可序列化的执行”，并接着指出PostgreSQL缺少谓词锁定系统。
在9.1版中，基于Cahill、Röhm和Fekete对可序列化快照隔离(SSI)的研究，PostgreSQL贡献者Grittner和Ports添加了对真正可序列化的支持。简而言之，SSI通过在运行时检查称为危险结构的事务之间的依赖关系来扩展SI：三个事务之间的一对相邻的读写依赖关系。除了快照隔离的正常规则之外，防止这些危险的结构只会产生可序列化的执行。在过去的九年中，PostgreSQL的“可序列化”模式理所当然地声称提供了可序列化。
PostgreSQL的“可重复读”保持快照隔离，但是并发控制文档令人惊讶地没有提到这个术语。相反，它提供：
可重复读隔离级别只看到事务开始之前提交的数据；它永远不会看到未提交的数据或并发事务…在事务执行期间提交的更改。这比SQL标准对此隔离级别的要求提供了更强的保证，并防止了表13.1中描述的所有现象(序列化异常除外)。如上所述，这是该标准特别允许的，它只描述了每个隔离级别必须提供的最低保护。
“序列化异常”是一个有点模棱两可的术语：文档简单地将其描述为“与一次运行一个事务的所有可能顺序不一致”。为了更好地理解“序列化异常”的具体含义，我们设计了一个实验。
我们使用Jepsen测试库为PostgreSQL设计了测试工具。我们的测试在单个Debian 10节点上安装PostgreSQL12.3-1.pgdg100+1(当前稳定版本)，或者选择连接到现有的PostgreSQL安装。我们还评估了版本9.5.22、10.13和11.8。我们的测试可以按随机顺序终止PostgreSQL进程，以帮助测量崩溃安全性，但我们在这里的发现不需要重现进程崩溃。我们使用PostgreSQL的官方Debian包提供的默认配置，只做了很小的更改(例如，绑定网络端口)，在一些测试中，缩短了自动真空午睡时间，并启用了更详细的日志记录。
我们的测试工作负载跨一组列表对象生成附加和读取操作的随机事务，并以指数频率选择。每个对象由唯一的整数逻辑键标识。我们将每个对象作为一行存储在多个表中的一个表中，这些表由键的散列选择。对象键存储在两个字段中：主键id和未索引的辅键sk，我们使用它通过表扫描测试访问。1每个列表的值存储为逗号分隔的文本列。
我们使用INSERT.将唯一的整数元素附加到由key标识的列表中(通过id或sk)。在冲突时执行UPDATE，或者通过UPDATE检查是否有任何行被修改，然后后退到INSERT，如果失败，则再次更新。读取返回特定对象的当前整数列表，例如，通过SELECT(Val)from txn0 where id=？
我们的测试使用JDBC PostgreSQL驱动程序(版本42.2.12)将这些事务应用到PostgreSQL，并使用ELLE事务隔离检查器分析结果历史。ELLE根据实验记录的历史推断事务依赖图，并在该图中搜索循环(和非循环异常)。这使我们能够从Adya、Liskov和Amp；O‘Neil的通用隔离级别定义中检测到广泛的异常，包括G0(脏写)、G1a(中止读取)、G1b(中间读取)、G1c(循环信息流)、G-Single(读取偏差)和G2-Item(反依赖周期)。我们还检查内部一致性，验证事务是否观察到与其自身先前写入一致的值、重复影响和垃圾值(例如，从未写入的元素)。
在大多数方面，PostgreSQL的行为与预期一致：未提交的读取和提交的读取都可以防止写入偏差和中止读取。我们没有观察到违反内部一致性的情况。然而，我们有两个令人惊讶的结果要报告。首先是PostgreSQL的“可重复读取”弱于可重复读取，至少按照Berenson、Adya、Bailis等人的定义，这不一定是错的：ANSI SQL标准是模棱两可的。第二个结果肯定是错误的，那就是PostgreSQL的“可序列化”隔离级别是不可序列化的：它允许在正常操作期间使用G2-Item。
PostgreSQL的“可重复读取”隔离级别实际上是快照隔离，在使用“可重复读取”时，我们没有观察到违反SI的异常。事实上，我们记录的历史与强大的快照隔离是一致的，这是一种更强的一致性模型，可防止陈旧读取和其他实时异常。
然而，我们观察到许多违反可重复读取的行为，正如Berenson，Adya等人正式定义的那样。例如，考虑一下这段历史，它每分钟产生大约140个反依赖周期。下面是由三个事务组成历史中的一个短周期-每个事务似乎都在下一个事务之前执行。
顶部事务通过读取键190开始，并找到列表[1 2]。中间事务将4附加到密钥190，得到版本[1 2 4]。由于写入覆盖了顶部事务读取状态，因此我们知道中间事务必须在顶部事务之后执行。我们称这种关系为反依赖关系，并将其表示为一条标记为RW的边。
中间事务将5附加到键190，然后对底部事务的读取[1 2 4 5]可见。该写-读依赖性由标记为WR的边表示。然而，底部事务读取关键字188，并且没有观察到顶部事务的附加8。这种反依赖性意味着底部事务必须在顶部事务之前执行：周期！
这个依赖循环包含两个反依赖的边缘，这使得它在阿雅的形式主义语言中成为G2现象。因为所有这些读取都是在通过主键2读取对象时发生的，所以它也是G2-Item：在Adya的可重复读取的形式化中明确禁止这种现象。我们认为这是PostgreSQL文档中提到的一种“序列化异常”。
然而，根据ANSI SQL对可重复读取的定义，这些异常是允许的，这要归功于对禁止现象的措辞含糊的简明英语定义。事实上，这种模棱两可正是促使Berenson、Bernstein等人撰写《ANSI SQL隔离级别批判》的部分原因，并首先将快照隔离的定义正式化。在这项工作中，Berenson等人对ANSI异常提出了两种解释：一种是严格的，一种是广义的。他们争辩说，严格的解释未能捕捉到直觉上不正确的行为，而ANSI的意思是定义广义的行为。
严格的解释A1、A2和A3有意想不到的弱点。正确的解释是宽泛的。
在Berenson等人喜欢的广义解释下，快照隔离不能与可重复读取相提并论：SI允许历史RR禁止，反之亦然。在严格的解释下，SI强于RR(确实，SI强于异常可序列化！)，并且这些G2项异常在可重复读取下是允许的。
因此，PostgreSQL的可重复读取行为是否正确取决于人们对该标准的理解。令人惊讶的是，基于快照隔离的数据库会拒绝关于SI的开创性论文所选择的严格解释，但经过反思，这种行为是可以辩护的。
当我们测试PostgreSQL的可序列化隔离级别时，出现了一个更严重的问题：在正常操作下，它还显示了G2项。在这两分钟的测试中，杰普森检测到6例G2-Item。例如，考虑这对事务，其中每个事务都未能观察到对方的插入：
或者，考虑以下三个事务。顶部事务错过了由底部只读事务观察到的中间事务的密钥1670的创建。然而，底部事务又未能观察到第一事务对密钥1671创建。值得注意的是，如果读写事务自己获取，则它是可序列化的。只读事务对于此周期是必需的：它观察某些(但不是全部)“逻辑上在先”事务的影响。
实际上，这些依赖图与PostgreSQL Serializable Snapshot隔离纸中的示例1(“简单写入偏差”)和示例2(“批处理”)完全对应，如下所示。当然，它们的SQL语句是不同的-但与示例1类似，我们的第一个周期涉及一对事务，它们读取一个键并写入另一个键，每个事务都未能观察到另一个键的影响；而我们的第二个周期涉及一个只读事务，该事务通过两个相邻的RW反依赖关系先于写入该只读事务观察到的状态的事务。这些周期正是PostgreSQL的SSI实现要防止的！
我们在可序列化隔离下观察到的G2-Item的每个实例都至少涉及新插入行的一个读写冲突。循环可能涉及对现有行的更新的RW反依赖，但似乎至少需要一次插入。
在与PostgreSQL贡献者讨论之后，Peter Geoghegan确定了此问题的可能原因：在给定三个并发事务的情况下，冲突检测机制可能会错误地将更新事务的事务ID(XID)标识为负责元组的原始版本和更新版本，而不是使用最初创建元组的事务ID。通过将错误的事务标记为潜在冲突，它允许事务提交，同时无法观察前一个事务的写入。Geoghegan与PostgreSQL社区的其他成员合作，编写了一个补丁来标记正确的事务ID，并添加了一个回归测试。在他们的测试中，这似乎解决了问题。
自从2011年引入可序列化快照隔离以来，这段代码基本上没有变化。我们一起确认PostgreSQL 9.5.22、10.13、11.8、12.3和13中存在此错误；我们假设它存在于所有现有版本中。
在我们对PostgreSQL12.3的测试中，在读提交时执行的事务似乎是正确的：我们从未观察到G0(脏写)、G1a(中止读)或G1b(中间读)。PostgreSQL“可重复读取”看起来与强快照隔离一致，但允许G2-Item，这在可重复读取的形式化中是被禁止的。但是，可以将此行为解释为与ANSI SQL可重复读取一致。最后，由于冲突检测机制中的错误，PostgreSQL“可序列化”允许G2-Item在正常操作下运行。已经提交了一个补丁，这类可序列化冲突应该会在下一个次要版本中解决--目前计划在8月13日发布。
PostgreSQL有一套广泛的精心挑选的示例，称为隔离测试程序，用于验证并发安全性。此外，像Martin Kleppmann的Hermitage这样的独立测试也证实了PostgreSQL的可序列化级别可以防止(至少有一些！)。G2异常。那么，为什么我们马上和杰普森一起找到了G2-Item呢？这个漏洞是如何持续这么久的呢？
PostgreSQL的隔离测试、Hermitage和大多数事务性Jepsen测试(在ELE之前)都依赖于使用手工验证的不变量执行少数巧妙构造的事务。例如，此隔离测试器规范通过执行Fekete，O‘Neil，&；O’Neil在快照隔离下的只读事务异常中提出的事务序列来验证可串行化。杰普森的银行测试基于一类定义狭窄的交易，该交易在快照隔离下保持总余额不变量。Hermitage通过执行一对对称的读取和更新事务来检查G2-Item-这确实成功地演示了在PostgreSQL“可重复读取”下的G2-Item，但不在Serializable下。
然而，ELLE是不同的：它允许我们生成广泛的事务类，同时仍然在结果历史上推断严格的属性。这种基于属性的方法允许我们捕获没有人想过要显式测试的意外行为。在本例中，它确定了并发更新和插入可能会混淆冲突检测机制，使其误认为哪个事务负责冲突。
也就是说，我们在这里设计的列表追加测试只验证了简单模式上的少数SQL操作。成熟的SQL数据库(如PostgreSQL)是具有无数交互组件和优化的复杂有机体。Jepsen假设我们的测试只执行PostgreSQL可能行为的一小部分。
一如既往，我们注意到杰普森采取了一种实验性的安全验证方法：我们可以证明错误的存在，但不能证明它们的存在。虽然我们努力寻找问题，但我们无法证明任何分布式系统的正确性。
用户应该知道，PostgreSQL的“可重复读取”实际上是快照隔离--这是PostgreSQL社区早就了解的事实，此前Kleppman曾报道过这一事实。由于G2-Item在可重复读取的常见形式化下是被禁止的，用户可能已经设计了应用程序，假设PostgreSQL也是如此。在这种情况下，用户可能希望改为在可序列化隔离下运行选定的事务，添加显式锁定，或重新设计这些事务，使其不再对G2-Item敏感。
我们建议PostgreSQL团队更新他们的并发控制文档，以解决围绕“可重复读取”的歧义。当前的文档没有提到“快照隔离”这个术语--声明PostgreSQL的“可重复读取”实际上意味着快照隔离可以立即澄清问题。文档还可以通过用G-Single、G2-Item和G2替换模糊的“序列化异常”来为用户提供更清晰的指导；SI禁止G-Single，但允许G2-Item和G2。
至于快照隔离是否比可重复读取更强，一种可能的解决方案是采用Berenson等人的定义，并声明快照隔离与可重复读取是不可比拟的：SI允许RR禁止的一些异常(例如写入偏差)，但是RR允许SI禁止的其他异常(例如幻影)。这样做将使PostgreSQL与Berenson、Adya、Bailis等人长达25年的事务隔离学术线索保持一致。
然而，正如Ports&；Grittner在他们关于PostgreSQL的可序列化快照隔离的论文中所指出的那样，ANSI规范是模棱两可的，我们观察到的G2项异常并不一定违反对可重复读取所禁止的现象的严格解释。在这种情况下，我们建议PostgreSQL显式声明他们选择严格的解释，而不是宽泛的解释。
似乎没有任何版本的PostgreSQL能够保证可序列化。用户应该意识到并发更新和插入事务可能表现为G2-Item。争用程度高的工作负载尤其容易受到影响。PostgreSQL团队已经编写了重现该问题的测试，并正在评估补丁；我们建议在下一个次要版本可用时进行升级。
最后要注意的是：我们的测试表明PostgreSQL提供的不仅仅是快照隔离和可序列化(或者，在可序列化的情况下，一旦G2项错误得到解决，它将提供)更多的功能。我们的历史记录似乎与强大的快照隔离和严格的可序列化一致，这两者除了防止常见的依赖图异常之外，还确保了与实时订单的兼容性。我们不确定这是故意的，还是在所有情况下都是如此，但如果是这样的话，PostgreSQL应该可以自由地宣称这些更强的一致性模型！
PostgreSQL的贡献者正在评估一个补丁，以解决我们发现的序列化冲突，并编写关于快照隔离与可重复读取的澄清文档。
ELLE的列表附加工作负载仅限于读取和附加与列表同构的数据类型。我们无法测试删除、替换或其他列表操作：这些代码路径中可能存在潜在问题。我们还有其他工作负载可用于寄存器和集合，尽管支持较弱的推断。两者都可以在PostgreSQL上实现，这可以帮助覆盖更多的领域。
我们似乎不太可能有效地检查甚至建模现代SQL数据库提供的所有功能。聚合、子查询和存储的p。
..