· ☕ 1 分钟
CAP BASE BASE 是 Basically Available(基本可用)、Soft state(软状态)和 Eventually consistent(最终一致性)三个短语的简写
复制状态机 https://zhuanlan.zhihu.com/p/86999794
复制状态机的思想是一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中。状态机的状态能够并且只能通过外部命令来改变。
上文提到的“一组状态变量”通常是基于操作日志来实现的。每一个复制单元存储一个包含一系列指令的日志，并且严格按照顺序逐条执行日志上的指令。因为每个状态机都是确定的，所以每个外部命令都将产生相同的操作序列 (日志)。又因为每一个日志都是按照相同的顺序包含相同的指令，所以每一个服务器都将执行相同的指令序列，并且最终到达相同的状态。
综上所述，在复制状态机模型下，一致性算法的主要工作就变成了如何保证操作日志的一致性。
服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中。它与其他服务器上的一致性模块进行通信以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。
复制状态机之所以能够工作是基于下面这样的假设:如果一些状态机具有相同的初始状态，并且它们接收到的命令也相同，处理这些命令的顺序也相同，那么它们处理完这些命令后的状态也应该相同。因为所有的复制节点都具有相同的状态，它们都能独立地从自己的本地日志中读取信息作为输人命令，所以即使其中一些服务器发生故障，也不会影响整个集群的可用性。不论服务器集群包含多少个节点，从外部看起来都只像是单个高可用的状态机一样。
复制状态机在分布式系统中常被用于解决各种容错相关的问题，例如，GFS、HDFS、Chubby、ZooKeeper和etcd等分布式系统都是基于复制状态机模型实现的。
FLP不可能性 No completely asynchronous consensus protocol can tolerate even a single unannounced process death.
在异步通信场景下，任何一致性协议都不能保证：只有一个进程失败，其他非失败进程能达成一致。这里的"unannounced process death" 指的是一个进程发生了故障，但其他节点并不知道，继续认为这个进程还没有处理完成或发生消息延迟了。
举个例子来说，甲、乙、丙三个人各自分开进行投票(投票结果是0或1)。他们彼此可以通过电话进行沟通，但有人会睡着。 例如:甲投票0，乙投票 1，这时候甲和乙打平，丙的选票就很关键。然而丙睡着了，在他醒来之前甲和乙都将无法达成最终的结果。即使重新投票，也有可能陷入无尽的循环之中。
根据FLP定理，实际的一致性协议(Paxos、 Raft等)在理论上都是有缺陷的，最大的问题是理论上存在不可终止性!至于 Paxos 和 Raft协议在工程的实现上都做了哪些调整(例如，Paxos 和 Raft都通过随机的方式显著降低了发生算法无法终止的概率)，从而规避了理论上存在的问题，下文将会有详细的解释。