# Theory

## Mutual Exclusion

同一时刻只有一个程序能访问一个资源，这种排他性的资源访问方式叫做分布式互斥（Distributed Mutual Exclusion），共享资源叫做临界资源（Critical Resource）。

### 集中式算法

**思想**：引入一个协调者程序，每次需要访问临界资源时需要向协调者发送请求，协调者根据先后顺序发送授权消息。

**特点**：简单、易于实现的特点，但可用性、性能易受协调者影响。

### 分布式算法

**思想**：使用组播和逻辑时钟，程序需要使用临界资源时向其它所有节点发送请求，其它节点根据请求时间响应是否授权。

**特点**：“先到先得”和“投票全票通过”的公平访问机制，但通信成本较高，可用性也比集中式算法低，适用于临界资源使用频度较低，且系统规模较小的场景。

### 令牌环算法

**思想**：所有程序构成一个环，令牌按照顺时针顺序在环之间传递，收到令牌的程序有资格访问临界资源，访问完成后传给下一个程序，若程序在收到令牌后不需要使用资源则直接传给下一个程序。

**特点**：公平性高，在改进单点故障后，稳定性也很高，适用于系统规模较小，并且系统中每个程序使用临界资源的频率高且使用时间比较短的场景。

**改进**：两层结构的分布式令牌环，外层是一个令牌环，令牌环的每一个节点又是一个令牌环。

## Election

### Bully 算法

选举过程有三种消息：

* Election，发起选举。
* Alive，响应 Election。
* Victory，宣布自己为主节点。

**思想**：“长者为大”

**前提条件**：集群中每个节点均知道其它节点的 ID

**选举过程**为，每个节点判断自己的 ID 是否为最大：

* 若是最大，则向其它所有节点发送 Victory。
* 若不是最大：
  * 向 ID 比自己大的节点发送 Election，并等待回复：
    * 若在一定时间内没有收到 Alive，则认为自己是主节点，发出 Victory。
    * 若收到 ID 比自己大的节点发送的 Alive，则等待 Victory。
* 不管是不是最大，若收到 ID 比自己小发送的 Election，则回复 Alive。

**优点**：选举速度快，算法复杂低，简单易实现。

**缺点**：每个节点都需要全局节点信息。如果一个 ID 较大的节点频繁重启，则会导致频繁重新选举（可优化）。

案例：MongoDB，Elasticsearch。

### Raft

节点有三种角色：

* Leader，主节点。
* Candidate，有资格成为 Leader。
* Follower，不可以发起选举。

思想：“少数服从多数”

选举流程：

1. 初始时，所有节点都为 Follower。
2. 开始选主，所有节点转换成 Candidate， 向其它节点发送选主请求。
3. 其它节点根据收到选举请求的先后顺序，回复是否同意。每个节点只能投一张票。
4. 获得半数以上的 Candidate 成为 Leader，其它变为 Follower。Leader 和 Follower 会有心跳。
5. Leader 任期到了或心跳丢了，则新一轮选主。

优点：选举速度快，算法复杂度低，易于实现。

缺点：每个节点都需要互相通信，

案例：etcd，consul。

### ZAB

案例：zookeeper。

## Consensus

分布式共识是多个节点均可独自操作的情况下，使所有节点针对某个状态达成一致的过程。

上面的分布式选举就是一种主要基于多数投票策略实现的分布式共识。

{% hint style="warning" %}
一致性与共识的区别：

* 一致性：一个分布式系统中的多个节点对外界呈现的数据或状态是一致的。
* 共识：分布式系统中的多个节点，彼此之间对某个状态达成一致的过程。

所以，一致性强调结果，共识强调达成一致的过程。
{% endhint %}

### PoW

Proof of work，工作量证明。通过计算能力来竞争，比如所有节点都计算满足某个条件的数值，计算出来后发送给其它节点，其它节点校验这个数值，若校验通过则同意那个节点的权限。这个算力强的节点获得权限后，将信息广播给其它节点。如比特币。

缺点：共识达成的周期长、效率低、资源消耗大。

### PoS

Proof of stake，权益证明。每个节点有数据和持有数据的时间，转换成权益。

缺点：容易出现垄断。

### DPoS

Delegated proof of stake，委托权益证明。节点虽然有权益，但是不能操作。但是可以用来投票，权益代表的是投票的权重，投给可信的其它节点。

## Lock

多个进程并发访问同一临界资源，同一时刻只有一个进程可以访问。

* 基于关系型数据库实现。
* [基于缓存实现](https://yunzhao.gitbook.io/notes/database/basic#fen-bu-shi-suo)。
* [基于 Zookeeper 实现](https://yunzhao.gitbook.io/notes/database/zookeeper-1#fen-bu-shi-suo)。