1. Spanner的设计概要

Spanner这是⼀个很少见的例子，该系统提供了针对分布范围很广的分离数据的分布式事务，这些数据可能分散在整个Internet下不同的数据中心之中。

Spanner具备了分布式事务、将数据分散在网络上以获得容错能力、确保在每个想要使用该数据的人的附近都有该数据的⼀份副本，为了做到以上这些，spanner使⽤了至少两个很巧妙的思想：

Spanner使用了两阶段提交，但为了避免⼆阶段提交中因为事务协调器崩溃而导致所有人都被阻塞这⼀情况，他们在Spanner中使⽤了Paxos算法来容错。
Spanner通过同步时间（TrueTimeAPI）来做到非常高效的只读事务。该系统实际上十分成功。
外部一致性（`external consistency`）是在Spanner中被提出来的，因此需要了解一下这意味着什么。

在Spanner中，他们真的对只读事务（只⽤于读取数据）的性能很感兴趣，很明显，他们也需要强⼀致性（Strong Consistency）。也需要外部一致性：这意味着，如果提交了⼀个事务，然后当它结束提交时，另⼀个事务就会开始执行，这第二个事务需要去看到由第一个事务所做的任何修改。即能看到最近所做的更改，有一点像线性一致性（linearizability）。

1.1 spanner servers的物理布局

上图是Spanner使用的物理布局。图上有多个数据中心，这里我们画3个，实际的数量应该更多。然后将数据进行分片，这里将数据通过key进行拆分，分散到许多服务器上。

这些数据中心一般是跨地域的，如DC1在纽约，DC2在加利福尼亚，DC3在匹兹堡。

可能在数据中心1中的一台服务器保存的是key以a开头的数据，另⼀台服务器保存的则是key以b为开头的数据，下面依次类推。即以key的开头字母的不同进行数据分片，完全覆盖最多需要26个服务器。可以看到每份在DC1中分片的数据都被复制备份到别的数据中心之中。不同数据中心中保存的数据是一样的，做到容错。

每个数据中心都有多个Spanner client，这些client其实就是web服务器，当我们需要使用Spanner的某些服务时，我们打开特定产品所在的网页，此网页会连接到其中一个数据中心的某个web服务器上（Spanner Client），也就是和其中⼀个Spanner client建立连接。

上图中跨数据中心的相同分片组成一个Paxos组，Spanner用的是Paxos的⼀种变体，它里面有leader，这和我们所熟悉的Raft非常相似。对于⼀个给定的数据分片，它都会由⼀个Paxos实例来管理该数据分片对应的所有replica。不同Paxos组的Paxos实例是彼此独立的，每个Paxos组都有属于自己的leader，各自维护着独立的数据版本协议。

之所以每个数据分片对应Paxos实例彼此独立，是因为，这样做可以让我们对这些数据并行加速处理，提高了并行吞吐量。

因此，如果一个client需要进行写操作，他要先把写请求正确发送到这个数据分片所在的Paxos组中的leader，leader会把关于操作的日志发送给它所有的follower，follower收到日志后严格按照顺序执行。

在Paxos组中，每个服务器都运行着Paxos实例，Spanner论文中有说明这一点（见图），这也类似于Raft。

这里放上论文中的Spanner Server的软件栈的图，Paxos实例运行在每个DC中的每个数据分片服务器上。

1.2 SpannerServer物理布局总结

上述的设计有几个点需要总结说明一下：

使用分片是为了提高并行吞吐量，因为涉及到不同分片的client的请求可以同时被处理而不会互相干扰。

将数据的多个副本放在不同的数据中心，这么做有两个原因：

容错：一个数据中心崩溃了，这一般不会影响到在另一个城市的数据中心。但是这么做需要付出代价：因为我们得通过Paxos协议和离leader很远得不同数据中心中的follower进行通信。
将数据放在位于不同城市的数据中心中，这可以让这些靠近该数据副本的所有不同的client去使用该数据，即实现临近副本读取，加快读取的速度。

