分布式系统一致性协议
Two-Phase Commit
二阶段提交，分布式系统架构下保证所有节点在事务处理中保持原子性和一致性而设计的一种算法。一个事务跨越多个节点时，为了保证事物的ACID特性，需要引入一个作为Coordinator来控制所有Cohorts的处理结果，总体的思路就是：Cohorts将操作结果通知Coordinator，Coordinator根据所有Cohorts的结果判断是否提交或者中止操作。
阶段一
进行事务询问，Cohorts执行事务，将Undo和Redo信息记入事务日志，然后向Coordinator反馈结果
阶段二
分两种情况，执行事务或者中断事务。首先提交事务或者中断请求，然后进行事务或者回滚的提交，提交完后反馈结果。
分析：2PC原理简单，实现也不复杂，缺点主要有同步阻塞，单点问题，容错性不足导致数据不一致
Three-Phase Commit
三阶段提交是2PC的改进版
阶段一：CanCommit
询问事务，反馈给Coordinator
阶段二：PreCommit
对于事务预提交，首先发送预提交请求，执行预提交，然后反馈预提交结果。
对于中断事务，直接发送中断请求，随后中断事务
阶段三：DoCommit
与2PC的阶段二一致
分析： 引入了超时中断机制，Cohorts在第三阶段如果没有及时收到Coordinator发来的DoCommit或者Abort将会默认执行事务，这样能够避免长时间等待造成的阻塞，不过当DoCommit阶段某些Cohorts接收到了Abort，某些因为网络原因没有收到，这样仍然执行事务提交就会出现数据一致性的问题。
Paxos算法
Paxos是分布式系统中最广为人知的高度容错一致性算法，最近看了一些论文和博客，现在整理一下推导过程
对于一致性的要求的描述是：
- 只有被提议的值才能被选择
- 只能选择唯一的一个值
- 其他进程只会学习到那些已经被选择的提议
P1 一个acceptor必须接受它接收到的第一个proposal
P2 若值为v的proposal被选择，那么任一编号更高的proposal的值都为v
P2a 若值为v的proposal被选择，那么被任一acceptor接受的更高编号的proposal的值都为v
P2b 若值为v的proposal被选择，那么被任一proposer提交的更高编号的proposal的值都为v
P2c 对于任一的值v和编号n，若一个值为v，编号为n的proposal被提交，存在一个多数acceptor组成的集合S中，使得S中不存在任何acceptor接受过编号小于n的proposal或者被S中acceptor接受过的编号最大的proposal的值为v
P1a 只有当一个acceptor没有接受编号大于n的proposal的时候才能接收编号为n的proposal
Phase1
- 一个proposer选择编号n并且向多数acceptor发送编号为n的 prepare proposal
- 若一个acceptor接收到一个比已回复的prepare proposal的编号更大的 prepare proposal，那么将保证不会再接受任何编号小于n的proposal，以及回复已接受的（如果有）最大编号的proposal
Phase 2
- 若一个proposer接受到多数acceptor对自己 prepare proposal的回复，将向这些acceptor发送编号为n的 accept proposal，v 为所有编号最大的回复的值，或者为任意值若没有回复任何proposal的话
- 若一个acceptor接收到一个 编号为n的 accept proposal，只要其未回复过编号更大的 prepare proposal，就能通过该 accept proposal
分析： Paxos有一个 Majority 的概念，类似于少数服从多数
Paxos在工程上的实现并不像算法描述的这么简单，会遇到很多问题。后续会补充Chubby中Paxos的应用
Chubby
Chubby使Paxos第一次从论文中走进工业界，但是Chubby并没有开源
Vector Clock
Paxos与VectorClock的异同