Technology

Chart Type 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go 内存管理 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 回溯法 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup Linux网络源代码学习——整体介绍 zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM执行 git maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

Architecture

实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 在离线业务混部 RNN pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台 tf-operator源码分析 k8s批处理调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF 生命周期管理 openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Kubernetes webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 serverless 泛谈 概率论 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念入门 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 用户登陆 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 当我在说模板引擎的时候,我在说什么 用户认证问题 资源的分配与回收——池 消息/任务队列


共识算法

2019年05月12日

简介

一致性和共识算法

分布式共识问题和复制状态机

周志明:系统高可用和高可靠之间的矛盾,是由于增加机器数量反而降低了可用性带来的(节点可能会挂掉)。为缓解这个矛盾,在分布式系统里主流的数据复制方法,是以操作转移(Operation Transfer)为基础的。我们想要改变数据的状态,除了直接将目标状态赋予它之外,还有另一种常用的方法,就是通过某种操作,把源状态转换为目标状态。能够使用确定的操作,促使状态间产生确定的转移结果的计算模型,在计算机科学中被称为状态机(State Machine)。

  1. 状态机有一个特性:任何初始状态一样的状态机,如果执行的命令序列一样,那么最终达到的状态也一样。在这里我们可以这么理解这个特性,要让多台机器的最终状态一致,只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以。无论这个操作指令是新增、修改、删除或者其他任何可能的程序行为,都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。广播指令与指令执行期间,允许系统内部状态存在不一致的情况,也就是不要求所有节点的每一条指令都是同时开始、同步完成的,只要求在此期间的内部状态不能被外部观察到,且当操作指令序列执行完成的时候,所有节点的最终的状态是一致的。这种模型,就是状态机复制(State Machine Replication)。
  2. 在分布式环境下,考虑到网络分区现象是不可能消除的,而且可以不必去追求系统内所有节点在任何情况下的数据状态都一致,所以采用的是“少数服从多数”的原则。也就是说,一旦系统中超过半数的节点完成了状态的转换,就可以认为数据的变化已经被正确地存储在了系统当中。

根据这些讨论,我们需要设计出一种算法,能够让分布式系统内部可以暂时容忍存在不同的状态,但最终能够保证大多数节点的状态能够达成一致;同时,能够让分布式系统在外部看来,始终表现出整体一致的结果。这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响,能最终表现出整体一致的过程,就是各个节点的协商共识(Consensus)。这里需要注意的是,共识(Consensus)与一致性(Consistency)是有区别的:一致性指的是数据不同副本之间的差异,而共识是指达成一致性的方法与过程。

最难 paxos 和最易 raft ?日志 + 状态机 可以成为任何有意义的工程系统。比如 rocksdb,leveldb 等等 lsm 存储,它们数据先写 append log ,通过重放日志到达的系统状态一定是一致的。

《大数据经典论文解读》我们可以把一个数据库的写入操作,看成是一系列的顺序操作日志,也就是把对于数据库的写入,变成了一个状态机(而不是直接向一台或多态数据库发出cud指令)。而对于这个状态机的更新,我们需要保障高可用性和容错能力。这个需要我们对于某一个服务器上的日志追加写入,能够做到同步复制到多个服务器上。这样,在当前我们写入的节点挂掉的时候,我们的数据并不会丢失。为了避免单点故障,我们希望可以从多台服务器都能写入数据,但是又不能要求所有服务器都同步复制成功。前者,是为了确保某个服务器挂掉的时候,我们可以快速切换到另一台备用服务器;后者,是避免我们写入的时候,因为某一台服务器挂掉了就无法写入成功。所以,Paxos 这样的分布式共识算法的基本思路,就是这样几点:

  1. 日志追加写入的时候,只要能够半数的服务器完成同步复制就算写入成功了。
  2. 在有节点挂掉的时候,因为我们有多个服务器,所以系统可以自动切换恢复,而不是必须修复某一台服务器才能继续运行。
  3. 系统的数据需要有“一致性”,也就是不能因为网络延时、硬件故障,导致数据错乱,写入的数据读出来变了或者读不出来。

