<返回更多

十分钟搞定分布式一致性算法

2021-01-19    
加入收藏

前言

本文编写的目的：为了深入理解后期关于zookeeper的文章，本文这里对分布式一致性算法的由来以及要解决的问题做一个简述，更加深入的原理性东西后续将会以专辑的形式撰写。另该文比较长，建议收藏阅读

本文编写的顺序:从集中式演化到分布式--->分布式出现的一些问题--->如何解决这些问题(即最重要的一致性问题)---->事务(保证一致性的方法)---->从早期的ACID到CAP/BASE理论---->2pc/3pc----->Paxos算法

背景

20世纪60年代大型主机被发明出来以后，集中式的计算机系统架构成为了主流，其单机处理能力方面的优势非常明显，但从20世纪80年代之后，传统的集中式处理模式越来越不能满足人们的需求，同时集中式系统有明显的单点故障问题，从2008年开始，阿里开启了“去IOE”计划，后来逐渐的往分布式系统的方向发展。

分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。因此分布式系统具有以下几个特点：

1.分布性

多台计算机在空间上随意分布，同时分布情况也会随时变动

2.对等性

集群中的每个节点角色都是一样的，注意副本的概念

3.并发性

多个机器可能会同时操作一个数据库或存储系统，可能会引起数据不一致问题

4.缺乏全局时钟

分布式系统中的多个主机事件先后顺序很难界定

5.故障总发生

服务器宕机，网络拥堵和延迟

 

同时和分布式系统进行对比发现集中式系统具有以下几个特点:

部署结构简单

成本高

单点故障

大型主机的性能扩展受限于摩尔定律

注意：这里要区分集群和分布式的概念，集群是指大量的机器做同一件事情；分布式是指每台机器都有不同的角色，做不同的事情

分布式异常问题

分布式系统体系结构从出现到现在仍有很多的问题，这里列出一些典型的问题

1.通信异常

从集中式向分布式演变，必然会引入网络因素，由于网络的不可靠性，必然会在分布式节点之间出现网络 异常的情况

2.网络分区

网络分区也就是常说的脑裂，即出现多个局部小集群，每个局部网络可以互相通信

3.三态

三态指的是三种状态，即成功、失败、超时；在集中式系统中只有成功和失败，而超时是由于分布式系统中会出现网络异常才会有的状态

4.节点故障

分布式节点总会出现宕机或者僵死现象

5.数据丢失

对于有状态的节点，数据丢失意味着状态丢失，通常只能从其他节点读取，恢复存储的状态；通常针对这种问题，通过引入副本机制就可以解决

 

衡量分布式系统的性能

性能

即系统吞吐能力、响应延迟、QPS等

可用性

可扩展性

一致性

一致性模型

分布式环境下，一致性指的是数据在多个副本之间是否能够保持一致的特性，对于一个将数据副本分布在不同节点的系统上来说，如果对一个节点的数据进行了更新操作，却没有使得第二个节点上的数据得到响应的更新，那么此时在读取第二个节点的数据时，将会出现脏读现象(即数据不一致).那么一致性又分为以下几种：

 

强一致性

即写操作完成后，读操作一定能够读到最新的数据，在分布式场景下，很难实现；Paxos、Quorum机制、ZAB协议能够实现,后面会对这几种协议算法进行讲解。

 

弱一致性

不承诺立即可以读到写入的值，也不承诺多久后能达到数据一致，但会尽可能保证某个时间级别后，数据达到一致状态

 

读写一致性

用户读取自己写入结果的一致性，保证用户能够第一时间看到自己更新的内容;这种实现的解决方案有:一种方案是对于特定的内容，我们去主库查询

设置一个更新时间窗口，在刚更新的一段时间内，默认去主库读取，过了这个窗口后，挑选最近更新的从库进行读取

直接记录用户更新的时间戳，在请求的时候把这个时间戳带上，凡是最后更新时间小于这个时间戳的从库都不响应

 

单调读一致性

本地读到的数据不比上次读到的旧，多次刷新返回旧数据会出现灵异事件，对于这种情况可以通过hash映射到同一台机器上

 

因果一致性

如果节点A在更新完某个数据后通知了节点B，那么节点B之后对该数据的访问和修改基于A更新的值。此时，和节点A无因果关系的节点C的数据访问则没有这样的限制

 

