分布式系列之分布式互斥

什么是分布式互斥

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

分布式互斥常用算法

集中式算法

集中式算法的核心是引入一个协调者程序，得到一个分布式互斥算法。每个程序在需要访问临界资源时，先给协调者发送一个请求。如果当前没有程序使用这个资源，协调者直接授权请求程序访问；否则，放到一个队列当中（先来先服务）。如果有程序使用完资源，则通知协调者，协调者从队列中里取出在最前面的请求，并给它发送授权信息。拿到授权信息的程序，可以直接去访问临界资源。

如图，程序1，2，3，4为普通运行程序，另一个程序为协调者。当程序2和程序4需要使用临界资源时，它们会向协调者发起申请，请求协调者授权。

此时，程序3正在使用临界区资源，这时协调者根据程序2和4的申请时间顺序，一次将他们放入等待队列。程序3使用完临界区资源（假设程序4先访问），通知协调者释放资源。此时协调者从等待队列中取出程序4，并给他发放授权，此时，程序4就可以访问临界区资源了。

可以看得出，一个程序访问临界区资源需要三次交互（1、协调者发送请求授权。2、协调者向程序发放授权信息。3、程序使用完临界资源，释放授权）。所以系统的性能相对会差一些

总结：集中式算法具有简单、易于实现的特点，但可用性（协调者单点故障导致系统不可用）、性能易受协调者影响。

分布式算法

该算法的工作过程如下：当一个进程要访问共享资源时，它会构造一个消息，其中包含要访问的资源的名字、其进程号、当前时间戳；然后它将该消息发送给系统中的所有其他进程；当一个进程接收到来自另一个进程的请求消息时，它根据自己与消息中的资源相关的状态来决定它要采取的动作：

1）如果接收者没有访问资源，而且也没有访问的打算，就会给发送者一个OK消息；

2）如果接收者已获得对资源的访问，那么他就不进行应答（或者回复拒绝消息），并把该请求放到队列中；

3）如果接收者想访问资源，但是还没开始访问呢，这个时候它就会把自己的请求的时间戳与接收到消息的时间戳做对比，时间戳小者胜出。

如图，程序1，3同时发出请求，程序1的时间是8，程序3的请求时间是12

程序2收到请求后，由于其不会访问资源，所有请求回复OK，同时进程1和3则进入判定环节，进程3判断进程1的请求时间戳8小于12，就给1回复ok。进程1判断时间戳12小于自己的请求时间戳，就把进程3放入请求队列中。此时进程1接收到所有的进程返回的OK，访问资源。

当进程1访问结束后，将进程3从请求队列中删除，同时给3发送OK消息，进程2此时获取到所有的进程返回OK，进入到资源访问环节。

可以看得出一次资源访问需要2*(n-1)次交互,如果n个进程同时访问资源，则需要2n(n-1)条消息。在大型的系统中使用分布式算法，消息会随着需要访问临界资源的程序数量呈指数级增加，沟通成本很高。

另外，当系统内需要访问临界资源的程序增多时，容易因为收到的请求完全超过自己的处理能力，导致正常业务无法开展。并且这种方案也存在单点故障问题（一个程序挂掉，无法应答），针对这种问题，可以使用如下方案解决：如果检测到一个程序故障，则直接忽略这个程序，无需再等待它的同意消息

总结：分布式算法的核心思想是“投票全票通过”，但是通信成本高，可用性也低，适用于临界资源使用频率较低且规模小的场景

令牌环算法

在一个分布式系统中，把所有进程逻辑上组成一个环，首先每个进程知道其下一个进程是谁（通常更常用的应该是每个进程要维护一个记录，知道其后的所有其他进程，以便在其直接后继发生崩溃时，能把令牌传递给其后继，更有甚者传递给其后继的后继）

当环初始化时，进程0得到一个令牌（可以理解为一个互斥锁），该令牌沿着环进行传递，当进程获得到令牌后，会首先检查其是否有访问共享资源的需求，如果需要，则进行资源访问，访问完成后向后继传递令牌；如果不需要访问，则直接传递令牌给其后继。为了增强可靠性，我们要求当令牌传递给下一个进程时，要求其往回回复确认信息，如果没有返回确认信息，则认为此节点崩溃，此时将令牌传递给后继的后继。

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