阅读http://book.mixu.net/distsys/replication.html的笔记，是本系列的第四章

拷贝其实是一组通信问题，为一些子问题，例如选举，失灵检测，一致性和原子广播提供了上下文。

同步拷贝

可以看到三个不同阶段，首先client发送请求。然后同步拷贝，同步意味着这时候client还在等待着请求返回。最后，服务器返回。

这就是N-of-N write，只有等所有N个节点成功写，才返回写成功给client。系统不容忍任何服务器下线。从性能上说，最慢的服务器决定了写的速度。

异步拷贝

相对的是异步拷贝。

master节点立即返回。该节点可能在本地做了复制，但是不会向其他服务器发送拷贝。只有在返回以后，异步的任务在开始执行。

相对地，这是1-of-N write。性能上说，快。但是不能提供强一致性保证。

主流拷贝的途径

作者用下面的方式分类：

• 可防止divergence（单拷贝系统）
• 存在divergence（多master系统）

第一类途径使系统表现得像“single system”，即使系统部分失效。

单拷贝系统按照一次执行中传递的消息数目，可以做一下分类：

• 1n messages（异步 主从备份）
• 2n messages（同步 主从备份）
• 4n messages（2-phase commit，Multi-Paxos)
• 6n messages （3-phase commit，Paxos with repeated leader election）

下面的图告诉我们，在不同侧重中选择（折中），我们会得到什么样的结果。

等待，性能就变差，一致性上的保证就更强。

主从备份拷贝（Primary/Backup replication）

最常见最基本的拷贝方式。所有的update发生在primary，并且以log的形式拷贝到backup 服务器。主从备份也分同步和异步两种。

MySQL和MongoDB都使用异步主从备份。同步主从备份保证在返回给client之前，backup节点成功存储了拷贝（Replica）。不过即使这样，同步方式也仅能保证较弱的承诺。考虑下面的场景：

• 主服务器收到write，发送到backup
• backup 写成功。返回ACK
• 主服务器fail，client超时，认为写失败。

client现在认为写失败，但是backup其实成功。如果backup promote成为primary，那么就不对了。

2阶段提交（2PC）

2PC在很多经典的关系型数据库中都使用到了。例如MySQL 集群使用2PC提供同步拷贝。下面是2PC的基本流程

[ Coordinator ] -> OK to commit?     [ Peers ]                <- Yes / No[ Coordinator ] -> Commit / Rollback [ Peers ]                <- ACK

在第一阶段，投票，协调者（Coordinator）给所有参与者发送update。每个参与者投票决定是否commit。如果选择commit，结果首先存放在临时区域（the write-ahead log）。除非第二阶段完成，这部分都只算“临时”的update。

在第二阶段，决策，协调者决定结果，并通知参与者。如果所有参与者都选择commit，那结果从临时区域移除，而成为最终结果。

2PC在最后commit之前，有一个临时区域，就能够在节点失效的时候，从而允许回滚。

之前讨论过，2PC属于CA，所以它没有考虑网络分割，对网络分割并没有容错。同时由于是N-of-N write，所以性能上会有一些折扣。

对网络分割容错的一致性算法

最著名的是Paxos算法，不过比较难理解和实现。所以Raft可以讲讲。

什么是网络分割（Network Partition）

节点本身正常运行，但是网络链路发生问题。不同的Partition甚至还能接收client的请求。

2节点，节点失效 vs 网络分割

3节点，节点失效 vs网络分割

单拷贝一致系统必须找到方法去破坏对称性。否则如果网络分裂成两个独立对等系统，divergence发生，无法保证single-copy。所以必须保证只有一个Partition处于活动状态。

多数的决策

所以，对分割容错的一致性算法依赖多数投票。依赖多数，而不是所有（例如2PC）节点，即可容许少数因为网络分割出现的较慢的，无法到达的节点。只要 （N/2 + 1）of N中的节点正常，系统就可以正常运行。

在对网络分割容错的算法中，系统一般使用奇数数目的节点，例如3个节点的系统，允许1个节点失效。5个允许2个失效。这样发生网络分割，我们总能找到一个“大多数”的Partition。

角色

在系统中，节点要么都扮演同一角色，要么各自担任不同角色。

一致性算法通常使节点扮演不同角色。有一个固定的领导或主节点，可以让算法更加高效。Paxos和Raft都利用了不同角色。在Paxos中，存在Proposer。领导者负责在操作中协调，余下的节点作为followers（Paxos中的Acceptors 或者 Voters）

