分布式系统的一些基础理论
前言
在一年前我曾经有做过一些 Zookeeper 的相关总结，现在我们再把它捡回来，重新的把一些前因后果都扯得更加明白。
以往链接
从零开始的高并发（一）--- Zookeeper的基础概念
从零开始的高并发（二）--- Zookeeper实现分布式锁
从零开始的高并发（三）--- Zookeeper集群的搭建和leader选举
从零开始的高并发（四）--- Zookeeper的分布式队列
从零开始的高并发（五）--- Zookeeper的配置中心应用
从零开始的高并发（六）--- Zookeeper的Master选举及官网小览
一、分布式系统与 Zookeeper 的关系
1.1 集中式服务
我们先从服务部署架构的发展历程说起，其实无非就是 集中式 和 分布式 ，集中式就是说，什么我都是由一台机器搞定的。分布式就是多台服务器联合完成。所以在一开始的时候一般都是从一台服务器开始，将我们的服务部署上去，然后就是一些老套路，Web 应用就部署在 Tomcat 上开放 8080 端口提供服务，然后它需要的一个数据库服务就开放 3306 端口提供。它的优点就在于结构，部署，项目架构都比较简单。
然后再根据业务的发展去扩展，那扩展同样也可以分为两种方式，一种是横向扩展，一种为纵向扩展。既然一台搞不定，那就要不提升这个服务器的性能，要不就整多几台一起上。但是我们想想，也不是个人就会把服务器安排的服服帖帖的呀，这台机子一挂，那就全挂了。而且大型主机的购买，还有研发，维护人才，那都是得花大价钱的。这里给大家扩展一个 “摩尔定律”
反正简单点来说，就是我花两倍的钱，根本买不到两倍的性能。但是横向扩展就不一样了，一个人打不过，叫多几个人一起打不就行了？
1.2 去 IOE 运动
阿里巴巴搞出来的一个口号，具体点就是 IBM小型机，Oracle数据库，EMC的高端存储，有兴趣的也可以了解一下。因为当时面临的问题是，企业如果需要提升单机处理能力，成本会很高且性价比极低。还整天怕这怕那的，一宕机就整个服务停掉。慢慢的国内很多公司跟着一起响应，分布式就起来了。
1.3 分布式服务
分布式系统有着它具体的定义：分布式系统是一个硬件或者软件组件分布在不同的网络计算机上，彼此之间仅通过消息传递进行通信和协调的系统。所以就是一堆计算机联合起来对外提供服务，但是对于用户来说，像是一台机子在完成这事。
特点很多，大致就是下面5个：
分布：这个就是多台计算机都被放置在了不同的位置
对等：集群中的多个工作节点都是一个货色，干的都一样的活儿。而且存在副本概念
并发：多个机器同时操作一份数据可能会引发的数据不一致问题
全局时钟：多个主机上的事件先后顺序会对结果产生影响，这也是分布式场景中非常复杂的一个问题
各种故障：某节点宕机，网络不好···突发情况
1.4 分布式场景中经常遇到的几个问题
通信异常：其实就是网络问题，导致多节点状态下数据不一致
网络孤立：这个其实就是各个子网络内部正常，但是整个系统的网络是不正常的。导致局部数据不一致的问题
节点宕机问题
分布式三态：成功，失败，超时这3种状态引出的各个问题。请求发送和结果响应都有可能丢失，无法确定消息是否发送/处理成功
数据丢失：这个一般通过副本机制，从其它节点读取解决，或者对于有状态的节点来说丢失数据就可以通过恢复状态来解决。
异常处理原则：任何在设计阶段考虑到的异常情况都必须假设一定会在实际运行中发生
1.5 衡量分布式系统的性能标准
性能：主要就是吞吐能力，响应延迟，并发能力。系统某一时间可以处理的数据总量，通常是用系统每秒处理的总数据量衡量，而响应延迟指的是完成某一功能所需要的的时间。并发能力就是同时完成某一功能的能力，通常就是用 QPS 衡量
可用性：在面对各种异常时可以正确提供服务的能力。比如我们常说的 5个9 就是指一年内只有5分钟的宕机时间。6个9 就是 31 秒
可扩展性：指可以通过扩大机器规模达到提高系统性能的效果
一致性：副本管理
但是这些标准都是一个方面要求太高之后会带动另外一方面变差，比如说我们需要做到高可用，可能需要多个副本，但是多个副本的状态下，对于数据的一致性又很难去做到了。然后高吞吐下又很难做到低延迟，所以我们需要针对自己的业务场景去进行考量。
1.6 对于一致性的扩展
强一致性：写操作完成之后，读操作一定能读到最新数据，在分布式场景中这样是非常难实现的，比如 Paxos算法，Quorum机制，ZAB协议都是干这个事的。
弱一致性：不承诺可以立即读到写入的值，也不承诺多久之后数据能够达到一致，但会尽可能的保证到某个时间级别（比如XX时，XX分，XX秒后），数据可达到一致性状态。
它还有一个特例叫做最终一致性，就是尽可能快的保证数据的一致。但是这个快到底是多快，就没有准确定义了。好比女票想要吃到炸鸡，你给点了份外卖，可是美团骑手，饿了吗骑手也说不准什么时候送到，他只能说保证尽快送到。就这么个意思。
因为最终一致性实在是太弱了所以我们还有一些特例情况会出现读写一致性，它是指用户读取自己写入的结果永远可以第一时间看到自己更新的内容，这个就像微信朋友圈一样的，我们发出来的东西，微信是一定会让我们看到的，可是朋友们是不是你发了立刻就能看到，那可就说不准了👀。
还有一些单调读一致性，因果一致性就不展开说明了，有兴趣的小伙伴可以自行搜索。
总而言之，为了保证系统的高可用，防止单点故障引发的问题，并能够让分布在不同节点上的副本都能正常为用户提供服务，这时，我们的 Zookeeper 就应运而生了。它就能帮助我们解决这个分布式系统中数据一致性的问题
需要解决这个问题我们需要了解分布式事务，分布式一致性算法，Quorum 机制，CAP 和 BASE 理论，接下来我们慢慢去展开
二、分布式事务
事务：单机存储系统中用来保证存储系统的数据状态一致性，这是不是读起来有点拗口，没事，我们换个说法，广义上的事务，就是指一个事情的所有操作，要不全部成功，要不全部失败，没有中间状态。狭义一点，那就是数据库做的那些操作。特征也很简单，就是耳熟能详的 ACID 。
分布式系统中每个节点都仅仅知道自己的操作是否成功，但是不知道其它节点是个啥情况，这就有可能导致各节点的状态可能是不一致的，所以为了实现跨越多节点且保证事务的 ACID 时，需要引入一个协调者，然后参与事务的各个节点都叫做参与者
典型的套路就是 2PC 和 3PC，接下来我们慢慢展开
2.1 2PC是个什么东西
在事务的参与过程中会产生多个角色，暂时我们先这么理解，协调者负责事务的发起，而参与者负责执行事务。
假定存在上面的3个角色，分别是一个协调和两个参与，此时我们需要 A ，B 执行一个事务，并且要求这个事务，要么同时成功，要么同时失败。
2PC 阶段一：执行事务
此时协调者会 先发出一个命令，要求参与者A，参与者B都都去执行这个事务，但是不提交
说的再详细一点，就会产生写 redo，undo 的日志，锁定资源，执行事务。但是执行完了之后，直接向协调者打报告，询问一下，大哥我能提交吗？
这个在日常写Java的过程中应该经常遇到，就是前面写了一大堆操作，但是等到最后一定会写一个 conn.commit() 这样的东西，这就是所谓的 执行但不提交
2PC 阶段二：提交事务
当协调者收到第一阶段中的所有事务参与者（图中的A，B）的反馈（这个反馈简单理解为，告诉协调者前面的第一阶段执行成功了）时，就发送命令让所有参与者提交事务。
如果要说的再细一点，那就是协调者收到反馈，且所有参与者均响应可以提交，则通知参与者进行 commit，否则 rollback
所以 2PC 也叫做二阶段提交，其实就是这么简单分成了两步，一步执行，一步提交。
2PC 的4个缺点：性能
整个流程看下来就知道这明显产生了同步阻塞，各个需要操作数据库的节点都占用了数据库的资源。只有当协调者收到所有节点都准备完毕的反馈，事务协调者才会通知 commit or rollback，而参与者执行完这个 commit or rollback 的操作后，才会去释放资源。
2PC 的4个缺点：单点故障
那我们刚刚也知道了，协调者才是这个事务的核心。假如此时协调者故障宕机，会导致通知无法传达到参与者的问题，比如收不到那个 commit or rollback ，整一个事务便会停滞。
2PC 的4个缺点：数据不一致
协调者在第二阶段会发送 commit or rollback。可是这并不能保证每一个节点都正常收到这个命令，所以会可能窜在，参与者A收到了命令，提交了事务，但是参与者B没有。所以网络波动是永恒的病因，你永远无法躲开这个因素。
2PC 的4个缺点：不存在容错机制
这个协调者需要收到所有的节点反馈准备完成才会下达 commit 的指示，任意一个参与者的响应没有收到，协调者就会进行等待，而且只要存在一个宕机的节点，都会使得整个事务失败回滚。
2.2 3PC 是个啥东西
在 2PC 的前提下进行了一个改良，将 2PC 中的准备阶段进行拆分，形成 can commit，pre commit，do commit 三个阶段。
并且引入超时机制，一旦事务参与者在指定时间内没有收到协调者的 commit or rollback 指令，就会自动进行本地 commit，解决协调者的单点故障问题
3PC 第一阶段 cancommit
协调者先询问：哎你们这帮人到底能不能行？参与者就根据自身的实际情况回答yes or no。
3PC 第二阶段 precommit
如果参与者都是返回同意，协调者则向所有参与者发送预提交请求，并进入准备阶段，这里的准备阶段其实就是让参与者锁定资源，等待指令的意思，然后就是事务的执行，此时也像 2PC 一样，执行但不提交。然后等待协调者的指令，此时如果迟迟等不到指令，一段时间后就会自行本地提交
但是这样也会存在弊端，比如协调者成功给1，2参与者都发送回滚，然后3刚好就没收到，那么3就自动提交了，所以超时机制其实并不能完全保证数据的一致性
三、分布式一致性算法
3.1 Paxos 算法
不知道大家有没有看到我上一年的那篇 从零开始的高并发（三）--- Zookeeper集群的搭建和leader选举 如果需要详细了解，推荐跳转到那篇哦。
Paxos 算法是一个名字叫 Lesile Lamport 提出的一种基于消息传递且具有高度容错特性的一致性算法
是不是觉得绕口？没事，我们只需要知道，分布式系统中不可避免的会发生进程被kill，消息延迟，重复，丢失···一系列问题，Paxos 算法就是在这些异常情况下的仍然保证数据一致性的东西。那这东西和 Zookeeper 有啥关系呢？Zookeeper 是存在一个 ZAB 协议的，但是这个 ZAB 协议底层就是封装了 Paxos 算法的。
3.2 Paxos 中存在的角色及与 Zookeeper 集群的关系
Proposer 提议者：顾名思义就是发起提案的人
Acceptor 接受者：它们是可以表决的，可以接受或者否决提案
Learner 学习者：提案被超过半数的 Acceptor 接受的话，就学习这个提案
映射到 Zookeeper 集群中，就分别是 leader，follower，observer，它们有点像是主席，人大代表，和全国老百姓的关系，主席提出一个提案，人大代表参与投票，全国老百姓被动接受😂，大概就是这么个感觉。相比于之前的 2PC，3PC，它只需要半数通过即可提交。所以这种属于弱一致性，2PC，3PC这些就属于强一致性
3.3 Raft 算法
请点击这个链接，相信你一定能够很快掌握。http://thesecretlivesofdata.com/raft/ 我这里还是小小的说明一下吧，这个是一个PPT的形式，告诉你，Raft 到底是个什么东西，非常好懂，我这里跳过前面的一些东西，直奔主题
这里说到了，Raft 是实现分布式共识算法的一个协议
这里假设一个节点有3种不同的状态
第一种，follower state（无线条）
第二种，candidate state（虚线）
第三种，leader state（实线） 记住leader是从 candidate 候选人那里选出来的
首先我们一上来，所有的节点都是 follower state
接下来，所有的 follower 节点都寻找 leader ，当他们找不到的时候，就会自发成为候选人发起投票（问其它人是否赞成我成为 leader），什么情况才会找不到呢？那肯定就是 leader 挂了嘛😂
此时它就发送给其它节点投票的提案，然后其它节点也会给予它反馈，当它接收到超过半数的节点的反馈的时候，它就可以顺理成章的成为 leader 了。
之后写数据的请求就会直接发给leader，由 leader 广播给其它的 follower，此时也是只要超过半数节点返回正反馈，那这个写数据的事务就会被执行，然后 leader 再给它们发送提交命令，事务就算执行成功了。
3.4 ZAB 协议
内容在 从零开始的高并发（四）--- Zookeeper的分布式队列
Zookeeper 的底层实现就是 ZAB 协议，它实现了崩溃恢复（leader崩溃）和消息广播（客户端写数据Zookeeper要保证多节点都成功写入）功能。主要就是保证在leader服务器上提交的事务最终让所有服务器都提交，并确保丢弃掉只在leader服务器上所提出的事务
3.5 Quorum NWR 机制
Quorum NWR：Quorum 机制是分布式场景中常用的，用来保证数据安全，并且在分布式环境中实现最终一致性的投票算法。这种算法的主要原理来源于鸽巢原理。它最大的优势，既能实现强一致性，而且还能自定义一致性级别。
鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理。
其中一种简单的表述法为：
若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。
另一种为：若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。
为什么从抽屉原理说起？一来大家对这个比较熟悉，也容易理解，二来它与 Quorum 机制有异曲同工的地方。抽屉原理，2个抽屉每个抽屉最多容纳2个苹果，现在有3个苹果无论怎么放，其中的一个抽屉里面肯定会有2个苹果。那么我们把抽屉原理变变型，2个抽屉一个放了2个红苹果，另一个放了2个青苹果，我们取出3个苹果，无论怎么取至少有1个是红苹果，这个理解起来也很简单。我们把红苹果看成更新了的有效数据，青苹果看成未更新的无效数据。便可以看出来，不需要更新全部数据（并非全部是红苹果）我们就可以得到有效数据，当然我们需要读取多个副本（取出多个苹果）。
回到 Quorum NWR 机制 的 NWR 到底指什么
N：复制的节点数，即一份数据被保存的副本数。
W：写操作成功的节点数，即每次数据写入写成功的副本数。W 肯定是小于等于 N 的。
R：读操作获取最新版本数据所需的最小节点数，即每次读取成功至少需要读取的副本数。
总结：这三个因素决定了可用性，一致性 和 分区容错性。只要保证（W + R > N）就一定能读取到最新的数据，数据一致性级别完全可以根据读写副本数的约束来达到强一致性！
分以下三种情况讨论：前提，当 N 已经固定了。
W = 1, R = N，Write Once Read All在分布式环境中，写一份，那么如果要读取到最新数据，就必须要读取所有节点，然后取最新版本的值了。写操作高效，但是读操作效率低。一致性高，分区容错性差，可用性低
R = 1, W = N, Read Only Write All在分布式环境中，所有节点都同步完毕，才能读取，所以只要读取任意一个节点就可以读取到最新数据。读操作高效，但是写操作效率低。分区容错性好，一致性差，实现难度更高，可用性高
W = Q, R = Q where Q = N/2 + 1可以简单理解为写超过一半节点，那么读也超过一半节点，取得读写性能平衡。一般应用适用，读写性能之间取得平衡。如 N=3, W=2, R=2，分区容错性，可用性，一致性取得一个平衡。而 ZooKeeper 就是这么去设计的
需要补充的是，Zookeeper 并没有实现必须要客户端读取超过半数的节点，所以它是允许客户端读取到的不是最新同步完成的数据的，但是可能性比较小。数据没有同步完成的节点其实客户端也大概率是连接不上的，因为无论是网络问题还是机器问题导致 leader 发送数据过去它做不了的话，客户端肯定也连不上它。要是刚好就是在同步数据的中间状态客户端发起了访问的话，也是有办法解决的，可以自己了解一下。
3.6 CAP 理论
CAP 理论：2000 年 7 月份被首次提出，CAP 理论告诉我们，一个分布式系统不可能同时满足 C,A,P 三个需求
C：Consistency，强一致性，分布式环境中多个数据副本保持一致
A：Availability，高可用性，系统提供的服务必须一直处于可用，对于用户的每一个操作请求总是能在有限时间内返回结果
P：Partition Tolerance 分区容错性，分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务
既然一个分布式系统不能同时满足 C,A,P 三个需求，我们就要就我们的需求去取舍了。
放弃 P：最简单的极端做法，就是放置在一个节点上，也就只有一个数据副本，所有读写操作就集中在一台服务器上，有单点故障问题。放弃 P 也就意味着放弃了系统的可扩展性，所以分布式系统一般来说，都会保证 P
放弃 A：一旦系统遇到网络分区或者其他故障时，服务需要等待一段时间，在等待时间内就无法正常对外提供服务，即服务不可用
放弃 C：事实上，放弃一致性是指放弃数据的强一致性，而保留最终一致性，具体多久达到数据同步取决于存储系统的设计
CAP 只能3选2，因为在分布式系统中，容错性P肯定是必须有的，所以这时候无非就两种情况，网络问题导致要么错误返回，要么阻塞等待，前者牺牲了一致性，后者牺牲了可用性。举个例子，比如 HBase 就是追求数据的一致性的，而 Cassandra 则是可用性。
经验总结：
1、不要花费精力浪费在设计同时满足CAP的分布式系统
2、分区容错性往往是分布式系统必然要面对和解决的问题。所以应该把精力放在如何根据业务特点在A和C之间寻求平衡。
3、对于单机软件，因为不用考虑P，所以肯定是 CA 型，比如 MySQL
4、对于分布式软件，因为一定会考虑P，所以又不能兼顾A和C的情况下，只能在A和C做权衡，
比如 HBase, Redis 等。做到服务基本可用，并且数据最终一致即可。
所以，就产生了 BASE 理论。
3.7 BASE 理论
多数情况下，其实我们也并非一定要求强一致性，部分业务可以容忍一定程度的延迟一致，所以为了兼顾效率，发展出来了最终一致性理论 BASE，来自 ebay 的架构师提出。BASE理论全称：全称：Basically Available(基本可用)，Soft state（软状态）,和 Eventually consistent（最终一致性）三个 短语的缩写。核心思想是：即使无法做到强一致性，但每个应用都可 以根据自身业务特点，采用适当的方式来使系统达到最终一致性。一句话概括，做事别走极端，BASE 是对 CAP 理论中的 C 和 A 进行权衡得到的结果。
不是强一致，而是最终一致。不是高可用，而是基本可用。
Basically Available（基本可用）：基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用
例如淘宝双11，为保护系统稳定性，正常下单，其他边缘服务可暂时不可用。部分非核心服务宕机此时是允许的。
Soft State（软状态）：软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。通俗的讲：允许存在不同节点同步数据时出现延迟，且出现数据同步延迟时存在的中间状态也不会影响系统的整体性能
Eventually Consistent（最终一致）：最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况，要求最终达到一致，而不是实时强一致
Finally
总的来说，我们提到了集中式 和 分布式服务部署架构的分析，设计分布式系统会遇到的各种难题：数据一致性的问题
2PC 和 3PC是通用的思路实现，还是有缺点。Paxos Raft ZAB 就算出现了分布式网络通信异常等相关棘手的问题，以上这些算法也能实现一致性
议会制 Quorum NWR机制：R + W > N ===> 少数服从多数
一致性 和 可用性的冲突问题，CAP 和 BASE：分布式系统一定要满足 P，只能在 C 和 A 中做权衡
绝大部分系统都是 BASE 系统（基本可用 + 最终一致）