分布式之Spanner

发表于 分类于 ， 阅读次数： 本文字数： 7k

0. 前言

MIT6.824 LEC13 Spanner

Spanner由谷歌2012年的论文《Spanner: Google’s Globally-Distributed Database》提出，是谷歌的一个全球级别的分布式数据库。它管理着全球成百上千个数据中心，数百万个服务器，将数万亿数据分片存储到这些服务器上。同时，它支持以下特性：

  1. 支持高可用（数据的备份和恢复）。数据可以有多个备份副本，并且可以灵活、细粒度地配置：副本数量、副本所在的数据中心等。副本甚至可以跨国家存储，即使面临大范围自然灾害，数据依旧可用。

  2. 同时，Spanner保证这些副本的外部一致性（谷歌创造出来的一种一致性）。

  3. 支持广域的分布式事务，对于涉及不同数据中心的事务，也能保证ACID特性。

Spanner如何保证这些特性呢？具体内容请看下文。

1. 架构

1

Spanner的架构如上图所示，Spanner管理着多个Zone，每个Zone管理着成百上千个spanserver，一个数据中心可能有一个或多个Zone。为了更好地理解，我们做如下假设。

假设，Spanner在北京、上海、杭州各有一个数据中心（一个数据中心只有一个Zone），每个数据中心都有数台服务器(spanserver)。某个应用将数据通过Spanner进行分片存储：在北京的数据中心有2台服务器，1台存储着a-m的数据，1台存储着n-z的数据。不同分片服务器处理不同分片的请求，提高系统并行吞吐量。同时，在上海的数据中心，也有1台存储着a-m数据的副本，1台存储着n-z数据的副本；杭州同理。这些不同数据中心的副本，相互保持一致。如此，每个数据中心的副本都可以快速地为当地的用户进行服务，且彼此之间保证高可用/容错。

1

Spanner通过Paxos算法保证不同数据中心副本之间的一致性。因此，不同数据中心存放相同数据副本的服务器可看作一个Paxos组。每个Paxos组中，会有一个leader（比如上图中的粉红色Server），它负责将状态变更同步到其它副本，同时它也负责事务操作。不同Paxos组的leader之间也会相互合作，完成跨数据分片（跨Paxos组）的分布式事务，其中一个leader会被选为事务协调者(coordinator leader)。

1

面临的挑战：

  1. 将副本分散在相隔较远的数据中心，其好处是能为当地用户快速响应，同时能更好地抵御突发情况（比如某个数据中心突然断电）。但坏处在于：leader与follower的通信成本增高；另外，Paxos只需要状态变更同步到超半数副本即可，因此较远的数据中心的副本可能并不是最新的。

  2. 当事务只对一个分片内的数据做读写时，比如修改数据b的值，它只需要请求分片(a-m)所在Paxos组的leader即可。但，如果事务需要跨分片操作时，比如将b的值赋给y，那事情将变得复杂（分布式事务）。

2. 事务

接下来，将主要介绍Spanner中事务的实现。

Spanner将事务分为以下4种，每种都采用不同的处理方式。

1

2.1. 读写事务

假设有如下读写事务：

1
2
3
4
BEGIN
  x = x + 1
  y = y - 1
END

如果x和y在同一分片内，那事情会相对简单一些。只需要执行一个本地单机事务，而后通过Paxos算法将状态变更同步到各个副本服务器即可。

在此，我们考虑更复杂的情况，即分布式事务，x和y不在同一分片。每个分片都有1个Paxos组，组内有3个副本，各自分布在3个数据中心，粉红色的为组内leader，如下：

1

从之前分布式事务的博客中可知，为了保证分布式事务的原子性，最通用的方法是两阶段提交2PC；为了保证隔离性，最通用的方法是两段锁2PL。Spanner中基本也是如此。

由于Spanner中每个分片都有一个对应的Paxos组，因此在分布式事务中，一个Paxos组充当一个协调者或参与者。实际上，最终由各个Paxos组中的leader负责处理客户端的请求，以及分布式事务的协调。

