2.2 分布式计算的理论基础

2.2.1 ACID原则

ACID是数据库事务正常执行的四个原则，分别指原子性、一致性、独立性及持久性。

1.A（Atomicity）——原子性

原子性很容易理解，也就是说事务里的所有操作要么全部做完，要么都不做，事务成功的条件是事务里的所有操作都成功，只要有一个操作失败，整个事务就失败，需要回滚。

例如银行转账，从A账户转100元至B账户，分为两个步骤：①从A账户取100元；②存入100元至B账户。

这两步要么一起完成，要么一起不完成，如果只完成第一步，第二步失败，钱会莫名其妙少了100元。

2.C（Consistency）——一致性

一致性也比较容易理解，也就是说数据库要一直处于一致的状态，事务的运行不会改变数据库原本的一致性约束。

例如现有完整性约束a + b = 10，如果一个事务改变了a，那么必须得改变b，使得事务结束后依然满足a + b = 10，否则事务失败。

3.I（Isolation）——独立性

所谓的独立性是指并发的事务之间不会互相影响，如果一个事务要访问的数据正在被另外一个事务修改，只要另外一个事务未提交，它所访问的数据就不受未提交事务的影响。

例如交易是从A账户转100元至B账户，在这个交易还未完成的情况下，如果此时B查询自己的账户，是看不到新增加的100元的。

4.D（Durability）——持久性

持久性是指一旦事务提交后，它所做的修改将会永久保存在数据库上，即使出现宕机也不会丢失。

这些原则解决了数据的一致性、系统的可靠性等关键问题，为关系数据库技术的成熟以及在不同领域的大规模应用创造了必要的条件。

数据库 ACID 原则在单台服务器就能完成任务的时代，很容易实现，但是现在面对如此庞大的访问量和数据量，单台服务器已经不可能适应了，而ACID在集群环境几乎不可能达到人们的预期，保证了 ACID，效率就会大幅度下降，而且为了达到这么高的要求，系统很难扩展，因此就出现了CAP理论和BASE理论。

2.2.2 CAP理论

1.CAP理论定义

2000年7月，加州大学伯克利分校的埃里克·布鲁尔（Eric Brewer）教授在ACM PODC会议上提出CAP猜想。两年后，麻省理工学院的塞思·吉尔伯符（Seth Gilbert）和南希·林奇（Nancy Lynch）从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。

一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项，如图2.1所示。

（1）一致性

一致性指“All nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。对于一致性，可以分为从客户端和服务端两个不同的视角来看。

从客户端来看，一致性主要指多并发访问时更新过的数据如何获取的问题。

从服务端来看，则是如何将更新复制分布到整个系统，以保证数据的最终一致性问题。

一致性是因为有并发读写才有的问题，因此在理解一致性的问题时，一定要注意结合考虑并发读写的场景。

从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。

对于关系型数据库，要求更新过的数据、后续的访问都能看到，这是强一致性。

如果能容忍后续的部分或者全部访问不到，则是弱一致性。

如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。

（2）可用性

可用性是指“Reads and writes always succeed”，即服务一直可用，而且是在正常的响应时间内。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是该系统使用的任何算法必须最终终止。

当同时要求分区容错性时，这是一个很强的定义：即使是严重的网络错误，每个请求也必须终止。好的可用性主要是指系统能够很好地为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。通常情况下可用性和分布式数据冗余、负载均衡等有着很大的关联。

（3）分区容错性

分区容错性指“The system continues to operate despite arbitrary message loss or failure of part of the system”，也就是指分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求应用虽然是一个分布式系统，但看上去却好像是一个可以运转正常的整体。例如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，或者是机器之间有网络异常，将分布式系统分隔为独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。

2.CAP理论的阐述与证明

图2.2所示是CAP的基本场景，网络中有两个节点N1和N2，可以简单地理解N1和N2分别是两台计算机，它们之间网络可以连通，N1中有一个应用程序A和一个数据库V，N2也有一个应用程序B和一个数据库V。A和B是分布式系统的两个部分，V是分布式系统的数据存储的两个子数据库，此时均为V。

