EA Blog

前言

Spanner是一种由Google开发的分布式数据库管理系统。它被设计为可扩展、全球范围内可用的数据库解决方案。Spanner结合了传统的关系型数据库和非关系型数据库的特点，旨在提供一种水平可扩展的、具有强一致性和高可用性的数据存储解决方案。

Spanner的一个重要特点是其能够跨多个数据中心和地理位置进行全球级别的复制和数据同步。这使得Spanner成为一个理想的选择，用于支持需要高度可用性和低延迟访问的应用程序。它提供了强一致性的事务处理，并通过使用TrueTime API来确保全球范围内的数据一致性。

除此之外，Spanner还提供了一套丰富的工具和API，用于管理和操作数据库。开发人员可以使用标准的SQL语言进行数据查询和操作，同时利用Spanner的自动分片和负载平衡功能来实现高性能和可扩展性。

一些值得思考的错误

分布式事务的实现的最大难题是什么呢？没错，就是不同机器的时间不同步的问题，假设现在的真实时间是 9:59，那么机器A可能是9:58，机器B可能是10:00，这样的误差给分布式事务的实现带来了巨大的挑战性

假设现在，实际时间戳为10，我们有两台机器，机器A的时间戳是9，机器B的时间戳是11，两台机器上存储了相同的数据对象

而此时，向机器B提交一个写事务，写事务请求将数据对象A1从0改成2，由于B的时间戳是11，那么得到的写入时间戳是11，由于时间戳是需要全局同步的，所以A也会将写事务的操作应用到本地，所以A得到的对数据对象A1的写入时间戳同样是11。

那么在一秒后，也就是实际的时间戳为11，机器A的时间戳为10，机器B的时间戳为12的时候，我们再向A提交一个写入事务请求，将A1改成1，由于机器A的时间戳为10，那么得到的写入时间戳就是10，而上一次对A1的写入的时间戳却是11，所以机器A和B就会认为，这一次发生的写入事件是比较早的事件，因此不会将这一次写入事务提交。

这时候问题就已经出现了，在分布式机器的环境下，明明是在真实时间上更晚执行的事务，却由于各个机器之间的时间不同步的问题，变成了更早执行的事务，最终导致我们所需的结果不符合预期。

为了解决这个难题，google在Spanner的设计中引入了TrueTime API。

正如他们在论文所说的那样：

| our goal is to demonstrate the power of having such an API.

这是一个强大的API，也影响到了后来许多的分布式数据库的设计。

TrueTime API

我们直接进入重点，关于Spanner的TrueTime API的背后的底层机制，笔者在这里不再做详细的分析，其实现原理可以详细参考原文论文

TT.now() 无疑是最重要的API，其返回值为 TT.Interval:[earliest, lastest]

这个返回区间保证了一个最重要的性质：假如说当前的绝对时间戳是 t_{abs}(e_{now}) ，那么下列公式必然成立，即

earliest < t_{abs}(e_{now}) < lastest

也就是说，我们的绝对时间戳是一定位于此区间内的

那么，假如有5台机器，那么假如他们在同一时间调用 TT.now() ，所返回的结果都是相同的，也就意味着这个API对于所有的机器来说都是一致的（笔者此处无法确定其所返回的结果是否都为相同的区间值，但是参考后面的分布式事务的设计，笔者认为理应如此）

而 TT.after(t) 和 TT.before(t) 则是对 TT.now() 的封装，前者在绝对时间戳 t 一定已经过去时返回true，而后者在绝对时间戳一定还没有到达时返回true

Spanner 分布式事务的实现

时间戳分配

Spanner对事务提交提供了两个限制以确保外部一致性(External Consistency)

1.Start

在Spanner中的一次写事务中，coordinator leader(暂时可以理解为分配时间戳的leader)在事务提交时会将提交时间戳设置为 s_1 > TT.now().lastest

2.Commit Wait

在提交时，一个事务必须直到 TT.after(s_1) 返回true时才能确认提交

假设 e_{1}^{commit} 为事务1提交的事件， e_{2}^{start} 为事务2提交的事件, Spanner给出了如下的定理

