分布式系统一致性和共识基础(一)

1. Consistency 一致性

一致性是分布式系统需要解决的基础问题，一致性是对外呈现的一致的状态或结果，一致性为什么很重要，举个扫码支付的例子。

小明到商场想玩夹娃娃机，他爸爸扫码支付了10元，娃娃取币机正常情况下需要弹出10个币，假设取币机出了问题，没接收到支付成功的通知，没弹出币就让人抓狂了。两个系统中订单状态不一致了，支付系统认为是支付成功，娃娃取币机认为订单待支付。

1.1一致性模型

一致性的模型定义，只列出一些常见的,一起学习研究。

(1) Strict Consistency严格一致性

一个处理器的写操作要即刻被其他处理器可见，即刻的定义可能是CPU的下一个时钟周期，这个模型过于严格，在分布式系统基本是不可能达到的。

(2) Sequential Consistency 顺序一致性

比严格一致性弱些，一个对变量的写操作不用马上被其它处理器可见，但不同处理器对变量的写操作的顺序对于所有处理器可见。

简单的可以理解为逻辑时钟，从所有处理器的视角，和从自身处理器视角看写操作执行的顺序是应当一致的。

这个逻辑时钟的论文Leslie Lamport发表于1978年, 不得不感慨美国学术的基础。

http://lamport.azurewebsites.net/pubs/time-clocks.pdf

而Linearizability线性一致性也是基于顺序一致性扩展，保证物理时间顺序，保证原子性。

Herlihy, M. and Wing, J. (1990) Linearizability: A Correctness Condition for Concurrent Objects

(3) Causal Consistency因果一致模型

因果相关的写操作，对系统的所有节点可见，且顺序一致，不相关则不同节点不同顺序。

https://link.springer.com/content/pdf/10.1007%2FBF01784241.pdf

(4) Eventual Consistency最终一致性

这个模型应该是我们最常见的，算是弱一致性，采用主动复制机制，获取最新数据。

我们在互联网应用中会大量看到，继续小明换币例子，如果能有一些机制主动去查询支付订单成功，就可以补偿业务补发购买的游戏币。很多分布式应用可能在操作会失败，但是也会提供一些补偿机制，对账机制，获取最新业务数据后重新恢复正常业务。

1.2 CAP原理

分布式系统一大重要原理。即分布式系统对于三个要素Consistency一致性，Availability可用性，Partition tolerance分区容忍性，不能同时保证两个以上特性。

一致性： 每次读返回最近的写结果或错误，所有的节点同一时刻看到同一结果。

可用性: 每次请求都能返回非错误的响应，但不保证返回最近写的结果。

分区容忍性: 系统在消息网络或某些节点出错的时候仍能提供服务。

现实中不同的系统对于CAP都有不同的需要。

(1) 弱一致性

我们平常看的网站，甚至购物网站，后台发布的文章内容也不是马上能看到对应页面变化，一些网站有很多机器和集群，甚至部署也是批量更新等，但是基本不影响使用。

(2) 弱可用性

例如对一致性要求高，发现后台或分布式哪些节点故障了，直接提示系统不能用了，好像一些柜员机，取票机等。

(3) 弱分区容忍

互联网上可是不少单机的应用, 没分区 :p

1.3 ACID事务

ACID特性通常用于数据库的事务

Atomicity原子性：保证每个事务操作要么成功，要么数据库保持不变。

Consistency一致性：事务保证数据库状态一致，无中间状态。

Isolation隔离级别: 用于并发事务控制，不同隔离级别可影响未完成交易的脏读，幻影读，可重复读，串行隔离级别最高。

Durability: 持久: 事务一旦提交就持久化保存了。

Java体系的XA两段提交标准的Atomikos，JOTM, Bitronix事务资源管理器，大多的关系型数据库都支持XA.

国内出名些分布式数据库, 阿里的OceanBase, PingCAP的TiDB, 微信的PhxSQL.

在事务要求不高的场景，例如以前蛮多PHP直接用MySQL的myisam引擎，不支持事务，但插入和查询都快，业务数据关联一致性就多靠代码去检查维护，有点最终一致性的味道，只是麻烦些。

2. Consensus共识

共识和一致性有点类似， 不过共识关注于如何达到一致性， 强调的是过程，共识的定义是对proposal提案达成一致的过程。

我们先学习一下常用的算法。

2.1 Paxos算法

又是Leslie Lamport的论文<<The Part-Time Parliament>>

http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos

一千年以前，爱琴海的Paxos岛屿商业很兴旺，政府准备从古老的神权管理转为议会管理，但是生意优先，没人愿意亲自跑到议会表决，议员只好在议会大厅进进出出传递消息运作。

Paxon的文明被外部入侵摧毁，考古学家只是恢复了Paxon议会协议的部分内容。

议会的主要职责是确定法律，市民只知道做生意，都不愿意到议会大厅当秘书，所以每个议员只好用一个账本记录他们之前通过的所有条例。

例如议员 Λ ̆ ινχ∂她的账本写着

155: The olive tax is 3 drachmas per ton