该设计的重点是让当地和离client最近的replica来处理读请求，这样做的话，读取起来既快又准。但是Spanner中使用的是类似于Raft的修改版Paxos协议，因此如果我们允许client去读取当地（临近）的replica的数据副本来提高速度的话，他可能会读到过时的数据。（类Raft协议的大多数投票特性）。

因此Spanner需要这种外部一致性思想（External Consistency），即让每次读操作看到的都是最新的数据。所以得通过某种方式来处理本地replica上数据的版本可能。有点落后的情况。

此外，一个事务可能会涉及到多个数据分片，这就涉及到了多个Paxos组，该事务可能要对不同分片上的数据进行读写，因此这就需要分布式事务。下面将会重点讲Spanner的事务机制。

与上节课学的Distributed Txns的场景几乎相同。

2. Spanner的读写型事务机制

这里教授举了一个例子，向我们展示了在实际应用中，如何把共识协议与两阶段提交（分布式事务）结合起来使用，并且说明用到的相关配置的情况：下面这张图是结果图，需要进行依次的说明：

Spanner实现了读写型事务，这与只读事务比起来是相当的不同的。因此这个例子是针对于读写型事务的：

2.1 例子-读写型事务说明

上图是一个银行转账的例子，X与Y是银行账户，X与Y的存款信息存在不同的数据分片中。我们要做的是从Y中取1元转到X中，这涉及到不同的数据分片中的操作，下面对该分布式事务的操作进行逐步溯源。

2.2 操作溯源-读写型事务

首先我们需要一个SpannerClient与某一个DC进行交互，该Client发起了这个事务。

Spanner想要对两阶段提交和两阶段锁进行完全支持，但是与上周所讲的有一个很大的不同在于：这里不会使用单独一个服务器作为参与者和事务协调器，而是使用由多台服务器所组成的Paxos组来充当参与者和事务协调器的角色，以此提高容错能力。

首先，client会选择一个唯一的事务id给他接下来要发送的所有消息打上标记，以告诉参与者这些操作所属的事务是哪一个。
如图所示，尽管代码看起来像是在读取x，然后对x进⾏写⼊，接着读取y，再对y进行写入，但事实上，它首先得去执行所有的读操作，然后在最后再同时去执行所有的写操作，最后的同时执行写操作本质是2PC中commit操作的一部分。
Client会与Paxos组中的leader进行交互，leader中维护着自己的那部分分片的相关锁信息，获取锁释放锁都遵循2PL协议。假设client很幸运，没有别的client在使用他要用到的数据，该client顺利的获取到了自己要读取的信息，并拥有相关数据上的读锁。
之后，client首先会选择其中的一个Paxos组来作为事务协调器使用，client会提前做好这件事，并将作为事务协调器的Paxos组的id发送出去。因此在上图中，存储Y数据的Paxos组的leader也是该事务的事务协调器。
之后就是由事务协调器开始协调写操作：coordinator发送关于x的写操作的日志给x所在paxos组的leader（Prepare），leader将日志发送给自己的follower，当leader收到大多数follower的响应后，X的leader可以发送一个prepared消息给事务协调器。
事务协调器同理也会向Y所在的Paxos组执行相同的操作，只不过这里Y的leader恰好是事务协调器。
当事务协调器收到了所有涉及到的Paxos组的prepared后，事务协调器会去提交这个事务，当事务协调器将commit消息落地后，才会给Paxos组们的leader发送commit消息，一旦不同的Paxos组都把这条Commit消息落地到日志中了，每个shard就可以去apply这些log，将这些log涉及到的数据变化落地到磁盘中，并释放相关的数据锁。

注意，在Raft中，针对于某条单独的log而言，当大多数的节点已经保存了这条log（commited），就说明该log可以被apply了。但是在分布式事务的场景下，只有Paxos组从协调器处收到了最终的该事务的commit消息，他才可以apply那些已经commit的、且属于该事务的log。
这样其他事务就可以使用这些数据了。

2.2.1 事务协调器—单点故障

因此，Spanner使用完全标准的2PL来获取有序性，使用完全标准的2PC来获得使用分布式事务的能力。人们一般不愿意在现实生活中使用2PC：因为事务协调器是单点故障，这会导致阻塞。

