对于任何一个系统中,都存在资源互斥访问的问题,也就是我们常说的临界资源。
针对于单应用、单机有编程语言、操作系统提供的原语进行处理,比如Java中一个简单的 synchronized
关键字就可以达到互斥访问的作用。
但是对于分布式系统呢?
当然可以使用zk、redis等实现分布式锁,本文主要讨论的是底层基础,非对中间件的应用。
解决互斥的前提条件
前提就是必须要解决的问题,比如,如果设计了一个互斥算法逻辑,实现之后,总是会出现死锁,这样会导致系统不可用,这种算法就是有问题的,必须进行改进。
其他问题
因为分布式系统的复杂性,还有几个问题需要解决。
- 所有的系统内主机都是通过网络互联起来, 进程之间的通信可靠性也严重依赖于连接系统的网络的稳定性。
- 在分布式系统中, 每个主机都有自身的物理时钟,难以进行同步。 因此, 需要设计一种全局的统一时钟机制, 对系统内所有主机进行统一。
- 通过网络互联, 由于网络延迟等多方面因素, 系统不能立即感知主机故障。 链路故障也不容易进行侦测,需要考虑各主机和链路的故障检测机制, 使得系统应对故障时有最少的反应时间, 提高系统稳定性。
性能评价标准
平均消息数
是指每个节点在一次临界资源的访问过程中需要发送的消息平均数。
这个指标可以简单理解为:沟通达成一件事情的过程中,你们说了多少废话?
废话多,那么性能差;废话少,性能高;
因为所有的 言语
都是通过网络传递的,网络本身就不是绝对可靠稳定的,废话越多,那么面临的风险与不稳定也是越高的。
而且请求变多时,大量的沟通也会增加网络负担。
同步延时
同步延迟是指当前节点离开临界区到下一节点进入临界区之间的时问间隔。
就像加油站,碰巧你加完油之后,离开了,加油车来了,下一个人得等着卸油,搞完了才能给他加油,这个等待时间就可以理解为同步延时。
同步延迟短, 则单位时间内的访问次数就比较多, 资源利用率高。
响应时间
响应时间是指节点从发送临界资源访问请求到进入临界区之间的时间间隔。
当然,这三个只是主要的,还会有其他很多的评价标准,比如容错性,这些东西仅作了解。
主要算法分类
集中式
选择一个节点作为中心,由他来进行控制。
任何其他进程产生访问临界资源的请求时, 都需要发送请求消息到这个管理进程。
复杂的分布式环境转换为单机,系统设计、实现更加简单,但是增加了选举逻辑复杂度,选举谁作为管理节点是一个新的问题。
而且,如果管理节点故障,将是致命的,必须有后续的弥补方案。
在可靠性和性能有一定保障的情况下,比如中央服务器计算能力强、性能高、故障率低,或者中央服务器进行了主备备份,主故障后备可以立马升为主,且数据可恢复的情况下,集中式算法可以适用于比较广泛的应用场景。
大致逻辑如上图所示,就是协调者负责安排,通常是采用队列的形式。
一个程序完成一次临界资源访问,需要如下几个流程和消息交互:
向协调者发送请求授权信息,1 次消息交互;
协调者向程序发放授权信息,1 次消息交互;
程序使用完临界资源后,向协调者发送释放授权,1 次消息交互。
可以看出来消息数算比较少的了。
民主式(基于许可)
相比集中式由一个节点说了算,民主式是由大家说了算。
也就是你问问身边的其他节点的人,是不是同意,根据同意人数的多寡,又分为全局以及部分。
全局是需要所有的节点同意,部分是某一个分组内大家都同意,或者平时说的少数服从多数,都是部分。
这种实现就比较麻烦,因为本身网络通信就是不可靠的,而且必须要有一个一致的收敛结果,否则无限发散下去可能迟迟无法达成一致。
上图是一种最基本的形式,节点0 需要临界资源,需要像其他节点进行通信,发起请求,别人回复同意,那么你就可以使用临界资源了。
此时假设n个节点,需要2(n-1)次消息通信,明显比集中式的消息要多,而且,这还是最理想的情况下,通常情况下,必然次数大于2(n-1)
另外,如果现在系统中的 n 个程序都要访问临界资源,则会同时产生 2n(n-1) 条消息,指数级上升了~
图中是一种最简单的形式,每个节点需要有自身的判断逻辑,一定的算法,比如节点0和节点1 都想要使用,如何应答?比如按照他们的id顺序?同意0 不同意1 还是如何?
沟通成本确实很高,比如在使用Zookeeper时,操作不慎发生的羊群效应,就是这个消息爆炸情况。
所以主要的问题就是:
- 当系统内需要访问临界资源的程序增多时,容易产生“信令风暴”,也就是程序收到的请求完全超过了自己的处理能力,而导致自己正常的业务无法开展。
- 一旦某一程序发生故障,无法发送同意消息,那么其他程序均处在等待回复的状态中,使得整个系统处于停滞状态,导致整个系统不可用。所以,相对于集中式算法的协调者故障,分布式算法的可用性更低。
如果系统规模非常大,这种沟通成本是灾难性的,不适合大规模节点。
令牌
令牌环算法中, 系统内部存在一个环结构, 可以是所有节点组成一个物理环,也可以是按照一定的策略构建一个逻辑环。
令牌自动地、 持续地在环内不断的循环,走到谁,就问问你是否需要?不需要直接下一个人,需要就访问临界资源。访问临界资源的人,就是持有令牌的人。
但是这样会造成资源浪费,有的人明明不需要,还要浪费时间询问,所以出现了优化的算法,那就是只有需要的人才来排队,也就是请求令牌,请求的人才来排队,不请求的人不在队伍中。
类算法的稳定性依赖于分布式系统的通信网络的可靠性,如果令牌传递丢失还必须重新生成令牌,何时重新生成等这都是问题。因为网络传输的延迟性, 不容易判断令牌是已经丢失或仅仅是阻塞在网络中, 又或者是被某些进程持有。
令牌环
组成环、循环移动、走到谁给谁,不用就继续下一个。
如果有单机节点故障,可以直接跳过,当然这就需要记住环上的每个节点以及他们的对应顺序。
而且算法很公平,当轮流到某个节点时,几乎没有多少通信沟通成本,使用就是用,不用就划过。
具体算法应用
Lamport算法
Time, Clocks and the Ordering of Events in a Distributed System
直接搜索论文标题就可以找到相关译文和原文。
直链
https://dl.acm.org/doi/pdf/10.1145/359545.359563
https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
译文:
https://zhuanlan.zhihu.com/p/484914733
https://blog.csdn.net/JKerving/article/details/102723101
论文的核心是讨论物理时钟与逻辑时钟。
如果单机系统应用,可以使用统一的物理时钟,然而分布式环境下,不管如何处理,也很难解决时钟同步的问题,所以干脆不再使用物理时钟,而是使用逻辑时钟。
一种对物理时钟转换过得逻辑顺序,用来表达时钟的排序。
概念上,时钟即给事件分配序号的方式。
那么问题就转换为:如何分配序号。
Lamport又叫做面包店算法。
逻辑类似于面包店, 医院等, 需要排队取号的场所。 顾客进入面包店前,首先抓取一个号码,然后按号码从小到大的次序依次进入面包店购买面包。
逻辑
- 面包店按由小到大的次序发放号码
- 两个或两个以上的顾客有可能得到相同号码,当多个顾客抓到相同号码,则按顾客名字的字典次序排序
- 买过的顾客号码清零,重新排队
具体过程
每个节点维护一个逻辑时钟 Ci
,他就是这个节点进程 Pi
的时钟,初始化时,所有都设置为同一个值。
节点发送请求消息时,Ci = Ci+1
;
发送消息时,格式为:(i,Ti)
,i
是节点 ID
,Ti
是逻辑时钟。
当节点 j
收到该请求消息以后, 更新自身的逻辑时钟, 使得 Cj =1+MAX(Cj,Ti)
。
然后按照下面的规则进行排序:
- 如果
Ti<Tj
,那么i的优先级高于j
;
- 如果
Ti=Tj
,那么比较i
和j
的编号,看谁的编号小,谁优先级高;
每个节点维护一个请求队列,按照优先级进行排序。
算法使用了 三种消息类型, 分别为:REQUEST
, REPLY
和 RELEASE
消息, 每个消息都包含发送节点的 ID
和 逻辑时钟
(i,Ti)
。
-
i
节点产生临界资源访问请求以后,发送 REQUEST(i,Ti)
消息至系统内的每个节点;
-
节点 j
收到 i
发送的请求消息以后,回复 REPLY
消息至 i
, 并且将 i
的请求插入到自己维护的请求优先级队列;
-
节点 i
可以访问临界资源, 仅当满足条件:REQUEST(i,Ti)
在自己维护的请求队列的顶端, 收到了所有其他节点的 REPLY
消息;
-
节点 i
执行完临界区以后, 将自身的请求消息从自己维护的请求队列中删除, 并且发送 RELEASE
消息至其他进程;
-
j
收到 i
的 RELEASE
消息以后,从请求队列中删除节点 i
的请求项。
上图就是最简单的一种可能情况,因为并发的可能,在P1 请求过程中,很可能P2 也发起请求,但是各自的队列中是按照大小排序的,只有是第一个的时候才会访问临界资源。
一次请求发送的消息数量为:
(n-1)*2+(n-1)= 3n-3 =3*(n-1)
n-1 REQUEST
,n-1 REPLY
,n-1 RELEASE
对于请求较多的分布式系统, 该算法效率较低, 发送消息数目太多容易导致网络堵塞。 对于请求较少, 网络通信质量较好的系统, 该算法比较合适
算法的同步延迟也较好, 节点访问临界区以后, 只需要发送一条RELEASE消息, 下一节点就能进入临界区。
Ricart-Agrawala 算法
An Optimal Algorithm for Mutual Exclusion in Computer Networks
https://dl.acm.org/doi/10.1145/358527.358537
- 节点
i
产生访问临界区的请求时, 发送REQUEST(i,Ti)
至系统内的所有其他进程;
- 节点
j
接受到请求REQUEST(i,Ti)
以后:如果当前j
节点没有访问临界区的请求, 则直接回复REPLY
消息; 如果j
正在访问临界区,或者j
正在请求临界区, 且根据逻辑时钟排序规则,j
节点的请求优先级高于i
节点,则保留i
的请求, 不回复任何消息至i
, 否则回复REPLY
消息;
i
收到所有其他节点的REPLY
消息以后, 方可进入临界区;
- 节点对临界区的访问结束以后, 对阻塞在请求队列中的请求节点发送
REPLY
消息。
类似Lamport算法中的简单例子示意图中,只需要两次 REQUEST
两次 REPLY
总共 2*(n-1)
条消息。
改进基于两个前提:
没有申请临界区资源的其他进程是没必要知道申请了临界区资源的进程是否释放(RELEASE)了临界区资源。
如果我的优先级更高,更早的回复也无济于事,反倒不如我退出临界区的时候在进行回复(REPLY)。
Maekawa 算法
A √N algorithm for mutual exclusion in decentralized systems
https://dl.acm.org/doi/10.1145/214438.214445
如果想要获得许可,征得所有人同意是简单粗暴的;
如果可以,征得一半以上的人同意也是OK的;
但是是否还可以继续减少?
Maekawa 算法 关键点在于仲裁集的概念,论证了只需要√N 即可。
对于总共N个人,我们可以把他们分成若干个投票组,确保任意两个投票组之间一定有交集。
这样一个人想申请,必须获得他所在的组的所有人的同意。
下一个人如果还想申请,他所在的投票组一定有人同时也属于前一个投票组,就会知道这时候临界区里面已经有人了,不会同意。
详见论文,有说明有示例。
https://dl.acm.org/doi/10.1145/214438.214445
转载务必注明出处:程序员潇然,疯狂的字节X,https://crazybytex.com/thread-237-1-1.html