分布式一致性算法基本阐述

admin管理员组

文章数量:1534190

1、问题

Hadoop 集群当中 N 多的配置信息如何做到全局一致并且单点修改迅速响应到整个集群？
    --- 集群配置管理
Hadoop 集群中的 namonode 和 resourcemanager 的单点故障怎么解决？
    --- 主从架构集群的主节点的单点故障

2、计算机软件服务的发展

1、从集中式到分布式：最大的特点就是部署简单。
2、集中式：底层都是采用性能卓越的大型主机，一个节点单独完整作业，不用考虑多个节点之间的协调问题
3、分布式：
    1、概念
    分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统

    2、特点
    分布性
    对等性
    并发性
    缺乏全局时钟
4、分布式环境的各种问题
    通信异常
    三态（成功，失败，超时）（超时：请求发送成功，但是服务器接收不成功，或者请求发送成功，服务器相应成功，但是客户端接收不成功）
    节点故障
    网络分区

那么为了保持数据一致，软件开发者们都采取了那些措施做出了那些努力呢？

3、事务

1、概念：
    事务是由一系列对系统中数据进行访问与更新的操作所组成的一个程序的执行逻辑单元。
    宏观概念：指不可分割的一个逻辑执行单元
    狭义概念：数据库事务
2、特征：ACID

    原子性（Atomicity）：全部执行成功或者不成功，没有中间状态
    一致性（Consistency）：不能破坏数据库数据的完整性和一致性
    隔离性（Isolation）：并发的事务是相互隔离的。不能干扰
    持久性（Durability）：事务一旦提交，数据库对应数据的状态变更就是永久性的。

关于隔离性，补充一些知识点：

        隔离级别    脏读        可重复读    幻读
        未授权读取    存在        不可以        存在
        授权读取    不存在        不可以        存在
        可重复读取    不存在        可以        存在
        串行化        不存在        可以        不存在

        四种不同的事务处理级别：

        未授权读取：读未提交，允许脏读
        授权读取：读已提交
        重复读：事务过程中多次读取同一数据是一致的，该操作禁止不可重复读和脏读，可能出现幻读
        串行化： 最严格的事务隔离级别。事务串行执行，不能并行执行

        两个重点概念：
        脏读：读到事务提交之前的值，因为读取到的未提交事务，有可能回滚
        幻读：同样的事务操作，前后可能读取同一数据出现不一致

 

4、分布式事务

    前提：分布式系统中，每个节点都能知道自己的事务操作是否成功，但是没法知道系统中的其他节点的事务是否成功。这就有可能会造成分布式系统中的各节点的状态出现不一致。
    因此当一个事务需要跨越服务器节点，并且要保证事务的ACID特性时，就必须引入一个"协调者"的 角色。那么其他的各个进行事务操作的节点就都叫做"参与者"

    典型的两种分布式事务的提交模式：

    2PC
        提交事务请求
        执行事务请求

    3PC
        CanCommit
        PreCommit
        DoCommit

 

分布式一致性的问题：

    1、为了提高系统的可用性，以防止单点故障引起的系统不可用
    2、提高系统的整体性能，通过负载均衡技术，能够让分布在不同地方的数据副本，都能够为用户提供服务

一致性级别：
    1、强一致性：写入什么，读到什么。当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值。这种是对用户最友好的，就是用户上一次写什么，下一次就保证能读到什么。
    2、弱一致性：尽量保证数据一致性。系统并不保证连续进程或者线程的访问都会返回最新的更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。
    3、最终一致性：弱一致性的一个特例。在一个特定时间内，保持最终一致。系统保证在没有后续更新的前提下，系统最终返回上一次更新操作的值。在没有故障发生的前提下，不一致窗口的时间主要受通信延迟，系统负载和复制副本的个数影响。

 

详细去了解2PC和3PC之后，我们可以发现，无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。Google Chubby的作者Mike Burrows说过："there is only one consensus protocol, and that’s Paxos – all other approaches are just broken versions of Paxos." 意即世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。

那么Paxos算法到底是怎样的一种算法呢？首先看NRW

 

5、Quorum NRW

    Quorum机制是分布式场景中常用的，用来保证数据安全，并且在分布式环境中实现最终一致性的投票算法。这种算法的主要原理来源于鸽巢原理

    N: 复制的节点数，即一份数据被保存的份数。
    R: 成功读操作的最小节点数，即每次读取成功需要的份数。
    W: 成功写操作的最小节点数，即每次写成功需要的份数。

    Write to all copies with latest version N, 
    wait synchronously for W success Read from all copies, 
    wait for first R responses, 
    pick the highest version number

    条件：W + R > N    保证一定能读取到最新的数据
              W + R > N    保证一定能读取到最新的数据
              W + R > N    保证一定能读取到最新的数据

    结论：这三个因素决定了可用性，一致性和分区容错性。
    只需W + R > N，就可以保证强一致性。

    在保证了强一致性的情况下：并且N一经固定，那么
    如果
        W = 1, R = N
            在分布式环境中，写一份，那么如果要读取到最新数据，就必须要读取所有节点，然后取最新版本的值了。
            对写操作要求高性能高可用。但是读麻烦
        R = 1, W = N, Read Only Write All
            在分布式环境中，所有节点都同步完毕，才能读取，所以只要读取任意一个节点就可以读取到最新数据
            对读操作要求高性能高可用，比如类似cache之类业务。
        W = Q, R = Q where Q = N/2 + 1
            可以简单理解为写超过一半节点，那么读也超过一半节点，取得读写性能平衡
            一般应用适用，读写性能之间取得平衡。如N=3,W=2,R=2

    这就是著名的鸽巢原理：
        即当数据备份存在N份时，k份数据已经更新，那么只要获取N−K+1个数据副本，至少有一个数据是更新了的。获取其中版本最高的那份数据，即最新的。
    目的就只有一个：就是为了在读写操作性能都不错的情况下取得数据一致性

 

