Google Spanner 事务在存储层的实现

Google Spanner 的论文于 2012 年发表，至今仍是世界上先进的、规模大的分布式数据库架构，毫无疑问对现代数据库设计产生了深远影响。其大的亮点莫过于 TrueTime API，凭借原子钟和 GPS 的加持在全球范围实现了单调递增的时间戳，从而达到外部一致性；其次则是验证了分布式 MVCC 的高性能实现，为业界指明一条发展方向。

不过，论文对存储层实现只作了模糊的阐述：原文中说到 Tablet 的实现类似于 Bigtable（复用了不少 Bigtable 的代码），底层基于 Colossus —— 继承 GFS 的下一代分布式文件系统。可以确定的一点是，存储层要为 Read-Only 和 Read-Write 事务提供支持：

• Read-Only 事务: 读取新或给定时间戳  的快照，也就是 Snapshot Read
• Read-Write 事务：读取事务开始时间戳  的快照，而写入操作在提交时间戳  生效

本文从 Spanner 本身设计出发，并结合开源实现 TiKV 和 CockroachDB，谈谈如何为 Spanner 设计一个存储层。本文假设读者阅读过原论文 Spanner: Google’s Globally-Distributed Database。

数据的 KV 表示

Spanner 对外提供（半）关系型数据模型：每张表定义了一个或多个主键列，以及其他的非主键列。这和我们熟知的 SQL 关系型模型几乎一摸一样，的不同是 schema 定义中必须含有主键。

Spanner 早期的设计中大量复用了 BigTable（开源实现即 HBase）的代码。回忆一下 BigTable 的数据模型：每一条数据包含 (Key, Column, Timestamp) 三个维度，满足我们需要的 MVCC 特性。从 BigTable 开始的确是个不错的选择。

不过，从性能上考虑 Bigtable 毕竟是分布式的 KV 存储系统，在存储这一层我们大可不用搞的那么复杂，分布式的问题例如 Scale-out 和 Replication 应当留给上层的 Sharding 机制和 Paxos 解决。事实上，一个单机的存储引擎足矣。

Google 自家的 LSM-Tree + SSTable 的实现 LevelDB 是个可选项。它接口非常简单，是一个标准的 KV 存储，可以方便的在它基础上实现我们想要的数据模型。主要接口其实就是两个：

• Write(WriteBatch *) 原子地写入一个 WriteBatch，包含一组 Put(K, V) 和 Delete(K) 操作
• Iterator() 及 Seek() 从指定位置开始顺序扫描读取 (K, V) 数据

如何实现列和时间戳呢？举个例子，有如下数据表 Accounts。在数据库中，主键索引通常也是的聚簇索引，它存放了真实的数据，而我们暂时不考虑其他索引。

| UserID (PK) | Balance | LastModified |
|-------------|---------|--------------|
| Alice       | 20      | 2018-02-20   |
| Bob         | 10      | 2018-02-01   |