【转载——两个很基础的选举算法】分布式系统进程的选举

简介: <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; color:rgb(69,69,69); font-family:Tahoma,Arial,Helvetica,STHeiti; font-size:14px; line-height:25px"> 在分布式系统中,为了协调一

在分布式系统中,为了协调一组进程的动作,我们常常需要一个进程扮演协调者、初始者或管理者的角色。这个进程可以是进程组的任何一个,但关键的是进程组必须选举出唯一一个而且必须达到共识。

如果所有的进程都完全一样,它们之间没有任何可区别的属性,那么也就没有办法选举出一个特别的进程。因此,我们假设进程有一个全局唯一的编号,这个编号可以是网络地址或其他方法产生的编号。不失一般性,我们可以假设选举算法总是选举编号最大的进程作为协调进程。

我们另外还假设,每个进程都知道组内其他进程的编号。如果最大编号的进程总是在运行中并且总是能够担当协调者的角色,那么选举就变成了指派。选举算法需要考虑的是,当最大编号的进程因为这样和那样的原因不能成为协调者时,选举过程才会发生。我们称它为一个进程召集选举。

如果一个进程启动了选举算法的一次执行,且每次只能启动一次召集选举的过程,则原则上有 n 个进程的分布式系统可以并发地召集 n 次选举。算法的一个基本要求是对当选进程的选择必须是唯一的,即使有多个并发的召集过程在执行,最后的结果必须保证所有召集选举和参与选举的进程对当选的进程达成共识。

霸道算法

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法(Bully Algorithm)。当一个进程 P 发现协调者进程不再响应时,这个进程就召集选举。由于进程的独立性,在同一个时刻,系统中可能有多个召集选举的过程。假设 P 是召集选举的进程,每个召集选举的过程如下:

  1. P 向所有比自己编号大的进程发送一条 ELECTION(选举)消息。
  2. 如果 P 得不到任何回复,则 P 赢得选举,P 向所有进程发送 COORDINATOR(协调者)消息,宣布自己的胜利。
  3. 如果 P 得到任何一个回复,回复一定来自于比自己编号大的进程。P 的召集选举的工作结束,因为 P 此时已经不可能赢得选举。

其他进程或正在召集选举,或可能接收到比自己编号小的进程的 ELECTION 消息。当它收到一个 ELECTION 后,它回复一个 OK 消息给发送消息的进程;如果这时它还不是召集选举的进程,它也将开始一个召集选举的过程,即执行 1 到 3 的操作。
拥有最大编号的进程不召集选举,它直接发送 COORDINATOR 消息宣布胜利,霸道算法的名字由此得来。

环选举算法

关于选举的另一个著名算法是基于进程环的机制设计的。与一般的环算法不同的是,环选举算法并不使用令牌。在这个算法中,我们假设所有进程能够在物理上或逻辑上组成一个环结构,每个进程都保留一个按进程编号逻辑排序的一个表,因此知道自己的所有后继进程。

算法的过程非常简单。当一个进程 P 注意到协调者进程不再工作时,它将启动一个召集选举的过程:

  1. 进程 P 构造一个包含自己进程编号的 ELECTION 给后继进程,如果直接后继进程没有响应,进程 P 就将消息发送给环上的下一个进程,直到找到一个正常运行的进程。
  2. 接收到 ELECTION 消息的进程将自己的编号增加到 ELECTION 消息中,然后按照同样的方式将消息发送给后继进程。这样,消息在环上的传递将构造一个包含所有正常运行的进程的编号表。
  3. 当 ELECTION 消息最后回到召集选举的进程时,消息中最大编号的进程即成为选举的胜利者。召集选举的进程将消息类型改为 COORDINATOR,然后将消息沿着环重新发送一次,将选举结果通知所有的进程。
  4. 当 COORDINATOR 消息重新回到召集选举的进程时,算法终止。

同样,在环选举算法中,也可能同时存在多个召集选举的过程。当在这个时刻环结构不变时,最后的结果也是一致的,只是消息数量多一些,并无大碍。

关于选举算法的讨论

霸道选举算法和环选举算法都依赖一系列苛刻的假设:

  1. 假设了可靠的通道通信,更进一步的假设是系统中任何两个进程之间都可以通信。
  2. 每个进程都知道其他进程的编号,也就是说算法依赖一个全局的数据。
  3. 在多个并发召集选举的过程中,进程组的正常进程数量保持稳定,而且在环选举算法中,环结构也必须稳定。
  4. 假设进程能够明确地判断出一个正常运行的进程和一个已经崩溃的进程。

有很多放宽假设条件下如何改进算法的讨论,但就算法的应用来说,召集选举的过程不应该是很频繁的,参与选举的进程数量和结构应该是相对稳定的。我们看不到频繁故障下的频繁选举的应用价值。因此,虽然算法的适用条件比较苛刻,但它们基本能够满足应用的需求。

