下载掌阅APP，畅读海量书库
立即打开
|
2.3 分布式系统理论 |
在分布式系统研究领域有诸多理论，笔者选择和后续案例或缓存开源软件相关的一些理论，试简略叙述之，以增强读者对相应知识的了解，对于分布式理论感兴趣的朋友可以查阅相关资料以做进一步了解。CAP理论提出了一致性、可用性、分区容忍性的取舍问题；Paxos、Raft、2PC、3PC分别给出了一致性的解决方案；Lease机制主要针对网络拥塞或瞬断的情况下，出现双主情况的解法；Quorum NWR和MVCC主要解决分布式存储领域的一致性问题；Gossip是一种去中心化、容错而又最终一致性的算法。
分布式系统的CAP理论：首先将分布式系统中的三个特性进行如下归纳：
· 一致性（C） ：在分布式系统中的所有数据备份，在同一时刻是否有同样的值。（等同于所有节点访问同一份最新的数据副本）
· 可用性（A） ：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）
· 分区容忍性（P） ：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在一定时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。
高可用、数据一致是很多系统设计的目标，但是分区又是不可避免的事情，由此引出了以下几种选择：
如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。
典型放弃分区容忍性的例子有关系型数据库、LDAP等。如图2-6所示：
图2-6 放弃分区容忍性
如果不要求A（可用性），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式，分布式锁也属于此种情况，如图2-7所示。
图2-7 放弃可用性
要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类，如图2-8所示。
图2-8 放弃一致性
该理论由brewer
提出，2年后就是2002年，Lynch与其他人证明了Brewer猜想，从而把CAP上升为一个Lynch
定理。但是，她只是证明了CAP三者不可能同时满足，并没有证明任意二者都可满足的问题，所以，该证明被认为是一个收窄的结果。
Lynch的证明相对比较简单：采用反证法，如果三者可同时满足，则因为允许P的存在，一定存在Server之间的丢包，如此则不能保证C，证明简洁而严谨。
在该证明中，Lynch对CAP的定义进行了更明确的声明：
·C：一致性被称为原子对象，任何的读写都应该看起来是“原子”的，或串行的。写后面的读一定能读到前面写的内容。所有的读写请求都好像被全局排序。
·A：对任何非失败节点都应该在有限时间内给出请求的回应。（请求的可终止性）
·P：允许节点之间丢失任意多的消息，当网络分区发生时，节点之间的消息可能会完全丢失。
该定义比Brewer提出的概念更为清晰，一度CAP理论成为分布式方面的圣经，频繁地被引用，言必称CAP。
《CAP理论十二年回顾：“规则”变了》一文首发于Computer杂志，后由InfoQ和IEEE联合呈现，非常精彩
。
文章表达了以下几个观点：
不是为了P（分区容忍性），要在A和C之间选择一个。分区很少出现，CAP在大多数时候允许完美的C和A。但当分区存在或可感知其影响的情况下，就要预备一种策略去探知分区并显式处理其影响。这样的策略应分为三个步骤：探知分区发生，进入显式的分区模式以限制某些操作，启动恢复过程以恢复数据一致性并补偿分区期间发生的错误。
“一致性的作用范围”其实反映了这样一种观念，即在一定的边界内状态是一致的，但超出了边界就无从谈起。比如在一个主分区内可以保证完备的一致性和可用性，而在分区外服务是不可用的。Paxos算法和原子性多播（atomic multicast）系统一般符合这样的场景。像Google的一般做法是将主分区归属在单个数据中心里面，然后交给Paxos算法去解决跨区域的问题，一方面保证全局协商一致（global consensus）如Chubby，一方面实现高可用的持久性存储如Megastore。
ACID和BASE这两个术语都好记有余而精确不足，出现较晚的BASE硬凑的感觉更明显，它是“Basically Available，Soft state，Eventually consistent（基本可用、软状态、最终一致性）”的首字母缩写。其中的软状态和最终一致性这两种技巧擅于对付存在分区的场合，并因此提高了可用性。
CAP与ACID的关系更复杂一些，也因此引起更多误解。其中一个原因是ACID的C和A字母所代表的概念不同于CAP的C和A。还有一个原因是选择可用性只部分地影响ACID约束。
最终一致性（Eventually consistent）是令人相对难理解的一个概念，最终具体是什么时间范围才算？业界有一种我相对认同的解释：
1）给定足够长的一段时间，不再发送更新，则认为所有更新会最终传播到整个系统，且所有副本都会达到一致。
注意
事实上，7×24小时持续提供服务的系统，比如电商网站，会不断有订单产生、有商品发布，这里说的不再更新是针对具体的对象（比如张三购买鞋子的交易记录，在大促活动期间可能没有及时更新到商户侧让商户可以查询到，但活动结束一般则可以查询到），如果有差错，IT系统解决掉之后还是会保障其正确性。
2）当存在持续更新时，一个被接受的更新要么到达副本，要么在到达副本的路上，比如网络闪断，有重试机制；为避免持续压力，可加大重试时间；超过重试次数，则引入手工决策或者第二套方案处理。
Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，Lamport在八年后重新发表，即便如此Paxos算法还是没有得到重视。2006年Google的三篇论文石破天惊，其中的chubby锁服务使用Paxos作为chubby cell中的一致性算法，工业界对它的兴趣趋于浓厚。2001年Lamport用简单的语言而不是难懂的天书重写这篇论文，命名为Paxos Made Simple。
一言以蔽之，Paxos协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。
Paxos协议是一个两阶段协议，分为Prepare阶段和Accept阶段。下面分别对2个阶段的处理展开叙述。
普及一下，该协议涉及2个参与者角色：Proposer和Acceptor。Proposer是提议提案的服务器，而Acceptor是批准提案的服务器。二者在物理上可以是同一台机器。
Proposer生成全局唯一且递增的提案ID（生成方法很多，比如时间戳+IP+序列号等），向Paxos集群的所有机器发送请求，这里无须携带提案内容，只携带提案ID即可（且把提案id叫作Pn，也有一种说法ID其实代表版本version）。如图2-9所示：
图2-9 Prepare阶段1图示
Acceptor收到提案请求后，做出以下约定：
1）不再应答<=Pn的Prepare请求；
2）对于<Pn的Accept请求亦不处理。
Acceptor做的处理包括：
1）应答前要在本地持久化当前提案ID；
2）如果现在请求的提案ID——Pn大于此前存放的proposalID，则做以下逻辑：
If Pn>proposalID then proposalID =Pn
如果该Acceptor Accept过的提案，则返回提案中proposalID最大的那个提案的内容，否则返回空值。
交互过程如图2-10所示。
Proposer收集到多数派应答（这里的多数派，就是超过n/2+1，n是集群数）Prepare阶段的返回值后，从中选择proposalID最大的提案内容，作为要发起Accept的提案，如果这个提案为空值，则可以自己随意决定提案内容。然后携带上当前proposalID，向Paxos集群的所有机器发送Accpet请求，如图2-11所示。
图2-10 Proposer发送Prepare
图2-11 Proposer发送Accept
Accpetor收到Accpet请求后，检查不违背自己之前做出约定的情况下，持久化当前Proposal ID和提案内容。最后Proposer收集到多数派应答的Accept回复后，形成决议。
如果需要进一步阅读，推荐倪超著的《从Paxos到ZooKeeper》一书。
在事务处理、关系型数据库及计算机网络中，2阶段提交协议（2PC）是一种典型的原子提交协议（atomic commitment protocol）。它是一种由协调器来处理分布式原子参与者是提交或者回滚事务的分布式算法。
该协议包括2个阶段：
该阶段的任务是确定相关参与者对于事务处理是否准备就绪，YES代表可以commit，NO则反之。
基于投票结果，由协调器决定提交事务抑或是退出事务处理；各事务参与者遵循指示，对本地事务资源做需要的动作。
如图2-12所示，协调器用coordinator表示，cohot1、cohot2分别表示事务参与者1、事务参与者2。在提交请求阶段，cohot1执行prepare（事务准备）动作，并返回给协调器；cohot2亦是如此。如果均返回YES则进入下一个阶段：commit phase（提交阶段）。如果有一个事务参与者返回NO，则协调器决策不进入commit phase阶段。
图2-12 commit request phase时序图
如图2-13所示，协调器向参与者1（cohort1）发出提交（commit）指令，参与者1执行提交并发确认信息给协调器；cohort2也是如法炮制。如果参与者1（cohort1）或者参与者2（cohort1）commit（提交）失败/超时，则通知协调器，发起回滚（rollback）。
图2-13 commit phase时序图
2PC最大的不足是提交协议是阻塞型协议，如果事务协调器宕机，某些参与者将无法解决他们的事务：一个参与者发送确认消息给协调器，因协调器无法工作而导致事务未处理完而处于悬挂状态。
因此在高并发网站中使用分布式事务的2PC协议要把握如下原则：
1）能不用2PC的尽量不用，综上所述可以发现，2PC协议要有提交请求阶段、提交阶段，而每个阶段也有协调器分别与多个事务参与者的应答，复杂度高，性能也受到挑战。
2）要获得事务强一致性，也要在性能和一致性上做折中，比如加上超时机制，阶段性补偿机制等。
如图2-14所示，3PC分为3次交互。第一阶段，投票，事务协调器询问参与者是否能提交（canCommit），都得到肯定回答后，继续第二阶段。第二阶段是预提交，都确认预提交成功后，进行第三阶段。第三阶段就是真实的提交，成功则完成事务；失败则继续重试。3PC是在2PC的基础上增加了一次交互，也就是preCommit（又称预提交）。只要预提交都成功，则一定要保证doCommit提交成功，即使协调器在下一阶段不可用，或者调用超时。这是协议的基本思想，在工业环境中，一般是通过重试补偿的策略来保证doCommit提交成功的。
图2-14 Three-phase_commit时序图
Raft提供了和Paxos算法相同的功能和性能，但是它的算法结构和Paxos不同。Raft算法更加容易理解并且更容易构建实际的系统。为了提升可理解性，Raft将一致性算法分解成了几个关键模块，例如领导人选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。Raft算法还包括一个新的机制来允许集群成员的动态改变，它利用重叠的大多数来保证安全性。
Paxos和Raft都是为了实现一致性（Consensus）这个目标，这个过程如同选举一样，参选者需要说服大多数选民（服务器）投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。
在Raft中，任何时候一个服务器可以扮演下面角色之一：
· 领导者： 处理所有客户端交互、日志复制等动作，一般一次只有一个领导者。
· 选民： 类似选民，完全被动的角色，这样的服务器等待被通知投票。
· 候选人： 候选人就是在选举过程中提名自己的实体，一旦选举成功，则成为领导者。
Raft算法分为2个阶段，首先是选举过程，然后在选举出来的领导人带领进行正常操作，比如日志复制等。下面用图示展示这个过程：
1）任何一个服务器都可以成为一个候选者，它向其他服务器（选民）发出要求选举自己的请求，如图2-15所示：
2）其他服务器同意了，回复OK（同意）指令，如图2-16所示。
此时如果有一个Follower服务器宕机，没有收到请求选举的要求，则只要达到半数以上的票数，候选人还是可以成为领导者的。
3）这样，这个候选者就成为领导者，它可以向选民们发出要执行具体操作动作的指令，比如进行日志复制，如图2-17所示。
图2-15 candidate发出请求
图2-16 follower返回请求
图2-17 candidate发出操作指示
4）如果一旦这个Leader宕机崩溃了，那么Follower中会有一个成为候选者，发出邀票选举，相当于再次执行1）～2）的步骤。
总结：1）～2）是选举过程，3）是具体协同执行指令操作的过程。
Lease英文含义是“租期”、“承诺”。在分布式环境中，此机制描述为：Lease是由授权者授予分布式环境一段时间内的承诺。以图2-18缓存服务器为例，缓存服务器（Server）把数据分发给对应的节点NodeA、NodeB以及NodeC。其中节点A、B得到数据v01，有效期为12：00：00，而节点C收到数据v02，有效期为12：15：00。节点A可以把v01数据缓存在本地，在Lease时间范围内，放心使用。而Server也遵守承诺，在Lease过期时间内不修改数据。
图2-18 缓存服务器分发数据给众节点
当时间到12：00：01时，此时v01的数据过期，则NodeA、NodeB会删除本地数据。而此时Server会阻塞一直到已发布的所有Lease都已经超时过期，再更新数据并发出新的Lease，如图2-19所示。
图2-19 Lease示意图
不难发现，这里有一些优化空间，且罗列如下：
1）已经过期的Lease的读问题。NodeA的数据已经过期，这事Server还未更新发布，读不到数据够郁闷的，影响业务可用性。改进之一就是还是给它数据，但是没有Lease时间。下次来则继续到Server请求，可能此时新的Lease已经生成好。
2）主动通知机制，如果Server的数据通过配置后台也好、事件触发也好，修改了数据，难道要等所有Lease都过期？它可以主动发起失效命令。如果所有失效成功，则直接更新数据，颁发新的Lease。如果不完全成功，则可以重试或者退化为原始的等待方案。
3）基于锁定资源的角度，如果一次更新动作的数据是分离的，则没有必要对所有Lease等待过期。比如对于v01/Lease：xx-xx-xx这个数据，只要所有节点的对应这个数据都过期或者失效就ok了，和v02没有关系。
主备是实现高可用的有效方式，但存在一个脑裂问题。脑裂（split-brain），指在一个高可用（HA）系统中，当联系着的两个节点断开联系时，本来为一个整体的系统，分裂为两个独立节点，这时两个节点开始争抢共享资源，结果会导致系统混乱，数据损坏。
前面提到了心跳检测策略。我们通过心跳检测做主备切换的时候，就存在不确定性。心跳检测的不确定性是发生脑裂问题的一个非常重要的原因。比如Slave提供服务了，但此前被判死的Master又“复活”了，还在继续工作，则对应用程序逻辑带来未知因素，其中就包括抢夺资源。
如何解决这个问题呢？如图2-20所示，有一种做法称为设置仲裁机制，例如设置第三方检测服务器（Monitor），当Slave确定准备接管Master时，让Monitor也ping一下Master，如果没有通讯，则判断其“死亡”；同时Master在对外提供服务时，每隔一段时间比如10s由Master服务器ping Slave服务器和Monitor，如果均出现异常，则暂定业务操作，重试。重试多次之后则退出程序执行或者执行服务器重启操作。
图2-20 Master-Slave示意图
当然，这里有新的问题，比如Monitor的高可用保障。
通过Lease机制也可以进一步处理双主脑裂问题，如图2-21所示。我们假设Slave已经在提供服务了，对应的Server服务器则获得Slave颁发的Lease。假设老Master仍在提供服务，则Lease必然是过期的，因此请求失效，老Master请求频繁时效的情况下，可以通过配置监控点触发报警，以人工介入让老Master放弃身份，转换为Slave。
图2-21 通过Lease解决双主脑裂
社区Hadoop2.2.0 release版本开始支持NameNode的HA，采用了Qurom Journal Manager方式解决高可用环境下NameNode的切换问题。大家可以通过查阅相关资料进一步阅读。
NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。
让我们先来看看这三个字母的含义：
·N：同一份数据的拷贝份数；
·W：是更新一个数据对象的时候需要确保成功更新的份数；
·R：读取一个数据需要读取的拷贝的份数。
具体策略通过2个公式计算：
这2个公式的意思是写操作要确保成功的份数应该高于同一份数据拷贝总份数的一半；同时，写操作加上读操作的总份数也要高于同一份数据拷贝总份数。
我们通过表2-1来讨论一下对于N不同取值，W、R如何的优劣情况。
表2-1 NWR示例
由表2-1可得，N至少达到3，大于3则付出更高的成本。小于3无法保障高可用。一般采取N=3、R=2、W=2的配置，W=2，可以保障大多数写成功，而R=2，则能保障读到大多数一致的最新版本。关于由于不同节点都在提供W和R，而W未必等于N，则一定存在数据不一致的情况。冲突解决策略一般有Cassandra使用的client timestamps和Riak的Vector clock等，如果无法解决，冲突可能会硬性覆盖或者推到业务代码。
Taobao File System，简称TFS，是淘宝针对海量非结构化数据存储设计的分布式系统，构筑在普通的Linux机器集群上，可为外部提供高可靠和高并发的存储访问，高可扩展、高可用、高性能、面向互联网的服务。TFS采取了N=3、W=3的策略，为了取得写性能与高可用之间的平衡，在某个DataServer出现问题的时候，采取异步策略，由对应block元数据管理机制启动恢复流程，选择继续写到成功为止。TFS架构图如图2-22所示。
图2-22 TFS架构图
具体的处理策略，描述如下：
TFS采用Block存储多份的方式来实现DataServer的容错。每一个Block会在TFS中存在多份，一般为3份，并且分布在不同网段的不同DataServer上。对于每一个写入请求，必须在所有的Block写入成功才算成功。当出现磁盘损坏DataServer宕机的时候，TFS启动复制流程，把备份数未达到最小备份数的Block尽快复制到其他DataServer上去。TFS对每一个文件会记录校验crc，当客户端发现crc和文件内容不匹配时，会自动切换到一个好的block上读取。此后客户端将会实现自动修复单个文件损坏的情况。
MVCC，全称Multiversion concurrency control，翻译为基于多版本并发控制。人们一般把基于锁（比如行级锁）的并发控制机制称成为悲观机制，而把MVCC机制称为乐观机制。由于MVCC是一种宽松的设计，读写相互不阻塞，可以获得较好的并发性能。
下面用一个例子来说明一下Multiversion
，如表2-2所示。
表2-2 MVCC示例
如表2-2所示，事务T0修改了Object1、Object2的值，而事务T1修改了Object1的值，那么对于Object1需要记录2个版本，分别是T0时刻和T1时刻的。在T1提交之后，事务T2查询，则T2可以查询Object1=“Hello”、Object2=“Bar”。而T2查询的时候，并发有T3事务，T3删除Object2并修改Object3，同样记录相应版本如表2-2所示。
不同数据库对于MVCC的具体实现有差异。MySQL的InnoDB是这样做的：
·引擎给每张表都增加2个字段，分别叫作create version和delete version。
·插入操作时：记录的创建版本号就是事务版本号。
·更新操作时：采用的是先标记旧的那行记录为已删除，并且删除版本号是事务版本号，然后插入一行新记录的方式。
·删除操作时：就把事务版本号作为删除版本号。
那么当我们做查询操作的时候，要符合以下两个条件的记录才能被事务查询出来：
1）delete version>当前版本号，就是说删除操作是在当前事务启动之后做的。
2）create version<=当前事务版本号。
下面我们通过表2-3来看一下MySQL实现MVCC的一个例子。我们在这个例子中做了三次操作。
1）insert一条name为“友强”的记录。
2）修改该记录的name为“王友强”，此时create version设置为2。
3）删除这条记录，在数据库引擎中的体现是insert新记录，并设置delete version=3。
表2-3 mysql实现mvcc的示例
可以通过示例追溯id=1的这条记录的变迁历程。如果当前查询版本为1，则查询name为友强，查询时版本为2，则查询name结果为王友强。
对于分布式系统而言，由于状态分散在集群中的各个节点上，集群的状态同步面临着集中式系统所不具备的问题：
·其中的每一个节点如何较快的得知集群状态全集的某些特征？
·如何避免多个节点就某个状态发生分歧，使得集群的状态实时或最终一致？
分布式系统中的各个节点通过一定的交互方式（分布式协议）解决上述问题。
Gossip就是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。因为其实现简单，具备较高的容错性和性能，成为分布式系统最广泛使用的状态同步协议之一。
以Gossip协议同步状态的思路类似于流言的传播，如图2-23所示。
图2-23 流言传播
A节点率先知道了某个流言（msg），它首先将此信息传播到集群中的部分节点（比如相邻的两个节点）B和C，后者再将其传递到它们所选择的“部分”节点，例如B选择了D和E，C选择了将流言传播到B和F。以此类推，最终来自于A的这条流言在3轮交互后被传播到了集群中的所有节点。
在分布式系统的实践中，这个“流言”可能是：某个节点所感知到的关于其他节点是否宕机的认识；也可能是数据水平拆分的缓存集群中，关于哪些hash桶分布在哪些节点上的信息。每个节点起初只掌握部分状态信息，不断地从其他节点收到Gossip信息，每个节点逐渐地掌握到了整个集群的状态信息。因此解决了状态同步的第一个问题：全集状态的获取。
对于集群中出现的部分网络分割，如图2-24所示。
图2-24 网络分割示意
消息也能通过别的路径传播到整个集群。
状态同步的第二个问题：对于同一条状态信息，不同的节点可能掌握的值不同，也能通过基于Gossip通信思路构建的协议包版本得到解决。例如水平拆分的Redis缓存集群，初始状态下hash桶在各个节点的分布如图2-25所示：
图2-25 状态一致案例
此时各个节点预先通过某种协议（比如Gossip）得知了集群的状态全集，此时新加入了节点D，如图2-26所示：
图2-26 加入节点D的变化
D分担了C的某个hash桶，此时C/D和集群中其他节点就C所拥有哪些hash这件事发生了分歧：A/B认为C目前有6/7/8个hash桶。此时通过为Gossip消息体引入版本号，使得关于C的最新状态信息（只有6/7两个桶了）在全集群达到一致。例如B收到来自A和C的Gossip消息时会将版本号更新的消息（来自C的v2）更新到自己的本地副本中。
各个节点的本地副本保存的集群全量状态也可能用来表示各个节点的存活状态。对于部分网络分割的情况如图2-27所示：
图2-27 网络分割下的状态
例如A和C的网络断开，但A和C本身都正常运行，此时A和C互相无法通信，C会将A标记为不可用状态。对于中心化思路的协议，如果C恰好是中心节点，那么A不可用的信息将会同步到集群的所有节点上，使得这些节点将其实可用的A也标记为宕机。而基于Gossip这类去中心化的协议进行接收到消息后的实现逻辑扩展（例如只有当接收到大多数的节点关于A已经宕机的消息时，才更新A的状态），最终保证A不被误判为宕机。
Gossip的核心是在去中心化结构下，通过信息的部分传递，达到全集群的状态信息传播，传播的时间收敛在O（Log（N））以内，其中N是节点的数量。同时基于Gossip协议，可以构建出状态一致的各种解决方案。