那个网站的公众后推广做的好,视频网站的防盗链是怎么做的,wordpress数据库文件在哪里,网上开店卖货流程1. 概述#xff1a;什么是分布式互斥
假设有两个小孩想玩同一个玩具#xff08;临界资源#xff09;#xff0c;但玩具只有一个#xff0c;必须保证一次只有一个人能够玩。当一个小孩在玩时#xff0c;另一个小孩只能原地等待#xff0c;直到玩完才能轮到自己。这就是 …1. 概述什么是分布式互斥
假设有两个小孩想玩同一个玩具临界资源但玩具只有一个必须保证一次只有一个人能够玩。当一个小孩在玩时另一个小孩只能原地等待直到玩完才能轮到自己。这就是 互斥Mutual Exclusion概念任意时刻只允许规定数量的进程或节点访问临界区其余进程只能排队等待。
临界资源在例子中即为玩具在分布式系统中可能是某个文件、数据库记录、硬件设备等。竞态多个进程同时争夺同一个资源时发生竞争。互斥每次只允许一个进程进入临界区其他进程只能先等待。
在单机单台服务器环境下各进程共享同一台机器的内存和时钟常用信号量、互斥锁等机制即可实现。但在分布式系统中进程分散在不同的网络节点上通信必须经过网络面临以下几个挑战 互联网特性 不同节点通过网络传输消息会有网络延迟、丢包或乱序等不确定性。节点彼此没有共享内存只能依赖消息传递来协调对临界资源的访问。 没有统一时钟 各节点各自拥有物理时钟难以做到完全同步。如果无法知道谁先谁后就无法保证公平先来后到需要引入逻辑时钟或其他机制来解决。 节点或网络故障 某个节点或链路出现故障时如何检测并进行故障恢复才能保证系统依旧可用且不会长时间阻塞。
基于上述特性分布式互斥算法应当满足
互斥性任何时刻最多只有一个节点能够进入临界区。无饥饿无饿死每个请求都能在有限时间内得到满足不会无限期等待。无死锁避免多个节点相互等待对方持有的资源从而导致整体停滞。公平性先发出请求的节点应当先获得访问权或至少不会被长期“插队”。 2. 分布式互斥算法分类
常见的分布式互斥算法可分为三大类本文重点介绍以下三种 集中互斥算法Centralized Algorithm 核心思想引入一个全局 “协调者Coordinator”所有节点的访问请求都交由它来排序和授权。 基于许可的互斥算法Permission-Based Algorithm 核心思想想要进入临界区的节点需要向系统中其他节点请求许可Permission只有获得足够许可后才能访问。 代表算法 Lamport 算法Richard Agrawal 算法 令牌环互斥算法Token Ring Algorithm 核心思想在所有节点之间形成一个逻辑环只有持有 “令牌Token” 的节点才能访问临界区令牌在环上顺序传递。
下面分别详细讲解三种算法的工作原理、消息流程与优缺点。 3. 集中互斥算法
3.1 核心思路 系统中预先选举出一个节点作为 “协调者Coordinator”。 当某个进程节点 Pi 想访问临界资源时向协调者发送 REQUEST(Pi) 消息。 协调者维护一个本地的“请求队列按先后次序”。 若此时没有其他节点在使用资源则直接向 Pi 发送 GRANT(Pi)Pi 收到后即可进入临界区。若已有其他节点持有该资源则把 Pi 的请求追加到队列尾等待前面的节点释放后再处理。 当 Pi 使用完毕后向协调者发送 RELEASE(Pi)协调者收到后从请求队列中弹出下一个节点 Pj并向其发送 GRANT(Pj)Pj 再进入临界区。
3.2 关键特性
互斥保证协调者一次只能向一个节点发放 GRANT确保只有一个节点能够访问。先来后到协调者将所有请求排队根据请求到达时间顺序依次授权。避免饥饿如果某节点长时间占用或宕机协调者可检测超时并将其移出队列或让其“自动释放”从而让后续请求有机会执行。
3.3 消息交互流程以两个节点 P1、P2 为例详见图 3-1
图 3-1集中互斥算法消息流程示意P1 协调者 P2
(1) REQUEST(P1) ──────→ 存入队列[(P1, TS1)]
(2) GRANT(P1) ←────── ←────── REQUEST(P2)更新队列[(P1, TS1), (P2, TS2)]
(3) P1 进入临界区
(4) RELEASE(P1) ──────→ 更新队列[(P2, TS2)]
(5) GRANT(P2) ←──────
(6) P2 进入临界区
(7) RELEASE(P2) ──────→ 空队列第 1 步P1 向协调者发送 REQUEST(P1)时间戳记为 TS1。协调者将 (P1, TS1) 加入本地队列。第 2 步发现队列仅有 P1直接向 P1 返回 GRANT(P1)。此时 P1 进入临界区。第 3 步P2 请求到达发送 REQUEST(P2)时间戳记为 TS2TS2 TS1。协调者将 (P2, TS2) 加入队列尾。第 4 步P1 使用完成后发送 RELEASE(P1)。协调者将 P1 从队列中移除只剩 (P2, TS2)于是向 P2 发放 GRANT(P2)。第 5 步P2 收到 GRANT 进入临界区使用完后再通知 RELEASE(P2)队列空。
3.4 优缺点分析 优点 实现简单理解直观每次临界区访问仅需 3 次消息REQUEST → GRANT → RELEASE。 缺点 单点故障协调者若发生故障整个系统无法继续扩展性差协调者会成为性能瓶颈随着节点数增多排队和消息处理压力变大协调者可能出现宕机或网络隔离需要额外的故障检测与选举机制。 4. 基于许可的互斥算法
当系统规模扩大时如果依赖单一协调者瓶颈和单点故障问题更严重。基于许可的互斥算法没有集中节点而是由各个节点之间互相“投票”或“许可”来决定谁先进入临界区。典型代表有 Lamport 算法和 Richard Agrawal 算法它们都基于逻辑时钟与请求队列来保证先来后到与互斥。
4.1 Lamport 算法
4.1.1 核心思想 逻辑时钟Logical Clock 每个节点 Pi 维护一个本地逻辑时钟 Li初始值为 0。当 Pi 发出临界区请求时先执行 Li Li 1并将新的 Li 作为时间戳 TSi 发送给其他节点。当 Pj 接收到一条请求消息或 RELEASE时先将本地时钟更新为 Lj max(Lj, TSi) 1再处理消息。 请求队列Request Queue 每个节点维护一个本地请求队列队列中元素为 (节点ID, 时间戳)按时间戳从小到大排序。如时间戳相等则按照节点 ID 从小到大排序。 当 Pi 发出 REQUEST(Pi, TSi) 时会将自己这一请求加入本地队列并向其它所有节点广播 REQUEST(Pi, TSi)。 当 Pjj ≠ i收到 REQUEST(Pi, TSi) 后 更新本地逻辑时钟Lj max(Lj, TSi) 1将 (Pi, TSi) 插入本地请求队列向 Pi 发送一条 REPLY(Pj, Lj)表明已许可。 进入临界区的条件 Pi 只有在以下两种条件同时满足时才可进入临界区 本地队列中排在最前时间戳最小且 ID 最小已收到来自所有其他节点的 REPLY 消息。 当 Pi 进入临界区并使用完毕后向所有节点广播 RELEASE(Pi, TSi’)TSi’ Li 1各节点收到后 更新本地逻辑时钟Lj max(Lj, TSi) 1从本地请求队列中删除 (Pi, …) 这样排在下一位的节点即可进入临界区。
4.1.2 消息流程示意图 4-1
图 4-1Lamport 算法消息交互3 个节点 P1、P2、P3P1 P2 P3
1L1 L11TS11请求REQUEST(P1,1) ──→更新 L2max(L2,1)12本地队列插入 (P1,1)←── REPLY(P2,2)更新 L3max(L3,1)12本地队列插入 (P1,1)←── REPLY(P3,2)2P1 收齐 P2、P3 的 REPLY且自己在 3 个节点队列中排第一→ 进入临界区3使用完毕L1 L1 1 2广播 RELEASE(P1,2)P2、P3 更新时钟并删除 (P1,1)4此时本地队列中可能有 (P2,2)、(P3,2) 等请求根据时间戳和节点 ID 排序让下一位进入消息数量每次进入临界区需发送 n – 1 条 REQUEST广播给其它节点n – 1 条 REPLY每个节点一个n – 1 条 RELEASE广播。 共计 3(n − 1) 条消息。
4.1.3 特点与适用场景 优点 无集中节点无单点故障基于时间戳排序保证先到先得具有公平性不存在死锁或循环等待。 缺点 通信开销较大消息数随节点数线性增长适合节点规模较小、临界资源请求频率相对较低的场景每个节点需维护本地请求队列存储开销为 O(n)。 4.2 Richard Agrawal 算法
4.2.1 算法思路
Richard Agrawal 算法是在 Lamport 算法基础上的改进目的是减少消息开销将原本的 RELEASE 与 REPLY 合并以降低通信量。主要思路如下 发送请求 当 Pi 想进入临界区时 将本地逻辑时钟 Li Li 1得到时间戳 TSi将 (Pi, TSi) 插入本地请求队列向其它所有节点广播 REQUEST(Pi, TSi)。 接收请求并判断 Pjj ≠ i收到 REQUEST(Pi, TSi) 后 更新本地逻辑时钟 Lj max(Lj, TSi) 1 若 Pj 当前 没有正在等待或占用临界资源则立即给 Pi 回复 REPLY(Pj, Lj) 若 Pj 正在等待或访问临界资源则比较 (TSj, Pj) 与 (TSi, Pi) 若 (TSi, Pi) 排在前面时间戳更小或时间戳相同且 ID 较小则等待并暂时不回复否则即 Pj 的请求优先级更高向 Pi 立刻回复 REPLY(Pj, Lj)但 Pj 本地继续排队。 将 (Pi, TSi) 插入本地请求队列按时戳排序。 进入临界区的条件 Pi 必须从所有 n – 1 个节点都收到 REPLY并且在自己本地队列中排在最前方能进入临界区。 使用完成后 Pi 进入临界区使用完成后将 (Pi, …) 从本地队列中删除并向本地队列如果有最前面的下一个节点发送 “伪 REPLY”即代替 RELEASE 的作用让该节点尝试进入。 其余节点在收到 “伪 REPLY” 时也会将 (Pi, …) 从自己的本地队列中删除并检查本地队列头部如果自己排在最前且已收到所有许可就可进入临界区。
4.2.2 消息流程示意图 4-2
图 4-2Richard Agrawal 算法消息流程3 个节点 P1、P2、P3P1 P2 P3
1L1 L1 1TS1 1请求REQUEST(P1,1) ──→ 更新 L2 max(L2,1)1 2本地队列插入 (P1,1)P2 无本地请求 → 立即 REPLY(P2,2)←──更新 L3 max(L3,1)1 2本地队列插入 (P1,1)P3 无本地请求 → 立即 REPLY(P3,2)←──2P1 收到 P2、P3 的 REPLY且本地队列头为 (P1,1)→ 进入临界区3使用完毕删除本地队列中 (P1,1)向本地队列中后续进程 “发送 REPLY” —— 假设本地队列后续为 (P2,2)则发送 REPLY(P2, …)允许 P2 进入。4其余节点收到 P1 的删除信号后也将 (P1,1) 从本地队列删除 若本地队列头为自己且已收到所有许可则进入临界区。4.2.3 特点与对比 消息开销 相比 Lamport 算法的 3(n − 1)Richard Agrawal 算法每次只需 2(n − 1) 条消息 一轮 REQUEST 给其他 n − 1 个节点收到的 n − 1 条 REPLY 即可进入使用完成后节点会“顺便”触发对下一个队列头的 REPLY 合并了原来的 RELEASE 优点 与 Lamport 算法相比消息量减少通信效率更高依旧使用时间戳排序保证先来后到公平性较好 缺点 相对于集中式或令牌环算法存储开销仍为 O(n)需要维护本地请求队列、逻辑时钟算法逻辑略微复杂 适用场景 中等规模节点数不太大且资源竞争不太频繁的场景希望在去中心化的同时尽量减少通信开销。 5. 令牌环互斥算法
5.1 核心思路
系统中将所有节点按某种顺序构成一个逻辑环Ring。整个系统中仅保有一个 “令牌Token”它代表了访问临界区的唯一许可。只有持有令牌的节点才能进入临界区使用完毕后必须将令牌传给环上的下一个节点。若节点收到令牌但不需要访问临界区则直接将令牌传给下一个。
只要令牌在系统内部一直循环传递就能保证
互斥性同时只有一个令牌自然只有一个节点能进入临界区公平性令牌按固定顺序依次传递每个节点都能轮到消息开销可控令牌在环上每传递一次记为 1 条消息若环上有 n 个节点则令牌完整绕行一圈需 n 条消息平均到每个请求上的消息开销约为 n/2。
5.2 消息流程示意图 5-1
图 5-15 个节点构成的令牌环示意P1 → P2 → P3 → P4 → P5 → P1循环1假设初始令牌在 P1若 P1 需要访问 P1 收到令牌 → 进入临界区 → 使用完毕 → 发送 TOKEN → P2 2若 P2 在收到令牌时不需要访问则直接 “转发” 令牌 P2 将令牌发送给 P3 → … 3若 P3 需要访问则 P3 收到令牌 → 进入临界区 → 使用完毕 → 发送 TOKEN → P44依此循环令牌永远在环上移动每个节点最终都能获得令牌。消息数每次令牌传递算作 1 条消息。若某个节点从请求到实际获得令牌需要等待 k 步则消息数为 k 直到令牌传到为止。
5.3 特点与缺点 优点 无需广播仅在相邻两节点之间传递令牌通信开销较小保证了先来后到的“轮询”机制公平性好不存在死锁只要令牌不丢失节点始终能轮到。 缺点 令牌丢失风险若持有令牌的节点宕机或网络隔离令牌就会丢失整个系统无法访问临界区需额外机制检测并重建令牌环重构复杂节点加入或退出都会破坏原有环需要重新组织环拓扑且重构过程中无法使用临界资源延迟受环大小影响若环上节点数较多则令牌传递到某一节点的延迟线性增大不适合大规模场景 适用场景 节点数量有限小规模系统资源访问频率高且使用时间短网络相对可靠、节点变动较少的场景。 6. 三种算法对比小结
算法名称消息开销互斥保证公平性单点故障扩展性适用场景集中互斥算法3 条REQUEST→GRANT→RELEASE绝对互斥先来后到存在单点故障较差小规模、对延迟要求不高的场景Lamport 算法3(n − 1) 条无单点故障严格基于时间戳无单点故障中等节点数不多、资源请求较频繁的场景Richard Agrawal 算法2(n − 1) 条无单点故障基于时间戳无单点故障中等想在 Lamport 基础上减少消息量的场景令牌环互斥算法每次令牌传递 1 条 → 平均 n/2 条无单点故障 若令牌丢失则宕机轮询公平令牌丢失视为故障较差 环受拓扑限制小规模、节点变动少、资源访问频繁且快的场景 6.1 选型建议 系统规模很小节点数 ≤ 10且对延迟要求不高 可以考虑集中互斥算法实现最简单但要保证协调者高可用 系统规模中等节点数约 10 – 50去中心化又希望保证较高公平性 可优先选择 Richard Agrawal 算法由于消息量比 Lamport 算法少且同样保证先来后到 系统规模小且临界资源访问速度快、频率高 令牌环互斥适合令牌在环上快速循环通信开销低但必须保障令牌不会丢失环重构开销也要评估 系统需要高度容错、节点可能频繁增删 Lamport 算法更易于动态扩展不用维护环结构但通信成本更高 7. 总结
分布式互斥算法的核心目标在无共享内存、无全局时钟的分布式环境下通过消息传递保证临界资源的互斥访问避免并发冲突、死锁与饥饿。集中互斥算法思想最简单、通信量最少但存在单点故障和可扩展性差的问题基于许可的互斥算法Lamport、Richard Agrawal去中心化、没有单点故障采用逻辑时钟保证先来后到通信开销随节点数线性增加令牌环互斥算法令牌唯一、通信开销低但令牌丢失或环结构变更的容错难度大。
不同场景应根据节点规模、资源访问频率、容错需求等综合考量选择最合适的分布式互斥算法。以上内容配以示意图力求图文并茂、层次清晰帮助您快速理解三类算法的工作原理和应用场景。
