江苏龙网

  1. 主页 > 生活百科 > >

Paxos算法被认为是类似算法中最有效的

Paxos算法

概述Paxos算法是莱斯利·兰伯特（Leslie Lamport ， 就是 LaTeX 中的"La" ， 此人在微软研究院）1990年提出的一种基于消息传递的一致性算法 。[1] 这个算法被认为是类似算法中最有效的 。
背景Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致 。一个典型的场景是 ， 在一个分布式数据库系统中 ， 如果各节点的初始状态一致 ， 每个节点执行相同的操作序列 ， 那么他们最后能得到一个一致的状态 。为保证每个节点执行相同的命令序列 ， 需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致 。一个通用的一致性算法可以应用在许多场景中 ， 是分布式计算中的重要问题 。因此从20世纪80年代起对于一致性算法的研究就没有停止过 。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing） 。Paxos 算法就是一种基于消息传递模型的一致性算法 。
不仅仅是分布式系统中 ， 凡是多个过程需要达成某种一致的场合都可以使用Paxos 算法 。一致性算法可以通过共享内存（需要锁）或者消息传递实现 ， Paxos 算法采用的是后者 。Paxos 算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端并发读写数据；分布式存储中多个副本响应读写请求的一致性 。
Lamport 最初关于Paxos 算法的论文The Part-Time Parliament 理解起来比较有挑战性 ， 个人认为部分原因是Lamport 通过故事的方式来表述、解释这个问题 ， 所以读者在阅读论文的时候需要透过故事来理解作者究竟想要说明什么 。章节安排如下：第二节对应原文的1.1-2.1 。第三节对应原文2.2-3.2 。
数学问题问题描述
既然Lamport 是通过故事的方式提出Paxos 问题 [1]  ， 我们就有必要简述下这个问题：希腊岛屿Paxon 上的执法者（legislators ， 后面称为牧师priest）在议会大厅（chamber）中表决通过法律 ， 并通过服务员传递纸条的方式交流信息 ， 每个执法者会将通过的法律记录在自己的账目（ledger）上 。问题在于执法者和服务员都不可靠 ， 他们随时会因为各种事情离开议会大厅 ， 并随时可能有新的执法者进入议会大厅进行法律表决 ， 使用何种方式能够使得这个表决过程正常进行 ， 且通过的法律不发生矛盾 。
说明：不难看出故事中的议会大厅就是我们的分布式系统 ， 牧师对应节点或进程 ， 服务员传递纸条的过程就是消息传递的过程 ， 法律即是我们需要保证一致性的值（value） 。牧师和服务员的进出对应着节点/网络的失效和加入 ， 牧师的账目对应节点中的持久化存储设备 。上面表决过程的正常进行可以表述为进展需求（progress requirements）：当大部分牧师在议会大厅呆了足够长时间 ， 且期间没有牧师进入或者退出 ， 那么提出的法案应该被通过并被记录在每个牧师的账目上 。
数学基础
Paxon 中的法律通过投票（ballots ， 也有翻译成选举）完成 ， 每次投票涉及到的一群牧师称为法定人数（quorum） ， 当且仅当法定人数中的所有牧师都赞成这个法案时 ， 投票成功并通过该法律 。每次投票B 包含以下内容：
B_dec 正在进行的投票
B_qrm 法定人数牧师的集合（非空牧师集合）
B_vot 赞成的牧师集合
B_bal 投票编号
有了以上定义 ， 我们看出投票B 通过的充要条件是：B_qrm 属于 B_vot 。接着我们定义B 为一次投票的集合 ， 并说明投票如果满足下面三个条件 ， 那么一致性可以得到保证 。实际中每一次投票都可以看做是一次读写请求 ， 所有法定人数的牧师赞成才通过法律表示：所有涉及到这次请求的节点都同时响应请求（比如更新某个值）才能保证一致性 。这里选举编号（B_bal）的大小代表选举发起的先后顺序 。下面给出三个重要的定义：
B1(B) B 中每个选举都有一个独一无二的选举编号 。
B2(B) B 中每两个选举至少有一个共同的牧师 。
B3(B) B中每一次选举B  ， 如果其法定人数中的牧师在之前的选举中投了赞成票（这些选举构成一个集合） ， 那么本次选举B 所对应的法律需要和上述选举集合中最近一次选举所对应的法律相一致 。


推荐阅读


上一篇：铁观音拉酸的特点是什么

下一篇：安溪铁观音春茶的品质特征