一致性哈希
为了缓解该问题，一些数据库（例如Apache Cassandra和Riak）使用一种叫作一致性哈希（consistent hashing）的分区方案。如前所述，路由键的值被输入哈希函数，返回的哈希值被映射到一个环上，以便在超过最大值之后回卷到最小值。
每个节点在环上拥有自己的位置，负责前一个节点到当前节点之间的值范围。使用一致性哈希能减少维持数据均衡所需的移动次数：节点离开或加入只会影响到环上与该节点直接相邻的节点，而不影响整个集群。定义中的一致性表示：当哈希表大小发生变化时，如果我们有K个可能的哈希键和n个节点，平均而言，我们仅需移动K/n个键。也就是说，一致性哈希函数的输出受函数范围变化的影响最小[KARGER97]。
7 Percolator分布式事务
回到分布式事务上来，由于允许一些读取和写入异常，隔离级别可能很难论证。如果应用程序不要求可串行化，避免写入异常的一种方法是使用SQL-92中描述的快照隔离（Snapshot Isolation，SI）事务模型。快照隔离保证事务内的所有读取结果与数据库的某个快照一致。快照中包含了在事务的开始时间戳之前提交的所有值。如果存在写-写冲突（即，两个并发执行的事务尝试写入同一单元格），那么只有一个能够提交成功。
这种策略通常称为首个提交者胜利（first committer wins）。快照隔离能避免读偏斜（read skew）—一种在读已提交隔离级别下允许的异常。例如，x、y之和应该等于100。事务T1执行操作read(x)读到值70。T2更新两个值write(x, 50)和write(y, 50)并提交。如果T1尝试运行read(y)，并根据T2新提交的y的值（50）继续执行事务，将会导致不一致。T1在T2提交之前读到的值x与新的y值彼此不一致。而快照隔离仅会让小于某个特定的时间戳的值对事务可见，新的y值对T1不可见[BERENSON95]。快照隔离有几个实用的特性：
- 它只允许对已提交数据的可重复读取。
- 值是一致的，因为它们是从某个时间戳的快照中读取的。
- 冲突的写入将被中止并重试，以防止产生不一致。
尽管如此，快照隔离下的操作历史不是可串行化的。由于只有对相同单元格的冲突写入会被中止，因此仍可能发生写偏斜（write skew）（参见5.3.3节）。写偏斜发生在两个事务修改的值集合不相交时，每个事务本身的写入都不违反约束。两个事务都能提交，但两个事务的写入合在一起就会违反这些约束。快照隔离提供的语义可以满足许多应用程序的需求，其主要优势在于读的效率较高，因为不需要加锁—快照数据是无法修改的。
Percolator是一个在分布式数据库Bigtable（参见1.3.4节）上实现事务API的库。这是在现有系统之上构建事务API的一个很好的例子。Percolator用不同的列保存数据记录、已提交的数据点位置（写入元数据）和锁信息。为了避免竞争条件，它使用Bigtable提供的条件修改API，该API允许在单个远程调用中执行读-修改-写操作。
每个事务必须和授时节点（timestamp oracle）通信两次（授时节点负责为整个集群提供单调递增的时间戳）：一次获取事务开始时间戳，另一次是在提交过程中。写入会先被缓存起来，最后由客户端驱动进行两阶段提交（请参阅13.2节）。图13-9展示了在执行事务的各步骤期间表的内容如何变化：
- a) 初始状态。
执行完上一个事务后，TS1是两个账户的最新时间戳。
没有锁。
- b) 第一个阶段称为预写（prewrite）。
事务尝试为所有写入的单元格加锁。
其中一个锁被标记为主（primary）锁，用于客户端恢复。
事务会检查是否存在可能的冲突：
是否存在其他事务已经用更晚的时间戳写入了数据，或者在任何时间戳下是否存在未释放的锁。
如果检测到冲突则中止事务。
- c) 如果成功获取了所有锁即排除了冲突的可能性，事务便可以继续执行。
第二阶段中，客户端开始释放这些锁，首先释放主锁。
它用写记录替换锁，通过该操作让写入对外可见，并更新写入元数据为最新数据点的时间戳。
由于客户端在提交事务时可能会发生故障，因此我们需要确保进行到一半的事务能被提交或回滚。如果之后的事务遇到一个不完整的状态，则应尝试释放主锁并提交事务。如果主锁已经释放，那么事务内容必须被提交。同一时刻只可以有一个事务持有某个锁，而且所有状态转换都是原子的，因此不存在两个事务都在尝试修改内容的情况。快照隔离是一种很重要也很有用的抽象，经常用在事务处理中。它简化了语义，排除了一些异常情况，并为改善并发性和性能提供了机会，因此许多MVCC系统都提供这种隔离级别。
一个基于Percolator模型的数据库的例子是TiDB（Ti代表钛元素）。TiDB是一个强一致、高可用、可水平扩展的开源数据库，兼容MySQL。
8 协调避免
讨论可串行化性的成本并尝试减少协调量，同时仍提供强大的一致性保证的另一个例子是协调避免[BAILIS14b]。在保持数据完整性约束的前提下，只要操作满足约束融合性，协调是可以避免的。约束融合性（Invariant Confluence或I-Confluence）定义为这样一种属性：两个满足约束但存在分歧的数据库状态一定能够合并为一个有效的最终状态。这里说的约束对应ACID中的一致性。
由于可以将任何两个有效状态合并为一个有效状态，因此满足约束融合性的操作不需额外协调就可以直接执行，这显著地提高了性能和可扩展性。
为了保持约束，除了定义修改数据库的操作之外，我们还必须定义一个合并（merge）函数，它接受两个状态作为输入。当状态被独立地修改时，可以用合并函数将分歧的状态重新收敛。
事务在本地的数据库版本（快照）上执行。如果事务执行需要用到其他分区中的某些状态，就把该状态也放到本地。事务提交时，产生的本地快照的改动会被迁移并和其他节点的快照合并。允许协调避免的系统模型必须保证以下性质：
全局有效性
无论对于合并后的状态，还是刚提交的存在分歧的状态，所需的约束条件始终是满足的，事务不会观察到无效
的状态。
可用性
如果所有包含状态的节点对客户端都是可达的，那么事务必然会成功提交，除非提交将违反某个事务约束，这种情况下事务会中止。
收敛
节点可以独立维护其本地状态，但如果之后没有新的事务并且网络分区不会无限持续下去，它们一定能够达到相同的状态。
一个实现协调避免的例子是读原子性多分区（Read-Atomic Multi Partition, RAMP）事务[BAILIS14c]。RAMP使用多版本并发控制和当前进行中操作的元数据来从其他节点获取缺失的状态更新，从而允许读取和写入操作能够并发进行。例如，如果读取操作与某些修改相同的条目的写入操作存在重叠，这种情况可以被检测出来，必要时，还可以通过一轮额外的通信，利用正在进行的写入操作的元数据获取所需的信息来对其进行修复。
在分布式环境下使用基于锁的方法可能不是个好主意，相反，RAMP提供以下两个性质：
同步独立性
一个客户端的事务不会阻塞、中止或是强迫另一个客户端的事务等待。
分区独立性
客户端无须联系那些事务不涉及的分区。
RAMP引入了读原子性（read atomic）隔离级别：事务不会观察到来自进行中的、未提交的或中止事务的正在进行的状态变更。换句话说，事务更新要么全都对并发事务可见，要么全都不可见。根据该定义，读原子性隔离级别还排除了断裂读（fractured read）：即事务仅观察到其他事务执行的写入的一个子集。
RAMP提供原子的写可见性，而不需要互斥—其他解决方案（例如分布式锁）往往将这两者耦合在一起。这意味着事务不会相互阻塞。
RAMP分发事务元数据，这些元数据允许读取操作检测到并发进行的写入。通过元数据，事务可以检测到较新的记录版本，找到并获取最新的记录版本，然后对它们进行操作。为了避免协调，所有本地的提交决定也必须在全局范围内生效。在RAMP中，这是通过以下要求解决的：当某个分区中的写入变为可见时，此事务中所有其他分区的写入也必须可见。
为了使得读写操作不阻塞其他并发的读写操作，同时在本地和整个系统范围内（事务修改过的所有其他分区中）都保持读原子性隔离级别，RAMP使用两阶段提交来处理写入操作：
准备阶段
第一阶段准备写操作并将其放到相应的目标分区中，但不使其对外可见。
提交/中止阶段
第二阶段将事务的写操作进行的状态更改变得可见，使其在所有分区上原子地变得可用，或者回滚更改。
RAMP允许一个记录同时存在多个版本：最新值、进行中的未提交更改，以及被后来的事务覆盖掉的过期版本。之所以需要保留过期版本，仅仅是为了正在进行中的读取请求。只要所有并发的读操作结束，就可以丢弃过期的值。
为了防止、检测、避免并发操作之间的冲突，往往需要引入协调开销，因此，想让分布式事务高效且可扩展并不容易。系统越大，承载的事务越多，产生的协调开销也就越大。本节中描述的方法尝试用约束条件来确定可以避免协调的地方，从而减少协调的量，只在绝对必要时才付出全部的代价。
9 本章小结
本章中，我们讨论了实现分布式事务的几种方法。首先，我们讨论了两种原子提交算法：两阶段提交和三阶段提交。这两种算法的最大优点是易于理解和实现，但也有一些缺点。在2PC中，协调者（或至少是它的代替者）必须在整个提交过程中都存活，这会大大降低可用性。3PC在一些情况下取消了这个要求，但在网络分区的情况下可能发生脑裂。
现代数据库系统中的分布式事务通常使用共识算法来实现，我们将在第14章中进行讨论。例如，本章讨论的Calvin和Spanner都使用Paxos。
共识算法比原子提交算法更复杂，但是具有更好的容错性，并且将决策结果与发起者分离开来，允许参与者决定一个值，而不是决定是否接受那个值[GRAY04]。
更多阅读
如果你想了解更多本章中提到的概念，可以参考以下来源：
原子提交与本地事务处理及恢复子系统的集成
Silberschatz, Abraham, Henry F. Korth, and S. Sudarshan. 2010. Database Systems Concepts (6th Ed.). New York: McGraw-Hill.
Garcia-Molina, Hector, Jeffrey D. Ullman, and Jennifer Widom. 2008. Database Systems: The Complete Book (2nd Ed.). Boston: Pearson.
分布式事务领域的最新进展（按时间顺序排列，此列表并不详尽）
Cowling, James and Barbara Liskov. 2012. “Granola: low-overhead distributed transaction coordination.” In Proceedings of the 2012 USENIX conference on Annual Technical Conference (USENIX ATC �12): 21-21. USENIX.
Balakrishnan, Mahesh, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabha-karan, Michael Wei, John D. Davis, Sriram Rao, Tao Zou, and Aviad Zuck. 2013.“Tango: distributed data structures over a shared log.” In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP �13): 324-340.
Ding, Bailu, Lucja Kot, Alan Demers, and Johannes Gehrke. 2015. “Centiman: elastic, high performance optimistic concurrency control by watermarking.” In Proceedings of the Sixth ACM Symposium on Cloud Computing (SoCC �15): 262-275.
Dragojevi, Aleksandar, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. 2015. “No compromises: distributed transactions with consistency, availability, and performance.” In Proceedings of the 25th Symposium on Operating Systems Principles(SOSP �15): 54-70.
Zhang, Irene, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. “Building consistent transactions with inconsistent replication.” In Proceedings of the 25th Symposium on Operating Systems Principles(SOSP �15): 263-278
