关键协议：Paxos，2PC，3PC，NWR，Gossip，Raft，Lease，ZAB

看到我的毁灭之锤到货突发灵感

有这么几个酋长

奥酋长，萨酋长，格酋长，加酋长，凯酋长，沃酋长，希酋长

部落不能群龙无首，奥酋长牺牲之后需要选出一个新的大酋长。但是幸存的兽人分散在各地，其中格酋长带领了一帮兽人在打游击，之后萨酋长也带领了一帮起义的奴隶兽人；之后他两汇合了，大家都知道最后是萨酋长担任了大酋长的位置，因为他任期(termId)大,

服务分区，脑裂问题：在Raft规则中,发生网络分区后，每个区都会选举（每次选举任期号都会加1）出一个主节点，等分区结束后会比较每个主节点的任期，以最大的为准同步他的数据。（如果任期比不出来，还会继续投票）

当年萨大酋长退位，加酋长很快就继任了，为什么继任的不是凯酋长或者沃酋长，因为Lease（租约）机制

Lease机制：萨大酋长退位成为了元老（中心节点），Lease机制中主节点需要拿到他（中心节点）的授权，萨酋长授权加酋长出任大酋长之位，期限是搞垮部落为止（一般租约是1-10s）。

之后凯酋长被加大酋长击杀下线，但是萨元老为什么没收回授权呢？因为他断开和部落的连接了（拯救世界还是更重要），虽然没有挂掉，但是无法和其他节点交互。

中心节点集群：要解决这种事也简单，就是弄个元老院，多来几个元老，他们总不可能一起断开吧。

加大酋长最终被群殴强制下线（40个访问量就顶不住了）；

服务限流：是分布式中很重要的一点，常见算法有窗口算法（一段时间内限制多少个访问数；加大酋长1分钟只能砍10个脚男）；漏桶算法（服务端匀速处理，好处是保证服务正常运行；脚男在加大酋长门口排队，砍完一个进一个）；令牌桶算法（以恒定的速度向桶里放令牌，进来请求先找令牌，有令牌继续，没令牌拒绝，好处是可以应对突发流量；直接变澡堂了）

沃酋长继任大酋长之位，沃酋长虽然没有什么出彩的表现，但是贵在稳定，萨酋长时期加入部落，一起打天下，从War3时期一直就在运行；

master（有的也叫leader）主节点选举：

1.Raft规则选举：主节点会向从节点不停的发心跳包，每个从节点有一个随机的反应时间（150ms~300ms），当超过反应时间还没有收到主节点的心跳包，那它就成为候选节点，要开始竞选了（一般最先开始竞选的最有优势）；首先发送投票请求给其他节点，如果超过一半的节点回复了那它就成为了主节点；如果两个候选节点同时开始竞选，并且票数相同，那么他们会重新随机反应时间，然后再来一遍。

2.Zookeeper的master选举：这就是一个抢锁的过程，集群每天都会向/master_election/2021-12-12（当天日期）下创建/binding 临时节点（名字可以自己设置），这个是唯一的，所以只有一个机器可以创建成功，创建成功的那个就是master；其他创建失败的就会在/binding下创建子节点来 Watcher监听主节点的状态（zookeeper的机制），master挂掉，其他的机器就开始重复之前的操作。方式简单粗暴，一般用来做分布式id这种活。

3.Zookeeper的leader（ZAB协议）选举：每个zookeeper都有两个id，一个myid（自己写在配置文件中，必定不同），一个ZXID（类似任期号；递增的事务编号，越大的说明数据越新），ZXID较大的优先，如果一样myid较大的优先。

ZAB协议中除了主节点，从节点，还有观察者节点，它不参与选举，其他功能和从节点一样。

最后沃大酋长在破碎海岸被刀刺穿，为什么一起的希酋长，小凯酋长都没事；因为只有主节点可以输入（这也是部落酋长的机制，凯酋长是个意外），从节点只能输出。

主从节点分工：

主节点可以做读写，写操作时发起事务控制；

从节点只读，收到写操作会转发给主节点，还有投票；

观察者节点只读，收到写操作会转发给主节点，不投票；

这是因为分布式事务的原因，主节点事务请求的唯⼀调度和处理者，保证集群事务处理的顺序性。

沃大酋长回城没多久就死了，由希酋长继位。再后面就没玩了。

总结

Paxos，2PC，3PC，NWR，Gossip这5个还没提到。

Paxos协议

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。多数派原则。

Paxos的三个角色

Proposer：提议者，提出方案的角色

Acceptor：接受者，接收方案的角色

