分布式笔记(二)paxos协议与chubby
Paxos协议
paxos协议是目前业内使用最广泛的一致性协议。
paxos解决的问题：
将所有的节点都写入同一值，且写入后不再改变
三个参与者： proposer 提出议案， accpetor接受议案， learner 推广议案
paxos保证：
1.只有提出的议案能被选中，没有议案提出就不会被选中
2.多个被提出的议案 只有一个会被选中
3.议案被选中后 就不能变了。
约束条件：
p1:acceptor必须接受他收到的第一个议案
p2:一个议案被选中，需要过半以上的acceptor同意
p3:当编号k0,V0为的提案被半数以上的accptor同意之后，之后的比k0编号更高的议案，其值必须也是V0
p4:只有没有被accptor选中过议案的proposer才能使用自己的value来提交，否则其提交的议案中value的值为
accptor接受过的最大编号的值。
流程：
proposer生成提案（该阶段是proposer产生自己的提案）
proposer需要获取到已经通过的提案，因此在产生一个编号为Mn的提案时，必须要知道当前将要或者已经被半数以上的acceptor批准的 编号小于Mn但为最大编号的提案。 并要求所有acceptor都不要再批准编号小于Mn的提案
步骤
1.proposer选择一个新的提案编号Mn, 然后向Acceptor集合发送，（prepare 请求）然后要收到acceptor的反馈 不再批准比Mn小的提案，且返回小于
Mn但是最大提案的值
2.proposer接收到半数以上的Acceptor的反馈，那么就可以产生提案为(Mn,Vn), 其中Vn的值为acceptor返回的编号仅次于Mn的最大编号的提案值 ，如果半数以上的acceptor都没有批准过任何提案，也就是反馈的提案为空，那么发送自己选择的值Vn (Mn,Vn) （acceptor请求）
这里有proposer会发送两个请求，第一次是prepare请求，第二次是acceptor请求 。
Acceptor批准提案( proposer产生自己的提案之后，会发送给acceptor 期待被批准 )
prepare请求：Acceptor可以在任何情况下响应prepare请求
acceptor请求：Acceptor只有在未批准过比编号Mn还大的议案的情况下 才能批准Mn的acceptor请求
这个算法允许Acceptor忽略任何请求而不影响算法的安全性。
算法优化：
提案编号是全局唯一且递增的 。
优化点在于 如果一个acceptor已经批准过一个编号大于Mn的提案，那么后续的对于编号小于等于Mn的编号 的prepare请求，就可以不做响应。
这样优化的话。acceptor只需记住自己批准过的最大编号的提案和已经做出prepare响应的最大编号即可。
具体流程：
阶段一：
1.proposer选择一个新的提案编号Mn, 然后向Acceptor集合的某个超过半数的子集合发送，编号为Mn的prepare 请求
2. 如果一个acceptor收到一个编号为Mn的prepare请求，且编号Mn大于该Acceptor已经响应过的所有Prepare请求的编号，
那么将已经批准过的最大编号的提案作为响应发送给proposer,同时该acceptor会承诺不会再批准任何编号小于Mn的提案。
阶段二：
1.如果Proposer收到半数以上的accpetor对于其发送的编号为Mn的prepare请求的响应，那么就会发送一个
Mn,Vn的提案的accpt请求给acceptor。 Vn的值就是收到的响应中编号最大的提案的值。 如果响应中没有任何值，
那么Vn就是自己的想发的值。
2.如果acceptor接收到这个Mn,Vn的accpet请求，那么只要acceptor尚未对编号大于Mn的Prepare请求作出响应，那么就可以通过
这个提案。
提案被批准之后，获取过程：
方案一：
learner需要获取的提案是一个 被过半acceptor批准的提案，那么每个acceptor将自己的提案发送给
learner，这样learner就可以知道是哪个提案被选中了。
缺点是 learner不止一个，acceptor也不止一个，那么通信次数就是二者的乘积。
方法二：
所有acceptor将审批结果发送一个主learner ，然后主learner知道被选择的提案之后，同步给其他learner。
通信次数就变为了二者之和。
缺点是，主learner有单点风险，可能会故障。
方法三：
acceptor将审核结果发送给一个learner集合，learner知道审批的方案之后，同步给所有的learner
learner集合的节点越多，可靠性越高。
真实场景下：
如果有多个proposer 可能会出现 多个proposer不断的竞争发送prepare请求进入活锁的情况。
比如说 A发送了m1的prepare请求 ，然后B发送了m2的 prepare请求 ，Acceptor先响应了m1的prepare请求，后面又响应了m2的prepare请求，此时不会再批准比m2小的accept请求，那么A只能再发个m3 的prepare ，如果又被响应，那么m2的accept请求也不会被通过，重复以上 不断循环
实际上会选择一个主proposer ，只有它能发起提案，那么只要主proposer能和acceptor通信，主proposer
发起的编号比较大的提案 就一定会被通过。
总结：
二阶段提交解决了分布式事务的原子性问题（要么全成功，要么全失败）
三阶段提交通过引入precommit阶段解决了二阶段提交 阻塞时间过长 ，通过约定阶段三如果收不到响应，则自动提交事务，如果协调者在阶段三挂了 事务锁定不释放的问题，但是遗留了网络分区下，数据可能不一致问题。
paxos算法 引入了半数投票的规则，少数服从多数，而且节点之间的身份可以轮换，解决了单点 无限期等待 和脑裂的问题，
是目前最好的分布式一致性协议之一。
paxos算法的经典实现有谷歌的chubby ，zookeeper也可以说是chubby的开源版本，出自雅虎，之后可以对比下，会发现
chubby和zookeeper非常相似。
chubby是一个分布式锁服务，面向松耦合的分布式系统的锁服务。
分布式锁的目的是使的在分布式环境下，多个节点能够实现同步。
chubby提供了粗粒度的分布式锁服务，客户端接口设计类似于unix文件系统结构，客户端通过chubby的客户端接口，可以对
chubby的文件系统进行读写，添加对锁节点的控制，订阅chubby的一系列文件变动的事件通知
chubby的应用场景，经典应用就是用于master的选举，或者进行系统运行时元数据的存储。
提供粗粒度的锁服务：
粗粒度是指客户端获取到锁之后，会长时间持有，而非用于短暂获取锁的场景。 在这种场景下，如果chubby集群中提供锁服务的机器短暂失效， chubby需要保持所有锁的持有状态（重新选举新的master节点，恢复状态），避免持有锁的客户端出现问题。
细粒度的锁服务，是设计成一旦锁服务失效，则立刻释放锁，因为细粒度的场景持有锁的时间很短，放弃锁的代价小。
提供锁服务的同时提供对小文件的读写功能：
chubby提供对小文件的读写功能，可以使得客户端竞争锁成功 成为master之后，非常方便的向其他客户端公布自己的信息，
比如说在获取chubby文件锁之后，往这个文件里面写入master信息，其他客户端可以通过读取这个文件得到master的信息。
高可用，高可靠：
部署多台机器，一般是5台组成集群，基于paxos算法实现，只要有3台正常 就能保证对外的服务。
支持成百上千个客户端对同一个小文件的监视和读取，以便于发布master的信息。
提供事件通知机制：
chubby客户端要能知道master的变化，因为客户端轮询在拥有非常多的客户端情况下 对服务器性能和带宽带来的压力都非常大，
因此chubby需要将事件变化通知给客户端。
chubby的技术架构：
一个chubby集群，通知由5台机器组成，然后通过paxos协议 ，选择出一台获得过半票数的master。
一旦master选出来之后，chubby会保证一段时间内 不会有其他服务器成为master，这段时间也叫租期。
运行期间，如果master正常，则会不断的续租。 如果master出现故障，则会重新发起选择， 选出新的matser,开始新的master租期。
集群中每台机器都维护一份数据库的副本，但是只有master能对数据库进行写操作，其他机器通过paxos协议从master同步数据库的更新。
chubby的客户端通过向记录有chubby服务端机器列表的DNS来请求所有的chubby服务器列表，
然后挨个发起询问是否是master, 被询问的机器如果不是master,会将当前master的信息返回，以便客户端更快的获取到master信息。
一旦客户端确定了master,只要master正常运行，那么客户端就会将所有请求都发送到该master服务器上。
针对写请求，chubby 会将该请求通过一致性协议广播给集群中其他副本机器，当一半服务器都接受了该请求的情况下，master才响应这个写请求给客户端。
对于读请求，则不需要在集群内部进行广播处理，直接由master服务器单独处理 。
如果master崩溃了，那么集群中其他机器会在master租期到期之后，重新开启新一轮的master选举，通常一次master选举需要花费几秒。
如果是集群中任意一台非master的机器崩溃了，那么集群是不会停止正常工作的。这台机器恢复之后，会自动加入到
集群中，新加入的服务器首先需要同步最新的数据库数据，同步完成之后才开始进入paxos运行流程与其他副本一起协同工作。
如果一个集群中的服务器崩溃几个小时仍无法正常恢复，那么需要加入新的服务器，并刷新dns列表。
在chubby的运行过程中，master会周期性的轮询DNS列表，发现dns列表发生了变更，就会将集群数据库中的dns列表进行刷新，其他机器对master进行复制同步。
目录和文件：
chubby对外提供了一套与unix文件系统非常相似的访问接口。其数据结构像是一个由文件和目录组成的树，
其中每一个节点都可以表示为一个用斜杠分割的字符串
/ls/foo/wombat/pouch
其中ls是所有chubby节点共有的目录，lock service的缩写，foo则指定了chubby集群的名字 wombat/pouch 则是真正包含业务意义的节点。 ls/集群名/业务服务名
chubby的命名空间，包括文件和目录，也叫节点。
每个节点的数据节点分为持久节点和临时节点
持久节点 需要显式调用Api删除
临时节点会在其对应的客户端会话失效后被自动删除，也就是临时节点的生命周期和客户端会话绑定，当该临时节点没有被
任何客户端打开，就会被删除。因此，临时节点可以用来进行客户端会话有效性的判断。
每个chubby的数据节点都包含了少量的元数据信息，其中包括用于权限控制的访问控制列表（ACL）信息。
同时每个元数据中还包括4个单调递增的64位编号。
1.实例编号 ：标示节点的创建顺序，即使两个节点名称相同，chubby也能通过实例编号知道是哪个
2.文件内容编号： 只针对文件，用于标示文件内容的编号，在文件内容被写入时增加
3.锁编号：用于标示锁的状态变化，该编号会在锁从自由转到持有时 增加。
3.ACL编号: 用于标示权限信息变更情况，当写入ACL信息的时候增加
同时还有一个64位的文件校验码，以便客户端能发现文件是否发生变更。
分布式锁中的问题：
当网络有延迟时候，锁服务器（比如说redis） 误以为之前获取锁的客户端已经掉线了，于是将锁分配给了另一个客户端
然后之前拥有锁的客户端的请求 又过来了。 这样就等于 同时有两个拥有锁的客户端 在进行读写需要同步保护的数据。
解决方案：
1.锁延时，服务端发现客户端断线之后，不立即释放锁，先延迟一段时间再释放锁，可以解决大部分的因为网络延迟的误判
2.锁序列号，需要修改代码，客户端可以在任何时候，向请求服务端一个锁序列器，内容包括全局编号 锁模式 锁名字 ，在需要锁机制保护的操作的时候，再次发送请求，需要向服务器验证这个序列号 ，如果出现网络延时 锁已经被分配给其他客户端的情况，
后面来的请求因为里面的序号和最新的序号不一致，锁服务端可以拒绝这个请求，继而客户端会接收到这个拒绝消息，进行回滚或者其他处理。
chubby中的事件通知：
为了避免大量客户端轮询chubby服务端状态带来的压力，chubby提供了事件通知机制。chubby的客户端可以向
服务端注册事件通知，当触发这些事件的时候，服务端就会向客户端发送对应的事件通知，在chubby的事件
通知中，消息都是异步发送给客户端的。
事件类型如下：
1.文件内容变更
比如说 获取到锁的master机器可以将master信息写入到这个文件，其他服务器通过监听这个文件内容变更，就可以知道是哪台成为了master。
2.节点删除
在chubby上指定节点被删除的时候，会产生节点删除事件，通常在临时节点中常见，可以利用该事件得知客户端会话是否有效。
3.子节点新增，删除
在chubby上指定节点的子节点新增，删除的时候，会产生子节点删除事件。
4.master转移
当chubby的master发生转移时，会以事件的形式通知客户端。
chubby中的缓存
为了提高chubby的性能，减少客户端和服务端中频繁的读压力。
chubby在客户端实现了缓存，会在客户端对文件内容和元数据信息进行缓存。
使用缓存机制在提高性能的同时， 最主要的问题是如何保证缓存一致性，chubby通过租期机制保证缓存一致性。
chubby缓存的生命周期和master租期机制紧密相关，master会维护每个客户端的数据缓存情况，并通过向客户端
发送过期信息的方式使得客户端的缓存失效。 如果客户端的租期到了，会向master发送续租请求延长租期。
当一个文件或者数据被修改时，master首先会阻塞该次操作，然后向所有客户端发送过期消息，只有收到了所有客户端
的响应（响应有两种 1.允许数据过期 2.需要缓存更新） 才允许这次修改操作。
这个机制是强一致性的保证，确保在缓存中，要么读到正确的数据，要么读不到数据，不会出现读到不一致的数据。
会话和会话激活 keepAlive
chubby客户端和服务端之间创建一个TCP连接来进行所有的网络通信操作，这一链接称为会话。
会话是有生命周期的，存在一个超时事件，服务端和客户端通过心跳检测机制来延长会话周期，
保持会话活性，这个过程叫会话激活 keepAlive。
keepAlive 请求
每个客户端向master服务端发送一个keepAlive请求， 服务端会将这个请求阻塞，然后等到客户端的租期快到期了，才进行响应。
默认租期是12秒，但是不是固定的，如果服务端压力大，会适当延长这个租期 以减少keepAlive的次数。
收到响应后，响应的内容有（新的租期时间，缓存是否失效），客户端会继续再发送一个keepAlive请求，然后继续被服务端阻塞。
如果master发现已经发生了缓存过期的通知，那么就会提前返回keepAlive给客户端。
会话超时：
在chubby中，会话的租期分为 客户端会话租期和master服务端会话租期，两者类似，但是不同，因为keepAlive在网络传输需要时间
且客户端和服务端时钟未必完全一致。
当chubby客户端收不到master的keepAlive响应，会进入危险状态，时间是45秒，这个期间会将客户端缓存标志不可用，
如果超过45秒，客户端的状态就变为过期状态，且断开这次链接 终止会话。 如果45秒内又收到服务端的keepAlive响应，就恢复正常状态。
有这个45秒的保证，可以尽量少重启，减少重启带来的影响。
chubby Master 故障恢复：
chubby的master上运行着一个租期管理计时器，用来管理所有会话的生命周期。
如果在运行期间master出现了故障，那么该计时器会停止，直到新的master产生。 旧master崩溃和新master产生之间的时间
不计入租期内，使得会话的生命周期延长。
如果很短时间选举出来了master , 那么会话就能在本地会话租期过期前与其创建链接。
如果master选举时间花了很长时间，那么客户端禁用掉缓存之后，还有45秒可以等待与master进行链接。
这个期间，所有访问客户端API的请求都会被阻塞住，避免访问到不正确的数据。
如果超过了宽限期，客户端就会向上层返回一个异常 并终止会话。
如果在宽限期，客户端和master建立了链接，新的master会设法将上一个Master服务器的内存状态构造出来。
因为本地数据库记录了每个客户端的会话信息， 以及其持有的锁和临时文件等 ，master会通过读取数据库来恢复一部分状态。
步骤如下：
1.新的master产生后，会产生新的master周期，master周期用一个唯一的标示一个chubby集群中 master的统治轮次，
以便区分不同的master。 一旦新的master周期确定下来，master就会拒绝所有携带其他Master周期编号的客户端请求，
同时告知其新的master周期编号。 一旦发生新的master选举，就必定有新的master周期编号，哪怕选的还是之前那台机器。
2.选举出来的master能立刻对客户端的master寻址请求作出响应。 但是不会立刻处理 客户端会话相关的请求状态。
3.master根据本地数据库中存储的会话和锁信息，恢复之前的内存状态。
4.恢复之后，已经可以处理keepAlive请求，但是还无法处理其他会话相关的操作。
5.发送一个master故障切换的事件通知给所有的客户端，客户端收到之后会清空本地缓存 并响应，
当master收到所有客户端响应之后，才会开始处理所有的请求操作
6.如果客户端使用了一个在故障切换之前的创建的句柄，那么master会重新为其创建这个句柄的内存对象，并执行调用，
如果在上个周期已经关闭了，那就不能在这个周期被重建。 这个机制保证 即使master因为网络原因收到了延迟或者重发的
数据包，也不会错误的重建一个已经关闭的句柄。
chubby内的paxos实现：
chubby的结构分为三层：
0.本地文件层：有事务日志和数据快照
- 日志层 最底层， 容错日志系统，通过paxos算法能够保证集群中所有机器上日志完全一致，同时具备比较好的容错性。
- 存储层 中间层，依赖底层容错日志系统实现的key-vlaue类型的容错数据库。依赖底层的容错日志系统保证一致性和容错性。
- 应用层 对外提供分布式锁服务和小文件存储服务
paxos算法作用在于保证集群中各个副本节点的日志能够保持一致。
每一个事务操作（写入或者更新），都由一个paxos instance来发起一个提案，chubby会为paxos instance分配一个全局的
唯一编号，为了避免之前说的每个paxos instance都发起一个提案 导致多个paxos round并存而不断循环的事情，优化算法性能
会选出一个副本节点作为paxos的主节点，这个节点就是master 也就是chubby集群的中master机器，由这个节点进行发布提案。
每个paxos instance 都会经过一轮或者多轮 prepare(proser确认编号)-> promise（accepter 承诺）->propose(proser申请批准)->accept(accepter 批准) ，来完成对一个提案值的选定。
假设chubby集群由5台机器，其中一台被选为master, 该master机器来发布提案
其他副本机器作为剩余的paxos instance 来作为acceter 。 只要半数以上accepter作出accepted批准。（包括Master在内，那么该提案通过)。
过程：
master使用新分配的编号N广播一个prepare消息，该prepare消息会被所有未accepted比N大的编号的提案和还没响应过任何prepare请求的accepter接收到。
各个accepter进行响应，返回自己的曾经审批通过的最大编号的提案值和作出不再审批比N更小的提案的承诺， 如果没有审批过，那么提案值返回null。
发起提案的master接收到响应之后，分别向各个accepter 发送 accept请求，提案的值为 如果收到的提案值为Null 那么就放自己的值。 （一开始 所有的accepter都没有审批过任何提案，所以返回必定为null ）
因为只有一个master节点可以发起提案，那么只要prepare->promise阶段经过之后，就可以不用再次执行这个阶段了，之后有请求
直接发给所有accepter进行accepted，因为没其他节点在发起议案。 但是一旦收到了acceter返回的reject消息 ，说明存在另一台master 并使用了更大的编号，那么此时这台master 就要用更大的编号再次进行prepare->promise过程。
paxos保证在master重启或者故障切换的时候存在多个master共存 不影响副本之间的一致性。（因为paxos本身就允许多个proposer发起提案）
任意节点（被选为learner的集群节点）收到多数accpted反馈之后，说明过半机器都审批了该请求，那么就将提案值写入本地事务日志并广播commit消息给集群中其他副本节点。
任意节点宕机之后，恢复时通过数据快照和事务日志进行恢复，先通过数据快照恢复到某个时间点，然后从那个时间点重放事务日志。 如果宕机之后，丢失了全部磁盘数据，那么就要向其他副本节点索取数据，进行恢复，恢复之后才能加入到paxos instance流程中去。 （加入的时机为k个paxos instance流程都结束之后，k为最大同时允许并发的paxos instance 数量 ）
另一个优化，不需要频繁实时flush数据到磁盘，当宕机之后未来的及flush到磁盘的数据，可以通过其他节点来恢复，提高集群性能。