Spanner通过对事务协调器进行复制解决了这个问题，事务协调器自身就是一个基于Paxos的复制状态机。如上图中，Y数据所在的Paxos组同时也是事务协调器的Paxos组。若当前的事务协调器组的leader故障了，他可以任意的选择组中的一个服务器来接收事务协调器组leader的工作，因为都是它的复制状态机。

因此，让事务协调器具有复制容错功能，这很有效的消除了两阶段提交带来的问题：事务协调器在持有锁的情况下发生故障会导致阻塞（在事务协调器不具备复制容错时，别的参与者只能阻塞等待事务协调器恢复）。

2.2.2 消息传输时延

不同的数据中心分布在不同的城市，因此有些距离client较远的Paxos组中的leader、或者是距离事务协调器组较远的那些参与者，他们之间发送消息可能需要较长的时延。两个服务器之间的消息传输快慢取决于二者地理位置上的距离，也取决于执行事务的类型。

读写型事务还是很慢，只读型事务很快，因此如果能提前知道执行事务的类型，有利于调整执行策略。

若只执行只读事务，这意味着Spanner可以使用速度更快、更加精简、并且不用发送太多消息的方案。下面将单独开一个章节来具体的说明Spanner只读型事务的设计。

3. Spanner只读型事务机制

只读型事务（Read-Only Txn）的工作方式用到的通信信息是读写型事务中的一部分，但这并不意味着二者的设计思想一样，事实上他们俩的设计思想是完全不同的。

首先，在Spanner中，只读型事务的设计消除了读写型事务中存在的两种巨大的成本消耗问题。

3.1 设计点1：local read

不同于读写型事务，只读型事务被允许从本地的replica（离当前client最近）中读取数据：如果有一个replica是client以及事务执行所需要的，并且他在本地数据中心，无论数据的版本是什么，你可以从本地的replica中读取数据。毫无疑问从本地读取数据要比每次向数据所在的Paxos组中的leader请求数据要快的多。

但是，风险在于，我们读到的数据版本可能不是最新的，因此Spanner要采取一些措施来保证数据的版本，下面会细讲这块内容。

3.2 设计点2：Read-Only Txn的无锁机制

只读型事务不使用锁，因此它自然不会用到2PL，那么也就不需要2PC，**故就不需要使用事务管理器管理。因此这就可以避免跨数据中心读取数据，即避免将读请求发送给跨数据中心的Paxos组的leader来处理这个事务。**

读写型事务因为要确保数据的版本最新，因此任何的读请求都要发送给分片所在的Paxos组的leader，若运气好leader就在本地，那会很快，若运气不好leader不在当地数据中心，那么就要跨数据中心进行读数据，这意味着更长的时延。

因为只读型事务没有使用锁，这不仅可以让只读型事务速度更快，也可以避免降低读写型事务的执行速度，因为他们不需要等待由只读型事务持有的锁。这一点很重要，下面同样会进行详细说明。

3.3 两个正确性约束

只读事务做的事情并不多，不像我们会要求读写型事务的执行要保证严格有序。考虑到系统中大部分情况下使只读型事务与读写型事务并存，因此我们需要在保证正确性的情况下去提升效率。为了做到上面的这些，设计者在Spanner的只读型事务中引入了两个正确性约束。

3.3.1 constraint1-serializable

他们想让Spanner中的所有事务的执行依然是有序的。

分布式数据库会同时并发或并行（需求的数据不在一个分片中的多个事务可以同时互不干扰的执行）执行很多事务，这些事务的结果既要返回给client，也得把修改落地到数据库。这里的serializabnle约束意味着，这些并发（并行）执行的事务生成的结果必须和连续依次的执行这些事务生成的结果是一致的。

对于只读型事务来说，这意味着，一个只读事务的所有读操作可以看到在它执行之前的那个事务中的所有写操作所执行的结果，相对的，它必然无法看到任何在它之后所执行事务中的任何写操作所执行的结果。So，我们需要通过一种方法来将一个夹在两个读写事务之间的只读事务的所有读操作都放在这两个读写事务中间。

下面会具体说明如何实现这样的机制。

3.3.2 constraint2-External Consistency

