Spanner 全球化分布式数据库

Title: Google’s Globally-Distributed Database,Spanner is Google’s scalable, multi-version, globallydistributed, and synchronously-replicated database

论文中实现了广域的事务服务，也是在Google广泛使用的一种技术

  • R/W Transaction: 2PC + 2PL + Paxos Group
  • R/O Transaction: Snapshot isolation + Synchronized Clocks

Implementation

Spanner部署

Spanner的部署叫做universe，可以让Spanne全球性的管理数据，谷歌中使用了三套Spanner部署分别用于:测试、研发、上线

​ 如上图Spanner server的结构图中，Spanner由多个Zone(管理部署的单元、物理隔离的单元)组成。一个数据中心中可以由一个或者多个Zone

​ 上图中的一个Zone有一个zonemaster(分配数据给spanserver) 和100-1000个spanserver (服务与客户端)，用户使用localtion proxies 定位每个Zone中分配数据服务的spanservers

  • universe master:主要是一个控制台，它显示了关于 zone 的各种状态信息，可以用于相互之间的调试
  • Placement driver: 会周期性地与 spanserver 进行交互，来发现那些需要被转移的数据，或者是为了满足新的副本约束条件，或者是为了进行负载均衡

    Spanserver SoftWare Stack

每个Spanserver的副本部署以及软件栈

SpannerSoftware

