Spanner：
提供了针对分布范围很广的分离数据的分布式事务，这些数据可以分布在Internet的任何地方。
事务
将数据分散在网络上：容错，数据靠近用户访问更快
事务实现：2PC，为了防止TC崩溃而导致所有人被阻塞，Spanner中使用了Paxos
通过同步时间来做到非常高效的只读事务。
设计Spanner的原因：
Google广告系统中的数据是存在于很多不同的 MySQL和bigTable数据库中的，维护这些分片是一个非常费事费力的过程。除此之外，他们的广告系统使用的数据库系统不支持垮多台服务器的事务，只支持单台服务器上的事务。但他们希望将数据分散到不同的服务器上以获得更好的性能，并且想具备在多个分片上使用事务的能力。 对于他们的广告系统使用的数据库系统来说，这里的workload是以读事务为主，table6上面可以看到，上面有数十亿个只读事务，读写事务只有数百万而已。所以，他们对只读事务的性能很感兴趣。很明显，他们也需要强一致性。他们想要顺序执行事务。同时，他们也需要外部一致性。that means，如果一个事务提交了，在它提交完成后第二个事务开始执行。第二个事务要能够看到第一个事务所做的任何修改。如果我们想去获得外部一致性的能力，那么就要考虑分布式下数据复制相关的问题。
Spanner的物理布局：
Spanner的数据中心遍布全球，有多个数据中心，DC1，DC2，DC3。然后，我们将数据分片，讲数据通过key来进行拆分，并分散到多个服务器上。（key为a和b的数据）每份数据都会被进行分片并复制备份到多个数据中心中，这些副本完全一样。每个数据中心有很多client，这些spanner cilent就是web server。这些replia是通过paxos管理，对于每一个 给定的数据分片，它都会由一个paxos实例来管理该数据分片对应的所有replia，包含a数据分片的所有replia就组成了一个paxos组，组成b数据分片的所有replia组成了另一个paxos组，这些paxos实例都是彼此独立的。每个paxos组都有属于自己的leader，各自维护者独立的数据版本协议。 之所以每个数据分片对应paxos实例彼此独立，是因为这样做我们可以让这些数据并行加速处理，提高了并行吞吐量。（为了处理海量的请求，spanner需要付出巨大的代价讲这些请求分散到数据分片所在的多个paxos组中，以此来做到对请求的并行处理）
每个paxos组都有一个leader， 如果一个客户需要进行写操作，它得讲这个写请求发送给需要处理的这个数据分片所在paxos组的leader，paxos所做的操作就是发送日志，leader会将关于操作的日志发送给他所有的follower。follower就会去执行这些日志，对于数据来说，这就是读取和写入。
Spanner物理布局的原因：
将数据副本放在不同的数据中心，一个数据中心发生了故障（停电，地震。。。），同一时间，保存着改数据其他副本的数据中心可能并不会发生故障，让靠近改数据副本的所有不同client去使用该数据（让靠近replila最近的client来处理读取请求）（使用分片为了提高吞吐量）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IM7JjUWH-1617203216280)(http://note.youdao.com/yws/res/9978/0FE698BDD84145AB89F82324A3823284)]
paxos和raft很像，它只需要得到大多数的支持，以此来对日志条目进行复制并处理。如果我们有一个数据中心很慢的情况下，paxos系统也能继续处理并接收新的请求。
Spanner需要面对的问题：
Spanner从本地读取处理。Spanner使用的Paxos，Paxos只需要将数据复制到大多数follower中即可，意味着有少数replila中的数据可能会落后（还没有看到提高的最新数据 ）。它们需要某种方式来处理本地replia上数据的版本有点儿落后的情况。一个事务可能回设计到多个数据分片，也就是多个paxos组。（这个事务可能要对数据库中的多个记录进行读写，这些记录被保存在多个数据分片和多个paxos组中），我们需要使用分布式事务。读写型事务（R/W transtction）：
// 转账，x和y都是在不同的数据分片上，两个数据分片被复制到不同数据中心中// 在每个数据中心，都会有一台用来保存x所对应数据分片服务器（X代表保存着账户X银行存款数据分片的replia，Y同理）BEGIN x = x + 1 y = y - 1ENDSpanner使用分布式事务。我们不会使用单独一个server作为参与者和事务协调器，我们是使用由多太服务器所组成的paxos组来充当参与者和TC的角色，以此提高容错能力。
DC2中的这台server是数据分片X这个paxos组中的leader，DC1中的y是。。，client会选择唯一一个事务id来给它所要发送的所有消息打上标记。 这样系统就会根据事务id知道该事物所对应的所有这些不同的操作。
步骤：
1.client首先要做的事情就是读取，它首先去执行所有的读操作（x,y），然后在最后同时去执行所有的写操作，本质上这是提交操作的一部分。(为了去维护锁，当需要对data item读取和写入时，负责处理该item的服务器得讲一把锁和这个data item关联起来，这些锁的类型是读锁，Spanner会在paxos组的leader处对这些锁进行维护，当client想执行事务时，即它想去读取x，它会向数据分片x所属的paxos组中的leader发送第一个读请求，该数据分片所在的paxos组中的leader会返回X的当前值，并对x加锁
（如果该数据被加锁累，那么只有当前持有该数据所对应的锁的事务提交并释放锁后，我们才能对这个client进行响应），然后该分片的leader才会讲x的值发送给client。（读取y同理）
2.读取x，y结束后，这个client会在内部进行计算，并弄清楚它想对x和y写入的值是什么。现在，client会将它要对该记录进行更新的值发送给leader。client会再事务的最后将这些写操作一次性提交给paxos组。
3.首先，client会选择一个paxos组来作为TC使用，client会将作为TC来使用的哪个paxos组的id发送出去。
方框标记的paxos组中的server，它不仅是该paxos组的leader，它同时扮演了该事务的TC的角色。
4.然后，client将它想写入的更新值发送出去。client会发送一个关于x的写请求给x的leader，该请求中携带累它想写入的值，以及改TC的id。当每个paxos组中的lelader收到携带写入值的这个写请求时，它会发送一条prepare消息给他的follower，并将它写入到paxos的日志中（p表示prepare消息，并且会被写入paxos日志中），如果它没有发生奔溃和丢失锁的情况下，那么它就能够执行这个事务。leader会将prepare消息发送给该paxos组中的follower，当它得到了大多数的follower响应后，这个paxos组中的leader就会发送一个yes给这个TC（Y同理）。当TC收到了来自所有涉及该事务的数据分片所属的paxos组中leader的响应后，如果响应都是YES，TC久能够提交这个事务。
5.只有当commit日志安全落地后，TC才会将commit消息发送给其他数据分片的paxos组。（TC发送给数据分片Y所属的paxos组中的follower一条commit消息。同时，也告诉X，）我们保证TC不会忘记它所做的决定
6.一旦这些commit消息都被提交到了不同shard中的paxos log日志中，每个shard久可以去执行这些写操作，讲这些数据写入，并释放这些data item上的锁。这样，其他事务就能使用这些数据了。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T9xU8JdZ-1617203216282)(http://note.youdao.com/yws/res/10101/37BEC3CF89BD47508DF0EE8AB4236855)]
锁用来确保事务执行的有序性，如果两个事务冲突了，他们都在操作同一个对象。前一个事务的锁释放之后，后一个事务才能对数据对象进行处理。Spanner使用了完全标准的两阶段锁来获取有序性，也使用了完全标准的两阶段提交来获得使用分布式事务的能力。
两阶段提交的问题：如果 TC发生了故障，那么它所管理的这些事务会一直阻塞下去，直到TC恢复为止。这些事务阻塞的时候，还拿着它们执行事务时所用到的锁。在现实生活中，因为这个特性，大家不愿意使用2pc。Spanner通过对TC进行复制，解决了这个问题。TC本身就是一个基于Paxos的replilcated state machine。这种方法有效消除了2pc带来的问题：即如果TC在持有锁的情况下发生故障导致阻塞的问题。
分布式事务的延迟：spanner的2pc涉及非常多的交互，这些交互是跨数据中心的。单个事务的延迟会比较高。因为数据被分好片了，系统可以同时并行处理很多无冲突的事务。吞吐量可能会很高。但对于单个事务的延迟就会非常明显。
R/O transaction对于只读事务，Spanner速度更快，更加惊简，并且不用发送那么多消息。
只读事务相对于读写型事务，消除了两大损耗：
从本地replia读取数据。 （如果从本地replia读取数据，那么所花时间可能不到1ms，如果是跨国读取数据，那么所花的时间就是数十ms）。没有使用锁，也没有使用2pc，不需要使用TC进行管理。（这样就避免跨数据中心读取数据，即避免讲读请求发送给跨数据中心的paxos组leader来处理这个事务）因为这里没有锁，这不仅可以 让只读事务速度更快，也可以避免降低读写型事务的执行速度。与读写型事务相比，只读事务在延迟方便改善了 10倍之多。降低了复杂性，并大大提高了吞吐量。
只读事务需要在保证正确性的情况下提升效率。Spanner在只读事务中引入了两个正确性约束：
他们想让所有事务的执行依然是有序的。即使这个系统会并行执行很多事务，这些并发事务执行所生成的结果，它们即得讲这些结果返回给client，也得讲这些修改落地到数据库。这些并发执行的事务所生成的结果必须和一次或者连续执行这些事务时所得到的结果一致。对于只读事务来说，一个只读事务的所有读操作可以看到在它执行之前的那个事务中的所有写操作所执行的结果。它必然无法看到在它之后所执行事务中的任何写操作所执行的结果。2.另一个约束是他们想要获取外部一致性的能力。（等同于线性一致性）当一个事务提交后，第二个事务开始执行。我们就会要求第二个事务能够看到第一个事务所做的所有写操作的结果。另一点就是这些事务，甚至是只读事务不应该看到过时的数据。
通过这种外部一致性，让程序员很容易编写出正确的程序。如果不具备外部一致性的话，程序员就得对数据库所可能提供的任何异常情况进行处理。
why not read latest value?BEGIN print x,yENDT1,T2 R/WT3 R/OT1 T2 T3 ? T1 T3 T2?T1: Wx Wy CT2: Wx Wy CT3: Rx Ry// do not work,cann't read latest value----------------------------------------------> timeline Snapshot isolationSpanner解决R/O的方法。
Snapshot loslationTIMESTAMP:R/W ts = commit timeR/O ts = start time每个机器上都有一个时钟，各个时钟是同步的，通过时钟为我们生成时间。初次之外，我们给每个事务都分配累一个特定的时间，即时间戳，这个时间戳是由时钟哪里拿到的。在读写型事务来说，它的时间戳就是事务提交的时间。对于R/O，它的时间戳就是事务开始的时间。
我们想去设计这样一个snapshot isloation系统，即如果所有的事务都是按照时间戳顺序执行，那么它们所生成的结果都是一样的。我们会为每一个事务分配一个时间戳，然后我们会根据时间戳来对事务的执行顺序进行安排。如果我们按照时间戳的顺序来执行事务，那么事务就会得到正确的执行结果。
只读事务的工作方式： 当每个replia保存数据时，实际上它保存了该数据的多个版本。如果我们对每条数据库记录多次写入，它会在每次写入每条记录时，保存该记录的单独副本。它们中的每个副本都是和写入这些副本的事务的时间戳相关联的。
对于只读事务，发起读请求时，它会让每个读请求携带一个时间戳，不论那台服务器保存了该事务所涉及数据的副本，它都会去这个多版本数据库中查看并找到它所要的那条记录。这条记录的时间戳时最新的时间，但这条记录的时间戳要比该只读事务所指定的时间戳要小。
Spanner使用这种snapshot isloation的思路来解决只读事务所存在的问题，在读写型事务方面，Spanner仍然使用两阶段锁和两阶段提交来解决问题。
读写型事务会给它们自己分配一个时间戳，这个时间戳就是事务的提交时间，除此之外，他们使用的还是锁和2pc。
// SNAPSHOT ISOLATION // T1，T2 R/W T3 R/O @后面是时间戳 x@10 = 9 x@20 = 8 // commit后的值 y@10 = 11 y@20 = 12T1@10 Wx Wy CT2@20 Wx Wy CT3@15 Rx Ry 9 11 T1 T3 T2 // 执行顺序 SAFT TIMER/O如何避免本地数据不是最新的，导致读到旧数据：
R/O允许我们从同一个数据中心下所属的本地replia中读取数据，但这个本地replia可能属于Paxos follower中的少数派，即它并没有看到哦leader发送给它的最新日志条目。我们读取数据的时候，可能拿到的是更古老的版本。Spanner使用了一种叫做安全时间的概念来解决这个问题。
安全时间的范围是，每个replia会记录它从它的Paxos leader处收到的日志记录。Paper中表明，leader会严格按照时间戳增加的顺序来发送日志记录。所以，replia可以根据它从leader处拿到的最后一条日志记录来进行更新。如果我要去读取时间戳15所对应的值，但 replia只从Paxos leader处拿到了时间戳13所对应的日志条目，那么repelia就会推迟给我们返回数据。直到它从leadere处拿到了时间戳15所对应的日志条目时，它才会对我们进行响应。这样做就确保了，对于一个给定时间点的请求来说，直到replia从leader那里知道了该时间点前所发生的一切事情，它才会对该请求进行响应。这对读请求来说，可能会造成延迟。
之前所讨论的这些问题，都是基于所有不同服务器上的时钟都是完美同步的，但事实上，你没法如此精准地对时钟进行同步。
TIME SYNC？What if clocks aren’t synced?