distributed

Two-phase Commit

二阶段提交的算法思路可以概括为:

参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

二阶段是指:

第一阶段 - 请求阶段(表决阶段)

第二阶段 - 提交阶段(执行阶段)

请求阶段(表决)：

事务协调者通知每个参与者准备提交或取消事务，然后进入表决过程，参与者要么在本地执行事务，写本地的redo和undo日志，但不提交，到达一种”万事俱备，只欠东风”的状态。请求阶段，参与者将告知协调者自己的决策: 同意(事务参与者本地作业执行成功)或取消（本地作业执行故障）

提交阶段(执行):

在该阶段，写调整将基于第一个阶段的投票结果进行决策: 提交或取消

当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务

参与者在接收到协调者发来的消息后将执行响应的操作

缺点

执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他节点访问资源不得不处于阻塞状态。
一旦协调者发生故障，参与者会一直阻塞下去。
数据不一致。在第二阶段中，当协调者向参与者发送commit请求之后，发生故障，这回导致只有一部分参与者接受到了commit请求。

Three-phase Commit

三阶段提交协议在协调者和参与者中都引入超时机制，并且把两阶段提交协议的第一个阶段分成了两步: 询问，然后再锁资源，最后真正提交。

canCommit阶段

协调者向参与者发送commit请求，参与者如果可以提交就返回yes响应，否则返回no响应。

preCommit阶段

协调者根据参与者canCommit阶段的响应来决定是否可以继续事务的preCommit操作。

a) 协调者从所有参与者得到的反馈都是yes:

那么进行事务的预执行，协调者向所有参与者发送preCommit请求，并进入prepared阶段。

参与和接收到preCommit请求后会执行事务操作，并将undo和redo信息记录到事务日志中。

如果一个参与者成功地执行了事务操作，则返回ACK响应，同时开始等待最终指令

b) 协调者从所有参与者得到的反馈有一个是No或是等待超时之后协调者都没收到响应:

中断事务，协调者向所有的参与者发送abort请求。

参与者在收到来自协调者的abort请求，或超时后仍未收到协调者请求，执行事务中断。

doCommit阶段

协调者根据参与者preCommit阶段的响应来决定是否可以继续事务的doCommit操作。

a) 协调者从参与者得到了ACK的反馈:

协调者接收到参与者发送的ACK响应，那么它将从预提交状态进入到提交状态，并向所有参与者发送doCommit请求。

参与者接收到doCommit请求后，执行正式的事务提交，并在完成事务提交之后释放所有事务资源，并向协调者发送haveCommitted的ACK响应。

那么协调者收到这个ACK响应之后，完成任务。

b) 协调者从参与者没有得到ACK的反馈, 也可能是接收者发送的不是ACK响应，也可能是响应超时:执行事务中断。

2PC vs 3PC

在2PC的准备阶段和提交阶段之间，插入预提交阶段，使3PC拥有CanCommit、PreCommit、DoCommit三个阶段。

PreCommit是一个缓冲，保证了在最后提交阶段之前各参与节点的状态是一致的。

Read Uncommitted

Read Committed

Repeatable Read

Serializable

Snapshot Isolation

快照隔离多采用MVCC实现，记录事务开始的时间点，将这个时间点之前的数据看作是一个快照，所有读操作都只读取该时间点之前的数据。

当然本次事务中Update/Insert/Delete的操作对本次事务也是可见的。

但是该事务之后新的事务所产生的数据对本次事务是不可见的.

Percolator

Percolator 是为了提升Google的搜索引擎索引系统效率而设计的。主要是用于增量事务，并且延迟不敏感，因为 Percolator里很多设计都是高延时的，所以要求应用不太在意延时。

Percolator 事务依赖 Bigtable 时间戳的多版本数据保存和事务。每个Value都绑定了一系列元数据列，写入到 Bigtable 的同一个本地组（Locality group）里。因为一个 Locality group 的物理部署在同一组 Bigtable 节点上，这样可以实现对同一个 Locality group 的多列进行原子操作，也能加快关联数据的查找速度。

Percolator 提供跨表、跨行的分布式事务，隔离级别为快照隔离（snapshot-isolation）。快照隔离级别中，如果两个事务同时修改同一个行，那么事务冲突，其中一个事务必须回滚然后重试。

Percolator中为事务提供支持的元数据是列的方式存储在Bigtable对应的行中。

可以认为Percolator为每行记录都新增了一些隐藏列，这些列保证了事务的正确执行或回滚。

快照隔离需要能够有效的处理写冲突，当有一个事务A和一个事务B同时写入同一个cell时，最多只有一个能提交成功。

Google搜索引擎建立网页索引：通过处理网页库，会建好一个索引库。之后爬虫会新抓下来少量页面。

