什么是分布式互斥？

减库存是一个很常见的例子，假如两个线程同时查到库存还有10件，同时卖出10件后，去库存中减10件，这样就会造成库存还剩下-10件。这显然是不合理的，这就需要当一个线程操作的时候，另一个线程不能操作，这就是排他性资源访问。

在分布式系统里，这种排他性的资源访问方式，叫作分布式互斥，而这种被互斥访问的共享资源就叫作临界资源。

我们一起来看下分布式技术中是如何对临界资源进行互斥访问的。

霸道总裁：集中式算法

集中式算法就是建立一个协调者，任何三方想要访问临界资源都要通过协调者，协调者认为你可以访问，你才可以访问，否则就不能访问。

具体操作就是访问者先访问协调者，协调者发现现在没有其他访问者占用资源，就给当前访问者发送放行信号，否则就要按照协调者的规则进行下一步动作，包括排队，自旋等。

这个互斥算法，就是我们所说的集中式算法，也可以叫做中央服务器算法。之所以这么称呼，是因为协调者代表着集中程序或中央服务器。

一个程序完成一次临界资源访问，需要如下几个流程和消息交互： 向协调者发送请求授权信息，1次消息交互； 协调者向程序发放授权信息，1次消息交互； 程序使用完临界资源后，向协调者发送释放授权，1次消息交互。 因此，每个程序完成一次临界资源访问，需要进行3次消息交互。

集中式算法的优点：

直观、简单、信息交互量少、易于实现，并且所有程序只需和协调者通信，程序之间无需通信。

集中式算法的缺点：

一方面，协调者会成为系统的性能瓶颈。 想象一下，如果有100个程序要访问临界资源，那么协调者要处理100*3=300条消息。也就是说，协调者处理的消息数量会随着需要访问临界资源的程序数量线性增加。

另一方面，容易引发单点故障问题。协调者故障，会导致所有的程序均无法访问临界资源，导致整个系统不可用，因此，在使用集中式算法的时候，一定要选择性能好、可靠性高的服务器来运行协调者。

目前市场上集中式算法的实现主要通过redis zookeeper 数据库实现，这些组件对于在应对高可用，高性能方面都有自己的方案。开发者需要根据不同的业务选择使用哪种方式。

民主协商：分布式算法

集中式算法是访问者访问资源前征求协调者的同意，那么分布式算法就是访问者在访问资源前征求其他访问者的同意。

具体操作为当一个程序要访问临界资源时，先向系统中的其他程序发送一条请求消息，在接收到所有程序返回的同意消息后，才可以访问临界资源。其中，请求消息需要包含所请求的资源、请求者的ID，以及发起请求的时间。

这就是民主协商法。在分布式领域中，我们称之为分布式算法，或者使用组播和逻辑时钟的算法。

这个算法中，一个程序完成一次临界资源的访问，需要进行如下的信息交互：

1. 向其他n-1个程序发送访问临界资源的请求，总共需要n-1次消息交互；
2. 需要接收到其他n-1个程序回复的同意消息，方可访问资源，总共需要n-1次消息交互。

可以看出，一个程序要成功访问临界资源，至少需要2*(n-1)次消息交互。假设，现在系统中的n个程序都要访问临界资源，则会同时产生2n(n-1)条消息。在大型系统中使用分布式算法，消息数量会随着需要访问临界资源的程序数量呈指数级增加，容易导致高昂的“沟通成本”。

分布式算法的优点：

分布式算法根据“先到先得”以及“投票全票通过”的机制，让每个程序按时间顺序公平地访问资源，简单粗暴、易于实现。

分布式算法的缺点：

当系统内需要访问临界资源的程序增多时，容易产生“信令风暴”，也就是程序收到的请求完全超过了自己的处理能力，而导致自己正常的业务无法开展。

一旦某一程序发生故障，无法发送同意消息，那么其他程序均处在等待回复的状态中，使得整个系统处于停滞状态，导致整个系统不可用。所以，相对于集中式算法的协调者故障，分布式算法的可用性更低。

当然可以通过检测其他程序是否可用的方式可以解决阻塞停滞问题，但是无疑增加了系统的复杂性。

因此，分布式算法适合节点数目少且变动不频繁的系统，且由于每个程序均需通信交互，因此适合P2P结构的系统。比如，运行在局域网中的分布式文件系统，具有P2P结构的系统等。

Hadoop是我们非常熟悉的分布式系统，其中的分布式文件系统HDFS的文件修改就是一个典型的应用分布式算法的场景。

处于同一个局域网内的计算机1、2、3中都有同一份文件的备份信息，且它们可以相互通信。这个共享文件，就是临界资源。当计算机1想要修改共享的文件时，需要进行如下操作：

计算机1向计算机2、3发送文件修改请求； 计算机2、3发现自己不需要使用资源，因此同意计算机1的请求； 计算机1收到其他所有计算机的同意消息后，开始修改该文件； 计算机1修改完成后，向计算机2、3发送文件修改完成的消息，并发送修改后的文件数据； 计算机2和3收到计算机1的新文件数据后，更新本地的备份文件。

轮值CEO：令牌环算法

程序访问临界资源问题也可按照轮值CEO的思路实现。 如下图所示，所有程序构成一个环结构，令牌按照顺时针（或逆时针）方向在程序之间传递，收到令牌的程序有权访问临界资源，访问完成后将令牌传送到下一个程序；若该程序不需要访问临界资源，则直接把令牌传送给下一个程序。 在分布式领域，这个算法叫作令牌环算法，也可以叫作基于环的算法。为了便于理解与记忆，你完全可以把这个方法形象地理解为轮值CEO法。

图片

令牌环算法优点：

相对于分布式算法，令牌环算法不需要再征求其他所有访问者的同意，只需要将令牌传递给下一个访问者即可，这样通信压力相对变小，通信效率更高。

公平性更好，在一个周期内，每个程序都能访问到临街资源。

不存在单点问题，如果某个访问者故障了，令牌可以直接往下一个访问者传递，故障的访问者会自动出局。

令牌环算法缺点：

不管环中的程序是否想要访问资源，都需要接收并传递令牌，所以也会带来一些无效通信。假设系统中有100个程序，那么程序1访问完资源后，即使其它99个程序不需要访问，也必须要等令牌在其他99个程序传递完后，才能重新访问资源，这就降低了系统的实时性。

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

本篇介绍了分布式技术中常见的分布式互斥算法，下一篇我们探讨下具体的分布式互斥实现方案-分布式锁具体实现。