改造Paxos算法消灭活锁.pdf

改造PAXOS 算法消灭活锁 罗小成 （深圳市瑞信易科技有限责任公司，2016-07-06 ） 摘 要: 分布式一致性协议的目的是确定一个不可变变量分布式存 储的取值；通过对国内外一致性算法的研究成果和PAXOS 协议活锁 的分析，发现引入一个角色作为竞争时的代理提交者就可以解决活 锁问题,从而在本文引入“代理提交抢占式多数派一致性算法 （PPMC）”。 关键词: 分布式一致性协议; PAXOS ;抢占式访问权;竞争代理提交; PPMC ; PAXOS 快速收敛;活锁; ABSTRACT : DISTRIBUTED CONSENSUS PROTOCOL WAS DESIGNED TO DETERMINE THE VALUE OF A VARIABLE DISTRIBUTED STORAGE, THROUGH TO THE DOMESTIC AND FOREIGN CONSISTENT ANALYSIS ALGORITHM RESEARCH RESULTS AND PAXOS PROTOCOL LIVELOCK RESEARCH, DISCOVERED,THAT INTRODUCING A ROLE OF A PROXY FOR THE COMPETITION,WE CAN SOLVE THE LIVELOCK PROBLEM. TO INTRODUCE THE PROXY SUBMISSION PREEMPTIVE MAJORITY GROUP CONSISTENCY ALGORITHM (PPMC) . KEY WORDS : DISTRIBUTED CONSISTENCY PROTOCOL ; PAXOS; PREEMPTIVE CONTROL MODEL ； COMPETITIVE AGENT SUBMISSION ; PAXOS FAST CONVERGENCE ; LIVELOCK ; 1 前言 分布式系统中的节点通信存在两种模型：共享内存（Shared memory ）和消息传递 （Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误： 进程可能会慢、垮、重启，消息可能会延迟、丢失、重复。在一个分布式数据库系统中，如 果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致 的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法” 以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式 计算中的重要问题。因此从20 世纪80 年代起对于一致性算法的研究就没有停止过。 2 分布式一致性协议的目的 分布式一致性协议的目的是确定一个不可变变量分布式存储的取值。此取值可以是任何 二进制数据，这个取值一旦最终确定将不再改变，并且可以被获取到。此取值在分布式系统 1 / 15 中采用多个副本的方式存储。为了简化问题的分析，可先不考虑可能出现消息篡改即拜占庭 错误的情况；解决问题是在可能发生重启、延迟、消息丢失或重复、进程不可用等异常的分 布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏取值的一致性。 3 一致性算法的回顾 3.1 互斥锁算法 3.1.1 算法角色定义 一、提案委员：是指获取决议，产生提案，提交提案的成员。 二、审批委员：是指接受或拒绝提案，或批准提案，或回复决议的成员。 3.1.2 算法原则 审批委员应用原则： a、锁定后就不再给其它提案委员分配访问权原则，b、永久保存已经批准的提案原则。 提案委员会应用原则： a、提案委员向审批委员先申请互斥锁，再提交提案，然后再释放互斥锁原则；b、值采 用二阶段提交原则； 3.1.3 算法的内容 提案委员向审批委员申请一个互斥锁，锁定审批委员，审批委员只能接受由发放锁的提 案委员提交的提案。然后审批委员批准这个提案形成决议。形成决议后提案委员向审批委员 申请释放这个互斥锁。审批委员没有互斥锁后其它的提案委员才能对它进行申请互斥锁。这 样就确定了一个不可变变量的取值。 3.1.4 算法的不足 如果提案委员已经申请到一个互斥锁，但在释放这个互斥锁之前故障，则系统就处 于死锁状态。因此，此算法不允许已经申请到锁的提案委员故障。 3.2 抢占锁算法 3.2.1