Spanner:TrueTime 和外部一致性

TrueTime 是一款高度可用的分布式时钟,面向所有 Google 服务器上的应用提供 1。TrueTime 使应用能够生成单调递增的时间戳:应用可以计算一个时间戳 T,如果在 T 开始生成之前已完成生成 T',那么时间戳 T 一定会大于任何时间戳 T'。这一保证适用于所有服务器和所有时间戳。

Spanner 使用 TrueTime 的这一功能将时间戳分配给 交易。具体而言,每个事务都分配有一个时间戳, 反映了 Spanner 认为其 错误。由于 Spanner 使用多版本并发控制, 借助时间戳的排序保证,Spanner 的客户端能够 在整个数据库内(即使跨多个 Cloud 区域)。

外部一致性

Spanner 为客户端提供最严格的并发控制 这称为外部交易保证 一致性2。在外部一致性下,系统的行为 即使所有事务都按顺序执行 实际上可能在多个服务器上 数据中心)以实现更高的性能和可用性。另外,如果一个事务在另一个事务开始提交之前完成,则系统保证客户端永远不会看到这样一种状态:即包含第二个事务的效果,但不包括第一个事务的效果。直观地说,Spanner 是 从语义上很难与单机数据库区分开来。尽管如此, Spanner 让应用能够 与提供较弱保证(反过来 )。例如,支持快照的数据库 Spanner 允许写入操作继续进行,而不会被 只读事务,但不会出现快照 实现隔离。

外部一致性大大简化了应用开发。例如: 假设您在 Spanner 上创建了一个银行应用和一个 的客户最开始是支票账户 500 元, 储蓄账户。然后,您的应用开始执行一个工作流:首先提交事务 T1,将 200 美元存入储蓄账户;然后发出第二个事务 T 2,从支票账户中扣减 150 美元。此外,假设在一天结束时,一个账户的负余额将自动从其他账户进行补偿,并且如果在当天的任何时间,客户的所有账户的总余额为负值,则客户会受到处罚。外部一致性可保证,由于 T2 是在 T1 完成后开始提交,则数据库的所有读取方将观察到存款 T1 发生在扣款 T2 之前。换句话说,外部一致性可保证没有人会看到 T2 发生在 T1 之前这种状态;换言之,扣款不会导致资金不足造成的处罚。

使用单版本存储和严格两阶段锁定的传统数据库具有外部一致性。不幸的是,在此类系统中,每当您的应用想要读取最新数据(我们称之为“强读”)时,系统都会获取对数据的读取锁定,从而阻止写入到正在读取的数据。

时间戳和多版本并发控制 (MVCC)

Spanner 及其他许多数据库系统在不阻止写入的情况下读取 保留多个不可变的数据版本(通常称为多版本并发) 控制)。写入会创建一个新的不可变版本,其时间戳是写入事务的时间戳。某个时间戳的“快照读取”将返回该时间戳之前最新版本的值,不需要阻止写入。因此,应务必让为版本分配的时间戳与观察到的事务提交顺序保持一致。我们将这种特性称为“适当的时间戳”。请注意,存在适当的时间戳等同于外部一致性。

为什么适当的时间戳非常重要呢?回顾一下上一节中的银行业务示例。如果没有适当的时间戳,系统为 T2 分配的时间戳可能早于为 T1 分配的时间戳(例如,如果假定的系统中使用的是本地时钟而不是 TrueTime,并且处理 T2 的服务器的时钟稍微延迟)。然后,即使在开始扣款之前,客户已看到存款完成,快照读取也可以反映从 T2 扣款,而不是存款 T1

实现适当的时间戳对于单机数据库来说轻而易举(例如,您可以从全局单调增加的计数器分配时间戳)。在 Spanner 等广泛分布式系统上实现该目标, 而世界各地的哪些服务器需要分配时间戳则远远超出 难以高效完成。

