### Paxos 算法解析

#### 并发问题

先看一个基本并发问题，假设有一个\<K,V>存储集群，三个客户端并发地向集群发送三个请求。请问，最后在`get(X)`的时候，X应该等于几?

从客户端的角度来看，三个请求是并发的，但三个请求到达服务器的顺序是不确定的，所以最终三个结果都有可能。

![4.png](https://developer.qcloudimg.com/http-save/yehe-10334881/894b1a0c50e5c53f0fff837bb6dc7ff2.png)

#### 时序

把上个问题进一步细化：假设\<K,V>存储集群有三台机器，机器之间互相通信，把自己的值传给其他机器，三个客户端分别向三台机器发生三个请求。假设每台机器把收到的请求按日志存下来（包括客户端的请求和其他节点的请求）。等到的结论是：**不管顺序如何，只要三台机器的日志顺序是一样的，结果就是正确的。**

![5.png](https://developer.qcloudimg.com/http-save/yehe-10334881/f56ce7880f90ec39dfcff66b05f5959b.png)

这个就是对于时序这个概念的直观理解，虽然三个客户端是并发的，没有先后顺序，但到了服务器集群中必须保证三台机器的日志顺序是一样的，这就是所谓的**分布式一致性。**

#### 复制状态机

可以把一个变量X或一个对象看成一个状态机。每一次写请求，就是一次导致状态机发生变化的事件，也就是日志。这里就涉及到了一个非常重要的思想：要选择持久变化的事件流（日志流），而不是选择持久化数据本身（状态机），原因如下：

![6.png](https://developer.qcloudimg.com/http-save/yehe-10334881/cb062d9016b0f09656e3e3e7bfce454a.png)

1、日志只有一种操作，就是追加。而数据或状态一直在变化，可以新增、删除、更新。把三种操作转换成一种，对于持久化存储来说简单了很多。

2、假如要做多机之间的数据同步，如果直接同步状态，状态本身可能有一个很复杂的数据结构（如关系数据库的关联表、树、图），并且状态也一直在变化，为了保证多个机器数据一致，需要做数据对比，就很麻烦，而如果同步日志，日志是一个一维的线性序列，做数据对比就非常容易。

无论是从持久化，还是从数据同步角度来看，存储状态机的输入日志流，比存储状态机本身更容易。

基于这种思路，可以把状态机扩展为复制状态机。状态机的原理是：一样的初始状态+一样的输入事件=一样的最终状态。因此，要保证多个节点的状态完全一致，只要保证多个节点的日志流是一样的即可。即使这个节点宕机，只需要重启和重放日志流，就能恢复之前的状态。

### Raft 算法解析

#### 单点写入

为了简化Paxos 晦涩难懂的问题，Raft限制为单点写入，必须选出一个Leader，并且任一时刻只允许一个有效的Leader存在，所有的写请求都传到Leader上，然后有Leader同步给超过半数的Follower。

这样一来问题则简化了很多，不用考虑节点之间的双向数据同步问题，数据的同步是单向的：只会从Leader同步到Follower，不会从Follower同步到Leader。

阶段1：选举阶段，选举出Leader，其他机器为Follower。

阶段2：正常阶段，Leader接收写请求，然后复制给其他Follower。

阶段3：恢复阶段，旧Leader宕机，新Leader上任，其他Follower切换到新Leader，开始同步数据。

#### 日志结构

复制的日志文件，需要先介绍日志的结构，因为复制的就是日志，日志的存储结构是这个算法的基石。每条日志里面都有两个关键字段：**term 和 index。** term只会单调递增，日志的顺序满足一个条件：后一条日志的term大于或等于前一条日志的term。

term 的核心作用：

**1、term 的一个关键作用是可以解决Leader的脑裂问题。** 假设一个集群有五台机器，当前的Leader 的 term =4，某一时刻发生了网络分区，Leader 在一个区，其他四个Follower在另外一个区。此时Leader 没有宕机，但是其他四个Follower认为他已经宕机了。

这时，在其他四个Follower中又选举出一个新的Leader term = 5，又开始向其他三个Follower复制日志。过了一会，网络分块恢复，之前的Leader 又加入了网络。

根据term 的值，旧Leader知道自己过期了，会自动退位，变成Follower，从而解决了脑裂问题，使得任何一个时刻，只有一个Leader是有效的。

**2、term 全局同步。** term 的每个节点都保存了一个term的值。因为网络延迟的问题，某些节点上term的值可能是过期的。因为选举的策略是要多数派（超过半数的节点）同意的，意味着在多数派里面一定有一个节点保存了最新的term值。如果一个节点被选为Leader，其term值一定是当前最大的，也就是最新的。

**commitIndex 与 lastApplied**

一条日志被提交，指的是这条日志被复制到了多数派的机器。一旦一条日志被认定处于提交状态，这条日志将不能被改变，不能被删除。任何一条日志，要么处于提交状态，要么处于未提交状态。

在这里，日志的提交设计应用了一个类似TCP协议中的技巧，可称为递增式的提交。假设commitIndex = 7，表示不仅index=7的日志处于提交状态，所有的index < 7的日志也都处于提交状态。

假设当前Follower的commitIndex=7，然后它收到Leader的index=9的日志，它会等到index=8的日志到来之后，一次性告诉Leader ，9之前的日志都提交了。

这样会带来两个好处：

*   不需要为每条日志都维护一个提交状态或未提交状态，而只需要维护一个全局变量commitIndex即可。
*   Follower不需要逐条的反馈给Leader，那一条日志提交了，那一条日志没提交。

这个机制和TCP协议里面的数据包的ACK机制有异曲同工之妙。


先看一个基本并发问题，假设有一个<K,V>存储集群，三个客户端并发地向集群发送三个请求。请问，最后在get(X)的时候，X应该等于几?

从 Paxos 到 Raft：一文讲透分布式一致性与复制状态机

从并发写 X 例子切入，说明日志顺序一致的重要性，引出复制状态机：相同初始状态+相同输入=相同最终状态。解释为何复制日志流比复制状态更简单。

Go开发工程师

架构设计

算法

Paxos算法通过复制状态机实现分布式一致性，核心是保证多节点日志顺序相同。Raft简化Paxos，采用单点写入和Leader选举机制，通过term值解决脑裂问题。日志复制采用commitIndex递增式提交，确保已提交日志不可变，提升系统可靠性和效率。

网络延迟

日志文件

数据同步

数据结构

数据库

服务器

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

从 Paxos 到 Raft：一文讲透分布式一致性与复制状态机-腾讯云开发者社区-腾讯云

从 Paxos 到 Raft：一文讲透分布式一致性与复制状态机

从 Paxos 到 Raft：一文讲透分布式一致性与复制状态机

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