Guanzhou (Jose) Hu

Guanzhou's personal storage for lecture notes, blog posts, & good mood.

Find me on GitHub
https://github.com/josehu07

Resume  |  LinkedIn  |  Google Scholar

Email guanzhou (dot) hu (at) wisc (dot) edu
josehu (at) cs (dot) wisc (dot) edu

To all my loved ones, my friends, and Annie ♥
Hosted on GitHub Pages — Theme by orderedlist

Notes on Consensus Algorithms - Paxos, Multi-Paxos, and Raft

04 Apr 2020 - Guanzhou Hu

分布式系统中,基础的共识算法(Consensus Algorithms)希望解决的是在节点可能 crash / restart、节点间网络消息可能乱序、丢失、重复的情况下,让所有节点对 clients 一串提案达成 strong consistency (linearizability),从而实现 Replicated State Machines,做到有效的 fault-tolerence。

共识算法针对的问题

分布式系统中,基础的 共识算法(Consensus Algorithm) 希望解决的是如下问题:节点可能 crash / restart、节点间网络消息可能乱序、丢失、重复的情况下,让所有节点对 clients 一串提案达成强一致1(see newer post for explanation of strong consistency)。

为什么对 Paxos、Raft 等的研究很重要

传统 2PC(两阶段提交)、3PC(三阶段提交) 在用于 transactions 之外也可以用于共识一个提案的问题,但缺点是一个节点宕机则系统不可用(或在出现 network partition 后存在 脑裂 无法解决);这些共识算法的目标就是在有多个副本同时参与、超半数仍正常工作的情况下(少数副本可以挂掉,从而可用性更高了)仍能保证 100% 一致性

Paxos、Multi-Paxos、Raft

其他共识算法

其他在部署中成功的共识算法有 Zab(即 Zookeeper 所基于的 replication)、ViewStamps 等等。

References

Please comment below anything you wanna say! 😉