常见的分布式算法有哪些
1. 常见的分布式算法有哪些
分布式算法通常包括：
- 共识与复制
- 分布式事务提交
- 数据分片与路由
- 节点间状态传播
- 全局唯一 ID 生成
- 拜占庭容错与理论边界
2. 可以先给一个总览分类
常见分布式算法或协议，大致可以分成下面几类：
2.1 共识算法
用于让多个节点对“同一个值”或“同一串操作顺序”达成一致。
常见有：
PaxosMulti-PaxosRaftZABPBFT以及其他 BFT 类协议
2.2 分布式事务提交协议
用于让多个参与者上的事务要么都成功，要么都失败。
常见有：
2PC（Two-Phase Commit）3PC（Three-Phase Commit）
2.3 分布式路由与分片算法
用于把数据或请求稳定地分配到不同节点，并尽量降低扩缩容带来的迁移成本。
常见有：
一致性哈希Hash Slot- 取模分片（严格说更像分片策略，不算高级协议，但工程里非常常见）
2.4 节点发现与状态传播算法
用于在大规模节点之间传播成员信息、健康状态、配置等。
常见有：
Gossip
2.5 全局唯一 ID 生成算法
用于在分布式系统中高并发地产生唯一 ID。
常见有：
Snowflake（雪花算法）
2.6 容错和理论边界相关
它们不一定直接是“业务算法”，但会深刻影响分布式系统设计。
常见有：
FLP 不可能性CAP- 拜占庭容错模型
3. 最常见的一类：共识算法
3.1 Paxos
Paxos 是经典共识算法，解决的问题是：
- 在节点可能宕机、消息可能乱序或重复的环境下，如何让多个节点对同一个值达成一致
它的核心思想是：
- 提案编号 + 多数派投票
关键点：
- 只要一个值被多数派接受，后续就不能再选出另一个冲突值。
- 任意两个多数派集合必有交集，因此不会出现两个不同值都被合法决定。
优点：
- 理论地位高，安全性强，是很多共识系统的基础思想。
缺点：
- 原始 Paxos 理解难、实现难、工程可读性差。
3.2 Multi-Paxos
原始 Paxos 更像是：
- 对“单个值”做一次共识
但真实系统往往需要：
- 连续不断地对一串日志做共识
所以工程里更常见的是：
Multi-Paxos
它通常通过引入稳定 leader，减少重复 prepare 开销，提高吞吐。
3.3 Raft
Raft 也是共识算法，目标和 Paxos 类似，但更强调：
- 可理解、可工程化
它把问题拆成三个核心部分：
- leader 选举
- 日志复制
- 安全性保证
核心特点：
- 集群同一时刻只有一个 leader 对外处理写请求。
- 写请求变成日志条目，复制到 followers。
- 日志得到多数派确认后才提交。
优点：
- 易讲、易实现、工程落地广泛。
典型场景：
etcdconsul的部分核心机制- 各类强一致元数据存储
3.4 ZAB
ZAB 是 ZooKeeper 使用的一致性协议。
它本质上也是：
- leader + 多数派 + 有序广播
核心点：
- leader 为每个事务分配
zxid - 事务先 proposal，再多数派确认，再 commit
- leader 宕机后，要先恢复出一个事务历史正确的新 leader
它和 Raft 很像，但不是同一个协议。
典型场景：
ZooKeeper
3.5 PBFT 和 BFT 类协议
前面的 Paxos、Raft、ZAB 一般默认处理的是：
- 崩溃故障（Crash Fault）
也就是节点可能挂，但不会主动作恶。
如果系统要应对：
- 节点返回错误数据
- 节点伪造消息
- 恶意篡改协议流程
那就进入：
- 拜占庭容错（BFT）
常见协议有：
PBFT（Practical Byzantine Fault Tolerance）
这类协议通常代价更高、消息量更大，但能容忍一部分恶意节点。
典型场景：
- 区块链
- 高安全要求的联盟链或多方协作系统
4. 第二类：分布式事务提交协议
4.1 2PC
2PC 解决的是：
- 多个资源管理器参与时，如何让一次事务要么全部提交，要么全部回滚
两个阶段：
preparecommit / rollback
优点：
- 概念直接，事务原子性表达清晰。
缺点：
- 协调者单点问题明显。
- 参与者在 prepared 后可能长时间阻塞。
- 在网络分区和故障下可用性较差。
4.2 3PC
3PC 在 2PC 基础上增加中间阶段与超时控制，试图降低阻塞。
常见理解是：
- 比
2PC更强调超时与状态过渡
但它要求更强的网络假设，在真实异步网络里并没有从根本上消灭问题，所以工程上远没有 2PC 常见。
5. 第三类：分布式路由与分片算法
5.1 一致性哈希
一致性哈希 主要解决：
- 节点增减时，如何尽量减少数据迁移
核心思想：
- 把节点和 key 一起映射到哈希环上
- key 顺时针找到第一个节点作为归属
优点：
- 扩容、缩容时迁移量小
常见场景：
- 分布式缓存路由
- 客户端分片
- 某些分布式存储路由
5.2 Hash Slot
Hash Slot 可以理解为：
- 一种比一致性哈希更工程化的固定桶分片方式
例如先把 key 映射到固定数量的 slot，再把 slot 分给节点。
优点：
- 迁移粒度可控
- 运维和重平衡更直观
典型场景：
Redis Cluster
5.3 取模分片
最简单的方式是：
hash(key) % N
优点：
- 简单，计算快。
缺点：
- 节点数变化时，几乎全量 key 都要重映射。
所以它通常适合：
- 节点数长期稳定的场景
6. 第四类：节点状态传播与服务发现算法
6.1 Gossip
Gossip 的核心思想类似“流言传播”：
- 每个节点周期性随机挑选少数其他节点交换状态
这样信息会逐步在集群里扩散。
优点：
- 去中心化
- 可扩展性好
- 适合大规模节点集群
缺点：
- 传播不是瞬时完成的
- 通常更偏最终一致，而不是强一致
典型场景：
- 成员管理
- 服务发现
- 健康状态传播
- 配置信息扩散
7. 第五类：分布式唯一 ID 算法
7.1 Snowflake
Snowflake 雪花算法用于：
- 在多节点高并发环境下生成全局唯一且趋势递增的 ID
经典结构一般包含：
- 时间戳
- 机器 ID
- 序列号
优点：
- 本地生成，无需每次都访问中心服务
- 性能高
- 基本有序
缺点：
- 对时钟回拨敏感
- 依赖机器 ID 分配正确
典型场景：
- 分布式订单号
- 消息 ID
- 业务主键
8. 第六类：分布式系统设计里绕不开的理论
8.1 CAP
CAP 不是具体实现算法，但它是分布式系统设计最基础的约束之一。
它说明系统面对网络分区时，不可能同时完美满足：
ConsistencyAvailabilityPartition Tolerance
工程上常见理解是：
- 分区发生时，你必须在一致性和可用性之间做取舍
8.2 FLP 不可能性
FLP 说明：
- 在纯异步网络里，只要允许哪怕一个节点崩溃，就不存在一个确定性算法，能保证共识总是在有限时间内完成
它告诉我们的不是“共识做不到”，而是：
- 你必须引入额外假设，比如超时、随机化、失败检测器，才能在工程里把共识做成“通常可用”
8.3 拜占庭容错
拜占庭容错关注的是：
- 节点不仅可能挂，还可能作恶、撒谎、伪造消息
这和普通崩溃容错不是一个难度级别。
如果面试官问“Raft 能不能处理拜占庭”，标准答案通常是：
- 不能，Raft 默认只处理崩溃故障，不处理恶意节点。
9. 这些算法分别解决什么问题
可以用一张简表来记：
| 类型 | 常见算法/协议 | 解决的问题 |
|---|---|---|
| 共识 | Paxos、Multi-Paxos、Raft、ZAB | 多个节点如何对同一个值或同一串日志顺序达成一致 |
| 分布式事务 | 2PC、3PC | 多个资源如何原子提交 |
| 路由/分片 | 一致性哈希、Hash Slot、取模分片 | key 或请求如何分配到节点 |
| 状态传播 | Gossip | 节点间如何扩散成员/健康状态 |
| ID 生成 | Snowflake | 如何生成全局唯一 ID |
| 容错理论 | CAP、FLP、BFT | 分布式设计的能力边界和取舍 |
10. 面试里应该怎么答
如果面试官问“常见的分布式算法有哪些”，可以这样回答：
- 常见的分布式算法可以按用途分类来看。第一类是共识算法，比如 Paxos、Raft、ZAB，用来解决多个节点如何对同一个值或日志顺序达成一致；第二类是分布式事务协议，比如 2PC、3PC，用来保证多个资源的原子提交；第三类是分片和路由算法，比如一致性哈希、Hash Slot，用来解决节点扩缩容时的数据路由和迁移；第四类是状态传播算法，比如 Gossip，用来做成员信息和健康状态扩散；第五类是分布式 ID 算法，比如 Snowflake，用来生成全局唯一 ID。除此之外，CAP、FLP 和拜占庭容错虽然不一定直接是具体业务算法，但它们决定了分布式系统设计的边界和取舍。
11. 最后给一个判断标准
看到一个“分布式算法”时，先问它到底解决哪类问题：
- 是解决一致性
- 还是解决事务提交
- 还是解决分片路由
- 还是解决状态传播
- 还是解决唯一 ID 生成
这样你就不会把：
Raft2PC一致性哈希Snowflake
这些本质完全不同的东西混成一类。