概述
https://www.cnblogs.com/frankyou/p/7238099.html
CAP
- Consistency
- Availability
- Partition-Tolerance
- 网络分区：网络延迟或中断导致的限时内通讯失败
- 由于必需满足，所以取舍在于C和A
BASE
- Basically Available
- Soft State
- 可异步
- Eventual Consistency
2PC
http://blog.csdn.net/feilengcui008/article/details/50557511?spm=a2c4e.11153940.blogcont5854.3.1e843545OLEAJn
https://yq.aliyun.com/articles/5854
- Vote + Commit
- 强一致，非高可用
- Commit阶段Coordinator和Participant同时挂掉；当其余Participant均返回accept时，无法决定下一步，会被阻塞
- 缺点
- 同步阻塞
- 单点故障
3PC
https://segmentfault.com/a/1190000004474543
- can_commit + pre_commit + do_commit
- 高可用，可能不一致
- Pre-Commit阶段发生网络分区，导致abort信号无法送达，Participant超时后commit，导致不一致
Paxos
https://www.cnblogs.com/linbingdong/p/6253479.html
- Google Chubby的作者Mike Burrows说：这个世界上只有一种一致性算法，那就是Paxos，其它算法都是残次品
What does Paxos do?
paxos-001.jpg
- 宕机或网络故障下，在集群内部对某个值达成一致
作者
- 莱斯利·兰伯特（Leslie Lamport，即LaTeX 中的"La"，现在在微软研究院）
- 作为2013年新科图灵奖得主，现在七十多岁，是计算机科学领域一位拥有杰出成就的传奇人物
- 期间多次荣获ACM，IEEE及其他各类计算机重大奖项
- Lamport对时间时钟、面包店算法、拜占庭将军问题及Paxos算法具创造性研究
诞生
- 1990年将其对Paxos算法的研究论文The Part-Time Parliament提交给了ACM TOCS Jnl.的评审委员会
- 由于Lamport“创造性”地使用了故事的方式进行算法的描述，导致当时委员会工作人员没有一个能正确地理解算法
- 并要求Lamport使用严谨的正面方式来描述算法，否则将不予接收这篇论文
- 最终，Lamport拒绝了对论文的修改，并撤销对论文的提交
- 时隔6周年，来自微软的Butler Lampson在WDAG96上提出了重新审视这篇论文的建议
- 次年的WDAG97上，麻省理工学院的Nancy Lynch公布其根据Lamport的原文重新修改后的Revisiting the Paxos Algorithm“帮助"”Lamport用数学术语定义并证明了Paxos算法
- 1998年的ACM TOCS上，这篇延迟了9年的论文终于被接受
- 标志着Paxos算法正式被计算机科学接收并开始影响更多的工程师解决分布式一致性问题
- 2001年，Lamport本人也做出了让步，使用了通俗易懂的语言重新讲述了原文，并发表了Paxos Made Simple
- 然而Lamport本人认为他自己的表述足够让人理解Paxos算法，所以通篇没有任何数学符号
论文故事
- 一个叫Paxos的小岛上住了一批居民，岛上所有事情由一些特殊的人决定，他们叫做议员(Senator)。议员总数是确定的，不能更改。岛上每次环境事务的变更都需要通过一个提议（Proposal），每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号的提议，就会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己的记事本上记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。
- 现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1。于是他给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息后查询记事本，哦，当前提议编号是0，这个提议可接受。于是他记下这个提议并回复：我接受你的1号提议；同时在记事本上记录：当前提议编号为1。发起提议的议员收到超半数的回复，立即给所有人发通知：1号提议生效！收到的议员会修改自己的记事本，将1号提议由记录改成正式法令，当有人问他电费为多少时，他会查看法令并告诉对方：1元/度。
- 现在看冲突的解决：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1设为1元/度, S2设为2元/度。S3先收到了S1的提议，他在记事本上做了记录。紧接着他收到了S2的提议，他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。
