分布式系列文章——Paxos算法原理与推导.docx

《分布式系列文章——Paxos算法原理与推导.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分布式系列文章——Paxos算法原理与推导本文章来自于阿里云云栖社区摘要： 网上有很多讲解Paxos算法的文章，但是质量参差不齐。看了很多关于Paxos的资料后发现，学习Paxos最好的资料是论文《PaxosMadeSimple》，其次是中、英文版维基百科对Paxos的介绍。本文试图带大家一步步揭开Paxos神秘的面纱。Paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点：1.难以理解2.工程实现更难。网上有很多讲解Paxos算法的文章，但是质量参差不齐。看了很多关于P

2、axos的资料后发现，学习Paxos最好的资料是论文《PaxosMadeSimple》，其次是中、英文版维基百科对Paxos的介绍。本文试图带大家一步步揭开Paxos神秘的面纱。Paxos是什么Paxos算法是基于**消息传递**且具有**高度容错特性**的**一致性算法**，是目前公认的解决**分布式一致性**问题**最有效**的算法之一。GoogleChubby的作者MikeBurrows说过这个世界上**只有一种**一致性算法，那就是Paxos，其它的算法都是**残次品**。虽然MikeBurr

3、ows说得有点夸张，但是至少说明了Paxos算法的地位。然而，Paxos算法也因为晦涩难懂而臭名昭著。本文的目的就是带领大家深入浅出理解Paxos算法，不仅理解它的执行流程，还要理解算法的推导过程，作者是怎么一步步想到最终的方案的。只有理解了推导过程，才能深刻掌握该算法的精髓。而且理解推导过程对于我们的思维也是非常有帮助的，可能会给我们带来一些解决问题的思路，对我们有所启发。问题产生的背景在常见的分布式系统中，总会发生诸如**机器宕机**或**网络异常**（包括消息的延迟、丢失、重复、乱序，还有网络分

4、区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对**某个数据的值**达成**一致**，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。注：这里**某个数据的值**并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令（command）。。。根据应用场景不同，**某个数据的值**有不同的含义。相关概念在Paxos算法中，有三种角色：·Proposer·Acceptor·Learners在具体的实现中，一个进程可能**同时充当多种

5、角色**。比如一个进程可能**既是Proposer又是Acceptor又是Learner**。还有一个很重要的概念叫**提案（Proposal）**。最终要达成一致的value就在提案里。注：·暂且认为『**提案=value**』，即提案只包含value。在我们接下来的推导过程中会发现如果提案只包含value，会有问题，于是我们再对提案**重新设计**。·暂且认为『**Proposer可以直接提出提案**』。在我们接下来的推导过程中会发现如果Proposer直接提出提案会有问题，需要增加一个学习提案的

6、过程。Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了。回到刚刚说的『对某个数据的值达成一致』，指的是Proposer、Acceptor、Learner都认为同一个value被选定（chosen）。那么，Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢？·Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需

7、要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。·Acceptor：只要Acceptor接受了某个提案，Acceptor就认为该提案里的value被选定了。·Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。问题描述假设有一组可以**提出（propose）value**（value在提案Proposal里）的**进程集合**。一个一致性算法需要

8、保证提出的这么多value中，**只有一个**value被选定（chosen）。如果没有value被提出，就不应该有value被选定。如果一个value被选定，那么所有进程都应该能**学习（learn）**到这个被选定的value。对于一致性算法，**安全性（safaty）**要求如下：·只有被提出的value才能被选定。·只有一个value被选定，并且·如果某个进程认为某个value被选定了，那么这个value必须是真的被选定的那个。我们不去精确地定义