外部一致性（External Consistency）的这个说法是在Spanner的论文中第一次被提出。外部一致性是在线性一致性的基础上，增加的一些额外的约束，在文末会进行具体的说明二者的不同。

具体来说，就是当前执行的事务要能看到最近最新提交的写操作。对于只读事务而言，只读事务应该是只能看到最新提交的数据。如果在一个已完成的事务中有已经提交的写操作存在，那么这个事务的完全提交应该出现在只读事务开始执行之前。

通俗来说，就是在单机数据库中，在Serializable的隔离级别下事务运行的所有规则。

3.3 只读事务问题阐述

我们设执行T3的机器很慢，他在读取完X值后过了很久后才开始读Y值，所以这造成了如下的错误场景：T3在T1执行完之后、T2开始执行之前读到了X值；但是在T2执行完之后读到了T2写入的值，这种结果明显不符合我们对serializable（在Spanner中叫外部一致性）的定义。因为T3读到的X值与Y值来自不同的事务，并且不符合任意时间点的最新的情况：

合理的情况是，T3的所有读操作在T1提交后、T2开始前之间全部执行完毕。T3的所有读操作在T2结束之后再开始执行。即分别对应着读到的数据全部是T1、读到的数据全部是T2的两种正确情况。

为确保每次读取都是上述的正确情况，Spanner采用了较为复杂的机制去实现外部一致性。下面会对采用的思路机制进行逐个分析说明。

3.4 机制1：Snapshot Isolation（快照隔离）

spanner中引入了TrueTimeAPI，在每个机器上都会有一个同步时钟，并且他们的时间在一定的误差限界内都可以认为是完全同步并相同的。我们给每个事务都分配了一个时间，即一个特定的时间戳，这是从上面的同步时钟那里拿到的。

R/W型事务：在上图中，他的时间戳就是该事务的提交时间。COMMIT TIME。

RO事务：在上图中，他的时间戳就是事务的开始时间。BEGIN/START TIME。

我们为每个事务都分配一个时间戳，然后根据时间戳来对事务的执行顺序进行安排，只要事务能严格的按照这些时间戳来执行，那么事务就可以得到正确的执行结果。

目标：我们需要一种实现方式，即遵守时间戳的顺序来执行事务。

这里要强调的一点是，当每个replica保存数据时，它实际上保存了该数据的多个版本。即若我们对某条数据库记录进行多次update，那么它会在每次写入每条记录时，保存在该时间戳下该记录的单独副本。

这就是为什么Spanner是一个多版本数据库的原因，这也是在开始就强调的内容。

因此基本策略是：当只读事务执行读操作时，因为只读事务在事务START时给自己分配了一个时间戳，故在只读事务发送读请求时，他会让读请求携带其所属事务的时间戳。无论是哪台服务器上保存了该事务读操作所涉及的副本，他都会去这个Multi-Version数据库中查找他所需要的那条记录。

在刚开始也强调过，Spanner相对于Bigtable的一个大的优势点是Spanner本身提供了对事务的支持，支持SQL queries，并且提供了更强大的多版本控制的能力。Spanner支持Snapshot Isolation，但是bigtable不支持。

服务器总是会显示出自己当前的最新时间戳，但是这个时间戳一定是小于等于读请求所携带的时间戳。这意味着，只读事务会根据自己被分配的时间戳（即事务开始、发起的时间），来读取相对自己而言，时间戳最新的那个数据。

即这个”最新”是相对于当前读请求携带的时间戳而言的，不能大于当前读请求携带的时间戳，这就是所谓的快照隔离。选择性的给当前只读事务展示数据的版本。

此外，我们必须意识到，Spanner使用这种snapshot isolation的思路来解决只读事务存在的问题。但是必须明确一点，Spanner在读写型事务方面，依然用的是两阶段锁和两阶段提交来解决问题。对于只读事务来说，他会去访问数据库中该数据对象的多个版本，并去获取时间戳**最高**的那个版本，但是这个**最高**是相对于当前事务携带的时间戳最高的。可见数据TS <= 只读事务携带的TS。即只读事务会根据自己发起时获取的时间戳来读取数据库中时间戳相对最新的那个数据，他可以看到之前所有更老的版本，但比自己新的版本它是看不到的。

