分布式系统中有个著名的原则CAP原则，C为Consistency(一致性)、A为Availability(可用性)、P为Partition tolerance(分区容错性)。这里主要介绍下分布式环境下如果达到一致性。
说到一致性不得不说下经典的拜占庭问题。
拜占庭问题
话说一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。
系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。
拜占庭问题其实是指在一个可妥协的通信网络中实现分布式协议的问题，也就是在不可靠的环境中建立一个可靠的系统的问题。
假始那些忠诚（或是没有出错）的将军仍然能通过多数决策来决定他们的战略，便称达到了拜占庭容错。
PBFT
PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法，复杂度过高O(N^2)。PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。
PBFT是一个三阶段算法，分为Pre-Prepare、Prepare和Commit。PBFT中有几个概念需要了解下，所有的节点称为副本，这些副本有两个角色，分别为主节点(primary)和备份节点(backups)，所有的副本在一个被称为视图(View)的轮换过程中运作。主节点和备份节点是针对视图而言，视图是连续编号的整数。在某个视图中，从副本中选出一个副本为主节点，选择算法为p = v mod |R|，其中v是视图编号，|R|为副本个数，p为副本编号，除主节点之外所有的节点都为备份节点。当主节点失效的时候就需要启动视图更换过程。
知道上述概念之后，来看下算法的具体流程：
其中0为主节点，123为备份节点，3宕机无法响应请求主节点0接收到客户端C发来的请求request，给请求分配一个序列号n，然后向所有备份节点群发预准备消息，预准备消息的格式为<
假如集群中存在背叛者，也就是有一些伪造信息，这种情况称为拜占庭错误，伪造信息的节点称为拜占庭节点。其一致性算法为BFT（Byzantine Fault Tolerance），上文介绍的PBFT就是一个拜占庭容错算法。如果集群中不存在背叛者，都是忠诚者，只是这些忠诚者由于某种原因无法正常工作，这种情况称为非拜占庭错误。其一致性算法为CFT（Crash Fault Tolerance）。
下面我们就介绍两个非拜占庭一致性算法Paxos和Raft。
Paxos
Paxos算法为非拜占庭一致性算法，运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。
Paxos算法中的角色分为Proposer和Acceptor，Proposer是提案者，用来发起提案（Proposal），Acceptor是决策者，用来接收和响应Proposer提出的提案。这个算法的场景是一个或多个提议进程（Proposer）可以发起提案（Proposal），需要在所有提案中选取某一个提案，使其在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。
