4 Calvin分布式事务
我们已经了解了同步的代价以及相关的几种事务方法。但是，还有其他方法可以减少争用并减少事务持有锁的总时间。一种方法是让各副本在获取锁并继续执行之前，就执行顺序和事务边界达成一致。如果我们能够做到这一点，节点故障就不会导致事务中止，因为节点可以从并行执行同一事务的其他参与者中恢复状态。
传统数据库使用两阶段锁或乐观并发控制来执行事务，并没有确定的事务顺序。这意味着必须协调各节点以保证事务顺序。而确定性事务顺序消除了执行阶段的协调开销，因为所有副本获得相同的输入，所以也会得到等同的输出。这种方法通常称为Calvin—一种快速的分布式事务协议[THOMSON12]。使用Calvin实现分布式事务的一个著名例子是FaunaDB。
为了获得确定性顺序，Calvin使用定序器（sequencer），它是所有事务的入口点。定序器决定事务的执行顺序，并建立全局事务输入序列。为了最大限度地减少竞争和批量决策，Calvin将时间线切分成epoch。定序器收集事务并将其分组到短时间窗口内（原论文使用10毫秒的窗口），这些窗口也就成为复制单元，因此不需要为每个事务单独进行通信。
当一个事务批被成功复制之后，定序器会将其转发给调度器（scheduler），它负责编排事务的执行。调度器使用确定性调度协议，可以并行执行部分事务，并同时保留定序器指定的串行执行顺序。将事务应用于特定状态只会产生由事务指定的更改，并且事务顺序是预先确定的，因此，各副本无须与定序器做更多的通信。
Calvin中的每个事务具有读取集（事务执行的依赖，即执行事务所需的当前状态的数据记录集合）和写入集（事务执行的结果，也就是它的副作用）。Calvin本身不支持事务依赖于额外的读取来决定读取集和写入集。
Calvin的工作者线程（由调度器管理）的执行过程分为四个步骤：
1. 分析事务的读取集和写入集，用读取集确定节点本地的数据记录，并创建活跃参与者的列表（即包含写入集元素且将对这些数据进行修改的参与者）。
2. 收集执行事务所需的本地数据，换句话说，收集恰好位于该节点上的读取集记录。收集到的数据记录将被转发给相应的活跃参与者。
3. 如果当前工作线程正在一个活跃参与者节点上执行，它将接收到其他参与者发来的数据记录，对应于步骤2中执行的操作。
4. 最后，执行一批事务，将结果持久化到本地存储中。不用将执行结果转发到其他节点，因为它们接收相同的事务输入，可以自己在本地执行并持久化结果。
一个典型Calvin的实现将定序器、调度器、工作者和存储子系统放在一起，如图13-7 所示。为了确保各个定序器就当前epoch/批包含哪些事务达成共识，Calvin使用Paxos共识算法（参见14.3节）或异步复制（其中某个专用副本作为领导者）。尽管使用领导者可以改善延迟，但节点必须重建故障领导者的状态才能继续，因此也带来了更高的恢复成本。
5 Spanner分布式事务
Calvin常常被拿来和另一个称为Spanner[CORBETT12]的分布式事务方法进行对比。Spanner的实现（或派生）包括几个开源数据库，最著名的是CockroachDB和YugaByte DB。Calvin通过在定序器上达成共识来建立全局事务执行顺序，Spanner则在每个分区的共识组（换句话说，每个分片）上使用两阶段提交。Spanner的架构相当复杂，本书中我们仅介绍一些高层次上的细节。
为了实现一致性并建立事务的顺序关系，Spanner使用TrueTime：一种高精度的物理时钟API，同时也暴露时钟误差的范围，允许本地操作中引入人为的减速以等待时钟误差范围过去。
每个写入操作必须通过Paxos组的领导者，而读取可以直接在最新副本的tablet上进行。领导者上有锁表（lock table）和事务管理器，锁表用于使用两阶段锁（参见5.3.8节）机制来实现并发控制，事务管理器负责跨分片的分布式事务。需要同步的操作（例如事务内的写入和读取）必须先从锁表中获取锁，而其他操作（快照读）可以直接访问数据。
对于跨分片的事务，Paxos组领导者必须协调并执行两阶段提交以保证一致性，并使用两阶段锁保证隔离性。2PC算法要求所有参与者都存活才能成功提交，因而可能会损害可用性。而Spanner使用Paxos组代替单个节点作为参与者，解决了这一问题。这意味着即使组内的某些成员宕机，2PC也可以继续运行。在Paxos组内部，只有领导者节点会参与2PC。
Paxos组用于在多个节点之间一致地复制事务管理器的状态。在执行事务时，Paxos组的领导者首先获取写锁，并选择一个写入时间戳—该时间戳必须比之前任何事务的时间戳要大，并通过Paxos记录一条2PC的prepare日志。事务协调者收集时间戳，随后生成一个大于任何准备时间戳（prepare timestamp）的提交时间戳（commit timestamp），并通过Paxos记录一条commit日志。然后，事务协调者需要等待直到提交时间戳过后，因为它必须保证客户端只能看到时间戳已经过去的事务结果。之后，它将此时间戳发送给客户端和各个领导者，领导者将一条commit日志连同新的时间戳一同记录到其所在的Paxos组中，此时便可以释放锁。
单分片事务无须与事务管理器通信（并且之后也不必进行跨分区的两阶段提交），因为查询Paxos组和锁表足以保证事务顺序和分片内部的一致性。
Spanner读写事务提供了称为外部一致性（external consistency）的序列化顺序：事务时间戳反映了序列化顺序，即使在分布式事务中也是如此。外部一致性具有与可线性化（linearizability）等效的实时属性：如果事务T1在T2开始之前提交，则T1的时间戳小于T2的时间戳。
总结一下，Spanner使用Paxos进行一致的事务日志复制，使用两阶段提交进行跨分片事务，使用TrueTime进行确定性事务排序。相比Calvin [ABADI17]，Spanner跨分区事务的成本更高，因为多出了一个两阶段提交的过程。理解这两种方法都很重要，依靠它们，我们能够在分区的分布式数据存储中执行事务。
6 数据库分区
讨论Spanner和Calvin时，我们经常用到分区（partitioning）这个词。现在我们来更详细地讨论一下它。对于大多数现代应用程序而言，将所有数据存储在单个节点上是不现实的，因此许多数据库都使用分区：逻辑上将数据分成较小的、易于管理的段。
数据分区最直接的方法是将数据划分成多个范围，并允许每个副本集（replica set）只管理特定的范围（分区）。执行查询时，客户端（或查询协调者）需要基于路由键将读写请求路由到正确的副本集。这种分区方案通常称为分片（sharding）：每个副本集作为数据某个子集的单个来源。
为了最有效地使用分区，必须考虑负载和值的分布并据此确定分区大小。这意味着可以将读写负担较重的范围分裂成更小的分区，从而分散负载。同时，如果某些范围包含的值比其他范围更密集，最好也将它们分裂成更小的分区。例如，假如我们选择邮编作为路由键，由于人口分布并不均匀，一些邮编范围可能分配到更多的数据（比如人或订单）。
当集群添加或删除节点时，数据库必须重新分区数据以保持均衡。为了保证数据迁移过程的一致性，我们应当在更新集群元数据及开始将请求路由到新的位置目标之前先搬运数据。一些数据库可以进行自动分片（auto-sharding），使用算法来决定最佳分区方式，并重新放置数据。这些算法通常基于各分片的读取和写入负载以及数据量等信息来进行决策。
为了从路由键找到目标节点，一些数据库计算路由键的哈希值，并通过某种方式将哈希值映射到节点ID。使用哈希确定副本位置的一个优点是能够减少范围热点，因为哈希值与原始值的排列顺序不同。两个字典序接近的路由键原本会被放在同一副本集上，但如果用哈希值，则会被放在不同副本集上。
将哈希值映射到节点ID的最直接的方法是将哈希值除以集群大小再取其余数（取模）。如果系统中有N个节点，则目标节点ID可以通过hash(v) mod N算出。该方法的主要问题是，每当添加或删除节点、集群大小从N更改为N'时，hash(v) mod N'算出的很多值都和原来不同。这意味着大部分数据都要被移动。
Spanner提供三种主要的事务类型：读写事务、只读事务和快照读。读写事务需要加锁，使用悲观的并发控制，并且存在领导者（leader）副本。只读事务是无锁的，可以在任何副本上执行。只有在读取最新时间戳时才需要领导者，领导者负责从Paxos 组中获取最后提交的值。对特定时间戳的读取是一致的，因为数据有版本，而快照的内容一旦写入就无法更改。每个数据记录都会被分配一个时间戳，记录了写入该值的事务的提交时间。这也意味着每条记录可能存在多个时间戳的版本。
图13-8展示了Spanner的架构。每个spanserver（副本，向客户端提供数据的服务器实例）包含多个tablet，每个tablet对应一个Paxos（参见14.3节）状态机。副本被分组为副本集，称为Paxos组，这是数据放置和复制的单元。每个Paxos组都有一个长期的领导者（参见14.3.4节）。在处理跨分片的事务时，领导者会相互通信。
