分布式原理-分布式互斥算法

前言

分布式技术在现阶段是非常重要的，掌握分布式计算原理是作为当今技术人员必备的技能，分布式计算的难点在于如何协调不同计算机上的程序可以更好的不出错的协作共同达成一个业务目标。所以分布式核心技术原理主要包含分布式节点协调、分布式调度、分布式数据存储和分布式高可用，只要理清楚这几点就可以利用这些分布式原理去理解各个分布式系统架构和分布式中间件的底层原理，能够根据各个分布式中间件在各个方面的优缺点做出合理的选型。

本篇文章我们主要是介绍分布式互斥算法，下面会介绍主流的3种分布式互斥算法，集中式互斥算法、分布式互斥算法、令牌环算法，通过介绍这3种算法让大家了解分布式互斥算法的原理。

集中互斥算法

集中式互斥算法的核心是增加一个全局协调者来约束大家使用临界资源。

每个程序在需要访问临界资源时，先给协调者发送一个请求。如果当前没有程序使用这个资源，协调者直接授权请求程序访问；否则，按照先来后到的顺序为请求程序“排一个号”。如果有程序使用完资源，则通知协调者，协调者从“排号”的队列里取出排在最前面的请求，并给它发送授权消息。拿到授权消息的程序，可以直接去访问临界资源。

集中互斥算法

上图描述了集中式互斥算法的流程：

1）Node1先向协调者发出对临界资源A的请求，时间戳为123，协调者在本地保存一个临界资源的有序链表，临界资源A的链表会记录（请求节点、访问时间戳）；

2）Node2也向协调者发出对临界资源A的请求，时间戳为124，协调者在临界资源A的访问链表中按照时间戳升序插入节点；

3）协调者按照临界资源的当前链表情况，选出第一个最早请求的节点，发现是Node1，此时就给Node1返回临界资源A可用；

4）Node1收到协调者返回A可用后，会去使用资源A，使用完毕后，会告诉协调者A已经使用完毕；

5）此时协调者查看队列中下一个待访问资源A的节点是Node2，此时就会告诉Node2资源A可用了；

6）Node2使用资源A,使用完后告诉协调者A使用完毕；

整个过程就是这样的，一个程序完成一次临界资源访问，需要如下3次消息交互：

1）向协调者发送请求授权信息，1 次消息交互；

2）协调者向程序发放授权信息，1 次消息交互；

3）程序使用完临界资源后，向协调者发送释放授权，1 次消息交互。

因此集中式互斥算法的缺点：

1）协调者会存在性能瓶颈；

2）容易引发单点故障。

集中式算法具有简单、易于实现的特点，但可用性、性能易受协调者影响。

分布式互斥算法

分布式互斥算法也叫民主协商互斥算法，当一个程序要访问临界资源时，先向系统中的其他程序发送一条请求消息，在接收到所有程序返回的同意消息后，才可以访问临界资源。其中，请求消息需要包含所请求的资源、请求者的 ID，以及发起请求的时间。

分布式互斥

如上图所示，一个程序完成一次临界资源的访问，需要进行如下的信息交互：

1） 先向其他 n-1 个程序发送访问临界资源的请求，总共需要 n-1 次消息交互；

2） 需要接收到其他 n-1 个程序回复的同意消息，方可访问资源，总共需要 n-1 次消息交互。

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

该民主协商互斥算法的优缺点也很明显，根据“先到先得”以及“投票全票通过”的机制，让每个程序按时间顺序公平地访问资源，简单粗暴、易于实现。但，这个算法可用性很低，主要包括两个方面的原因：

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

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

针对可用性低的一种改进办法是，如果检测到一个程序故障，则直接忽略这个程序，无需再等待它的同意消息。但这样的话，每个程序都需要对其他程序进行故障检测，这无疑带来了更大的复杂性。

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

令牌环互斥算法

令牌环互斥算法，所有程序构成一个环结构，令牌按照顺时针（或逆时针）方向在程序之间传递，收到令牌的程序有权访问临界资源，访问完成后将令牌传送到下一个程序；若该程序不需要访问临界资源，则直接把令牌传送给下一个程序。

令牌环互斥

因为在使用临界资源前，不需要像分布式算法那样挨个征求其他程序的意见了，所以相对而言，在令牌环算法里单个程序具有更高的通信效率。同时，在一个周期内，每个程序都能访问到临界资源，因此令牌环算法的公平性很好。

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

对于集中式和分布式算法都存在的单点故障问题，在令牌环中，若某一个程序出现故障，则直接将令牌传递给故障程序的下一个程序，从而很好地解决单点故障问题，提高系统的健壮性，带来更好的可用性。但，这就要求每个程序都要记住环中的参与者信息，这样才能知道在跳过一个参与者后令牌应该传递给谁。

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

总结

	集中式互斥算法	分布式互斥算法	令牌环互斥算法
算法	引入一个协调者，将所有请求者进行排序，最早请求的参与者可以使用临界资源	征求其他参与者同意后，使用临界资源	所有参与者组成一个环，轮流使用资源
优点	简单、易于实现通信高效	可用性低	单个参与者通信效率较高可用性高
缺点	可用性低性能易受协调者影响	通信成本高复杂度较高	当参与者对临界资源使用频率较低时，会带来较多无用通信
应用场景	在协调者可靠性和性能有一定保障的情况下，可以适用于比较广泛的场景	临界资源使用频度较低且系统规模较小的场景	系统规模较小，并且系统中每个程序使用共享资源频度较高且时间较短的场景