Paxos 算法的出发点,是为了达成分布式共识。状态机复制,只是分布式共识的一个特例,所以如果我们看原始的 Paxos 算法,去理解 Chubby 乃至 ZooKeeper 的实现,会有一个转化过程,不容易理解。而 Raft 算法,则是直接就从状态机复制的问题出发,算法和需要解决的问题直接对应。

关系

陈现麟:线性一致性是数据存储系统对外表现的一种形式,即好像只有一个数据副本,但是在实现数据一致性,实现容错的时候,我们需要共识算法的帮助。当然,这里要特别注意,我们通过共识算法,除了可以实现线性一致性,也可以实现顺序一致性等其他的数据一致性,共识算法是用来满足线性一致性的容错性的。同时,不使用共识算法,我们也可以实现数据的线性一致性,比如 ABD 和 SCD broadcast 之类的非共识算法,也可以实现线性一致性。

总而言之,我们通过共识算法,可以实现高可用的线性一致性,以及其他的一致性存储系统,在这种情况下,共识算法是手段,一致性是目的,先有共识算法,后有高可用的线性一致性系统。同时,不通过共识算法,我们也可以用其他的方法,来实现线性一致性等其他的一致性,在这种情况下,共识和一致性就没有关系了。不过,目前通过共识算法,来实现高可用的线性一致性模型,是一个最常见的选择。

事务和数据一致性是非常类似的,它们本质上都是期望它的一个完整操作是原子操作,研究的本质问题都是数据的一致性问题。只不过事务对一个完整操作的定义是,一个事务内,对一个或多个数据对象的一个或多个读写操作,它需要解决的是对多个数据对象操作的一致性问题;而数据一致性对一个完整操作的定义是,在多个数据副本上对一个数据对象的写操作,它要解决的是单个数据操作,复制到多个副本上的一致性问题。

两阶段提交

对于原子性来说,在分布式系统中,需要通过 2PC 或 3PC 之类的原子提交协议来实现。我们认为 2PC 或 3PC 之类的原子提交协议是共识协议。二阶段提交协议,不仅仅是协议,也是一种非常经典的思想。二阶段提交在达成提交操作共识的算法中应用广泛,比如 XA 协议、TCC、Paxos、Raft 等。在分布式系统中,为了让每个节点都能够感知到其他节点的情况,会进行多轮协商,“先搞清楚大家的想法再做决定”。所以不管是为了事务一致性,还是副本数据一致性,都有prepare 和 commit 的影子在。

  1. 如果没有 一个中心化的协调者 coordinator角色存在的话,每个节点都要与其它节点 进行两轮以上的通信。
  2. 如果有一个中心化的协调者coordinator角色,则由 coordinator 担任 “话事人”,每个participant 只需与coordinator 沟通即可(两轮以上)。网络中节点的数量和身份可以是提前确定好的,也或者干活前先推举一个“话事人”。

就好像连通n台服务器,要么两两都相连,要么大家都连在“交换机”上。协商的事情越复杂,人员构成越复杂,协商的次数、消息数量越多。协商2次 只是很理想的场景。

basic-paxos

每个Node 可以同时充当了两个角色:Proposer和Acceptor,在实现过程中, 两个角色在同一个进程里面。

  proposer acceptor 作用
