专栏首页分布式架构分布式架构设计篇-一致性算法概述
原创

分布式架构设计篇-一致性算法概述

- 一致性定义 -

提到一致性这个词,大家会想到外文中有几个单词,如CAP中的Consistency、Cache Coherence、区块链的Consensus。这三个单词在外文不同环境拥有不同的含义。但在汉字中统一可以翻译为“一致性”。因此在谈一致性之前,有必要对这几个概念做一个区分,否则很容易让人迷惑。

  • Coherence:出现在Cache Coherence 一词中,称为“缓存一致性”。
  • Consensus:准确翻译是共识,即多个提议者达成共识的过程,例如Paxos、Raft 就是共识算法,是一种共识理论,分布式系统是它的场景,一致性是它的目标。
  • Consistency:一致性,即在分布式系统中的所有数据备份在同一时刻的值是否相同。

一些常见的误解

  • 一致性等于共识?其实一致性比共识含义更宽泛,一致性指的是多个副本对外呈现的状态。包括线性一致性、顺序一致性、最终一致性等。而共识特指达成一致的过程,但注意,共识并不意味着实现了一致性,一些情况下它是做不到的。
  • 使用了 Raft 或者 Paxos 的系统都是线性一致的(Linearizability)吗?其实不然,共识算法只能提供基础,要实现线性一致还需要在算法之上做出更多努力

因为分布式系统引入了多个节点,节点规模越大,宕机、网络时延、网络分区就越会成为常态,任何一个问题都可能导致节点之间的数据不一致。Paxos 和 Raft 共识算法初始被提出来是为了在分布式场景下处理数据同步问题。因为分布式一致性的范围更大,且Paxos、Raft只需引入一些小改动就可以达到线性一致性,所以被扩展引申为“Paxos、Raft是分布式系统中的一致性算法”。

- 一致性分类 -

强一致性和弱一致性只是一种统称,按照从强到弱,可以划分为:

  • 线性一致性 Linearizability consistency 定义:任何操作都可能在调用或者返回之间原子和瞬间执行,也称为原子一致性(atomic consistency),是标准的强一致性(strong consistency)。简而言之,在任意时刻,保证对外提供的数据是一样的。主要实现的算法有 Paxos、Raft、PacificA 等,它们都达到以下要求:
    • 任何一次读都能读到某个数据的最近一次写的数据。
    • 系统中的所有进程,看到的操作顺序,都和全局时钟下的顺序一致。
  • 顺序一致性 Sequential consistency 定义:程序的执行顺序和它编写的顺序一致。因为读的操作通常不改变数据,所以通常我们也认为它算一种强一致实现,主要实现的算法有ZAB协议。它的特点有:
    • 一个线程中的所有操作必须按照程序的顺序来执行。
    • 不管程序是否同步,所有线程都只能看到一个单一的操作执行顺序。在顺序一致性内存模型中,每个操作都必须原子执行且立刻对所有线程可见。
  • 因果一致性 Causal consistency 定义:所有进程必须以相同的顺序看到具有潜在因果关系的写操作。即只有存在因果关系的写操作才要求所有使用者以相同的次序看到,对于无因果关系的写入则并行进行,无次序保证。因果一致性可以看作对顺序一致性性能的一种优化。
  • 管道一致性 PRAM/FIFO consistency 定义:所某一个使用者完成的写操作可以被其他所有的使用者按照顺序的感知到,而从不同使用者中来的写操作则无需保证顺序,就像一个一个的管道一样。通常我们认为它算是一种弱一致性。
  • 最终一致性 Eventual consistency 定义:存储系统保证如果没有新的更新提交,最终所有的访问都将获得最后的更新。主要实现算法有Gossip协议等,根据更新数据后各进程访问到数据的时间和方式的不同,又可以区分为:
    • 读不旧于写一致性 Read-your-writes Consistency :使用者读到的数据,总是不旧于自身上一个写入的数据。
    • 会话一致性:对系统数据的访问过程框定在了一个会话当中,系统能够保证在同一个有效的会话中实现“读己之所写”的一致性,也就是说,执行更新操作之后,客户端能够在同一个会话中始终读取到该数据项的最新值。
    • 单调读一致性 Monotonic-read Consistency :如果一个进程从系统中读取出一个数据项的某个值后,那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。
    • 单调写一致性 Monotonic-write Consistency :一个系统需要能够保证来自同一个进程的写操作被顺序地执行。
    • 写不旧于读一致性 Writes-follow-reads Consistency :写入的副本不旧于上一次读到的数据,即不会写入更旧的数据。

因果一致性因为实现非常困难,所以通常我们不认可这个分类。同理还有很多其他的弱一致性实现不具备太大的意义,也被排除释放一致性(Release Consistency)、滑动不一致(Delta Consistency)。

- 线性一致性 -

线性一致性是强一致性的标准实现,线性一致性分为:线性一致性写、线性一致性读。

线性一致性写

所有的 write 都会来到 Leader,write 会有 Op log Leader 被序列化,依次顺序往后 commit,并 apply 然后在返回,那么一旦一个 write 被 committed,那么其前面的 write 的 Op log 一定就被 committed 了,保证日志完整性。所有的 write 都是有严格的顺序的,一旦被 committed 就可见了。简而言之, 线性一致性写,就是Leader write + 过半写入 ,Raft、Paxos、ZAB都是这样实现的。

