文章482
标签257
分类63

共识算法的前生今世总结

共识算法的概述;

视频:


共识算法的前生今世总结

为什么我们需要共识算法?

consensus-1

如上图所示,一台服务器给客户端提供服务,但是这种服务是很不稳定的;

因为如果这台服务器挂掉了,服务马上就不再可用!

因此,通常情况下会使用增加服务器副本的方式来保证系统的高可用;

image-20221105104523837

上面增加的两个副本和原来的服务器一起构成了一个分布式系统;

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

  • 如何确保增加的副本可以发挥作用?(主服务器宕机,如何判断那台服务器成为主?);
  • 如何将切换后的结果通知给客户端?
  • 备用服务器如何判断主服务器宕机(网络分区时避免脑裂);
  • 备用服务器都想要成为主节点、都不想成为主节点?

一个解决思路是:

image-20221105104922308

由客户端或者另一类节点维持所有服务器节点的信息,当发现主节点不可用时,他们就选择另一台服务器作为主(例如,Redis 中的 sentinel);

这类节点也被称为“管理节点”;

但是此方法存在另一个问题:如何保证管理节点的高可用性?

由于管理高可用节点的管理节点本身也存在高可用的问题,因此此方法存在无限循环的问题;

一个解决方法是引入外界因素,例如管理节点如果宕机,则人为介入为维护等:

image-20221105105456779

但是这种方法需要人工介入!

有没有一个不依赖外界因素来自动完成主节点选举,错误切换的方法呢?

答案就是:共识算法!


共识算法的作用

共识算法中一个最重要的思路就是投票选举;

image-20221105110018007

简单来讲就是:

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

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

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


Paxos历史

Lamport 投稿 Paxos 被拒的故事…

论文 1990 年提交给了TOCS,直到 1996 年 由图灵奖获得者 Butler Lampson 发现,并在:

《How to build a Highly Available System Using Consensus》对算法进行了描述;

才让 Paxos 获得了广泛关注;

1998 年,TOCS 发表了:

《The part time parliament》


Paxos算法发展

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

最重要的是 Google 的两篇 2006 年的论文:

  • 《Bigtable:A distributed storage system for structured data》;
  • 《The chubby lock service for loosely-coupled distributed systems》;

Chubby:

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

目前为止所有异步共识算法的核心都是 Paxos;

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

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

下面是一些演变:

  • Basic Paxos:
    • Multi Paxos
    • ZAB
    • Raft

其中,他们一个一致的改造点是:设计了一个有较长生命周期的 Leader!

对于 Basic Paxos 而言,每次决议一个新的问题,都要投票选举出一个对此问题的负责人,由此负责人处理此问题,因此每次出现新问题都要重新进行一次投票选举;

而有长生命周期的 Leader 的方案是由集群选出一个 Leader,此 Leader 在他的任期内直接负责处理所有问题,只有 Leader 宕机或任期结束,才会重新进行一次投票选举;

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


附录

共识算法的概述;

视频:



本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/2022/10/30/共识算法的前生今世总结/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可