CSE_lecture14:2PC+Replication

Consistency under partial failure: 2PC & replicated state machine

2PC and CAP

CAP认为consistency(linearizability, all-or-nothing, before-or-after, …), availability（响应时间短，规避重启）, partition tolerance（在网络分区的前提下，保证在消息丢失或系统故障下正常运行）三者不能兼得

2PC保证了consistency，使用replication保证availability，而replication难以保证操作顺序，解决方法为：

• optimistic replication: eventual consistency
• pessimistic replication: linearizability

为了防止顺序不一致导致的死锁问题，2PC使用linearizability更好，因此希望primary-backup model更通用

当primary挂了时，有以下方法：

• 选一台backup变为primary，但人类难以快速切换
• 使用coordinator决定哪个backup来充当primary，速度极快，但为了防止coordinator挂了，需要使用多个coordinator，但它们的决定可能不一样
• 黑魔法，如raft

而网络分区也可能导致各个coordinator处在不同的分区，导致它们认为自己分区的backup是primary，从而导致同时出现多台primary

view server记录谁才是真正的primary，还记录了历史的primary，切换时view号加一

coordinator询问谁是当前的primary，得到结果后会cache这个view信息，减小网络开销；view server监听replica的heartbeat，primary挂了时，更新view number并分配新的primary（新的primary直到收到view number后才从backup变为primary，此前还是接受primary的同步和拒绝coordinator的请求）；而网络分区也可能导致heartbeat收不到，导致出现多台primary(split brain)，因此backup同步时还需要带上view number，当其小于primary时就reject，从而区分旧的和新的primary（这是建立在primary必须等待backup全部ACK的前提下的，从而实现请求的拒绝）

由于primary要等待所有的backup的ACK，当backup挂了时，反而导致了系统不工作；可以让primary只等待一部分backup的ACK，但选择新的primary时需要额外处理，即需要从多台机器中读取最新的数据拼接起来来恢复，事实上很快

quorum要求，写入时挑选 $Q_w$ 台机器写入，恢复时从 $Q_r$ 台机器中读取出来，只要保证 $Q_r + Q_w > \text{Nreplicas}$ 即可

最后的问题是view server挂了怎么办，因此需要引入paxos

paxos

single-decree paxos: agree on a single value w/o a view server

当只有一台writer时，遵循quorum即可，但问题在于怎么处理多台writer

paxos的角色有client, proposer, acceptor, learner，每个paxos node为后三者三合一，即每个节点充当里面的所有职责：

proposer要判断自己是否是唯一的writer(leader)，即当它的proposer number最大时为唯一的writer（只需要询问超过半数的机器，从而保证冲突，需要存放highest proposal number seen）（因为另一个proposer在询问时势必会访问到重叠的acceptor，从而保证能决定冲突

single-decree paxos的流程如下：

• prepare:
  • proposer接收到client的请求后，生成一个递增的proposal number N（为轮次/server id对，先比较前者）（N应当大于previous proposal number seen），并发送给所有的acceptor（当然理论上发送给半数以上就可以了，但这是为了更保险）
  • acceptor收到消息后，与自己已经做出承诺的proposal number比较，当N大于它时作出承诺，且当已经有接受的提案时返回额外的acceptedProposal和acceptedValue；否则拒绝或忽略。proposal收到半数以上的promise后，认为可以进入accept阶段（这里就会更新已作出承诺的proposal number，而acceptedProposal还没更新）
• accept:
  • proposal收到多数派后，选择acceptedProposal最大的哪个acceptedValue，否则才能由自己决定value，并发送消息给多数派
  • acceptor收到消息后，还是要检查N是否大于已作出承诺的proposal number，通过后再更新acceptedProposal和acceptedValue（注意这里才更新acceptedProposal）

可以认为slot, one single-decree paxos, client request一一对应；而被拒绝的request后续会对应到新的slot和single-decree paxos上去；而learner一般只读，作为一个可选的部分，在系统紧张时才参与进来；在phase 1结束后，那个获得多数派承诺的proposer成为leader，直到它挂了

一个简单的理解是proposal number用于选举唯一的write(leader)，而single-decree paxos是为了让leader知道它现在不再是唯一的writer了

举个例子，假设现在有三个acceptor A, B, C，其中A和B也是proposer：

• A发送<prepare, 1>，得到A和C的响应
• A发送<accecpt, 1, “foo”>给A和C并得到响应，此时A得到多数派响应，认为”foo”被选择；但A在给B发送<accept, 1, “foo”>前挂了
• B发送<prepare, 2>并得到B和C的响应
• B发送<accept, 2, “bar”>给B和C并得到响应，此时B得到多数派响应，因此认为”bar”被选择

事实上上述流程并不会发生，这并不是说B不是多数派，而是”bar”不会覆写”foo”

故在paxos，以下情况哪个让V被写入？

• leader收到了多数派的<promise, …>：还没有开始写value
• 多数派收到了<accept, N, V>：只是收到了，因为prepare-accept之间可能被人抢先；还有可能acceptor挂了
• leader收到了多数派的<accepted, …>：现在才能确保V被写入

paxos使用以下方法应对failure：

• acceptor在发送promise后挂了：acceptor需要记住 $N_h$
• acceptor在收到accept后挂了：acceptor需要记住 $N_h$, $N_a$, $V_a$
• leader在发送accept后挂了：重新生成一个 $M_n$ ，其不用被记住

目前我们在没有view server的情况下也能正常运行，但让leader挂了后，就再也修改不了value了

multi-paxos: agree on a sequence of values

为每个log entry分配一个paxos(paxos instance)，当发起的paxos instance在别的acceptor里面已经有了value时，选择一个更大的paxos instance，直到找到一个没有value的paxos instance，但这样的方法导致了需要多次尝试，这反而在性能上不如primary-backup（多了一轮RPC）

paxos在只有一个确定的leader时，可以进行优化，即一次性bacth完所有的paxos instance来发起一次prepare，再依次进行accept

paxos其实是不需要leader也能保证正确性的，但leader可以加速实现

paxos的log可能会出现不连续的情况，维护更困难