prepare阶段 proposer 生成全局唯一且自增的proposal id,广播propose
只广播proposal id即可,无需value
Acceptor 收到 propose 后,做出“两个承诺,一个应答”
1. 不再应答 proposal id 小于等于当前请求的propose
2. 不再应答 proposal id 小于 当前请求的 accept
3. 若是符合应答条件,返回已经accept 过的提案中proposal id最大的那个 propose 的value 和 proposal id, 没有则返回空值
争取提议权,争取到了提议权才能在Accept阶段发起提议,否则需要重新争取
学习之前已经提议的值
accept阶段 提案生成规则
1. 从acceptor 应答中选择proposalid 最大的value 作为本次的提案
2. 如果所有的应答的天value为空,则可以自己决定value
在不违背“两个承诺”的情况下,持久化当前的proposal id和value 使提议形成多数派,提议一旦形成多数派则决议达成,可以开始学习达成的决议

假设一个分布式系统有五个节点,分别是 S1、S2、S3、S4 和 S5;全部节点都同时扮演着提案节点和决策节点的角色。此时,有两个并发的请求希望将同一个值分别设定为 X(由 S1 作为提案节点提出)和 Y(由 S5 作为提案节点提出);我们用 P 代表准备阶段、用 A 代表批准阶段,这时候可能发生下面四种情况。情况一:比如,S1 选定的提案 ID 是 3.1(全局唯一 ID 加上节点编号),先取得了多数派决策节点的 Promise 和 Accepted 应答;此时 S5 选定的提案 ID 是 4.5,发起 Prepare 请求,收到的多数派应答中至少会包含 1 个此前应答过 S1 的决策节点,假设是 S3。那么,S3 提供的 Promise 中,必将包含 S1 已设定好的值 X,S5 就必须无条件地用 X 代替 Y 作为自己提案的值。由此,整个系统对“取值为 X”这个事实达成了一致。PS: 这个图表示的特别好,其它情况就不一一列举了。这里的“设置值”不要类比成程序中变量赋值操作,应该类比成日志记录操作

目前比较好的通俗解释,以贿选来描述 如何浅显易懂地解说 Paxos 的算法? - GRAYLAMB的回答 - 知乎

另一种表述

应用程序连接到任意一台服务器后提起状态修改请求(也可以是获得某个状态锁的请求),从图上看也就是服务器 1,会将这个请求发送给集群中其他服务器进行表决。如果某个服务器同时收到了另一个应用程序同样的修改请求,它可能会拒绝服务器 1 的表决,并且自己也发起一个同样的表决请求,那么其他服务器就会根据时间戳和服务器排序规则进行表决。表决结果会发送给其他所有服务器,最终发起表决的服务器也就是服务器 1,会根据收到的表决结果决定该修改请求是否可以执行,事实上,只有在收到多数表决同意的情况下才会决定执行。当有多个请求同时修改某个数据的情况下,服务器的表决机制保证只有一个请求会通过执行,从而保证了数据的一致性。

multi-paxos

