共识算法的前世今生

Angelia-Wang / 2023-08-12 / 原文

为什么需要共识算法

一台服务器给客户端提供服务时，这种服务是很不稳定的，因为如果这台服务器宕机，服务马上就不再可用。因此，通常情况下会使用增加服务器副本的方式来保证系统的高可用。图中增加两个副本，和原来的服务器一起构成了一个分布式系统。

此时存在下面的一系列问题：

如何确保增加的副本可以发挥作用，即如何进行主备切换？(主服务器宕机，如何判断那台服务器成为主)
如何将切换后的结果通知给客户端？
备服务器如何判断主服务器宕机？(网络分区时避免脑裂)
备服务器都想要成为主服务器/都不想成为主服务器，咋办？

一个直接的解决思路：由客户端 or 另一类节点维持所有服务器节点的信息，当发现主节点不可用时，他们就选择另一台服务器作为主(如 Redis 中的 sentinel)。这种维持所有服务器信息并负责选主的节点，被称为 管理节点。

此方法存在另一个问题：如何保证管理节点的高可用性 (管理节点宕机了咋办)？若再为管理节点设置备机，管理节点怎么进行主备切换？若再为管理节点设置管理节点则会陷入无限循环。即，负责保证高可用的节点本身也需要高可用，导致高可用问题会嵌套下去。

一个解决方法是引入外界因素来终止此循环，🌰 若管理节点宕机，则人为介入维护 (DBA)，人工判定是否需要主备切换及切换到哪台备机。

有没有一个方法能让节点在不依赖外界因素的情况下，自动完成主节点的选举呢？ —— 共识算法。

共识算法

共识算法的一个重要思路是 投票选举。简单来讲就是：

负责处理客户端请求的主服务器，由集群中所有其他服务器投票选举出来；

只有得票超过半数的服务器才能够成为主服务器，从而负责处理客户端请求；

因此，只要集群中存在超过半数的服务器没有宕机，整个集群就能正常对外提供服务。

若图中集群有三台服务器，宕了一台，剩下两台服务器依旧能通过投票选出主来提供服务。即该系统能容忍一台服务器的宕机，具备初步的高可用性。

目前公认的最早提出的共识算法为 Paxos。

Paxos 算法的发展

1990年 Lamport 将 Paxos 论文投稿给 TOCS 但被拒，直到 1996 年由图灵奖获得者 Butler Lampson 发现，并在《How to build a Highly Available System Using Consensus》中对算法进行了描述，才让 Paxos 获得了广泛关注。于 1998 年在 TOCS 发表《The part time parliament》。

由于 Paxos 算法难以理解并且难以落地，因此学术界和工业界在此基础之上进行了很多探索。

最重要的是 Google 的两篇 2006 年发表于 OSDI 的论文：

《Bigtable：A distributed storage system for structured data》

《The chubby lock service for loosely-coupled distributed systems》

Indeed, all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

实际上，我们迄今为止所有为解决异步共识问题而设计的可用协议，核心都是 Paxos。—— chubby 论文

chubby 发表后，在开源社区推出了与之对应的 ZooKeeper (其 ZAB 共识算法是 Paxos 的一个变种)。

2014 年发表的 Raft 共识算法也是 Paxos 的一个更易理解的变种。

Multi Paxos 是 Paxos 用于工业生产的改造版。

三者相比于 Basic Paxos 的一个一致的改造点是：设计了一个有较长生命周期的 Leader。

Basic Paxos 中，每次决议一个新的问题，都要投票选举出一个对此问题的负责人，由此负责人处理此问题，因此每次出现新问题都要重新进行一次投票选举；
有长生命周期的 Leader 的方案：由集群选出一个 Leader，此 Leader 在他的任期内直接负责处理所有问题，只有 Leader 宕机或任期结束，才会重新进行一次投票选举；

显然，长生命周期的 Leader 的方案选举次数更少，也就是用于维持共识算法的代价更小，因此更适用于工业生产。