分布式互斥：一山不容二虎
本文内容
前言
前面了解了分布式的基础知识，接下来就要逐一去攻破它们。首先要讲的是 让程序间拥有 “团队精神” 的 “分布式协调与同步”，也就是 如何让程序通过协作共同去完成一个业务目标。
本章主要讲 分布式互斥，即让分布式中的程序 互斥地访问共享资源。
1. 什么是分布式互斥？
如果你已经学过并发编程，相信你对互斥这个词一点儿都不陌生。在并发编程中，互斥指的是：多个线程并发执行时，对共享的资源（变量、文件等）需要进行互斥的访问，即保证一个时刻只能由一个线程操作该共享资源，从而防止多个线程同时修改而造成的数据不一致或其他意想不到的情况。
类比到 分布式，互斥就是 在多个节点（机器）或程序去访问共享资源（数据库、文件等）时，保证同一时刻只能由一个程序去访问该资源。
可见互斥是一种排他性的资源访问方式，这种被互斥访问的共享资源，叫作临界资源。
那么如何才能做到互斥访问这些临界资源呢？
- 在并发编程中：一般是通过 锁、信号量、原子操作或者 CAS 无锁算法 来保证；
- 而在分布式互斥中：有一些实现互斥的算法，它们分别是 集中式算法、分布式算法、令牌环算法等。
2. 霸道总裁：集中式算法
一个最简单直观的想法就是，找一个 “霸道总裁” 来控制每个程序访问临界资源的权限，它能保证每一时刻只能有一个程序能访问临界资源，这个 “霸道总裁” 的真名，就叫 协调者。
引入了协调者后，每个程序在访问临界资源时，都需要先给协调者发送一个请求，协调者根据当前临界资源的访问情况来判断是否允许该程序进行访问：
- 若当前无程序使用该资源，则授权程序访问；
- 若当前有程序使用该资源，则将该程序放入请求队列；
- 若有程序使用完了该资源，则要通知协调者，接着协调者再去队列中给最前面的程序授权。
这个互斥算法，就叫 集中式算法，因为协调者代表着一个集中程序或中央服务器。
下面给出一个简单的示例图：
从上述流程可以看出，一个程序完成一次临界资源的访问，需要进行三次消息交互：
- 向协调者发送授权请求；
- 协调者向程序授予权限；
- 程序使用完资源后，向协调者发送释放权限。
所以集中式算法虽然简单直观、易于实现，而且程序之间无需通信，只需要跟协调者通信即可。
但是，羊毛出在羊身上，这个算法的 问题 就在于协调者自身：
- 协调者成为了系统的性能瓶颈，如果有很多程序需要访问临界资源，那么协调者要处理的消息数量也会很多（程序数量的 3 倍）；
- 容易引发单点故障，即协调者宕机，所有程序均无法正常访问临界资源，从而导致系统不可用。
因此，如果选用集中式算法，一定要选择性能最好、可靠性最高的机器给协调者。
3. 民主协商：分布式算法
既然引入协调者会带来它自身的问题，那么我们就不要它，让程序之间自己去进行协调。
当一个程序要访问临界资源时，可以先向系统中的其他程序发送一条请求消息，在收到所有程序的同意消息后，才可以访问临界资源。这个请求消息需要包括请求的资源 ID、请求者 ID 和请求时间。
若一个程序收到了多了请求，也需要使用一个队列将其保存起来：
- 若该程序自身没有使用该临界资源，则按时间先后依次发出同意的消息；
- 若该程序自身使用了该临界资源，则使用完成后再依次发出同意的消息。
这样就保证了先请求的程序先得到临界资源的使用权限。
这种内部自协调的方式，就是一种民主协商的过程，在分布式领域中称为分布式算法。
我们来看看分布式算法完成一次请求需要多少次消息交互：
- 向其他 n - 1 个程序发出访问请求，需要 n - 1 次消息交互；
- 收到其他 n - 1 个程序的同意回复后，才能访问资源，也需要 n - 1 次消息的交互。
所以完成一次请求需要进行 2*(n-1) 次消息交互，如果在大型分布式系统中，消息的交互次数便会随着程序的增加而呈指数级增长，将会导致高昂的通信成本。
而且虽然分布式算法也很简单、易于实现，但其实算法的 可用性很低，因为：
- 当系统需要访问临界资源的程序增多时，会产生 “信令风暴”，即 程序收到的请求还远远超过了自己的处理能力，导致自己的业务都无法正常完成；
- 一旦某个程序发生故障，其他程序都需要等待它的回复，导致整个系统处于卡死状态。
因此，分布式算法适用于节点数量少且变动不频繁的系统。因为每个程序均需要进行交互，因此很适合 P2P 结构的系统。比如一些文件共享系统。
P2P（Peer-to-Peer）结构的系统是指不依赖中心化服务器，所有的节点（也称为对等节点）都可以直接相互通信和协作的分布式系统。
举个例子，处于同一个局域网内的计算机 1、2、3 中都有同一份文件的备份信息，且它们可以相互通信。这个共享文件，就是临界资源。当计算机 1 想要修改共享的文件时，需要进行如下图的操作：
分布式算法的优化方案：
- 可以让同意回复的数量只要满足程序数量的一半时，就允许访问；
- 如果检测到节点出现故障，则跳过此节点即可。
4. 轮值 CEO：令牌环算法
还有一种既不使用协调者，也能大大减少程序间相互通信的算法，就是 令牌环算法，非常像华为的轮值 CEO。
华为轮值 CEO 机制，即 CEO 的职位是由多名高管轮流出任。这个临界资源就是 CEO，多名高管就是程序。
这个算法的核心是 把所有程序构成一个环状结构，然后在环中有一个特殊的令牌在程序之间循环传递。只有收到令牌的程序才能访问临界资源，访问完成后即可传递给下一个程序。
这个算法的示意图如下：
可以看出，令牌环算法的 通信效率非常高，而且也很公平。但 如果环中需要访问资源的程序很少，那么会带来很多无效通信，即无效的令牌传递。
如果出现环中某个程序出现故障的情况（单点故障问题），则需要直接将令牌传递给下下个程序，这就需要每个程序都记住环中参与者的信息了。
所以，令牌环算法非常适合系统中 每个程序使用临界资源的频率高 的场景。
令牌环算法优化方案：
- 可以为每个程序根据使用评率添加轮值权重，每次使用一个加权轮询算法选出下一个参与者，节省不必要的通信（令牌传递）。
5. 总结
一张图总结三大分布式互斥算法：