抽屉原理也即鸽巢原理

回顾抽屉原理，2个抽屉每个抽屉最多容纳2个苹果，现在有3个苹果无论怎么放，其中的一个抽屉里面会有2个苹果。那么我们把抽屉原理变变型，2个抽屉一个放了2个红苹果，另一个放了2个青苹果，我们取出3个苹果，无论怎么取至少有1个是红苹果，这个理解起来也很简单。我们把红苹果看成更新了的有效数据，青苹果看成未更新的无效数据。便可以看出来，不需要更新全部数据（并非全部是红苹果）我们就可以得到有效数据，当然我们需要读取多个副本完成（取出多个苹果）。这就是Quorum机制的原型，其实质是将Write All 的负载均衡到 Read Only 上。

 

6、CAP理论

   2000年7月份被首次提出。CAP理论告诉我们，一个分布式系统不可能同时满足C,A,P三个需求

    C：Consistency，一致性： 
        多个副本保持一致
    A：Availability，可用性：
        系统提供的服务必须一直处于可用，对于用户的每一个操作请求总是能在有限时间内返回结果
    P：Partition Tolerance分区容错性：
        分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务

    放弃P：最简单的极端做法，就是放置在一个节点上。放弃P也就意味着放弃了系统的可扩展性
    放弃A：一旦系统遇到网络分区或者其他故障时，服务需要等待一段时间，在等待时间内就无法正常对外提供服务，即服务不可用
    放弃C：事实上，放弃一致性是指放弃数据的强一致性，而保留最终一致性，具体多久达到数据同步取决于存储系统的设计

    经验：
    1、架构师不要花费精力浪费在设计同时满足CAP的存储系统
    2、分区容错性往往是分布式系统必然要面对和解决的问题。所以架构师应该把精力放在如何根据业务特点在A和C之间寻求平衡。

    经验推荐，也是以往各种软件的设计经验：
    1、对于单机软件，因为不用考虑P，所以肯定是AC型，比如MySQL
    2、对于分布式软件，因为一定会考虑P，所以又不能兼顾A和C的情况下，只能在A和C做权衡，比如HBase, Redis等
    做到服务基本可用，并且数据最终一致即可。所以就有了BASE理论

7、BASE理论

是对CAP理论中的C和A的权衡结果：  不是强一致，而是最终一致， 不是可用，而是基本可用。    

Basically Available：基本可用
        响应时间的损失
        功能上的损失
Soft State：软状态
        允许存在不同节点同步数据时出现延迟，且出现数据同步延迟时存在的中间状态也不会影响系统的整体性能。
Eventually Consistent：最终一致性
        系统中所有数据副本，在经过一段时间后，都可以达到同步：要求最终达到一致，而不是实时强一致

 

8、Paxos算法

    Paxos算法是Lesile Lamport提出的一种基于消息传递且具有高度容错特性的一致性算法。分布式系统中的节点通信存在两种模型: 共享内存和消息传递。基于消息传递通信模型的分布式系统，不可避免会发生进程变慢被杀死，消息延迟、丢失、重复等问题，Paxos算法就是在存在以上异常的情况下仍能保持一致性的协议。

    Paxos算法使用一个希腊故事来描述，在Paxos中，存在三种角色，分别为
    Proposer(提议者，用来发出提案proposal), 
    Acceptor（接受者，可以接受或拒绝提案), 
    Learner(学习者，学习被选定的提案，当提案被超过半数的Acceptor接受后为被批准)。
    
    下面更精确的定义Paxos要解决的问题： 
    1、决议(value)只有在被proposer提出后才能被批准 
    2、在一次Paxos算法的执行实例中，只批准(chose)一个value 
    3、learner只能获得被批准(chosen)的value

    所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为leader服务器，而余下的其他服务器则成为follower服务器。leader服务器负责将一个客户端事务请求转换成一个事务proposal，并将该proposal分发给集群中所有的follower服务器。之后leader服务器需要等待所有follower服务器的反馈，一旦超过半数的follower服务器进行了正确的反馈后，那么leader就会再次向所有的follower服务器分发commit消息，要求其将前一个proposal进行提交。

    ZAB协议需要确保那些已经在leader服务器上提交的事务最终被所有服务器都提交。
    ZAB协议需要确保丢弃那些只在leader服务器上被提出的事务。
    如果让leader选举算法能够保证新选举出来的leader服务器拥有集群中所有机器最高编号（ZXID）的事务proposal，那么就可以保证这个新选举出来的leader一定具有所有已经提交的提案。

    ZAB两种基本的模式：崩溃恢复和消息广播。    

 

本文标签： 分布式算法一致性