1.3 分布式基础问题与理论

1.3.1 拜占庭将军问题

拜占庭将军问题是1982年由图灵奖获得者莱斯利·兰波特（Leslie Lamport）在论文“The Byzantine Generals Problem”中提出的分布式对等网络通信容错问题。其主要观点是，在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。在分布式计算中，不同的计算机通过通信交换信息并达成共识，从而按照同一套协作策略行动；但有时系统中的成员计算机可能会发送错误的信息，用于传递信息的通信网络也可能导致信息损坏，使网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

为了便于理解，莱斯利·兰波特在其论文中通过拜占庭将军的故事将问题描述为：一群拜占庭将军各带领一支军队共同围困一座城市拜占庭（东罗马帝国的首都）。如图1-13所示，为了简化问题，军队的行动策略只有两种：进攻（Attack，后面简称A）或撤退（Retreat，后面简称R）。如果这些军队不是统一进攻或撤退，就可能造成灾难性后果，因此将军们必须通过投票来达成一致策略：同进或同退。因为将军们分别在城市的不同方位，所以他们只能通过信使互相联系。在投票过程中，每位将军都将自己的投票信息（A或R）通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以分析出共同的投票结果，从而决定行动策略。

这个抽象模型的问题在于：将军中可能存在叛徒，他们不仅会发出误导性投票，还可能选择性地发送投票信息。由于将军之间需要通过信使通信，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。即使在保证所有将军都忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通信可靠性来解决问题。假使那些忠诚（或没有出错）的将军仍然能通过多数投票来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。

将上述故事映射到分布式系统中，将军便成了机器节点，信使就是通信系统。

莱斯利·兰伯特在其论文中提出了几个解决方案，达到了拜占庭容错。其中一个为BFT（Byzantine Fault Tolerant，拜占庭容错）算法，假设将军总数是N，叛徒将军数为F，则当N≥3F+1时，问题才有解，才能达成共识。只要有问题的将军的数量不到三分之一，仍可以达到“拜占庭容错”，原因是把同样的标准下放到“军官与士官的问题”时，在背叛的军士官不足三分之一的情况下，有问题的军士官可以很容易地被发现。比如有军官A、士官B与士官C，当A要求B进攻，却要求C撤退时，即使B与C交换所收到的命令，B与C仍不能确定是否A有问题，因为B或C可能将已篡改的消息传给对方。也就是说，当将军总数为3、叛徒将军数为1时，系统无法达成一致或拜占庭容错。当将军总数为4、叛徒将军数为1时，系统可以达成一致或拜占庭容错。以函数来表示，将军的总数为n，其中背叛者的数量为t，则只要n＞3t就可以容错。

拜占庭容错算法是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能出现故障或作恶的情况下如何达成共识。长期以来，拜占庭问题的解决方案都存在运行过慢或复杂度过高的问题，实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）算法解决了该问题。其核心思想是：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。也就是说，利用不断的信息交换让可行的节点确认哪一个记录选择是正确的，即发现其中的背叛者。PBFT算法本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息，通信代价是非常高的。通常，采用PBFT算法，节点间的通信复杂度是节点数的平方级。

1999年，这一算法由Castro和Liskov在论文“Practical Byzantine Fault Tolerance and Proactive Recovery”中提出。该算法首次将拜占庭容错算法的复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在恶意节点不超过总数1/3的情况下同时保证安全性和活性。PBFT算法采用密码学相关技术（RSA签名算法、消息验证编码和摘要）确保消息在传递过程中无法被篡改和破坏。

1.3.2 Paxos算法

Paxos问题是指分布式系统中存在故障，但不存在恶意节点的场景（即消息可能丢失或重复，但无错误消息）下的共识达成问题，这也是分布式共识领域最为常见的问题。解决Paxos问题的算法主要有Paxos算法和Raft算法。

Paxos算法是分布式一致性算法，用来解决一个分布式系统如何就某个值（决议）达成一致的问题。但需要注意的是，Paxos经常被误称为“一致性算法”，但“一致性”和“共识”并不是同一个概念。Paxos是一种共识算法。

