分布式锁
1.锁的特点
| 名称 | 特点 |
|---|---|
| 互斥的 | 任何时候只能有一个线程持有锁 |
| 可重入 | 如果一个线程持有锁，也不会因为多次获取而死锁 |
| 安全 | 如果一个线程获得了锁，即使崩溃，也必须被释放 |
2.分布式锁
| 名称 | 特点 |
|---|---|
| 高性能 | 因为有很多的服务器来获取，所以需要能够高性能的释放和获取 |
| 高可用 | 不能因为某一个分布式锁获取的服务不可用，就导致所有服务都拿不到或释放锁 |
| 锁失效机制 | 某个应用获取到锁之后，一直没有来释放锁，可能服务本身已经挂掉了，不能一直不释放锁，导致其他服务一直得不到锁 |
| 非阻塞 | 若锁以及被获取了，别的服务不能一直等待 |
常见的分布式锁实现方式
| 方式 | 特点 | 缺点 | 优点 | 解决方案 |
|---|---|---|---|---|
| 基于数据库 | 基于mysql来实现： 1.基于唯一索引实现/行级表：写入方法名/线程名 2.insert ignore,释放的时候delete。和第一种差不多 3.select..for update的排他锁：释放锁用commit |
1.唯一索引缺点: a.没有线程唤醒 b.非常依赖数据库 c.可能导致数据库压力比较大 d.非公平锁，别的只能等待 3.排他锁方案：可能对数据库的并发要求比较高,瓶颈比较严重 |
||
| 基于缓存 | 通过Redis来实现分布式锁，setnx(如果不存在插入，如果存在不插入) lock_key 1，del lock_key（释放） | 长时间可能拿着锁 | 1.配置过期时间，通过监听机制来延长过期时间（看门狗机制） 2.一般配置一个slave，来保证如果主节点不可用的情况。 3.红锁 |
|
| 基于Zookeeper | 获取和释放是差不多的，在zookeeper里会有一个锁节点,在锁的节点下创建临时的顺序节点，若自身是整个节点中最小的节点，那么就可以加锁，否则就一直监听，前面的释放了锁，那么就可以开始拿锁 | 1.依赖性比较强，需要重新加一个环境，比缓存实现比较复杂。2.性能差一点 | 1.可以保证一致性，如果需要100%不出问题，使用zookeeper |
什么是分布式锁，为什么需要分布式锁
随着业务发展，单机环境可能已经扛不住压力了，一般采用的方式是加机器，然后从单机到多机，也产生了很多分布式的问题，我们的服务可能在不同的进程里，也可能在不同的机器里，这个时候需要去解决这个问题。
分布式最大的问题在于多进程，这个时候需要分布式锁
分布式事务
分布式事务是指一个业务流程，跨越了多个分布式系统或服务的事务处理，需要保证多个参与者之间的数据一致性和原子性（电商平台中的付款、支付的数据一致性）
由于网络不靠谱，所以可能产生很多脏数据
两阶段提交协议的基本过程，以及应用 (2PC)
1.上游发起事务，然后事务管理器来去询问别的微服务是否已经准备好了。
2，如果都准备好了，管理器向所有的参与者都发送一个commit命令，如果有一个参与者返回了no，那么管理器向所有参与者都发送回滚命令
优点：
1.能够利用数据库本地的事务来完成提交和回滚
2.
缺点：
1.会造成同步阻塞，可能等待时会导致阻塞
2.如果事务管理器挂了，那么就会出问题
3.协调器发送回滚/提交的命令的时候，可能会网络波动
4.必须等待一整个事务都结束了之后，才会释放资源
2PC协议怎么处理协调者和参与者之间的通信故障
首先，故障无法避免，那么出现了怎么保证一致性和可靠性呢？
1.超时时间，如果参与者响应大于了超时时间，那么就直接回滚
2.心跳机制，定期向参与者发送心跳，如果一段时间没有收到响应，那么认为参与者挂了
3.预备性提交，在第一个阶段，协调者告诉参与者，可以预备提交，如果第二阶段协调者无法收到消息，那么向该参与者发送回滚
4.备份协调器，两个节点
5.采用MQ，来发送消息
3PC协议
通过一个额外的阶段来减少同步阻塞和单点故障
1.在2PC只有协调者才有超市机制，现在都有了
2.分为conCommit（类似准备阶段） preCommit doCommit三个阶段
3.到第三阶段了，参与者还是会去提交，因为很可信了
AT模式
补偿性事务
1.尝试阶段，协调者向所有参与者发送一个参与请求，然后每个参与者先保存数据库的before image,然后修改，之后创建after imgae,然后加上行锁，如果都成功了，那么把这些生成的都删了
2.如果失败了，那么就通过before image和after image来恢复和回滚，最后再删除这些东西
脏写可能需要人工检验
TCC模式
try:
先进行操作
confirm:
如果都confirm了，就成功了
cancel:
有一个没有confirm，那么就取消
仍旧为二阶段的协议，但是具有自我修复的能力的，执行逆操作
需要改造逻辑，开发成本高很多，可以很好的保证一致性
Saga模式
把复杂的事务拆分成小事务
方式
基于事件：产生新事件，然后别的进行监听，回滚需要为服务提供补偿机制
优点：简单容易理解，个个参与方之间无直接沟通，完全解藕
缺点：微服务多了可能导致环形监听。
基于命令：
优点：避免了业务方的环形依赖，可维护，减少了复杂度，不用监听不同服务的类型
共识算法
Raft
什么是Raft,相比于Paxos，Raft最大的特性就是易于理解,且状态简化
共区分为三个问题，分别为
1.领导者选举
2.日志复制
3.安全性
复制状态机
核心思想：相同的初始状态+相同的输入=相同的结束状态
多个节点上，从相同的初始状态，执行相同的一串命令，产生相同的最终状态
在Raft中，leader将客户端请求封装到一个个的log entry中，将这些log entries复制到所有的follower节点，然后大家按相同顺序应用log entries中的command，根据核心思想，那么大家结束状态肯定一一致
状态简化
在任何一个时刻，Raft的每一个服务器节点都处于 leader follower或者candidate这三个状态之一,只需要考虑状态的切换就可以了
Raft把时间分成任意长度的任期，任期用连续的整数标记
每一段任期从一次选举开始，在某些情况下，这一任期会以没有leader（相同票数/都没超过一半）结束，一个新的任期很快会重新开始。Raft保证在任意一个任期内，最多只有一个leader
节点通信
Raft中服务器之间通过 RPC进行通信，且Raft中只有两种主要的RPC
1.请求投票
由candidate在选举期间发起
2.追加条目
由leader发起，用来复制日志和提供一种心跳机制
服务器在通信的时候会交换当前任期号，如果一个服务器的当前任期号比其他的小，那么会把任期号更新为较大的那一个
如果一个candidate或者leader发现自己的任期号过期了，会立即回到follower状态
如果一个节点接收到一个包含过期的任期号的请求，他会直接拒绝这个请求
1.领导者选举
Raft内部有一种心跳机制,如果存在leader，那么他就会周期性地向所有follower发送心跳，来维持自己的地位，如果follower一段时间内没有收到心跳，那么他就会认为系统中没有可用的leader了，那么就开始选举
开始一个选举过程后，follower先增加自己的当前任期号，并转换为candidate状态，然后投票给自己，并且并行的通过RPC给其他节点发送投票请求
对于一个节点来说最终会有三种结果：
1.它获得了超过半数选票赢得了选举 -> 成为主并开始发送心跳
2.其他节点赢得了选举 ->收到新的leader心跳后，如果新leader的任期号不小于自己当前的任期号，那么从candidate->follower
3.一段时间后没有任何获胜者，每个candidate在一个自己的超时时间后增加任期号并开始重新选举
消息如图所示
follower的投票采用先来先得的原则投出选票
2.日志复制
Leader被选举出后，开始为客户端请求提供服务，怎么知道谁是leader呢？
随机向某个节点发送请求：
如果为leader，ok。 如果为follower，那么通过心跳拿leader。 如果宕机了，那么重复
leader接收到客户端的指令后，会把指令作为一个新的条目追加到日志中去
一条日志需要有三个信息
1.状态机指令
2.leader的任期号
3.日志号（日志索引）
leader并行发送追加条目 RPC给follower，让他们复制该条目，当该条目被超过半数的follower复制后，leader就可以在本地执行该指令并把结果返回客户端
把本地提交指令，也就是leader应用日志与状态机这一步，称为提交
只需要超过半数就可以提交(包括leader)
那么如果出问题，Raft怎么样才能让出问题的节点获取到完整的日志呢？
这里有三种情况
1.follower没有响应（慢了）
leader不断地发送追加条目请求，哪怕leader已经回复了客户端（已经提交）
2.follower崩溃后恢复
Raft追加条目的一致性检查(leader发送每个追加条目的时候，会添加上前一个日志的索引位置还有任期号，如果follower在它的日志中找不到前一个日志，那么就拒收，然后leader再发送前一个日志，可以二分优化)生效，保证follower能够按序恢复
3.leader宕机
可能leader上有未提交的日志，对外来说是无所谓的，因为客户端会认为此次失败了，但是leader恢复后会出现问题，因为会发生冲突，老leader收到appendRPC，之后一致性检查出现问题，强制floower复制leader的日志
（没有提交，所以可以丢弃）
这样的日志复制，可以保证
1.只要过半服务器能正常运行，Raft就可以接受，复制并应用新的日志条目
2.在正常条件下，新的日志条目可以在一个RPC来回中被复制给集群中的过半机器
3.耽搁运行慢的follower不会影响整体的性能
追加条目的消息
3.安全性
由于Raft追求易理解性,所以日志是没有空洞的，但是如果leader有问题，你的日志也可能是有问题的，所以Raft通过几个补充规则完善了这个算法
| 类型 | 表现 | 处理方式 |
|---|---|---|
| leader宕机处理：选举限制 | 如果一个follower落后了leader若干条日志(但没有漏任意一个任期)，那么下次选举中，它依旧有可能当选leader，但无法补上，造成状态机的不一致 | 保证被选举出来的leader包括所有的已经提交的日志条目。由request RPC的消息条目实现，由于请求投票的request中最后有candidate的最后一个日志号还有最后一个日志的任期，假设当前follower的日志比candidate要新，那么拒绝投票 |
| leader宕机处理：新leader是否提交之前任期内的日志条目 | 前leader在提交某个日志条目前崩溃了 | 以后的leader会尝试完成该日志条目的”复制”(no 提交),即尝试复制，只有当前任期内的日志条目才通过计算副本数目的方式来提交，然后提交的时候会把之前的日志条目间接地提交 |
| follower和candidate宕机 | 如果follower和candidate都崩溃了，那么后续发送给他们的RequestVote和AppendEntries都会失败，Raft通过无限的重试来处理这种失败，如果崩溃的机器重启了，那么这些RPC就会成功的完成 | |
| 时间和可用性限制 | 平均故障时间>>选举超时时间(10ms-500ms)>>广播时间（0.5-20ms）（由硬件决定） | Raft不依赖客观事件，哪怕因为网络或其他因素，造成后发的RPC先到，也不会影响Raft的正确性 |
Raft的提交：
单点提交(leader 提交)<->集群提交(全部，使用心跳包发送leader commit参数，告诉follower是否能提交)
4.集群成员变更
在需要改变集群配置（增减节点，替换宕机机器）的时候，Raft可以进行配置变更自动化
最大的问题是变更过程中不会出现同一任期的两个leader（脑裂问题：由于原配置可以出现leader，新配置也可以出现leader）
Raft采用一种两阶段的方法：
集群先切换到一个过渡的配置，称为联合一致
1.第一阶段，leader发起$C_{old,new}$使整个集群进入联合一致状态，此时，所有的RPC都要在新旧两个配置中都达到大多数才算成功
2.第二阶段，leader发起$C_{new}$使整个集群进入新配置状态，此时，所有RPC只要在新配置下到达大多数就算成功
一旦某个服务器将该新配置日志条目增加到自己的日志中，他就会用该配置来做出未来所有的决策（服务器总是使用它日志中最新的配置，无论该配置日志是否被提交)大概有以下三种情况
| 情况 | 说明 |
|---|---|
| leader在$C_{old,new}$未提交时宕机 | 不会出现问题，因为需要都满足才行 |
| leader在$C{old,new}$已提交但$C{new}$未发起时宕机 | 已经符合这种情况了 |
| leader在$C_{new}$已发起时宕机 | 也不会有问题，因为没有Cnew的节点选举成功后也会发送Cnew |
Paxos
Basic Paxos
角色
|角色|功能|
|-|-|
|Client|请求发起者|
|Proposer|接受client请求，向集群发起提议，起到冲突调节的作用|
|Acceptor|提议投票和接受者，只有在行程法定人数时，提议才会被最终接受|
|Learner|提议接受者，备份，对集群一致性没有影响|
流程
1.Prepare
Proposer提出一个提案，编号为N,此N大于这个Proposer之前提出的提案编号，请求acceptor的quorum接受
2.Promise
如果N大于此acceptor之前接受的任何提案，则接受，否则拒绝
3.Accept
如果达到了多数派，proposer会发出accept请求，次请求包含提案编号N，以及内容
4.Accepted
如果此acceptor在此期间没有收到任何大于N的提案，则接受此提案内容，否则忽略