在分布式系统中，排他性的资源访问方式,就叫做分布式互斥（Distributed Mutual Exclusion）,而这种被互斥访问的共享资源，就叫做临界资源
分布式系统中解决分布式互斥主要有以下几种方式
集中式算法/中央服务器算法
我们引入一个协调者程序，得到一个分布式互斥算法。每个程序在需要访问临界资源时，先给协调者发送一个请求。 如果当前没有程序使用这个资源，协调者直接授权请求程序访问；否则，按照先来后到的顺序为请求程序“排一个号”。 如果有程序使用完资源，则通知协调者，协调者从“排号”的队列里取出排在最前面的请求，并给它发送授权消息。 拿到授权消息的程序，可以直接去访问临界资源。
集中式算法示意图：
如上图所示，协调者程序根据普通程序请求临界资源的顺序，将其放入请求队列中，依次发放授权，每个程序完成临界资源请求后，通知协调者释放授权，排队的下一次程序继续获得授权。
交互次数
- 向协调者发送请求授权信息
- 协调者向程序发放授权
- 程序使用完临界资源后，向协调者发送释放授权信息
优点
直观，简单，信息交互量少，易于实现
缺点
- 协调者会成为性能瓶颈，当普通程序很多时，协调者需要处理的消息数量会随着需要访问临界资源的程序数量线性增加
- 容易引发单点故障，当协调者故障时，会导致所有的程序都无法访问临界资源，导致整个系统不可用。
可改进点
通过将master节点集群化，来降低协调者单点故障时，系统的可用性
总结
集中式算法具有简单、易于实现的特点，但可用性、性能易受协调者影响。在可靠性和性能有一定保障的情况下，比如中央服务器计算能力强、性能高、故障率低，或者中央服务器进行了主备，主故障后备可以立马升为主，且数据可恢复的情况下，集中式算法可以适用于比较广泛的应用场景。
分布式算法/使用组播和逻辑时钟的算法
如何不引入协调者的情况下，实现对于临界资源的互斥访问呢。当一个程序要访问临界资源时，先向系统中的其他程序发送一条请求消息，在接收到所有程序返回的同意消息后，就可以访问临界资源。其中，请求消息需要包含所请求的资源，请求者id，发起请求的时间。
如图所示，程序 1、2、3 需要访问共享资源 A。在时间戳为 8 的时刻，程序 1 想要使用资源 A，于是向程序 2 和 3 发起使用资源 A 的申请，希望得到它们的同意。在时间戳为 12 的时刻，程序 3 想要使用资源 A，于是向程序 1 和 2 发起访问资源 A 的请求。
此时程序 2 暂时不访问资源 A，因此同意了程序 1 和 3 的资源访问请求。对于程序 3 来说，由于程序 1 提出请求的时间更早，因此同意程序 1 先使用资源，并等待程序 1 返回同意消息。
程序 1 接收到其他所有程序的同意消息之后，开始使用资源 A。当程序 1 使用完资源 A 后，释放使用权限，向请求队列中需要使用资源 A 的程序 3 发送同意使用资源的消息，并将程序 3 从请求队列中删除。此时，程序 3 收到了其他所有程序的同意消息，获得了使用资源 A 的权限，开始使用临界资源 A 的旅程。
交互次数
- 向其他 n-1 个程序发送访问临界资源的请求，总共需要 n-1 次消息交互
- 需要接收到其他 n-1 个程序回复的同意消息，方可访问资源，总共需要 n-1 次消息交互。
- 一个程序要成功访问临界资源，至少需要 2*(n-1) 次消息交互。假设，现在系统中的 n 个程序都要访问临界资源，则会同时产生 2n(n-1) 条消息。
优点
基于先到先得，投票全票通过的公平访问机制
缺点
- 在大型系统中使用分布式算法，消息数量会随着需要访问临界资源的程序数量呈指数级增加。当系统内需要访问临界资源的程序增多时，容易产生“信令风暴”，也就是程序收到的请求完全超过了自己的处理能力，而导致自己正常的业务无法开展。
- 一旦某一程序发生故障，无法发送同意消息，那么其他程序均处在等待回复的状态中，使得整个系统处于停滞状态，导致整个系统不可用。所以，相对于集中式算法的协调者故障，分布式算法的可用性更低。
可改进点
在某些场景下，可以当系统中过半数（n/2+1）程序回复通信消息即视为获取临界资源成功，这样可以降低通信数。常用于分布式选举场景
总结
分布式算法是一个“先到先得”和“投票全票通过”的公平访问机制，但通信成本较高，可用性也比集中式算法低，适用于临界资源使用频度较低，且系统规模较小的场景。
令牌环算法/基于环的算法
将临界资源的访问权以令牌的形式在程序间进行环形传递，收到令牌的程序有权访问临界资源，访问完成后，将令牌传递给下一个程序，如果该程序不需要访问临界资源，继续进行传递。
如上图所示，每一个环中程序不管是否想要访问资源，都需要接收并传递令牌，所以也会带来一些无效的通信。不过，该算法的通信效率较高，并且在一个通信周期内，每一个程序都有机会使用到临界资源，公平性很好。
如果出现单点故障，令牌环算法，可以最直接将令牌传递给故障程序的下一个程序，从而解决单点问题，提高系统的健壮性。
优点
令牌环算法公平性高，当改进单点故障后，稳定性也很好
缺点
- 程序1在使用完临界资源后，需要等待一个通信周期才能再次使用，实时性较低
- 如果程序对临界资源的使用频率较低，会带来很多无效通信
可改进点
可以根据参与者使用频率去更新程序的权重，结合权重值选出下一位参与者，这样可以提高单个程序实时性，降低其令牌周期
总结
令牌环算法的公平性高，在改进单点故障后，稳定性也很高，适用于系统规模较小，并且系统中每个程序使用临界资源的频率高且使用时间比较短的场景。
令牌环算法通常会与通信令牌结合，从而取得很好的效果。特别是当系统支持广播或组播通信模式时，该算法更加高效、可行。
多层结构的分布式令牌环算法
由于大规模分布式系统的复杂性，因此该算法也比较复杂。它把整个广域网系统中的节点组织为多层结构，分割为多个局域网。
在每个局域网中都构成环结构，有令牌环算法进行协调。同时局域网和局域网之间也构成环结构，这个·环为上级环。通过这种形式，实现分布式互斥。
Comments