【论文阅读】Spanner

论文链接 Spanner: Google’s Globally-Distributed Database

1 背景

Spanner 是一种可扩展，分布式数据库，本质上也是一种由多个Paxos状态机组成的分片式数据库。它能实现全局数据拷贝，数据迁移。Spanner的目的是为了管理跨数据中心的复制数据，相比较于Bigtable不能很好的完成复杂且变化的模式的应用。而且将原先key-value存储结构改为半关系型表中。

Spanner具备一些特性，第一能够动态控制管理数据中心，读写延迟，第二提供外部全局一致的读写，基于时间戳全局一致性。

2 实现

Spanner的部署被称为universe(宇宙？领域？) 。Spanner 被组织为一组名为zones的集合，每个zone可以类比为Bigtable中的服务器。zone是一个管理部署的单元，正如字面的意思，通常可以用地理位置划分。每个数据中心可以有一个或多个zone来操作添加和删除。

如下图所示，每个zone内部包含一个zonemaster和成百上千个spanserver，前者负责传递数据给spanserver, 而spanserver为客户端提供服务。Universemaster通常用来显示每个zone的信息和调试，placement driver负责自动管理跨zone通信，同时也能控制span server数据移动和更新。

2.1 Spanserver 软件架构

Spanner的tablet是一种数据结构，每个spannerserver会包含100到1000个tablet。这里和Bigtable中类似，实现了一个映射 (key:string, timestamp:int64) →string，不同点是spanner为每个数据增加了时间戳，这样更像是一种使用时间戳划分多版本的数据库。Colossus是一个分布式文件系统，保存的是tablet的预写式日志。为了支持复制，tablet上有一个单独Paxos状态机，采用基于时间的领导者租约，默认时长是10秒。Paxos 状态机被用于实现 一致复制的键值映射集合）。每个副本的键值映射状态都存储在其对应的 Tablet 中。写入必须由领导者启动 Paxos 协议，而取则可以直接访问任何的副本的底层 Tablet。

2.2 目录和位置

目录作为数据放置的基本单位

• 所有属于同一目录的数据共享相同的复制配置
• 当数据在 Paxos 组之间迁移时，它是以目录为单位进行迁移的，如下图所示。
• Spanner 可能会移动一个目录，以：
  1. 减少某个 Paxos 组的负载（shed load）。
  2. 将经常被一起访问的目录放入同一个 Paxos 组（提高访问效率）。
  3. 将目录迁移到更靠近其访问者的 Paxos 组（减少访问延迟）。

目录可以在客户端操作进行的同时迁移，且 一个50MB大小的目录通常可以在几秒钟内完成迁移

Movedir 是一个后台任务，用于在 Paxos 组 之间移动 目录。此外，它还负责 添加或移除 Paxos 组中的副本，因为 Spanner 目前尚未支持 Paxos 内部的配置变更。为了避免在大规模数据迁移时 阻塞正在进行的读写操作，Movedir 不会 作为一个单一事务执行，而是首先 注册迁移操作，然后在后台移动数据。当大部分数据迁移完成后，Movedir 通过 一个事务 来 原子性地 迁移剩余的小部分数据，并更新两个 Paxos 组的元数据。

目录是数据放置的最小单位，应用可以指定其 地理复制属性。Spanner 设计了一种 数据放置配置语言 来管理复制配置管理员 负责 控制副本的数量和类型 以及 副本的地理位置，并预定义不同的复制配置应用通过标记数据库或目录，选择合适的复制配置。

例如： 用户 A 的数据可以存储在欧洲的3个副本 中 用户 B 的数据可以存储在北美的5个副本 中 实际上，目录可能会被拆分成多个片段，如果目录增长过大，这些片段可能会被分配到 不同的 Paxos 组（甚至不同的服务器）。因此，Movedir 真正迁移的是片段，而不是整个目录。

2.3 数据模型

Spanner 为应用提供了以下关键特性：基于具有模式（schema）的“半关系型”表的数据模型、类 SQL 的查询语言，以及支持跨行操作的通用事务功能。Spanner 要求所有表必须有一个或多个主键列，且这些主键列是有序的。Spanner 选择提供完整的事务支持，允许开发者先使用简单的方式编写具有事务语义的应用，然后在需要时再对性能瓶颈进行针对性优化，而不是在一开始就因为缺少事务而让开发者编写额外的应用层逻辑来保证一致性。

2.4 TrueTime

