Paxos 和 Raft 算法
1. 概述
在分布式系统中,一个核心的问题就是解决数据一致性的问题,即共识问题(多副本共识问题):
Consensus Problem : Requires agreement among a number of processes (or agents) for a single data value.
共识问题简单来说,就是多个进程(代理)就某个单值达成一致,主要的应用场景数据多副本的复制。而
Paxos 及 Raft
算法的提出便是为了解决共识问题,它们在工程实现上得到了广泛的应用,如
Goggle 的 Chubby、Apache 的 ZooKeeper 及 Raft算法实现
Etcd。这些算法都可以统称为一致性算法。
一致性算法大概可以分为4个类型:
- Basic-Paxos : 提供就一个提案达成一致的算法,是最基本的算法,在工程实践中很少使用该算法;
- Multi-Paxos : 在 Basic-Paxos 算法的基础上,提供了就一批提案达成一致的算法,在工程中有很多类似的实现;
- Raft : 针对 Multi-Paxos 算法难于理解及实现复杂,提供了一种简化的实现;
- Multi-Raft : 为了提供更大的并发请求量,可以将单个 Raft 集群进行分区,提供更大的集群规模。
这篇文章就四种类型的算法进行一个概要的分析,更多的是逻辑概念层面,不会对细节及实现过多讨论,那也超出本人的认知。