Learner：学习者，充当该协议的复制因素(不参与投票)；有点像ZAB的观察者。

4个步骤

1.Proposer提出一个提案,编号为N, 此N大于这个Proposer之前提出所有提出的编号, 请求Accpetor的多数人接受这个提案

2.如果编号N大于此Accpetor之前接收的任提案编号则接收, 否则拒绝

3.如果达到多数派, Proposer会发出accept请求, 此请求包含提案编号和对应的内容

4.如果此Accpetor在此期间没有接受到任何大于N的提案,则接收此提案内容, 否则忽略

2PC（2段提交），3PC（3段提交）

2段提交，先询问接收到所有反馈；再提交，接收事务提交结果。

3段提交，先询问收到所有反馈；再准备提交，收到所有反馈；再提交，接收事务提交结果（进入第三阶段如果超时，所有参与者也会进行提交）。

NWR协议

比如亚马逊云储存系统

N：有多少备份

W：代表一次成功的更新操作要求至少有w份数据写入成功

R：代表一次成功的读数据操作要求至少有R份数据成功读取

N<W+R是强一致性

Gossip协议（流行病协议）

去中心化传播

反熵传播：无限制。可以保证最终完全一致，消息数量非常庞大。

谣言传播：一段时间会俞除，停止传播。一定概率会不一致。

传播之后更新版本号。

适合于 AP 场景的数据一致性处理，常见应用有：P2P 网络通信、Redis Cluster、Consul。

问题思考

1.主从的读写分离在高并发下怎么确保能读到最新数据？

如果从库没有更新到数据就被读了,造成数据错误,大量数据写入时间太久，造成延迟。

我先自己猜一下：本着计算机系统的运行原理，先更新一块内存，然后将引用转到更新的这块内存。

是不是数据同步到时候也可以，先更新一部分服务器，然后开放这部分服务器访问，再逐步完成所有同步。

再查查网上的解决方案：

半同步复制：介于异步复制和全同步复制之间，主库在执行完客户端提交的事务后不是立刻返回给客户端，而是等待从库接收到并写到relay log中才返回给客户端（等待多少ACK？应该可以设置）。半同步复制提高了数据的安全性；

并行复制：更新同步可以一起执行。

上面两个只是解决了安全性和同步效率，但是哪些从库是最新数据？还是不知道

NWR协议好像可以解决这个问题。读几个服务器的数据然后取最新版本。

或许可以在接收到relay log时给从节点加上一个更新中标识，禁止读，commit成功后再去掉。

2.分布式事务到底怎么做？

假如按功能分表后，有两个表分别在不同的服务器，但是他们又要做事务处理，应该怎么办？

正常在一个数据库中是所有修改都预提交，然后一起commit。

2PC还是3PC都是有出错几率的，出错了怎么办？

可以使用缓存数据库：先将数据保存在缓存数据库，再分别向要插入的数据库执行插入操作，直到返回成功或超过重试次数。

2PC 和 3PC有点类似君子协议；问你有没有偷东西？你说没偷！他就当你没偷，也不会搜身检查。

还有哪些实现方案？

2PC 和 3PC 都不能保证数据100%一致，因此一般都需要有定时扫描补偿机制。它们最大的区别是在第二段超时会回滚，第3段超时会继续提交。

先设想一个方案，MySql回滚是依靠undo log，而事务所有id的；是否可以让所有MySql共享事务id，这样就可以根据统一的事物id进行回滚。

本地消息表：先保证本地插入成功，但是状态不写，等下一个操作成功了才改成成功。未成功的会有重试次数，超过次数报人工处理。

消息事务：思路类似，通过中间件消息队列；本地提交时把消息提交到消息队列；然后消费方去队列拿，消费方提交后再发送消息去队列；本地会定期去消息队列查询消费方发送的消息，来确认是否回滚。（感觉复杂度提高了，但是还没上一个稳，但是对于很多服务器来说，会方便一点）

3.分布式锁有哪些？

看名字的意思就A服务器可以锁B服务器；

实现思路就是在一个大家都能访问到的地方，创建一个锁，谁获取了，就可以执行工作；

比如在MySql中建个表；字段为：锁id，状态，使用者id，使用时间。大家执行这个工作的时候都要去取锁A，谁先修改表成功，谁就取到了锁。

还有用唯一键做插入的方式，有点像下面的ZooKeeper分布式锁。

还可以用ZooKeeper：上面提到的Zookeeper的master选举就是一种分布式锁的实现。规定同一个目录下只能有一个唯一文件名。

Redis://todo