MapReduce批处理方式是新旧网页合并在一起，建立新的索引库。

Percolator采用了新的增量更新的方式，将新抓来的页面增量地更新到原来的索引库，形成新的索引库。

处理新抓取的网页时，系统会维持一些索引库的不变量(invariants)，建立索引的过程是一个有特定数据约束的过程。

将一个数据集从一个一致的状态修改变为另一个一致的状态，这中间恰是事务Transaction要解决的问题。

Percolator的设计包含两个相对独立的要点，即分布式事务和观察者机制实现的通知。

分布式事务是为了支持应用通过事务方式方便地访问数据，观察者机制是为了组织增量计算。

Percolator实现2PC协议来支持分布式事务时，其实现过程与我们所见过的直接构建在OS之上的2PC实现差别非常大。

并行事务分为3种情况:

读-读

由于快照隔离read并不加锁，所以读-读操作并不会冲突，事务并不需要aborted。

读-写

执行Get操作时，需要检查[0,start_timestamp]之间的lock信息。

如果此时lock列中有数据时，说明目前该cell正在被一个事务操作，那么Get操作等待该事务完成，lock释放后再读取数据。

如果没有发现lock数据，那么Get操作获取write列中在[0，start_timestamp]之间最新数据的timestamp，该timestamp指向了该get操作可以访问的最新的数据。

这种情况下读事务等待写事务完成，也不会需要aborted。

写-写

假如事务A需要修改一个cell，但是看到了cell已经存在lock锁，那么说明可能存在事务B正在对cell进行修改，此时事务B处于两阶段提交的第一阶段。两个事务发生冲突，需要aborted。

假如事务A需要修改cell，并且lock列中没有发现有数据，但是write列中有数据，并且该write列的时间戳晚于事务A的开始的时间戳，说明在事务A开始后，有事务B已经修改了cell的值，此时的B处于两阶段提交的第二个阶段或者已经提交成功，存在冲突，事务A需要aborted。

如果write列的时间戳早于事务A开始的时间戳的话，说明事务B结束后事务A才开始，这时候就没必要aborted了，所以除了看write列是否有数据外，还要看write列的时间戳是否跟A有冲突。

MVCC

事务隔离在数据库系统中有着非常重要的作用，因为对于用户来说数据库必须提供这样一个“假象”：当前只有这么一个用户连接到了数据库中，这样可以减轻应用层的开发难度。但是，对于数据库系统来说，因为同一时间可能会存在很多用户连接，那么许多并发问题，比如数据竞争（data race），就必须解决。在这样的背景下，数据库管理系统就必须保证并发操作产生的结果是安全的，通过可串行化（serializability）来保证。

虽然 Serilizability 是一个非常棒的概念，但是很难能够有效的实现。一个经典的方法就是使用一种两段锁（2PL）。

通过 2PL，DBMS 可以维护读写锁来保证可能产生冲突的事务按照一个良好的次序（well-defined) 执行，这样就可以保证 Serializability。但是，这种通过锁的方式也有一些缺点：

读锁和写锁会相互阻滞（block）。
大部分事务都是只读（read-only）的，所以从事务序列（transaction-ordering）的角度来看是无害的。如果使用基于锁的隔离机制，而且如果有一段很长的读事务的话，在这段时间内这个对象就无法被改写，后面的事务就会被阻塞直到这个事务完成。这种机制对于并发性能来说影响很大。

多版本并发控制（Multi-Version Concurrency Control） 以一种优雅的方式来解决这个问题。在 MVCC 中，每当想要更改或者删除某个数据对象时，DBMS 不会在原地去删除或这修改这个已有的数据对象本身，而是创建一个该数据对象的新的版本，这样的话同时并发的读取操作仍旧可以读取老版本的数据，而写操作就可以同时进行。这个模式的好处在于，可以让读取操作不再阻塞，事实上根本就不需要锁。这是一种非常诱人的特型，以至于在很多主流的数据库中都采用了 MVCC 的实现。

Chandy Lamport Algorithm

Flink处理流，支持三种级别语义:

At Most once: 消息最多被处理一次，sender发出消息之后，receiver无论是否处理成功，都不会再重发。

At Least once: 消息至少被处理一次，sender发出消息之后，receiver处理失败或者处理成功但是回复sender确认成功的时候超时，都会重发，直到sender确认成功。

Exactly once: 消息恰巧被处理一次。

Flink中实现 Exactly once，采用的是Asynchronous barrier snapshots 算法，而该算法是Chandy Lamport Algorithm的轻微变种。Chandy Lamport Algorithm 算法是一个采用分布式快照算法来解决记录分布式全局状态一致的算法。

