分布式一致性与共识算法(一)

本文涉及的产品
服务治理 MSE Sentinel/OpenSergo,Agent数量 不受限
简介: 分布式一致性与共识算法(一)

是什么


从实现效果上来说,很多人或多或少都了解或者设计过具有强一致性的系统。但是,大部分人并不了解强一致性的系统是如何运作的,也不知道该怎么设计。老实说这确实很难,以至于计算机科学界有一类专门解决这种问题的算法 —— 共识算法。


ACID


就数据库来说,我们都知道要保证原子性(atomicity,或称不可分割性)、一致性(consistency)、隔离性(isolation,又称独立性)、持久性(durability)。


  • Atomicity(原子性):一个事务(transaction)中的所有操作,要么全部完成,要么全部不完成,不会结束在中间某个环节。事务在执行过程中发生错误,会被恢复(Rollback)到事务开始前的状态,就像这个事务从来没有执行过一样。


  • Consistency(一致性):在事务开始之前和事务结束以后,数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设规则,这包含资料的精确度、串联性以及后续数据库可以自发性地完成预定的工作。


  • Isolation(隔离性):数据库允许多个并发事务同时对其数据进行读写和修改的能力,隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别,包括读未提交(Read uncommitted)、读提交(read committed)、可重复读(repeatable read)和串行化(Serializable)。


  • Durability(持久性):事务处理结束后,对数据的修改就是永久的,即便系统故障也不会丢失。


CAP


就分布式来说,也需要保证CAP:一致性,可用性,分区容错性


CAP 理论是 Eric Brewer 教授在 2000 年提出 的,是描述分布式一致性的三个维度,分别是指:


  • 一致性(Consistency)


每次读操作都能保证返回的是最新数据;在分布式系统中,如果能针对一个数据项的更新执行成功后,所有的请求都可以读到其最新的值,这样的系统就被认为具有严格的一致性。


  • 可用性(Availablity)


任何一个没有发生故障的节点,会在合理的时间内返回一个正常的结果,也就是对于每一个请求总能够在有限时间内返回结果。


  • 分区容忍性(Partition-torlerance)


当节点间出现网络分区,照样可以提供满足一致性和可用性的服务,除非整个网络环境都发生了故障。那么,什么是网络分区呢?分区是系统中可能发生的故障之一,可能有节点暂时无法提供服务:发生了像 长时间 GC、CPU 死循环、链接池耗尽或者是网络通信故障等问题。


组合


CP 系统:一致且容忍分区的系统。更倾向于减少服务时间,而不是将不一致的数据提供出去。一些面向交易场景构建的 NewSQL 数据库倾向于这种策略,如 TiDB、阿里云 PolarDB、AWS Aurora 等。但是它们会生成自己的 A,也就是可用性很高。


AP 系统:可用且具有分区容忍性的系统。它放宽了一致性要求,并允许在请求期间提供可能不一致的值。一般是列式存储,NoSQL 数据库会倾向于 AP,如 Apache Cassandra。但是它们会通过不同级别的一致性模式调整来提供高一致性方案。


CP 系统的场景实现思路是需要引入共识算法,需要大多数节点参与进来,才能保证一致性。如果要始终保持一致,那么在网络分区的情况下,部分节点可能不可用。


而 AP 系统只要一个副本就能启动,数据库会始终接受写入和读取服务。它可能最终会丢失数据或产生不一致的结果。这里可以使用客户端模式或 Session 模型,来提供一致性的解决方案。


一致性概念


  • 严格一致性


这只是理论模型,现实中无法实现。因为各种物理限制使分布式数据不可能一瞬间去同步这种变化。


  • 线性一致性


如 TiKV


  • 顺序一致性


如 Google Megastore 这类系统都是使用 Paxos 算法实现了顺序一致性。也就是说在 Megastore 内部,如果有一个数据更新,所有节点都会同步更新,且操作在各个节点上执行顺序是一致的。


  • 因果一致性


因果一致性典型案例就是 COPS 系统,它是基于 causal+一致性模型的 KV 数据库。它定义了 dependencies,操作了实现因果一致性。这对业务实现分布式数据因果关系很有帮助。另外在亚马逊 Dynamo 基于向量时钟,也实现了因果一致性。


  • 最终一致性


Gossip协议


共识


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


为什么需要共识算法


从实现效果上来说,很多人或多或少都了解或者设计过具有强一致性的系统。但是,大部分人并不了解强一致性的系统是如何运作的,也不知道该怎么设计。老实说这确实很难,以至于计算机科学界有一类专门解决这种问题的算法 —— 共识算法。


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


