光与影的个人博客

NEUCoder

0%

Spanner：“真”分布式数据库

发表于 更新于 分类于 ，

Spanner：“真”分布式数据库

Spanner: Google’s Globally Distributed Database

Spanner作为Google开发的全球分布式数据系统，具备外部一致性、支持分布式事务、多副本容错等特性，相较于Aurora，更具“分布式”特征。

从何而来？

论文的intro介绍Spanner是从类似于MegaStore的基于BigTable的kv存储系统演化而来的，MegaStore虽然能够很好得解决大部分客户的数据存储需求，但还存在一部分问题

  1. 对于关系模型的支持较差，难以支持复杂的、经常变化的模型
  2. 无法在使用大范围副本的同时保证强一致性，并且支持分布式事务

针对以上问题，一个支持更强关系模式的多时间版本的数据库-Spanner诞生了。

基本架构与存储设计

类似于Aurora,Spanner同样采用了多数据中心+多server的架构模式，一个Spanner部署称为一个universe，一个universe跨越不同的数据中心(Zone)，每个Zone内部有多个span server，其中架构中不同职责角色如下图

  • universe maseter：管理所有的zone信息
  • palcament driver：负责跨zone的数据移动
  • zone master：管理当前Zone的所有span server
  • location proxy：通知客户端访问数据所在的spanserver位置
  • span server：存储并为客户端提供数据

每个span server的内部组成如下图所示，自下而上进行分析：

  • 底层数据存储在Colossus（基于GFS改进的文件系统）上

  • 底层数据以类似于bigtable中tablet的数据结构为单位进行存储

  • 每个server存储100-1000个tablet，每个tablet实现一个基于Paxos的状态机，用来维持副本的一致性，一个tablet的所有副本组成一个Paxos Group（意味着同步单位为tablet）

  • 每个span server维护一个lock table，维护基于两阶段锁实现的并发控制锁信息

  • 对于每个Paxos Group中被选为leader的span server，在lock table上层同时会实现一个transaction manager，用来协调和管理分布式事务

数据模型

Spanner的数据库模型来自于BigTable的数据模型，区别关系型数据模型，论文中称为Directory Table（directory-bucketed key-value mappings），一种类似于关系模型的kv存储模型

  • Directory是一系列key的集合（bulk），是系统放置和同步备份的基本单位
  • 每个table的列为key，行为key对应value(这点是关系模型的特征)，每个key必须定义name
  • 每个表由主键+非主键定义，一张表可以理解为是主键->非主键的映射关系(这点是kv模型的特征)

如下图所示，创建了Users和Albums表，其中Albums表是Users表的子表

  • 从图中可知，表项按照类似目录的形式进行交错存储
  • 交错存储考虑到了不同表之间关系，在分布式存储环境下访问具备locality性质（我理解的是通常有关系的表要一起访问，不如就交错存储在一起，论文中一部分出发点是为了magastore对于跨行事务支持较差的问题）

分布式事务实现

Spanner中最难理解的一部分内容就在这一点，通过TrueTime API+分布式锁+Paxios的方式实现了满足强一致性的分布式事务支持，其中设计细节和实现细节较多，理解不到位，仅仅整理一下理解到的内容。

True Time API

Spanner通过True Time API为分布式系统提供全局时间戳，在全局时间戳的基础上实现了分布式事务的线性一致性（linearizability）。其中True Time API提供如下图的几个接口：

  1. TT.now()：获取一个当前的时间范围，保证当前时间一定在范围内
  2. TT.after(t)：判断时间t是否已经过去
  3. TT.before(t)：判断时间t是否还未到来

分布式事务

Spanner分布式事务基于两阶段提交的思想，并结合全局时间戳分配+锁实现分布式事务的并发控制，基本的阶段提交过程如下：

  1. 首先由客户端选择一个Coordinator Group(主块)，将提交信息(以及选择的Coordinator Group)和写入内容发送给所有的Participant Group中的leader（简单描述，首先选一个主group，然后告诉所有group我要提交了，且选的主group是他）
  2. 所有的non-coordinator-participant leader首先获取写锁，并生成一个大于先前所有事务时间戳的prepare timestamp，写入到Paxios日志中后，通知coordinator-participant leader。coordinator-participant leader同时也要获得写锁，但是不生成prepare timestamp
  3. 由coordinator-participant leader根据接收到的prepare timestamp，确定一个commit timestamp后，将commit信息写入Paxios日志中
    • 该commit timestamp确保大于所有的准备时间戳且大于coordinator-participant leader收到客户端发送的提交信息时TT.now().latest时间（保证事务时间戳单增，且事务开始时间一定大于事务发起时间）
  4. coordinator-participant leader等待直到TT.after(commit timestamp)为true后，发送commit信息给所有的non-coordinator-participant leader，执行提交操作，并将提交信息记录到Paxios日志中，释放锁资源

上述描述过于复杂，从两阶段提交的角度简单理解为：

  1. 准备阶段：主leader联系所有的协作leader，准备提交事务，获取所有的准备时间戳
  2. 提交阶段：主leader确定提交时间戳后，等到时间过了确定的时间戳后，发送提交信息，完成提交

考虑时间戳的两阶段提交

相较于普通的两阶段提交，Spanner的实现中考虑了大量的时间戳分配关系，通过时间戳的分配，保证性质：若事务T2开始于T1提交以后，则其提交时间戳必须小于T1提交时间戳，该性质由以下两个性质保证

  1. start：事务开始时间戳不会小于事务到达系统时调用TT.now().latest的时间（事务打上开始时间戳时，对应时间保证已经过去）
  2. commit wait：事务的真正提交（或者说提交结果为客户可见）的时间为TT.after(事务结束时间戳)为true以后（事务真实提交时，保证提交时间戳对应的真实事件已经过去）
  • “已经过去”指的是TT.after(t)为True

