Multi-Paxos做复制协议的挑战 - emailed

  在廉价PC机上,服务的容错高可用性可以通过多副本来达到,带来的代价是需要维护多副本的一致性。paxos用来在多个process之间对同一个值达成一致,称这个过程叫做一个paxos instance。通常来说,运行一个paxos instance对于数据库来说用处不大, 然而多个paxos instance 可以用来复制operation log,每条log对应一个对副本的更新操作,更新操作的顺序由leader决定,leader可以由一个选主算法选出。一条log通过一个paxos instance同步给其它的副本,其它副本通过回放log达成一致。

  复制协议是对一致性协议的扩展,对一系列更新操作进行排序并且持久化。复制协议其实就是并行的跑多个paxos instance。每个更新操作有一个sequence number,第 i 个paxos instance 决定的更新操作sequence number 为i。 Server 回放日志时按照sequence number递增顺序进行apply到内存。复制协议和一致性协议一样,选出一个主,由主给每个更新操作赋予一个sequence number,当主稳定不变时,它可以不断的propose 更新操作,可以将这段时期叫做一个View,所以在复制协议中,通过(view number, sequence number) 来标识一个proposal。

  在基于multi-paxos的复制协议中,选主的算法可以很简单,比如IP地址最小的Server为主。一旦选好主后,就可以由主来propose 更新操作。prepare阶段请求包含(view number, sequence number),acceptor响应(view number, sequence number, log)。如果主出现故障怎么办? 其它的备需要接替为主,那么备如何检测主故障?严格来说,这个不属于一致性协议的范畴。理论上来说,检测一台机器宕机无法做到。但是可以通过一些简单的手段例如定时心跳来检测。主每隔一段时间给所有备发心跳,当备有一段时间没有收到主的心跳时,则认为主宕机,这是备可以重新运行选主算法选主。但是,实际上主有可能没有宕机,只是网络闪断,主和其它备之间出现网络分区,这时,可能出现两个主,两个主同时propose 更新操作,这个时候,副本之间的一致性由paxos协议来保证。

   磁盘故障容错

   当磁盘出现故障时,持久化状态将丢失,比如已经promise的最大的view number,这会导致replica重启后接收到一个proposal消息时,有可能会promise一个比已经promise过的最大的view number更小的proposal。这违反了paxos算法的思想。这个问题可以如下方式解决:磁盘坏掉的replica重启后,作为一个不能进行promise/ack的replica参与paxos instance,也就是说他利用catch up机制从其它的replica恢复状态,catchup机制和raft类似。当replica观察到了一次完整的paxos instance时该replica结束不能promise/ack状态,进入正常replica状态参与随后的paxos instance。

   考虑一轮paxos,一个未经优化的paxos instance需要写5次磁盘,分别对应于propose(leader),promise,accept(leader),ack,commit(leader)消息。在每次发送消息之前,都需要将状态通过日志持久化到磁盘上便于宕机后通过回放log恢复状态。在这里,显然,磁盘成为整个算法的性能瓶颈。这里的磁盘容错方法刚好可以作为一种优化手段使得replica可以不必每次发送消息之前都flush状态到磁盘上。

    读优化

    对replica的读需要走一次paxos instance,原因在于非leader的replica可能选了一个新的leader,新leader可能拥有更加新的状态数据,还没有同步到老的leader。这会导致老的leader可能会返回旧状态数据。大体过程是客户端给leader发请求,leader做一次paxos instance,成功后,如果这次paxos instance同步的operation log以及之前的log都是连续的,则回放这条operation log,并且返回最新状态给客户端。也可以给所有的replica包括leader发请求,每个replica返回状态和对应的版本号,客户端取最大的版本号对应的状态即可。 对于读为主的workload的系统中,这个开销不能接受。为了避免出现多leader同时propose value到paxos中的情况,给master加上lease,含义是在leader lease有效期间,其它的replica不能选新leader,不能响应非leader的消息。这样一来,读请求只请求leader即可。这个方法也会带来问题:如果leader宕机,lease失效之前系统将没有leader,从而不能提高读写服务,与经典的paxos相比可用性大大降低,经典的paxos的一个很大的优点是可用性很高,少部分replica宕机同样可以读写。这个问题可以适当减少lease有效期解决,带来的代价是leader需要频繁延长lease。

    SnapShot

    使用paxos来做日志复制,日志不能无限增长,一是无限磁盘空间不实际,二是宕机恢复时间不可控。自然想到的方法是对内存状态做snapshot,宕机恢复只需加载最近的snapshot并且回放后续日志即可。原理与Raft类似。

    并行执行paxos instance

    多个paxos instance 可以并行执行,初始化时指定group member,编号为1~K的paxos instance可以并行执行,第i个paxos instance决定log的同时,也决定了第i+K个paxos instance的group member。随后编号为K+1~2K的paxos instance可以接着并行执行。并行执行paxos instance带来的一个问题是:由于log entry是顺序存放在文件中的,编号更大的paxos instance对应的log entry可能先commit,导致先写盘。如果编号更小的paxos instance对应的log entry长度比较大,就需要移动后面的log entry的位置。一个简单的处理方法就是限定每个log entry的尺寸大小,写盘时计算好偏移即可。

参考文献:

Paxos made simple

Paxos Made Live

Paxos for  System Builders

In Search of an Understandable Consensus Algorithm

http://raftconsensus.github.io/

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章