Epochs(不翻了。。。）

在Paxos和Raft中，每次操作的周期都叫一个Epoch（”term“ in Raft）。在每个epoch，都有一个节点被指定为领导（Leader，后面都用英文吧，免得有歧义）。这个有点类似中国的朝代。

在每一次成功的选举后，一个epoch始终使用一个固定的leader，如上图。一些选举可能失败，那么epoch里面迭代到下一个。

真有点类似前面提到的逻辑时钟，让其他节点可以辨识凹凸的节点。那些分割的节点的epoch计数会比较小。

通过决斗（Duels），改变Leader

在一开始，某节点变成leader，其他节点成为follower。在操作过程中，leader维护心跳消息，这样follower就知道leader是否失灵，或者有网络分割发生。

当某节点发现leader没有响应了，（或者在初始状态，没有leader），该节点就转换成中间模式（在Raft称为candidate），然后将其epoch计数加1，发起leader的选举（election），竞争成为leader。

要成为leader，节点必须接收到足够多的votes，一种获取vote的方式就是谁先到谁取得。这样，最终会选出一个leader。

在epoch内，数字标记提案(Proposal)

在每个epoch，leader提议某值用于投票。提案用一个唯一的递增的数字标记。followers则接受它们收到的第一个提案。

普通操作

普通操作中，所有提案都经过leader节点。当一个client提交提案（client指分布式系统使用者），leader节点联系所有法定人数中的节点，如果在follower的回复中，没有与此冲突的提案，leader就提议某值。如果大多数follower都接受该值，那么该值就被认为正式接收。

当然有可能另外一个节点也在尝试成为leader，我们需要确保一旦提案被接受，该值永不改变。否则一个已经接受的提案可能被另外一个竞争leader推翻。

Lamport对该属性有如下表述：

如果对于值v的某提案被选中，那么每一个有较高数字标记的提案都有该值v。

 原文如下：

P2: If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

这个性质可以理解为一致性，也就是业已提出的提案，对其他后来提案都可见，是一种有效性。

为了保证该属性，proposer（leader）必须首先要求followers出示它们已有的最高数字的提案和值。如果proposer发现某提案已经存在，那么必须首先完成执行而不是重新提出提案。Lamport表述如下。

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

更具体地，

P2c. For any v and n, if a proposal with value v and number n is issued [by a leader], then there is a set S consisting of a majority of acceptors [followers] such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the followers in S.

这是Paxos算法的核心。如果之前有多个提案存在，那么数字标记最高的提案会被提出。为了保证在leader在依次询问每个acceptor其最新的value的过程中不出现冲突的提案，leader告知follower不要接受比当前提案数字标记小的提案。

那么在Paxos中要达成一个决策，需要两轮通信。

[ Proposer ] -> Prepare(n)                                [ Followers ]             <- Promise(n; previous proposal number                and previous value if accepted a                proposal in the past)[ Proposer ] -> AcceptRequest(n, own value or the value   [ Followers ]                associated with the highest proposal number                reported by the followers)                <- Accepted(n, value)

准备阶段，proposer须知道任何冲突或者之前的提案。第二个阶段，一个新的value或者之前被提出的value，在proposer处提出。在某些情况下，比如说同时有两个proposer；比如消息丢失了；或者大多数节点失灵，那么不会有提案被多数节点接受。而这时允许的，因为最终的value还是收敛的。（也就是拥有最高数字标记的那个提案）。

这里非常类似西方民主国家的决策流程。在某项政策需要执行前，首先举行听证会，广泛征求意见。然后根据反馈的结果确定最后的政策。

当然在工程实现上还有不少挑战，这里列举了一些。

网络分割容忍一致性算法的例子：Paxos，Raft和ZAB

强一致下的拷贝算法

总结下各类算法的一些关键特征。

主从备份

• 单独的，静态的master节点
• 复制日志，slaves节点并不参与执行具体操作
• 拷贝操作的延时没有上限
• 无法容错网络分割
• 在不一致和错误发生情况下，需要手工干涉

2PC

• 统一投票：提交或者放弃
• 静态的master节点
• 协调者和普通节点同时挂掉情况下无法保证一致性
• 无法容错网络分割

Paxos

• 多数投票
• 动态master节点
• 允许n/2-1节点挂
• 对延时并不太敏感

[分布式系统学习]阅读笔记 Distributed systems for fun and profit 之四 Replication 拷贝