针对上述分布式事务，具体执行步骤如下：

  1. 客户端为事务指定一个事务ID，用于标识这个事务。

  2. 客户端向数据x所在分片对应的Paxos组1请求读取x，Paxos组1的leader会返回x的值，并对x加读锁。同样，它再向Paxos组2请求读取数据y。注：分布式事务中的读操作是不需要请求协调者的，客户端完成所有读操作，并缓存所有写操作后，它才会将所有写操作交由协调者进行两阶段提交。

  3. 客户端在本地进行计算，得出x和y的最终结果。假设x和y的初始值都是10，那么最终x=11，y=9。

  4. 2PC准备阶段：

    1. 客户端请求事务的协调者，获取协调者的ID，将所有要进行的写操作(x=11, y=9)一次性告知协调者。假设当前事务的协调者是Paxos组1，那么这次请求将会发给Paxos组1的leader。

    2. 客户端负责将各个写操作发送给对应分片的Paxos组（包括协调者和参与者），同时还会携带协调者ID。比如，客户端会将写操作y=9发送给Paxos组2的leader。注：由客户端发送各个写操作，可减少协调者压力。

    3. 各个Paxos组的leader收到写请求后：

      1. 对数据加写锁。

      2. 发送Prepare消息给各个follower，并记录在Paxos日志中。

      3. 当它收到大多数follower的成功响应后（日志已提交），它会告诉协调者，它已经准备好了。

  5. 2PC提交阶段：

    1. 当协调者收到全部参与者对于Prepare阶段的Yes响应后，它会决定Commit。当部分参与者响应No，或者超时未响应，它就会决定Abort。假设，它决定Commit：

      1. 协调者leader会向follower发送Commit消息，并记录到Paxos日志中（保证容错，即使leader崩溃，新的leader也不会忘记当初的决定，继续该事务）。

      2. 当大多数follower成功响应（Paxos日志提交成功）后，协调者才会告诉其它参与者，可以提交该事务了。

    2. 各个参与者（Paxos组的leader）收到Commit消息后：

      1. 将Commit消息记录到Paxos日志中（发送给follower），并保证已提交。

      2. 当Commit消息已提交后，参与者才会执行对应写操作（leader将状态变更日志同步给follower），并释放锁。

相比于传统的分布式事务，Spanner分布式事务中每一个分片是一个Paxos组。因此，在2PC过程中，参与者或协调者的每一次操作都需要提交到Paxos日志。

由于Paxos算法的高容错特性，且各个副本较为分散，Spanner中分布式事务具有以下优点：

  1. 参与者或协调者的Paxos组中，只要有超半数的服务器存活，参与者或协调者就能正常工作。因为就算leader崩溃后，follower能快速成为新leader，继续进行后续操作。

  2. 能有效避免在Commit阶段，协调者崩溃或网络阻塞后，参与者一直等待的情况。因为协调者leader崩溃或网络阻塞后，新leader能快速替代它。

当然它也有缺点：由于要提交Paxos日志，而副本又分散在各个数据中心，因此通信成本非常高。在Spanner论文中有关于这方面的测试，每个Paxos组中的副本都分布在跨城市的数据中心，一次跨分片的读写事务耗时为100ms。不过，通过数据分片，可以并行处理许多不相交的分布式读写事务。另外，数据中心相隔较近的话（这种布局更为常见，许多应用并不需要把数据分散到全球），性能也会大幅提高。

2.2. 只读事务

只读事务是指一个事务中只存在读操作，可能是读一个分片内的数据，也可能是读多个分片的数据。在现实生活中，只读事务发生的次数要远远大于读写事务，因此它的性能要求远高于读写事务。

为了提高性能，Spanner对只读事务有如下设计：

  1. 只读事务可以从本地数据中心的副本读取数据，提高读取速度。但问题在于，本地数据中心的副本可能不是最新的。

  2. 不需要加锁，更不需要两阶段提交，避免了跨数据中心的通信。

但是，为了保证正确性，只读事务需要满足以下特性（约束）：

  1. 事务的串行化（隔离性），所有事务就像串行执行一样。虽然只读事务可以跟读写事务并行执行（因为只读事务不加锁），但只读事务只能看到上一个已提交的读写事务执行后的结果，它不能看到处于未提交事务中间状态的数据。

  2. 副本的外部一致性（线性一致性）。当一个读写事务提交后，下一个事务应该看到所有最新的修改。在单机数据库中，一个事务提交，下一个事务一定能看到最新的修改。但在多副本的情况，并不是每一个副本的数据都是最新的，因为Paxos算法只需要超半数的副本同步成功即可。

快照隔离——保证事务隔离性

由于只读事务不加锁，在并行的场景，就会出现无法串行化情况。示例如下，Wx表示写x，Rx表示读x，C表示事务提交。

