分布式相关理论详解

1.绪论

2.什么是分布式系统，和集群的区别

3.CAP理论

3.1 什么是CAP理论

3.2 一致性

3.2.1 计算机的一致性说明

1.事务中的一致性

2.并发场景下的一致性

3.分布式场景下的一致性

3.2.2 一致性分类

3.2.3 强一致性

1.线性一致性

a) 定义

a) Raft算法是如何实现线性一致性的

2.顺序一致性

a）顺序一致性的定义

b) 顺序一致性和线性一致性的区别

c) zookeeper是如何实现顺序一致性的

3.2.4 弱一致性

3.2.5 最终一致性

3.3 可用性

3.4 分区容忍性

3.5 CAP组合

4.Base理论

4.1 Base理论的定义

4.1.1基本可用

4.1.2 软状态

4.1.3 最终一致性

5.拜占庭将军问题

6.引用

1.绪论

本文主要介绍的分布是系统中的一些常见的理论知识，比如CAP理论，BASE理论，拜占庭将军问题等。

2.什么是分布式系统，和集群的区别

分布式系统就是将整个系统根据业务拆分多个微服务，服务之间通过Rpc进行通信。

集群是将多个相同应用部署到不同的集群模式上，本质上是为了提高吞吐量已经保证高可用性。

3.CAP理论

3.1 什么是CAP理论

CAP理论是分布式系统的理论基础,即一个分布式系统最多满足CAP这三项中的两项。即只能满足一致性(Consistance)、可用性（Aviablity）、分区容忍性（Partition tolerance）中的两项。

3.2 一致性

在CAP理论中，一致性指的是，每次读取到的数据一定是当前最新的数据，否者报错。可以看出一致性其实指的是强一致性。

3.2.1 计算机的一致性说明

在计算机中机中有很多地方都会出现一致性这个概念，我们也经常将他们混淆一谈，这里将根据我的经验，来说明不同的一致性表达的含义。

1.事务中的一致性

事务有4个性质，分别是ACID，原子性，一致性，隔离性，持久性。什么是一致性呢？我认为这里的一致性是事务的操作逻辑应该客观事实一致。比如，张三向李四转账50元，张三卡中减少50，李四增加50，钱的总数是不变的。如果张三卡中减少50，而李四卡中余额未变，相当于钱的总数增加50，这是不符合客观事实的。

2.并发场景下的一致性

在并发场景下，由于资源的共享，导致锁竞争，所以可能出现每次请求到结果是不一样的问题，这样就会出现一致性问题。

3.分布式场景下的一致性

分布式场景下的一致性其实是并发场景下的一致性的演变。我们可以想象，分布式场景下，由于有副本的概念，可能因为同步时延问题，或者其他问题，导致不同的副本之间数据是不完全一致的，所以访问不同的节点，会有不同的结果，这也会有一致性问题。

那为什么说这个一致性是并发场景下一致性的演变呢？在JMM里面我们讲到过为什么会有一致性问题，主要原因是java的缓存采用二级缓存的方式，线程A读取本地缓存前，可能线程B更新数据到了共享缓存中，但是线程A读取到的还是老数据。所以这里一致性本质上是解决线程A、B、C的本地缓存之间数据不一致问题。

由于不同副本之间需要网络同步，所以在同一个时刻，不同的客户端访问不同的节点可能得到的数据是不一致的。

可以看出，并发场景下的一致性和分布式系统中的一致性其实都是为了解决同一个时刻多个副本之间数据一致的问题。

3.2.2 一致性分类

我们这里主要介绍的是分布式场景下的一致性问题，这里一致性主要分为强一致性，弱一致性和最终一致性。

3.2.3 强一致性

1.线性一致性

a) 定义

线性一致性是要求最高的一种一致性，他要求无论从哪个副本读取数据，一定读到的是当前整个集群里面最新的数据。其实在并发的一致性中，我们可以常用加悲观锁的方式，使得整个程序像是在单线程中执行一样。

像Paxos、Raft等共识算法其实就实现了线性一致性。

a) Raft算法是如何实现线性一致性的

在讲Raft算法是如何实现一致性之前，我们先来大概了解一下Raft算法接受写请求的原理，其实就是通过二阶段提交来保证数据的一致性。Raft算法详细介绍可以看深度解析RocketMq源码-高可用存储组件（一） raft协议详解

1.主节点接收写请求

2.主节点向所有的从节点发送预写请求

3.从节点返回ack给主节点

4.当主节点收到超过半数的从节点返回ack过后，将数据commit并且应用到状态机中。

5.向所有的从节点发送commit请求，从节点将数据应用到状态机中。

注：这里状态机是什么，Raft算法是一个共识算法，目的是为了让所有节点达成共识，也即可以将客户端接收的数据写入到磁盘中，而写入磁盘这个动作其实就是交给状态机来实现的。状态机其实就是应用Raft算法达到共识过后的逻辑处理。

我们知道，Raft算法的写请求只能交给主节点处理，我们如果要保证线性一致性的话，可以在有写请求到达的时候，将全部节点加锁，此时所有节点不能处理任何请求，当主节点接收请求并且应用到状态机中过后，同时将数据同步给所有的节点都成功(不只是半数以上节点成功)才给客户端返回成功，并且释放锁。这样，后面所有的读请求无论访问哪个节点，数据一定是一样的。但是这样性能太低，所以Raft算法是如何实现的呢？