目录
相关文章
|
1月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
8天前
|
算法 人机交互 调度
进程调度算法_轮转调度算法_优先级调度算法_多级反馈队列调度算法
轮转调度算法(RR)是一种常用且简单的调度方法,通过给每个进程分配一小段CPU运行时间来轮流执行。进程切换发生在当前进程完成或时间片用尽时。优先级调度算法则根据进程的紧迫性赋予不同优先级,高优先级进程优先执行,并分为抢占式和非抢占式。多队列调度算法通过设置多个具有不同优先级的就绪队列,采用多级反馈队列优先调度机制,以满足不同类型用户的需求,从而优化整体调度性能。
28 15
|
10天前
|
算法 调度 UED
深入理解操作系统之进程调度算法
【9月更文挑战第9天】在操作系统的心脏跳动中,进程调度扮演着关键角色,就如同指挥家控制交响乐的节奏。本文将通过浅显易懂的语言和生动的比喻,带领读者走进进程调度的世界,探索不同调度算法背后的哲学与实践,以及它们如何影响系统的性能和用户体验。从最简单的先来先服务到复杂的多级队列和反馈循环,我们将一同见证操作系统如何在众多任务中做出选择,确保系统的高效与公平。
|
29天前
|
消息中间件 JSON 自然语言处理
Python多进程日志以及分布式日志的实现方式
python日志模块logging支持多线程,但是在多进程下写入日志文件容易出现下面的问题: PermissionError: [WinError 32] 另一个程序正在使用此文件,进程无法访问。 也就是日志文件被占用的情况,原因是多个进程的文件handler对日志文件进行操作产生的。
|
1月前
|
存储 算法 NoSQL
(七)漫谈分布式之一致性算法下篇:一文从根上儿理解大名鼎鼎的Raft共识算法!
Raft通过一致性检查,能在一定程度上保证集群的一致性,但无法保证所有情况下的一致性,毕竟分布式系统各种故障层出不穷,如何在有可能发生各类故障的分布式系统保证集群一致性,这才是Raft等一致性算法要真正解决的问题。
76 11
|
20天前
|
存储 算法 调度
深入理解操作系统:进程调度的算法与实现
【8月更文挑战第31天】在操作系统的核心,进程调度扮演着关键角色,它决定了哪个进程将获得CPU的使用权。本文不仅剖析了进程调度的重要性和基本概念,还通过实际代码示例,展示了如何实现一个简单的调度算法。我们将从理论到实践,一步步构建起对进程调度的理解,让读者能够把握操作系统中这一复杂而精妙的部分。
|
20天前
|
算法 调度 开发者
深入理解操作系统:进程管理与调度算法
在数字时代的心脏,操作系统扮演着至关重要的角色。它不仅是计算机硬件与软件之间的桥梁,更是确保多任务高效运行的守护者。本文将带你一探操作系统中进程管理的奥秘,并通过实际代码示例深入解析进程调度算法。无论你是编程新手还是资深开发者,了解这些基础概念都将有助于你更好地理解计算机工作原理,并提升你对系统性能调优的认识。准备好,让我们一起揭开操作系统的神秘面纱!【8月更文挑战第31天】
|
20天前
|
算法 调度
探索操作系统的心脏:进程调度算法揭秘
【8月更文挑战第31天】本文将带领读者深入理解操作系统中至关重要的一环——进程调度。通过浅显易懂的语言和逐步深入的内容安排,我们将从基础概念入手,探讨进程调度的目的和挑战,进而分析几种常见的调度算法。文中不仅提供了丰富的代码示例,还设计了互动问题,鼓励读者思考并应用所学知识。让我们一起揭开操作系统进程调度的神秘面纱,看看它是如何在幕后支撑着我们日常使用的电脑和移动设备的顺畅运行。
|
1月前
|
存储 算法 索引
(六)漫谈分布式之一致性算法上篇:用二十六张图一探Raft共识算法奥妙之处!
现如今,大多数分布式存储系统都投向了Raft算法的怀抱,而本文就来聊聊大名鼎鼎的Raft算法/协议!
|
1月前
|
存储 算法 Java
(五)漫谈分布式之一致性算法篇:谁说Paxos晦涩难懂?你瞧这不一学就会!
没在时代发展的洪流中泯然于众的道理很简单,是因为它们并不仅是空中楼阁般的高大上理论,而是有着完整落地的思想,它们已然成为构建分布式系统不可或缺的底层基石,而本文则来好好聊聊分布式与一致性思想的落地者:Paxos与Raft协议(算法)。

热门文章

最新文章