t_{abs}(e_{1}^{commit}) < t_{abs}(e_{2}^{start}) \Rightarrow s_1 < s_2

这条定理说明，只要在绝对时间上，事务1的提交时间早于事务2的开始时间，那么事务1能够获得的时间戳必然小于事务2能够获得的时间戳

论文原文给出的证明如下：

笔者详细解释一下这个证明：

首先，由于 commit wait 机制，事务在 TT.after(s1) 返回true才能够确认提交，这就说明了提交时间戳是必然小于提交时的绝对时间戳的，因此 s1 < t_{abs}(e_1^{commit}) 成立

而由我们的假设得 t_{abs}(e_1^{commit} ) < t_{abs}(e_2^{start})

又因为，事务请求到达服务器的绝对时间戳我们称为 t_{abs}(e_2^{server}) ，事务必须要先开始，才能把请求上传到服务器，因此 t_{abs}(e_2^{start}) < t_{abs}(e_2^{server})

而由于 Start 机制，必然有 t_{abs}(e_2^{server}) < TT.now.lastest() < s2

因此 s1 < s2 成立

读写事务 (Read-Write Transaction)

Paxos集群领导者租约机制(Paxos Leader Leases)

Spanner的Paxos会给每个任期的leader一个租约(lease)，每个租约拥有时间间隔 lease\ interval:[Starting, s_{max}] ，假设leader能够使用的时间戳为s ，那么必然有 s\in [Starting, s_{max}]

详细的lease机制的解析已经超越了本篇解析的范畴，笔者在此处不再做深入解析，我们仅需知道Spanner Paxos提供了一个严格的保证：每一个 leader的的 lease interval不可能与其他leader的 lease interval相重叠，这就意味着每一个leader可分配出去的时间戳是不可能与其他leader相同的，这是保证时间戳分配的单调性的原因之一

读写流程

读写事务采用了两阶段提交(2 Phase Commit)和两阶段锁(2 Phase Lock)协议

每个Paxos Group都维护了一个 Lock Table，而Leader则会作为Transaction Manager来管理Lock Table，Lock Table记录了当前被上锁的key和负责上锁的事务。

一次读写事务的写入会首先将写入缓存在客户端，直到提交的时候才会对所有的服务端的机器可见，与此同时，读写事务的读操作会选择任意一个Paxos组，上读锁，然后执行读取。

在事务执行期间，客户端会不断地发报文以提醒服务端：该事务仍然是存活的，不要停止该事务的执行。（按原论文的意思，笔者推测，若遇到网络故障，服务端会主动地停止该事务的所有的操作，并执行回滚来撤销事务操作造成的影响。）

两阶段提交(2 Phase Commit : Abridge: 2PC)

等到读写事务的写入数据全部缓存到了客户端，以及读操作需要读取的数据全部传送到了本地以后，读写事务便开始执行写入提交流程。

第一阶段

首先，客户端会选出一个Paxos Group 作为Coordinator来统筹本次读写事务的提交流程，而其他的所有的Paxos Group则称为Participant。

数据上传到服务端后（论文此处并未提到上传的细节，笔者认为应该是将数据同时传到Coordinator和Participant，因为这样实际上并不会影响一致性），Participant会根据Lock Table上写锁，并将该数据应用到本地的Paxos Group，在成功将数据提交到本地的Paxos集群后，Participant会选择一个时间戳 s_{prepare} （笔者认为，这里在所有的Paricipants上应用该数据，就是我们需要的第一阶段的提交）。

所以我们选择的时间戳必须满足 s_{prepare}^{current} > s_{prepare}^{previous} 且 s_{prepare}^{current} > s_{commit}^{previous} ，这才能保证我们这次的提交是最新的。

这该如何理解呢，其实用我们上面提到过的外部一致性的观点是能够解释的，假如在绝对时间上，有一个事务A已经提交了，那么就意味着 t_{abs}(A_{commit}) < t_{abs}(Start_{Current}) < S_{prepare}^{current} ，又因为 S^A_{commit} < t_{abs}(A_{commit}) ，所以 s_{prepare}^{A} < s_{commit}^{A} < s^{current}_{prepare} ，这也就意味着，我们至少要保证当前的时间戳是最新的，才能够保证我们的总体提交的时间戳是单调递增的。

