Cloud Spanner:TrueTime 和外部一致性

TrueTime 给 Cloud Spanner 带来的好处

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

Cloud Spanner 使用 TrueTime 的这一特性为事务分配时间戳。具体而言,每个事务都分配有一个时间戳,它反映 Cloud Spanner 认为事务发生的时间。由于 Cloud Spanner 使用多版本并发控制,时间戳的排序保证使 Cloud Spanner 的客户端能够在整个数据库内(即使跨多个云端区域)执行一致的读取,而不会阻止写入。

外部一致性

Cloud Spanner 为客户端提供最严格的事务并发控制保证,称为外部一致性 2。在外部一致性下,系统的行为就好像是所有事务都按顺序执行,即使 Cloud Spanner 实际在多个服务器(可能位于多个数据中心)上运行这些事务以获得更高性能和可用性时也是如此。另外,如果一个事务在另一个事务开始提交之前完成,则系统保证客户端永远不会看到这样一种状态:即包含第二个事务的效果,但不包括第一个事务的效果。直观地说,Cloud Spanner 在语义上与单机数据库没有区别。Cloud Spanner 不仅提供如此强有力的保证,还使应用能够实现与提供较弱保证(以获得更高性能)的数据库相媲美的性能。例如,与支持快照隔离的数据库类似,Cloud Spanner 允许写入继续执行,而不会被只读事务阻止,但不会出现快照隔离允许的异常情况。

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

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

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

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

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

实现适当的时间戳对于单机数据库来说轻而易举(例如,您可以从全局单调增加的计数器分配时间戳)。在分布广泛的系统(例如 Cloud Spanner)中高效执行难得多,因为在这样的系统中,全世界的服务器都需要分配时间戳。

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

常见问题解答

Cloud Spanner 提供什么一致性保证?

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

Cloud Spanner 是否提供可线性化?

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

Cloud Spanner 是否提供可序列化?

是。事实上,Cloud Spanner 提供外部一致性,这是比可序列化更严格的特性。如果事务处理系统执行事务的方式是通过按顺序执行事务的系统无法分辨的,则它是可序列化的。Cloud Spanner 还可以确保连续顺序与观察到的事务提交顺序一致。

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

Cloud Spanner 是否提供高度一致性?

是。事实上,Cloud Spanner 提供外部一致性,这是比高度一致性更强的特性。Cloud Spanner 中读取的默认模式是“强”,这保证了它们可观察到在操作开始之前提交的所有事务的效果,这与哪个副本接收读取无关。

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

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

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

Cloud Spanner 提供外部一致性,这是比最终一致性更强的特性。最终一致性不能保证获得较高性能。最终一致性会出现问题,因为它意味着读取方可以观察到数据库处于某种状态,但实际上数据库从未处于该状态(例如,读取方可能会观察到一种状态表明事务 B 已提交,而事务 A 未提交,即使 A 是在 B 之前发生的也是如此)。Cloud 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. 《分散式计算机系统中的信息存储》。博士论文,斯坦福大学,1981 年。