1990年，Leslie Lamport在其论文“The Part-time Parliament”中提出的Paxos共识算法，在工程角度实现了一种最大化保障分布式系统一致性的机制。Paxos算法被广泛应用于Chubby、ZooKeeper等分布式系统中。Leslie Lamport在论文中通过一个故事描述了Paxos算法问题：古代爱琴海的Paxos岛通过议会的形式修订法律，执法者在议会大厅中表决通过法律，并通过服务员传递纸条的方式交流信息，每个执法者会将通过的法律记录在自己的账目上，问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会大厅，服务员也有可能重复传递消息，并随时可能有新的执法者（或者是暂时离开的）回到议会大厅进行法律表决，因此，议会协议要求保证在上述情况下能够正确地修订法律并且不会产生冲突。

Paxos是首个得到证明并被广泛应用的共识算法，通过消息传递来逐步消除系统中的不确定状态。其基本思路类似于两阶段提交：多个提案者先要争取到提案的权利（得到大多数接受者的支持）；成功的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。

Paxos算法有时也被称为Paxos协议，它是少数在工程实践中被证实的强一致性、高可用的去中心化分布式协议。Paxos协议的流程较为复杂，但其基本思想却不难理解，类似于人类社会的投票过程。在Paxos协议中，有一组完全对等的参与节点，这组节点各自就某事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos协议中只要有超过一半的节点正常，就可以很好地对抗停机、网络分化等异常情况。

1.3.3 ACID原则

在数据库系统中，事务（transaction）是指由一系列数据库操作组成的一个完整的逻辑过程。例如，银行转账过程中要从原账户扣除金额和向目标账户添加金额，这两个数据库操作的总和构成一个完整的逻辑过程，不可拆分。这个过程被称为一个事务，具有ACID特性。

ACID是指数据库管理系统在写入或更新资料的过程中，为保证事务是正确可靠的所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）和持久性（durability）。

●原子性：一个事务中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（rollback）到事务开始前的状态，就像该事务从来没有执行过一样。也就是说，事务不可分割、不可约简。

●一致性：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。

●隔离性：数据库允许多个并发事务同时对其数据进行读写和修改，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据不一致。事务隔离分为不同级别，包括未提交读（read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（serializable）。

●持久性：事务处理结束后，对数据的修改是永久的，即便系统故障也不会丢失。

1.3.4 CAP定理

1.CAP定理的发展历史

1985年，Fischer、Lynch和Patterson三位学者证明了异步通信中不存在任何一致性的分布式算法（FLP impossibility），即在异步通信场景中，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性。因此，人们开始寻找分布式系统设计的各种因素。既然一致性算法不存在，找到一些设计因素并进行适当的取舍以最大限度地满足系统需求，就成为当时的重要议题。

2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM的分布式计算原则（Principles of Distributed Computing）研讨会上，首次提出了著名的CAP猜想。两年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了Brewer教授CAP猜想的可行性。从此，CAP理论正式在学术上成为分布式计算领域的公认定理，并深深地影响了分布式计算的发展。

CAP定理是指对于一个分布式计算系统来说，不可能同时满足一致性（consistency）、可用性（availability）和分区容错性（partition tolerance），这三项基本需求，最多只能同时满足其中的两项。

●一致性：所有节点访问同一份最新的数据副本。在分布式系统中的所有数据备份在同一时刻具有同样的值。

●可用性：对数据更新具备高可用性。集群中的部分节点出现故障后，集群整体还能响应客户端的读写请求。

●分区容错性：当分布式系统集群中的某些节点无法联系时仍能正常提供服务。分区是指是否允许集群中的节点之间无法通信。由于是分布式系统，必须满足分区容错性，因为网络的不可靠性必定会导致两个机器节点之间无法进行网络通信，从而导致数据无法同步。

2.CAP定理的应用

CAP猜想在被证实和规范化后，被正式称为CAP定理，极大地影响了大规模Web分布式系统的设计。当在分布式存储系统中应用CAP定理时，最多只能实现上述两项需求。而由于当前的网络硬件肯定会出现延迟或丢包等问题，因此分区容错性是必须要实现的。所以，我们在设计分布式系统时只能在一致性和可用性之间进行权衡。

事实上，在设计分布式应用系统时，这三项基本需求最多只能同时实现两项，不可能三者兼顾，如图1-14所示。

如果选择分区容错性和一致性，那么即使有节点出现故障，操作必须既一致又能顺利完成，所以必须100%保证所有节点之间有很好的连通性。这是很难做到的。因此，最好的办法就是将所有数据放到同一个节点中。但显然这种设计是不满足可用性的，即一旦系统遇到网络分区或其他故障，受到影响的服务就需要等待一定的时间，因此在等待期间系统无法对外提供正常的服务，即不可用，如BigTable、HBase。