《分布式协议与算法实战》Multi-Paxos 是一种思想,不是算法,缺失实现算法的必须编程细节。而 Multi-Paxos 算法是一个统称,它是指基于 Multi-Paxos 思想,通过多个 Basic Paxos 实例实现一系列值的共识的算法(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。Multi Paxos 对 Basic Paxos 的核心改进是,增加了“选主”的过程。

  1. 提案节点会通过定时轮询(心跳),确定当前网络中的所有节点里是否存在一个主提案节点;
  2. 一旦没有发现主节点存在,节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程,向所有其他节点广播自己希望竞选主节点的请求,希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识;
  3. 如果得到了决策节点中多数派的批准,便宣告竞选成功。

当选主完成之后,除非主节点失联会发起重新竞选,否则就只有主节点本身才能够提出提案。此时,无论哪个提案节点接收到客户端的操作请求,都会将请求转发给主节点来完成提案,而主节点提案的时候,也就无需再次经过准备过程,因为可以视作是经过选举时的那一次准备之后,后续的提案都是对相同提案 ID 的一连串的批准过程。

注意,二元组 (id, value) 已经变成了三元组 (id, i, value),这是因为需要给主节点增加一个“任期编号”,这个编号必须是严格单调递增的,以应付主节点陷入网络分区后重新恢复,但另外一部分节点仍然有多数派,且已经完成了重新选主的情况,此时必须以任期编号大的主节点为准。

从整体来看,当节点有了选主机制的支持后,就可以进一步简化节点角色,不必区分提案节点、决策节点和记录节点了,可以统称为“节点”,节点只有主(Leader)和从(Follower)的区别。此时的协商共识的时序图如下:

在这个理解的基础上,我们换一个角度来重新思考“分布式系统中如何对某个值达成一致”这个问题,可以把它分为下面三个子问题来考虑:

  1. 如何选主(Leader Election),有paxos 就行, 当然会涉及到许多工程上的细节,比如心跳、随机超时、并行竞选等
  2. 如何把数据复制到各个节点上(Entity Replication),会涉及到网络分区、节点失联等
  3. 如何保证过程是安全的(Safety),选主的结果一定是有且只有唯一的一个主节点,不可能同时出现两个主节点;保证选主过程是一定可以在某个时刻能够结束的。

另一种表述:Basic Paxos达成一次决议至少需要两次网络来回,并发情况下可能需要更多,极端情况下甚至可能形成活锁,效率低下。Multi-Paxos选举一个Leader,提议由Leader发起,没有竞争,解决了活锁问题。提议都由Leader发起的情况下,Prepare阶段可以跳过,将两阶段变为一阶段,提高效率。Multi-Paxos并不假设唯一Leader,它允许多Leader并发提议,不影响安全性,极端情况下退化为Basic Paxos。Multi-Paxos与Basic Paxos的区别并不在于Multi(Basic Paxos也可以Multi),只是在同一Proposer连续提议时可以优化跳过Prepare直接进入Accept阶段。

Paxos 优化

以 Chubby 的 Multi-Paxos 实现为例

  1. 主节点作为唯一提议者,这样就不存在多个提议者同时提交提案的情况,也就不存在提案冲突的情况
  2. 在 Chubby 中,主节点是通过执行 Basic Paxos 算法,进行投票选举产生的,并且在运行过程中,主节点会通过不断续租的方式来延长租期(Lease)。
  3. 在 Chubby 中实现了兰伯特提到的,“当领导者处于稳定状态时,省掉准备阶段,直接进入接受阶段”这个优化机制,减少非必须的协商步骤来提升性能。
  4. 在 Chubby 中,为了实现了强一致性,所有的读请求和写请求都由主节点来处理。也就是说,只要数据写入成功,之后所有的客户端读到的数据都是一致的。

减少 Paxos 算法的网络开销:对于原本是两阶段的 Prepare-Accept 的请求,我们可以在 Accept 请求里,带上下一次 Paxos 算法里的 Prepare 请求。因为所有的外部请求都会先到达 Master,然后由 Master 发起提案,所以这样的策略在实现上非常容易。而且因为请求都是从 Master 发起的,所以达成共识的过程中很少会有冲突,往往一个 Prepare-Accept 的过程,共识就已经达成了。这样,原先是两阶段的 Prepare-Accept,常常只要一个网络请求就已经完成了,我们的 Paxos 算法在大部分情况下,就变成一个一阶段就能完成的了。

Raft

Raft(一):不会背叛的信使斯坦福大学在 2013 年发表的一篇论文《In Search of an Understandable Consensus Algorithm》。 中文版 Raft:寻找一种易于理解的一致性算法 论文大纲

  1. 复制状态机问题
  2. 讨论 Paxos 的优点和缺点
  3. 为了可理解性而采取的方法
  4. 阐述 Raft 一致性算法
  5. 评价 Raft 算法

论文提到,与 Paxos 不同,Raft的首要目标是可理解性,使用一些特别的技巧来提升它的可理解性

  1. Raft 算法则把问题拆分成了一个个独立的子问题(Raft 主要被分成了领导人选举,日志复制和安全三个模块),这些子问题都解决了,状态机复制的问题自然就解决了。我们只要能够理解和证明每一个子问题就够了,这个对于问题分而治之的办法,降低了理解问题的复杂度。首先是让系统里始终有一个 Leader,所有的数据写入,都是发送到 Leader。一方面,Leader 会在本地写入,另一方面,Leader 需要把对应的数据写入复制到其他的服务器上。这样,问题就变简单了,我们只需要确保两点,第一个是系统里始终有 Leader 可用;第二个,是基于 Leader 向其他节点复制数据,始终能确保一致性就好了。
    1. 因为 Leader 所在的服务器可能会挂掉,那么挂掉之后,我们需要尽快确认一个新 Leader,所以我们就需要解决第一个子问题,就是 Leader 选举问题。
    2. 我们需要保障分布式共识,所以 Leader 需要把日志复制到其他节点上,并且确保所有节点的日志始终是一致的。这个,就带来了第二个问题,也就是日志复制问题。
    3. 同时,在 Leader 挂掉,切换新 Leader 之后,我们会遇到一个挑战,新的 Leader 可能没有同步到最新的日志写入。而这可能会导致,新的 Leader 会尝试覆盖之前 Leader 已经写入的数据。这个问题就是我们需要解决的第三个问题,也就是“安全性”问题。
  2. Raft 算法加强了系统里的限制,使得问题在很多状态下被简化了。比如,Raft 算法是有一个强 Leader 的,而 Paxos 算法是无 Leader 或者弱 Leader 的。而因为有了强 Leader,Raft 算法就可以进一步地要求日志里面不能有空洞。使用随机化来简化 Raft 中领导人选举算法。

Raft 和 Paxos

Raft 算法属于 Multi-Paxos 算法,它是在兰伯特 Multi-Paxos 思想的基础上,做了一些简化和限制,比如增加了日志必须是连续的,只支持领导者、跟随者和候选人三种状态,在理解和算法实现上都相对容易许多。Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统(比如 Cubby、Spanner)都是在 Raft 算法发布前开发的,当时没得选;而全新的系统大多选择了 Raft 算法(比如 Etcd、Consul、CockroachDB)。

《In Search of an Understandable Consensus Algorithm》: In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered.

《In Search of an Understandable Consensus Algorithm》单决策(Single-decree)Paxos 是晦涩且微妙的:它被划分为两个没有简单直观解释的阶段,并且难以独立理解。正因为如此,它不能很直观的让我们知道为什么单一决策协议能够工作。为多决策 Paxos 设计的规则又添加了额外的复杂性和精巧性。我们相信多决策问题能够分解为其它更直观的方式。PS: 现实问题是多决策的,paxos 单决策出现在 多决策之前,彼时是以单决策的视角来考虑问题(在单决策场景下,选主不是很重要),又简单的以为将单决策 组合起来就可以支持 多决策。

Raft与Multi-Paxos中相似的概念:

raft Multi-Paxos
leader proposer
term proposal id
log entry proposal
log index instance id
Leader选举 prepare 阶段
日志复制 Accept阶段

Raft与Multi-Paxos的不同:

  raft Multi-Paxos
领导者 强leader 弱leader
领导者选举权 具有已连续提交日志的副本 任意副本
日志复制 保证复制 允许空洞
日志提交 推进commit index 异步的commit 消息

Raft 和 Paxos 最大的不同之处就在于 Raft 的强领导特性:Raft 使用leader选举作为一致性协议里必不可少的部分,并且将尽可能多的功能集中到了leader身上。这样就可以使得算法更加容易理解。例如,在 Paxos 中,leader选举和基本的一致性协议是正交的:leader选举仅仅是性能优化的手段,而且不是一致性所必须要求的。但是,这样就增加了多余的机制:Paxos 同时包含了针对基本一致性要求的两阶段提交协议和针对leader选举的独立的机制。相比较而言,Raft 就直接将leader选举纳入到一致性算法中,并作为两阶段一致性的第一步。这样就减少了很多机制。

强Leader在工程中一般使用Leader Lease和Leader Stickiness来保证:

  1. Leader Lease:上一任Leader的Lease过期后,随机等待一段时间再发起Leader选举,保证新旧Leader的Lease不重叠。
  2. Leader Stickiness:Leader Lease未过期的Follower拒绝新的Leader选举请求。

Leader 选举

Raft协议比paxos的优点是 容易理解,容易实现。它强化了leader的地位,把整个协议可以清楚的分割成两个部分,并利用日志的连续性做了一些简化:

  1. Leader在时。leader来处理所有来自客户端的请求,由Leader向Follower同步日志 ==> 日志流动是单向的
  2. Leader挂掉了,选一个新Leader
    1. 在初始状态下,集群中所有的节点都是follower的状态。
    2. Raft 算法实现了随机超时时间的特性。也就是说,每个节点等待Leader节点心跳信息的超时时间间隔是随机的。等待超时时间最小的节点(以下称节点 A),它会最先因为没有等到Leader的心跳信息,发生超时。
    3. 这个时候,节点 A 就增加自己的任期编号,并推举自己为候选人,先给自己投上一张选票,然后向其他节点发送请求投票 RPC 消息,请它们选举自己为领导者。
    4. 如果其他节点接收到候选人 A 的请求投票 RPC 消息,在编号为 1 的这届任期内,也还没有进行过投票,那么它将把选票投给节点 A,并增加自己的任期编号。
    5. 如果候选人在选举超时时间内赢得了大多数的选票,那么它就会成为本届任期内新的领导者。节点 A 当选领导者后,他将周期性地发送心跳消息,通知其他服务器我是领导者,阻止跟随者发起新的选举,篡权。

在 Raft 算法中,约定了很多规则,主要有这样几点

  1. 领导者周期性地向所有跟随者发送心跳消息,通知大家我是领导者,阻止跟随者发起新的选举。
  2. 如果在指定时间内,跟随者没有接收到来自领导者的消息,那么它就认为当前没有领导者,推举自己为候选人,发起领导者选举。
  3. 在一次选举中,赢得大多数选票的候选人,将晋升为领导者。
  4. 在一个任期内,领导者一直都会是领导者,直到它自身出现问题(比如宕机),或者因为网络延迟,其他节点发起一轮新的选举。
  5. 在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,并且按照“先来先服务”的原则进行投票。
  6. 日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。
  7. 如果一个候选人或者领导者,发现自己的任期编号比其他节点小,那么它会立即恢复成跟随者状态。
  8. 如果一个节点接收到一个包含较小的任期编号值的请求,那么它会直接拒绝这个请求。

在议会选举中,常出现未达到指定票数,选举无效,需要重新选举的情况。在 Raft 算法的选举中,也存在类似的问题,那它是如何处理选举无效的问题呢?其实,Raft 算法巧妙地使用随机选举超时时间的方法,把超时时间都分散开来,在大多数情况下只有一个服务器节点先发起选举,而不是同时发起选举,这样就能减少因选票瓜分导致选举失败的情况。如何避免候选人同时发起选举?

  1. 跟随者等待领导者心跳信息超时的时间间隔,是随机的;
  2. 如果候选人在一个随机时间间隔内,没有赢得过半票数,那么选举无效了,然后候选人发起新一轮的选举,也就是说,等待选举超时的时间间隔,是随机的。

日志复制

Leader,本质上是通过一个两阶段提交,来做到同步复制的。一方面,它会先把日志写在本地,同时也发送给 Follower,这个时候,日志还没有提交,也就没有实际生效。Follower 会返回 Leader,是否可以提交日志。当 Leader 接收到超过一半的 Follower 可以提交日志的响应之后,它会再次发送一个提交的请求给到 Follower,完成实际的日志提交,并把写入结果返回给客户端。

一旦被leader创建的条目已经复制到了大多数的服务器上,这个条目就称为可被提交的(commited)

副本数据是以日志的形式存在的,日志是由日志项组成,日志项是一种数据格式,它主要包含用户指定的数据,也就是指令(Command),还包含一些附加信息,比如索引值(Log index)、任期编号(Term)。

  1. 指令:一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
  2. 索引值:日志项对应的整数索引值。它其实就是用来标识日志项的,是一个连续的、单调递增的整数号码。
  3. 任期编号:创建这条日志项的领导者的任期编号。

  1. 接收到客户端请求后,领导者基于客户端请求中的指令,创建一个新日志项,并附加到本地日志中。
  2. 领导者通过日志复制 RPC,将新的日志项复制到其他的服务器。
  3. 当领导者将日志项,成功复制到大多数的服务器上的时候,领导者会将这条日志项应用到它的状态机中。
  4. 领导者将执行的结果返回给客户端。
  5. 当跟随者接收到心跳信息,或者新的日志复制 RPC 消息后,如果跟随者发现领导者已经提交了某条日志项,而它还没应用,那么跟随者就将这条日志项应用到本地的状态机中。

在实际环境中,复制日志的时候,你可能会遇到进程崩溃、服务器宕机等问题,这些问题会导致日志不一致。那么在这种情况下,Raft 算法是如何处理不一致日志,实现日志的一致的呢?

  1. 领导者通过日志复制 RPC 的一致性检查,找到跟随者节点上,与自己相同日志项的最大索引值。也就是说,这个索引值之前的日志,领导者和跟随者是一致的,之后的日志是不一致的了。
  2. 领导者强制跟随者更新覆盖的不一致日志项,实现日志的一致。

跟随者中的不一致日志项会被领导者的日志覆盖,而且领导者从来不会覆盖或者删除自己的日志。

深入剖析共识性算法 Raft

类似的思路:The Google File System (二):如何应对网络瓶颈?

ZAB

Paxos 算法有点过于复杂、实现难度也比较高,所以 ZooKeeper 在编程实现的时候将其简化成了一种叫做 ZAB 的算法(Zookeeper Atomic Broadcast, Zookeeper 原子广播)。

ZAB 算法的目的,同样是在多台服务器之间达成一致,保证这些服务器上存储的数据是一致的。ZAB 算法的主要特点在于:需要在这些服务器中选举一个 Leader,所有的写请求都必须提交给 Leader。由 Leader 服务器向其他服务器(Follower)发起 Propose,通知所有服务器:我们要完成一个写操作请求,大家检查自己的数据状态,是否有问题。如果所有 Follower 服务器都回复 Leader 服务器 ACK,即没有问题,那么 Leader 服务器会向所有 Follower 发送 Commit 命令,要求所有服务器完成写操作。这样包括 Leader 服务器在内的所有 ZooKeeper 集群服务器的数据,就都更新并保持一致了。如果有两个客户端程序同时请求修改同一个数据,因为必须要经过 Leader 的审核,而 Leader 只接受其中一个请求,数据也会保持一致。PS:怪不得带有广播二字

在实际应用中,客户端程序可以连接任意一个 Follower,进行数据读写操作。如果是写操作,那么这个请求会被这个 Follower 发送给 Leader,进行如上所述的处理;如果是读操作,因为所有服务器的数据都是一致的,那么这个 Follower 直接返回自己本地的数据给客户端就可以了。

其它

生活中面临的任何选择,最后都可以转换为一个问题:你想要什么(以及为此愿意牺牲什么)。任何不一致问题, 本质上都可以转换为一个一致问题。 一个队伍谁当老大 可以各不服气,但大家可以对“多票当选”取得一致,这就是所谓“民主”。你可以不尊重老大,但必须尊重价值观。而在basic-poxos 中,底层的“价值观”就是:谁的ProposerId 大谁的优先级更高。有了“优先级”/“价值观” 就可以让“无序”的世界变“有序”。