但是有一种情况需要处理，离我们最近的replica中并没有我们应该获取到的相对最新数据，因为是Paxos组中的少数派。比如RO事务的TO是15，此时leader中最近的几个版本有8,9,10,13,14,16,因此RO正常来说应该读到版本为14的数据。但是RO事务所读取的本地replica中，由于他是少数派，所以可能只有8,9,10这三个版本，故若执行本地读取的话只能读到10，这样的结果不符合外部一致性的要求，因此也不是该只读事务应该读到的数据，所以我们需要做一些处理来应付这些情况。

Spanner采用了一种叫SafeTime的技术来解决这个问题，下面会进行详细的说明。

3.4 SnapShot Isolation例子

T1与T2是R/W型事务，T3是RO型事务。由上图不难得知，T1在T3开始前执行完毕，T3在T2开始前开始执行，T3与T2是并发执行的，他们的执行时间有重叠。

根据外部一致性定义，三个事务并发执行产生的最终结果应该和顺序执行：T1,T3,T2的结果是相同的，因此，虽然T3的第二个READY操作实际上在T2完成后才开始，但是根据Snapshot Isolation的实现，T3只能看到在自己之前的所有更改，而看不到自己后面的更改。因此T3只能看到T1时刻的更改，因此读到的是T1事务做的更改。

在RO事务选择的Replica中，我们假设该Replica是Paxos组中的多数派。少数派的情况会有专门的处理机制。

此外，Spanner对数据记录的版本有专门的垃圾回收机制。如果不进行回收，磁盘和内存是有可能被占满的，论文中没有说具体的机制是什么，但是他们支持读取相对于现存的时间戳最早的事务而言更早的时间戳的数据。

3.4.1 问题1：Replica为少数派

我们本地读取的目标Replica为Paxos组中的多数派时，是工作正常的，但是当该Replica是少数派时，若不做任何处理，该RO事务读取到的结果就会是过时的数据。比如RO事务的TO是15，此时leader中最近的几个版本有8,9,10,13,14,16,因此RO正常来说应该读到版本为14的数据。但是RO事务所读取的replica他是少数派，所以可能只有8,9,10这三个版本，故若执行本地读取的话只能读到10，这样的结果不符合外部一致性的要求，因此也不是该只读事务应该读到的数据，所以我们需要做一些处理来应付这些情况。

Spanner使用了T~saft~ （安全时间）的机制来解决这个问题。每个replica会去记录它从它的Paxos leader处收到的日志记录。论文中说，leader会严格按照时间戳增加的顺序来发送日志记录，replica会根据他从leader处拿到的最后一个日志记录进行更新。

比如说，如果我们要去读取时间戳15对应的值，但replica只从leader处拿到了时间戳13对应的日志条目，即该replica是paxos组中的少数派，Spanner就会让这个replica推迟给我们返回数据，直到该replica从leader处拿到了时间戳15对应的log（或是拿到的log时间戳>=15时），才可以对我们进行相应。

在论文中的4.1.3节是这么描述的：每个副本都跟踪一个称为安全时间t~safe~的值，该值是副本状态最新的时间戳。如果一个RO型事务携带的时间戳t <= t~safe~，那么该副本可以满足这个读请求，否则该副本就会推迟答复，直到t~safe~被推进到符合要求的值才会答复该事务。

这种机制就确保了，对于一个给定时间点的请求而言，直到该replica从leader处得到了该时间点前所发生的一切事情，它才会对这个只读事务进行响应。呼应了论文中阐述的这个机制。但是可能会造成一定的延迟。

4. 时钟同步问题

承接上面讨论的Snapshot Isolation读，在因为赋予时间戳的过程中要用到时钟，在分布式的场景下不同服务器的时钟同步就显得尤为重要。我们要讨论的主题是时间同步，因为我们要确保不同服务器上的时钟在同一时间读取到的是同一个值。

时间是由政府实验室的机构规定的，传播到服务器上需要花费一定的时间，因为延迟时间的不同，这些服务器会在不同的时间收到这些时间，因此可能会造成相同时间戳在不同的服务器上的具体对应的时间不同步。