TrueTime 是 Google Spanner 数据库中使用的 全局时钟同步系统，用于提供 严格的外部一致性的事务保证，它能提供一个全局统一的时间戳，并且能够量化时间的不确定性。 TrueTime 采用 时间区间而不是单一时间点，使用范围来表示不确定性。它依赖于 Google 的全球数据中心基础设施，结合了 两种物理时钟：

GPS 时钟（Global Positioning System）：接收卫星信号，提供全球时间同步。 原子钟（Atomic Clocks）：用于提供高度精准的本地时间

TrueTime 主要用于 全局事务一致性，确保分布式事务满足 外部一致性和线性化。如果事务 T1 在事务 T2 之前提交，那么所有节点都会看到 T1 的更改在 T2 之前生效。即使 T1 和 T2 发生在不同的数据中心，顺序也能保持，通过时间戳排序来实现这一点，事务提交时通过等待机制避免时钟不同步导致的问题。

3 并发控制

并发控制是分布式系统所必须的，这学期有门课叫数据库系统实现，用的PostgreSQL也提到了这个概念。接下来主要讲如何利用TrueTime实现外部一致性，无锁只读事务，无阻塞读取。

3.1 时间戳管理

Operation	Timestamp Discussion	Concurrency Control	Replica Required
Read-Write Transaction	§ 4.1.2	pessimistic	leader
Read-Only Transaction	§ 4.1.4	lock-free	leader for timestamp; any for read, subject to § 4.1.3
Snapshot Read, client-provided timestamp	—	lock-free	any, subject to § 4.1.3
Snapshot Read, client-provided bound	§ 4.1.3	lock-free	any, subject to § 4.1.3

如上面的表所示，Spanner支持4种事务。只读事务必须预先声明不会进行任何写入操作；它不仅仅是一个没有写入的读写事务。 在只读事务中，读取操作会在系统选定的时间戳上执行，并且不需要加锁，因此不会阻塞新的写入操作。 只读事务的读取操作可以在任何足够新的副本上执行。快照读取是指在过去某个时间点执行的读取操作，并且不使用锁。 客户端可以指定一个时间戳来进行快照读取，或者提供所需时间戳的过时性上限，由 Spanner 自动选择时间戳。

3.1.1 Paxos 领导者租期

Spanner 的 Paxos 实现使用定时租约来使领导者的任期较长（默认 10 秒）一个潜在的领导者会发送请求以获得定时租约投票；当收到法定数量的租约投票后，该领导者便知道自己已获得租约。副本在成功写入时会隐式地延长其租约投票，而领导者会在租约即将到期时请求延长租约投票。Spanner 依赖以下互斥性不变量：对于每个 Paxos 组，每个 Paxos 领导者的租约区间都与其他领导者的租约区间互不重叠。

3.1.2 为读写事务分配时间戳

事务的读写操作使用两阶段锁，Spanner 依赖以下单调性不变量：在每个 Paxos 组内，Spanner 以单调递增的顺序为 Paxos 写入操作分配时间戳，即使是在不同的领导者之间也是如此。Spanner 还强制执行以下外部一致性不变量：如果事务 T2 的开始时间发生在事务 T1 提交之后，则 T2 的提交时间戳必须大于 T1 的提交时间戳。

3.1.3服务读取时间戳

Spanner需要确定所有副本是最新的，以正确处理请求。每个副本会维持一个t_safe表示该时间戳之前的数据是最新的，只有当读取时间戳 t 满足 t ≤ t_safe 时，副本才能满足该读取请求。t_safe由两个值取最小值决定，第一个是Paxos安全时间，第二个是事务管理器（TM）安全时间，由于受到两阶段提交的影响，处理已准备但尚未提交的事务。对于如何计算TM，每个参与者领导者为每个事务 T_i 记录一个“准备”时间戳 s_prepare_i,g，表示该事务 T_i 在 Paxos 组 g 的准备时间。

事务的最终提交时间 s_i 必须大于等于 s_prepare_i,g（即 s_i ≥ s_prepare_i,g）取所有参与者 Paxos 组 g 中，所有处于“已准备”状态事务 T_i 的 s_prepare_i,g 的最小值 min(s_prepare_i,g)-1，那么 \begin{align} t_{\text{safe}}^{TM} &= \min_{i} \left( s_{\text{prepare}, i, g} \right) - 1 \end{align} 这样可以确保 Spanner 不会读取到那些可能会回滚或未确定的事务状态。

3.1.4 只读事务分配时间戳

只读事务的执行分为两个阶段 1 分配一个时间戳s 2 在 s 时间戳下执行事务的读取操作，这些读取操作作为快照读取执行，并且可以在任何足够最新的副本上完成