线性一致性读

线性一致性读的实现有很多方式,在Raft中,read 有多种实现:

  • Raft log Read:每个 read 都有一个对应的 Op log,和 write 一样,都会走一遍一致性协议的流程,会在此 Read Op log 被 Apply 的时候读,那么这个 read Op log 之前的 write Op log 肯定也被 applied 了,那么一定能够被读取到,读到的也一定是最新的。
  • ReadIndex:我们知道 Raft log read,会有 raft read log 的复制和提交的开销,所以出现了 ReadIndex,read 没有 Op log,但是需要额外的机制保证读到最新的,所以 read 发送给 Leader 的时候:
    • 它需要确认 read 返回的数据的那个点 ?必须返回最新 committed 的结果,但是一个节点刚当选 Leader 的时候并不知道最新的 committed index,这个时候需要提交一个 Noop log entry 来提交之前的 log entry,然后开始 Read;
    • 它需要确认当前的 Leader 是不是还是 Leader,因为可能因为网络分区,这个 Leader 已经被孤立了,所以 Leader 在返回 read 之前,先和 Replica-group 的其他成员发送 heartbeat 确定自己 Leader 的身份。通过上述两条保证读到最新被 committed 的数据。
  • Lease Read:主要是通过 lease 机制维护 Leader 的状态,来减少了 ReadIndex 每次 read 发送 heartheat 的开销。每次Follower进行读请求时,Leader只需要判断自己的Leader租约是否过期了,如果没有过期,直接可以回复Follower自己是Leader,但是该机制对于机器时钟要求很严格,如果有做时钟同步的话,可以考虑使用该线性读模式。
  • Follower Read:先去 Leader 查询最新的 committed index,然后拿着 committed Index 去 Follower read,从而保证能从 Follower 中读到最新的数据,当前 etcd 就实现了 Follower read。
- 总结 -

咱们整体介绍了一致性与共识的差别、一致性的分类,线性一致性的实现方案分类。总结如下:

  • 共识是一种数据同步过程,一致性是数据同步状态。所以一致性算法含义更广泛,包含了共识。
  • 强一致性分线性一致性、顺序一致性,根据场景可以选择合适的一致性算法。
  • 弱一致性因为实现成本和场景意义问题,我们通常认为弱一致性就是最终一致性。
- 作者介绍 -

林淮川

毕业于西安交通大学;奈学教育《百万架构师训练营》讲师、企业级源码内源负责人,前大树金融高级架构师、技术委员会开创者、技术总监;前天阳宏业交易事业部技术主管;多年互联网金融行业(ToB)经验。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分布式架构设计篇(五)-刚性事务之2PC详解

    ​ 分布式场景下,多个服务同时对服务一个流程,比如电商下单场景,需要支付服务进行支付、库存服务扣减库存、订单服务进行订单生成、物流服务更新物流信息等...

    林淮川
  • 分布式架构设计篇(四)-聊聊cap

    CAP理论,被戏称为“帽子理论”,CAP是Eric Brewer在2000年ACM研讨会上出了一个想法:“一致性、可用性和分区容错性三者无法在分布式系统中被同时...

    林淮川
  • 一致性算法 - Raft协议总述

    Raft协议起源于 2013 年 斯坦福 Diego Ongaro和John Ousterhout的论文《In Search of an Understanda...

    林淮川
  • CAP原理和最终一致性

    在足球比赛里,一个球员在一场比赛中进三个球,称之为帽子戏法(Hat-trick).在分布式数据系统中,也有一个帽子原理(CAP Theorem),不过此帽子非彼...

    后端技术探索
  • 谈谈数据一致性

    数据一致性这个单词在平常开发中,或者各种文章中都能经常看见,我们常常听见什么东西数据不一致了,造成了一定的损失,赶快修复一下。但是很多同学对一致性具体代表什么意...

    用户5397975
  • 「分布式架构」“一切都是分布式”说最终一致性

    大约一年前,我在一致性模型上写了这篇文章的第一个版本,但我从来没有对它感到满意,因为它写得很匆忙,而且这个主题足够重要,需要得到更彻底的处理。ACM Queue...

    首席架构师智库
  • 首次揭秘:腾讯TDSQL分布式多级一致性数据库系统技术

    ? 作者:李海翔,腾讯TDSQL专家工程师 “在分布式背景下,怎么实现双一致性(事务一致性、分布式一致性),并提高分布式事务型集群的处理效率?”腾讯TDSQL...

    腾讯技术工程官方号
  • 分布式理论——从ACID到CAP再到BASE

    在传统的数据中,有ACID四大原则,在分布式中也有对应的CAP理论和BASE理论,这些都是分布式理论的基础。 更多内容参考:大数据学习之路 ACID ACI...

    用户1154259
  • 分布式事务之ACID、BASE和CAP原理

    ACID,是指在数据库管理系统(DBMS)中,事务(transaction)所具有的四个特性:原子性(Atomicity)、一致性(Consistency)...

    lyb-geek
  • 简单聊聊数据一致性这个概念

    今天这篇笔记是讨论数据一致性概念的文章,作者是大名鼎鼎的All Things Distributed博客博主,AWS的CTO Werner Vogels。文章完...

    哒呵呵

扫码关注云+社区

领取腾讯云代金券