精华内容
下载资源
问答
  • 共识和一致共识的区别
    2021-07-26 00:44:47

    此文为缝合的结果,来源见参考。
    本文为学习所用,如有侵权请告知本人。

    共识与一致性

    共识描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。 在实践中,要保障系统满足不同程度的一致性,核心过程往往需要通过共识算法来达成。

    共识算法解决的是对某个提案(proposal)大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛,如多个事件发生的顺序、某个键对应的值、谁是领导……等等。可以认为任何可以达成一致的信息都是一个提案。对于分布式系统来讲,各个节点通常都是相同的确定性状态机模型(又称为状态机复制问题,state-machine replication),从相同初始状态开始接收相同顺序的指令,则可以保证相同的结果状态。因此,系统中多个节点最关键的是对多个事件的顺序进行共识,即排序。

    一致性往往指分布式系统中多个副本对外呈现的数据的状态。如后面提到的顺序一致性、线性一致性等,描述了多个节点对数据状态的维护能力。

    共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。

    因此,一致性描述的是结果状态共识则是一种手段达成某种共识并不意味着就保障了一致性(这里的一致性指强一致性)。只能说共识机制,能够实现某种程度上的一致性。

    什么是一致性?

    在谈到一致性这个词时,你会想到CAP理论的 consistency,或者 ACID 中的 consistency,或者 cache 一致性协议的 coherence,还是 Raft/Paxos 中的 consensus?

    一致性大概是分布式系统中最容易造成困惑的概念之一,因为它已经被用烂了。在很多中文文献中,都将consistency,coherence,consensus 三个单词统一翻译为”一致性”。因此在谈一致性之前,我认为有必要对这几个概念做一个区分:

    Consensus

    准确的翻译是共识,关注的是多个提议者达成共识的过程。比如 Paxos,Raft 共识算法本质上解决的是如何在分布式系统下保证所有节点对某个结果达成共识,其中需要考虑节点宕机,网络时延,网络分区等分布式中各种问题。共识算法通常应用在复制状态机中,比如 etcd,zookeeper,用于构建高可用容错系统。在这种应用情景下,Raft/Paxos 共识算法被用来确保各个复制状态机(节点)的日志是一致的。类似的,区块链中非常重要的一部分也是共识算法,但通常使用是 POW(Proof of Work) 或 POS(Proof of Stake),这类共识算法通常适合用在公网,去中心化的情形下。

    Coherence

    Coherence 通只出现在 Cache Coherence 一词中,作为”缓存一致性”被提出。我们知道现代的多核 CPU Cache 都是多层结构,通常每个 CPU Core 都有一个私有的 LB/SB, L1, L2 级 Cache,多个 CPU Core 共享一个 L3 Cache。比如 CPU1 修改了全局变量 g 并写入了 CPU1 L1 Cache,此时 CPU2 要读取变量 g,然而 CPU2 L1 Cache 中的 g 仍然是旧值,这里就需要 Cache Coherence (以下简称 CC)机制来保证 CPU2 读取到的一定是 g 的最新值。因此,CC 的本质是让多组 Cache 看起来就像一组 Cache 一样。现代 CPU 都已经实现了 CC,通常程序员也不需要关心 CC 的具体实现策略,目前大部分 CPU 采用的是基于 MESI(Modified-Shared-Invalid-Exclusive) 协议的 CC,这里有一篇参考文章

    解释完了Consensus 和 Coherence,剩下 ACID 和 CAP,两者的 C 都叫做 Consistency,你可能以为这两者应该就是我们常提到的分布式中的一致性了吧。其实并不是,两者也是完全不同的概念。

    ACID Consistency

    ACID 中的一致性是指数据库的一致性约束,ACID 一致性完全与数据库规则相关,包括约束,级联,触发器等。在事务开始之前和事务结束以后,都必须遵守这些不变量,保证数据库的完整性不被破坏,因此 ACID 中的 C 表示数据库执行事务前后状态的一致性,防止非法事务导致数据库被破坏。比如银行系统 A 和 B 两个账户的余额总和为 100,那么无论 A, B 之间怎么转换,这个余额和是不变,前后一致的。

    CAP Consistency

    CAP 理论中的 C 也就是我们常说的分布式系统中的一致性,更确切地说,指的是分布式一致性中的一种: 线性一致性(Linearizability),也叫做原子一致性(Atomic consistency)。

    谈到 CAP,和一致性一样,CAP 理论也是个被滥用的词汇,关于 CAP 的正确定义可参考cap faq

    简单总结CAP理论,在一个分布式的存储系统中,只能Consistency, Availability, Partition三选二,而由于在大规模的分布式系统中,网络不可靠几乎是不可避免的,即Partition网络分区容忍是必选项,因此对系统设计需要在AP(舍弃一致性,可能读出不一致)和CP(发生网络分区时系统不可用,即无法写入)之间权衡。

    很多时候我们会用 CAP 模型去评估一个分布式系统,但这篇文章会告诉你 CAP 理论的局限性,因为 CAP 理论是一个被过度简化的理论(一个只能读写单个数据的寄存器),按照 CAP 理论,很多系统包括 MongoDB,ZooKeeper 既不满足一致性(线性一致性),也不满足可用性(任意一个工作中的节点都要可以处理请求),但这并不意味着它们不是优秀的系统,而是 CAP 定理本身并没有考虑处理延迟(为了做到强一致性的事务同步开销),硬件故障,可读/可写的部分可用性等。这里不再展开,推荐阅读原文。

    正因为 CAP 中对C和A的定义过度理想化,后来又有人提出了BASE 理论,即基本可用(Basically Available)、软状态(Soft State)、最终一致性(Eventual Consistency)。BASE的核心思想是即使无法做到强一致性,但每个应用都可以根据自身的业务特点,采用适当的方法来使系统达到最终一致性(关于最终一致性,这篇亚马逊CTO Werner Vogels的博客值得一读)。显然,最终一致性弱于 CAP 中的 线性一致性。很多分布式系统都是基于 BASE 中的”基本可用”和”最终一致性”来实现的,比如 MySQL/PostgreSQL Replication 异步复制。

    以下我们不再纠结CAP理论本身,而聚焦于分布式一致性的定义和基本概念。

    分布式“顺序”的概念

    要理解分布式一致性,先来谈谈分布式中几个必要的概念: 时间,事件,和顺序。

    分布式系统的时间主要分为物理时间和逻辑时间两种,物理时间是指程序能够直接获取到的 OS 时间,在分布式系统中,由于光速有限,你永远无法同步两台计算机的时间。想要在分布式中仅依靠物理时间来决定事件的客观先后顺序是不可能的。因此分布式系统中,通常使用逻辑时间来处理事件的先后关系。

    分布式中的事件不是瞬间的概念,它有一个起始和结束时间,因此不同进程 发起的事件可能发生重叠,对于发生重叠的事件,我们说它们是并发执行的,在物理时间上是不分先后的。

    理想情况下,我们希望整个分布式系统中的所有事件都有先后顺序,这种顺序就是全序,即整个事件集合中任意两个事件都有先后顺序。但 1.物理时间是很难同步的,2. 网络是异步的,因此在分布式系统中,想要维持全序是非常困难的。不同的节点对两个事件谁先发生可能具有不同的看法,并且大部分时候我只需要知道偏序关系,用于确保因果关系。所谓偏序关系是指:

    1. 如果a和b是同一个进程中的事件,并且a在b前面发生,那么 a->b
    2. 如果a代表了某个进程的消息发送事件,b代表另一进程中针对这同一个消息的接收事件,那么a->b
    3. 如果 a->b且b->c,那么a->c (传递性)

    逻辑时间中的 Lamport Clock和Vector Clock等都可以用于建立偏序关系。

    一致性的分类

    强一致性

    相比较严格一致性,强一致性对于时间上的限制不再那么苛刻。当满足强一致性时,需要满足以下要求 :

    当分布式系统中更新操作完成之后,任何多个进程或线程,访问系统都会获得最新的值。

    强一致性中分为两种情况 :

    • 顺序一致性
    • 线性一致性

    顺序一致性

    Leslie Lamport 在1979年提出了Sequential Consistency。

    顺序一致性是指任何执行结果都是相同的,就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的,并且每个进程的操作按照程序所指定的顺序出现在这个序列中 。

    什么是顺序一致性 ? 我们这里举一个例子

    假设现在存在两个线程A和B,有两个初始值x=y=0,两个线程分别执行以下两条指令。

    线程A线程B
    X=1Y=1
    ThreadA=YThreadB=X

    由于多线程的执行顺序并不一定,所以可能出现几种可能。

    情况1情况2情况3
    X=1Y=1X=1
    ThreadA=YThreadB=XY=1
    Y=1X=1ThreadA=X
    ThreadB=XThread=YThreadB=Y
    结果 : ThreadA = 0 ThreadB = 1结果 : ThreadA = 1 ThreadB = 0结果 : ThreadA = 1 ThreadB = 1

    我们能够看到,上述过程虽然是正常执行,但是由于多个线程的执行顺序不同,最终结果也发生了变化。

    **所谓的顺序一致性,**其实就是规定了一下两个条件:
    (1)单个线程内部的指令都是按照程序规定的顺序(program order)执行的
    (2)多个线程之间的执行顺序可以是任意的,但是所有线程所看见的整个程序的总体执行顺序都是一样的

    可以将满足顺序一致性的分布式系统想象成一个调度器,将多个并发线程的请求看做是多个FIFO请求队列;调度器只能从队列首部逐条取出请求并执行,调度器不能保证多个队列的调度顺序,但是调度器保证所有服务节点对队列的调度顺序是相同的。

    线性一致性(Linearizability)

    也叫做strong consistency或者atomic consistency,于 1987年提出,线性一致性强于顺序一致性,是程序能实现的最高的一致性模型,也是分布式系统用户最期望的一致性。 线性一致性要求 Server 在执行 Operations 时需要满足以下三点:

    1. 瞬间完成(或者原子性)
    2. 任何 Operation 都必须在其发起调用,收到响应之间被执行。
    3. 一旦某个Operatio执行之后,所有后续的Operations都可以观测被操作对象最新的值(如果是写操作的话)。

    如下例,线段表示一个Operation,左端点表示请求时间点,右端点表示相应时间点:
    在这里插入图片描述

    先下结论,上图表示的行为满足线性一致。

    对于同一个对象 x,其初始值为 1,客户端 ABCD 并发地进行了请求,按照真实时间(real-time)顺序,各个事件的发生顺序如上图所示。对于任意一次请求都需要一段时间才能完成,例如 A,“x R() A” 到 “x Ok(1) A” 之间的那条线段就代表那次请求花费的时间段,而请求中的读操作在 Server 上的执行时间是很短的,相对于整个请求可以认为瞬间,读操作表示为点,并且在该线段上。线性一致性中没有规定读操作发生的时刻,也就说该点可以在线段上的任意位置,可以在中点,也可以在最后,当然在最开始也无妨。

    第一点和第二点解释的差不多了,下面说第三点。

    反映出“最新”的值?我觉得三点中最难理解就是它了。先不急于对“最新”下定义,来看看上图中 x 所有可能的值,显然只有 1 和 2。四个次请求中只有 B 进行了写请求,改变了 x 的值,我们从 B 着手分析,明确 x 在各个时刻的值。由于不能确定 B 的 W(写操作)在哪个时刻发生,能确定的只有一个区间,因此可以引入上下限的概念。对于 x=1,它的上下限为开始到事件“x W(2) B”,在这个范围内所有的读操作必定读到 1。对于 x=2,它的上下限为 事件“x Ok() B” 到结束,在这个范围内所有的读操作必定读到 2。那么“x W(2) B”到“x Ok() B”这段范围,x 的值是什么?1 或者 2。由此可以将 x 分为三个阶段,各阶段"最新"的值如下图所示:
    在这里插入图片描述

    清楚了 x 的变化后理解例子中 A C D 的读到结果就很容易了。

    最后返回的 D 读到了 1,看起来是 “stale read”,其实并不是,它仍满足线性一致性。D 请求横跨了三个阶段,而读可能发生在任意时刻,所以 1 或 2 都行。同理,A 读到的值也可以是 2。C 就不太一样了,C 只有读到了 2 才能满足线性一致。因为 “x R() C” 发生在 “x Ok() B” 之后(happen before [3]),可以推出 R 发生在 W 之后,那么 R 一定得读到 W 完成之后的结果:2。

    如果说顺序一致性只保证单个客户端多个请求的执行顺序,线性一致性还保证了多个客户端请求的执行先后顺序;即,如果Client B的请求b发起时间晚于Client A的请求a相应时间,那么Client B的请求b一定晚于Client A的请求a,顺序一致不能给出该保证。

    弱一致性

    弱一致性是指系统并不保证对于从节点的后续访问都会返回最新的更新的值。系统在数据成功写入主节点之后,不保证可以立即从其他节点读到最新写入的值,也不会具体承诺多久读到。但是会尽可能保证在某个时间级别(秒级)之后,让数据达到一致性状态。也就是说,如果能容忍后续的部分或者全部访问不到,则是弱一致性。

    最终一致性

    最终一致性是弱一致性的特定形式,最终一致性保证主从节点之间数据不一致的状态只是暂时的。

    读写一致性

    手机刷虎扑的时候经常遇到,回复某人的帖子然后想马上查看,但我刚提交的回复可能尚未到达从库,看起来好像是刚提交的数据丢失了,很不爽。

    在这种情况下,我们需要读写一致性,也称为读己之写一致性。**它可以保证,如果用户刷新页面,他们总会看到自己刚提交的任何更新。**它不会对其他用户的写入做出承诺,其他用户的更新可能稍等才会看到,但它保证用户自己提交的数据能马上被自己看到。

    如何实现读写一致性?

    最简单的方案,**对于某些特定的内容,都从主库读。**举个例子,知乎个人主页信息只能由用户本人编辑,而不能由其他人编辑。因此,永远从主库读取用户自己的个人主页,从从库读取其他用户的个人主页。

    如果应用中的大部分内容都可能被用户编辑,那这种方法就没用了。在这种情况下可以使用其他标准来决定是否从主库读取,例如可以记录每个用户最后一次写入主库的时间,一分钟内都从主库读,同时监控从库的最后同步时间,任何超过一分钟没有更新的从库不响应查询。

    还有一种更好的方法是,客户端可以在本地记住最近一次写入的时间戳,发起请求时带着此时间戳。从库提供任何查询服务前,需确保该时间戳前的变更都已经同步到了本从库中。如果当前从库不够新,则可以从另一个从库读,或者等待从库追赶上来。

    单调读

    用户从某从库查询到了一条记录,再次刷新后发现此记录不见了,就像遇到时光倒流。如果用户从不同从库进行多次读取,就可能发生这种情况。

    单调读可以保证这种异常不会发生。单调读意味着如果一个用户进行多次读取时,绝对不会遇到时光倒流,即如果先前读取到较新的数据,后续读取不会得到更旧的数据。单调读比强一致性更弱,比最终一致性更强。

    实现单调读取的一种方式是确保每个用户总是从同一个节点进行读取(不同的用户可以从不同的节点读取),比如可以基于用户ID的哈希值来选择节点,而不是随机选择节点。

    *因果一致性

    在本文中阐述因果一致性可能并不是一个很好的时机,因为它往往发生在分区(也称为分片)的分布式数据库中。

    分区后,每个节点并不包含全部数据。不同的节点独立运行,因此不存在**全局写入顺序。**如果用户A提交一个问题,用户B提交了回答。问题写入了节点A,回答写入了节点B。因为同步延迟,发起查询的用户可能会先看到回答,再看到问题。

    为了防止这种异常,需要另一种类型的保证:因果一致性。 即如果一系列写入按某个逻辑顺序发生,那么任何人读取这些写入时,会看见它们以正确的逻辑顺序出现。

    这是一个听起来简单,实际却很难解决的问题。一种方案是应用保证将问题和对应的回答写入相同的分区。但并不是所有的数据都能如此轻易地判断因果依赖关系。如果有兴趣可以搜索向量时钟深入此问题。

    分布式一致性模型的局限性

    分布式一致性模型是被简化过的模型,它将整个分布式系统简化为single-object(如 k-v store, queue),single-op(如 Read/Write, Enqueue/Dequeue),因此有些东西是它没有讨论到的:

    1. single-object: 分布式系统有多个节点,不同的节点可能提供的一致性并不相同,比如连 master 节点可能满足线性一致性,而 slave 节点则不是。
    2. single-op: 前面的例子中,我们简单将事件当做原子性的操作,而在实践中,往往需要事务(2PC, 3PC)来保证整个分布式系统的内部一致性,这个内部一致性和我们前面讨论的外部一致性是有区别的。同样,事务,串行化这些东西和一致性模型也是不同的东西。

    因此一些分布式系统在不同的配置选项或不同的连接状态下,可能体现出不同的一致性。

    参考

    1. 线性一致性和 Raft | PingCAP线性一致性和 Raft | PingCAP
    2. 通俗易懂 强一致性、弱一致性、最终一致性、读写一致性、单调读、因果一致性 的区别与联系 - 知乎 (zhihu.com)
    3. 一致性杂谈 | wudaijun’s blog
    4. 分布式系统理论学习总结 | 无咎 NOTE (wujiu.space)
    更多相关内容
  • 所谓分布式共识(consensus),与CAP理论中的一致性(consistency)其实是异曲同工,就是在分布式系统中,所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法,它与一致性协议这个词也经常...
  • 在我们认知分布式理论时,有两个东西常常混在一起,在我的角度看来,他们应该是两个东西——共识算法与一致性协议。

    [系列目录]

    大话分布式理论之二——共识算法与一致性的区别

    大话分布式理论之一——从单体到SOA再到微服务

    在我们认知分布式理论时,有两个东西常常混在一起,在我的角度看来,他们应该是两个东西——共识算法与一致性协议。
    前者强调共识,即在一个范围内的所有节点,如何在一个确定的提案上达成一个统一的结论。
    后者强调多副本(或者叫多节点)上的数据一致。

    很经典的一个错误认知就是wikipedia在2019年8月的一个对Paxos的定义中,将其描述为“一致性算法”,这一错误在同年12月被修正:

    共识算法

    拜占庭将军问题

    要清晰的认知什么是共识算法,我们需要了解一个广为传播的问题——拜占庭将军问题。

    一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

    共识统一:只要每位将军的消息能够正确的到达其他将军那里,产生多数/少数的情况下,必将产生一个统一的共识。
    破坏共识

    • 叛徒将军,叛徒将军刻意谎报,每次拿到其他人的结果之后投票或弃权,导致票数五五开无法达成共识。
    • 叛徒信使或信使被拦截:同样会导致一样的情况,甚至可能让将军们产生截然不同的认知,产生行动的分裂——向提议进攻的将军的将军们送去的信全篡改成进攻,向提议撤离的将军的将军们送去的信全篡改成撤离。
    • 将军数量为偶数: 偶数情况下,可能产生五五开的局面。当然可以再次发起投票,但是也可能再次出现五五开。

    分布式理论中的将军们

    对于计算机分布式理论中,其实也存在着类似的场景,比如说区块链,比如在具体的应用中,我们部署服务的多个副本应用时需要产生一个主节点。

    • 有同学可能会问,要产生主节点的话,直接用redis锁/zookeeper来存储主节点标识不就可以了吗?

    当然可以,但是这里的前提是引入了三方协调者节点,如果不引入,单靠我们自己的一些应用节点该如何实现呢?

    此时共识算法就发挥作用了,一套完善的共识算法,可以帮助我们在集群启动时选举一个leader,并且在这个leader宕机的时候,还能重新选举一个leader上来。

    这里我们要强调一下,相较于拜占庭将军问题,企业级分布式应用不需要考虑上面的叛徒将军(叛徒节点)和叛徒信使(信道劫持)问题,因为分布式应用之间的通信一般都是隔离网络(内网),网络安全的事情可以交个安全部门去考虑。
    当然我们也可以简单思考一下,如果我们的应用是在公网上,该如何防止?区块链就是这样的场景,而他们的做法一般都是建立一套经济模型+POW等机制来预防这样的事情发生。

    共识算法-Paxos/Raft等

    Leslie Lamport是拜占庭将军问题的提出者,Paxos则是他提出的一种共识算法,可以应用在分布式系统中。
    具体的算法内容有兴趣可以再研究,我们这里之分析这些算法的作用。
    Paxos Wikipedia:https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95

    • Paxos
      多个副本节点对一个提案达成一个统一的结果,比如多副本节点的选主。
    • Multi-Paxos
      由于Paxos每次流程只能支持一个提案的达成,效率较低,于是又出现了Muti-Paxos,支持一次协调达成一揽子的提案。
    • Raft
      Raft是对Muti-Paxos的精简,强调易理解、易实现。
    • Multi-Raft
      当下很多分布式数据库存在分片,不同分片之间的数据/信息应该是隔离的,于是需要多个Raft来支持分片,每个Raft对应一个分片,这就是Multi-Raft。
    • ZAB
      ZAB也是对Multi-Paxos算法的改进,是Zookeeper中的选主机制,比Raft协议出现的更早。

    共识算法能解决一切共识问题吗?

    显然是不可以的。

    • 最大的问题就是脑裂
      什么是脑裂?

      副本节点之间的网络短时间产生隔离,那就很可能产生两/多个leader,当网络恢复正常时,两个leader都保留了下来,产生混乱。

    此时只能通过 一些标准来决定谁留下,谁下去

    • 另外一个问题是偶数节点
      在拜占庭将军冢也提到了偶数节点问题,也是因为这个原因,我们在一些zookeeper类似的情况中,官网往往会推荐我们配置的节点数为奇数,以此防止选举不成功-重复选举的情况发生。

    了解了什么是共识算法,我们再来聊一聊什么是分布式理论中的一致性。

    分布式理论中的一致性

    一致性的概念来自CAP理论的定义,其中的C就是一致性:

    在理论计算机科学中,CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer’s theorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:

    • 一致性(Consistency) (等同于所有节点访问同一份最新的数据副本)
    • 可用性(Availability)(每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据)
    • 分区容错性(Partition tolerance)(以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。)

    今天我们只看一致性:

    副本节点间的一致性(分布式一致性)

    一个分布式集群需要对外部提供强一致性,即集群内部某一台节点的数据发生了改变,必须要所有节点都同步到这个改变之后,外界才能访问集群获取数据。

    我们简单了解了什么是强一致性,那么现在我们常说的最终一致性又是什么?

    最终一致性:
    最终一致性属于弱一致性。

    弱一致性:在数据发生变化之后,节点间的数据会逐步趋向于一致。
    最终一致性:在数据发生变化时,一段时间后,节点间的数据会最终达到一致状态。

    而最终一致性的语义放到今天我们的实践环境中,往往代表的是不要求实时节点数据一致,但要求尽量短的时间窗口内达到数据一致。

    最终一致性的方案往往由可靠的异步化完成。

    案例-kafka中的一致性

    kafka是一个具有主从结构(多副本节点)的分布式消息队列,多副本,就意味着存在一致性问题,那么kafka是如何来实现强一致性与弱一致性的?
    其中一个可配置参数是min.insync.replicas,表示 最少的in-sync的节点数

    只有所有in-sync的节点都提交了,消息才算提交了。这个数值如果我们配置为全部节点数,那么显然这将是一个强一致性的配置,而如果我们配置的不是全部节点数,那么他就是弱一致性的配置,因为一次数据变更操作完成后,并不能保证每个副本拿到的数据一致。
    这也是为什么CAP中的C和A只能选择其一,数据一致性越强,需要同步的副本节点就越多(越全),耗时自然长,那么可对外系统服务的时间就相对缩短了。

    应用服务间的一致性(分布式事务一致性)

    应用服务中的最终一致性又有所不同,应用服务中的一致性往往谈的是分布式事务中的一致性,与数据库事务的ACID中的C是一样的。
    强调一个事务过程中,服务A产生的数据变更,对应的服务B也要做出符合逻辑的数据变更,这个因果关系是一定的。

    以具体的业务举例,一个下单流程中,支付服务成功收款,那么库存系统必须减少相应的库存,这就是分布式事务中的一致性。
    而分布式事务最终一致性,同样也是对一致性的时间限制放松,只要在一定时间内,最终的数据能够满足一致性即可。

    分布式事务的强一致性实现方案
    2PC(二阶段提交):

    2PC存在一些广为人知的问题,比如协调者和参与者宕机的case,于是出现了3PC,有兴趣的同学可以深入了解。

    在数据库领域,2PC的实现叫做XA事务。当然今天的分布式数据库基本上都是采取了其他的方案而非XA,这是后话。
    而在应用服务领域,应用2PC这些理论,产生了一些分布式事务的框架,比如Seata提供的XA/AT/TCC模式其实都有2PC的影子在里面。

    案例2-应用系统中的最终一致性

    应用系统中的最终一致性同样依赖可靠的异步化来实现。
    以下单为例,在事务发生的时候不去扣减库存,而是在事务结束之后,借用消息等方式实现库存的异步化扣减。
    当然,这样做的前提是这个业务系统中,库存的扣减没有对下单的动作的逻辑限制。

    那么消息又如何保证可靠呢?怎么保证一定不丢失呢?
    关于这个问题,可以参考ebay曾经提出的一种解决方案——MQ中间件+本地消息表方案。
    或者 RocketMq的事务消息等。


    欢迎关注微信公众号 【JAVA技术分享官】,公众号首发,持续输出原创高质量JAVA开发者知识点

    展开全文
  • 关于一致性协议和共识算法的一点点皮毛理解资料汇总

    一致性

    强一致性(原子一致性,顺序一致性)

    • 任何一次读都能读到某个数据的最近一次写的数据。

    • 系统中的所有进程,看到的操作顺序,都和全局时钟下的顺序一致。

    简言之,在任意时刻,所有节点中的数据是一样的。

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

    顺序一致性

    • 任何一次读都能读到某个数据的最近一次写的数据。
    • 系统的所有进程的顺序一致,而且是合理的。即不需要和全局时钟下的顺序一致,错的话一起错,对的话一起对。

    这里写图片描述

    1)图a是满足顺序一致性,但是不满足强一致性的。原因在于,从全局时钟的观点来看,P2进程对变量X的读操作在P1进程对变量X的写操作之后,然而读出来的却是旧的数据。但是这个图却是满足顺序一致性的,因为两个进程P1,P2的一致性并没有冲突。从这两个进程的角度来看,顺序应该是这样的:Write(y,2) , Read(x,0) , Write(x,4), Read(y,2),每个进程内部的读写顺序都是合理的,但是这个顺序与全局时钟下看到的顺序并不一样。

    2)图b满足强一致性,因为每个读操作都读到了该变量的最新写的结果,同时两个进程看到的操作顺序与全局时钟的顺序一样,都是Write(y,2) , Read(x,4) , Write(x,4), Read(y,2)。

    3)图c不满足顺序一致性,当然也就不满足强一致性了。因为从进程P1的角度看,它对变量Y的读操作返回了结果0。那么就是说,P1进程的对变量Y的读操作在P2进程对变量Y的写操作之前,这意味着它认为的顺序是这样的:write(x,4) , Read(y,0) , Write(y,2), Read(x,0),显然这个顺序又是不能被满足的,因为最后一个对变量x的读操作读出来也是旧的数据。因此这个顺序是有冲突的,不满足顺序一致性。

    弱一致性

    数据更新后,如果能容忍后续的访问只能访问到部分或者全部访问不到,则是弱一致性。

    最终一致性

    不保证在任意时刻任意节点上的同一份数据都是相同的,但是随着时间的迁移,不同节点上的同一份数据总是在向趋同的方向变化。

    简单说,就是在一段时间后,节点间的数据会最终达到一致状态。

    共识(Consensus)

    在介绍共识协议之前,我们要来聊聊它的三个属性。

    1. 正确性(Validity):诚实节点最终达成共识的值必须是来自诚实节点提议的值。
    2. 一致性(Agreement):所有的诚实节点都必须就相同的值达成共识。
    3. 终止性(Termination):诚实的节点必须最终就某个值达成共识。

    你会发现共识算法中需要有“诚实”节点,它的概念是节点不能产生失败模型所描述的“任意失败”,或是“拜占庭失败”。因为数据库节点一般会满足这种假设,所以我们下面讨论的算法可以认为所有节点都是诚实的。

    共识问题中所有的节点要最终达成共识,由于最终目标是所有节点都要达成一致,所以根本不存在一致性强弱之分。

    例如,Paxos是共识(Consensus)算法而不是强一致性(Consistency)协议。共识算法没有一致性级别的区分。

    一致性和共识的区别

    图3 Consistency和Consensus的区别

    从上面对一致性和共识的描述我们可以列出二者之间的一些联系如下:

    图4 Consistency和Consensus的关系

    可以说,Consistency是系统中需要保证的一个属性(即“Allowed ways”),而Consensus算法是实现Consistency的一种手段(主要是最终一致性)。当然,保证一致性的方法还有其它手段,如强一致性可通过2PC,3PC,TCC保证。

    一致性协议

    Quorum(本身并不能保证强一致性需要结合其他策略)

    Quorum与Paxos,Raft等一致性协议有什么区别,这个问题的答案本身很简单:一致性协议大多使用了Quorum机制,但仅仅有Quorum(R+W>N)机制是保证不了一致性的

    Quorum

    Quorum 在 1979 被提出,其主要数学思想来源于鸽巢原理

    这个协议有三个关键值NRW
    N表示数据所具有的副本数。
    R表示完成读操作所需要读取的最小副本数。
    W表示完成写操作所需要写入的最小副本数。

    该策略中,只需要保证R + W > N,就会提供强一致性的保证,因为读取数据的节点和被同步写入的节点是有重叠的(鸽巢原理)。

    分布式系统通常支持多副本,副本存放在不同节点上,读写时需要对多个副本进行操作。考虑到一致性问题,可以在写操作更新所有副本,而读取时只要读其中一个副本。但是,这样写负载太重了,读很轻松,读写负载明显不平衡。
      采用Quorum机制后,写操作需要即刻完成的副本数减少,读操作需要成功读取的副本数增加,一定程度上平衡了读写两种操作,系统整体性能会得到提升。比如,有5个副本,可以让写操作只要写完3个就返回。剩下的由系统内部缓慢同步完成。而读操作,则需要至少读3台,就可保证至少可以读到一个最新的数据。(鸽巢原理)

    例如:N=3,W=2,R=2,那么表示系统中数据有3个不同的副本,当进行写操作时,需要等待至少有2个副本完成了该写操作系统才会返回执行成功的状态,对于读操作,系统有同样的特性。由于R + W > N,因此该系统是可以保证强一致性的。

    NWR模型中的读(写)延迟由最慢的R(W)副本决定,有时为了获得较高的性能和较小的延迟,R和W的和可能小于N,这时系统不能保证读操作能获取最新的数据。

    如果R + W ≤ N,这时读取和写入操作是不重叠的,系统只能保证最终一致性,而副本达到一致的时间则依赖于系统异步更新的实现方式,不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

    下面为不同设置的几种特殊情况。
      当W = 1,R = N时,系统对写操作有较高的要求,但读操作会比较慢,若N个节点中有节点发生故障,那么读操作将不能完成。
      当R = 1,W = N时,系统要求读操作高性能、高可用,但写操作性能较低,用于需要大量读操作的系统,若N个节点中有节点发生故障,那么写操作将无法完成。
      当R = W = N / 2 + 1时,系统在读写性能之间取得了平衡,兼顾了性能和可用性,Dynamo系统的默认设置就是这种,即N=3,W=2,R=2。

    对于NWR模型来说,存在着版本冲突的问题,为此,Amazon的Dynamo引入了Vector Clock

    ZAB

    Raft

    raft-zh_cn/raft-zh_cn.md at master · maemual/raft-zh_cn (github.com)

    系统中每个结点有三个组件:

    状态机: 当我们说一致性的时候,实际就是在说要保证这个状态机的一致性。状态机会从log里面取出所有的命令,然后执行一遍,得到的结果就是我们对外提供的保证了一致性的数据
    Log: 保存了所有修改记录
    一致性模块: 一致性模块算法就是用来保证写入的log的命令的一致性,这也是raft算法核心内容

    Raft协议的每个副本都会处于三种状态之一:Leader、Follower、Candidate。

    Leader:所有请求的处理者,Leader副本接受client的更新请求,本地处理后再同步至多个其他副本;
    Follower:请求的被动更新者,从Leader接受更新请求,然后写入本地日志文件
    Candidate:如果Follower副本在一段时间内没有收到Leader副本的心跳,则判断Leader可能已经故障,此时启动选主过程,此时副本会变成Candidate状态,直到选主结束。

    1. Leader Election

    组成一个Raft集群至少需要三台机器,而Raft限制每一时刻最多只能有一个节点可以发起提案,这个限制极大的简化了一致性的实现,这个可以发起提案的节点称为Leader。因此所要解决的第一个问题便是:

    • 如何保证任何时候最多只有一个Leader节点
    • 以及当Leader节点异常时如何尽快的选择出新的Leader节点

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SXap7YH1-1656056424530)(http://catkang.github.io/assets/img/raft_subproblem/status_trans.jpg)]

    如上图所示:

    • 所有的节点以Follower的角色启动;
    • Leader周期性给其他节点发送心跳;
    • 在超时时间内没有收到心跳包的Follower变成Candidate,将自己的Term加一,并广播Vote请求,发起新一轮选举;
    • 选举结束:
      • 收到大多数节点的投票,变成Leader,并向其他节点发送自己Term的AppendEntry。在一个Term里,同一个Server只会给出一次投票,先到先得;
      • 收到相同或更大Term的AppendEntry,承认对方为Leader,变成Follower;
      • 超时,重新开始新的选举,通过随机的超时时间来减少这种情况得发生。

    2. Log Replication

    • Leader被选出来后,就可以接受客户端发来的请求了,每个请求包含一条需要被replicated state machines执行的命令。Leader会把它作为一个log entry append到日志中,然后给其它的server发AppendEntriesRPC请求。当Leader确定一个log entry被safely replicated了(大多数副本已经将该命令写入日志当中),就apply这条log entry到状态机中然后返回结果给客户端。如果某个Follower宕机了或者运行的很慢,或者网络丢包了,则会一直给这个Follower发AppendEntriesRPC直到日志一致。

      当一条日志是commited时,Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。

    • 到目前为止,我们都只关注了Leader崩溃的情况。FollowerCandidate崩溃后的处理方式比Leader要简单的多,并且他们的处理方式是相同的。如果Follower或者Candidate崩溃了,那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单地通过无限的重试;如果崩溃的机器重启了,那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC,但是还没有响应的时候崩溃了,那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的,所以这样重试不会造成任何问题。例如一个Follower如果收到附加日志请求但是他已经包含了这一日志,那么他就会直接忽略这个新的请求。

    3. Safety

    通过上述的两个子问题已经解决了大部分的难题,除了下面两个细节:

    1. Leader Crash后,新的节点成为Leader,为了不让数据丢失,我们希望新Leader包含所有已经Commit的Entry。为了避免数据从Follower到Leader的反向流动带来的复杂性,Raft限制新Leader一定是当前Log最新的节点,即其拥有最多最大term的Log Entry
    2. 通常对Log的Commit方式都是Leader统计成功AppendEntry的节点是否过半数。在节点频发Crash的场景下只有旧Leader Commit的Log Entry可能会被后续的Leader用不同的Log Entry覆盖,从而导致数据丢失。造成这种错误的根本原因是Leader在Commit后突然Crash,拥有这条Entry的节点并不一定能在之后的选主中胜出。这种情况在论文中有详细的介绍。Raft很巧妙的限制Leader只能对自己本Term的提案采用统计大多数的方式Commit,而旧Term的提案则利用“Commit的Log之前的所有Log都顺序Commit”的机制来提交,从而解决了这个问题。另一篇博客中针对这个问题有更详细的阐述Why Raft never commits log entries from previous terms directly

    Raft

    Gossip

    Gossip协议是基于六度分隔理论(Six Degrees of Separation)哲学的体现,简单的来说,一个人通过6个中间人可以认识世界任何人

    Gossip 过程是由种子节点发起,当一个种子节点有状态需要更新到网络中的其他节点时,它会随机的选择周围几个节点散播消息,收到消息的节点也会重复该过程,直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间,由于不能保证某个时刻所有节点都收到消息,但是理论上最终所有节点都会收到消息,因此它是一个最终一致性协议。

    在这里插入图片描述

    注意:Gossip 过程是异步的,也就是说发消息的节点不会关注对方是否收到,即不等待响应;不管对方有没有收到,它都会每隔 1 秒向周围节点发消息。异步是它的优点,而消息冗余则是它的缺点。

    Gossip 的特点(优势)

    1)扩展性

    网络可以允许节点的任意增加和减少,新增加的节点的状态最终会与其他节点一致。

    2)容错

    网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播,Gossip 协议具有天然的分布式系统容错特性。

    3)去中心化

    Gossip 协议不要求任何中心节点,所有节点都可以是对等的,任何一个节点无需知道整个网络状况,只要网络是连通的,任意一个节点就可以把消息散播到全网。

    4)一致性收敛

    Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播,因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。

    5)简单

    Gossip 协议的过程极其简单,实现起来几乎没有太多复杂性。

    Gossip 的缺陷

    分布式网络中,没有一种完美的解决方案,Gossip 协议跟其他协议一样,也有一些不可避免的缺陷,主要是两个:

    1)消息的延迟

    由于 Gossip 协议中,节点只会随机向少数几个节点发送消息,消息最终是通过多个轮次的散播而到达全网的,因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。

    2)消息冗余

    Gossip 协议规定,节点会定期随机选择周围节点发送消息,而收到消息的节点也会重复该步骤,因此就不可避免的存在消息重复发送给同一节点的情况,造成了消息的冗余,同时也增加了收到消息的节点的处理压力。而且,由于是定期发送,因此,即使收到了消息的节点还会反复收到重复消息,加重了消息的冗余。

    总结

    Gossip协议通过反熵传播(anti-entropy)和谣言传播(rumor mongering)两种机制进行实现并保证节点数据的最终一致性。

    1. 种子节点周期性的散播消息

    2. 被感染节点随机选择N个邻接节点散播消息

    3. 节点只接收消息不反馈结果,每次散播消息都选择尚未发送过的节点进行散播

    4. 收到消息的节点不再往发送节点散播,即单向不可逆,如A -> B,那么B进行散播的时候,不再发给 A

    所以适合于AP场景的数据一致性处理,常见应用有:P2P网络通信、Apache Cassandra、Redis Cluster、Consul。

    问题抛出

    拜占庭问题:如果有一个恶意传播消息的节点,Gossip协议的分布式系统就会出问题。

    问题描述:

    拜占庭将军问题是一个协议问题拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。 问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。 叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。

    问题的解决:

    论文中指出,对于拜占庭问题来说,假如节点总数为 N,故障节点数为 F,则当 N >= 3F + 1 时,问题才能有解,由 BFT 算法进行保证。

    例如,N = 3,F = 1 时。

    视图更换协议

    视图检查所有节点必须在同一个配置下才能正常工作。如果节点的视图配置不一致,比如主节点不一致、节点数量不一致,那统计合法票数的时候,真没法干了。

    在一致性协议里,已经知道主节点在整个系统中拥有序号分配,请求转发等核心能力,支配着这个系统的运行行为。然而一旦主节点自身发生错误,就可能导致从节点接收到具有相同序号的不同请求,或者同一个请求被分配多个序号等问题,这将直接导致请求不能被正确执行。视图更换协议的作用就是在主节点不能继续履行职责时,将其用一个从节点替换掉,并且保证已经被非拜占庭服务器执行的请求不会被篡改。即,核心有2点:1,主节点故障时,可能造成系统不可用,要更换主节点;2,当主节点是恶意节点时,要更换为诚实节点,不能让作恶节点作为主节点。

    最终一致性的实现方式

    直接邮寄(Direct Mail)、反熵(Anti-entropy)和谣言传播(Rumor mongering)是实现最终一致性的常用三种方法。

    直接邮寄(Direct Mail)

    每个节点更新都会立即从其变更节点邮寄通知到所有其他节点。

    主要是当节点有数据更新便开始遍历节点池,遍历发送其他所有节点消息来通知自身节点数据的更新情况

    好处:实现起来比较容易,数据同步也很及时
    缺点:当数据发送失败时,将数据缓存下来,然后重传。虽然实现起来比较容易,数据同步也很及时,但可能会因为缓存队列满了而丢数据。只采用直接邮寄是无法实现最终一致性的,

    节点A发送数据给B成功。
    节点A发送数据给D失败,但是节点A的缓存满了,发送的数据无法保存。
    节点B和D数据不一致

    反熵(Anti-entropy) (SI model) 熵:混乱的意思,反熵,就是反差异的意思

    Suspective(病原):处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。

    Infective(感染):处于 infective 状态的节点代表其有数据更新,并且会将这个数据分享给其他节点。

    每个节点都会定期随机选择节点池中的一些节点,通过交换数据内容来解决两者之间的任何差异。

    所有参与节点只有两种状态:Suspective(病原)、Infective(感染)
    过程是种子节点会把所有的数据都跟其他节点共享,以便消除节点之间数据的任何不一致
    缺点是消息数量非常庞大,且无限制;通常只用于新加入节点的数据初始化。
    反熵是一种通过异步修复实现最终一致性的方法。

    实现反熵的方式

    ● 推
    就是将自己的所有副本数据,推给对方,修复对方副本中的熵

    ● 拉
    就是拉取对方的所有副本数据,修复自己副本中的熵

    ● 推拉
    就是同时修复自己副本和对方副本中的熵

    对于反熵(anti-entropy) 这种方式,和直接邮寄(direct mail)相比的最大特点就是解决了消息丢失无法补偿容错导致的数据无法保持一致的致命问题。它通过单点的定时随机通知周边节点进行数据交互的方式保持各节点之间数据的一致性。这里需要注意的是,一致性的保持是在节点数据变更后一段时间内通过节点间的数据交互逐渐完成的最终一致,并且由于每个节点都定期广播数据到周边随机的一部分节点,因此在数据交互上是存在冗余和延迟的。

    注意
    反熵需要节点两两交换和比对自己所有的数据,执行反熵时通讯成本会很高,所以不建议在实际场景中频繁执行反熵,可以通过引入校验和(Checksum)等机制,降低需要对比的数据量和通讯消息等。

    执行反熵时,相关的节点都是已知的,而且节点数量不能太多,如果是一个动态变化或节点数比较多的分布式环境(比如在 DevOps 环境中检测节点故障,并动态维护集群节点状态),这时反熵就不适用了。那么当你面临这个情况要怎样实现最终一致性呢?答案就是谣言传播。

    谣言传播(Rumor mongering)(SIR model

    Suspective(病原)、Infective(感染)、Removed(愈除)。

    Removed(愈除):其已经接收到来自其他节点的更新,但是其并不会将这个更新分享给其他节点。

    所有的节点在最开始没有产生数据变更时都假设是未知状态,它是不知道任何谣言信息的
    当节点收到其他节点更新数据通知时,相当于听到了一条谣言,并将其视为热门开始传播给周边节点
    当某个节点谣言盛行时,它会定期随机选择其他节点,并确保另一个节点知道
    当某个节点发现周边节点都知道这个谣言时,该节点将停止将该谣言视为热点,并保留更新,而不会进一步传播
    节点 A 向节点 B、D 发送新数据
    节点 B 收到新数据后,变成活跃节点,然后节点 B 向节点 C、D 发送新数据。

    共识算法

    raft

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-231I5Umh-1656056424531)(https://segmentfault.com/img/remote/1460000022361105)]

    Raft和它的三个子问题 | CatKang的博客
    定期随机选择其他节点,并确保另一个节点知道
    当某个节点发现周边节点都知道这个谣言时,该节点将停止将该谣言视为热点,并保留更新,而不会进一步传播
    节点 A 向节点 B、D 发送新数据
    节点 B 收到新数据后,变成活跃节点,然后节点 B 向节点 C、D 发送新数据。

    共识算法

    raft

    [外链图片转存中…(img-231I5Umh-1656056424531)]

    Raft和它的三个子问题 | CatKang的博客

    展开全文
  • 一致和共识区别 一致性往往指分布式系统中多个副本对外呈现的数据的状态。共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。因此,一致性描述的是结果状态,共识则是一种手段。 在...

    一致性和共识的区别

    一致性往往指分布式系统中多个副本对外呈现的数据的状态。共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。因此,一致性描述的是结果状态,共识则是一种手段。

    在分布式系统中,我们常说的一致性问题就是:对于同一个数据的多个副本之间,如何保持其对外表现的数据一致性。例如,研究客户端B怎样能读取到客户端A做的修改,然后两者之间的数据可以达成一致。

    在实践中,要保障系统满足不同程度的一致性,核心过程往往需要通过共识算法来达成。共识算法解决的是对某个提案大家达成一致意见的过程。

    一致性

    分布式系统中的一致性按照对一致性要求的不同,主要分为,严格一致性,强一致性(线性一致性),顺序一致性,弱一致性、最终一致性。

    严格一致性

    假如有人说他设计了一个满足严格一致性的分布式系统,那么这个系统的外部表现就应该完全等价于一台计算机。这意味着,对于这个系统中任意数据项x的任何读操作将返回最近一次对x进行的写操作的结果所对应的值。对于所有的进程来说,所有写操作都是瞬间可见的,系统维持着一个绝对的全局时间顺序。

    事实上,严格一致性要求系统不发生任何故障,而且所有节点之间的通信无需任何时间这种理想的条件下,才能达到。因此现实世界中,这样的分布式系统是不存在的。
    在这里插入图片描述

    顺序一致性

    在讲强一致性之前,首先要讲一下顺序一致性,它虽然不满足强一致性,但是又优于弱一致性,是一种过渡状态。

    Leslie Lamport 在1979年提出了顺序一致性,对系统提出了两条访问共享对象时的约束:

    • 从单个处理器(线程或者进程)的角度上看,其指令的执行顺序以编程中的顺序为准;
    • 从所有处理器(线程或者进程)的角度上看,指令的执行保持一个单一的顺序;

    更通俗的解释,顺序一致性要满足两个条件:

    • 每个进程的内部操作顺序是确定不变的
    • 假设所有的进程都对一个存储单元执行操作,那么任一进程都可以感知到相同的操作顺序,即使感知到的操作顺序与实际的全局时钟顺序不同。(实际上就是保证所有进程感知到的写操作顺序是相同的)

    顺序一致性的关键在于找到一个满足现实情况的全局执行顺序,使其同时又能符合每个单独进程内部的操作顺序。
    在这里插入图片描述
    以上图片中(a)为顺序一致性,(b)不为顺序一致性。
    对于(a),由于要保持进程内部的操作顺序不能变,所以P3和P4中都是先读取x=b再读到x=a,所有两者感知到的写顺序是相同的,感知到的整体操作顺序为W(x)b -> R(x)b -> W(x)a -> R(x)a。
    对于(b),P3和P4感知到的写操作顺序不同,导致无法找到一个符合顺序一致性的整体操作顺序。

    顺序一致性中没有全局时钟的限制,多个进程的操作可以任意调整顺序,以找到符合每个单独进程内部的操作顺序的全局操作顺序。所以如果每个进程中感知到的写操作顺序是相同的,那么一定可以通过调整读操作的顺序来获得符合要求的全局操作顺序,那么一定是顺序一致性的。

    强一致性(线性一致性)

    当一个数据副本的更新操作完成之后,任何多个后续节点对这个数据的任意副本的访问都会返回最新的更新过的值。强一致性和严格一致性的区别在于强一致性中写操作是耗时的,对系统可用性的影响较大,只要上次的操作没有处理完,就不能让用户读取数据。

    线性一致性,是一种强一致性,在顺序一致性前提下加强了进程间的操作排序,形成唯一的全局顺序。线性一致性假设操作具有一个全局有效时钟的时间戳,要求时间戳在前的进程先执行,从而确定唯一的全局操作顺序,即所有的操作按照全局时钟的顺序被所有进程感知。

    顺序一致性和线性一致性的区别

    两者都要求所有进程感知到整体操作顺序是相同的。所有的写操作都以相同的顺序被每个进程感知。

    但是在顺序一致性中只需要保证单个进程中的操作顺序确定不变,而没有全局时钟的限制,多个进程中的操作可以任意排序,所以进程感知到的整体操作顺序可以不符合实际的全局时钟。只要能保证所有进程感知到相同的写操作顺序,即可保证顺序一致性。
    在线性一致性中,在顺序一致性的基础上,有了全局时钟的限制,所有操作必须按照全局时钟顺序,确定了唯一的全局顺序。同时这也保证了写操作之后,读操作必须读取最新数据,即强一致性。
    顺序一致性中,读操作可以不用读取最新的数据,即非强一致性。线性一致性中,读操作必须读取最新的数据,即强一致性。

    在这里插入图片描述
    图(a)满足顺序一致性,但是不满足线性一致性的。原因在于,从全局时钟的观点来看,P2进程对变量X的读操作在P1进程对变量X的写操作之后,然而读出来的却是脏数据。但是确实符合顺序一致性的,因为P1和P2感知到相同的写操作顺序: Write(y,2) ,Write(x,4)(虽然这并未从图上显示出来)。所以P1和P2可以感知到相同的整体操作顺序:Write(y,2) , Read(x,0) , Write(x,4), Read(y,2)。每个进程内部的读写顺序都是合理的,但是这个顺序与全局时钟下看到的顺序并不一样。

    图(b)满足强一致性,因为每个读操作都读到了该变量的最新写的结果,同时两个进程看到的操作顺序与全局时钟的顺序一样,都是Write(y,2) , Write(x,4), Read(x,4) ,Read(y,2)。

    一句话总结:顺序一致性要求所有进程感知到相同的操作顺序(本质上只需要保证感知到相同的写操作顺序),只要求单进程中操作顺序不变,整体顺序可以不遵循全局时钟。线性一致性要求所有进程感知到相同的按照全局时钟确定的整体操作顺序。

    弱一致性

    弱一致性是指系统并不保证后续进程或线程的访问都会返回最新的更新的值。系统在数据成功吸入之后,不承诺立即可以读到最新写入的值,也不会具体承诺多久读到。但是会尽可能保证在某个时间级别(秒级)之后。可以让数据达到一致性状态。

    最终一致性

    最终一致性是弱一致性的一种特例。某个进程更新了副本的数据,如果没有其他进程更新这个副本的数据,系统最终一定能够保证后续进程能够读取到写进的最新值。

    最终一致性根据更新数据后各进程访问到数据的时间和方式的不同,又可以区分为:

    • 因果一致性。如果进程A通知进程B它已更新了一个数据项,那么进程B的后续访问将返回更新后的值,且一次写入将保证取代前一次写入。与进程A无因果关系的进程C的访问遵守一般的最终一致性规则。
    • “读己之所写(read-your-writes)”一致性。当进程A自己更新一个数据项之后,它总是访问到更新过的值,绝不会看到旧值。这是因果一致性模型的一个特例。
    • 会话(Session)一致性。保证在同一个会话中,实现“读己之所写”一致性。如果由于某些失败情形令会话终止,就要建立新的会话,而且系统的保证不会延续到新的会话。
    • 单调(Monotonic)读一致性。如果进程已经看到过数据对象的某个值,那么任何后续访问都不会返回在那个值之前的值。
    • 单调写一致性。系统保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性,就非常难以编程了。

    共识

    在这里插入图片描述
    为了达到共识,每个进程都提出自己的提议(propose),最终通过共识算法,所有正确运行的进程决定(decide)相同的值。

    根据解决的是非拜占庭的普通共识问题还是拜占庭共识问题(是否允许系统内节点作恶,以及对完备性的不同要求),共识算法可以分为Crash Fault Tolerance(CFT)类算法和Byzantine Fault Tolerance(BFT)类算法。

    针对常见的非拜占庭错误的情况,已经存在一些经典的解决算法,包括Paxos、Raft及其变种等。这类容错算法往往性能比较好,处理较快,容忍不超过一半的故障节点。对于要能容忍拜占庭错误的情况,一般包括PBFT(Practical Byzantine Fault Tolerance)为代表的确定性系列算法、PoW为代表的概率算法等。

    对于确定性算法,一旦达成对某个结果的共识就不可逆转,即共识是最终结果;而对于概率类算法,共识结果则是临时的,随着时间推移或某种强化,共识结果被推翻的概率越来越小,成为事实上的最终结果。拜占庭类容错算法往往性能较差,容忍不超过1/3的故障节点。

    总结

    一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性,描述了多个节点对数据状态的维护能力。
    共识则描述了分布式系统中多个节点之间,彼此对某个提案达成一致结果的过程。因此,一致性描述的是结果,共识则是一种手段。
    共识方法可以用来实现强一致性。

    参考博客:
    https://zhuanlan.zhihu.com/p/68743917
    https://www.cnblogs.com/xdyixia/p/11716079.html
    https://wenku.baidu.com/view/2038aff77c1cfad6195fa7d4.html
    https://blog.csdn.net/chao2016/article/details/81149674
    https://blog.csdn.net/cadem/article/details/80359270

    展开全文
  • 一致性、顺序一致性、弱一致和共识 提到分布式架构就一定绕不开“一致性”问题,而“一致性”其实又包含了数据一致事务一致性两种情况,本文主要讨论数据一致性(事务一致性指ACID) 复制是导致出现数据...
  • Raft是分布式环境下的一致性算法,它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常类似于paxos协议(参见我...
  • 说的简单明了他们说你是泛泛而谈,算法这东西是讲明白的吗?自己不动手光想听别人...2000年,Eric Brewer教授在ACM分布式计算年会上指出了著名的CAP理论:分布式系统不可能同时满足一致性(Consistency),可用性(Availa
  • 共识算法和一致

    千次阅读 2018-04-08 14:48:12
    共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致性。讲,各个节点通常都是相同的确定性状态机模型(又称为...
  • 一致共识 ppt

    2018-12-16 20:22:07
    介绍区块链中的共识机制。 私有链(paxos, raft); 联盟链(pbft);公有链(pow)
  • 一致共识算法-BFT/PAXOS

    千次阅读 2022-06-01 15:51:03
    介绍了类Paxos算法BFT主流算法
  • 共识机制作为区块链的核心技术,决定了参与节点以何种方式对某些特定的数据 达成一致,关系到区块链的安全性、可扩展性去中心化程度等许多重要特性。共识设计的 优劣是区块链自治能否进入良性循环的关键。共识机制...
  • 1. 大村子因为人口增长变成 11 个小村落分散在地图各地 2. 村落之间的通信只能依靠信鸽 3. 一只信鸽可能无法完全覆盖所有村落,需要有中继村落代为传输消息
  • 共识、线性一致性、顺序一致性、最终一致性、强一致性讲解
  • 文章基于区块链共识机制应用于泛在电力物联网,首先分析区块链整体架构的特性,将其应用于泛在电力物联网身份认证环节,构建基于区块链的身份认证算法,解决了终端(SM)与数据聚合器(SP)之间的身份认证问题,提高...
  • 相亲大会的举办权会为村子带来巨大收益,为了产生合理的举办者,人们约定了几条规则:大会举办权从 A B 两个村子中产生,他们每一届都是候选村;投票时所有村落仅能投 A 或 B;用投票的方式产生举办者,少数服
  • Raft算法是一切以领导者为主,在分布式系统中,就一系列值达成共识与日志的一致。是一种强领导者模型,领导者的性能决定了整个集群的性能。它是现今最常用的一种分布式共识算法。Raft算法使用如下的三个角色,描述每...
  • 共识(Consensus)和一致性(Consistency)虽然近似,但还是有一些差别: 传统一致性研究 共识研究 侧重 节点共识过程最终达成的稳定状态 分布式节点达成...
  • FLP不可能原理(FLPimpossibility):在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。1985年 FLP原理实际上说明对于允许节点失效情况下,纯粹异步...
  • 关于糖尿病足管理预防的国际共识和实践指南 关于糖尿病足管理预防的国际共识和实践指南 J. Apelqvist K. Bakker WH van Houtum MH Nabuurs-Franssen NC Schaper* 代表糖尿病足国际工作组邮政信箱 9533,荷兰...
  • 共识算法是区块链的核心技术之一,没有共识算法就无法实现分布式节点间的状态一致。简单介绍了一种目前联盟链中常用的共识算法——实用拜占庭容错(PBFT,practical Byzantine fault tolerance)算法,并在其基础上...
  • Consistency(一致性):在事务开始之前事务结束以后,数据库的完整性没有被破坏。Isolation(隔离性):多个事务并发访问时,事务之间是隔离的,一个事务不应该影响其它事务运行效果。Durability(持久性):事务...
  • 摘要:本篇文章是【区块链之技术进阶】的第七篇文章,在之前的文章中咱们多多少少提及了共识算法等相关知识,但是却没有具体地更加深入地了解,本文就为大家掰一掰区块链共识机制与分布式一致性算法,两者究竟有什么...
  • Swirlds是一种算法,可构建强一致分区容错、点对点仅追加日志。 实现非常简单:代码被划分为与论文中相同的函数: 主循环(这是一个协程,用于启用逐步评估并避免线程)。 sync(, )它查询远程节点并更新本地...
  • 本文讨论构建容错分布式系统的算法协议的一些案例。假设所有问题都可能发生网络中的数据包可能会丢失、重新排序、重复推送或任意延迟;时钟只是尽其所能近似;节点可以暂停(如GC)或随时崩溃。构建容错系统的最好...
  • 由于版本的异步性以及提供并发访问的文档部分的潜在存在,可能会发生冲突并使部分副本无法整体合并:它们是不一致的,这意味着它们包含冲突的部分。 本文的目的是提出一种合并方法,该合并方法使用树自动机以这种...
  • 比特币的共识机制

    2018-11-28 10:40:14
    共识算法就是用来解决上述问题,分布式系统一致性的算法就是用来解决上述问题,从而保证分布式系统一致性的方法。 • 共识定义 : -- 终止 性(Termination ):所有 :所有 正常运作的进程(节点)最终会在有限步数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,895
精华内容 15,958
热门标签
关键字:

共识和一致共识的区别