e-works数字化企业网  »  文章频道  »  基础信息化  »  终端和服务器

关于分布式系统的思考

2017/11/12    来源:中国云计算    作者:佚名      
关键字:分布式系统  分布式  
对于数据库来说,可能关心的最多的就是数据的一致性了,由此衍生出了不同场景下的算法和策略。
    对于数据库来说,可能关心的最多的就是数据的一致性了,由此衍生出了不同场景下的算法和策略。
 
    在上一篇末尾提及了两种集群结构:中心化和去中心化。
 
    中心化
 
    一种是中心化的,由中心节点去存储集群信息并管理集群状态,其它节点只需响应数据请求,而无需知道集群中其它节点的情况。 这种模式的核心便是选举或者指定一个节点作为集群的管理者,由管理者去协调跨节点的操作、备份数据和处理故障等。
 
  关于分布式系统的思考
 
    一般的,对于跨节点的操作,为了保证事务的原子性,提出了两步提交协议或三步提交协议,下面分别介绍。
 
    2pc
 
    两步提交协议,顾名思义,就是将数据的提交分为两步:投票和决策。
 
  关于分布式系统的思考
 
    首先,在第一阶段,
 
    中心节点(在这里我们称之为协调者)发起事务操作请求,包含事务内容,询问是否可以执行提交操作并等待响应;
 
    其它节点(在这里称之为参与者)执行事务操作并记录undo/redo log,最后返回是否同意提交。
 
    然后,在第二阶段,协调者根据所有参与者的投票结果,如果是都同意则通知所有参与者提交事务,否则回滚事务。 收到所有参与者回应后,完成事务。
 
    接着,我们考虑下两步提交过程中如果发生异常,会出现什么样的情况,会不会影响结果的一致性,并尝试解决。
  
    在第一阶段时,有节点宕机
 
    有参与者宕机,此时协调者接收到错误响应,可认为是失败,将中断事务。
 
    协调者宕机,此时参与者等待协调者的操作通知,事务会阻塞直到协调者恢复。 对于此种情况,解决的办法是可以设置多个协调者,一主多从,宕机后指定一台从作为新的主。
 
    参与者也需要记录事务的投票状态,以便新的协调者重新找回事务状态。
 
    参与者和协调者都宕机了,如上一条,新的协调者将会获取不到参与者的事务状态(该参与者的状态只有自己和原协调者知道),会一直阻塞地等待所有参与者恢复。 其它参与者也会处于两阶段之间,直到宕机的参与者恢复。
 
    在第二阶段,有节点宕机
 
    有参与者宕机,此时未宕机的参与者会正常地提交/回滚事务,而由于并不知道宕机的时机,所以可能会导致数据的不一致。
 
    协调者宕机,若是在发送通知前,那么参与者将阻塞地等待协调者恢复。可通过设置协调者的备份来解决,要求参与者记录事务状态。若是在发送通知后,不影响可忽略。
 
    参与者与协调者都宕机了,如上两条,可能会导致数据的不一致或阻塞。
 
    注意,以上的宕机如果替换为网络分区,也会是同样的情况。
 
    可以看出,2pc的优点是简单直接,缺点是:
 
    当有故障发生会阻塞事务的执行,进而影响到相关资源的释放;
 
    协调者的单点问题;
 
    当二阶段有参与者宕机或者网络分区时,可能会导致数据不一致。
 
    针对这些缺陷,出现了3pc。
 
    3pc
 
    三步提交协议,改进了2pc的一些缺陷,它增加了一个询问是否可提交阶段。如图所示:
 
  关于分布式系统的思考
 
    第一阶段时,协调者询问各参与者是否可以执行事务提交,包含事务内容,并等待参与者的响应。 参与者收到请求后,如果认为可以成功执行事务,则返回同意,否则中止事务。
 
    第二阶段时,协调者根据第一阶段参与者的返回消息,决定是准备提交或是中止事务。如果都是同意,那么发送预提交请求。 参与者收到请求后,会执行事务操作,并记录undo/redo log, 最后返回提交/中止事务。
 
    第三阶段时,协调者根据第二阶段的响应,决定通知参与者提交/回滚事务,收到响应后完成事务。
 
    3pc相比于2pc的优点在于:
 
    在协调者和参与者端都添加了超时机制,其中:参与者超时未应答均认为是失败;协调者在第二阶段超时未发送请求视为失败,而第三阶段超时未发送请求视为成功,参与者在经过了指定超时时间后提交事务。这样便具备了一定的容错性。
 
    不仅如此,这样还可以有效减少阻塞时间。
 
    提供了协调者的主备方案,避免了单点问题。
 
    缺点:
 
    第二阶段时,参与者在接收到预提交请求后发生网络分区,此参与者在超时后提交事务,而协调者在超时后认为事务失败并通知其它参与者回滚事务,最终导致数据不一致。若发生此情况,只能通过上层去协调解决这个问题,如上一篇提到的两种解决方案。(2pc也有类似缺陷)
 
    比2pc多了一个阶段,意味着同等情况下,耗时要多一点。
 
    去中心化
 
    另一种则是去中心化的,由节点之间互相通信去协商一致。比较有名的算法如Paxos。
 
    Paxos算法在分布式领域具有非常重要的地位,Google Chubby的作者Mike Burrows曾经说过,这个世界上只有一种一致性算法,那就是Paxos,其它的都是残次品。
 
    不过这个算法实在是难理解,难实现;以后有机会我会专门总结一篇文章分享下,有兴趣的道友可以先去看看《Paxos Made Simple》,写得很不错。
 
    此外,考虑到集群中的节点数量并不是一成不变的,所以如果使用的是一般的Hash算法,那么在集群新增节点或删除节点时,会导致节点间大量数据的迁移,进而影响可用性,故而提出了一致性Hash算法以减少数据的迁移量。
 
    一致性Hash
 
    一般的Hash算法,如对key取模然后分散到不同的节点中:假设有3个节点,共有key分别为1~7的数据,分配结果如下图
 
  关于分布式系统的思考
 
    现在,如果新增一个节点,那么分配结果变为:
 
  关于分布式系统的思考
 
    可以发现大部分的节点都被重新分配到了不同的节点上,即迁移数据是O(n)复杂度(n为数据总量),无法平滑地扩缩容。
 
    接下来再来看下一致性Hash,它的分配方式是对key和节点做相同的Hash运算,然后将key分配到刚好大于或等于它Hash值的节点上(若节点都比它Hash值小,则分配到最小的节点上,即形成一个“环”);
 
    还是上面的那个例子,对key和节点都做对7取模的Hash计算,然后分配。先是有三个节点:
 
  关于分布式系统的思考
 
    新增一个节点:
 
  关于分布式系统的思考
 
 
    可以看出,增加一个节点后只有少量数据从5节点移动到4节点,极大的减少了数据迁移量。
 
    但是,一致性Hash也有缺陷:查找效率低。一般需要逐个去比较Hash值直到找到刚好大于等于的节点,故查找复杂度为O(k)(k为节点数量)。
 
    可以通过在节点中冗余一份节点表来加快查找。
 
    总结
 
    保证一致性,要么是通过共享存储,要么是通过消息协调。
 
    数据库本身就是共享存储。
 
    不管是2pc、3pc还是paxos,都是通过节点间的交换消息去达到一致的状态,这也是分布式系统的常用做法。
 
    了解了这些策略的原理后,不管是用Zookeeper、RabbitMQ、Redis或其它消息组件(甚至是基于socket通信)去实现它,都是水到渠成的事情了。
 
    超时是个好设计,因为它是不需询问便可以察觉错误的方式(毕竟没有错误就不会超时了),很多设计中都会将超时作为一种信号,并尝试容错/修复等操作。
 
    在运行过程的一些错误并不能通过底层的策略完全规避,需要根据具体业务在上层做相应的容错措施。
 
    冗余是个好设计,几乎在各种组件的设计都能见到,通过牺牲一点空间较大地提高检索效率。
 
    有机会的话,之后的篇章我会收集并比较几种典型分布式组件的具体实现,对这些组件有个更加直观和深入的理解,以便充实和改进自己的知识结构并分享出来。
 
责任编辑:李欢
本文为授权转载文章,任何人未经原授权方同意,不得复制、转载、摘编等任何方式进行使用,e-works不承担由此而产生的任何法律责任! 如有异议请及时告之,以便进行及时处理。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。
e-works
官方微信
掌上
信息化
编辑推荐
新闻推荐
博客推荐
视频推荐