System|分布式|Spanner

Spanner is Google's scalable, multi-version, globally distributed, and synchronously-replicated database.

引论

Spanner是Bigtable的魔改版，下面这张谷歌云的PPT几乎和intro一一对应。

• 针对第一个lesson，Spanner提供了全球级的分布。
• 针对第二个lesson，Spanner提供了分布式事务支持。
• 针对第三个lesson，Spanner提供了跨数据中心的同步备份。
• 针对第四个lesson，Spanner提供了基于SQL的查询语言。
• 同时Spanner也提供了优雅的Time API保证外部一致性。

有个Client库https://www.codota.com/code/java/packages/com.google.cloud.spanner

架构

部署的Spanner集群被称为Universe,由于是全球化的,谷歌仅仅拥有测试/开发+产品/产品三个Universe。Spanner由多个Zone组成，Zone是管理部署的单元，数据的备份应该在不同zone上，一个数据中心存在一个或者多个Zone。

每个Zone由zonemaster、spanserver、location proxy构成。和Bigtable类似，这里的客户端不需要为了寻址访问zonemaster。

在GFS的时候,master负责控制流和client直接交互, 后来master只负责写assignment,而读assignment由寻址服务器负责，从这里也能看出设计的scalability变化(我的垃圾系统设计则是master直接负责数据流+控制流不得不进行集群化，所以还是太年轻了)

• zonemaster - 分配数据
• spanserver - 提供数据
• location proxy - 供客户端寻址

universemaster和placement driver则属于单例，前者是整个系统的monitor，后者周期性地询问spanserver是否因为备份或者负载均衡而需要进行数据迁移。

Spanserver软件栈

文件系统升级到了论文没发的Colossus(目测未来又是篇OSDI)，存储引擎依然是之前的LSM tree。tablet的结构稍微改变了一点，没有按照行列组织。一方面是常规的键值对存储，但是增加的时间戳又更像是多版本数据库。

(key:string, timestamp:int64) → string

Paxos状态机

不同于Bigtable所保证的最终一致性，谷歌用了Paxos状态机保证强一致性

一组Paxos维护的备份称为Paxos Group

tablet的状态储存在Colossus的类似B树的文件和WAL中。备份的tablet之间通过单个Paxos状态机维护(多个太复杂，谷歌放弃了),状态机的metadata和log就放在tablet里面。因为log在tablet里面，所以每次Paxos写都需要写tablet的log和paxos的log,是谷歌的权宜之计。

谷歌的Paxos实现维护了长期leader,租期为10s。通过流水线化降低WAN时延弥补Paxos性能,但是写操作保证有序。写操作通过Paxos状态机，而读操作直接通过tablet。

Lock表

专门的锁服务器，实现key粒度的锁，因为长期存在的单leader，因此保证了效率。长期的事务通过锁来保证。但是在OCC下性能不佳，所以谷歌用时间戳来做无锁事务。

事务管理器

专门用来处理跨Group的事务,通过2PC协议维护分布式事务。paxos的leader称为participant leader，其他备份称为participant slaves。当多Group事务时，其中某个group会被选为coordinator。

leader的状态存储在Paxos Group中(用来处理2pc的单点错误问题？)

2PC

省略TrueTime不提，这里精妙的地方在于利用广播降低了时延。Client同时向所有participant发出信息告知coordinator和对应的写操作，避免传播两次。

1. Client选择事务的某个Paxos Group作为Coordinator，其他的作为Participant
2. Client发送COMMIT请求给所有的Participant和Coordinator，对于Coordinator告知所有Participant信息，而对于Participant告知Coordinator信息，同时附带所有写操作。
3. Participant获取写锁，并且log PREPARE
4. Coordinator获取写锁，跳过log PREPARE，等待所有Participant的Prepared消息
5. Coordinator收到所有Participant的Prepared消息之后，直接log COMMIT[注]，再通知所有participant commit，告知client commited。
6. Coordinator与Participant持久化输出，并释放写锁

注: 这里如果用TrueTime,需要在log COMMIT后进行Commit Wait，直到TT.after(s)，也就是在所有的group看来时间都在提交点之后，然后把时间戳s传给participant和client。

Directories and Placement

谷歌表示Directory这个名字是历史遗留问题，正确的名字叫bucket正好。Directory是一组连续的键，拥有相同的前缀，从而保证locality。(同Bigtable思想)

• Directory是数据移动的基本单元(注：实为fragment)。通过使得经常同时访问的Directory移动到同一个Paxos Group保证本地性。
• Directory是数据放置的基本单元。同Directory的数据有着相同的备份配置，管理员可以以directory为单元配置备份的数目、类型、放置地区。

Tablet有了改动，现在的key不是连续的，可以是分段的，这样可以把经常同时访问的directory放到同一个tablet，保证本地性。保证本地性不仅仅是性能优化，也规避了分布式事务的开销。

Movedir是两个事务，首先迁移数据，然后再修改metadata。没有作为单个事务的目的是为了防止阻塞持续的读以及庞大数据移动时发生的写。

论文表示上面的是简化，实际上，当dir数据过大时，会分为多个fragment，可以放在不同group中，实际上的Movedir是针对fragment的，也就是基本单元其实是fragment。

数据模型

Spanner基于schematized 半关系表,支持类SQL的查询语言和广义事务。

之所以叫半关系表，是因为表面上看起来像是行列，实际上却是仅有key。主键的值的组合作为key，而非主键的值则作为value。因此查询的时候必须带主键。

TrueTime API

谷歌说这里就简单描述下API，因为要拿TrueTime再水一篇论文(逃

区间长度是不确定性

的两倍，TrueTime保证如果此时事件发生，那么必然在这个区间内。TrueTime的底层是通过GPS和原子钟实现的,前者受卫星影响，后者自身频率有误差，因此提供两种模式。

产生于保守最坏情况的本地时钟偏差，同时取决于时间服务器的不确定性以及通信时延。在谷歌的生产环境下，它是个锯齿波,例如周期区间是30s的钟，每秒偏移200微秒，那么不确定性是0-6ms，加上1ms的通信时延影响。

并发控制

u1s1,能做TrueTime的企业应该少之又少吧,基本没法复现,一堆公式打字打不动了，干脆不写了。反正就是因为有精确的时间戳，所以事务上能够很容易看出先后关系，实现无锁事务。

These features enable, for example, the guarantee that a whole-database audit read at a timestamp t will see exactly the effects of every transaction that has committed as of t.

有兴趣去读https://zhuanlan.zhihu.com/p/47870235吧，或者直接读原文。这个是最大的创新点，但是一般的分布式系统真用不起。

Reference: Spanner: Google’s Globally-Distributed Database

Problem: 锁的性能+分布式广域时延+查询语言 +强一致性

Related work: 无查询语言，完全依赖锁，无法处理全球分布式，最终一致性

Observation: TrueTime + BroadCast 2PC + 行列转key-value的数据模型

Solution: 时间戳保证顺序，client向participant广播减少时延，Paxos状态机保证一致性

Evaluation: 无锁性能高很多，可用性比起Bigtable提升巨大

Comments: 感觉除了财大业大的那几个企业根本没法落地TrueTime