MultiPaxos协议

赵星宇

本文是学习《Paxos理论介绍(2): Multi-Paxos与Leader》的学习总结 http://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483798&idx=1&sn=42dd222ae255b13f1f67cd9e6d3f3dc0&scene=0#wechat_redirect 

MultiPaxos的目标是确定多个值和多个值之间的顺序在多个节点保持一致。其中的一个值被称为一个实例。如果这些实例分别使用BasicPaxos协议的话每一个实例都要进行prepare和accept两步。

MultiPaxos做的改进就是将所有的prepare请求变成一个，prepare请求的内容是bal和未决实例区间，同时promise bal变成一个，prepare的返回结果是所有未决实例区间内实例的bal和值，每次prepare就相当于对所有未决实例进行prepare。这样未决实例的accept就可以并行发了。当遇到accept成功则说明这条日志已决，当遇到accept失败则需要重新prepare。因此当多个节点同时prepare时其性能会严重退化。因此可以引入Leader防止其他节点prepare。做法是：收到来自其他节点的accept请求，则在一段时间内不发送prepare请求即可。Leader并不严格限制只有一个，出现多个也不会影响算法正确性，只不过会退化性能。