如果要满足可用性和一致性，那么为了保证可用性，则数据必须要有副本（replica）。因此，系统显然无法容忍分区。当同一数据的两个副本被分配到两个无法通信的分区时，会返回错误的数据，如关系数据库。另外，需要明确的一点是，对于一个分布式系统而言，分区容错性是一个最基本的要求，因为分布式系统中的组件需要被部署到不同的节点。

最后分析满足可用性和分区容错性的情况。要满足可用性，说明数据必须要在不同节点中有副本。还必须保证在产生分区的时候操作仍然可以完成。那么，操作必然无法保证一致性，如Dynamo、Cassandra、SimpleDB。

3.CAP问题实例

为了让读者更好地理解CAP定理的概念，下面通过一个具体的分布式应用的例子进行说明。如图1-15所示，假如有两个应用A和B分别运行在两个不同的服务器N1和N2上。A负责向它的数据仓库（主存储器）写入数据，而B则从另一个数据库副本（备份存储器）读取数据。服务器N1通过发送数据更新消息给服务器N2来实现同步，以达到两个数据库之间的一致性。客户端应用程序调用put（d）方法更新数据d的值，应用A会收到该命令并将新数据通过write()方法写入它的数据库，然后服务器N1向服务器N2发送消息以更新在另一个数据库副本里的d′的值，随后客户端应用调用get（d）方法想要获取d的值，B会收到该命令并调用read()方法从仓库副本里读出d′的值，此时d′已经更新为新值，因此，整个系统看起来是一致的。

假如服务器N1和N2之间的通信被切断了（网线断了），如果希望系统是容错的，则将两个数据库之间的消息设定为异步消息，那么系统仍然可以继续工作，但是数据库副本内的数据不会更新，随后用户读到的数据便是过期的数据，这就造成数据的不一致。即使将数据更新消息设定为同步的也不行，这会使服务器N1的写操作和数据更新消息成为一个原子性事务，一旦消息无法发送，服务器N1的写操作就会随着数据更新消息发送失败而回滚，导致系统无法使用，违背了可用性。

CAP定理告诉我们，在大规模的分布式系统中，分区容错性是基本要求，所以要对可用性和一致性有所取舍。对于上面的实例，我们可以选择使用最终一致模型，数据更新消息可以是异步发送的，但如果服务器N1在发送消息时无法得到确认，那么它就会重新发送消息，直到服务器N2上的数据库副本与服务器N1达到一致为止，而客户端则需要面临不一致的状态。实际上，如果你从购物车中删除一个商品记录，它很可能再次出现在你的交易记录里，但是显然，相对于较高的系统延迟来说，用户可能更愿意继续他们的交易。对于大多数Web应用来说，牺牲一致性来换取高可用性是主要的解决方案。

1.3.5 BASE理论

ACID要求强一致性，通常用于传统的数据库系统。而BASE要求最终一致性，通过牺牲强一致性来达到可用性，通常用于大型分布式系统。BASE理论是对CAP中的一致性和可用性进行权衡的结果，其核心思想是：即使无法做到强一致性，每个应用也都可以根据自身业务特点，采用适当的方式使系统达到最终一致性。

BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistency（最终一致性）三个短语的缩写。BASE理论是对CAP中AP的扩展，通过牺牲强一致性来获得可用性，当出现故障时允许部分不可用，但要保证核心功能可用，允许数据在一段时间内是不一致的，但最终达到一致状态。满足BASE理论的事务，我们称之为“柔性事务”。

●基本可用：分布式系统在出现故障时，允许损失部分可用功能，保证核心功能可用。例如，电商网站交易付款出现问题后，依然可以正常浏览商品。

●软状态：允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性，即允许系统不同节点的数据副本之间进行同步的过程存在延时。由于不要求强一致性，因此BASE允许系统中存在中间状态（也叫软状态），该状态不影响系统可用性，如订单的“支付中”“数据同步中”等状态，待数据最终一致后状态改为“成功”状态。

●最终一致性：最终一致性是指经过一段时间后，所有节点数据都将会达到一致，即强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。如订单的“支付中”状态，最终会变为“支付成功”或者“支付失败”，使订单状态与实际交易结果达成一致，但需要一定时间的延迟、等待。