分布式算法复习

CAP理论：

Consistency一致性：访问每个节点都返回一致的数据

Availability可用性：每个访问一定会响应

Partition Tolerance分区容忍性：集群被分区仍能正常提供服务

二阶段提交：

一阶段通知各事务节点预留资源

二级段通知各事务节点执行事务

XA：mysql表直接上锁

AT：自定义全局锁

TCC：预留+确认+撤销【可用于非关系型数据库+且必须是可预留资源】

SATA：补偿业务

流量过大的处理：

流量削峰，延迟响应，体验降级，过载保护

Poxos：

准备阶段：提议者向所有接受者提出准备请求（携带提案编号x），接受者响应则表达承诺以后不再响应提案编号小于或等于x的做准备请求，也不会通过编号小于x的提案，不响应则表示已经响应了提案编号比x大的提案

接受阶段：提议者收到过半接受者对准备请求的响应后，将发出接受请求，接受者接收到接受请求后，如果不违背已作出的承诺就会响应并执行（记录日志），反之不响应

【问题：当有三个提议者时，可能三个提议各占三分之一的接受者，此时全部提议无效】

【问题：编号本质是优先级，没有顺序性（其实应该改用时间戳）】

Multi-Paxos：

只有领导者一个提议点时，不会有提案冲突

当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段

Chubby还为了实现强一致性，读操作也只在主节点上进行

Raft：

跟随者：随机超时（刚开始启动时或已有领导者断线时）——参与竞争（任期+1）——投票

候选人：发起投票——收到过半选票——发表宣言

领导者：定时心跳（含最大日志序号+任期）+日志复制（日志是连续的且顺序提交的，写操作时过半成功持久化时响应，剩下的即合没有成功也能用日志慢慢补，心跳时有最大日志序号）

如果接收到任期比自己任期大，且其日志序号大于自己的领导者心跳或新领导者投票，则自己变成跟随者

【成员变更时：单节点变更，即如果要加两个节点，则领导者要在先知道第一个新节点后，才能再加第二个节点】

读操作时，有三种方法：

一是AC：只允许读主节点（相当于没有P，肯定AC）

二是AP：模式任意节点只要存在这个信息就返回

三是CP：模板要得到过半节点的相同信息才返回（例如有2k+1个节点，读取时要有k+1个相同的信息才返回，或者取K+1个信息中最新者）

BASE理论：

Basically Available基本可用

Eventually Consistent最终一致性

Soft State软状态

一致性哈希算法：

对2^32进行取模，对三个节点映射到哈希环上（可以有虚拟节点），每次增删节点都，只有小部分KV要迁移

Gossip：

直接邮寄：传送失败时记在缓存队列中，当OOM时会丢失数据

反熵：推，拉，推拉三种方法，即每个节点都随机往另一个节点进行推，拉或推拉

谣言传播：对所有节点设计一个闭环的过程（例如编号1，2，3，到n，再回到1这样，一次修改所有节点的副本数据不一致的问题）

Quorum NWR：

N表示集群中同一份数据有多少个副本

W表示W个副本更新成功才完成写操作

R表示读取一数据对象时需要读取R个副本并取最新的那个

当N<W+R时，有强一致性