Spanner 依赖 TrueTime 生成单调递增 时间戳。Spanner 以两种方式使用这些时间戳。首先,它将它们用作写入事务的适当时间戳,而不需要进行全局通信。其次,它将它们用作强读的时间戳,这使强读可以在一轮通信中执行,即使强读跨越多个服务器也是如此。

常见问题解答

Spanner 提供哪些一致性保证?

Spanner 提供外部一致性,这是事务处理系统最严格的一致性特性。Spanner 中的所有事务 而不仅仅是某个分区内的那些属性。外部 一致性表明,Spanner 以特定方式执行事务, 与按顺序执行事务的系统难以区分, 而且,该序列顺序与 可以观察到事务的提交。由于为事务生成的时间戳与连续顺序相对应,因此,如果任何客户端看到事务 T2 在另一个事务 T1 完成后开始提交,系统将为 T2 分配一个高于 T1 时间戳的时间戳。

Spanner 是否提供可线性化?

是。事实上,Spanner 提供外部一致性, 因为可线性化并无说明任何价值 事务行为可线性化是支持原子读取和写入操作的并发对象的一个特性。在数据库中,“对象”通常是单行甚至单个单元格。外部一致性是事务处理系统的一个特性,其中,客户端会动态地合成任意对象上包含多个读写操作的事务。可线性化可被视为外部一致性的一个特例,其中,事务只能包含单个对象上的单个读取或写入操作。

Spanner 是否提供可序列化?

是。事实上,Spanner 提供外部一致性,这是更严格的 属性而非可序列化。如果事务处理系统执行事务的方式是通过按顺序执行事务的系统无法分辨的,则它是可序列化的。Spanner 还保证 序列顺序与交易的顺序一致 被观察到提交。

再回顾一下前面使用的银行业务示例。在提供可序列化而非外部一致性的系统中,即使客户按顺序先后执行 T1 和 T2,系统也能重新对它们进行排序,这可能会导致扣款引发资金不足处罚。

Spanner 是否提供强一致性?

是。事实上,Spanner 提供外部一致性, 而不是强一致性。Spanner 中的默认读取模式是 “strong”:保证可观察到所有交易的效果 与哪个副本无关 收到读取操作的通知。

高度一致性和外部一致性有什么区别?

如果复制对象是可线性化的,则复制协议具有“高度一致性”。与可线性化一样,“高度一致性”比“外部一致性”弱,因为它没有对事务行为做任何说明。

Spanner 是否提供最终(或延迟)一致性?

Spanner 提供外部一致性,这是一种更强大的特性, 比最终一致性更高最终一致性不能保证获得较高性能。最终一致性会出现问题,因为它意味着读取方可以观察到数据库处于某种状态,但实际上数据库从未处于该状态(例如,读取方可能会观察到一种状态表明事务 B 已提交,而事务 A 未提交,即使 A 是在 B 之前发生的也是如此)。Spanner 提供“过时读取”,从而提供类似的 最终一致性带来性能优势,但一致性更高 保证。过时读取会从“旧”状态返回数据时间戳,不能 块写入,因为以前版本的数据是不可变的。

深入阅读

备注

  • 1J.C.Corbett, J.Dean, M.Epstein, A.Fikes, C.Frost, J.Furman, S.Ghemawat, A.Gubarev, C.Heiser, P.Hochschild, W.Hsieh, S.Kanthak, E.Kogan, H.Li, A.Lloyd, S.Melnik, D.Mwaura, D.Nagle, S.Quinlan, R.Rao, L.Rolig, Y.Saito, M.Szymaniak, C.Taylor, R.Wang,和 D.Woodford.Spanner:Google 的全球分布式数据库。第十届 USENIX 操作系统设计与实现专题论文集 (OSDI 12) 第 261-264 页,加利福尼亚州好莱坞,2012 年 10 月。
  • 2Gifford, D. K.K. 《分散式计算机系统中的信息存储》。博士论文,斯坦福大学,1981 年。