3.2细节

3.2.1 读写事务

1. 事务的写入不会立即生效，而是缓存在客户端直到提交。如果读取操作时，事务正在执行尚未提交，那么则看不到写入。

2. 在读写事务中使用would-wait避免死锁，读取过程：客户端向 适当 Paxos 组的 leader 副本发送读取请求。leader 副本获取读取锁，并返回最新的数据。在事务仍然活跃的情况下，客户端持续发送 keepalive 消息，防止参与者超时，从而保持事务状态。

3. 事务提交的两阶段提交（2PC）。当客户端完成所有读取，并且缓存了所有写入，它开始两阶段提交。PC客户端选择一个协调者，向所有参与者的 leader 发送 commit 消息其中包括：协调者的身份信息，所有缓存的写入数据。让客户端负责驱动 2PC 过程，避免在广域网络（WAN）中发送两次数据，从而提高效率。

4. 非协调者的提交步骤：先获取写锁。选择一个准备时间戳 s_prepare必须大于该 leader 为先前事务分配的所有时间戳，通过 Paxos 记录 prepare 事务状态，通知协调者自己的 prepare 时间戳。

5. 协调者的提交步骤：协调者 leader先获取写锁，在所有参与者 leader 反馈 prepare 时间戳后，选择整个事务的提交时间戳 s。通过 Paxos 记录提交状态（如果超时等原因导致提交失败，则记录 abort）

6. 提交等待 为了保证外部一致性，协调者 leader 必须等待 TT.after(s)，s 是基于 TT.now().latest 选择的

7. 事务最终提交，等待结束后，协调者 leader 将最终提交时间戳 s 发送给客户端（通知事务已提交），所有参与者 leader（同步最终事务状态。所有参与者 leader 通过 Paxos 记录事务结果，所有副本在相同的时间戳 s 应用写入，并释放锁。

3.2.2 只读事务

只读事务的时间戳分配需要在所有涉及的 Paxos 组之间进行协商，以确保读取数据的一致性。 Spanner 需要为每个只读事务提供一个“范围表达式”，它概括了事务将要读取的键。

只涉及单个 Paxos 组的情况下，Spanner 可以使用 LastTS() 作为 s_read，避免不必要的延迟。涉及多个 Paxos 组的情况下，Spanner 直接使用 TT.now().latest 作为 s_read，避免额外的通信开销，但可能需要等待 t_safe 。

3.2.3 模式变更事务

Spanner 的模式变更事务是一种“非阻塞”版本的事务，相比标准事务，影响范围更小，避免阻塞整个系统。主要有两个特性，并且依赖于TrueTime

1. 未来时间戳提交，模式变更事务的时间戳 t 预先分配在未来，并在准备阶段注册，这样可以确保跨千台服务器的模式变更操作能在最小干扰下完成。
2. 读写操作如何与模式变更事务同步，所有读取和写入操作都会隐式依赖数据库模式，如果某个读写操作的时间戳早于 t，那么它可以正常执行，不受模式变更的影响。如果某个读写操作的时间戳晚于 t，那么它必须阻塞，等待模式变更事务完成

3.2.4 改进

Spanner 中 t_safe和 LastTS()可能会产生阻塞，这里提出了一种方法避免这个问题。

对于事务管理器安全时间的问题，按照键范围存储已准备事务的时间戳。这些信息可以存储在锁表中，因为锁表本身就维护了键范围与锁元数据的映射。读取请求到达时仅需要检查与其冲突的键范围的安全时间。避免无关的数据读取被阻塞，减少不必要的等待。

对于LastTS()（最后提交时间）的局限性，在锁表中维护一个映射，记录每个键范围的提交时间戳。读取请求到达时只需要查询相关键范围的 LastTS()，并基于事务冲突情况分配 s_read。提高读取效率。

对于Paxos 安全时间的局限性，利用领导者租约的“互斥性不变量“，每个 Paxos 领导者维护 MinNextTS(n) 映射。MinNextTS(n) 记录 Paxos 序列号 n 之后的最小可分配时间戳，当某个副本已应用 Paxos 序列号 n，它可以将 t_safe^{Paxos} 推进到 MinNextTS(n) - 1。

对于领导者的 MinNextTS() 推进策略，默认情况下，每个 Paxos 领导者每 8 秒推进 MinNextTS()。在没有已准备事务的情况下，Paxos 组中的健康从节点最多只能落后 8 秒。如果从节点需要更高的 t_safe^{Paxos}，它可以向领导者请求提前推进 MinNextTS()