在一个Participant完成Prepare后，Participant会将为该事务选择的 s_{prepare} 返回给Coordinator。

第二阶段

在Pariticipant执行Prepare阶段时，Coordinator只会对相应的数据上写锁，而不会执行Prepare阶段。

Coordinator在收到所有当前事务的Participant回复的 s_{prepare} ，且在自己的Paxos集群也应用了事务提交的数据以后，会选择一个 s_{commit} 决定事务的最终提交的时间戳， s_{commit} 必须满足如下条件

1: s_{commit} 要大于所有收到的 s_{participant}

2: s_{commit} 必须满足Start机制（也就是必须比上传到服务器时选出的 TT.now().lastest 要大）

随后，Coordinator会将 s_{commit} 返回到各个Participants中，并执行Commit Wait机制，在执行等待期间，Participants同时在本地执行提交，也就是把 s_{commit} 应用到本地，然后所有的Participans会把获取的锁释放，并且全局机器上，对该事务应用的 s_{commit} 都是一致的

只读事务(Read-Only Transactions)

对于只读事务，Spanner提供了 快照读(Snapshot Reading) 机制，只读事务能够读取所有时间点的安全副本，只读事务开始执行的时候，Spanner会为该事务选择一个 s_{read} 时间戳，该时间戳用于保证读取的安全性（关于安全性我们在下文会分析），首先我们分析Spanner的leader该如何去分配 s_{read} 给只读事务

单机读取(Single Paxos-Groups Reading)

对于单机读取，由于该读取不涉及多个集群，Spanner是这样去选择的

s_{read} = LastTS()

其中 LastTS() 是该Paxos Group最新一次提交的写入时间戳，意味着最新的变更，这也就意味着这一次快照读能够读取到最新的数据，且不会读取到不安全的数据

之所以不选择 s_{read}=TT.now().lastest ，是因为这个阻塞时间可能会比较长，且当前读取不涉及多集群，所以可以直接读取到最新落盘的数据，这样的选择也可以在一定程度上提升只读事务的效率。

多端读取(Multiple Paxos-Groups Reading)

对于多集群的读取，Spanner会直接选择 TT.now.lastest() 作为 s_{read} ，在这里，用 Start 机制理解即可。

安全性分析

事务的读取是有时间戳的，而可被读取的副本同样是有时间戳的，Spanner定义了如下的规则：

只要一个副本的时间戳满足 t<t_{safe} ，即可被读事务执行读取，否则就不能被读取（也就是这部分数据对于读取事务来说是不可见的）

在这里，笔者要花费一定的篇幅来解释 t_{safe} 的定义

t_{safe} = min(t_{safe}^{Paxos}, t_{safe}^{TM})

1. t_{safe}^{Paxos} 的定义较为简单，它代表了在一个Paxos集群中最后的成功提交日志的时间戳，这个时间戳也代表了能够被安全读取的日志的范围

2. t_{safe}^{TM} 则较为复杂，它的定义是 t_{safe}^{TM}=min_{i}(s_{i,g}^{prepare}) - 1

这是什么意思呢？实际上， t_{safe}^{TM} 的取值是在该机器上未提交，但是已经Prepare的事务的值减去1的值，若当前机器上没有Prepare的事务，则当前事务的 t_{safe}^{TM}=\infty

那么，根据前面我们分析过的读写事务的流程，我们可以知道，Leader分配的 s_{prepare} 是单调递增的，所以这就可以保证，只要我们读取的副本的时间戳小于最小的 s_{prepare} ，那么这个数据就一定是已提交的，也就是可以被安全读取的数据

结语

Spanner的分布式事务的实现是相当复杂的，笔者在此也花费了巨大的篇幅来解释了TrueTime API与分布式事务的实现流程，可能存在一些理解上的错误问题，而由于近期时间比较紧，有些地方可能解释的不如人意，希望读者们若发现文章有错误，或者有什么疑惑，及时在评论区留言，谢谢！