Spanner事务漫谈

Spanner是谷歌开发的一款高可用、分布式、支持全球部署的数据库，它可以被看做是NewSQL的开山之作（虽然NewSQL这个词越来越被业界认识抵触了），在它之后，一大批分布式数据库（CockroachDB、TiDB、YugabyteDB......）如雨后春笋般崛起。本文主要讨论Spanner的事务实现。

一：整体架构

在介绍讨论事务实现之前，先简单介绍一下Spanner的架构作为铺垫。

如上图所示是一个Spanner集群（universe）。它包括一个universemaster服务、一个placement dirver服务和多个Zone（类似于Bigtable中的server）。在集群运行过程中，可以给集群加入新的zone或者从集群中退役现存的zone。一个zone包含一个zonemaster和成百上千个spanserver，每个spanserver负责管理100～1000个tablet，每个tablet都是一段kv map（其数据模型是[(key:string, timestamp:int64)→string]），这些kv map都是LSM tree。zonemaster将数据分配给spanner，其实就是在spanserer里构建（写入）tablet，客户端根据location proxy定位到确定的spanserver获取数据服务。universemaster用于监控集群中每个zone的状态信息。placement driver定期与每个spanserver交互，找到那些由于副本的约束信息更新或者为了平衡负载而需要移动的数据。

为了实现高可用，spanner给一份数据维护多个副本（通常3～5个副本），具体实现就是每个spanserver在每个tablet之上维护一个paxos复制状态机。paxos用于实现table的一致性复制，所有对table的写操作，都必须在这个paxos组的leader上发起，然后同步复制到这个paxos的法定数量的副本之后才表示这个写操作成功。一个读操作可以在任何足够新（up-to-date）的副本上进行。

先铺垫这么多了，虽然Spanner还有很多其它特性，但是本文主要探讨Spanner的事务实现，所以在此不做介绍了。

二：事务实现

作为一款支持全球部署的分布式数据库，Spanner的大的特点之一就是它提供了支持外部一致性的通用事务。在Spanner中，事务分为以下几种类型：Read-Write Transaction、Read-Only Transaction（包括Snapshot Read，它们的底层原理是相似的）和Schema-Change Transaction。实现这一切的基础，是Spanner实现了一个基于硬件的TrueTime时间戳接口，通过这个接口，使得Spanner能将集群的时钟偏移控制在10ms（下文一律用  表示系统的大时钟偏移）以内，这样再加上并发控制时的特殊处理，终让Spanner给用户提供了支持外部一致性的通用事务（关键在于事务的延迟在用户可接受范围之内，如果不考虑事务延迟，那么即是时钟偏移有数百毫秒，也能通过特殊手段实现外部一致性，但是这样的事务由于高延迟是没有实用价值的）。在这里我们也不深究TrueTime接口是如何实现的，只需要知道通过TrueTime，系统的时钟偏移下降到  。TrueTime提供三个主要的方法，TT.now()方法返回一个时间戳区间[earliest, latest]，如果假设此时的时间是t，那么这个区间就是[t-  , t+  ]，TT.after(t)返回true如果TT.now()的时间戳区间肯定已经过了时间戳t（其实也就是TT.now().earliest > t，TT.before(t)返回true如果TT.now()的时间戳区间肯定还没有到达时间戳t（即TT.now().latest < t)。

1：Spanner的外部一致性

Spanner在论文中并没有给出外部一致性（externally consistent）的严格定义，而只是说明了外部一致性的表现：如果一个事务T1在事务T2开始之前提交了，那么可以肯定T1的提交时间戳小于T2的开始时间戳。这其实也正是分布式系统中线性一致性（linearizability）的表现，他们也说明了外部一致性等价于线性一致性。这里会介绍一下什么是线性一致性。

在介绍线性一致性之前，首先介绍一下什么是Serializability。Serializability是数据库中的一个概念，表示的是数据库的隔离级别，在这种隔离级别下，数据库对多个并发事务的一个调度和将这些事务以某种顺序逐个串行产生的结果相同。比如如下场景：

#txn1           #txn2                     #txn1         #txn2
read(A);                                  read(A);
write(A);                                 write(A);
                read(A);                  read(B);
                write(B);      ====>      write(B);
read(B);                                                read(A);
write(B);                                               write(A);
                read(B);                                read(B);
                write(B);                               write(B);