分布式互斥

内容来自极客时间专栏: 《分布式技术原理与算法解析》

互斥指的是对于一个条件资源，在同一时间只能被一个单位占用，在分布式系统里，这种排他性的资源访问方式，叫作分布式互斥（Distributed Mutual Exclusion），而这种被互斥访问的共享资源就叫作临界资源（Critical Resource）

分布式互斥的几种实现方式:

集中式算法

联想到Yarn的资源调度机制

系统引入一个协调者的角色，每个程序在请求资源的时候先向协调者发送一个请求，然后协调者判断资源是否空闲，空闲的话就直接分配给这个程序，如果被占用的话，就给这个请求排号，相当于一个请求队列排队获取资源. 但同时也会存在以下两个问题:

单点问题，协调者故障，会导致所有的程序均无法访问临界资源，导致整个系统不可用, 因此需要额外的机制保障协调者的正常运行状态(其实感觉 zookeeper 也是类似这种)
协调者通常会成为系统的性能瓶颈，协调者处理的消息数量会随着需要访问临界资源的程序数量线性增加
集中式算法示意图如下所示:

HDFS中文件修改机制采用了这种算法

不同于集中式算法，分布式算法实现的原理是当某个程序请求资源时，先向系统内所有其他程序发送请求，其他程序如果没有占用这个资源那么返回同意的结果，在接收到所有其他程序返回的同意消息后，才可以访问临界资源。
这个算法可用性很低，主要包括两个方面的原因：

随着系统内程序数增多，消息数量会随着需要访问临界资源的程序数量呈指数级增加(2n * (n-1))，容易产生“信令风暴”，也就是程序收到的请求完全超过了自己的处理能力，而导致自己正常的业务无法开展
我们知道在计算机网络中消息的可靠性保证也是很难的，会出现比如消息丢失，消息延时到达等情况，在分布式算法中也同样，比如某个程序发生故障，导致无法发送同意请求资源的响应消息或者延时响应，那么其他程序往往就会因此而陷入等待使系统阻塞，导致系统不可用

分布式算法根据“先到先得”以及“投票全票通过”的机制，让每个程序按时间顺序公平地访问资源，简单粗暴、易于实现，适用于临界资源使用频度较低，且系统规模较小的场景

算法示意图如下：

如同所示，程序排成环形结构，令牌循环传递，收到令牌的程序有权访问临界资源，访问完成后将令牌传送到下一个程序；若该程序不需要访问临界资源，则直接把令牌传送给下一个程序；

ps: 我一开始想到了限流机制的令牌桶算法，但其实不一样

以下思考内容可能存在问题，欢迎指正

改进思路: 可参照redis集群通信模式，通过hash key将大量的请求分散到不同的master,以处理大量请求,每个master由小集群主从节点来保障单点故障

设置超时，如果某个节点发生故障迟迟没有响应达到超时时间限制，将其从系统中剔除出去，或者直接忽略

改进思路: 可根据参与者使用频率列出权重，结合平滑加权轮询算法选出下一个参与者
同时需要注意若环中某个节点发生故障需要及时剔除出去，保证令牌在正常节点之间传递

单机上互斥可以用信号量、锁机制、线程同步等方法，可以在jvm层级或单机硬件层面做到互斥。分布式环境，彼此都是运行在不同的服务器彼此不可感知，需要用额外的手段保证各节点访问互斥