1
2
3
T1:  Wx=9 Wy=11 C
T2:                        Wx=8 Wy=12 C
T3:                  Rx                   Ry

假设x是用户的一个银行账户余额为10，y是另一个银行账户余额也为10，初始总余额是20。有三个事务，T1和T2都是读写事务，T3是只读事务。由于没加锁，T3执行过程中，Rx读取到的是T1事务执行后x的值9，而Ry读取到的是T2事务执行后y的值12。此时，用户会发现他的两个银行账户的总余额为21，这肯定是不正确的。那为什么呢？因为对这三个事务，我们无法得到一个可串行化的顺序，既不是T1 T2 T3，也不是T1 T3 T2。

为了解决上述问题，有一种方法称为 快照隔离(Snapshot Isolation, SI) ，这称为 多版本并发控制(MVCC) 。

首先，我们需要一种机制对事务进行排序：

  1. 假设参与事务的每台机器上都有一个时钟，且相互同步。

  2. 为每一个事务都分配一个特定的时间（时间戳）。假设，读写事务的时间戳是它提交的时间，只读事务的时间戳就是它开始的时间。

  3. 根据事务的时间戳对事务进行排序。对于上述示例，事务排序的结果为：T1 T3 T2。按照该顺序执行，T3的Rx将读到10，Ry将读到10。但由于T3执行过程中，T2执行并提交了，如何保证T3不受T2影响才是问题的关键。

然后，规定每条数据记录都有多个版本，每个版本通过时间戳标识。当对某条数据记录写入时，写入结果会另存为一个单独的记录副本（快照），副本的时间戳即为事务的时间戳。当读取某条数据记录时，它会读取小于当前事务时间戳且时间戳最新的记录副本。因此，只读事务只会看到，从它开始的那一刻之前，上一个已提交读写事务执行后的最新的值。而过程中即便有其它读写事务提交，它也不会看到修改的值。

回到上述示例，假设T1的时间戳为10（提交时间），T2的时间戳为20（提交时间），T3的时间戳为15（开始时间）：

1
2
3
T1@10:  Wx=9 Wy=11 C
T2@20:                        Wx=8 Wy=12 C
T3@15:                  Rx                   Ry

每个读写事务执行完，旧数据并不会被覆盖，而是会为记录创建一个新的副本：

1
2
3
4
x@0 = 10, y@0 = 10   // 初始时间戳为0，记录的初始状态
x@10 = 9, y@10 = 11  // T1执行完
x@20 = 8, y@20 = 12  // T2执行完

当只读事务T3开始执行时，时间戳为15。它读取x时，系统返回时间戳小于15且最新的记录副本，也就是x@10 = 9。当它读取y时，即便T2已提交，它也看不到T2写入的y的新值，系统只会返回y@10 = 11。如此，用户读取到的值，才是正确的。这三个事务的执行，也符合串行化的顺序T1 T3 T2。

快照隔离是一种空间换时间的方法，它会浪费一定的存储空间，但系统也会定期地清理太过时的记录副本。

safe time——保证分布式一致性

由于只读事务被允许从本地数据中心读取数据，而本地数据中心的副本可能并不是最新的（Paxos算法）。比如，执行T3的Rx时，本地数据中心的副本还未同步T1的更改，x值依旧为最初状态x@0 = 10。

为了解决这个问题，Spanner提出了safe time。每个Paxos组中，leader在同步状态变更日志给follower时，会携带时间戳（递增的）。follower会将最新收到的日志时间戳作为safe time，能够保证的是，follower肯定知晓safe time之前的所有更改。因此，当只读事务的时间戳小于等于safe time时，follower肯定能返回该事务开始前最新的数据状态。反之，follower则会等待新日志。

考虑上述示例，当客户端向本地数据中心的follower副本发起事务T3（时间戳为15）时，follower的safe time为0，x的状态为x@0 = 10，它会等待leader的新日志。直到新日志的时间戳大于等于15，follower才会将x的值返回给客户端。

关于safe time的问题：

  1. 日志的时间戳与事务时间戳相等吗？应该是不相等的，比如事务T1的提交时间戳为10，但leader发送相关状态变更日志（比如W(x@10)=9）的时间戳，可能稍微大于T1的时间戳。另外，论文中提到：$t_{safe} = min(t^{Paxos}_{safe}, t^{Tx}_{safe})$，真正safe time是Paxos safe time和事务safe time的最小值。

  2. 如果一直没有状态更新，leader一直没发送新的日志，难道就一直阻塞不响应只读事务吗？