4.1 对RO型事务的影响

如果快照隔离的时间不同步：

对于RW型事务而言，这没什么，因为RW型事务使用了锁和两阶段提交，他们实际上并没有使用SI机制，因此他们不在意时间不同步这种问题。因为基于2PL机制，可以确保RW型事务依然是有序执行的。

所以我们的重点是RO型事务碰到这种情况后会发生什么，该如何解决RO型事务遇到的问题？下图是教授针对只读事务携带时间戳过大/过小时会发生的情况的说明：

当RO型事务携带的时间戳过大时。这意味着：当有人把这个读请求发送给了某个replica，replica会说该读请求携带的时间戳远大于replica目前从Paxos leader处拿到的最后一条log对应的时间戳，因此该读请求需要等待，要等到replica收到的log的TS追上了该读请求携带的时间戳时，它才能响应该读请求。

因此，时间戳过大时，最后得到的结果是正确的，但是要等待很久，可能会触发事务超时机制。

当RO型事务携带的时间戳过小时。这可能是时钟本身的问题，如设置有问题，或者时钟原本设置是正确的，但是时钟走的太慢了，这会让一个时间戳实际对应的的时间远远的小于它应该对应的时间。那么这里就会演变为一个正确性问题，一个错误的时间戳会让replica返回给我们一个更早的写操作，这会使我们丢失最近已经落地的写操作，正确的情况是我们应该获取到一个更新的数据，故违反了外部一致性。

4.2 时钟同步问题溯源

如上所所述，时间是政府实验室的高精度时钟提供的时间集合的中间值。Spanner通过各种协议进行的广播来收到这些时间，如雷达广播协议，GPS为Spanner做了这些，GPS把从政府实验室收到的当前时间通过GPS卫星发送给Google机房中的GPS接收器。当然采用别的广播协议也可以。

如上图所示，政府实验室定义的世界时间是UTC，我们从某些实验室收到UTC时间，通过雷达或网络将时间广播给Spanner。传播中的延迟不可忽视，因此为了让收到的时间保持最新，要修正政府实验室与GPS卫星间的传播延迟和GPS卫星与我们当前所在地的传播延迟。

在Spanner系统中，每个DC（Data Center）里都有一个GPS接收器，它与Paper中提到的Time Master（时间服务器）进行了连接，为了实现容错，每个DC可能会有多个time master服务器。此外，要明确的一点是，每个DC中有数百台运行着Spanner的服务器，有的是Spanner Server，有的是Spanner Client，因此Spanner客户端并不是在外部的。

每台服务器会定期向本地的time master请求时间，通常会向多个time master发送请求，以防止其中一个time master崩溃。在请求时间这一过程中也存在着误差：当某服务器请求时间，该请求到了time master上，time master响应了该请求，并在那一刻给了他那一刻的时间，但是可能该服务器收到回复（reply）的过程中有延迟。

即time master的响应（response）是即时的，但是服务器收到time master的回复（Reply）这一段时间内有延迟。这个延迟也许是time master很忙，回的很慢，也许是中间要经历一定的传输时间。可能这会造成1s的传输时延，比如说我们收到的时间是12:00:00，但是我们存在最多1s的时延，因此我们知道真正的时间是在12:00:00-12:00:01之间的。所以时间上的误差是始终存在的，我们无法忽略这些误差。

4.3 Spanner中的时钟误差来源

除了上面提到的一些误差，Spanner系统中也有一些特定的误差是无法避免的。

在Spanner中，时间上的误差主要取决于安全等待的持续时间以及提交等待的暂停时间。

另一种误差是，每台服务器每隔一定时间会向time master请求当前时间，在服务器发送请求并等待time master的回复这段时间里，每台服务器会运行自己的本地时钟，本地时钟是从time master已经获取到的最后一次当前时间处开始走的。这些本地时钟很糟糕，他们会随着不断地运行而产生的越来越大的误差。在这里，他们会随着不停地运行而产生的毫秒级的偏移。

