spanner特性
Spanner是谷歌公司研发的、可扩展的、多版本、全球分布式、同步复制数据库。
目的：管理跨越多个数据中心的数据副本，弥补BigTable在一些场景下的不足
它具有以下特性：
- 大规模，可扩展，全球分布式：可以扩展到几百万个机器节点，跨越成百上千个数据中心，具备几万亿数据库行的规模
- 细粒度动态副本配置
- 读写操作的外部一致性
- 一个时间戳下面的跨越数据库的全球一致性的读操作
实现
一个Spanner部署称为一个universe，下图所示为universe架构，由许多个zone组成，每个zone相当于一个bigtable服务器，zone是管理部署的基本单元。一个zone包括一个zonemaster，和一百至几千个spanserver。Zonemaster把数据分配给spanserver，spanserver把数据提供给客户端。客户端使用每个zone上面的location proxy来定位可以为自己提供数据的spanserver。Universe master和placement driver，当前都只有一个。Universe master主要是一个控制台，它显示了关于zone的各种状态信息，可以用于相互之间的调试。Placement driver会周期性地与spanserver进行交互，来发现那些需要被转移的数据，或者是为了满足新的副本约束条件，或者是为了进行负载均衡。
spanserver软件栈
tablet
每个spanserver负责管理100-1000个tablet，一个tablet实现如下映射：
(key:string, timestamp:int64)->string一个tablet的状态是存储在类似于B树的文件集合和写前(write-ahead)的日志中，所有这些都会被保存到一个分布式的文件系统中，这个分布式文件系统被称为Colossus，它继承自Google File System
Paxos
每个tablet上都实现一个Paxos状态机，一组Paxos维护的副本称为Paxos Group，Paxos组中的leader租期为10s，并通过流水线化降低时延弥补Paxos性能，写操作保证有序。写操作通过Paxos状态机，而读操作直接通过tablet。
lock table
作为leader的副本上会实现一个lock table来进行并发控制。这个lock table包含了两阶段锁机制的状态：它把key的值域映射到锁状态上面，对于那些需要同步的操作，比如事务型的读操作，需要获得lock table中的锁，而其他类型的操作则可以不理会lock table。
transaction manager
在leader上还有一个事务管理器来支持分布式事务。如果一个事务只包含一个Paxos组，就可以绕过transaction manager，如果一个事务包含了多于一个Paxos组，那些组的领导者之间会彼此协调合作完成两阶段提交。每个事务管理器的状态，会被保存到底层的Paxos组。
Directories and Placement
Directory是一组连续的键，拥有相同的前缀，从而保证locality。
- Directory是数据移动的基本单元。通过使得经常同时访问的Directory移动到同一个Paxos Group保证本地性。
- Directory是数据放置的基本单元。同Directory的数据有着相同的备份配置，管理员可以以directory为单元配置备份的数目、类型、放置地区。
TrueTime
spanner使用TrueTime API作为分布式的时间系统
| method | returns |
| TT.now() | 时间区间[earliest, latest] |
| TT.after(t) | true if t has definitely passed |
| TT.before(t) | true if t has definitely not arrived |
TT.now()返回一个时间区间，[t - ε, t + ε]，这个ε通过GPS和原子钟可以达到ms级别，TrueTimes是通过硬件实现的，一般的分布式系统难以实现，TiDB采用TSO来进行授时
TrueTime保证了在时间戳为t的时刻的数据库读操作，一定只能看到在t时刻之前已经提交的事务。
并发控制
Spanner可以支持的操作包括：
- 读写事务
- 只读事务（预先声明的快照隔离事务）
- 快照读
Paxos leader租约：当一个leader的候选者获取到一定数量的票之后，将会获得一个租约，成为leader，租约的默认时间是10s，当一个副本的写操作成功之后会延长自己的租约的时间。spanner会保证一个Paxos组中每个leader的租期不连续，假设s为一个leader租期的最大值，只有当TT.after(s)为true时，leader才能够退位。
读写事务：假设事务a发生绝对时间为tt.a，那么我们只能知道tt.a.earliest <= tt.a <= tt.a.latest, 所以对于另一个事务b，只要tt.b.earliest > tt.a.latest，我们就能确定b一定是在a之后发生的，也就是说，我们需要等待大概2ε（commit wait）的时间才能去提交b
独立写操作：会被当成读写事务来执行；非快照独立读操作，会被当成只读事务来执行。
快照读事务：通过指定时间戳读取数据，不需要锁机制，每个副本会记录一个安全的时间戳，t_safe，只要指定的时间戳t<t_safe，那么该副本就可以被这个读操作读取。
只读操作：只读操作被分配时间戳为s_read=TT.now().latest，然后就可以当做快照读来处理，但是如果t_safe不够大，s_read的读操作将被阻塞，为了减少阻塞的概率，Spanner应该分配可以保持外部一致性的最老的时间戳。
