Introduction
Spanner 数据库中的数据是分片(Shard)分散存储在多个数据中心的，数据是用 Paxos 算法(状态机)保证一致性。如果数据中心发生变化，Spanner 自动做 reshard。
Spanner 中的数据是存储在 schematized semi-relational table 上的。 在 commit 的时候把 timestamp 作为数据的 version。老版本的数据可以被垃圾回收，client 也可以读老数据。
Spanner 有两个特性是一般的分布式系统非常难实现的，
- 读和写操作的外部一致性。
- 在一个时间戳下，读操作是全局一致的。
能实现以上两点，是因为 Spanner 可以分配全球范围内保持一致的 commit timestamp。Spanner 的 timestamp 靠 TrueTime API 实现，甚至可以用 GPS 和原子钟来提高 TrueTime API 的精度。
Implementation
一个 Spanner 集群被称为一个 universe，如下图所示
Spanner 被组织成许多个 zone 的集合，zone 是管理部署的基本单元。一个数据中心可能会有多个 zone，zone 也是物理隔离的单元，例如，两个不同应用的数据就会被分散在两个 zone 上。
- Zonemaster 把数据分配给 spanserver，spanserver 是真正存数据的地方
- Client 从 location proxy 定位数据在哪个 spanserver 上
- Universe master 主要是一个管理界面
- Placement driver 周期性的与 spanserver 交互，进行负载均衡
Spanserver Software Stack
每一台 spanserver 上会存 100 到 1000 张表，每一张表上都有一个 Paxos 状态机，每一个 Paxos 状态机都会把自己的 metadata 和 log 存在 tablet 上。
每个 spanserver 会实现一个锁表 lock table 来实现并发控制，锁表包含了两阶段锁机制的状态:它把键的值域映射到锁状态上面。
Spanner 专门为长事务做了优化，比如对于报表操作，可能要持续几分钟，当存在冲突时，采用乐观并发控制机制会表现出很差的性能。
对于那些需要同步的操作，比如事务型的读操作，需要获得锁表中的锁，而其他类型的操作则可以不理会锁表。
乐观锁 optimistic locking，总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量，
悲观锁 pessimistic locking，总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁
事务，是访问并可能操作各种数据项的一个数据库操作序列，这些操作要么全部执行,要么全部不执行，是一个不可分割的工作单位
Directories and Placement
目录是数据放置的基本单元，当数据在不通 Paxos group 之间移动时，是基于目录一个一个移动。
一个 Paxos group 可以包含多个目录，一个 Spanner tablet 没有必要是一个行空间内按照词典顺序连续的分区，相反，它可以是行空间内的多个分区。
一个目录也是一个应用可以指定的放在哪个地理位置的最小单元。
Data Model
Spanner 类似于一个关系型数据库，但也有区别。比如每一个表都要包含一个或多个主键的排序集合。这一点让 Spanner 看起来像 KV 的数据库。
以下是一个类似 SQL 创建表的 Schema 的例子
TrueTime
TrueTime 是由每个数据中心上面的许多 time master 机器和每台机器上的一个 timeslave daemon 来共同实现的。
每个 daemon 会从许多 master 中收集投票，获得时间参考值，从而减少误差。Daemon 会使用一个 Marzullo 算法的变种，来探测和拒绝欺骗
Concurrency Control
Timestamp Management
Spanner 可以支持读写事务、只读事务和快照读。独立写操作，会被当成读写事务来执行。非快照独立读操作，会被当成只读事务来执行。
一个只读事务具备快照隔离的性能优势。一个只读事务中的读操作不包含锁机制，因此，后面到达的写操作不会被阻塞。在一个只读事务中的读操作，可以到任何足够新的副本上去执行。
一个快照读操作，是针对历史数据的读取，执行过程中，不需要锁机制。
Paxos Leader Leases
这一节是关于 Paxos leader 的租约，原文不长但是讲的很抽象，不知道具体怎么实现。
Assigning Timestamps to RW Transactions
事务读和写采用两段锁协议。当所有的锁都已经获得以后，并且任何锁被释放之前，都可以给事务分配时间戳。对于一个给定的事务，Spanner 会为事务分配时间戳，这个时间戳是 Paxos 分配给 Paxos 写操作的，它代表了事务提交的时间。
Serving Reads at a Timestamp
上一节中描述的单调性，使得 Spanner 可以正确地确定一个副本是否足够新，从而能够满足一个读操作的要求。每个副本都会跟踪记录一个值，这个值被称为安全时间 tsafe，它是一个副本最近更新后的最大时间戳。如果一个读操作的时间戳是 t，当满足 t<=tsafe 时， 这个副本就可以被这个读操作读取。
Assigning Timestamps to RO Transactions
一个只读事务分成两个阶段执行:分配一个时间戳 sread[8]，然后当成 sread 时刻的快照读来执行事务读操作。快照读可以在任何足够新的副本上面执行。
Details
重点介绍读写操作实践的细节，包括三种类型的事务：读写事务，只读事务，Schema 变更事务。
中间关于 Benchmark 的部分省略。
Related Works
最后一节 “相关工作” 值得一读，从中能了解业界还有哪些类似 Spanner 的系统，以及他们的优缺点。翻译拷贝自参考资料。
Megastore[5]和 DynamoDB[3]已经提供了跨越多个数据中心的一致性复制。DynamoDB 提供了键值存储接口，只能在一个 region 内部进行复制。Spanner 和 Megastore 一样，都提供了半关系数据模型，甚至采用了类似的模式语言。Megastore 无法活动高性能。Megastore 是架构在 Bigtable 之上，这带来了很高的通讯代价。Megastore 也不支持长寿命的领导者， 多个副本可能会发起写操作。来自不同副本的写操作，在 Paxos 协议下一定会发生冲突，即使他们不会发生逻辑冲突:会严重影响吞吐量，在一个 Paxos 组内每秒钟只能执行几个写操作。Spanner 提供了更高的性能，通用的事务和外部一致性。
Pavlo 等人[31]对数据库和 MapReduce[12]的性能进行了比较。他们指出了几个努力的方向，可以在分布式键值存储之上充分利用数据库的功能[1][4][7][41]，二者可以实现充分的融合。我们比较赞同这个结论，并且认为集成多个层是具有优势的:把复制和并发控制集成起来，可以减少 Spanner 中的提交等待代价。
在一个采用了复制的存储上面实现事务，可以至少追述到 Gifford 的论文[16]。Scatter[17] 是一个最近的基于 DHT 的键值存储，可以在一致性复制上面实现事务。Spanner 则要比 Scatter 在更高的层次上提供接口。Gray 和 Lamport[18]描述了一个基于 Paxos 的非阻塞的提交协议，他们的协议会比两阶段提交协议带来更多的代价，而两阶段提交协议在大范围分布 式的组中的代价会进一步恶化。Walter[36]提供了一个快照隔离的变种，但是无法跨越数据中心。相反，我们的只读事务提供了一个更加自然的语义，因为我们对于所有的操作都支持外部语义。
最近，在减少或者消除锁开销方面已经有大量的研究工作。Calvin[40]消除了并发控制: 它会重新分配时间戳，然后以时间戳的顺序执行事务。HStore[39]和 Granola[11]都支持自己的事务类型划分方法，有些事务类型可以避免锁机制。但是，这些系统都无法提供外部一致性。Spanner 通过提供快照隔离，解决了冲突问题。
VoltDB[42]是一个分片的内存数据库，可以支持在大范围区域内进行主从复制，支持灾难恢复，但是没有提供通用的复制配置方法。它是一个被称为 NewSQL 的实例，这是实现 可扩展的 SQL[38]的强大的市场推动力。许多商业化的数据库都可以支持历史数据读取，比如 Marklogic[26]和 Oracle’ Total Recall[30]。Lomet 和 Li[24]对于这种时间数据库描述了一种 实现策略。
Faresite 给出了与一个受信任的时钟参考值相关的时钟不确定性的边界[13](要比 TrueTime 更加宽松):Farsite 中的服务器租约的方式，和 Spanner 中维护 Paxos 租约的方式 相同。在之前的工作中[2][23]，宽松同步时钟已经被用来进行并发控制。我们已经展示了 TrueTime 可以从 Paxos 状态机集合中推导出全球时间。