因此系统必须将本地时钟运行时产生的这种不确定的时间偏移量添加到时间的不确定性中去。Spanner为了捕获这种不确定性，并解决它所带来的问题，Spanner采用了TrueTimeAPI的方案。

5. TrueTimeAPI

论文中有一节专门讲述TrueTimeAPI，这是它提供的API调用接口。

当询问时间时，调用的是TT.now()，我们实际拿到的是一个区间，称之为TTinterval：[earliest，latest]。程序查询时间时获得的是一个区间，而不是一个准确的值。这意味着，事务知道当前时间是位于这个TTinterval范围内的某一个时间点，该API能保证正确的时间严格在TTinterval这个范围内。但是具体在哪个位置不得而知。

Spanner是如何使用TTinterval消除这种时间上的误差并确保时间正确呢？只读事务要遵守外部一致性，因此这确保了只读事务能看到在自己之前已经完成的事务中的写操作所做的所有修改。

论文中谈论了两条规则，这两条规则可以确保事务之间严格遵守外部一致性。分别是start rule和commit wait两条规则，在论文中有对这部分的详细说明，同样这二者也是误差的主要来源。

5.1 start rule

Start Rule会告诉我们事务选择的时间戳是什么。当事务向time master请求当前时间，time master返回给该事务的是一个TTinterval，事务的TS=TT.now().latest。即时间戳的具体时间总是最右的区间。TrueTimeAPI可以保证这个latest时间是一个还未发生的时间，因为真实时间是位于这个区间之中的。

RO型事务是在开始执行的时候被分配时间戳，读写型事务是开始提交的时候被分配时间戳。Start Rule说明了Spanner分配时间戳的方式。

5.2 commit wait

提交规则只适用于读写型事务。事务协调器会先收集参与者的prepared消息，当所有的参与者都回复该消息后，协调器确定可以提交该事务。那么协调器就会为该事务分配一个时间戳。为了做到所有参与者提交时间是一致的，对提交做了如下的规定。

在实际提交RW型事务（执行所有操作并释放锁）之前，参与者们需要等待一段时间。因为请求到的时间是一个TTinterval，对于所有参与者得到的提交时间戳而言，我们只能确定该时间最晚不会超过TT.now().latest，但是具体的时间可能各不相同。为了保证分布式环境下各个数据分片master的时间协调性，我们让所有的服务器都统一等到TT.now().latest这个时间点再提交，这样就可以做到所有服务器的实际提交时间相同。

此外，若该RW型事务后紧跟着一个RO型事务，我们要确保T~RW~ .now().earliest < T~RO~ .now().latest，即两个事务的时间戳时间是没有相交的。该RW型事务的时间戳是绝对小于下一个RO型事务的时间戳的earliest time。

5.3 example

教授用这个例子向我们说明了Spanner的事务如何使用这两条规则来做到强制外部一致性。如上图所示，T0与T1是RW型事务，T2是RO型事务；我们假设T2是在T1完成提交之后才开始执行的，因此T2读到的值应该是2才满足外部一致性的要求。

首先，他们是如何确定自己的时间戳的。T0经过一系列过程，确定自己的时间戳为1（latest time）。接下来T1开始执行，他确定了自己可以提交，于是开始选择时间戳，它通过TrueTimeAPI拿到了一个TTinterval，这里我们设这个区间为[1，10]，根据规则，T1必须选择latest time 10作为时间戳，因此T1的提交时间就是10。但是我们不能马上提交，因为当前的真实时间并不是10，当前的真实时间位于那个区间之中。

Commit wait规则表示，我们必须等到这个时间点才可以进行提交。这里的方法是，T1会不停地去询问时间，直到它拿到的TTinterval中不包括10为止。比如说，在某一刻，T1拿到了一个时间段，区间为[11，20]，这就表示着T1知道时间戳10已经过时了，自己已经经历过这个时间点了，所以他会去提交这个事务。

在T1确定时间戳后（时间戳为10），与确定自己可以提交的时间点（拿到[11，20]这个区间时）时，中间经历的这一段时间我们称为commit wait时间。这就是提交等待的来源。