在满足一致性的时候，N1和N2中的数据是一样的，即V0= V0。在满足可用性的时候，用户不管是请求N1或者N2，都会得到立即响应。在满足分区容错性的情况下，N1和N2有任何一方宕机，或者网络不通的时候，都不会影响N1和N2彼此之间的正常运作。

图2.3所示是分布式系统正常运转的流程，用户向N1机器请求数据更新，程序A更新数据库V0为 V1，分布式系统将数据进行同步操作 M，将 V1同步到 N2中 V0，使得 N2中的数据 V0也更新为V1，N2中的数据再响应N2的请求。

这里，可以定义N1和N2的数据库V之间的数据是否一样为一致性；外部对N1和N2的请求响应为可用性；N1和N2之间的网络环境为分区容错性。这是正常运作的场景，也是理想的场景，然而现实是残酷的，当错误发生的时候，一致性、可用性和分区容错性是否能同时满足？还是说要进行取舍呢？

作为一个分布式系统，它和单机系统的最大区别就在于网络。现在假设一种极端情况，N1和N2之间的网络断开了，要支持这种网络异常，相当于要满足分区容错性，能否同时满足一致性和响应性，还是要对它们进行取舍。

假设在N1和N2之间网络断开的时候，有用户向N1发送数据更新请求，那N1中的数据V0将被更新为V1，由于网络是断开的，所以分布式系统同步操作M，所以N2中的数据依旧是V0；此时，有用户向N2发送数据读取请求，由于数据还没有进行同步，应用程序无法立即给用户返回最新的数据V1，此时有两种选择：第一，牺牲数据一致性，响应旧的数据V0给用户；第二，牺牲可用性，阻塞等待，直到网络连接恢复，数据更新操作M完成之后，再给用户响应最新的数据V1。这个过程证明了要满足分区容错性的分布式系统，只能在一致性和可用性两者中，选择其中一个，如图2.4所示。

3.CAP权衡

通过CAP理论，知道无法同时满足一致性、可用性和分区容错性这三个特性，那应该如何取舍呢？

（1）CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。

（2）CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P （分区）会导致同步时间无限延长，如此CP 也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

（3）AP without C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

对于多数大型互联网应用的场景，主机众多、部署分散，而且现在的集群规模越来越大，所以节点故障、网络故障是常态，而且要使服务可用性很高，即保证 P 和 A，舍弃 C（退而求其次保证最终一致性）。虽然某些地方会影响客户体验，但没达到造成用户流程中断的严重程度。

对于不能有一丝让步的场景，C必须保证。网络发生故障宁可停止服务，这是保证CA，舍弃 P。还有一种情况是保证CP，舍弃A。例如网络故障是只读不写。

孰优孰劣，没有定论，只能根据场景选择，适合的才是最好的。

2.2.3 BASE理论

丹·普里切特（Dan Pritchett）在对大规模分布式系统的实践总结过程中，提出了BASE理论， BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consistency）。

BASE是指基本可用（Basically Available）、软状态（Soft State）、最终一致性（Eventual Consistency）。

1.基本可用

基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。

2.软状态

软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。

分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。例如MySQL replication的异步复制就是这种体现。

3.最终一致性

最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。

BASE和ACID的区别与联系是什么呢？ACID是传统数据库常用的设计理念，追求强一致性模型。BASE支持的是大型分布式系统，提出通过牺牲强一致性获得高可用性。ACID和BASE代表了两种截然相反的设计哲学。在分布式系统设计的场景中，系统组件对一致性要求是不同的，因此ACID和BASE又会结合使用。

2.2.4 最终一致性

最终一致性可概括为：过程松，结果紧，最终结果必须保持一致性即可。由于最终一致性使用广泛，本小节再次通过实例来阐述一下这个概念的含义。

为了更好的描述客户端一致性，通过以下的场景来进行，这个场景中包括三个组成部分。

存储系统：存储系统可以理解为一个黑盒子，它提供了可用性和持久性的保证。