快照算法是一个用来在分布式同创建快照来是分布式系统的状态保持一致的算法，因为分布式系统中没有一个全局共享的内存和全局时钟，所以它基本是不可能的

Single Token Conservation

End to End Argument

端到端的可靠通信，只能通过通信两端的application层来保证，而中间件只能提高效率，而无法保证通信的可靠性。

举个现实世界的例子：A要告诉B一件事情，A要保证B“知道”了这件事情是“高层意图”，声波的传递是“低层”，面对面说话，物理世界“保证”声波传递到了B，但是由于B可能在想别的事情走神儿了，或者由于噪音没听清，所以B未必最终“知道”了这件事。

TCP的可靠，只是保证TCP层，两端的OS的socket实现把数据从一端“确定，可靠的”放在了另外一端的socket buffer里。

Gossip Protocol

Gossip Protocol(Epidemic Protocol)是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用。Gossip Protocol利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip Protocol是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。

Gossip Protocol是可扩展的，一般需要 O(logN) 轮就可以将信息传播到所有的节点(N 代表节点个数)。每个节点仅发送固定数量的消息，并且与网络中节点数目无关。在数据传送的时候，节点并不会等待消息的 ack，所以消息传送失败也没有关系，因为可以通过其他节点将消息传递给之前传送失败的节点。

网络中任何节点的重启或者宕机都不会影响 Gossip Protocol的运行。

Gossip Protocol是去中心化的协议，集群中的所有节点都是对等的，任何节点出现问题都不会阻止其他节点继续发送消息。

Gossip Protocol实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。

Gossip Protocol 类型：

Anti-Entropy（反熵）：以固定的概率传播所有的数据
Rumor-Mongering（谣言传播）：仅传播新到达的数据

Anti-Entropy 每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。Anti-Entropy 方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，以此不会频繁使用。Anti-Entropy 使用simple epidemics的方式，所以其包含两种状态：susceptible 和 infective，这种模型也称为 SI model。处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新；处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点。

Rumor-Mongering: 当一个节点有了新的信息后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息，所有大大减少了通信的负担。Rumor-Mongering 使用complex epidemics方法，相比 Anti-Entropy 多了一种状态：removed，这种模型也称为 SIR model。处于 removed 状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。因为 Rumor 消息会在某个时间标记为 removed，然后不会发送给其他节点，所以 Rumor-Mongering 类型的 Gossip Protocol有极小概率使得更新不会达到所有节点。

节点间的交互方式主要有三种: Push、Pull 以及 Push&Pull。

Push：发起信息交换的节点 A 随机选择联系节点 B，并向其发送自己的信息，节点 B 在收到信息后更新比自己新的数据，一般拥有新信息的节点才会作为发起节点。

Pull：发起信息交换的节点 A 随机选择联系节点 B，并从对方获取信息。一般无新信息的节点才会作为发起节点。

Push & Pull：发起信息交换的节点 A 向选择的节点 B 发送信息，同时从对方获取数据，用于更新自己的本地数据。

Time, Clocks and the Ordering of Events in a Distributed System

Round Robin

Round Robin 俗称哈希取模法，常用数据分片方法。

假设有N台物理机，H(key) = hash(key) mod N

Google Percolator

Percolator是由Google公司开发的、为大数据集群进行增量处理更新的系统，主要用于google网页搜索索引服务。使用基于Percolator的增量处理系统代替原有的批处理索引系统后，Google在处理同样数据量的文档时，将文档的平均搜索延时降低了50%。

Percolator的特点如下

为增量处理定制
处理结果强一致
针对大数据量

Percolator为可扩展的增量处理提供了两个主要抽象：

基于随机存取库的ACID事务
观察者(observers): 一种用于处理增量计算的方式

Percolator 提供了跨行、跨表的、基于快照隔离的ACID事务。

Percolator 通过一个全局的授时服务器给予事务一个全局时间戳来解决分布式环境下事务的全局时序问题；通过经典的两阶段提交来解决分布式事务原子提交的问题。

Percolator 不仅仅是一个改进版的两阶段提交，它涵盖的内容更多，可以认为是一个完整的分布式事务解决方案，它还包括了依据全局时间戳实现 Snapshot Isolation 隔离级别的并发控制协议，并给出了在故障发生如何进行自动 failover 的细节。

Lamport 逻辑时钟

在分布式系统中，一个事件发生在另一个事件之前，用它描述了事件的偏序关系。给出了一种分布式算法，该算法用于同步逻辑时钟系统，逻辑时钟系统可以用于确定事件的全序关系。全序关系的用途被作为一种解决同步问题的方法给出。这个方法之后被专门用于解决同步物理时钟，并且限定同步时钟的误差。

