Spanner - Google的全球化分布式数据库

section 1 介绍

---

优点：

高可用、可扩展、（中间态的？tmp）多版本、全分布式、同步复制、对外一致的分布式事务

应用：

F1

高可用 vs 低延迟：大多数应用使用3-5个datacenter，以获得较低延迟，可抵抗1-2个datacenter的失效

关注点：

管理复制到数据中心间的数据。同时在底层分布式系统之上提供一些数据库功能。

因为bigtable UI不够简单。megastore写吞吐低

描述：

从Bigtable类型的多版本的key-value store演变到带有中间态多版本的数据库。数据保存在半关系型的表中，可有多版本并被标上提交时的时间戳。老版本数据可通过时间戳访问，可被内部机制（他们说是cop哦-_-）垃圾回收。支持事务并提供SQL接口。

复制功能各指标可配置：

数据位置（在哪个数据中心）

读延迟（与应用的距离）

写延迟（各副本的距离）

持久性、可用性与读性能（副本数）

平衡各数据中心的资源使用（动态地、向上透明地在数据中心间迁移数据）

！对外一致的读写，各数据中心全局一致的指定时间戳的读操作

Section 2 实现

结构

universe —— zone（可理解为对应数据中心）

universemaster（1个，显示状态的终端）、placement driver（1个，自动在数据中心间迁移数据，时间大概以分钟记）

zonemaster（1个/zone，指派数据给spanserver）、location proxy（N个/zone，向client提供查询数据所在spanserver服务）、spanserver（N个/zone，向client提供数据服务）

spanserver

自下而上包含的基本组件：colossus（GFS的进化版，据说消除了单点？未考究） -> tablet（结构化的存储，大致对应bigtable的tablet） -> paxos（为支持高层的副本概念） -> replica（注意副本概念提升到了较高层）

写操作需要先在leader处初始化paxos状态，而读操作则可直接访问任意足够新的replica。

相同数据的多个replica组成一个paxos组，组里的leader需要使用lock table（2PL）和transaction manager来支持并发控制（2PC）和分布式事务。其中，当不需要同步读时（只读操作），可以绕过lock table；当事务只涉及一个paxos组时，可绕过transaction manager（不使用2PC，减轻可用性问题，因为lock table与paxos已经保证了）。当事务涉及到多个paxos组时使用，leader与其他组的leader使用2PC进行协同，此时leader也 participant leader。多个组中有一个被选作协调者coordinator，而此时的participant leader也是coordinator leader。

directory

一组带有共同前缀的连续的key的数据集。是数据部署、迁移的单位。

迁移可线完成。50MB大小的directory可在秒级迁移完。迁移时并非从头到尾使用事务，而是在迁移快完成时才使用，在事务中完成数据迁移及元数据的修改。

应用可指定的部署属性的数据粒度也是directory，属性包含两方面：副本的数量与类型、副本的位置。

以上是简化的说明，实际上，directory在过大时会拆成多个fragment，并分布在不同的paxos组中（因此可能在不同的机器上），数据迁移的实际上是fragment的迁移，而不是整个driectory。

！当directory拆成fragment以后，又回到了数据相关性问题，这个先放一下。

数据模型

很多人诟病2PC带来的性能与可用性问题。可用在性方面：下层先使用paxos与2PL，上层才使用2PC，以减轻可用性问题。性能方面：作者认为控制过度使用的事务（需要用2PC的原因）比纠结没事务要好方式的编码要好一些。

database定义在universe上，可有多个。一个database下可有多个table（带有行、列、 版本）。table要求定义一个有序（可排序？）的主键，各个table中都有主键到非主键的映射。

！数据分区后，相关性是由应用指定的。table是带有层次结构的，最上层的是directory table，下层的可以使用INTERLEAVE IN指定其属于哪个table。directory table中的每一条记录（假设其主键为K），与所有在其下table中前以K作为主键前缀的记录共同组成一个directory。

Section 3 TrueTime

定义了几个操作，跳过没细看，大致了解其使用到Marzullo算法、 GPS、原子钟

TT.now()          TTinterval: [earliest; latest]

TT.after(t)        true if t has definitely passed
TT.before(t)     true if t has definitely not arrived

！以上几个操作基于Marzullo算法，而其时间的同步则依赖于GPS和原子钟。这种TrueTime操作给出了时序表达的另一种思路，但不能忽略其使用GPS与原子钟的前提（还在整Logic time吗，看看这个）

Section 4 并发控制！

！可能是论文中直接给出最有价值的内容，或者说是我最关注的点，但要注意它的实现与TrueTime机制支持分不开。

三种类型的读写操作：读-写、只读（需要预定义）、快照读。

重试逻辑：在服务内部重试，客户端不需要再进行重试。

leader权使用租约（lease）机制传递，选举机制是quorum vote（容错性）。每次写操作成功后，各replica会自动延长lease时间，而leader则会在租约快过期时，启动新的选举。

leader权在各replica间传递时"租期不相交性"是spanner后续工作（即使事务由不同leader处理，也能保证对外的一致 性）的依赖之一（拗口-_-）。为了保证这个不相交性，当前leader在让出其leader权时，必须要等到其应用过的时间戳”毫无疑问已经过期”。 （此处leader指 participant leader）

读-写

提交使用了2PC，由应用驱动第一个phase以减少通信消耗。为了与上述的TrueTime配合来保证时序并做到对外的一致和并发控制，非 coordinator leader需要向coordinator leader确认一个prepare ts，而coordinator leader则在此基础上定出事务的commit ts。

GPS/原子钟（全局时间同步）+ marzullo算法（估算精确时间）+ lease租期不相交性（多leader）+ 多处monotonicity机制

快照读

快照读可以在任意“足够新”的replica上进行。“足够新”是指所要读的快照时间t在t_safe之内（t ≤ t_safe )，问题就转移到了t_safe上：

，由两个值中较小的一定确定。

其中，前者为replica上最后一次paxos写操作的时间。但如果最近一次写操作隔得比较久呢？更进方法是记录一个后续写事务时间的阈值 （或叫分水岭？）MinNextTS（实际上是与paxos序列ID对应的一个mapping），只要paxos安全时间不超过这个值就可以了。

而后者，则是paxos组里边，最后一个没有未提交（prepared but not committed）读写事务的时间点。由上述读写事务描述可知，事务的commit ts不小于各participant/replica的prepare ts，因此可以安全地选择prepare ts作为TM安全时间的界限。

在以上的方案下，即使读操作与当前未提交的数据没有关联，也需要等待，这是不合理的，简单的只关注与自己scope相关的那部分，具体做法就是把TM的安全时间考虑粒度切分开。

只读

首先要确定一个时间戳t_read，然后就按照快照读的方式来读取数据，所以问题转换成t_read的确定方式。

最简单的方式就是直接使用“当前时间” t.now().latest，但为了让t ≤ t_safe成立，可能需要等待。如果应用能提供读事务中所涉及的数据范围（scope，单独的事务可由spanner自行推导出 scope），spanner是否能按照scope选择一个更优的t_read？

是滴，当scope只包含一个paxos组时，t_read可以选择该组上最后一次commit write的时间戳（记为LastTS，在没有未提交事务时）。涉及多个组时，spanner则是直接使用上边的t.now().latest（也就意义 着需要等），原因是不想为了这个t_read实施一次协商（通信消耗啊）。注意到，在第一种情况下，如果最后一次commit write刚提交，那么即使读操作所涉及的数据与其无关，也需要等待，改进的方法也是切小粒度。

修改schema

在使用了TrueTime机制之后，支持原子的schema修改（事务），当机器数可能达到百万级时，这个是非常有意义的。做法就是提前注册一个t，在这个t之前的操作可以继续进行。而且由于它执行的速度较快，对其他操作的影响也较小。

改进

关于Paxos安全时间、TM安全时间和LastTS的选取的改进已经在上文提到了。

其他

benchmark、related work、future work等，没有什么太大的东西，几个 数字自己看看也就OK了（如果因为不看数字就而被以上内容忽悠，那……）。