“Hi，这是小5自学算力大集群相关知识的第10篇笔记。作为分布式系统，其内部的各个服务器可能正如其名字的字面意义一样——分散在不同地方。那有没有一种专门为数据广泛分散的情况下提供分布式事务而设计的方案呢？”
摘要
现实的场景中，由于考虑到灾备和区域性访问速度响应的要求，数据存储可能散布在互联网中。它们往往存储于不同的数据中心中，甚至这些数据中心也彼此散布在距离较远的地区。
Spanner为上述的场景提供了一种设计思想，目前有不少开源系统（如CockroachDB）明确地采用了这种设计。
- 设计理念
Spanner的设计理念主要有以下两点：
1.运行两阶段提交（实际上是通过Paxos复制参与者来执行），以此来规避两阶段提交中因协调器崩溃而导致阻塞的问题；
2.利用同步时间来实现非常高效的只读事务。
- 方案原理
数据被以关键词的方式进行分片，并分散在多个服务器上。可能在这个数据中心有一台服务器负责以A开头的密钥，另一台负责以B开头的密钥，以此类推。事实上，每个数据中心都拥有任意一份数据，任何分片都在不止一个数据中心进行了复制。比如存在3个数据中心，那么所有的数据即存在3份副本。
所有副本的管理由Paxos算法负责，它更像是Paxos的一种变体，具有领导者机制，非常类似于我们熟知的Raft协议。每个Paxos实例管理特定数据分片的全部副本。在这些Paxos实例中，每个实例都是独立的，拥有自己的领导者，运行着自己的Paxos协议实例版本。而每个分片独立运行Paxos实例的原因是为了实现并行加速和大量并行吞吐量。
如果一个普通人在其网络浏览器前连接到使用Spanner的Google服务，他们将连接到某个数据中心中的某台Web服务器。即这些 Spanner 客户端之一。所以会同时存在大量的客户端，这就带来了对大量并行吞吐量性能的要求。
如果客户端需要执行写操作，它必须将该写操作发送给其数据需要被写入的分片领导者。通过Raft协议，这些Paxos实例实际上是在发送日志。领导者向所有跟随者复制和分发操作目志，而跟随者则执行该日志中的操作，即读取和写入操作。因此，它按照相同的顺序执行这些日志。
如同Raft一样，Paxos仅需多数派同意即可复制日志条目并继续推进。
这意表示即使存在一个速度较慢、距离较远或不稳定的的数据中心，Paxos系统仍能持续运行并接收新请求。哪怕其中一个数据中心运行缓慢，也不会拖累系统整体的性能。
上图是一个示例：
列表示不同数据中心、内部服务器与客户端，如DC1数据中心下有包含数据a、b分片的服务器，同时被客户端C连接着；
行表示不同数据中心的服务器都保存着同一个数据的不同分片，如a数据的分片被分别保存在DC 1、2、3。并由Paxos负责管理，即红色虚线。
- Spanner方案面临的挑战
1.可能会读取到过时数据：
由于采用Paxos算法，且Paxos仅需每个日志条目在多数节点上复制，这意味着少数副本可能滞后，未能获取Paxos已确认的最新数据。为了满足读取速度的要求，如果客户端从本地副本快速读取数据。那么当所请求的副本恰好是未接收到最新更新的少数派时，他们可能会读取到过时的数据。
2.由于一个事务可能涉及多个分片，因此涉及多个Paxos组
2.1 针对读写事务：
整个事务还是通过二阶段锁定的方式进行，以实现串行化。同时也使用二阶段提交来实现分布式事务。但不同点在于，参与者与事务管理器不再由单个计算机担任，而是由Paxos复制的服务器集群构成，以增强容错能力。
以银行系统为例，某客户端请求转账变更余额，这里涉及两个账户，即需要转账的X账户与接收转账的Y账户。首先发生的是客户端会选取一个唯一的交易ID，该ID将伴随所有此交易相关的来往消息，以便系统知晓所有不同的操作都与单个交易相关联。事务代码的组织方式必须先执行所有读操作，然后在最后阶段，一次性完成所有写操作。
为了维持锁的状态，每当读取或写入数据项时，负责该数据项的服务器必须为其关联一个锁，其中读锁仅在Paxos领导节点上维护。例如，当客户端事务需要读取X时，它会向Spanner发送一个读取X的请求，该请求指向X所在分片的领导者。X所在分片的领导者将返回X的当前值，并同时对X设置一个锁。如果锁已经设置，那么在当前持有数据锁的事务通过提交释放锁之前，它不会对客户端做出响应。随后，该分片的领导者将X的值返回给客户端。
现在，客户端将发送它想要写入的记录的更新值。第一步会选定一个Paxos组成员作为事务协调者。客户端会发送一个带有写入X新值和事务协调器身份的请求至X数据的领导者节点。当Paxos领导者接收到请求时，它会向其追随者发送一个Prepare消息，并将其记录到Paxos日志中。当已从多数追随者那里收到响应后，这个Paxos领导者会向事务协调器（事务协调器可以就是领导者其自身）发送一个yes，表示：是的，我承诺能够执行我的事务部分。
接下来，该事务涉及客户端将待写入Y的值发送给Paxos协议的领导者，该服务器作为Paxos领导者向其追随者发送Prepare消息，并在Paxos中记录这些消息，同时等待来自多数派的确认。随后向事务协调器发送肯定投票，表明：“是的，我可以提交该事务。”
当事务协调器从所有不同分片的领导者那里获得响应。而这些分片的数据都涉及此次事务时，如果他们都表示同意，那么事务协调器就可以提交该事务（否则就不能提交）。随后，事务协调器向Paxos追随者发送一条提交消息，内容为：“请注意，在事务日志中永久记录，我们正在提交此事务。”同时，它也会通知参与此次交易的其他Paxos 组别的领导者，以便他们也能进行提交。因此，现在X的领导者也会向其追随者发送提交消息。
一旦提交完成，事务协调器很可能不会向其他分片发送提交消息，直到其提交记录在日志中安全保存。这样一来，事务协调器就不会有忘记其决策的风险。
提交后，这些提交消息就会被记录到不同分片（Shards）的Paxos日志中，每个分片实际上能够执行写操作。即放置写入的数据并释放对数据项的锁，以便其他事务可以使用这些数据项。之后，该交易彻底结束。
需注意的是，这个过程中可能有大量的消息传递。由于许多节点分布在不同的数据中心。因此，在这些分片之间或客户端与分片之间（分片领导者位于另一数据中心）传递的一些消息可能需要许多毫秒的时间。这样的开销可能是相当沉重的性能负担。
2.2 只读事务：
Spanner在其只读事务设计中消除了两大成本。
1）它从本地副本中读取。因此，若存在副本，只要该副本包含客户端所需数据，即本地数据中心内的交易所需数据，便可直接从本地副本进行读取，此过程仅需毫秒级的时间开销：相较之下，若需跨地域访问，则可能耗时数十毫秒。但这里的一个风险是，任何给定的副本可能不是最新的。
2）针对只读事务，不使用锁、不使用两阶段提交，也不需要事务管理器。这样可以避免诸如跨数据中心或数据中心间向Paxos领导者的消息传递。由于无需获取锁，这不仅使得只读事务执行速度更快还避免了读写事务因等待只读事务持有的锁而导致的延迟。
但上面的两点优化如何保证只读事务仍然需要是可串行化呢？
尽管系统可并行地执行并发事务，但这些并发事务所产生的结果，无论是它们返回给客户端的值，还是对数据库的修改，都必须与一次一个或串行执行的结果相同。对于那些事务以及只读事务，其本质含义是：一个只读事务的所有读操作必须恰好介于其之前的一系列读写事务的所有写操作，以及其之后的一系列读写事务的所有写操作之间，且不得观察到任何后续读写事务的写操作。如果让只读事务不采取任何特措施来确保一致性，而是仅仅读取数据的最新副本，会导致非串行化的错误结果。
另一个问题是外部一致性。这意味着，如果一个事务提交完成，而另一个事务在第一个事务完成后的实时时间开始，那么第二个事务必须能够看到第一个事务所做的写入操作。即，虽然是只读事务，也不应看到过时数据。
为了解决上面的挑战，Spanner需要用到快照隔离（Snapshot）技术。
我们将以一个简化的版本来讲述快照隔离的基本原理，在开始之前需要满足几个前置条件的假设：
1）设想所有参与的计算机都拥有同步的时钟；
2）设想每笔交易都被赋予了一个特定的时间，即时间戳；
3）对于读写事务，其时间戳，在此简化设计中即为提交时的实时时间；
4）对于读操作，或在事务管理器开始提交的时刻，对于只读事务，其时间戳等于启动时间。因此，每个事务都有一个时间戳，快照隔离系统执行时获得与所有事务按时间戳顺序执行相同的结果。为每个事务分配一个时间戳，然后按照执行顺序以确保事务获得的结果仿佛它们是按该顺序执行的；
5）每个副本在存储数据时，实际上拥有数据的多个版本，所以我们拥有一个多版本数据库。每个数据库记录都可能存在多次写入的情况，因此，对于每次写入，它都会有一个单独的记录副本，每个副本都与写入该记录的事务的时间戳相关联。
简单的说：对于只读事务，当它执行读操作时，在其启动时已经为自己分配了一个时间戳，因此它会将该时间戳随同读请求一并发送。存储该事务所需数据副本的任何服务器，将会在其多版本数据库中查找所需记录，该记录的时间戳最高且仍然小于只读事务指定的时间戳。即只读事务将看到所有时间戳较低的读写事务的写入操作，而不会看到时间戳较高的读写事务的任何写入操作。当进行写入操作，数据库将记住一组新的记录，还包括这些旧记录，即不会覆盖旧数据。在不同时间点（写入前后）拥有了每条记录的副本。于是便得到了符合串行化的结果。
下面我们将讨论几个相关的问题：
1.为什么读去一个旧的值是被允许的？
技术层面，线性一致性和外部一致性的规则是，如果两个事务是并发的，那么数据库被允许使用的串行顺序可以将这两个事务以任意顺序排列。所以读取到旧的值是合法的。
2.但或许本地的副本所存储的数据过于久远，如那些未曾见到领导者最新日志记录的Paxos追随者。即或许我们的本地副本甚至从未收到过领导者的日志记录。
Spanner处理这个问题的方式是采用其“安全时间”的概念。其关键在于，每个副本都会记住它从其Paxos领导者那里接收到的日志记录。因此，副本可以通过查看从其领导者接收到的最新日志记录，来了解自己的更新程度。如果请求的时间戳大于本仅从Paxos领导者那里接收到时间戳，系统将会延迟直到它从领导者那里接收到一个时间戳大于等于请求的时间戳为止。这确保了副本在确信从领导者那里获取了直至该时间戳的所有信息之前，不会响应针对特定时间戳的请求。
Snapshot隔离本身足以维护多个版本并为每个事务分配一个时间戳。其保证了可序列化的只读事务，因为Snapshot隔离将使用这些时间戳作为等效的串行顺序，并通过安全等待、安全时间等机制确保只读事务确实按照其时间戳读取数据，观察到所有在此之前的读写事务，而不会观察到此之后的任何事务。但它本身并不能保证外部一致性。因为在分布式系统中，是不同的计算机选择时间戳。因此，除了快照隔离，Spanner还需具备同步时间戳功能。正是同步时间戳加上提交等待规则（后文将进行叙述），使得Spanner能够保证外部一致性以及序列化性。
关于时间同步，上述方案的一个前提假设是所有服务器上的时间都是准确同步的。问题在于，时间靠广播的方式获取，而广播时间可能带来延时。如果快照隔离状态下时钟未同步（它们通常也确实不会同步），其影响究竟是什么？
Spanner的读写事务实际上没有任何问题，因为读写事务采用了锁和两阶段提交协议。
针对只读事务可能存在时间戳过大或者过小两种异常情况。
- 如果时间戳过大
假设一个只读事务选择了一个过大的时间戳。如，现在是12点01分。它选择了一个时间戳，比如说，下午1点钟。这意味着它将执行读取请求，向某个副本发送读取请求，然后该副本会说：等一下，时间戳远大于我从Paxos领导节点看到的最后一个日志条目。因此，我将让您等待，直到Paxos、时间和Paxos领导者的日志条目赶上您所请求的时间。
此时，读取者将等待。
- 时间戳过小
这对应于其时钟设置错误，导致时间被设定在过去，或者可能最初设置正确，但其时钟走得太慢。这显然会导致正确性问题。这将导致外部一致性被破坏，因为多版本数据库会赋予一个远在过去的时戳，比如一小时前，而数据库将根据该时戳提供如一小时前的值，这可能会忽略掉更近期的写入操作。因此，为交易分配一个过小的时戳会导致错过最近提交的写入操作。即违反了外部一致性。
解决方法
GPS卫星向位于谷歌机房的GPS接收器广播当前时间，这些时间经过校准及距离校正。在每个数据中心内。都配备有一个GPS接收器，该接收器与“时间主控”相连接。数据中心中的每个节点都会周期性地发送请求，询问：“现在是什么时间？”给本地的一个或多个时间主控节点。时间主控器将会回复说：“我认为从GPS接收到的当前时间是xxxxxx。”但这里还是内置了一定程度的不确定性 —— 我们实际上并不确切知道我们距离GPS卫星有多远，因此，无线电信号需要一定的时间。即便GPS卫星确切知晓当前时间，信号传输至GPS接收器仍需一定时间。此外，在所有时间信息进行通信的过程中，都会引入额外的误差。另一个重大的不确定性在于，这些服务器仅偶尔从主服务器请求当前时间，比如说，每隔一分钟或根据需要不定时进行。
时间的这种不确定性直接关系到这些安全权重需要持续多久，以及某些其他暂停需要持续多久，即提交权重。为了捕捉这种不确定性并对其进行考量，Spanner采用了这种真时方案，即当你询问当前时间时，实际返回的是一个TT间隔，它由最早时间和最晚时间组成的一对值构成。只能确保正确的时间既不会早于最早时间（earliest)，也不会晚于最晚时间（latest）。
针对事务的处理，除了知晓时间区间外，还需要遵循两个规则：
1.启动规则
对于只读事务而言，其时间戳被赋予为启动时的最新时间。对于读写事务，它会分配一个时间戳，即其开始提交时最新值的时间标记。一个事务的时间戳必须等于当前真实时间（TT时间区间）的后半部分。
2.提交等待规则
仅适用于读写事务，规定是当事务协调器收集到表决结果并确定能够提交且选定时间戳后，在实际允许提交、写入值井释放须之前，必须延迟，等待一定时间。因此，一个读写事务必须延迟，直到它开始考虑提交时所选择的时标小于当前最早的时间。这一保证意味着，由于现在最早可能的正确时间已超过交易的时间戳，这意味着当提交等待完成后，该交易的时间戳绝对保证已成为过去。
事实证明，如果并非在写入数据，即事先知晓事务中的所有操作均为读取操作，那么Spanner针对只读事务拥有一种更为快速、高效且消息传递较少的执行方案。当时的Spamner可以说是一项突破，因为它非常罕见地实现了在地理位置上分散于不同数据中心的系统中提供分布式事务的功能。