Process A：主要实现从存储系统“写”和“读”操作；

Process B和Process C：独立于A，并且B和C也相互独立的，它们同时也实现对存储系统的“写”和“读”操作。

下面以上面的场景来描述下不同程度的一致性。

强一致性（即时一致性）：假如A先写入了一个值到存储系统，存储系统保证后续A、B、C的读取操作都将返回最新值。

弱一致性：假如A先写入了一个值到存储系统，存储系统不能保证后续A、B、C的读取操作能读取到最新值。此种情况下有一个“时间窗口”的概念，它特指从A写入值，到后续操作A、B、C读取到最新值这一段时间。“时间窗口”类似时空穿梭门，不过穿梭门是可以穿越到过去的，而一致性窗口只能穿越到未来，方法很简单，就是“等会儿”。

最终一致性：是弱一致性的一种特例。假如A首先“写”了一个值到存储系统，存储系统保证如果在 A、B、C 后续读取之前没有其他写操作更新同样的值的话，最终所有的读取操作都会读取到 A 写入的最新值。此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中复本的个数。最终一致性方面最出名的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。

最终一致性就是“等会儿就一致”，早晚会一致的。使用最终一致性的关键就是想方设法让用户“等会儿”。这个方法有个学名叫“用户感知到的一致性”，意思就是“让用户自己知道数据已经不一致了，你再忍会儿”。

还有一些最终一致性的变体如下。

Causal consistency（因果一致性）：如果Process A通知Process B它已经更新了数据，那么Process B的后续读取操作则读取A写入的最新值，而与A没有因果关系的C则可以最终一致性。

Read-your-writes consistency：如果Process A写入了最新的值，那么Process A的后续操作都会读取到最新值。但是其他用户可能要过一会才可以看到。

Session consistency：此种一致性要求客户端和存储系统交互的整个会话阶段保证Read-your-writes consistency。Hibernate的session提供的一致性保证就属于此种一致性。

Monotonic read consistency：此种一致性要求如果Process A已经读取了对象的某个值，那么后续操作将不会读取到更早的值。

Monotonic write consistency：此种一致性保证系统会序列化执行一个Process中的所有写操作。

2.2.5 一致性散列

一致性散列也是分布式系统中常用到的一个技术。

1.基本概念

一致性散列算法（Consistent Hashing）最早在论文“Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”中被提出。简单来说，一致性散列将整个散列值空间组织成一个虚拟的圆环。假设某散列函数H的值空间为 0～232－1（即散列值是一个 32 位无符号整形），整个散列空间环如图2.5所示。

整个空间按顺时针方向组织。0和232－1在零点中方向重合。

下一步将各个服务器使用散列算法进行一个散列运算，具体可以选择服务器的IP或主机名作为关键字进行散列，这样每台机器就能确定其在散列环上的位置，这里假设将上文中4台服务器使用IP地址散列后在环空间的位置，如图2.6所示。

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出散列值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如有Object A、Object B、Object C、Object D四个数据对象，经过散列计算后，在环空间上的位置如图2.7所示。

根据一致性散列算法，数据A会被定位到Node A上，B被定位到Node B上，C被定位到Node C上，D被定位到Node D上。

2.容错性和扩展性

（1）容错性

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般来说，在一致性散列算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间的数据，其他不会受到影响，如图2.8所示。

（2）扩展性

如果在系统中增加一台服务器Node X，如图2.9所示。

此时对象A、B、D不受影响，只有对象C需要重定位到新的Node X。一般来说，在一致性散列算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其他数据也不会受到影响。

综上所述，一致性散列算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

（3）虚拟节点

一致性散列算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如图2.10所示。

此时必然造成大量数据集中到Node A上，只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性散列算法引入了虚拟节点机制，即对每一个服务节点计算多个散列，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算“Node A#1”“Node A#2”“Node A#3”“Node B#1”“Node B#2”“Node B#3”的散列值，于是形成6个虚拟节点，如图2.11所示。

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”“Node A#2”“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。