在T1提交之后，T2想去读取X，它也会给自己选择一个时间戳。上面已经假设T2是在T1结束后开始执行的，事务T2同样也会得到一个TTinterval，该interval的earliest time至少是10，这一点不难理解。但是在latest time最小是11还是12这一点有一些疑惑。教授的意思是，T2是在T1结束后开始执行的，这就意味着11必然小于该latest time，因此T2会选择12作为latest time。

在论文中的描述是：根据提交等待规则，协调者领导者等待直到TT.after(s)为真，其中s是基于TT.now().latest选择的提交时间戳。这确保了在应用提交记录之前所选择的时间戳已经过去。

当上述表达式为真时，即对应本例中得到区间[11，20]的那一刻，T2选择12作为latest time而不是11，这里我猜是为了确保该RO型事务的读取时间戳与该读写型事务的提交等待时间完全不相交。实际上，我们不清楚T2的earliest time到底是多少，但是我们必须确保T2的latest time是在T1的提交时间后的，并确保不产生任何的相交。

5.4 summary

在Spanner中，我们通过使用TimeStamp和安全等待时间（commit wait）来确保只读事务只能看到在自己开始前提交的RW型事务的更改，只读事务开始后的RW型事务做的更改对该只读事务是不可见的。

**快照隔离这项技术本身是无法保证外部一致性的，即使在事务执行中做到了线性一致性，我们也无法确保分配给这些事务的时间戳会遵守外部一致性。**因此，为了使用SI，Spanner也得对时间戳进行同步。

同步时间戳+commit wait规则，这二者使spanner能够保证外部一致性和线性一致性。

通常情况下分布式系统中是不提供事务的，因为事务很慢。但是Spanner设法让RO型事务的执行速度变得非常快，RO型事务可以做local read，而不是每次从paxos leader中读取。但是RW型事务使用的依然是2PL与2PC，因为安全等待时间与commit wait机制的原因，很多时候Spanner还是会遇到阻塞，但是只要时间足够准确，那么提交等待时间就会变得很小。

Spanner中我们最需要关注的是：Snapshot Isolation与Timestamp。

5.5 Why SI need additional mechanism to do External consistency?

时间戳在确保系统序列化方面起着重要作用，它们能够确保多个并发事务的执行顺序。通过为每个事务分配唯一的时间戳，系统可以确定它们发生的相对顺序。这使得系统能够强制执行**可串行化**，确保并发事务看起来像是依次执行的。因此，时间戳有助于维护系统的内部一致性。

然而，需要注意的是，单独的时间戳并不能保证外部一致性。外部一致性是指在分布式系统的所有节点或副本上一致地反映事务的影响的特性。尽管时间戳为事务排序提供了机制，但它们并不解决分布式系统中复制和同步所带来的挑战。

在分布式系统中，可能会出现传播更新到所有副本时的延迟、故障或不一致性。仅凭时间戳无法解决这些问题。即使事务根据时间戳正确排序，事务的影响可能不会立即在所有副本上可见或同步。要实现外部一致性，需要额外的机制，如分布式一致性协议或冲突解决策略，以确保更新正确传播和应用于分布式系统中的各个部分。

啊，时间戳，系统序列化的小守护者！它们在保持事务井井有条方面表现出色。每个事务都有自己特殊的时间戳，使系统能够确定它们发生的顺序。就像在夜店里有保安一样，让每个人都有序排队，避免混乱。因此，时间戳对于维护系统的内部一致性非常有用。

但是，等一下，时间戳并不能像魔术棒一样保证外部一致性。那是完全不同的问题。外部一致性是确保事务的影响在分布式系统的所有节点或副本中以一致的方式可见的特性。时间戳可以给你一种顺序的感觉，但它们不能解决分布式环境中复制和同步所带来的问题。

在分布式系统的狂野世界中，有很多事情可能出错。延迟、故障和不一致性可能会使所有副本难以保持一致。时间戳虽好，但它们不能单独应对这些挑战。它们需要一些支持，比如分布式一致性协议和冲突解决策略，以确保更新被正确传播，让分布式节点像完美协调的舞蹈一样同步。因此，请记住，时间戳对于序列化很有用，但外部一致性需要一点额外的努力！

back.