组成部分

  • Colossus:放置tablet的文件系统,GFS的升级版
  • tablet:类似于bigtable中的tablet，实现如下映射(key:string, timestamp:int64)->string
  • Paxos:共识算法于raft类似
  • replica:Paxos的上层状态机
  • locktable:实现并发控制,与分布式事务([[Distribute Transaction 笔记#两阶段锁（Two-Phase Locking）——悲观并发]])的二阶段锁相同
  • Transaction manager：每个Paxos组中的支持分布式事务的软件

    结构分析

universe的结构中展示了多个Zone中都含有100-1000个Spanserver，Zone可以理解为一个区域(地域)的数据中心。而每个SpanServer都是由一个Paxos状态机和Paxos协议组成(但是一个Paxos Group的Paxos副本不一定在一个Zone中),不同Zone之间的数据复制也是通过Paxos Group

​ Spanner于bigtable不同之处在于，Spanner分配Timestamp给数据作为版本号，是其更像是一个多版本数据库，而不是键值对的存储，tablet的状态存储在B-tree类似的文件与WAL中

​ tablet的上层则是一个paxos的状态机方便复制(Paxos的一些细节我也没有研究过，复制过程可以参考[[Raft实验#Lab 2B : Log Replicated]])。每次写操作都需要写入两次：1.写入tablet的log中 2.写入Paxos的日志中。写操作必须在领导者上初始化 Paxos 协议，读操作可以直接从底层的任何副本的 tablet 中访问状态信息，只要这个副本足够新。副本的集合被称为一个 Paxos group。

​ 对于每个是领导者的副本而言，每个 spanserver 会实现一个锁表来实现并发控制。对于那些需要同步的操作，比如事务型的读操作，需要获得锁表中的锁，而其他类型的操作则可以不理会锁表。

​ 对于每个Paxos Group中都会有Leader会开启Transaction manager功能，每个拥有该功能的副本就称为一个Participant Leader，其余副本称为Participant slave。如果只有一个Paxos组如果一个事务只包含一个 Paxos 组(对于许多事务而言都是如此)，它就可以==绕过事务管理器==，因为锁表和 Paxos 二者一起可以保证事务性。如果一个事务包含了多 于一个 Paxos 组，那些组的领导者之间会彼此协调合作完成==两阶段提交==。其中一个参与者组，会被选为协调者，该组的 participant leader 被称为 coordinator leader，该组的 participant slaves 被称为 coordinator slaves。

directory

directory

​ Spanner 对具有公共前缀的键做了一个抽象，称为 directory。目前一个 directory 是数据存放的基本单位。属于一个目录的所有数据，都具有相同的副本配置。 当数据在不同的 Paxos 组之间进行移动时，会一个目录一个目录地转移，如上图所示。Spanner 可能会移动一个目录从而减轻一个 Paxos 组的负担，也可能会把那些被频繁地一起访问的目录都放置到同一个组中，或者会把一个目录转移到距离访问者更近的地方。当客户端操作正在进行时，也可以进行目录的转移。我们可以预期在几秒内转移 50MB 的目录。

directory 是数据复制和placement配置的基本单位。spanner中负载均衡的最小单位也是 directory，同时提供方法 MoveDir 可以手动将一个 directory 移动到指定的zone

Data Model

​ spanner的行模型是 (key:string, timestamp:int64) -> row content，可以看到跟big table的模型最大的不同是这里强化了row的概念，不再突出column；这样spanner的timestamp是赋给整行数据的，是有物理意义的，这使得spanner更像一个实现多版本并发的数据库，而在big table中，timestamp仅仅用于保存多个版本的key-value，跟并发完全无关；我觉得这也是为什么spanner称自己为semi-relational 数据库，而big table只称自己是semi-structure 数据库的原因。

​ Spanner 的数据模型不是纯粹关系型的，它的行必须有名称。更准确地说，每个表都需 要有包含一个或多个主键列的排序集合。这种需求，让 Spanner 看起来仍然有点像键值存储: 主键形成了一个行的名称，每个表都定义了从主键列到非主键列的映射。当一个行存在时，必须要求已经给行的一些键定义了一些值(即使是 NULL)。采用这种结构是很有用的，因为这可以让应用通过选择键来控制数据的局部性。

High-level Organization

​ 考虑下图3个数据中心的A、B、C(存在于不同的地域中)，数据存储在分片中,包含了数据库的行和一些键值对，例如A的分片中有键A-M的。现将该分片复制到B、C数据中心中，即使整个数据中心出现故障也可以继续。

​ 位于不同数据中心的spanserver形成了Paxos Group 如Figure3中所示，也就是一个Paxos Group中的副本可以存在于不同数据中心中。三个键A-M的shard是通过日志复制使状态机去更新键值对

设计原因

  • 多个分片是为了获得更好的并行性

  • 每个分片有一个Paxos组用于复制，若a-c的距离远复制开销大，也只需要a、b之间获得majority即可

  • 数据中心的容错，速率过慢

  • 副本靠近客户端，客户可以获得高性能的只读事务,其原理[[KVRaft#Read-Only Query:]]

Challenge

Read of local Relipca yield latest write

​ 追求更强的一致性，在ZooKeeper中实现的fast-read是弱的线性一致性。本地副本需要读到最新的写，在本文中将会用到

Trasaction across shard

​ 支持跨分片的事务，例如转账事务中一个分片是一个账户、另一个分片是目标账户，当我们要执行转账操作时可以像事务一样执行，并且具有ACID的语义

Transaction must be serializable

​ 读取多条记录的事务必须是可序列化的。但是本地碎片可能反映已提交事务的不同子集!

True Time

Method return
TT.now() TTinterval: [earliest, latest]
TT.after(t) true if t has definitely passed
TT.before(t) true if t has definitely not arrived

TrueTime API 是一个非常有创意的东西，可以同步全球的时间。

  • TT.now()可以获得一个绝对时间TTinterval，这个值和UnixTime是相同的，同时还能够得到一个误差e。

  • TT.after(t)和TT.before(t)是基于TT.now()实现的。

​ 那这个TrueTime API实现靠的是GFS和原子钟。之所以要用两种技术来处理，是因为导致这两个技术的失败的原因是不同的。GPS会有一个天线，电波干扰会导致其失灵。原子钟很稳定。当GPS失灵的时候，原子钟仍然能保证在相当长的时间内，不会出现偏差。实际部署的时候。每个数据中心需要部署一些Master机器，其他机器上需要有一个slave进程来从Master同步。有的Master用GPS，有的Master用原子钟。

Denote the absolute time of an event e by the function $t_{abs}$(e).

In more formal terms, TrueTime guarantees that for an invocation tt = TT.now(), tt.earliest ≤ $t{abs}$($e{now}$) ≤ tt.latest, where enow is the invocation event.

Concurrent control

Timestamp Management

Spanner使用TrueTime来控制并发，实现外部一致性。支持以下几种事务。

  • 读写事务：读写操作的集合
  • 只读事务：只有读操作，并且提供的snapshot isolation的功能，保证强一致性
  • 快照读,只读事务由客户端提供时间戳：可以读取stale data
  • 快照读,客户端提供时间范围

​ 上表是Spanner现在支持的事务。单独的写操作都被实现为读写事务 ； 单独的非快照被实现为只读事务。事务总有失败的时候，如果失败，对于这两种操作会自己重试，无需应用自己实现重试循环。

​ 时间戳的设计大大提高了只读事务的性能。事务开始的时候，要声明这个事务里没有写操作，只读事务可不是一个简单的没有写操作的读写事务。它会用一个系统时间戳去读，所以对于同时的其他的写操作是没有Block的(只读事务是lock free的)。而且只读事务可以在任意一台已经更新过的replica上面读。

​ 对于快照读操作，可以读取以前的数据，需要客户端指定一个时间戳或者一个时间范围。Spanner会找到一个已经充分更新好的replica上读取。

​ 还有一个有趣的特性的是，对于只读事务，如果执行到一半，该replica出现了错误。客户端没有必要在本地缓存刚刚读过的时间，因为是根据时间戳读取的。只要再用刚刚的时间戳读取，就可以获得一样的结果。

读写事务

RW Transaction without TS

​ A、B是两个不同的数据中心，客户端最开始的请求的读操作并不是事务操作，目的是为了找到Paxos Group的leader，并且Leader在锁表中分配该数据的锁，当client获得返回值时进行提交(commit)，该实现与Lab3中的读操作服务本质相同。后续执行二段提交部分，提交完成后并释放锁。

​ 这种实现与Distribute Transaction中实现的2PC+2PL的实现方法相同，只不过加入了Paxos的容错设计

Assigning Timestamp to RW Transaction

​ 事务的读写将会用到二段锁，当所有的锁都已经获得以后，在任何锁被释放之前(也就是持有所有锁期间)，就可以给事务分配时间戳。对于一个给定的事务，Spanner 会为事务分配时间戳，这个时间戳是 Paxos 分配给 Paxos 写操作的，它代表了事务提交的时间。

​ Spanner 依赖下面这些单调性:在每个 Paxos 组内，Spanner 会以单调增加的顺序给每个 Paxos 写操作分配时间戳，即使在跨越多个领导者时也是如此。一个单个的领导者副本，可以很容易地以单调增加的方式分配时间戳。在多个领导者之间就会强制实现彼此隔离的不连 贯:一个领导者必须只能分配属于它自己租约时间区间内的时间戳。要注意到，一旦一个时间戳 S 被分配，$S_{max}$就会被增加到 s，从而保证彼此隔离性(不连贯性)。

  • $Si$：一个读写事务的时间戳，当$S_i$被分配，$S{max}$就会增长到S
  • $T_i$：表示一个事务
  • $e_i$：代表一个事务的一些事件如开始或结束
  • $e_i^{server}$ ：表示写事务$T_i$的Commit请求到达Coordinator的时间
  • $t_{abs}$：一个时间的绝对时间

External consistency -> 不变性(invariant)：如果事务T2开始发生在T1提交事务之前，T2的时间戳就必须大于T1的提交事务的时间戳：由tabs($e_1^{commit}$) < tabs($e_2^{start}$) 可得 $S_1$ < $S_2$

Start：为一个事务 $T_i$担任协调者的领导者分配一个提交时间戳 $s_i$，不会小于 TT.now().latest 的值，TT.now().latest的值是在$e_i^{server}$事件之后计算得到的。要注意，担任参与者的领导者， 在这里不起作用。第 4.2.1 节描述了这些担任参与者的领导者是如何参与下一条规则的实现的。

Commit Wait：担任协调者的领导者，必须确保客户端不能看到任何被$T_i$提交的数据，直到 TT.after( $s_i$)为真。提交等待，就是要确保 $s_i$ 会比$T_i$的绝对提交时间小。Commit Wait 的证明如下图所示(只针对于R/W 事物)

  • commit wait：T1的时间戳小于其commit提交开始的绝对时间
  • assumption：T2的开始时间大于T1 commit的事件的事件
  • causality： T2开始的时间小于或等于其commit消息到coordinator的时间
  • start：commit消息到达coordinator的时间小于等于T2的时间戳则事物开始
  • transitivity：可以得到s1发生在s2之前

detail(论文内容—-了解)

​ Spanner在2PC开始之前读操作将会发生在transaction中被Client缓存，这样的话读操作就不会看见同一事务中写入的影响了

读写操作的实现细节
读操作在读写事务中使用wound-wait方法去避免死锁。Client发起读操作到合适Paxos Group的leader副本，获取读锁并且读取最近的数据，在客户端事务存活的时候会不断的向leader发心跳，防止超时。当客户端完成了所有的读操作，并且缓存了所有的写操作，就开始了两阶段提交。客户端选择一个coordinator group，并给每一个leader发送coordinator的id和缓存的写数据。(由客户端驱动二段提交避免两次广域的链接)

写操作开始
non-coordinator-leader首先会获取一个写锁，选择一个prepare时间戳大于之前事务已经分配时间戳的，通过Paxos记录prepare日志。每一个Participant的都要给coordinator发送他自己prepare的那个时间戳。

​ coordinator leader首先获得写锁但是需要跳过Prepare阶段，在收到(hearing,应该是类似与心跳的机制)所有Participant的Prepare消息后，它需要准备一个时间戳给整个事务，并且commit timestamp S必须大于或等于所有的prepare的时间戳(满足4.1.3中的限制)，大于TT.now().lastest，同一时间coordinator收到commit消息(Participant回复Prepare消息是commit/abort形式)并且大于leader分配给之前事务的时间戳

​ 在coordinator的副本apply commit的日志记录之前，为了遵循commit-wait规则coordinator leader需要等待TT.after(S)。因为coordinator leader需拿着S基于TT.now().lastest,并且。在commit-wait之后coordinator leader会commit的时间戳发送给client和所有Participant leader

只读事务:高性能读

  • 快速的读从本地的(邻近的)分片中
  • 不需要二段锁
  • 不需要二段提交

Corretness

Serializeble: ${R/W}_1$（T1） R/O ${R/W}_2$ （T2） R/W

External consistency(外部一致性)：Serializable+Real time

与线性一致性相似只不过Extenal consisitency是==事务级别的属性==

示例：下一个事务必须看见上一个事务的写入

  1. 如果事务T1再另一个事务T2开始之前提交, 则T1提交的时间戳会小于T2提交的时间戳
  2. 如果T1< T2 ，则T2 必须看见T1的写入

Bad Plan 只读操作读取最新提交的值

由于R/O操作是不加锁的，T3在只读操作时Ry会读取到T2提交的值，因此违背了事务的隔离性也不是串行化。

R/O with Snapshot isolation(只读事务快照隔离)

  1. 分配时间戳给事务:
    • R/W: commit 提交开始(coordinator leader分配)
    • R/O: Start 事务开始(paxos leader分配)
  2. 执行事务按照时间戳的顺序
  3. 每个副本的数据存储都需要有时间戳作为版本号(MVCC,multiple version concurrent control)

In both Bigtable and Spanner, we designed for long-lived transactions (for example, for report generation, which might take on the order of minutes), which perform poorly under optimistic concurrency control in the presence of conflicts

​ 论文中所讲到Spanner在事务(实际上是只读事务，读写事务还是需要加锁)上使用了乐观并发控制，对于只读事务我们是不加锁的，因此对于只读事务我们使用乐观并发控制。

PS: 在FaRM论文中实现了对与读写事务的OCC，对于读操作是不加锁的

DDIA中说到：Serilaizability + Snapshot isolation = ==Optimistic concurrent control==

​ 如下图：T1提交的时间戳为@10，T2提交的时间戳为@20，T3只读事务开始的时间戳为@15，读取y值，会按照时间戳的顺序，因此读取y值会现读@15以前的数据，满足了快照隔离性与可串行性

R/O from Local Replica(non-Leader of Paxos)

问题：从当地副本进行只读事务，有可能只读事务之前写入还没有同步复制到该副本。例如：副本中没有W@10的操作

解决方案

  • Saft Time ：所有副本中会跟踪这个$t{safe}$值是所有副本中最大的时间戳，以此来保证副本是最新的。若读操作时间戳为@t,一个副本需要满足t<=$t{safe}$ ,才能进行读写。
  • Paxos按照时间戳的顺序发送写操作给副本
  • 在Rx@15执行前，需要等待大于@15的时间戳写入(与no-op操作道理是一样的)
  • 等待prepared但是未commit的事务执行

Clock must be perfect

  • 对只读事务很重要

  • 只读事务的时间戳过大 => 等待时间过长

  • 只读事务的时间戳过小 => 分配给T3更小的时间戳例如为5

1
2
3
4
5
Example of problem if r/o xaction's TS is too small:
  r/w T1 @  0: Wx1 C
  r/w T2 @ 10:         Wx2 C
  r/o T3 @  5:                   Rx?
(C for commit)

根据上述情形我们只会看见T1@0写入的x=1的值，但是实际上T3开始在T2提交过后，根据external consistency：T3必须看见T2的写入(x=2)。该问题就是不正确时钟导致的分配时间戳错误的问题,

下述方案中将会解决不正确时钟导致时间戳过小的问题

Timestamp are interval

如何保证R/O Txn不会的时间戳不会太小导致读写错误?

4.12节两个规则:

  • Start rule:
    事务的时间戳==TS = TT.now().latest==
    对于只读事务来说时间戳TS就是开始时间
    对于读写事务来说时间戳TS就是事务提交开始(commit begin)的时间，也就是prepared完成时间。
  • Commit wait, for r/w xaction:
    在完成提交前, 延迟直到TS < TS.now().earliest，保证该时间戳已经过去，因此只读操作永远不会选择在commit事务开始之前的时间戳。

update example with interval

该方案是T1提交然后T2开始，T2必须看见T1的写入，需要TS1 < TS2

1
2
3
4
5
6
  r/w T0 @  1: Wx1 C
                   |1-----------10| |11--------------20|
  r/w T1 @ 10:         Wx2 P          C
                                 |10--------12|
  r/o T2 @ 12:                           Rx?
(P for T1's Prepare, C for T1 finishing Commit)

在P中T2选择了TS2 = TT.now().lastest = 10，Commit-Wait确保C发生在TS2之后(@10过去)，C开始读取时钟获得间隔为11-20 (CommitWait TS.now().earliest =11 >10)。

T3开始在C之后通过Commit-wait规则我们已经直到@10这个真实时间已经过去(assumption条件)，因此T3在@10之后，T2选择TS3=TT.now().latest=12,这个值是在当前时间之后所以是在@10之后,我们将会读到T2写入的值。

为什么当T2在提交时，T3并发执行能够获得会得到T2的值? 因为根据lab3中只有committed的log才会应用(applied)到状态机，从而修改数据库的值。如果在处理只读事务T3时，并状态机没有应用T2@10写入的数据，会导致T3读取不到T2的值。

我的猜想是saft time的机制解决该问题，等待大于@12的值写入数据库之后才能处理只读。因为我们已经分配了为@12的时间戳给了只读事务T3，执行顺序也不会出错，现在就是保证replica中一定由@10的写入。

Commit-Wait的规则是保证序列化与时间戳的正确性。

该例子只是解释了commit-wait+True Time的机制可以防止时钟的错误导致违背外部一致性，因此是否能够读写的T2的写入我想是必然的(因为读取不到T1的写入也违背外部一致性)，但是如何解决T2事务commit与T3并发处理的机制，还是取决于设计者。

最后可得${TS}_3$>${TS}_2$,因此T3的可以读到T2写入的X的值

Why this provides external consistency for r/o transactions:
Given that T1 finishes before T2 starts.Commit wait means TS1 is guaranteed to be in the past. TS2 = TT.now().latest is guaranteed to be >= correct time thus >= TS of any previous committed transaction (due to its commit wait)

detail

分配时间戳需要参与到读事务的Paxos groups的协商，这样的话，Spanner需要一个Scope的表示每一个只读操作，可以描述整个读事务的键(PS：应该不需要coordinator的参加)

single Paxos：scop的值只被一个Paxos Group提供，client提交只读事务到leader。leader分配一个$S{read}$的时间戳并执行读操作。LastTS()是Paxos Group最后一次comitted的读操作，如果没有任何的已经准备的事务，$S{read}$=LastTS()满足了external-consistency:事务将会看见最后一次写入的结果，因此只读事务将会安排到之后一次提交写事务完成之后

multiple Paxos：拥有多个的选项，最复杂的选项是所有groups的leader协商完基于LastTS()的$S{read}$，一个更简单的选着是clent避免协商的回合，当满足$S{read}$ = TT.now().lastest。所有的读操作将会发送到up-to-date的副本

discussion

  • R/W Txn => 2PC + 2PL
  • R/O Txn => Snapshot isolation + serializablity
  • extenal consistency => timestamp order + time interval

FQA

https://pdos.csail.mit.edu/6.824/papers/spanner-faq.txt

Q: 原子时钟是什么?

A: 一个非常稳定的振荡器。有两种主要的技术被称为“原子钟”:铷钟和铯钟。两者都利用了外层电子状态的变化，这涉及到特定的能量量子和波长。人们可以通过观察电子的兴奋程度来精确地将信号发生器调节到那个波长。原子钟只是时钟的振荡器部分:它产生一个频率，使时钟以正确的频率滴答作响，但它自己不知道它是什么时间。为了提供时间，原子钟最初必须与时间同步，通常是通过GPS(它本身是由一堆原子钟提供时间的)。

Q: Spanner使用什么种类的原子时钟?

A: 遗憾的是，论文没有说明。铷时钟通常是几千美元(e.g. https://thinksrs.com/products/fs725.html)。铷时钟可能每周漂移几微秒，所以每隔一段时间就需要重新同步到UTC(通常是通过GPS)。铯钟的价格大概是5万美元;HP 5071A就是一个很好的例子。铯钟不会漂移。当然，任何一个时钟都可能发生故障或电源故障，所以即使有完美的铯时钟，你仍然需要多个铯时钟，并能够同步到UTC。我猜，基于价格，Spanner使用的是与GPS接收器同步的铷时钟。

Q: TrueTime如何以一种保证包含正确时间的方式选择间隔?

A: 这里有一个简单的例子来说明它所使用的推理方法。

假设主时间服务器S1拥有正确的时间(来自GPS或原子钟)。S2向S1发送请求，询问时间，并得到响应。响应显示“10:00:00 AM”，它在S2发送请求后两秒到达(可以合理地假设S2可以计算事情所花费的时间，即使它不知道绝对时间)。由于整个请求/响应花费了两秒，S2可以推断网络可能将请求延迟了两秒;或者将响应延迟两秒;但仅此而已。因此S2可以得出结论，在它接收到响应的那一刻，正确的时间必须在09:59:58和10:00:02之间。

Q: 外部一致性与线性一致性和序列化有什么关系?

A: 外部一致性似乎等同于线性化，但应用于整个事务，而不是单个的读写。外部一致性似乎也等同于严格的串行性，这是添加了等效串行顺序必须服从实时顺序的约束的串行性。关键属性是，如果事务T1完成，然后(随后实时)事务T2开始，T2必须看到T1的写入。

Q: 为什么外部一致性是可取的?

A: 假设哈特谢普苏特通过圣何塞数据中心的网络服务器修改了她的工作组共享的一个帐户的密码。她低声说把新密码隔着隔间告诉了她的同事卡桑德拉。卡桑德拉通过位于圣马特奥的另一个数据中心的网络服务器登录了这个账户。外部一致性保证Cassandra将观察到密码的更改，而不是，例如，看到一个陈旧的副本。

Q: 云Spanner使用Raft而不是Paxos?

A: 是的。在这篇论文的层面上没有区别。在Spanner构建的时候，Raft还不存在，谷歌已经有了一个调优的可靠的Paxos实现。看看Chandra等人的论文Paxos Made Live。

Q: Spanner的Commit Wait有什么目的?

A: 提交等待确保读/写事务在其时间戳中保证已经过时才完成。这意味着在读/写事务完成后启动的只读事务保证具有更高的时间戳，从而可以看到读/写事务的写操作。这有助于实现外部一致性的保证:如果T1在T2开始之前完成，T2将以相同的串行顺序在T1之后完成(即T2将看到T1的写入)。

Q: 什么地方使用Spanner?

A: 据说有数百个谷歌服务依赖于Spanner。本文介绍了谷歌广告系统对其的使用。谷歌的Zanzibar授权系统使用Spanner。它以云Spanner的形式提供给谷歌的云客户。CockroachDB开源数据库是基于Spanner设计的。

参考

  1. Spanner 论文笔记 | Life is magic. Coding is art.
  2. spanner论文
  3. MIT6.824 Spanner讲义