分布式一致性与共识
在学习微服务RPC，服务注册发现等相关概念时，总是绕不开一个话题分布式一致性，虽然之前在MIT6.824的课程中已经进行深入的学习，但是每每遇到还是对这些概念不甚清晰，因此这篇博客主要是从整合的角度复习之前学过的知识。
常见概念
分布式和单机本质的不同在于没有一个统一的时钟以及一份数据有多个副本，不同的用户请求于不同时间发出，由于网络延迟等问题以不同的顺序，对不同数据副本进行操作，这就带来两个问题：
- 如何确定谁的请求先来，谁的请求后来，怎么确定一个所谓的“先来后到”？（可以类比Mysql并发控制的感觉）
- 副本的操作如何及时同步，用户能不能看到最新的副本？
分布式一致性 实际上就是对分布式服务对上述两个问题解决程度的一种抽象描述，定义了一个分布式应用能够有像“单机应用”的衡量标准，几个分布式一致性的概念不在赘述，见分布式事务总结。而共识算法则是保证分布式一致性的手段，采取合适的共识算法达到不同程度的分布式一致性,简单理解就是如何在一群人中对一个方案达成共识，常见的共识算法包括：
- Paxos：所有共识算法的亲爹，见 共识算法-Paxos
- Raft：目前广泛应用的共识算法， 见 共识算法-Raft
- ZAB：zookeeper中实现的共识算法，见 ZooKeeper论文总结
- Gossip：经典的弱一致性共识算法
- Distro：Nacos实现的弱一致性共识算法
上述是从理论的角度分析分布式一致性问题，当我们把视角转到分布式应用又会引出两个概念：
- CAP：当发生网络分区时（Partition），一个分布式应用是选择保C（Consitincy）还是选择保A（Availability）
- BASE：作为一个服务提供商，在网络分区问题出现时我不可能舍弃A，在牺牲一定程度C的情况下，继续提供一定程度的A。
- Basically Available：提供一定程度的可用性
- Soft State: 软状态指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性， 即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时
- Eventually Consistency: 经过一段时间同步后，所有副本都达到一致性的
主要的概念其实就这么多，其他都是深入实现细节后引出的拓展概念，下面简单总结一下之前没学过的分布式共识算法。
共识算法
三个强一致性协议在之前就已经学习过，不再废话，主要新整理一下最近接触到的弱一致性共识算法。
Gossip算法
原论文：《Epidemic Algorithms for Replicated Database Maintenance》
博客写的太好了，我在他的基础上简单总结强化记忆，建议直接看：[分布式系列]Gossip协议
论文中描述了三种节点见数据同步的方式：
- 直接邮寄（direct mail）：广播模式，每个结点的更新都会通知到其他所有节点。
- 反熵传播（anti-entropy）：每个节点都会定期随机选择节点池中的一些节点，交换数据实现同步。
- 谣言传播（rumor mongering）：当节点更新时，周期性随机选择向周围固定数量的节点同步更新，接收到的节点更新的节点执行相同逻辑（不会向发送个自己的节点发送），直到节点节点发现周边节点都获取到这个更新
其中通信模式包括：
- 推模式：推送数据到目标节点，目标节点更新
- 拉模式：发送节点通知目标节点自己版本号，目标节点根据版本号推送新数据到发送节点，发送节点完成更新
- 推拉模式：在拉模式最后，发送节点再发送自己更新的数据给目标节点。
Gossip协议存在消息冗余，收敛速度不可控等问题
Distro算法
Distro算法是Nacos自己实现的AP共识算法，直观感觉就是Gossip算法的变形优化，其主要特点为：
Nacos每个节点是平等的都可以处理写请求，同时把新数据同步到其他节点
每个节点只负责部分数据，定时发送自己负责数据的校验值到其他节点来保持数据一致性
1
int target = distroHash(serviceName) % healthyList.size();
每个节点独立处理读请求，及时从本地发出响应
当一个Nacos集群进程上线时，会轮询集群中所有的节点获取全量数据，正常运行时定期相互发送带有元数据信息的心跳，当接收方发现数据不一致时，会主动发起拉取任务。
由于每个节点负责部分数据，存储全量数据，因此读操作可以在任意实例上执行，写操作需要转发到对应的实例上执行。
总结：本质上还是Gossip协议，通过数据分片管理缓解了Gossip协议的消息冗余问题
- eureka类似于Nacos，同样基于一个类似于Gossip的协议实现了AP性质
- Consul基于raft实现了强一致，但是提供了三种读取模式，default（基于lease的leader读一致），consistent（基于确认消息的leader读一致），stale（任意节点均可读）
Raft补充
开头废话：之前在面试中回答完Raft协议本身，总要被问到一个问题：“你怎么保证客户端一定读取到最新的数据？“，对于这个问题我每次都会回答只要保证每次读取在leader节点读即可，然而往往会引入下一个问题：”只读主节点那么是不是浪费了副本节点的性能？有没有其他的解决方法？“。问题到这里我就回答不上来了，下面补充一下相关知识。
回顾上文中提到的分布式环境带来的两个主要问题，不难发现类似Raft一系列的强共识算法的解决方案基本相同：
- 通过定义逻辑时钟解决分布式环境下的”统一时钟问题“。如Raft的term，zab的zxid中高 32 位的epoch号
- 通过选举唯一的leader解决请求先来后到的问题，所有请求都由唯一leader执行，自然就有了顺序。
所以”读到最新副本问题“从何而来，本质上有两个原因：
- ”读操作“并不改变副本状态，不是一致性算法考虑的问题，一致性算法只保证修改状态的”写操作“的一致性。
- 一致性算法只能保证所有副本一致性的修改状态，不能保证何时达到一致性的状态（参考分布式中的safety & liveness概念）
因此要保证”读到最新副本“ 有两种解决方案：一是读leader，leader一定是最新数据；二是拓展一致性协议，使之兼顾follower 读。
leader读
leader读看起来美好，但是在遇到”脑裂“问题是还是会读到过期数据：
- ”脑裂“场景：网络出现分区划分为多数和少数节点分区，旧leader在少数节点分区仍认为自己是leader，然而此时多数节点分区已经选举出新的leader并执行了写操作
- 此时如果客户端向旧leader发起读操作，旧leader认为自己还是leader返回请求，就导致客户端读到了旧数据。
针对上述问题两个解决方案：
- follower read：leader在选举成功后维护一个lease（大于选举超时时间）,在当前lease内认为不会有其他的leader出现（即自己不会被取代），在lease时间内响应客户端请求，lease失效请求多数节点更新lease
- ReadIndex：leader在响应前通过心跳多数节点确认自身的leader身份
follower读取
leader读再怎么改进还是存在着单点性能问题，实现follower读方式为：
- follower read：follower向leader查询commitIndex，若commitIndex > applyIndex，则副本等待日志应用到对应index后再响应用户请求。
总结
根据上文中分析能够得到通过增加节点通信的方式能够解决”读不到“最新数据的问题，需要根据应用场景考虑是否一定需要保证读到最新数据，下面举几个例子：
- zookeeper 只提供弱一致性支持，即不保证客户端读到最新数据，除非客户端显式调用
sync()方法 - redis cluster基于raft选主，但是基于gossip实现同步集群信息同步，基于主从同步实现副本同步
- TiKV 默认支持 lease read（基于raft log 更新lease），后续版本更新了对于 follower read的支持
- etcd基于ReadIndex实现强一致性