简单理解就是

  1. start性质保证：事物的提交时间戳不会早于开始时间戳
  2. commit wait性质保证：后续发生事务的开始时间戳不可能小于用户已将看到提交事务的提交的时间戳

通过以上两个执行保证了外部一致性

只读事务的一致性保证

只读事务保证一致性实际上就是保证在某个时间点上的读读到了当前时间点的最新数据，在Spanner中这一点同样是通过时间戳实现，基本思路如下：

  1. 为只读事务分配时间戳（快照读相当于自带时间戳的只读事务）：若只读事务只涉及一个Paxios Group，则直接由Group leader为其分配时间戳；涉及多个Paxios Group，直接将时间戳设置为最新即TT.now().latest
  2. 根据时间戳查找对应新旧程度的副本，保证读取副本的最新时间戳($t_{safe}$)大于等于当前时间戳（如果没有就需要阻塞更新副本）

由于以上根据时间戳进行读的特性，RO事务不需要上锁（lock-free），这极大的降低了只读事务的处理速度，同时避免了只读事务影响其他写事务的进行

其他实现细节

选主过程中的时间戳分配问题

每个Paxios leader带有一个超时时长为10s的lease，由于leader需要维护大量的状态信息（锁表、时间戳等），leader短时间交换的成本得不偿失，Spanner设计的Paxios leader机制在我看来更像是一个长期leader，可通过以下两种方式延长lease:

  1. 每次执行写入事务时，延长lease
  2. 在lease快过期时，leader主动向其他server发送请求延长lease

由于每个leader维护一个当前最大时间戳，在leader切换时Spanner保证新leader的时间戳与此时间戳重叠

  • 老Leader在退位之前，必须等待TT.after(最大时间戳)为True，即等到True Time Api不会生成小于等于老Leader维护时间戳的时候，老Leader再进行退位操作

Spanner vs Aurora vs Frangampani

Spanner最难理解一点是通过True Time API实现的外部一致性，在于Aurora对比思考过程中，发现两个系统均实现了强一致性保证，可Aurora并没有用到Spanner用到的True TIme API也没用到分布式事务涉及到的两阶段提交、分布式锁，这点让我想了很久才明白具体区别点在哪。

首先还是要明白Linearizability和 Serializability的区别与联系（已经看了多少次了，总是忘记）

  • Linearizability（线性一致性）：分布式系统中的概念，强调的是能为分布式系统中的发生事务安排全局认可的一个合理的顺序，因为分布式系统并没有类似单机系统全局时钟等的决定发生在不同机器上的事务的顺序，对应分布式系统CAP中的C。
  • Serializability（可序列化）：单机系统中的概念，指的是一系列并发事务之间通过并发控制，使得并发的事务按照一定的顺序（这个顺序是随机的，却决于锁和事务实现机制），执行结果满足数据库约束。

为什么分布式系统中一点要确定一个合理的执行顺序？分布式系统中如果没有全局顺序，不同机器副本上由于网络延迟、宕机等问题，会导致不同副本上操作执行顺序不一致，访问时可能看到不一致的结果（看到过期数据、看到错误数据等）。

通过上述定义，我们可以明白两个性质实际上是两个不同的问题，同样也对应着不同的解决方案

  1. Linearizability（线性一致性）：通过Spanner类似的全局时钟或者Aurora类似的自增日志号，实现分布式事务操作顺序的判断
  2. Serializability（可序列化）：单机数据库往往通过锁机制实现并发控制，从而实现一定程度的可序列化

当单机数据库迁移到分布式环境中时，需要解决上述两个问题

  1. spanner：采用了 全局时钟 + 分布式锁实现
  2. Aurora：采用全局自增编号解决了Linearizability问题，但是并没有其他机制实现并发控制问题，这是为什么？
  3. Frangapani：采用了分布式锁实现解决了并发控制问题，但是没有机制实现Linearizability的问题，这是为什么？

原因就在于:

  1. Aurora相较于Spanner采用的“伪分布式”，写操作只通过一个server执行，通过log自增即解决了并发控制的问题；
  2. Frangapani同样是“伪分布式”，虽然写可以分布于不同的server，但是底层存储抽象相当于单机磁盘存储，不涉及多副本同步，所以只控制并发即可
  3. Spaner的写操作分布于不同的机器之上，是真“分布式”，即“写分布”+“存储分布”，所以即需要分布式控制也需要单机并发控制。

全局顺序 vs 并发控制

通过上面总结我们可以得出两种一致性的区别实际上就是全局顺序和并发控制的区别

  • 相同点：两者的相同点均是为了确定一系列事务的发生顺序
  • 不同点：全局顺序是为了让分布式环境中不同副本均认可事务的发生顺序（认可的顺序不一定是真正的发生顺序，因为每个副本的时钟不可能同步），并发控制是为了让一系列有“同时发生”的事务按照一定的顺序执行

其中如果不需要多个副本认可即不需要全局顺序（Frangapani），如果通过全局顺序能够间接实现并发控制（Aurora）即不需要采用类似锁的机制进行并发控制，这两个系统都通过部分“非分布式”降低了所谓的一致性实现难度

总结

数据库知识对于目前阶段的我来说还是有点心有余而力不足，尽力而为。

参考

  1. wikipedia Serializability
  2. 知乎：Transaction management：可串行性（serializability）