分类： Mysql/postgreSQL
2013-07-14 23:03:32
原文地址：两阶段提交协议与paxos投票算法 作者：invincibleliu
为了实现分布式事务，必须实现一套协商算法，使得多个参与者对某一个状态的变更保持一致，对应到CAP三角形，我们必须选CP这条边
两阶段提交算法大致是这样的：
定义coordinator为某一状态变更的的发起者（唯一），有多个participant（可以理解为多个从库在做id自增过程），且为了一致性participant只接受coordinator发起的自增，要增全部增，否则回滚
第一阶段：coordinator发起投票，某一个participant都投了赞成票，他得先做做两件事情：
持久化该同意（并不是最终提交哦，举例说mysql就是写redo log和undo log）
向coordinator回应同意该提案
第二阶段：如果每一个participant都投了赞成票，则coordinator
向每一个participant发起最终的commit
每一个participant接到commit后提交事务，释放锁，删掉redo undo log，并向coordinator发送acknowledgment
当coordinator收到所有的acknowledgment后提交该事务
失败情况：如果存在participant投了反对票，则coordinator通知所有投了赞成票的participant回滚，目的是使得这一次投票造成的影响消失，回到最初的状态，这就用到了undo log，这一步也是需要发acknowledgment的，作为coordinator关闭该事务的依据
点评：2PC绝对是CP的死党，是分布式情况下强一致性算法，因此缺点也是很明显的，
单点coordinator是个严重问题：
没有热备机制，coordinator节点crash了或者连接它的网路坏了会阻塞该事务；
吞吐量不行，没有充分发动数量更多的participants的力量，一旦某个participant第一阶段投了赞成票就得在他上面加独占锁，其他事务不得介入，直到当前事务提交or回滚
Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法
它将角色分为proposers，accept和learners：proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以接受（accept）提案，若提案获得多数 acceptors 的接受，则称该提案被批准（chosen）；learners 只能「学习」被批准的提案，角色可以客串
算法的核心过程分为两阶段：
prepare阶段：
a:proposer 选择一个提案编号 n 并将 prepare 请求发送给 足够多的acceptors
b:acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上次接受的提案[2b]回复给 proposer，并承诺不再回复小于 n 的提案
accept阶段：
a:当一个 proposor 收到了 acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 acceptors 发送 accept 请求，包括编号 n 和一个suitable value（下文会讲这个value的来头）
b:在不违背自己向其他 proposer 的承诺[1b]的前提下，acceptor 收到 accept 请求后丢弃曾经accept过的value[2b]接着接受这个请求并持久化
本来还有第三阶段：proposer最终提交事务，它跟2PC的第二阶段基本一样：proposer收到过半的accept后向所有acceptor发布最终的决议（有的实现版本是由learner负责统计accept票数并发布决议，这里为了跟2PC作比较不特别区分）
proposer选择一个会自增的编号n，这个编号可以由一个统一的机构颁发，但是一定得保证从这里取得的编号是自增且唯一的（即多个proposer取到的编号存在时序关系）；
名词解释
一个锁：当acceptor收到prepare消息后，当且仅当这是它见过的最大的编号n时，持久化该n，并将最近一次接受提案的value返回给propose，并加锁：在1b阶段只回复大于n的prepare消息，2b阶段不接受小于n的accept请求，对于大于n的的accept请求会被接受并导致该acceptor之前所接受过的value被清空
suitable value：proposer收到足够多的prepare回复后，会决定出一个suitable value作为提案：在1b中如果收集到的每一种回复都不能形成多数派，也就是说acceptor的情况有点类似乌合之众，那么proposer就可以按照它的意愿来进行投票，即可以任意设置suitable value；如果收集到的某种value过半了，则将这个value作为suitable value发起accept请求
paxos虽然也是分布式情况下强一致性算法，但他在2PC上至少有两点改进
不存在说网路问题导致事务阻塞甚至失败，尤其是连接coordinator的，因为paxos的角色是可以互串的，必要时participant也能充当coordinator
加在任何一个在1b2b阶段投了赞成票的participant上的锁是可以被砸开的：只要新提案的编号更大，这样就提高吞吐量了，当然频繁的产生新proposer可能会导致活锁：永远无法达成协议，最好设置一个超时机制，过了一定的时间才产生一个proposer
