一致性的原因
- 数据存在多台机器上
- 数据在不同机器上需要保证相同
分类
-
强一致性
保证提交改变后，马上改变集群的状态
- Paxos
- Raft (multi-paxos)
- ZAB (multi-paxos)
-
弱一致性
最终一致性，不保证改变马上生效，随着时间的推移，状态会最终一致
- Gossip
Paxos算法
概念：
- Proposal：提案，编号N，内容value
- Client：负责提交提案
- Propser：负责接收client的提案，并向Acceptor发出修改的建议
- Acceptor：负责对提案进行投票
- Learner：负责接收提案，并修改自身的数据
算法步骤：
- client向Proposal提交N号提案
- Proposal发起要求Acceptor对N号提案投票
- Acceptor对比N号是否大于自身的数据版本，如果大于，则同意，否则投否定票
- 如果通过，Proposer广播提案，Learner接收
节点故障：
- Proposer故障，则在集群中选出新的Proposer
- Acceptor故障，由于是多数派选举，所以没问题
存在的问题：
- 加入系统有多个Proposer，他们不断的向Acceptor发出提案，还没等上一个提案达到多数派，下一个提案又来了，会导致Acceptor不断放弃提案，于是系统的大部分提案都有可能通过不了
- 没有选主功能
Multi Paxos算法
- 让整个系统只有一个Proposer来解决上述问题
- 算法步骤：
- 如果集群中没有Leader，则选择一个节点作为Leader
- Acceptor只表决最新Leader发出的提案
- 其他跟Paxos算法一致
Raft算法
Paxos算法不容易实现，Raft是对Paxos算法的简化和改进
概念：
- Leader，负责发出提案
- Follower：追随者，负责提案的投票
- Candidate：负责争夺Leader
步骤：
- Leader选举
- Leader会向Candidate发出心跳，来表示自己活着
- Candidate如果长时间没有收到Leader的心跳，就会向其他Candidate发出自己要成为Leader的要求
- 状态复制
- Leader收到提案
- Leader向Follow发出提案的投票要求，半数以上通过则通过
- 日志复制
- client提交改变到Leader，leader会同步到Follower，并写入Log
- Follow也会写入log
- Leader与Follow的心跳会带有log的最大index，Leader会比较index，来决定Follow的log是否与自己的一致
- 如果出现不一致，Leader会修复Follower的日志，直到一致为止
问题：
如果半数以上的节点故障，则会造成提案永远通不过
Gossip算法
集群中的节点在收到提案后，会随机向集群内的部分节点发起数据同步，接收到新数据的节点也会随机的向集群内的其他节点发起数据同步。
在经过一段时间后，集群的数据达到一致
应用案例
Consul
- 使用Raft协议和gossip
- 第一个Consul Server设置成Bootstrap，选举自己为Leader
- 随后当集群扩大，boostrap被禁止，Consul server作为peer set加入
- 当RPC请求到非leader节点，请求会转发到leader节点
性能问题：
如果Consul Server过多，会导致提案的修改，需要等待半数以上的Server同意，Server过多，会导致等待过长时间，带来性能问题
模式：
- Default： Leader有约期，如果在约期内，发生脑裂，原来的leader没办法获得半数以上的投票，因此没法提交任何新的改变，但是客户端可以支持读取，但读取的数据有可能是陈旧的
- consistent:强一致性，数据由leader保证
- stale：允许在任何集群中的服务器读取，不管是不是leader。这会导致读取到的数据有可能是陈旧的
Redis cluster
通过gossip协议使元数据保持一致
Gossip的好处是所有节点陆陆续续的更新，有一定的延时，但是降低了网络的压力
消息类型：
- Meet：申请加入集群
- Ping，节点会定期向集群的其他节点发送ping，消息中带有槽，状态，地址和最后一次通讯的时间
- Pong，节点收到ping或者meet会回复pong，消息带有元数据
- Fail：节点被检测下线，会向集群广播该节点下线
由于去中心化的通讯机制，Redis cluster选择最终一致性和基本可用的原则
除了Fail信息是立即全网通知，其他的消息都是通过ping信息一层一层的扩散出去的。
故障检测
- ping消息不通，标志位主观下线，并gossip到其他主节点
- 如果集群内有大于半数的主节点判定节点为主观下线
- 则广播fail消息，通知节点客观下线
- 如果下线的是主节点，从节点会根据与主节点的数据落后程度，选择一个最优的从节点，从节点会询问集群中的主节点投票是否支持自己成为主节点
- 如果有半数以上的投票数，从节点会成为主节点
Reshard原理
- 迁移哈希槽
- 标记目标机器的slot
- 设置源机器的slot是migrate中，使得如果有请求过来，会先判断key是否已经migrate，如果没有，则处理，否则会让client重定向到目标机器，进行操作
- 从源机器迁移数据到目标机器
- 用gossip协议，通知所有集群节点slot的新归属机器
zookeeper
采用ZAB协议
- 集群在半数以下的节点诺记，可以正常对外服务
- 客户端的写请求全部转交leader处理，leader实时同步到所有的follower和observer
- leader 宕机或者整个集群重启，需要保证那些已经在leader服务器提交的事务最终被所有服务器提交
选主
- leader 宕机
- 节点选举自己为leader，并广播自己的id和事务id
- 其他节点比较事务id，如果大于或者等于自己的id，那么投赞成票，否则投反对票
- 判断自己收到过于半数以上的票，则成功，并广播出去
选主后消息同步
- 获得learner的信息
- 比较事务id，如果id不再leader的事务列表中，learner的事务需要回滚
- 如果id小于leader的事务id，则leader会向learner同步余下的事务
事务操作
consistenct-zk