第155条法令, 橄榄油每吨的税收是3个银币，一旦审议通过就用不涂改的墨水记录在她自己的账本上。每个议员都在各自这样记录该条例，保证内容一致没冲突。

如果议员Φισ∂ρ记录了

132: Lamps must use only olive oil

则其它议员不会记录不同的内容，但是可能又一些议员的账本会没有132条法令，因为他们可能没听见审核通过了该法令。

这样的账本一致性是不完善的，有可能很多账本都是空的，所以需要一些措施保证法令都通过了且都记录在各自的账本。

在现代的议会，法令的通过可以被不同意的议员反对而不能通过。 而在Paxon，议员间相互信任，他们愿意通过任何已提交的法案，但也存在一些问题。例如对于法令

37: Painting on temple walls is forbidden

一组议员审议通过了后去参加宴会去了，而另外一组议员来到了议会大厅，根本不知道之前通过的法令，而且他们又通过了一条相冲突的法令

37: Freedom of artistic expression is guaranteed

这样一致性丢失了，除非足够的议员能呆在大厅足够的时间。而这些议员都不愿意削减他们的户外活动时间，但是议员都能保证，在议会大厅的时候，他们和助手都会迅速的处理议会的所有事情。这个保证就让Paxon设计出他们的议会协议：

如果大部分的议员在会议大厅，且足够长的时间之内，没人进入或离开大厅，期间任意议员的提议都会被通过，每个通过法令都会记录在各自的记账本上。

设想

议员还需要一些额外资源才能实现该协议。他们需要坚固的记账本，笔和以可涂改的墨水，他们可能会在账本的背后记录一些备忘录提醒自己在议会的工作任务，通过的法令在账本上不可改变，但是备忘录可删除。议员可能还需要一个计时的沙漏。

议员随时带账本在身边，账本是用最好的羊皮纸制造，只用来记录重要的东西。其它日志只用普通的纸记录。

议会大厅传导声音差，没法进行演讲，议员聘请一个或多个信使，让他们帮忙传递消息给其它议员。可以保证信使不篡改消息，但是他们可能会忘记曾经传递过消息，可能会重传。和议员一样，信使只在部分时间完成他们的工作。信使有时会离开议会去处理自己业务，例如在传递消息前，会去航行6个月去运输货物，或者不回来，消息可能会丢失。

虽然议员和信使可以在任何时候进入或者离开会议大厅，但在大厅的时候，他们是全心投入议会的事宜，信使会很快的传递消息，议员会快速的响应接收的消息。

具体的算法推导有点晦涩，后面在论文<<Paxos Made Simple>>做了简化。

http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

定义了三个角色：proposers, acceptors, leaners,

通过提议分两个阶段执行

一. Prepare准备阶段

(1) Proposer选择一个proposal提案编号n发送到大多的acceptors

(2) Acceptor收到prepare请求后，如果提案编号n大于已回复的提案的编号，那么acceptor将回复proposer承诺不再受理小于n提案， 而且回复包含之前受理过的最高编号的提案内容。

二. Commit提交阶段

(1) 如果proposer从大多的acceptors接收到了自己编号为n的提案的响应，proposer会发送一个accept请求给这些acceptors, 提案编号是n,值是v, 而v值是响应中最高编号提案对应的值， 如果响应没任何最高编号提案信息，则proposer自己填充任意值。

(2) 如果一个acceptor收到提案编号为n的accept请求，它将接受这个请求，如果它已经响应过编号大于n的prepare请求则不接受。

Learner学习者如何得知通过的决议呢?

每个acceptor接受提案的时候，会响应所有的learners提案的内容。当然通知会失败，learner也可以直接询问acceptor接受过的提案，或者让proposer发出一个新的提案请求去查询和确认。这些都可待扩展。

注意：这里提到的大多数的acceptors, 应该是要超过一半以上节点才能正常工作才能大概率的达成共识。这个是不是和Apache Zookeeper必须部署2N+1个节点有点类似， 我们来接着学习Raft算法。

2.2 Raft算法

Paxos算法较粗，后续不断有一些优化算法， 如Fast Paxos, Muti-pPaxos, Raft.

Raft在Apache Zookeeper中得到应用，Hadoop, Dubbo等集群中使用.

Raft论文<<In Search of an Understandable Consensus Algorithm>>

https://raft.github.io/raft.pdf

算法三个三个角色：Leader, Candidate, Follower

开始所有节点都是Follower.

时间超时没收到Leader请求, 则转换为Candidate进行选举。

Candidate收到大多的选票，一般超过一半, 成为Leader。

当发现服务器有更高更新的任期的时候，则降为Follower.

时间轴被分为不同的任期

Leader很重要，最多只有一个，负责受理日志的提交， 向Flollower日志的复制。

以上提到的Paxos和Raft算法，实际默认网络节点是可信任的， 只是节点可能存在节点奔溃问题， 这种类型的算法实际我们统称为Crash Fault Tolerant/CFT算法， 也成为非拜占庭Byzantine Fault Tolerant/BFT算法。

没想到一写内容那么多，为了保证质量， 专门在下篇介绍拜占庭算法。

http://www.javatree.cn/news/3d56a70d2d8641eb9961ef61b7d47e5a