Calvin - 确定性、分布式ACID事务 (2020)

# Calvin：确定性的魔力 来源：https://www.mydistributed.systems/2020/08/calvin.html Calvin 是一种事务调度与复制协议，为分区和复制的系统提供分布式 ACID 事务。其核心依赖于一种锁定机制，与两阶段锁（2PL）不同，这种锁定是确定性的。这种确定性消除了对原子提交协议（如两阶段提交）的需求，从而显著降低了分布式事务的竞争足迹。 Calvin 和 Spanner 都在 2012 年提出，却用完全不同的方法解决了相同的问题。因此，将它们并排比较是件有趣的事。不过，本文我们主要关注 Calvin。你可以参考这篇文章来了解 Spanner 的更多内容。 ## 核心理念：消除非确定性，摆脱两阶段提交！ 假设我们有一个单节点数据库，没有分区或复制。正如我们在这篇文章中所说，实现严格可串行化的一种方法是通过实际串行执行，即在一个线程中逐一执行事务。这消除了事务之间所有类型的冲突，提供了最高级别的隔离。然而，它无法扩展，因为我们受限于单线程。每个事务都必须等待前一个事务完成，即使这两个事务完全无关、访问不同的数据。为了提高可扩展性，我们希望能在并行运行无关事务的同时，串行执行冲突事务。这正是两阶段锁（2PL）所提供的。因此，2PL 很棒！它在不牺牲可串行化的情况下打开了并行的大门。 对于当今的大多数应用，单节点数据库是不够的。为了获得更高的可扩展性和可用性，我们必须对数据库进行分区和复制。在分区数据库中，单个事务可能访问位于多个分片上的数据。我们如何实现多分片事务的可串行化呢？难道不能将事务发送到所有涉及的分片，让它们各自运行 2PL 吗？不幸的是，不能。主要问题在于 2PL 的非确定性。例如，如果两个访问同一锁的事务同时执行，无法确定哪一个会先运行。2PL 也有可能为了避免死锁而中止其中一个事务（参见这篇文章）。假设 T1 和 T2 都是多分片事务。如果我们简单地将它们发送到各分片，让它们独立运行 2PL，最终可能会陷入糟糕的局面：1）执行顺序在各分片上可能不同，从而违反**隔离性**；2）一个事务可能在一个分片上提交，在另一个分片上中止，从而违反**原子性**。 如你所见，由于 2PL 的非确定性，我们不能简单地将事务发送到所有分片并让它们独立运行 2PL。为了解决这个问题，我们可以使用原子提交协议，例如两阶段提交（2PC）。通过使用 2PC 协调事务涉及的所有分片，并在每个分片上运行 2PL，我们可以保证分布式事务的可串行化。这正是 Spanner 的做法。你可以参考这篇文章了解更多。 [图 1. 仅靠 2PL 无法保证分布式事务的隔离性（左图）。2PC+2PL 保证了分布式事务的隔离性和原子性（右图）。] 所以问题解决了！使用 2PC+2PL 我们实现了分布式可串行化。是的，但有一个问题：在 2PL 中，当一个事务持有锁时，所有其他请求同一锁的事务都必须等待。在单节点数据库中，事务管理器获取锁、快速执行事务、然后释放锁。所以没问题。但在分区和复制的系统中，事务管理器还必须等待两件事：2PC 和复制。换句话说，尽管本地分片已经完成了事务并准备释放锁，但它不能这样做，因为在此之前它必须确保参与事务的所有分片上的足够副本已经接收到该事务，并且所有分片都同意提交。这些额外的延迟增加了事务持有锁的时间。这段时间被称为**竞争足迹**。在事务系统中，我们希望尽可能缩小竞争足迹。 采用 2PC+2PL 的分布式事务有较大的竞争足迹，主要由 2PL 的非确定性导致。如果能在保证可串行化和保持并行性的同时摆脱这种非确定性，那就太棒了。好消息是，我们能做到！通过使用**确定性锁定**，我们可以实现确定性、可串行化和并行性。我们将在本文中详细介绍确定性锁定的细节，但其总体思路是：预先通过一个单线程执行来定义事务的全局顺序，并利用这个顺序决定哪个事务应该先执行。 *那么确定性与实际串行执行有何不同？* 在实际串行执行中，一个线程既对事务排序又执行事务。在确定性执行中，一个线程对事务排序，但执行可以并行进行，只要不违反全局顺序。 [图 2. 实际串行执行（左图）与确定性执行（右图）的区别] 一旦我们消除了 2PL 的非确定性，就可以摆脱 2PC。现在有了确定性锁定，我们可以简单地将事务按全局顺序发送到对应的分片。每个分片运行确定性锁定，保证在可能并行执行事务时保持全局顺序。 *但如果某个分片发生故障呢？如果其中一个分片失败，事务就会在未完成时被应用。* 下面我们将详细介绍 Calvin 的细节，但分片故障不成问题，因为我们通过预先将事务追加到复制的日志中来确保所有事务的持久性。这个日志可以被视为系统的预写日志。因此，该日志既定义了顺序，又保证了持久性和原子性。 全局排序所有事务的需求阻止了我们使用交互式事务，因为如果使用交互式事务，一旦事务开始，所有后续事务都必须等待它完成，这是不可接受的。因此，在 Calvin 中，事务必须以**存储过程**的形式存在。存储过程是一段定义事务逻辑的代码。事务可以读取一些数据，并基于这些数据更新其他数据，但逻辑不能在客户端运行。相反，客户端一次性提交其逻辑，由数据库执行。 ## 设计 理解了 Calvin 的理念后，让我们来看看它是如何实际处理事务的。图 3 展示了 Calvin 的整体架构。Calvin 由三个层组成，下面我们分别讨论。 [图 3. Calvin 的架构 [1]] ### 排序层 我们看到 Calvin 需要为所有事务定义一个全局顺序。最简单的方法是拥有一个单线程的进程，逐个接收事务并对它们排序。显然，单线程存在可扩展性和可用性问题。Calvin 的排序层负责提供类似单线程的全局排序，同时提供水平可扩展性和更高的可用性。 如图 3 所示，Calvin 集群中的每个节点都有一个排序器进程。首先考虑没有复制的情况。排序器将时间划分为若干时段。在每个时段中，排序器相互分享它们接收到的事务。然后，它们使用轮询方式定义顺序。例如，假设在第一个时段，排序器 1、2 和 3 分别接收到事务 T1、T2 和 T3。每个排序器将其排序为 T1、T2、T3。在下一个时段，它们接收到 T4、T5、T6。这次，排序器将它们排序为 T5、T6、T4。因此，到目前为止的全局顺序是 T1、T2、T3、T5、T6、T4。这样，所有排序器都能接收请求，同时保证全局顺序。 现在考虑有复制的情况。在这种情况下，我们可以选择同步或异步复制。在异步复制中，一个副本是主副本，按照上述方式运行。其他副本将异步接收事务并应用它们。因此，所有请求必须发送到主副本。这种方法的优点是复制是异步的，客户端无需等待复制，因此速度更快。然而，处理故障比较复杂。在同步复制中，我们基本上必须使用诸如 Paxos 之类的共识协议来确保写入在继续前进并应用之前已复制到足够多的副本。无论如何，复制不会改变上述轮询机制；在每个时段中，排序器以轮询方式对每个分片提出的事务进行排序。请注意，为了分摊共识和通信的成本，排序器将每个时段内接收到的所有事务分批处理，然后与其他副本和排序器共享这些批次。Calvin 论文建议每个时段为 10 毫秒，以便排序器能够批处理事务。 注意，在复制系统中，我们需要确保所有副本以相同方式修改数据，否则副本之间会变得不一致。在 Calvin 中，每个事务将作为存储过程由每个副本执行。虽然它们都执行相同的逻辑，但逻辑中的任何非确定性来源都可能导致副本的偏离。例如，当事务代码中有随机数时，每个副本可能产生不同的随机数。此外，当事务代码中调用系统时间时，不同副本很可能得到不同的值。当我们希望每个副本独立执行事务逻辑时，所有这些可能性都必须消除。因此，在将事务追加到复制日志之前，排序器必须进行预处理步骤，以消除这些非确定性来源。具体来说，排序器分析事务代码并预执行任何非确定性代码。 ### 调度层 每个排序器将下一批事务提交给同一节点上的调度器。调度器使用确定性锁定进行并发控制。如前所述，与 2PL 不同，确定性锁定从不中止任何事务，并保证在允许并行执行的同时尊重事务的全局顺序。让我们看看它是如何工作的。 图 4 展示了一个确定性锁定的例子。排序器的输出提供了一个日志，即一个事务序列。有一个单一的调度器线程接收这些事务。有一个锁表，将每个对象映射到请求该对象的等待事务队列。每当调度器线程从事务日志中读取一个事务时，它会为事务读写集合中的所有键添加一个锁请求。*这就是为什么 Calvin 需要在执行事务之前知道事务的读写集合。* 竞争同一锁的事务根据锁队列的先进先出顺序获取锁。当事务获得了它需要的所有锁时，它就可以执行了。事务完成后，将从锁表中移除，允许队列中的所有事务获取该锁。注意，不竞争共同锁的事务永远不会相互阻塞，因此它们可以并行执行。另一个有趣的地方是，与 2PL 不同，使用确定性锁定永远不会出现死锁。 [图 4. 确定性锁定。T1 和 T4 可以执行。T2 和 T3 将被阻塞。] ### 存储层 一旦事务准备好执行，就可以由其中一个执行器线程执行它。我们可以根据需要设置任意数量的执行器线程。一个事务可能读取或写入多个分片中的键。因此，一个分片上的执行器可能无法独立执行该事务，因为要执行事务的逻辑，它需要读取托管在其他分片上的键。例如，考虑事务 T，它在分片 A 上读取值 x，并在分片 B 上将值 y 更新为 x 加 1。 不同分片上的执行器线程协作执行事务。具体来说，每个执行线程的工作流程如下： - **读写集合分析**：每个执行线程首先检查读写集合，看看事务涉及哪些分片。每个为事务写入值的节点称为该事务的**活动节点**。在上面的例子中，分片 A 上的执行线程看到事务 T 正在分片 B 上写一个值。 - **读取本地对象**：每个执行线程读取当前节点上托管的键。在上面的例子中，节点 A 上的执行线程读取 x 的值。 - **服务远程读取**：每个执行线程将本地读取到的值发送给事务的所有活动节点。在上面的例子中，节点 A 上的执行线程将 x 的值发送给节点 B 上的对应线程。 - **收集远程读取**：如果执行线程运行在活动节点上，它会等待直到收到来自其他节点的所有读取值。在上面的例子中，节点 B 上的执行线程会阻塞，直到收到来自节点 A 上的对应线程的 x 值。 - **执行**：一旦活动节点获得到所有读取值，它就执行事务。在上面的例子中，B 上的执行线程在收到 x 值后解除阻塞，并更新 y 的值。 ## 复杂情况 #### 依赖事务 如前所述，Calvin 需要知道事务执行前的读写集合。然而，有时在执行业务逻辑之前无法知道完整的读写集合。例如，一个事务可能需要先读取某个对象，然后根据其值决定更新哪些键。Calvin 如何支持这类事务呢？这类事务被称为**依赖事务**。Calvin 通过一个两阶段方案支持依赖事务。在第一阶段，它运行一个查询，执行所有必要的读取以确定事务的完整读写集合。为了加速这一阶段，Calvin 使用一种称为**侦察查询**的低成本、低隔离级别且不复制的读查询来读取键。请注意，普通的只读事务必须经过正常