- Introduction
- Implementation
- Spanserver Software Stack
- Directories and Placement
- Data Model
- TrueTime
- Concurrency Control
- Timestamp Management
- Paxos Leader Leases
- Assigning Timestamps to RW Transactions
- Serving Reads at a Timestamp
- Assigning Timestamps to RO Transactions
- Details
- Read-Write Transactions
- Read-Only Transactions
- Refinements
Spanner是Google的全球分布式数据库，它主要具有以下特点：
- 可细粒度动态控制数据副本的配置，包括数据的分片方式，数据的迁移等。
- 读和写操作的外部一致性
- 一个时间戳下跨数据库的全球一致性读
Spanner能提供全球范围内的有序事务提交时间戳，而这个功能基于TrueTime API及其实现。
Implementation
一个Spanner的部署被称为一个universe，其包含如下部分：
- universe master：管理和控制zone的状态和信息
- placement driver：周期性和spanservers交互，发现需要转移、更新的数据。
- 多个zone，每个zone代表了一个数据存储单元，其包含：
- zonemaster：管理当前zone的spanservers（如分配数据）
- spanserver：存储和提供数据
- local proxy：给客户端定位提供数据的spanservers
Spanserver的软件协议栈各部件功能如下：
- tablet：spanserver中的数据结构，是一个具有版本的key-value条目，其形式为(key:string, timestamp:int64) -> string。tablet的状态存储在Colossus分布式文件系统当中，并且存储于类似B+树的文件和WAL中。
- Paxos group：每个tablet运行在Paxos协议下，代表一份数据副本，Paxos协议的状态(如log等)也存储在tablet中。多个replica组成一个Paxos group，并有一个leader进行管理。
- leader的选举租约为10s。
- 写操作必须经过leader，并由Paxos保证半数复制，读操作可以直接访问最新的副本。
- leader维护lock table，用于存储如2PL的锁状态。
- leader拥有transaction manager，用于维护事务状态和事务并发控制。
- participant leader：基于transaction manager创建，用于协调跨Paxos group的事务，以完成2PC事务提交。
Spanner中定义了directory的概念，它是数据放置的最小单位：
- 每个Paxos group可拆成多个目录，每个目录由一系列共同前缀的键所对应的数据项组成（实际为将tablet进行划分）。
- directory中的所有数据都具有相同的replication configuration。
- 目录的replica在其所在的Paxos group中。
- 目录可以转移到不同的Paxos group，以调整负载，转移操作可以在执行client operations时进行（50MB转移只需要几秒）。
- Movedir background task用于在Paxos groups间转移目录。
- 若一个目录过大，会被分片到不同的Paxos group，Movedir实际上移动的时分片而不是目录。
Spanner的对外数据特征为：
- schematized semi-relational tables：每个表的行都必须有名称，可定义外键和级联的关系。
- a query language：一个查询语言（类SQL）。
- general purpose transactions：通用的事务（基于2PC+2PL）
Spanner中的Data Model实例如下所示，其结构如下：
- database由client分割成多个不同层级的hierarchy table（INTERLEAVE IN关键字）
- 每个hierarchy table的top row为directory table，并包含key K。
TrueTime的实现机制：
- 底层为GPS + atomic clock。 GPS可能会因为天线等故障出现误差，atomic clock可能会因为长时间使用导致的频率误差产生时钟漂移。
- 每个datacenter中配置有多个time master
- 一些使用GPS获取时间，一些使用atomic clock获取时间
- time master之间互相校对时间，若差距过大则会将自己驱逐出去
- 每个server中都有一个timeslave daemon
- 每个server收集time master的时间，使用类Marzullo算法同步本地server时钟。
- 考虑到延迟等影响，引入了时间误差 ϵ epsilon ϵ
基于TrueTime API实现了一个重要特性：在timestamp t时产生的读操作，会看到所有在t之前提交的事务。
Timestamp ManagementSpanner支持以下几种读写事务：
- Read-Write：使用pessimistic lock进行并发控制。
- Read-Only
- 必须声明不含写操作
- 时间戳由leader决定，无锁，可在任何足够新的副本执行
- Snapshot Read
- 可读取历史数据，无锁
- 时间由客户端决定，可以是时间戳，也可以是时间下限（由Spanner具体决定，满足条件即可）
Paxos的leader租约具有以下特点：
- leader lease的默认时间为10s
- 成功执行一次写操作会延展leader lease
- leader lease快到期前会申请延长
- leader可主动放弃该身份
- 不同leader的lease interval不同
- 假设前一个leader使用过的最大时间戳为 s m a x s_{max} smax，则下一个leader的租约起始时间必须满足 T T . a f t e r ( s m a x ) TT.after(s_{max}) TT.after(smax)。
读写事务需要依赖2PL。Spanner是用在提交事务时的Paxos写操作的时间戳作为事务时间戳。
Spanner提供了读写事务时间戳的两个保证，Paxos group内单调递增和外部一致性。
Paxos group内读写事务timestamp单调递增由以下机制保证：
- leader不同租约区间互不相交
- leader分配的时间戳只能在自己租约区间内
WR事务的外部一致性保证为：如果事务
T
2
T_2
T2发生在事务
T
1
T_1
T1提交之后，则事务
T
2
T_2
T2的提交时间戳一定大于事务
T
1
T_1
T1的提交时间戳，即
t
a
b
s
(
e
1
c
o
m
m
i
t
)
<
t
a
b
s
(
e
2
c
o
m
m
i
t
)
⇒
s
1
<
s
2
t_{abs}(e_1^{commit}) < t_{abs}(e_2^{commit}) Rightarrow s_1 < s_2
tabs(e1commit) 其中一些记号标识说明如下： WR事务的外部一致性通过以下机制保证： 证明如下： 每个replica都会维护一个
t
s
a
f
e
t_{safe}
tsafe，表示副本最近更新的最大时间戳，当读事务的时间戳为
t
t
t时，可以在满足
t
≤
t
s
a
f
e
t leq t_{safe}
t≤tsafe的副本上读取且
t
s
a
f
e
=
m
i
n
(
t
s
a
f
e
P
a
x
o
s
,
t
s
a
f
e
T
M
)
t_{safe}=min(t_{safe}^{Paxos},t_{safe}^{TM})
tsafe=min(tsafePaxos,tsafeTM)。
t
s
a
f
e
P
a
x
o
s
t_{safe}^{Paxos}
tsafePaxos为Paxos write的最近事件，
t
s
a
f
e
T
M
t_{safe}^{TM}
tsafeTM为副本对应的transaction manager维护的安全时间，其具体取值如下： 只读事务分为两个阶段进行： Spanner在执行读写事务时： Spanner中变种的2PC协议具体如下： 只读事务需要分为时间戳
s
r
e
a
d
s_{read}
sread，具体原则如下：
t
s
a
f
e
T
M
t_{safe}^{TM}
tsafeTM存在的问题：当存在一个prepared但没commit的事务，
t
s
a
f
e
t_{safe}
tsafe无法变大，会阻塞
s
r
e
a
d
>
t
s
a
f
e
s_{read}>t_{safe}
sread>tsafe的读操作，即使可能并没有冲突。 解决方案：建立一个
L
a
s
t
T
S
(
)
LastTS()
LastTS()存在的问题：当一个事务刚被提交，一个读请求时间戳必须跟在刚提交事务的后面，造成阻塞，即使读操作不会造成冲突 解决方案，建立一个
t
s
a
f
e
P
a
x
o
s
t_{safe}^{Paxos}
tsafePaxos：没有发生Paxos write时，
t
s
a
f
e
P
a
x
o
s
t_{safe}^{Paxos}
tsafePaxos无法变大，会造成读阻塞。
Assigning Timestamps to RO Transactions
Details
Read-Write Transactions
Read-Only Transactions
Refinements
解决方案：每个Paxos group leader维护一个下一个Paxos write可能会发生的最小时间戳
M
i
n
N
e
x
t
T
S
(
n
)
MinNextTS(n)
MinNextTS(n)，并令
t
s
a
f
e
P
a
x
o
s
=
M
i
n
N
e
x
t
T
S
(
n
)
−
1
t_{safe}^{Paxos}=MinNextTS(n) - 1
tsafePaxos=MinNextTS(n)−1。注意，
M
i
n
N
e
x
t
T
S
(
n
)
MinNextTS(n)
MinNextTS(n)必须在租约内，且如果
M
i
n
N
e
x
t
T
S
(
n
)
MinNextTS(n)
MinNextTS(n)超过了租约期需要先延长租约。