最终一致性

所有分布式一致性模型中最弱的。不考虑中间的任何状态，只保证经过一段时间之后，最终系统内数据正确，最大程度上保证了系统的并发能力，因此在高并发场景下，也是使用最广的一致性模型

 

事务

事务是可以保证一致性的方法，在集中式系统架构中可以通过ACID的方式实现，在早期分布式架构，是通过CAP/BASE理论来实现的，后来又演化出了2pc/3pc,以及Paxos、Raft等算法来保证一致性。

事务是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元。(概念性的东西直接略过～)

分布式一致性协议算法

2pc

即二阶段提交，绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理。即将事务的提交过程分为了两个阶段来处理

十分钟搞定分布式一致性算法

 

3pc

基于2pc出现的一些问题，3pc进行了改进，也就是三阶段提交，将2pc的第二个阶段进行了一分为二，形成了CanCommit（提交询问）、Precommit（预提交）、doCommit阶段(最终提交)三个阶段；其实3pc和2pc的不同点在于3pc增加了超时机制。

十分钟搞定分布式一致性算法

 

Paxos

Paxos算法要解决的问题就是如何保证数据一致性，这是一种基于消息传递且具有高度容错特的一致性算法

首先要引入拜占庭问题

拜占庭问题：即不同军队的将军之间必须制定一个统一的行动计划，但是在地理上都是分隔开来的，只能依靠通讯员进行通信，但是通讯员可能会存在叛徒，对消息进行篡改，从而欺骗将军。

这种消息篡改的情况在同一个局域网内几乎不会出现，或者简单通过校验算法进行避免。但是在实际工程实践中，可以假设不存在拜占庭问题，基于这种假设如何保证一致性呢？这个时候又引入Paxos的故事

古希腊有一个Paxos小岛，岛上采用会议的形式来通过法令，议会上的议员通过信使来传递消息，注意信使和议员都是兼职的，有可能随时会离开议会，而且信使有可能会重复传递消息，也有可能一去不返。那么在这种情况下议会协议也要保证法令能够正确选举出来，而且不会产生冲突。

根据这个故事也就衍生出了Paxos算法，该算法有3个角色：

1.Proposer（提议者，用来发起提案的，相当于zk中的leader角色）

2.Acceptor(接受者，可以接受或拒绝提案，相当于zk中的follower角色)

3.Learner(学习者，学习被选定的提案，相当于zk中的observer角色)

注意这里讲解的是Basic Paxos，基于Baisc Paxos演化出了Multi Paxos,这里不做过多讲解，有兴趣的同学可自行查阅

大致流程就是首先选举出一个Leader，也就是Proposer用来发起提案，然后发送给所有的Acceptor来进行投票，当超过一半投通过票的时候，该提案也就通过了，那么这个时候Proposer会将该提案进行同步所有机器进行学习

也就是说Paxos是基于议会制，以少数服从多数的核心思想来保证一致性的

Raft

该算法不做过多讲解，想要了解，请查看http://thesecretlivesofdata.com/raft/网址

Raft算法是一个分布式共识算法，有三个角色

1.Leader

2.follower

如果follower接收不到leader的心跳时，会变为candidate(这里会有150s~300s的等待时间)，发起投票是否成为新的leader

3.candidate(候选人)

核心思想：少数服从多数！

ZAB协议

zookeeper是基于该协议(zookeeper原子广播协议)实现的。这里只做简单介绍，该协议比较重要，后面会和zookeeper相关文章结合单独进行讲解！

该协议有两种模式:

1.崩溃恢复

2.消息广播

它和Paxos的区别联系在于:

1.都存在类似于Leader角色，负责协调多个Follower进程的运行

2.Leader进程都会等待超过半数的Follower做出正确反馈后，才会将一个提案进行提交

3.zab协议中，每个proposal都包含一个epoch值,用了代表当前Leader周期；Paxos中也存在同样的标识，名字为Ballot

4.zab协议主要用于构建一个高可用的分布式数据主备系统

5.Paxos算法主要用于构建一个分布式的一致性状态机系统

声明：本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系，我们将立即删除或处理。
▍相关推荐
更多资讯 >>>
Copyright @ 简易百科 V 2.0 京ICP备14042104号