会如何发展


列举


Paxos算法


Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。 Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。


Paxos算法除了难懂之外,还难以实现。尽管如此,以下服务还是在生产环境中使用了Paxos算法和Paxos算法的修改版。


Google Chubby:分布式锁服务


Google Spanner:NewSQL


Ceph


Neo4j


Amazon Elastic Container Service


ZAB(Zookeeper Atomic Broadcast)协议


官网上最古老的版本是 27 October, 2008: release 3.0.0 available


Zookeeper 通过 Zab 协议保证分布式事务的最终一致性。


【1】Zab协议是为分布式协调服务 Zookeeper专门设计的,是 Zookeeper保证数据一致性的核心算法。Zab借鉴了 Paxos算法,但又不像 Paxos那样,是一种通用的分布式一致性算法。支持崩溃恢复 和 原子广播协议。


【2】在 Zookeeper中主要依赖 Zab协议来实现数据一致性,基于该协议,zk实现了一种主备模型(即 Leader和 Follower模型)的系统架构来保证集群中各副本之间数据的一致性。主备系统架构模型指只有一台客户端(Leader)负责处理外部的写事务请求,然后 Leader客户端将数据同步到其他 Follower节点。


Raft 算法


由斯坦福大学的 Diego Ongaro 和 John Ousterhout 在 2014 年提出,在证明了算法的正确性之外,还提供了相关实现及参考代码。


Raft算法的应用:


分布式KV系统,etcd


微服务基础设施,consul


参考引用


分布式系统的一致性与共识性


分布式一致性与共识算法简介


从 Paxos 到 Raft,分布式一致性算法解析


分布式一致性算法,你确定不了解一下


分布式一致性算法-Paxos、Raft、ZAB、Gossip

相关实践学习
基于MSE实现微服务的全链路灰度
通过本场景的实验操作,您将了解并实现在线业务的微服务全链路灰度能力。
目录
相关文章
|
5天前
|
前端开发 JavaScript 算法
分布式系统的一致性级别划分及Zookeeper一致性级别分析
分布式系统的一致性级别划分及Zookeeper一致性级别分析
|
7天前
|
算法 Go 分布式数据库
构建高可用的分布式数据库集群:使用Go语言与Raft共识算法
随着数据量的爆炸式增长,单一数据库服务器已难以满足高可用性和可扩展性的需求。在本文中,我们将探讨如何使用Go语言结合Raft共识算法来构建一个高可用的分布式数据库集群。我们不仅会介绍Raft算法的基本原理,还会详细阐述如何利用Go语言的并发特性和网络编程能力来实现这一目标。此外,我们还将分析构建过程中可能遇到的挑战和解决方案,为读者提供一个完整的实践指南。
|
7天前
|
算法
基于一致性理论的微电网分布式控制策略仿真模型【自适应虚拟阻抗】【simulink仿真】
基于一致性理论的微电网分布式控制策略仿真模型【自适应虚拟阻抗】【simulink仿真】
|
7天前
|
算法
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
|
7天前
|
算法 Serverless 调度
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
|
7天前
|
存储 算法 安全
5. raft 一致性算法
5. raft 一致性算法
|
7天前
|
存储 运维 物联网
【专栏】OceanBase 是一款先进的分布式数据库系统,以其分布式架构、高扩展性、高可用性和强一致性特点,应对大规模数据处理挑战
【4月更文挑战第29天】OceanBase 是一款先进的分布式数据库系统,以其分布式架构、高扩展性、高可用性和强一致性特点,应对大规模数据处理挑战。它支持混合负载,适用于金融、电商和物联网等领域,提供高性能、低成本的解决方案。尽管面临技术复杂性、数据迁移和性能优化等问题,通过合理策略可克服挑战。随着技术发展,OceanBase 在数字化时代将持续发挥关键作用。
|
7天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
4天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
24 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
|
5天前
|
算法
MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
这段内容介绍了一个使用改进的麻雀搜索算法优化CNN-BiLSTM模型进行多输入单输出预测的程序。程序通过融合正余弦和柯西变异提升算法性能,主要优化学习率、正则化参数及BiLSTM的隐层神经元数量。它利用一段简单的风速数据进行演示,对比了改进算法与粒子群、灰狼算法的优化效果。代码包括数据导入、预处理和模型构建部分,并展示了优化前后的效果。建议使用高版本MATLAB运行。