1.写写顺序性：写请求只能交给主节点处理，并且Raft算法是交给主线程来处理写请求的，这样其实就保证了写写的顺序性。

2.写读顺序性：当读请求来的时候。如果访问的是主节点，主节点首先会判断当的lastApplyIndex和lastCommitIndex是否相等，如果不相等便等待。这里lastApplyIndex表示的是最后的应用状态机的index，lastCommitIndex表示的是最后达成共识的index，因为主节点可能在达成共识过后，就给客户端返回成功，但是还没有将数据应用到状态机，如果此时有读请求到达主节点，会返回老数据；如果访问的的是从节点，从节点首先会发送一个请求获取lastCommitIndex的请求到达主节点，只有当前从节点的lastApplyIndex和主节点的lastCommitIndex相等，才能返回数据，此时一定返回的是最新的数据。

2.顺序一致性

a）顺序一致性的定义

顺序一致性主要满足两点:

1.对于单个线程来说，它的所有操作一定是保证顺序性的；

2.对于多个线程的写操作，需要需要按照时间排列。即所有线程的写操作是放到一个队列中，先到达的写先被读取。

b) 顺序一致性和线性一致性的区别

对于写写的关系，顺序一致性和线性一致性都要求全局有序；对于写读操作，线性一致性要求全局写读有序，但是顺序一致性只要求本线程类写读有序。比如客户端A更新了集群的数据，客户端B来读取数据，如果是线性一致性，一定能够读取到客户端A更新的数据。如果是顺序一致性，客户端B可能读取老数据，但是在过一定的时间后，一定能够读取到A更新的数据。

c) zookeeper是如何实现顺序一致性的

zookeeper是采用自己的zab协议来实现顺序一致性的。就我的理解，zab中的顺序一致性其实只实现了写写的顺序性，没有实现单个客户端之间写读的顺序性。我们来看看zab是如何实现写写的一致性的。

1.和Raft协议一样，zab也是一个单主节点共识算法，所以他会通过选举得到一个主节点，来接收写请求。

2.如果写请求到达的时候，会给每个日志维护一个全局递增的zxid，并且采用二阶段提交的方式将数据同步给从节点。

3.当超过半数以上的节点返回同步成功(ack)响应的时候，主节点会将数据应用到状态机中，并且给从节点发送应用请求。

4.从节点应用数据到状态机。

可以看出zab协议和raft协议的最本质的区别就是否实现线性一致性读(保证写读的顺序性)，这也是线性一致性和顺序一致性最本质的区别。

3.2.4 弱一致性

弱一致性包括因果一致性，会话一致性等子模型，并不常见，这里不再过多叙述。

3.2.5 最终一致性

最终一致性不关心的请求执行的先后顺序，只关心结果正确的就行。比如有A->B->C三个写请求，最终一致性要求无论你先执行A还是B或者C，只要结果正确，便满足最终一致性。而顺序一致性要求执行结果一定是按照请求到达顺序执行的，这也是最终一种性和顺序一致性的区别。

3.3 可用性

在CAP理论中，可用性指的是，每次读取到的数据一定要返回数据，可以是旧数据。

3.4 分区容忍性

分区容忍性就是当某个网络节点宕机或者丢包的情况下，依然能够向外提供服务。

3.5 CAP组合

cap理论中，c和a其实是天然矛盾的两个性质，所以在分布式系统中是不能够共存的。对于单点系统，其实是保证ca两个性质；而对于zookeeper这种，保证的是cp两个性质; 对于redis其实保证的是ap两个性质。

4.Base理论

4.1 Base理论的定义

base理论主要由基本可用、软状态、最终一致性三个性质组成.

4.1.1基本可用

基本可用指的是服务在某些情况下，比如流量突增等情况下，可以对某些边缘服务进行降级，只保证核心服务可用即可。

4.1.2 软状态

软状态指的是运行系统存在中间状态，比如下下单支付两个微服务，下单成功过后不需要立刻进行支付并支付成功，存在一个中间状态-支付中，这个状态就是软状态。在支付中这个状态中，如果我们扣款失败，可以进行重试，直到扣款成功。

4.1.3 最终一致性

最终一致性在前面已经讲过，其实就是不关心中间状态，只需要保证最后的结果达成一致性即可。

5.拜占庭将军问题

拜占庭将军问题描述的是，拜占庭的一队军队需要攻打一个城市，攻打成功需要不同的将军进行系统决策，但是有些将军可能是叛徒，他们可能发出虚假的信息干扰决策，如何让每个将军在不知道哪些将军是叛徒的情况下做出决策。

常见的解决方式就是就是采用少数服从多数的原则，每个将军会对一个指令进行投票，只要超过半数的将军的投票通过，该协议便被达成共识。只要叛徒数不超过一半，那一定能做出正确的决定。

这个解决方案在Raft协议，zab协议中都会用到，Raft协议和zab协议本质上是为了选举出拥有最新日志的节点成为主节点，这就是将军们的决议。所以在选举的时候，只要超过半数节点同意某个节点成为主节点(选举的规则就是备选举节点拥有比超过半数的节点新的日志)，该节点便会升为leader。为了保证叛徒节点不超过半数，Raft协议或者zab协议在同步日志的时候，二阶段提交的时候，要求半数以上节点同步成功日志，才会返回成功，保证了整个集群至少有半数的节点拥有最新日志。