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

本文涉及的产品
服务治理 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实现微服务的全链路灰度
通过本场景的实验操作,您将了解并实现在线业务的微服务全链路灰度能力。
目录
相关文章
|
1月前
|
NoSQL 算法 安全
Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题
Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题
152 0
|
1月前
|
存储 缓存 负载均衡
分布式系统Session一致性问题
分布式系统Session一致性问题
31 0
|
19天前
|
缓存 算法 关系型数据库
深度思考:雪花算法snowflake分布式id生成原理详解
雪花算法snowflake是一种优秀的分布式ID生成方案,其优点突出:它能生成全局唯一且递增的ID,确保了数据的一致性和准确性;同时,该算法灵活性强,可自定义各部分bit位,满足不同业务场景的需求;此外,雪花算法生成ID的速度快,效率高,能有效应对高并发场景,是分布式系统中不可或缺的组件。
深度思考:雪花算法snowflake分布式id生成原理详解
|
19天前
|
存储 算法 前端开发
作者推荐 | 分布式协议之巅 — 揭秘基础Paxos与Raft协议如何实现分布式系统达成一致性(非变种Paxos协议)
作者推荐 | 分布式协议之巅 — 揭秘基础Paxos与Raft协议如何实现分布式系统达成一致性(非变种Paxos协议)
17 0
|
1月前
|
算法 Java 数据中心
分布式ID生成系统之雪花算法详解
在当今的云计算和微服务架构盛行的时代,分布式系统已成为软件开发的重要组成部分。随着系统规模的扩大和业务的复杂化,对数据一致性和唯一性的要求也越来越高,尤其是在全局唯一标识符(ID)的生成上。因此,分布式ID生成系统应运而生,成为保证数据唯一性和提高系统可扩展性的关键技术之一。雪花算法(Snowflake)是Twitter开源的一种算法,用于生成64位的全局唯一ID,非常适用于分布式系统中生成唯一标识符。下面我们将深入探讨雪花算法的原理、结构和实现方式。
93 2
 分布式ID生成系统之雪花算法详解
|
1月前
|
NoSQL 关系型数据库 MySQL
分布式锁(redis/mysql)
分布式锁(redis/mysql)
54 1
|
3月前
|
NoSQL Java 测试技术
字节二面:Spring Boot Redis 可重入分布式锁实现原理?
字节二面:Spring Boot Redis 可重入分布式锁实现原理?
157 1
|
21天前
|
NoSQL Java Redis
如何通俗易懂的理解Redis分布式锁
在多线程并发的情况下,我们如何保证一个代码块在同一时间只能由一个线程访问呢?
31 2
|
1月前
|
缓存 NoSQL Java
【Redis】5、Redis 的分布式锁、Lua 脚本保证 Redis 命令的原子性
【Redis】5、Redis 的分布式锁、Lua 脚本保证 Redis 命令的原子性
56 0