在我们的思维中，时间是一个非常基础的概念。它来源于更基础的概念——时间的发生顺序。事件时间顺序的概念贯穿我们对系统的思考，但在分布式系统中，我们需要重新审视这个概念。

分布式系统由一系列空间上分离，通过交换信息来通信的进程组成。与单个进程内事件发生的间隔时间相比，系统中消息传递延迟不可以被忽略，这个系统可以被认为是一个分布式系统。

在一个分布式系统中，有时候无法确定一个事件发生于另一个事件之前。而发生之前的关系只是系统中事件的一个偏序关系。我们发现由于人们没有弄清楚这一点而导致一些问题问题的出现。

我们讨论偏序关系，并给出一个分布式算法将其拓展为所有事件的全序关系。这个算法能够提供有效的机制来实现一个分布式系统。我们通过一个解决同步问题的简单方法来说明它的用法。不幸的是，如果通过这个算法得出的顺序和用于感知的不一样，可能会发生异常的行为。这可以通过引入真实的物理时钟来避免。我们描述了同于同步这些时钟的简单方法，并且推导出了时钟偏差的范围。

Spanner

Spanner 的特点是基于时间戳多版本数据库，查询语言基于SQL，支持分布式事务，支持跨行事务，支持原子更新，副本管理可以随着数据量增长动态分配，也可以由应用程序控制。数据在数据中心中的迁移对应用层是透明的。

Spanner 设计有两个难点:对外的读写一致性，全局读的强一致性，即某个时间点在整个集群任意节点读取数据都是一致的。

向量时钟

向量时钟是在 Lamport 时间戳基础上演进的另一种逻辑时钟方法，它通过向量结构不但记录本节点的 Lamport 时间戳，同时也记录了其他节点的 Lamport 时间戳，因此能够很好描述同时发生关系以及事件的因果关系。

PS：因果关系指的是时序关系，即时间的前后，并不是逻辑上的原因和结果。时间戳如无特别说明，都指的是逻辑时钟的时间戳，不是物理时钟的时间戳。

Lamport 逻辑时钟算法，提供了一种判断分布式系统中事件全序关系的方法：如果 a -> b，那么 C(a) < C(b)，但是 C(a) < C(b) 并不能说明 a -> b。也就是说C(a) < C(b) 是 a -> b 的必要不充分条件，我们不能通过 Lamport 时间戳对事件 a、b 的因果关系进行判断。

ZAB

ZAB(Zookeeper Atomic Broadcast)，看到Atomic和Broadcast两个词，应该就能大概明白ZAB的主要工作方式了。ZAB是一个为Zookeeper量身定制的支持崩溃恢复的原子广播协议，用于保障各副本之间数据一致性。

ZAB协议中存在两种角色，Leader和Follower。Leader负责数据的读和写请求，Follower只负责读请求，外部应用可以给任意的Zookeeper端发送请求，所以如果是写请求，就会转给Leader处理，读的话则就地响应。这样做同时也是为了达到所有写请求都能有序处理的效果。

原子可以理解为事务，Zookeeper收到一个写请求后，对其分配一个全局唯一且递增的Zxid，然后将该请求转化为事务Proposal，严格按照请求的接收次序放到针对每个Follower的FIFO队列中，即向集群中所有Follower广播该数据，Follower成功收到数据后，会发送Ack给Leader，当Leader收到的Ack超过半数，则向Follower发送commit命令，完成事务的提交。

ZAB事务的提交过程中是遵循2PC协议的，即事务预处理请求和事务提交是分成两阶段进行的，不同之处在于2PC要求所有副本应答，而ZAB只要求超过半数的副本应答即可，这样也避免了2PC单点超时造成阻塞的问题。

崩溃恢复

各类Consistency对比小结

Linearizability

node1写A, node2写B, 写A操作在写B开始前完成, B一定覆盖A; 对于多个观察者来说, 任意一个观察者看到B后, 其他观察者必须只能观察到B; 或者B操作完成后, 所有观察者都只能观察到B;

Sequential

Causality

混沌工程（Chaos Engineering）

Chaos Engineering is the discipline of experimenting on a distributed system in order to build confidence in the system’s capability to withstand turbulent conditions in production.

混沌工程在分布式系统上进行由经验指导的受控实验，观察系统行为并发现系统缺陷，以建立对系统在规模增大时因意外条件引发混乱的能力和信心。

混沌工程和传统测试在关注点和工具集上都有很大的重叠。在Netflix的很多混沌工程实验研究的对象都是基于故障注入来引入的。混沌工程和这些传统测试方法的主要区别在于：混沌工程是发现新信息的实践过程，而故障注入则是对一个特定的条件、变量的验证方法。

Reference: