用故事的方式说Paxos和Fast Paxos算法

落日映苍穹つ 2023-06-29 02:18 15阅读 0赞

## | Paxos ##

### 1. 故事背景 ###

有一个25人的团队（**Porposer**：P1，P2 … P25），现在需要选举一个团队负责人（TL）

有人说：可以采用投票制，但如果每个人都投自己，就会出现无解情况了…

那么我们来看看Paxos是如何选举的～

### 2. 选举方法 ###

邀请了5个评审人员（**Acceptor**：C1，C2，C3，C4，C5），**奇数个!!**

同时选择一个临时负责人专门汇报情况（**Leader**：P1），P1自己也有推荐权，所有人员先把情况告诉P1，由P1初步筛选之后统一汇报给评审团（防止出现竞争和活锁的情况）

**团队人员：**

*  第一步（**prepare**阶段）：首先发信息给临时负责人，临时负责人汇总告诉各个评审人员告诉自己的编号n，评审人员会回复四种情况
    
     *  1.评审员无编号则保留编号min = n ，**回复ok**；
     *  2.评审员min < n，则更新自己的min = n，**回复ok**；
     *  3.评审员保留的编号min >= n，则**忽略请求**；
     *  4.评审员记录了accept阶段的推荐人员，则**回复记录的min和推荐人员，同时更改min = n**
 *  第二步（**accept**阶段）：每个成员可以向评审人员推荐一个，并同时上送prepare阶段的编号n
    
     *  如果min <= n，则记录本次推荐的人员，**回复Accepted**
     *  如果min > n，则不记录，并返回记录编号，**回复Rejected(min)**

**举例说明，初始情况如下：**

**prepare1**：P1向C1和C2申请了编号n = 100  
C1返回 **ok**  
C2返回 **ok**

**prepare2**：P2向C2和C3申请了编号n = 101  
C2返回 **ok**  
C3返回 **ok**

=====================================================================  
prepare2还有一种情况（**后面都是以覆盖的情况推算**）：  
**prepare2**：P2向C2和C3申请了编号n = 99  
C2 **忽略请求**  
C3返回 **ok**

=====================================================================

**accept1**：P1向C1和C2推荐P8，编号是prepare1时的编号100 （100， P8）  
C1返回 **Accepted**  
C2返回 **Rejected(101)**

**accept2**：P2向C2和C3推荐P9，编号是prepare2时的编号101 （101， P9）  
C2返回 **Accepted**  
C3返回 **Accepted**

因为P1还没有确定结果（即半数以上评审团队确定）, 所以P1增大编号从头开始  
**prepare3**：P1向C1和C2申请了编号n = 102（**要比之前拒绝返回的101大**）  
C1返回 **(100, P8)**  
C2返回 **(101, p9)**

**accept3**：**因为准备阶段返回了2个编号，其中101>100，所以选择p9推荐**，P1向C1和C2推荐P9，编号是prepare3时的编号102 （102， P9）  
C1返回 **Accepted**  
C2返回 **Accepted**

**OK，只要评审团里面超过半数确定同一个人，选举即结束，P9成为新的团队LD!!**  
所以上面说了评审团队必须奇数个2N+1，这样只要有N个以上的人同意了，就选举成功。

--------------------

如果理清了上面的小故事，那么就初步对Paxos有了大概的了解了

需要了解几个概念：  
**Proposer** 团队人员  
**Leader** 临时负责人（中间协调汇报）  
**Acceptor** 评审团  
**Learner** 最终学习决策者（所有人：团队人员+评审团，包含临时负责人）

整个通信线路如下：

Proposer-----Leader-----Acceptor-----Learner

--------------------

## | Fast Paxos ##

Lamport老哥对Paxos进行不断改进之后，在2005年诞生了Fast Paxos

将通信线路拆成了如下两步：

Leader-----Acceptor （Any）
    Proposer-----Acceptor-----Learner

Leader先发送一个Any的消息给Acceptor，Acceptor便可以直接接收Proposer的请求，即团队人员不需要经过临时负责人，直接和评审团沟通了。

### 1. Round / Fast Round ###

一个Round包含prepare阶段和accept阶段，每个Round会有一个固定的编号n，这也就是上面申请和推荐都用了同一个编号的原因。

Fast Round的区别仅仅是Leader先发送一个Any的消息给Acceptor之后的Round，就是称为Fast Round（**Round和Fast Round的编号n规则不一样，可以区分**）

### 2. 冲突（Collision） ###

Round模式：是由临时负责人Leader汇总发给评审团，所以每个Round只会有一个推荐

Fast Round模式：是团队人员提交给评审团的，允许多个推荐在一个Fast Round中，这也就会出现如下情况：

P1推荐（100，P8）, P2推荐（101， P9）
    Fast Round变成（200，P8，P9）的情况（200是Fast Round的编号）

而评审团每次只能选择一个推荐，就造成了冲突情况。（如果选择多个，后面就别人）

那么，怎么解决冲突了？  
评审团里面搞出了一个临时评审团（Quorum），并对Fast Round里面的推荐进行投票，**必须选出且只能选择一个**！

--------------------

## | 总结 ##

个人觉得Paxos算法还是比较繁琐的，但是相比较投票选举来说，会有结果，但是还有很多细节问题需要考虑，比如：  
1.临时负责人Leader有事去了，不能传递消息了，如何处理？ – 重新选举Leader  
2.在高并发情况下，Fast Paxos冲突概率也会越大，解决冲突的成本也会越高  
3.Fast Paxos虽然缩短了通信流程，但是架构扩展性相对较差  
…

实际应用场景中，还是Paxos的简化形式用的比较多，Fast Paxos偏理论、较复杂，可行性较差。

--------------------

## | 代码示例 ##

写了一份示例代码，已上传到github [需要完整代码点我][Link 1]

### 选举方法 ###

package com.paxos.service;
    /** * yanghao * Copyright (C) 2020-2030 All Rights Reserved. */
    
    import com.paxos.bean.Porposer;
    import com.paxos.domain.result.AcceptResult;
    import com.paxos.bean.Acceptor;
    import java.util.List;
    import java.util.Map;
    
    /** * @author yanghao * @version Elect.java, v 0.1 2020-01-11 10:08 */
    public class Elect { 
    
        /** * 选举方法 * @param proposerNumber * @param acceptorMap * @return */
        public void electReferrer(Integer proposerNumber, Map<String, Acceptor> acceptorMap){ 
            if(acceptorMap == null || acceptorMap.size() == 0){ 
                return;
            }
    
            //团队人员
            Porposer porposer = new Porposer();
            //System.out.println(Thread.currentThread().getName() + " ==申请人== " + porposer.getReferrer() + " == " + proposerNumber);
    
            //超过半数同意，则进行accept阶段（没有申请通过的就需要一直发信息了！！）
            Integer agreeCount;
            Round round;
            String referrer;
    
            while (true){ 
                //创建Round
                round = new Round(proposerNumber);
    
                //1.prepare阶段（向评审团发送请求）
                agreeCount = round.prepare(acceptorMap);
    
                //没有超过半数同意
                if(agreeCount < (acceptorMap.size() + 1) / 2){ 
                    proposerNumber ++;
                    continue;
                }
    
                //2.accept阶段
                List<AcceptResult> resultList = round.accept(porposer, acceptorMap);
                for(AcceptResult acceptResult : resultList){ 
                    //取Rejected(n)里面n最大的一个去申请
                    if(!acceptResult.isSuccess() && acceptResult.getAccepNumber() > proposerNumber){ 
                        proposerNumber = acceptResult.getAccepNumber();
                    }
                }
    
                //判断循环是否结束
                referrer = round.isEndExecute(acceptorMap);
                if(referrer != null){ 
                    break;
                }
    
            }
    
            return;
    
        }
    
    }

### Round核心处理逻辑 ###

package com.paxos.service;
    /** * yanghao * Copyright (C) 2020-2030 All Rights Reserved. */
    
    import com.paxos.bean.Acceptor;
    import com.paxos.bean.Porposer;
    import com.paxos.domain.result.AcceptResult;
    import com.paxos.domain.result.PrepareResult;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /** * @author yanghao * @version Round.java, v 0.1 2020-01-11 10:01 */
    public class Round extends AbstractRound { 
    
        /** * 构造器 * * @param proposerNumber 唯一编号 */
        public Round(Integer proposerNumber) { 
            super(proposerNumber);
        }
    
        /** * 准备方法 * * @param acceptorMap * @return */
        @Override
        public Integer prepare(Map<String, Acceptor> acceptorMap) { 
    
            //返回集合
            List<PrepareResult> resultList = new ArrayList<>();
            PrepareResult prepareResult;
            Integer agreeCount = 0;
    
            for(Acceptor acceptor : acceptorMap.values()){ 
                if(acceptor.getAccepNumber() == null || acceptor.getAccepNumber() < this.getProposerNumber()){ 
                    //取请求者的编号
                    acceptor.setAccepNumber(this.getProposerNumber());
                    //返回对象
                    prepareResult = new PrepareResult(true, acceptor);
                    //统计返回成功个数
                    agreeCount ++;
    
                }else{ 
                    //返回对象
                    prepareResult = new PrepareResult(false, acceptor);
    
                }
    
                resultList.add(prepareResult);
            }
    
            //存储每个Round的prepare阶段返回值
            this.setResultList(resultList);
    
            return agreeCount;
        }
    
        /** * 推荐方法（提交方法） * * @param porposer * @param acceptorMap * @return */
        @Override
        public List<AcceptResult> accept(Porposer porposer, Map<String, Acceptor> acceptorMap) { 
            List<AcceptResult> resultList = new ArrayList<>();
            AcceptResult acceptResult;
    
            //从上次返回结果里面取出编号最大的结果（没有就默认是创建对象时生成的）
            Integer max = 0;
            for(PrepareResult result : this.getResultList()){ 
                if(result.getAcceptor().getReferrer() != null && result.getAcceptor().getAccepNumber() > max){ 
                    max = result.getAcceptor().getAccepNumber();
                    //取上次prepare阶段返回的推荐
                    porposer.setReferrer(result.getAcceptor().getReferrer());
                }
            }
    
            Acceptor acceptor;
            for(PrepareResult result : this.getResultList()){ 
                //查出最新的评审团信息
                acceptor = acceptorMap.get(result.getAcceptor().getAccepName());
    
                //如果评审团的编号已经大于本次提交，则返回失败和评审团编号
                if(acceptor.getAccepNumber() > this.getProposerNumber()){ 
                    acceptResult = new AcceptResult(false, acceptor.getAccepNumber());
                }else{ 
                    acceptor.setAccepNumber(this.getProposerNumber());
                    acceptor.setReferrer(porposer.getReferrer());
    
                    acceptResult = new AcceptResult(true);
                }
    
                resultList.add(acceptResult);
    
            }
    
            return resultList;
        }
    
        /** * 判断是否停止选举 * * @param acceptorMap * @return */
        @Override
        public String isEndExecute(Map<String, Acceptor> acceptorMap) { 
            Map<String, Integer> electMap = new HashMap<>();
            Integer referrerCount = 0;
    
            for(Acceptor acceptor : acceptorMap.values()){ 
                if(electMap.get(acceptor.getReferrer()) == null){ 
                    referrerCount = 1;
    
                }else { 
                    referrerCount = electMap.get(acceptor.getReferrer());
                    referrerCount ++;
    
                    //评审团超过一半同意即可选举结束
                    if(referrerCount >= (acceptorMap.size() + 1) / 2){ 
                        return acceptor.getReferrer();
                    }
    
                }
    
                electMap.put(acceptor.getReferrer(), referrerCount);
    
            }
    
            return null;
        }
    
    }

[Link 1]: https://github.com/yh381352864/paxos