分布式算法笔记

选举

Bully算法

选取存活的节点中id最大的做为主节点。MongoDB就是用的这种算法。 缺点：当故障节点恢复后重新加入集群，会导致切换主节点，可能引起频繁切主。

Raft算法

有3种类型的节点: Leader, Candidate and Follower.

• 初始时，所有节点为follower
• 开始选举时，所有follower升级为candidate
• 一个节点只能投一张票，可以采用随机投票的方法
• 接收到请求的节点回复是否同意成为leader
• 有节点超过一半的投票，则成为leader, 其他节点降为follower
• leader有任期，到期之后要重新选举

k8s内部使用的etcd组件内部，就是用的Raft算法，还有RabbitMQ, TiDB.

缺点：发送消息多

ZAB算法

ZAB 选举算法的核心是“少数服从多数，ID 大的节点优先成为主”.

缺点：由于要对比节点id和数据id, 选举时间长。发送消息多，可能导致广播风暴。

共识

POW(proof of work)

所有节点中，谁的计算能力强，谁就获得记账权。获得之后就广播给其他节点，其他节点接受。

POS(proof of stake)

谁拥有的货币多时间长，谁就拥有记账权。

DPOS(Delegate proof of stake)

某些节点委托别的节点去竞争记账权。

事务

基于XA(xtented architect)协议的刚性事务

一般是数据库要支持XA协议，才能实现2PC, 3PC方法。

二阶段提交

通过一个事务协调器，先发送请求给不同模块做出修改，等收到所有模块都Ok的消息之后，再发送提交事务消息给各模块。

问题：

• 等待太久，阻塞所有的改动
• 事务协调器若故障，则所有模块都锁住资源
• 提交时某个消息丢失了，将会导致最终数据不一致

三阶段提交

分为准备阶段，预提交阶段和提交阶段。

• 准备阶段，协调者向节点发送修改信息，节点回复是否Ok
• 预提交阶段，协调者向节点发送pre commit消息，节点回复ack或abort
• 提交阶段，协调者发送do commit消息，各节点commit之后，向协调者发送ack。或者，协调者发送do abort消息，各节点回滚之后，回复ack

某个地方超时，就会取消

问题：

• 提交时某个消息丢失了，将会导致最终数据不一致

柔性事务

TCC

Try confirm cancel, 在业务系统实现。

所有业务系统都需要实现这个接口的3个方法，需要实现幂等, 超时重试。

SAGA

核心思想：各个本地事务各自完成，如果其中一个失败，通过事件或者命令的方式让其他的模块执行补偿操作(如果需要）。需要有超时重试机制以及幂等的实现。

• 基于事件的方式 可以通过MQ来实现，但是事件的监听一旦多起来，就会很乱

• 基于命令的方式 引用一个单独的协调者模块做命令的分布，某个步骤失败后，先通知协调者，协调者再下发命令给其他模块做补偿操作。

本地消息表

• 事务发起方有一张消息表，本地DB操作与写消息表为同一个本地事务，事务提交后，通过MQ发消息给另外一个服务，对方若成功执行并提交事务，回复消息给发起方，修改消息表的状态。
• 若发起方发给MQ的消息丢掉了，则通过定时任务从消息表轮询未完成的消息进行重试
• 若接受方从MQ获取消息时网络问题丢失了消息，也是通过定时任务从消息表轮询未完成的消息进行重试
• 或接受方处理时中途事务回滚，则需要通过发起方，进行补偿回滚操作。因此发起方需要实现补偿回滚的接口。

MQ最终一致性

这种方案无需本地消息表。目前貌似都是用的RocketMQ. 它支持half message, 只有producer ack了才能被消费者消费该消息。如果该消息一直处于half message状态，则RocketMQ会自动重试，回查该消息，所以消息发送者需要实现消息回查的功能。

或消费端失败，则处理跟本地消息表的处理方法一致。

它跟本地消息不同的是，利用RocketMQ内部实现了本地消息表的功能，缺点是要实现事务回查的功能。

锁

zookeeper实现

有4种节点

• 持久节点
• 持久顺序节点
• 临时节点
• 临时顺序节点

临时节点：客户端可以建立一个临时节点，在会话结束或者会话超时后，ZK 会自动删除该节点。 事件监听：在读取数据时，我们可以同时对节点设置事件监听，当节点数据或结构变化时，ZK 会通知客户端。

curator-recipes封装了很多ZooKeeper的常用功能，可以直接调用来实现分布式锁。

排他锁

所有的客户端试图通过调用 create() 接口，在 /exclusive_lock 节点下创建临时子节点 /exclusive_lock/lock，最终只有一个客户端能创建成功，那么此客户端就获得了分布式锁。同时，所有没有获取到锁的客户端可以在 /exclusive_lock 节点上注册一个子节点变更的 watcher 监听事件，以便重新争取获得锁

共享锁

1、客户端调用 create 方法创建类似定义锁方式的临时顺序节点。 2、客户端调用 getChildren 接口来获取所有已创建的子节点列表。 3、判断是否获得锁，对于读请求如果所有比自己小的子节点都是读请求或者没有比自己序号小的子节点，表明已经成功获取共享锁，同时开始执行度逻辑。对于写请求，如果自己不是序号最小的子节点，那么就进入等待。 4、如果没有获取到共享锁，读请求向比自己序号小的最后一个写请求节点注册 watcher 监听，写请求向比自己序号小的最后一个节点注册watcher 监听。