consensus协议，有paxos、raft、pacificA，应用最普遍的有paxos。由于paxos难以理解、实现困难，例如日志空洞（leader宕机时，当前leader在上一任leader的任期内可能错过了一些日志的同步, 而这些日志在其他机器上形成多了多数派. 由于logID连续递增, 被错过的日志就成了连续logID连续递增序列中的”空洞”, 需要通过重确认来补全这些”空洞”位置的日志。）的处理等非常复杂，诞生了raft，逐渐替代paxos普遍应用到分布式系统中，例如mongodb、kafka等。
raft
一致性协议，一般是基于replicated state machine，基于这个理论：所有节点处理相同顺序相同内容的指令，结果就会一致。一般是以log的方式实现，将client请求append到log中，并同步给各节点，对raft而言做了简化，只有leader才执行读写，日志只会从leader流向follower，follower只参与选主，平时只做replicate。 
consensus解决的实际上是3个问题：选主、log复制、safety(never returning an incorrect result) under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering.)。 client请求只要大多数执行成功即返回成功。只要the majority of servers are operational and can communicate with each other and with clients，这个分布式系统就是稳定的。 Raft只有两类rpc，选举与append log，并约定一定的规则。见如下两图：注意约定的规则，在图中也有说明。
以下是选主rpc
以下是append log rpc
以下是各节点选主状态转换图
初始时，大家都是follower。leader通过定期heartbeat告诉follower自己是主。如果heartbeat间隔大于elect timeout，follower认为没有leader，就会发起选主。 任期term随时间递增，发起elect，会生成新的term，发给rpc给其他所有server，变成candidate. 万一同时有多个candidate多个term怎么办？重试 + raft引入了随机时间。每个节点的Elect timeout(150-300ms)在满足一定规则（broadcastTime ≪ electionTimeout ≪ MTBF）的情况下是随机的，这样保证有先后之分，万一发生，就重选。重选很快，一般是ms到1s级完成。
注：broadcastTime is the average time it takes a server to send RPCs in parallel to every server in the cluster and receive their responses，取决于server持久化的时间，一般是0.5-20ms写到硬盘。MTBF is the average time between failures for a single server，一般非常大。
Log replication： leader会不停地重试，向follower发append log rpc，直到得到follower的确认。当大多数follower确认了，leader才写自己的log，才响应给client说完成。这个和kafka的acks=all是一致的。后面kafka实现Kraft时，默认是acks=all。log设计的很有特点，有index，也有entry，相同index必须相同，所以对相同index的write是幂等的。
为了保证一致性，会执行consistency检查。首先，A leader never overwrites or deletes entries in its own log。 并且leader appendrpc（nextid）判断和follower保存的是否一致的，不一致的话，会decrease，直到找到nextid = match index。正常情况下是majority保持同步，所以a single slow follower will not impact performance。
关于日志空洞，raft通过elect rpc中的规则限制保证不会发生。并在论文中用了反证法论证。 关于节点变更等集群配置动态更新，raft是使用了c_old + c_new，同时支持，并结合两阶段提交实现事务，平滑切换集群。
扩展浅谈kafka的副本一致性：
主要涉及replicate factor、acks、metadata refresh、isr的设计。
- Replicate factor 副本数，默认是broker级别，可topic定制。kafka官方或行业的经验值，是副本数设为3，这样可以有两个节点宕机的容错性。
- client只从分区leader读写数据，通过metadata refresh知道leader在哪个server。可见的消息leader会知道，所有isr都写入的latest offset即是高水位。
- 没有用majority vote，因为kafka做为数据服务，majority 2n+1浪费存储. 一致性的对象是isr(in sync replica)，Isr通过配置lag time指定isr允许的最大延迟。leader写follower，只有isr都写入了，这个log才算commit，万一都没有isr呢？所以配了一个min.isr（这个折衷看consistency需求和不可用的风险，默认为2），达到最小isr数量才能写，否则分区不可用。 如果开了unclean.leader.election.enable则会允许数据丢失，因为不在isr中的也有成为leader的可能。什么时候isr会写到zk？isr变更时，就会更新，降低了zk的压力。
- Acks主要设计的是生产消息时，是否ack，保证持久化才ack，即能保证数据是写入成功了，严格说和副本一致性没什么关系。ack=all指的是ISR都写入了，而不是所有分区都写入。
No Comments
Leave a comment Cancel