共计 2982 个字符，预计需要花费 8 分钟才能阅读完成。
Spanner 要满足的 external consistency 是指：后开始的事务一定可以看到先提交的事务的修改。所有事务的读写都加锁可以解决这个问题，缺点是性能较差。特别是对于一些 workload 中只读事务占比较大的系统来说不可接受。为了让只读事务不加任何锁，需要引入多版本。在单机系统中，维护一个递增的时间戳作为版本号很好办。分布式系统中，机器和机器之间的时钟有误差，并且误差范围不确定，带来的问题就是很难判断事件 (在本文，事件指分布式事务版本号) 发生的前后关系。反应在 Spanner 中，就是很难给事务赋予一个时间戳作为版本号，以满足 external consistency。在这样一个误差范围不确定的分布式系统时，通常，获得两个事件发生的先后关系主要通过在节点之间进行通信分析其中的因果关系(casual relationship), 经典算法包括 Lamport 时钟等算法。然后，Spanner 采用不同的思路，通过在数据中心配备原子钟和 GPS 接收器来解决这个误差范围不确定的问题，进而解决分布式事务时序这个问题。基于此，Spanner 提供了 TrueTime API，返回值实际为一个区间[t-ε,t+ε]，ε 为时间误差，毫秒级，保证当前的真实时间位于这个区间。
Spanner 是一个支持分布式读写事务，只读事务的分布式存储系统，只读事务不加任何锁。和其他分布式存储系统一样，通过维护多副本来提高系统的可用性。一份数据的多个副本组成一个 paxos group，通过 paxos 协议维护副本之间的一致性。对于涉及到跨机的分布式事务，涉及到的每个 paxos group 中都会选出一个 leader，来参与分布式事务的协调。这些个 leader 又会选出一个大 leader，称为 coordinator leader，作为两阶段提交的 coordinator，记作 coordinator leader。其他 leader 作为 participant。
数据库事务系统的核心挑战之一是并发控制协议。Spanner 的读写事务使用两阶段锁来处理。分布式读写事务请求到达 coordinator leader 后，coordinator leader 运行两阶段提交协议，将读写请求发给 participant，pariticpant 和 coordinator leader 开始加读，写锁。最后 commit 的时候，读写锁解除。
如第一段所述，给事务赋予一个时间戳版本号是这样一个分布式存储系统的核心。下面先说如何确定读写事务的版本号，再说只读事务。
前面已经说了两阶段提交过程中两阶段锁的过程，这里就省略这些，只讨论两阶段提交过程中如何确定最后的读写事务的时间戳版本号。
读写事务
读写事务开始时，coordinator leader 首先调用 TrueTime API，获得一个时间区间 [t1-ε1,t1+ε1]，然后给所有的 participants 发送 prepare 消息，participants 收到 prepare 消息后，调 TrueTime API 返回区间[PB,PE]，然后取 PB 和这个 participants 维护的已 commit 的事务版本号的最大值。记 participant 维护的已 commit 的最大事务时间戳为 maxtimestamp, 那么将 max(maxtimestamp+1, PB) 返回给 coordinator leader。coordinator leader 收集到所有 prepare 的时间戳后，从中选出一个最大的，记作 maxpreparetimestamp，同时 coordinator 需要再次调用一次 TrueTime API，获得时间区间 [t2-ε2,t2+ε2]，为了保证这个分布式事务的时间戳确实位于这个分布式事务执行过程中的某个点，coordinator leader 必须为这个分布式事务选择一个介于[t1+ε1,t2-ε2] 的时间戳。显然这需要 t1+ε1 < t2-ε2. 可以看出，Spanner 必须等到 t1+ε1 < t2-ε2 成立之后，才能提交这个事务。另外，这个分布式事务的时间戳还必须满足一个条件，就是大于 maxpreparetimestamp。从 B 的角度来看，如果本地已提交事务版本号比要读的版本号大，就可以读。这就要保证后面提交的单机事务和分布式事务版本号都要比现在已提交事务的版本号更大。否则，读的时候可能会有事务插进来，导致都到的数据可能不是一个快照。
另外，一台机器在收到快照读时，有可能需要阻塞。举个例子，在分布式系统中，即有分布式事务也有单机事务，以 A，B，C 为例，A 为 coordinator leader，B 和 C 为 participant，以 B 为例，假设 B 当前维护的本机最大的 commit 时间戳为 100，现在从 A 来了一个分布式事务 T1 的 prepare 请求，B 返回了 101 给 A，在这个分布式事务 commit 之前，B 机器来了一个单机事务 T2，并且先于 T1 提交，时间戳为 105，而 A 可能为这个分布式事务指定的版本号为 104. 显然，如果在 T1 提交前来了一个大于 101 比如 110 的快照读事务，这个快照读事务必须被阻塞住直到 T1 提交才能向客户端返回结果，因为 B 不知道 T1 这个还未 commit 的事务最后的时间戳是多少。
只读事务
一种方法是询问一边所有的 participants，从所有的 commit timestamp 中拿出最大的作为时间戳去读即可。或者调用 TrueTime API，将右区间作为只读事务的版本号即可。
下面说一下两阶段提交的错误处理。
两阶段提交协议由于协调者和参与者的故障可能会有严重的可用性问题。Spanner 的两阶段提交实现基于 Paxos 协议，每个 participant 和 coordinator 本身产生的日志都会通过 Paxos 协议复制到自身的 Paxos group 中，从而解决可用性问题。同样以 A，B，C 三份数据为例，他们分别有三个副本，记作(A1，A2，A3)，(B1，B2，B3)，(C1，C2，C3)，每组作为一个 Paxos group，内部通过 paxos 协议保证一致性。假设，A1，B1，C1 分别为各自 paxos group 的 leader，A1 为 coordinator leader。
Prepare 阶段：A1 给 B1 和 C1 发送 prepare 消息后，假设 B1 挂了，A1 等待超时，A1 给 C1 发送 rollback。B1 后续回滚分为两种情况：1. B1 在持久化 prepare 消息之前挂了，B1 恢复后可自行回滚 2. 如果 B1 持久化 prepare 消息之后挂了，B1 自身可以回放日志得知事务未决，主动联系(A1,A2,A3)。A1 给 B1，C1 发送 prepare 消息之后，自己挂了，同样，A1 通过回放日志可以得知。实际上，A1 本身挂了之后，A2 和 A3 通过选主协议马上会选出一个新的 leader，不至于影响到可用性。
Commit 阶段：A1 给 B1，C1 发送 commit 消息，B1 commit 成功，C1 挂了，C1 起来后，如果 C1 之前没有持久化 commit 消息，则 A1 主动要求 C1 继续 commit。如果 C1 之前已经持久化了 commit 消息，则自己 commit。如果 C1 由于某些原因，始终 commit 不成功，则由上层业务进行回补操作。
本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-03/115175.htm