2.3. 快照读事务

只读事务是读取事务开始时间之前，最新的快照。而快照读事务，就是读取指定的快照。

3. 时钟同步

在设计保证只读事务的正确性时，有一个非常关键的前提——每台服务器上的时钟必须同步。

时钟不同步的影响

我们先考虑，如果时钟不同步，这会引发什么问题？对于读写事务而言，由于使用了锁，它们不会受到影响。关键是对只读事务的影响：

  • 如果收到只读事务请求的服务器分配给它的时间戳，比正常时间晚。那么只读事务将会比正常的safe time大，它将等待更长的时间。比如，此刻正常时间是15，但副本服务器的时间是20，它分配给此刻只读事务的时间戳将为20，而safe time是16，只读事务只能等待safe time大于等于20。这种情况下，只读事务的延迟会增加，但不会出现错误。

  • 如果服务器分配给只读事务的时间戳，比正常时间早。那么只读事务将无法保证分布式一致性，它将读到过期版本的数据。比如，此刻正常时间是15，但服务器的时间是10，它分配给此刻只读事务的时间`戳将为10。如果数据有@10和@15两个版本，它将读取到@10版本的数据，而正常应该读取@15版本的数据。

而实际上，各个服务器的时钟并不同步，每台服务器的时钟都会有偏差，为什么呢？因为计算机时钟会出现偏移，每台计算机的时钟并非按照相同的速率前进。

一种保证时钟同步的方法是：大家都与一个时钟精准的服务器同步时钟。但这种方法存在通信延迟，特别是这个服务器相隔较远时。而且，这个服务器的负载将会很高。

Spanner的黑科技——TrueTime

为了解决时钟同步的问题，就不得不提Spanner的核心技术——TrueTime，下图是它的主要接口。

1

TT.now()会返回一个时间区间，并保证当前时间在这个区间内。区间的宽度，是通过测量网络延迟、时钟偏移、GPS误差等数据计算出来的。这个宽度通常是微秒级别，但有时也会是毫秒级别。

为了提供TrueTime API，Spanner在每个数据中心都会放置多个高精度的时间戳服务器。这些服务器采用GPS或者原子钟的方式保证时钟准确，通常会使用GPS的方式，GPS会接收政府实验室广播的高精度时间(UTC)，但GPS失效时，会使用原子钟的方式。并且，相互之间会进行时钟同步。数据中心内的其它服务器会时不时与这些时间戳服务器通信，来保证自己时钟的同步。

TrueTime如何保证事务顺序

为了保证外部一致性（副本间的线性一致性），就需要给所有事务排序：如果事务T2在事务T1提交后开始执行，那么T2的时间戳一定比T1的时间戳大。

为了实现这一点，Spanner制定了两条规则：

  1. Start。设置事务的时间戳S时，S = TT.now().latest。对于读写事务，它的时间戳是在协调者向参与者和客户端发送Commit请求后设置的。对于只读事务，它的时间戳是在事务开始时设置的。

  2. Commit wait。读写事务中，协调者发起Commit请求后，各个Paxos组（包括参与者和协调者）的leader，必须等到TT.after(S)为真，才将事务结果记录到Paxos日志中，并向follower同步。这样做的原因是TT.now()返回的是一个区间，那么S = TT.now().latest就可能比正常时间要大，比如：此时时间是10，而TT.now().latest可能是11，那就必须要等到11才能将事务结果写入各个副本。这就确保了客户端在时间戳S之前，不能看到任何事务提交的数据。

4. 总结

Spanner的出现对当时产生了非常大的影响，它的优势在于：作为一个全球性的分布式数据库，它不仅支持多副本+分布式事务，还提供了高性能的只读事务。

对于读写事务，Spanner采用了分布式事务常规的2PL+2PC，但引入Paxos实现了多副本，并通过Paxos避免了2PC中一直阻塞等待的情况。

对于只读事务，Spanner通过不加锁和从本地副本读取，将只读事务的性能提高了10倍。接着，它又通过快照隔离(MVCC)保证了事务隔离性，通过safe time保证了副本的一致性。而为了实现快照隔离和safe time，它又设计了特有的时间戳机制，保证了事务的全局排序和外部一致性。