本文摘录自《分布式系统的事务处理》。
Master-Slave
Master-Slave结构中，Slave一般是Master的备份。
- 由Master负责读写请求
- 写请求到Master上后，由Master同步到Slave。
同步方式：
- 异步或同步。
- Master来push或者slave来pull。
属于最终一致性。
异步的问题
如果Master在同步的周期内垮掉，会导致这段时间的数据丢失。如果不想出现数据丢失，Slave就需要设为Read-Only等待Master恢复。
如果能容忍数据丢失，可以马上让Slave代替Master工作。（对于只负责计算的节点来说，没有数据丢失的问题）。
强一致性，同步写
在事物中，Master先写自己，成功后，再写Slave，都成功后再返回成功。
如果Slave写失败，有两种方法。
- 标记Slave不可用，报错并继续服务。（等Slave回复后同步Master的数据，有多个Slave时，少一个就还有备份）
- 滚回，返回写失败，
注意：一般不会先写Slave，因为如果Master失败后，还要回滚Slave，这样就增加了风险，如果此时Slave回滚失败，就得手工订正数据。
阿里云的RDS
RDS就是采用的主从热备。主库负责读写，然后通过DRC异步传输到备库，最终一致。目前支持备库读数据。
如果出现主库异常，会停止主备库的写，然后同步主备数据，在备库增量跟上主库后，将链接切到备库。
Master-Master
Master-Master，又叫Multi-master，一个系统存在两个或两个以上Master，每个Master都提供read-write服务，这个模型是Master-Slave的加强版。数据同步通常异步完成。也是最终一致性。
也存在同步周期内垮掉时数据丢失的问题。
多个Master对同一个数据进行修改时，就会出现数据冲突的问题。
Two/Three Phase Commit
又叫2PC，两阶段提交。
分布式系统中，一个事物会跨越多个节点。但是每个节点无法知道其它节点操作是否成功。所以需要加入一个协调者来管理所有节点的操作，指示各个节点是否真正提交事物（持久化）。
第一阶段：
- 协调者询问参与者是否可以执行提交操作。
- 参与者进行准备，比如上锁，预留资源等
- 响应协调者是否可以提交。
第二阶段：
如果所有参与者回应可以提交，则发送正式提交命令，参与者完成正式提交，然后回应完成。协调者接受完成回应，结束这个事务。
如果有一个参与者回应拒绝提交，协调者向所有参与者发送回滚指令。参与者会释放所有资源，然后回应回滚完成。协调者接收到所有回滚回应后，取消这个事务。
小结：
2PC就是第一阶段投票，第二阶段决定。2PC比Master-Slave的强一致性策略更为保守，先尝试后提交， try -> confirm的流程。
举个例子，西方结婚的场景：
- 牧师分别问新郎和新娘：你是否愿意……不管生老病死……（询问阶段）
- 当新郎和新娘都回答愿意后（锁定一生的资源），牧师就会说：我宣布你们……（事务提交）
问题：
同步阻塞操作，影响性能。
TimeOut的问题。
- 第一阶段，询问时，参与者没收到询问，或者协调者没收到回应。（认为失败，或重试）
- 第二阶段，正式提交命令发出，参与者未收到，或者协调者未收到回应。（重试，或者剔除集群）
- 第二阶段，参与者收不到协调者指令。可能是协调者宕机。（死等协调者，或者重发第一阶段的回应）
最大问题：第三项中，如果第一阶段完成，参与者在第二阶段没有收到决策（提交命令），数据节点会进入“不知所措”的状态，block住整个事物。
三段提交
把二段提交的第一个段分为两段，询问，然后再锁定资源。
3PC的状态迁移图：（注意图中的虚线，那些F,T是Failuer或Timeout，其中的：状态含义是 q – Query，a – Abort，w – Wait，p – PreCommit，c – Commit）
核心理念：询问时不锁定资源，所有同意后锁定资源。
- 第一阶段，询问，接收回应。如果所有回应可以提交，进入下一阶段。否则通知失败。
- 第二阶段，通知锁定资源，接收回应。如果所有回应可以提交，进入下一阶段。否则通知失败。
- 第三阶段，通知正式提交。如果有回应拒绝提交，则发送回滚操作。
依据：第一阶段所有节点返回成功，有理由相信提交成功概率很大。
相对二阶段提交的好处在于，如果前两个阶段都成功（相对与三阶段提交），即使参与者没收到正式提交通知，也可以继续提交。因为前两个阶段都成功，说明正式提交的可能性很大。
一个网络服务会有三种状态：1）Success，2）Failure，3）Timeout，第三个绝对是恶梦，尤其在你需要维护状态的时候。
Two Generals Problem（两将军问题）
有两支军队，它们分别有一位将军领导，现在准备攻击一座修筑了防御工事的城市。这两支军队都驻扎在那座城市的附近，分占一座山头。一道山谷把两座山分隔开来，并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。不幸的是，这个山谷已经被那座城市的保卫者占领，并且存在一种可能，那就是任何被派出的信使通过山谷是会被捕。 请注意，虽然两位将军已经就攻击那座城市达成共识，但在他们各自占领山头阵地之前，并没有就进攻时间达成共识。两位将军必须让自己的军队同时进攻城市才能取得成功。因此，他们必须互相沟通，以确定一个时间来攻击，并同意就在那时攻击。如果只有一个将军进行攻击，那么这将是一个灾难性的失败。
抽象一下：
- A给B一个信息x，但A无法确定B是否收到这个信息。
- 所以，B发一个信息y，确认收到A的信息x。
- 但是，无法保证A收到B的信息y，所以B可能还会发一个信息z给A,确认收到信息Y。
于是，我们发现这个事情就是个无解的问题。
说明：试图通过建立在一个不可靠的连接上的交流来协调一项行动的隐患和设计上的巨大挑战。
我们无法保证可靠，但可以削减不可靠性。
拜占庭将军问题 (Byzantine Generals Problem)
拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，些叛将军与将军之间只能靠信差传消息。 在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，这徒将军们会扰乱或左右决策的过程。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，这就是拜占庭将军问题。
Paxos算法
2PC/3PC都是分布式一致性算法的残次版本，Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。
Paxos算法基本上来说是个民主选举的算法——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案，是否通过这个提案取决于这个集群中是否有超过半数的结点同意（所以Paxos算法需要集群中的结点是单数）。
第一阶段：Prepare阶段
A把申请修改的请求Prepare Request发给所有的结点A，B，C。注意，Paxos算法会有一个Sequence Number（你可以认为是一个提案号，这个数不断递增，而且是唯一的，也就是说A和B不可能有相同的提案号），这个提案号会和修改请求一同发出，任何结点在“Prepare阶段”时都会拒绝其值小于当前提案号的请求。所以，结点A在向所有结点申请修改请求的时候，需要带一个提案号，越新的提案，这个提案号就越是是最大的。
如果接收结点收到的提案号n大于其它结点发过来的提案号，这个结点会回应Yes（本结点上最新的被批准提案号），并保证不接收其它<n的提案。这样一来，结点上在Prepare阶段里总是会对最新的提案做承诺。
优化：在上述 prepare 过程中，如果任何一个结点发现存在一个更高编号的提案，则需要通知提案人，提醒其中断这次提案。
第二阶段：Accept阶段
如果提案者A收到了超过半数的结点返回的Yes，然后他就会向所有的结点发布Accept Request（同样，需要带上提案号n），如果没有超过半数的话，那就返回失败。
当结点们收到了Accept Request后，如果对于接收的结点来说，n是最大的了，那么，它就会修改这个值，如果发现自己有一个更大的提案号，那么，结点就会拒绝修改。
总结：
著名的CAP理论：一致性，可用性，分区容忍性，你只可能要其中的两个。
目前而言，对于数据库来说，最最重要的还是log需要先写入磁盘，持久化。因为只有它才能恢复当时的操作。所以，分布式系统中，通常需要保证log写入半数以上的slave，然后确认提交事务。
