本篇文章是 极客时间《分布式技术原理与算法解析》的学习笔记

分布式互斥

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

如何才能让分布式系统里的程序互斥地访问临界资源?

霸道总裁：集中式算法

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

优点：所有程序只需和协调者通信，程序之间无需通信，信息交互量少、易于实现。
缺点：协调者单点故障问题，导致整个系统不可用。

民主协商：分布式算法

当一个程序要访问临界资源时，先向系统中的其他所有程序都发送一条请求消息，在接收到所有程序返回的同意消息后，才可以访问临界资源。

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

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

可以看出，一个程序要成功访问临界资源，至少需要 2*(n-1) 次消息交互。假设，现在系统中的 n 个程序都要访问临界资源，则会同时产生 2n(n-1) 条消息。所以在大型系统中使用分布式算法，消息数量会随着需要访问临界资源的程序数量呈指数级增加，容易导致高昂的“沟通成本”。容易使得程序收到的请求完全超过了自己的处理能力，而导致自己正常的业务无法开展。

另外，一旦某一程序发生故障，无法发送同意消息，那么其他程序均处在等待回复的状态中，使得整个系统处于停滞状态，导致整个系统不可用。

所以，相对于集中式算法的协调者故障，分布式算法的可用性更低。

分布式算法使用场景：hdfs文件修改

轮值 CEO：令牌环算法

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

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

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

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

总结

一些改进：分布式算法可以大多数投票而不是全部投票，令牌环可以为每个节点增加轮值权重，比如不常访问的两轮才轮一次。