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

简介: <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. 假设进程能够明确地判断出一个正常运行的进程和一个已经崩溃的进程。

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

目录
相关文章
|
2月前
|
算法 调度 Python
深入理解操作系统中的进程调度算法
在操作系统中,进程调度是核心任务之一,它决定了哪个进程将获得CPU的使用权。本文通过浅显易懂的语言和生动的比喻,带领读者了解进程调度算法的重要性及其工作原理,同时提供代码示例帮助理解。
|
5月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
2月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
95 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
1月前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
53 1
|
2月前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
82 4
|
2月前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
2月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
3月前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。
|
3月前
|
算法 调度 UED
深入理解操作系统的进程调度算法
【10月更文挑战第7天】在操作系统的心脏——内核中,进程调度算法扮演着至关重要的角色。它不仅影响系统的性能和用户体验,还直接关系到资源的合理分配。本文将通过浅显易懂的语言和生动的比喻,带你一探进程调度的秘密花园,从最简单的先来先服务到复杂的多级反馈队列,我们将一起见证算法如何在微观世界里编织宏观世界的和谐乐章。

热门文章

最新文章