type
status
date
slug
summary
tags
category
icon
password
原文
13.1 Spanner 介绍13.2 基本布局13.3 读写事务13.4 只读事务13.5 快照隔离13.6 时间同步（Time Sync）13.7 时钟同步（Clock Sync）13.8 START、COMMIT WAIT
13.1 Spanner 介绍
今天我要讲讲 Spanner 这篇论文，为什么选这篇论文，是因为它堪称罕见范例，一种可在大范围分散数据上实现分布式事务的系统。
即数据可能散步于互联网及不同的数据中心，生产系统中几乎从未有过这种情况。当然能进行事务处理是极为理想的。
为实现容错将数据分散于整个网络也极为理想。并确保数据就近存储，让每个想使用数据的人附近都有一份数据副本。在实现这一目标的过程中至少采用了两个巧妙的办法。其一他们采用两阶段提交，但实际上他们是在 Paxos 复制参与者上运行此操作。为避免两阶段提交中崩溃协调器阻塞所有人的问题。另外一个巧妙的想法是他们通过使用同步时间来实现高效的只读事务，而且该系统实际很成功，谷歌内部众多不同服务大量使用了它。
Google 将其转换成为了一种产品，一项面向其云客户的服务，并且它还激发了一系列其他研究。以及其他系统或多或少都以这些广域事务可行的例子为参照，此外具体而言至少有一个开源系统 CockroachDB，它明确采用了许多该设计理念。
某种程度上，他们开始设计 Spanner 是因为已经有了…… 嗯，实际上。他们在谷歌内部有许多大型数据库系统，尤其是广告系统，其数据被分片存储在众多不同的 MySQL 和 Bigtable 数据库中，而且维护这种分片很麻烦，还很耗人力和时间，此外他们以前的广告数据库系统，不允许进行跨服务器的事务操作，但他们很想更广泛地分散数据以提升性能，并能对多个数据分片进行事务处理。对于其广告数据库，显然工作负载以只读事务为主，在表6 中可见，其中有数十亿笔只读事务，而读写事务仅有数百万笔，所以他们对只读事务的性能很感兴趣，这些事务仅执行读取操作。显然他们还要求强一致性尤其是特定的哪些事务，所以他们需要可串行化事务并且他们还需要外部一致性。这意味着当一个事务提交时，然后在第一个事务提交完成后，另一个事务开始，第二个事务需要看到第一个事务所做的所有修改，并且这种外部一致性在数据复制时显得很有趣。
13.2 基本布局
好的，下面我来画一个基本布局即 Spanner 使用的服务器的物理布局。它的服务器分布在多个数据中心，想必遍布全球，当然在美国境内也随处可见，每条数据都会在多个数据中心进行复制，所以示意图中得有多个数据中心，比如说有三个数据中心，实际上会有更多，然后数据会被分片也就是拆分，你可以把它想象成按键拆分，然后分布到多台服务器上。所以在这个数据中心可能有一台服务器处理以 A 开头的键，其他的则以 B 开头，以此类推，有很多服务器。
在许多服务器上进行分片存储，实际上每个数据中心或者任何一块数据，任何一个分片都会在多个数据中心复制，所有会有 A 键的另一个副本，还有 B 键等等，第二个数据中心还有一份，希望第三个数据中心也有这些数据的相同副本。
此外每个数据中心会有多个客户端或者他们是 Spanner 的客户端。
而实际上这些客户端实际上就是网页服务器，所有会有普通人坐在网页浏览器前连接到使用 Spanner 的 Google服务。他们会连接到某个数据中心的网络服务器，那就是 Spanner 客户端之一，所以它会被复制。复制由 Paxos 管理，实际上它是 Paxos 的一种变体有领导者，与我们熟悉的 Raft 非常相似。
每个Paxos 实例管理给定数据分片的所有副本，所以此数据分片的所有副本构成一个 Paxos 组，并且此数据分片的所有副本构成另一个 Paxos 组。每个 Paxos 实例都是独立的，有自己的领导者，运行自己版本的 Paxos 协议。
数据分片的原因，每个数据分片有独立 Paxos 实例是为了实现并行加速，以及大量并行吞吐量，因为有大量代表网络浏览器工作的客户端，所以通常会有大量并发请求，这就是将他们拆分能带来巨大收益的原因。分布在多个分片及多个并行运行的 Paxos 组上。
好的，你可以设想，在这些 Paxos 组中的每一个都有一个领导者，很像 Raft。所以这个分片的领导者可能是数据中心1 的副本（ 图 6 中的 DC1 中标识）,这个分片可能是数据中心2 的中的副本以此类推（图 6 DC2 中的 b）。
这意味着客户端写入，它必须将写入请求发送到要写入数据的分片的领导者，和 Raft 一样，这些 Paxos 实例，它们实际在做的是发送日志，领导者会向所有追随者复制操作日志，执行者执行该日志，该日志用于数据读写，所以它会按相同顺序执行那些日志。如我所说，分片是为了提高吞吐量，在不同的数据中心复制，原因有二。其一，在不同数据中心设置副本，以防某个数据中心发生故障，数据中心所在的整个城市停电，或者发生地震、火灾等情况，你会希望有其他副本。在其他可能不会同时故障的数据中心，这得付出代价。因为 Paxos协议需要通信，可能要远距离与不同数据中心的副本通信，在多个数据中心存储数据的另一个原因是，这能让你在靠近所有使用该数据的不同客户端附近存储数据副本。所以要是有一条数据在加州和纽约都可能被读取，那在加州存一份该数据或许不错，在纽约存一份，从而使读取操作非常快速。事实上该设计的许多重点在于让从本地。最近的副本读取既能保证快速又能确保正确。最后 Paxos 与多个数据中心之间的另一个有趣交互是 Paxos，与 Raft 一样，只需要多数派就能复制日志条目并继续。这意味着如果有一个速度慢的或距离较远、不太稳定的数据中心，Paxos 系统仍能持续运行并接受新请求。即便有一个数据中心速度慢。好的，那么在这种安排下，有几个大挑战等着这篇论文去应对。
其一他们确实想从本地数据中心读取数据，但由于他们使用的 Paxos 协议而且因为 Paxos 只要求每个日志条目在多数节点上进行复制，这就意味着少数副本可能会滞后并且可能尚未看到 Paxos 提交的最新数据。这意味着若允许客户端为求速度从本地副本读取数据，他们可能读到过时的数据。要是他们的副本恰好属于未获取最新更新的少数派，由于他们要求数据正确，要求具备外部一致性的这种理念，每次读取都能看到最新数据。他们都有办法应对这种可能性。即本地副本可能滞后，他们要处理的另一个问题是一个事务可能涉及多个分片进而涉及多个 Paxos 组，所以你可能正在进行读取或写入操作，单个事务可能正在读取或在数据库中写入多条记录，这些记录存在多个分片及多个 Paxos组中，所以这必须得是，我们需要分布式事务。
13.3 读写事务
接下来我要解释下事务是如何运作的，这将是本次讲座的重点所在。
Spanner处理和实现事务的方式与只读事务截然不同，那么我们先从读写事务说起，其设计相对更为传统。
好，首先是读写事务。我先给大家讲讲事务是怎样运行的，那我们选一个简单的类似银行转账的例子。在其中一台客户端机器上，Spanner 的一个客户端，你要运行一些代码，你要运行这个事务代码，代码会显示我要开始一个事务，然后会显示我要读写这些记录。比如说 数据库记录 X 里有个银行余额，我们要增加它。然后减少这个银行的余额，这就完成事务了。现在客户端希望数据库能提交所有这些操作。
好的，现在我来梳理下所有必要步骤，以便 Spanner 执行读写事务。
首先，有一个客户端在某个数据中心驱动着这个事务。我在这画出客户端假设 X且 Y 在不同分片上，因为这是一个有趣的情形。而这些分片，两个分片都在三个不同数据中心进行了复制。在每个数据中心，有一台服务器，我将用 X 表示数据副本，持有 X 银行余额的分片。用 Y 表示这三台服务器。
Spanner 运行两阶段提交，完全是标准的。两阶段提交和两阶段锁定，几乎与上周 6033 教材阅读材料中描述完全相同。巨大的差异在于，这里的参与者并非，事务管理器也不是单个计算机。事务管理器中的参与者是通过 Paxos 协议复制的服务器组以增强容错能力。这是为了提醒你那个分片，存储 X 的分片的三个副本，实际上是一个 Paxos组。存储 Y的三个副本同样如此。我们假设对于其中每一个，三个服务器中有一个领导者，那么假设数据中心2中的服务器是 X 分片的 Paxos领导者，数据中心 1 的服务器是 Y 分片的 Paxos领导者。
好啦，首先发生的是，客户端选取一个唯一的事务 ID，它会包含在所有这些消息里。系统就能知道所有不同操作和同一个事务有关。首先客户端得读取，所以尽管代码是这样的，它对 X 和 Y 进行读写操作，但实际上事务代码的组织方式。它必须先执行所有读取操作，然后在最后阶段，同时执行所有写入操作，这本质上是提交的一部分，所以客户端必须执行读取操作。（这里翻译有点问题）
为维护锁 如同上周 6033 课程中所讲，每次读取或写入一个数据项时，负责该数据项的服务器必须为其关联一把锁，锁会被维护。Spanner中的读锁仅在Paxos领导者处维护。所以当客户端事务要读取 X 时，它向 X 分片的领导者 Spanner 发送读取 X 的请求。X 分片的领导者返回 X 的当前值并对 X 加锁。当然，如果锁已设置，那么在之前它不会回复客户端。
当前锁定该数据的事务通过提交来释放锁，然后该分片的领导者将 X 的值发送给客户端。客户端需要读取 Y ，这次挺幸运，假设客户端位于数据中心 1，那么本地数据中心的领导者，所以这次读取会快很多，读取操作会在 Paxos领导这种对 Y 加锁，然后返回。现在，客户端已完成所有读取操作。它会进行内部计算，然后确定要执行的写入操作。它想写入 X 和 Y 的值，于是现在客户端要发送，它想要写入的记录的更新后的值，它会在事务快结束时，一次性完成这些操作。
首先，它会从多个 Paxos 组中选择一个作为事务协调器，它会提前选定并会发送出哪个 Paxos 组将担任事务协调器，假设它选定了这个 Paxos组，我在这里画个双框，表明此服务器不仅是其所在Paxos 组的领导者，它还充当此事务的事务协调器。
然后客户端发送更新后的值，它想写入，所以会在此处发送带新值的写 X 请求，以及事务协调器的标识。
当每个写入值的 Paxos值的 Paxos领导者，接收到正确请求后，它会向追随者发送一条准备消息，并将其记录到 Paxos 日志中，我将用 P 表示已记录到 Paxos日志中。因为它要承诺可以，又或者用“提交”这个词并不恰当。它承诺能够执行这个事务，比如说它没有崩溃且未丢失其锁。所以它发出这条准备消息。通过 Paxos将该准备消息记录到日志中，当它从大多追随者哪里得到响应时，然后这个 Paxos领导者向事务协调器发送“同意”回复。我承诺能够执行。
我在事务中的部分，即对 Y 的权限，理论上关于这个事务，我们来看，客户端也会发送，将写入 Y 的值发送给 Y 的 Paxos领导者。而充当 Paxos领导者的这台服务器会想向追随者发送准备消息，并将其记录到 Paxos中，并等待多数方的确认。
然后可以认为是 Paxos 领导者向事务协调器发送，它与事务协调器在同一台机器上，可能是同一个程序。一张赞成票，表示“可以 我能提交”。
好的，那么当事务协调器收到来自不同……的响应时，来自参与此事务的各个不同分片的领导者，要是他们都同意，那么事务协调器就能提交，否则就不行。假设它决定进行提交，此时事务协调器向 Paxos追随者发送一条提交消息，写到“请永久记录在事务日志中”。我们在正在提交事务中。
并且它也会告知参与此事务的其他 Paxos组的领导者，然后它们也能够提交。所以此时这个领导者也会向其追随者发送提交消息。实际上我认为领导者，事务协调者可能不会向其他分片发送提交信息，直到其提交在日志中处于安全状态。所以事务协调器无法保证不会忘记其决定。一旦提交，这些提交信息就会被写入不同分片的 Paxos日志中，每个分片实际上都能执行写入操作，即放置写入的数据并释放数据项上的锁。以便其他事务能够使用它们，然后事务便结束了。
关于目前的设计有一些要点需留意，到目前为止，它仅涵盖了事务的读写方面。一是锁确保了可串行性，即如果两个事务因使用相同数据而冲突，一个事务必须完全等待另一个事务释放锁后才能继续，所以 Spanner 采用完全标准的两阶段锁定，以实现可串行性，并通过完全标准的两阶段提交来实现分布式事务。两阶段提交广受诟病，因为如果事务协调器发生故障或无法访问，那么它所管的任何事务都会无限期阻塞，直到事务协调器重启，并且它们会在持有锁时发生阻塞。所以总体而言，人们在现实中一直很不愿意使用两阶段提交，因为它会造成阻塞。Spnaner 通过复制事务管理器来解决这个问题。事务管理器本身就是一个由 Paxos复制的状态机。所以它的所有操作，比如记录是否已提交这一操作会被复制到 Paxos日志中。
所以若此处领导者发生故障，即便它当时在管理该事务，因为它采用了包装复制方式，这两个副本中的任何一个都能活跃起来，接管领导权并接管事务管理器的角色。若事务管理器决定提交，它们的日志中会有记录，任何接管的领导者都会在其日志中看到提交记录，并能立即告知另一方，告知两阶段提交中的其他参与者，此事务已提交。所以这有效地消除了两阶段提交存在的问题。即出现故障时，它可能会有持有锁而被阻塞，这真的很重要。否则对于任何有大量可能故障部件的大规模系统而言，都是完全不可接受的。
Q：Leader 提交时而宕机，后续如何恢复正常状态？
这里记录一个问题，是否可以在 log 记录中有一个特殊状态，来标记log or 事务的提交状态，这样因为 Leader 提交时宕机而导致新选出的 Leader 无法提交后续日志导致的其他问题如无法将操作日志应用到状态机，Follower、Leader 无法更新 CommitIndex 等。
另一件需要注意的是，这张图上有大量消息，这意味着其中有许多消息时跨数据中心传输的，这些在分片之间传输的消息中，有些，在客户端与由另一个数据中心领导的分片之间传输，可能需要好几毫秒。在一个计算以纳秒计的世界中，这可能是一笔相当大的代价。事实上，你可以在表 6 中看到，查看它时，它描述了一个 Spanner 部署的性能。不同副本分布在美国东西两岸，完成一次事务大约需要 100 毫秒。所涉及的不同副本分布在不同海岸。这时间可够长的，这是十分之一秒，可能看上去没那么糟。因为系统的吞吐量，因为它是分片的能并行运行很多不冲突的事务，吞吐量可能会非常高，但当个事务的延迟十分明显。我是说100 毫秒可能略低于人类的可察觉范围，但是你得执行其中几个来，比如说生成一个网页或者执行一条人工指令，这段时间开始变得明显，甚至会让人觉得烦扰。另一方面，我猜想对于 Spanner 的许多应用场景而言。所有副本可能都在同一城市或就在城市不同地方。在那里，你在表 3 中看到的快得多的时间就很关键了。在哪里，表三显示它能够完成事务，在数据中心较近的情况下，我觉得应该是 14 毫秒而不是 100 毫秒，所以还不算太糟糕，然而这些读写事务很慢，所以我们会尽可能避免这种开销。所以这会让我们进入只读事务。事实证明，你不进行写入，也就是说，如果你事先知道，事务证的所有操作都保证是读操作，那么 Spanner 拥有一种快得多、精简得多的，用于执行只读事务的消息密集程度低得多的方案。
接下来是只读事务。只读事务可行，尽管它们依赖于读写事务中的某些信息，但其设计与读写事务有很大差异。并且 Spanner 在其只读事务设计中消除了两大成本。消除了读写事务中所存在的两项成本。首先如我所说，它从本地副本读取，所以若你有一个副本，只要有客户端所需数据的副本就行。事务在本地数据中心所需的那份数据，就能从那个本地副本读取，与之通信可能只需几分之一毫秒，而不是跨国读取可能需要几十毫秒，所以它能从本地副本读取，但要注意，这里有个风险，任何一个副本可能不是最新的，所以这肯定有原因。只读设计的另一大好处是它不用锁，它不采用两阶段提交，而且它不需要事务管理器，这避免了像跨数据中心这样的情况或数据中心给 Paxos领导者的消息，而且因为不用获取锁，这不仅让只读事务更快，还能避免减慢读写事务，因为它们无需等待只读事务持有的锁。
先来说说为什么这对它们很重要，表 3 和表6 显示，只读事务的延迟降低了 10 倍，与读写事务相比，所以只读设计让它们的延迟降低到十分之一，而且复杂度大大降低，所以几乎可以肯定吞吐量也会大幅度提高，而最大的挑战将是如何权衡。要知道，只读事务不会执行很多操作，而这些操作是读写事务实现可串行性所必需的。所以他们得想办法把提高的效率和正确性平衡一下。所以实际上 有两个主要的正确性约束，他们希望只读事务遵守。
第一个是和所有事务一样，它们仍然需要是可串行化的，这意味着只是回顾一下，即使系统可能同时执行并发事务并并行执行结果。无论是他们返回给客户端的值，还是对数据库的修改。一组并发事务的结果必须与一次只执行一个事务的结果相同，即串行执行。而对于只读事务，这本质上意味着对于一个完整的只读事务的所有读取操作，必须妥善地融入一系列事务的所有权限之间，可看作在它之前发生的事务且它不能看到任何一项权限，那些我们视为在它之后发生的事务的权限，所以我们需要一种方式来合理安排一个事务的所有读操作，要巧妙的置于读写事务之间
论文提到的另一个主要约束是他们需要外部一致性。而这意味着，实际上它等同于我们之前见过的线性一致性，这实际上意味着，这实际上意味着如果一个事务提交并完成，而另一个事务在第一个事务实时完成后启动。那么第二个事务应能看到第一个事务的写入操作。即使是只读事务，也不应该看到陈旧数据。如果一个已完成的事务有提交的写入操作。在读取对齐事务开始之前，读取对齐事务需要正确地看到这一点。例如，像 MySQK等数据库可配置为提供这一种一致性，所以某种程度上，它有点类似于这种一致性。如果你不太了解的画，这正是一个简单系统应有的一致性。
13.4 只读事务
如果我们干了一件及其愚蠢的事情，让只读事务不采取任何特殊操作来实现一致性，而只是读取数据的最新拷贝，所以每次只读事务执行读取操作时，我们可以让它去查看本地副本，并找到数据的当前最新拷贝，那样会非常简单直接开销极低，所以我们得弄明白为什么那样行不通。所以问题来了，为啥不直接读取最新值。那么或许我们可以设想这个事务，它只是简单读取 X 和 Y 并打印出来，那是只读的。我要打印 XY好了。
若此事务仅读取最新值，会产生不正确且不可序列化的结果。
假设我们有正在运行的事务 T1、 T2 、 T3，T3 是我们要讨论的事务，T1、T2 是读写事务。那么假设 T1写入 X和 Y 然后提交，也许这是一笔银行转账操作即 X 转账给 Y。假设T2也在 X 和 Y 余额之间进行了另一笔转账，然后提交。现在我们有了事务 T3，它需要读取 X 和 Y。假设在此处读取了 X，我绘制图表的方式时，实时向右移动的。所以对 X 的读取在T1完成之后、 T2开始之前在此处进行。
假设 T3 在一台缓慢的计算机运行，所以它要很久之后才能成功发出对 Y 的读取，那么事情会这样发展，事务三会看到 T1 写入的 Y 的值，但看到的确实 T2 写入的 X 值。假设它采用这种可疑的方法，只是简单读取数据库的最新值。所以这是不可序列化的。因为，我们知道，任何可能存在的串行顺序必定是 T1 在 T2 之后，T3 只能放在两个地方。
但 T3放不了这（T1、T2 之间），因为若在等效串行顺序里 T3 排第二，那它就不该看到 T2 的写入，而 T2 在它之后，它应该看到 T1 产生的 Y 值，但它没看到，对吧？它看到的是 T2 产生的值，所以它不是一个等效串行顺序。这个序列顺序不会得出相同的结果，我们唯一能用的就是这个。
这个序列得到的 Y 值会和 T3 实际产生的一样，但是如果是这个序列顺序，那么 T3 应该能看到 T2 写入的值，但实际上它看到的是 T1 写入的值，所以这个执行与任何一次只执行一个的序列顺序都不等效。这就好比单纯读取最新值是有问题的。
当然，我们真正要寻找的是，即事务在此时读取两个值。
看上去还是隔离性的问题。如果事务是并发执行的，那读取最新值确实存在这种问题。参考 MySQL 的 MVCC。
13.5 快照隔离
Spanner 解决此问题的方法，有点复杂，第一个主要想法是个已有概念，就是快照隔离。想象一下所有相关计算机的时钟都已同步，即他们都有一个时钟，时钟会给出一种类似挂钟显示的时间，比如时间是 2020—04-07 pm 1:43，所以这就是我们所说的挂钟时间（clock time）。
假设所有相关的计算机的时钟都已同步，尽管这并非事实。此外，假设每笔交易都被分配了一个特定时间，即时间戳。好了，我们有了这些时间戳。这些是从同步时钟获取的挂钟时间，对于读写事务其时间戳是，就这个简化设计而言是提交时的实际时间，而对于读操作或者在事务管理器开始提交的时间。而对于只读事务，时间戳等于开始时间。
每个事务都有一个时间，我们要设计的快照隔离系统执行起来就好像能得到和所有事务按时间戳顺序执行一样的结果，所以我们会给每个事务都分配一个时间戳，然后我们要安排执行，以便事务能得到按那个顺序执行的结果。那么给定时间戳，我们需要一个能遵循时间戳的实现方式，基本上向每个事务展示数据在其时间戳时的大致状态。好的，对于只读事务，其工作方式是每个副本存储数据时，实际上有该数据的多个版本。所以我们有一个多版本数据库，每个数据库记录都有。也许已经被写入过几次，每次写入都会生成该记录的一个单独副本，他们各自都与写入它的事务的时间戳相关联，然后基本策略是对于只读事务，当进行读取操作时，它在启动时就已为自己分配了一个时间戳，所以它会在读取请求中附上自己的时间戳，以及存储该事务所需数据副本的服务器，它会查看其多版本数据库，并找到所需的记录，其时间戳小于该时间戳且所有小于该时间戳的时间里最大的，由只读事务指定，这意味着只读事务看到的数据是截至该时间的最新数据，截至其选定的时间戳，关于这种快照理念适用于只读事务或者 Spanner 将其用于只读事务。Spanner 在读写事务中仍采用两阶段锁定和两阶段提交，于是读写事务会自行分配用于提交的时间戳。但除此之外，它们通过锁和两阶段提交，按常规方式运行。而只读事务会访问数据库中的多个版本，并获取由……写入的版本（翻译有点小问题）。其时间戳最高，但任小于只读事务的时间戳，而这会给我们带来的是只读事务会看到时间戳较低底的读写事务的所有写入操作，而看不到时间戳较高的读写事务的任何写入操作。那么对于我们的示例，快照隔离是如何起作用的呢？
我之前的举例，在这个例子中出现了可串行性失败。因为读事务读取的值不在任何两个读写事务的值之间。
现在我采用快照隔离的方式重新举例。展示这个例子是为了说明快照隔离技术解决了我们的问题，使事务具有可串行性。那么，再次出现这两个读写事务 T1 和 T2，并且我们有一个只读事务T3。T1、T2如之前所述，它们写入并提交，但现在它们提交时为自己分配时间戳。所以通过两阶段提交，两阶段锁定，这些读写事务会分配一个时间戳，那么在假设提交时，T1 看了看时钟，看到时间为 10，我会用 10、20 这样的时间，但是你可以把时间想象成实际的时刻，那么假设 T1提交时看到的时间是10，T2 看到的时间是 20，那我要写下这些事务并在@符号后面选定时间戳。然后是数据库存储系统，Spanner 存储系统会进行存储。
当事务一致性写入操作时，它们会存储新的而不是覆盖当前的值，它们只会添加这条带有时间戳的记录的一个新副本，所以数据库会存储一条新记录，它表明在时间 10 时 X的值是多多少，假设是 9，时间 10 时记录 Y 的值是 11，也许我们在进行从到 X 到 Y 的转移，T2 选择了时间戳是 20。因为那是提交时间，并且数据库除了这些旧记录外还会存储一批新记录，时间 20 时它显示 X 的值为 8，Y 的值为 12，所以现在我在不同时间有每条记录的两份副本。
现在 T3 即将到来，大约在这个时间，并读取 X，这次依然很慢，直到很久以后（下图中的 T3 RY）。
然而T3 事务开始时，选择了一个时间戳，通过查看当前时间，那么假设，我们实时直到T3 在在 T1之后、T2 之前启动，我们直到它必定在 10 到 20 之间选择了一个事务时间，假设它与时间 15 开始，并为自身选择了时间戳 15，所以这意味着当它读取 X 时，它会持有X 的本地副本发送请求并附上其时间戳 15，请给我截至时间 15的最新数据，当然 T2 还未执行。此时，X 的最高时间戳副本是 T1 在 10 时写入的那个，所以我们会得到 9。
现在 T3 进行第二次读取，同样它也会带有时间戳 15 的读取请求发送到服务器。现在服务器有两条记录，但同样由于服务器获取到 T3 的时间戳为 15，服务器查看记录并说，15 在这两个之间（指的是 10、20 这两个时间戳），我要返回 X 的最高时间戳记录，对于 Y 这个时间戳小于请求的时间戳，那仍是 Y 在时间 10 的版本，所以读取 Y 会返回 11。
也就是说，读取 X 的值会在此时发生，但是我们记住了时间戳，而且我们让数据库按不同写入时间保存数据，就好像两次读取都在时间 15 发生，而不是一次在 15 另一次在更晚的时间。
到这里，我不确定像这种本地事务读取最新的值是否存在问题。我想起了MySQL的 MVCC 实现，这种版本控制解决缓读的问题，像是回答了本地事务也会存在读取最新值的问题。MVCC 的解决方案是版本链+事务Id+活跃事务 Id组，来进行判断当前事务应该读取哪个版本的数据。
起初我看到这里，我想到为什么 MVCC 用这种“逻辑时钟”来构建版本链的技术，而不是采用真的时钟，因为在MySQL不是分布式数据库，它只会在同一台机器上执行事务，用时钟不是更方便的构建吗？但是答案应该是不行，因为机器时钟存在误差、或者可能时钟回拨。
现在你会看到，实际上，这本质上就是模拟一次执行一个的串行方式，其顺序为时间戳顺序，即 T1、T3、T2，这种串行顺序，这于结果等效，实际产生的时间戳顺序是 10、15、20，这是 Spanner 针对只读事务的一种简化工作方式，还有更多复杂之处，稍后会讲到。你可能会问，为什么 T3 读取的是 Y 的旧值呢？也就是说，它在这个时间点对 Y 进行了读取操作，Y 的最新数据是 12 这个值。但它实际得到的值却是一个故意使用的旧值。不是最新值，而是之前值。不久前的值是 11，那么这为什么行的通呢？为什么不使用数据的最新版本也行呢？其技术依据在于 T2和 T3 是并发的，这就是事务上的重叠部分。T2的时间范围在这，T3 的时间范围在这(见下图蓝线标注处）。它们是并发的，关于可线性画的规则，以及外部一致性的规则是，如果两个事务并发，那么数据库允许采用的串行顺序可将这两个事务以任意顺序排列。在此处，数据库 Spanner已选择在串行顺序中把 T3 排在 T2 之前。
学生提问：
Q: 像时间戳这种外部一致性，是否总是意味着强一致性？
A: 我猜是，我想如果是强一致性，那么就是强一致性。通常人们所说的强一致性就是指可线性化，而且我认为可线性化的定义是和外部一致性相同的，所以我会说是。还有一问题，这为何不会把存储空间撑爆呢？这是个很棒的问题，答案是它肯定会使存储空间撑满。原因是现在存储系统得保留数据记录的多个副本，这些数据记录最近被多次改动，这绝对是笔开销，包括存储成本，以及磁盘和内存的空间，而且这就像多了一层薄记工作，现在查找时必须同时考虑时间戳和键值。我觉得存储成本没达到应有的程度。因为系统会丢弃旧记录，论文未提及是什么策略，但据推测，它肯定在丢弃旧记录。当然，如果多条记录的唯一目的是实现这类事务的快照隔离，那么你其实无需记住太过久远的值。因为你只需记住值，追溯到某个仍在运行的事务最早可能开始的时间，而且如果你的事务大多总能完成，或者在一分钟内通过某种方式被迫完成。如果没有事务会超过一分钟，那么你只需记住数据库中最后一分钟的版本。事实上，论文暗示他们会记住比那更早的数据，因为看起来他们有意支持这些快照读取。这使他们能够支持查看不久前或昨天等数据的概念。但他们没有说明旧值的垃圾回收的策略是什么，所以我不知道这对它们来说成本有多高。好的，那么就它合法的理由就外部一致性而言。外部一致施加的规则而言，如果一个事务已经完成，那么在它之后开始的事务必须看到其修改内容。所以 T1 或许已经完成，假设此时 T1 已经完成，T3 在其之后立即开始，也许是外部一致性，但要求 T3 能看到 T1 的修改。但因为 T2 肯定在 T3 开始前未完成，根据外部一致性，我们没有义务让 T3 看到 T2 的修改。事实上，在这个例子中 T3 看不到 T2 的修改，所以实际上是不合法的。（不确认这里对不对，T3 看不到 T2 的修改，根据规则应该是合法的）
好的，出现的另一个问题是，T3 需要读取特定的时间戳的数据，但这样做的原因是，这能让我们从同意数据中心的本地副本读取数据。但或许那个本地副本，是未在领导者处看到最新日志记录的少数派 Paxos追随者，所以或许我们的本地副本，也许它甚至从未见过对 X 和 Y 的写入，它仍停留在一个较早版本，比如伍、六、或 七个版本之前，所以要是我们不采取巧妙的办法，当我们请求最高版本记录时，小于时间戳 15，我们可能得到一些旧得多的版本，其并非T1 实际产生的值，而这时我们必须要看的。所以 Spanner 处理此问题的方式是借助其安全时间概念，其实就是每个副本都记得。它从其 Paxos领导者处获取日志记录，而这些日志记录，原来论文是这样安排的。领导者按时间戳严格递增顺序发送日志记录，因此副本可以查看其从领导者处获取的最新日志记录，从而知晓自身的更新情况。若我请求时间戳为 15 时的旧值，但副本仅收到来自 Paxos 领导者、时间戳截至 13 的日志条目。副本会导致延迟。在从领导者获取到时间戳为 15 的日志记录之前，它不会回应。这确保副本不会响应给定时间戳的请求，直到它们确定已掌握领导者处直至该时间戳的所有信息，所以这可能会造成延迟，这可能会延迟读取。
13.6 时间同步（Time Sync）
好的，下一个问题。在这次讨论中，我假定时钟与所有不同服务器能完美同步。所以每个人的时钟显示，比如都是 10 点 01 分 30 秒，丝毫不差，但事实证明，时钟无法如此精确地同步。要让时钟完全同步，基本上是不可能的，而且原因十分根本。所以主题是时间同步。所以就是要确保时钟显示相同的实际时间，不同时钟显示相同的值。根本问题在于时间的定义是，基本上就是政府实验室里那一堆高精度昂贵时钟所显示的时间，所以我们无法直接读取，这些政府实验室能够以多种方式播报时间，而且播报是需要时间的，所以过了一段时间后，过了一段可能未知的时间后，我们会听到这些时间播报。所以由于延迟各异，我们可能在不同时间听到这些播报。所以实际上，我首先想考虑一下在快照隔离时，时钟不同步会有什么影响。
好吧，那么时钟不同步会怎样呢？Spanner的读写事务根本没有问题。因为读写事务使用锁及两阶段提交，他们实际上并未使用快照隔离。所以读写事务仍会通过两阶段锁定机制进行序列化，所以我们只关注只读事务的情况。那么假设一个只读事务选择了一个过大的时间戳，即那是在很遥远的未来，现在是下午12:01 分。它选择了一个时间戳比如下午 1 点。所以如果一个事务选择的时间戳过大，实际上这并不算太糟。这意味着它会执行读请求，它会向某个副本发送读请求。副本会说：“等一下”，你的时钟时间要晚的多。你的时间比我从我的 Paxos领导者哪里看到的最后一条日志记录要晚的多。所以我会让你一直等到 Paxos的情况出现，直到 Paxos领导者的时间和日志条目赶上你所请求的时间，那时我才会回应。所以这是对的，但是速度慢。读者将不得不等待。而且这还不是最糟糕的。但要是我们有个只读事务而它的时间戳又太小，会怎样呢？
这就意味着它的时钟要么被设置错了，以至于被设置到了过去。又或许它原本设置无误，只是时钟走的太慢了，这会带来一个问题，这显然会引发正确性问题。这会导致违反外部一致性，因为多版本数据库，你给它的时间戳会非常久远。比如说 1 小时前，数据库会读取与一小时前时间戳关联的值，这可能会忽略较新的写入，所以给事务分配一个过小的时间戳，会让你错过近期提交的写入操作。这违背了外部一致性原则，所以不具有外部一致性。
所以我们这儿确实有个问题，认为时钟已同步，这一假设实际上很关键，而且无法依赖它就意味着，除非我们有所行动，系统就会出错。那么我们能让时钟完美同步吗？那可就理想了。那时钟同步是怎么回事呢？
13.7 时钟同步（Clock Sync）
正如我所说，时间从哪来,实际上是政府实验室里多个时钟的某种平均值集合。我们了解时间的方式是它是通过协议广播的，有时是无线电协议，像 GPS 对 Spanner 做的是基本上是GPS 充当无线电广播系统。广播当前时间，通过全球定位系统，卫星将时间从一些政府实验室传输到位于Google 机房的全球定位系统接收器。还有许多其他的无线电协议，比如宽频带广播是另一种用于广播当前时间的较旧的无线电协议。还有更新的协议，比如有网络时间协议，它通过互联网运行，主要负责广播时间，那么系统示意图如下。
有一些政府实验室，政府实验室用精准时钟定义了一个名为协调世界时的通用时间概念，所以我们的协调世界时来自一些时钟和实验室，然后我们有一些无线或互联网广播之类。对于 Spanner 而言，我们可以设想政府实验室向 GPS 卫星广播，卫星随后进行广播，并且它们向数百万个 GPS 接收器广播。花费几百美元就能买到 GPS 接收器，它能解码 GPS 信号中的时间戳，随时准确掌握时间，已校准政府实验室之间的传播延迟，以及 GPS 卫星之间的延迟还有 GPS 卫星与你当前位置之间的延迟也已校正。每个数据中心都有，有一个 GPS 接收器连接到论文中提到的时间主控器。也就是一台服务器，每个数据中心都有不止一个这样的设备，以防有一个出现故障。
接着数据中心还有数百台服务器，这些服务器要么作为服务器，要么作为客户端运行着 Spanner。它们每一个都会定期发送一个请求，向本地的一个或多个询问现在几点了，通常不止一个，以防其中一个无法连接到时间主控设备，然后时间主控器会回复说，我认为从 GPS 接受到的当前时间是如此这般。
不幸的是，这其中存在着一定程度的不确定性，我认为不确定性的主要来源在于，从根本上讲，不确定性在于，我们实际上并不知道自己与 GPS 卫星的确切距离。所以无线电信号需要一定时间，即便 GPS 卫星确切知道当下时间，信号到达我们的 GPS 接收器也需要一些时间，若我们不确定其时长，这意味着当我们收到 GPS 卫星传来的无线电信号，显示正好 12 点时，要是传播延迟可能有几纳秒。
这意味着我们，实际上传播延迟要要比这大的多，这实际上就是传播延迟的不确定性，这意味着我们并不确定是否正好是 12 点，还是稍微早一点或者晚一点，此外每次传达时间时，都必须增加一些你必须考虑的不确定因素。最大的来源在于，当服务器发送请求时，过一会它会收到响应。如果响应时间恰好为 12 点。但假设在两者之间过去了1 秒。当服务器发送请求时，和当它收到响应时，服务器只知道即便主时钟时间正确，服务器只直到时间在 12 点前后 1 秒内，因为也许请求时瞬间发送出去的，但回复延迟了，或者请求延迟了 1 秒，响应是及时的，所以你只直到时间在 12 点整到 12 点零1 秒之间，总是存在这种不确定性。
不过我们不能忽视，因为存在不确定性，我们这里说的是毫秒，我们必须弄清楚，时间上的不确定性直接决定了这些安全等待的时长，还有其他一些暂停的时长，如我们所见，毫秒级别的不确定性是个严重问题，另一个大的不确定性在于，这些服务器各自仅请求，每隔一段时间从主服务器请求当前时间，在此期间每个服务器都运行自己的本地时钟，它大致从上次与主时钟同步的时间开始记录时间，那些本地时钟其实偏差很大，而且各自之间可能会漂移数毫秒，服务器与主时钟通信的时候，所以系统得某种程度上加上这个未知值。但要把本地时钟的估计漂移量加到时间的不确定性里，所以为了把握并考虑这种不确定性。Spanner 采用了这种真实时间方案，当你询问时间的时候，你实际得到的是其中一个 TT 时间间隔，它是由最早时间和最晚时间组成的一对值。最早时间指的是可能的最早时间可能达到的最早时刻。第二个是时间可能达到的最晚时刻，所以当应用程序调用这个库来询问时间时，它会得到这组值，它只直到当前时间介于最早时间和最晚时间之间，所以在这种情况下，最早时间可能是12 点，最晚可能是 12:01，我们只确定正确的时间不小于最早时间，且不大于最晚时间。我们不知道它在两者之间的何处。
下面是当事务向系统询问时间时，这就是事务从时间系统实际得到的回复。
13.8 START、COMMIT WAIT
现在让我们回到原来的问题，原来的问题是如果时钟太慢，那么一个只读事务可能会读取到太过久远的数据，且不会读取近期已提交事务的数据。因此我们要弄清楚 Spanner 如何利用这些 TT 时间间隔，及其真实时间概念，以确保即便时间不确定，事务遵循外部一致性。即只读事务必定能看到已完成事务的操作结果。一个在我们之前完成的事务，此外 Spanner 采用了两条规则，论文中提到这些规则共同作用以确保此点。
第 412 节里有两条规则，其中一条是 START规则，另一条是提交等待。
START 从事务层面告诉我们时间戳，事务选择的时间戳，基本上就是说，事务的时间戳必须等于当前真实时间的后半部分，所以这是对 tt.now 的调用。它返回最早与最新时间对中的一个，也就是当前时间，而且事务的时间戳必须是最新的。也就是说，这将是一个保证尚未发生的时间，因为真实时间在最早时间和最晚时间之间，对于只读事务，它被分配从开始时起的最新时间，对于读写事务，它被分配一个时间戳，从开始提交时起的这个最新值。START 规则规定了 Spanner 就是这样选择时间戳的。
Commit wait 规则仅适用于读写事务，当事务协调器收集选票时，并确认可以提交后选择一个时间戳，在选择时间戳之后，需要进行延迟，需等待一段时间后才能实际提交，然后写入值并释放锁，所以读写事务必须延迟到其选择的时间戳。即开始考虑提交时的时间戳要小于当前最早时间，这里的情况是它处于循环中调用 ts.now，它会一直停留在循环中直到，它所选的时间戳，在提交过程开始时小于当前最早时间，这确保了现在最早可能的正确时间大于事务时间戳，这意味着当循环结束时，当提交等待结束，事务的这个时间戳绝对在过去。
那么系统究竟如何运用这两条规则，为对只读事务强制执行外部一致性，我想回到，或者我想虚构一个简化场景来说明此点。所以我来设想，写入事务每次仅执行一次写入以降低复杂度，假设有两个读写事务，那么 T0 和 T1 是读写事务，两者都写入 X，还有个 T2 它将读取 X。我们要确保T2 在时间戳处使用快照隔离，我们要确保它能看到最新写入的值，所以我们设想，假设 T2 写入 X，并向 X 写入 1 然后提交，T2 也向 X 写入值然后提交，我们需要区分准备和提交，所以实际上是一次准备，事务选择其时间戳，所以这就是它在此选择其时间戳，然后过一段时间它再提交，然后假设T2在 T1 完成后开始，所以之后它会读取 X，我们要确保它能看到 2。
那么假设 T0 选择了时间戳 1 并提交，然后写入数据库。
假设T1 开始，当它选择时间戳时，它会获取一些，它不会从中得到单个数字，双时间系统实际会获取一系列数字，一个最早值一个最晚值。假设在它选择时间戳时，其值的范围，最早的，它获取到的时间为 1，当前最新字段是 10，所以规则规定它得选 10，最新值即其时间戳
所以T1 将用时间戳 10 提交，现在它还不能提交。因为提交等待规则要求它得等待，直到其时间戳确定已过去。T1 就会一直等着，不断询问几点了，直到它得到一个不含时间 10 的时间区间，所以在某个时刻，它会问几点了，然后它会得到一个时间点。即最早值为 11，最晚值我不知道，就说 20 吧。现在我直到我的时间戳已经过去，我可以提交了。
所以 T1 实际上会，这是其提交等待时段，它会在那等着。在提交前等一会。
它提交后（指 T1），T2 出现并想超过 X，它也会选个时间戳，我们假定它在 T1 完成后启动，因为这是外部一致性方面的有趣情形。假设它询问时间时，它在 11 之后的某个时刻询问，所以它会得到一个包含时间 11 的时间区间，那么假设它得到一个时间 10 起的时间区间，最早时间 10，最晚时间是 12，因为我们直到它至少得是时间 11，因为T2 在 T1 结束后才开始，这意味着 11 要小于最晚值。
T2 会选择它的最晚部分作为时间戳，所以它实际会选择时间戳 12。
在这个例子中，进行读取操作时，它会向存储系统询问，我想读取时间戳为 12 的数据，因为T1 是用时间戳 10 写入的，这意味着，假设安全时间机制有效，我们实际上读取到正确的值，这里发生的情况是，所以这成功了，但是实际上，如果 T2……则保证会成功。只要T2 在T1 提交后启动，原因是提交等待会使T1 在其时间戳保证在过去之后才完成提交，直到其时间戳被保证处于过去，所以 T1 选择了一个时间戳，它保证在该时间戳之后提交，T2 在提交后开始，所以我们对它的最早值一无所知，但其最新值保证在当前时间之后，但我们直到当前时间在 T1 的提交时间之后，因此 T2的最新值，它选择的时间戳保证在当前时间之后，当 C （指 T1 commit）提交时其时间戳必然在 C 所使用的时间戳之后(T1选择了时间戳 10，它保证在时间戳 10之后提交)，由于T2 在 T1 完成之后开始，T2 必然会获得更高的时间戳，而快照隔离机制，多个版本致使它进行读取，它会读取所有较低时间戳事务中的较低值写入，这意味着 T2会看到 T1，这基本上意味着 Spanner 就是这样为其事务强制实施外部一致性的，关于这个机制有问题吗？好的，我想稍微向后退一下。在我看来，这里发生了两件大事，其一是快照隔离本身，快照隔离本身足以给你，它会保证多个版本，并为每个事务分配一个时间戳，快照隔离能确保为您提供可序列化的只读事务，因为快照隔离的本质是我们会将这些时间戳用作等效的串行顺序，还有安全等待、安全时间等，确保只读事务确实依据其时间戳进行读取。在此之前查看所有读写事务，之后不再查看，所以实际上分为两个部分，不过快照隔离不仅常被使用，不仅 Spanner 会用，它一般来说，它自身无法保证外部一致性，因为在分布式系统里，是不同计算机选择时间戳，我们不确定那些时间戳是否符合外部一致性要求，即便它们能实现可串行性，所以除了快照隔离，Spanner 还具备同步时间戳即同步时间戳加上提交等待规则，使 Spanner 能够保证外部一致性及可串行性。再说，这一切有趣的原因在于程序员们很喜欢事务，并且他们很喜欢外部一致性，因为这让应用程序编写轻松很多。传统上，分布式环境中无法提供它们，因为速度太慢。所以 Spanner 能做到，至少能让只读事务速度极快，这很有吸引力。无锁定、无两阶段提交，甚至只读事务也无需远程读取，用于只读事务，它们在本地副本上运行高效。如表3 和表 6 所示，这能将延迟大幅降低至十分之一，但要提醒一下，并非一切都很美好，所有这些出色机制仅适用于只读事务，读写事务仍使用两阶段提交和锁定。Spanner也会因为安全时间和提交等待而不得不阻塞，但只要它们的时间足够精准，这些提交权重可能相对较小。好总结一下，当时的 Spanner 堪称一项突破，因为很少见到已部署的系统能提供分布式事务且数据分布在地理位置差异极大的数据中心，要知道 Spanner 令人惊讶，居然有人在使用一个在这方面表现出色的数据库，这让人们感到惊讶，而且性能还能过得去。而快照隔离和时间戳部分或许是这篇论文最有意思的地方。
- Author:newrain-zh
- URL:https://alex.sh.cn/article/ MIT6.824-13
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
.png?table=block&id=26b332f2-d485-807d-9f05-e01b6c17fab0&t=26b332f2-d485-807d-9f05-e01b6c17fab0)