西安商城网站建设制作,台州专业网站建设,北京建网站价格,wordpress admin-ajax.php远程sql注入漏洞文章目录 导图概述分布式系统的特性与挑战分布式互斥算法的目标分布式互斥算法集中互斥算法集中互斥算法示意图集中互斥算法流程 基于许可的互斥算法Lamport 算法示意图Lamport 流程 令牌环互斥算法令牌环互斥算法示意图 1. 集中互斥算法#xff08;Centralized Mutual Exclus… 文章目录 导图概述分布式系统的特性与挑战分布式互斥算法的目标分布式互斥算法集中互斥算法集中互斥算法示意图集中互斥算法流程 基于许可的互斥算法Lamport 算法示意图Lamport 流程 令牌环互斥算法令牌环互斥算法示意图 1. 集中互斥算法Centralized Mutual Exclusion工作原理优缺点适用场景 2. 基于许可的互斥算法Permission-Based Mutual Exclusion工作原理优缺点适用场景 3. 令牌环互斥算法Token Ring Mutual Exclusion工作原理优缺点适用场景 比较分析 导图 概述
分布式系统的核心特点是多个应用服务部署在不同的机器或网络环境中这些服务需要相互通信与协作。然而当多个服务同时访问共享资源时会产生互斥问题。例如当多个服务尝试修改同一数据时就会发生数据竞争导致数据不一致。
为了避免这种冲突需要通过互斥算法来控制对共享资源的访问确保同一时间内只有一个服务可以操作该资源。 互斥算法是理论基础在实际工作中我们会利用分布式锁来解决互斥问题 当多个应用服务共同完成一个任务时会出现分布式事务问题会使用分布式事务的原则和解决方案 应用和服务在集群部署情况下通常会有主从Master/Slave之分主服务器用来写入、读取数据从服务器Slave用来读取数据当主服务器出现故障时通常需要选举新的主服务器
分布式系统的特性与挑战
分布式系统中的进程互斥问题比单机模式下的互斥问题复杂得多主要由以下几个特性和挑战所构成 网络延迟和丢包分布式系统中的进程部署在不同的服务器上这些服务器通过网络相互通信。因此进程之间的请求和响应会受到网络状况的影响例如延迟、丢包和带宽限制等。这可能导致进程请求临界资源时的时序问题或者造成进程进入等待状态时不能及时获得资源。 无统一时钟在分布式系统中各台服务器通常有独立的物理时钟且不同机器之间的时钟并不完全同步。因此不能保证每个进程在相同的时刻获取资源或被通知资源释放。这给分布式互斥算法带来了一定的困难因为无法依赖系统时钟来协调进程的行为。 故障容忍与感知分布式系统中的每个进程和服务器可能会出现故障。如果某个进程或服务器在竞争资源时发生故障其他进程应该能够感知到并采取适当的处理措施。对于分布式互斥算法而言需要考虑如何在故障发生时保持系统的稳定性并确保故障恢复后不导致数据不一致或死锁。 分布式互斥算法的目标
在设计分布式互斥算法时必须确保以下几个关键特性 互斥性保证在任何时刻只有一个进程能够访问临界资源。也就是说进程必须能够协调访问临界资源防止多个进程同时操作资源造成数据不一致或资源冲突。 无饥饿任何申请访问临界资源的进程都最终能够获得资源避免某些进程因长时间等待而永远无法获得资源。为此算法需要在进程间合理调度资源避免出现无限等待的情况。 无死锁死锁是指两个或多个进程持有互相依赖的资源并互相等待对方释放资源导致系统无法继续执行。在分布式互斥算法中必须确保不会发生死锁。例如通过适当的资源请求和释放顺序、超时机制等方法避免死锁的发生。 公平性所有请求访问临界资源的进程都应该有公平的机会获得资源。也就是说应该避免某些进程长期无法获得资源而其他进程不断获得资源。算法应当保证请求资源的顺序和优先级是公平的。 分布式互斥算法
集中互斥算法
集中互斥算法的核心是增加一个全局协调者由该协调者帮助进程访问并使用临界资源。
集中互斥算法示意图 当节点进程 1 和节点进程 2 都想访问临界资源时
首先向协调者发起申请协调者会将这两个节点进程放到自己本地的顺序链表中这个链表就像一个等待队列节点进程和申请访问资源的时间戳都记录在其中。各节点进程会按照自己在顺序链表中的排列顺序访问临界资源从而保证了互斥性。另外如果一个节点进程长时间使用资源而不释放或者由于内部、网络故障无法正常工作协调者都可以将其从顺序链表中移除让后面排队的节点进程得到资源的访问权限这也保证了进程访问的无饥饿。
集中互斥算法流程
(1) 节点进程 1 率先向协调者发起访问临界资源的请求其请求时间戳记作时间戳 1。协调者会在本地维护一个针对此临界资源的链表其中记录着发出请求的节点进程和请求时间戳。(2) 此时节点进程 2 也向协调者发出访问临界资源的请求由于请求时间比节点进程 1 稍晚一点所以请求时间戳记作时间戳 2同样协调者会在临界资源访问链表中插入这条请求记录。由于此次请求的时间晚于节点进程 1因此节点进程 2 排在节点进程 1 后面。(3) 协调者通过临界资源链表中各节点进程的排列顺序选择第一个节点使之获得访问临界资源的权限。这里的第一个节点是节点进程 1因此就给节点进程 1 返回临界资源。(4) 节点进程 1 接收到协调者返回的可访问临界资源的消息就会去访问临界资源。访问完毕后节点进程 1 主动通知协调者已访问完毕。(5) 协调者接收到消息后查看链表发现节点进程 1 后面排着的是节点进程 2于是通知节点进程 2 临界资源可用了。(6) 节点进程 2 接收到协调者的通知后开始访问临界资源同样使用完毕后会通知协调者。 不难看出在集中互斥算法中每个节点进程要想获取一次临界资源的访问权限都需要进行三次消息交互。
第一次向协调者发送访问临界资源的请求。第二次协调者通过链表中进程的先后次序选择排在最前面的节点进程向其发送资源可用的消息第三次节点进程在使用完临界资源后通知协调者。
集中互斥算法引入了协调者解决资源互斥问题其中协调者需要面对所有节点进程的资源请求在高并发系统中有可能成为系统瓶颈同时可能出现单点故障。因此这种算法需要考虑协调者的可用性和可扩展性 基于许可的互斥算法
基于许可的互斥算法的思想是当进程访问临界资源时先向分布式系统中的其他节点发送请求请求获取临界资源的使用权限等得到所有节点或者部分节点的同意后方可访问临界资源。
Lamport 算法是许可算法的一种该算法中提到了逻辑时间戳的概念解决了分布式系统中没有统一时间戳的问题。由于分布式系统没有统一的时钟因此无法知道各个进程申请访问临界资源的先后顺序。
在集中互斥算法中是通过协调者记录先后顺序的而在 Lamport 算法中每个节点进程都会维护一个逻辑时钟当系统启动时所有节点上的进程都会对这个时钟进行初始化每当节点进程向其他节点进程发起临界资源访问申请的时候就会将这个逻辑时间戳加 1。
同样每个节点进程在接收到来自其他节点进程的申请请求时也会更新自己的逻辑时钟具体地对自己逻辑时钟与发出请求的节点的逻辑时钟进行比较选出最大值后加 1。
在 Lamport 算法中根据逻辑时钟的大小来选择由哪个节点进程获取临界资源的访问权限逻辑时钟最小的节点将首先获得临界资源的使用权如果逻辑时钟相同就让节点编号较小的进程使用资源。
同时每个节点进程都会维护一个请求队列这个队列按照时间戳的优先级对各节点进程的请求进行排序时间戳越小的节点进程排在越前面。
Lamport 算法示意图
Lamport 算法对时间戳的计算过程总结如下
每个节点进程在初始化时时间戳为 0当节点进程发起资源使用申请时将其自带的时间戳加 1发起申请的节点进程将节点编号和时间戳一起发送给分布式系统中的其他节点其他节点接收到申请消息以后更新本地的时间戳更新公式是 Max本地时间戳消息中的时间戳 1
节点进程对系统中其他节点进程发送请求时会使用三种消息类型分别是 REQUEST、REPLY 和 RELEASE。每种消息都包含发送节点的 ID 和逻辑时钟 Lamport 流程
(1) 节点进程 1 完成对时间戳的初始化以后需要访问临界资源于是通过 REQUEST 消息将节点 ID 和时间戳发送给节点进程 2 和节点进程 3。(2) 节点进程 2 和节点进程 3 接收到请求以后根据 Lamport 算法更新本地的时间戳同时将节点进程 1 的请求添加到本地的资源访问链表中。这样做的目的是如果此时还有其他节点也在申请访问资源那么根据时间戳算法其他节点的时间戳比节点进程 1 大因此在链表中排在节点进程 1 后面。排队以后节点进程 2 和节点进程 3 会发送 REPLY 消息给节点进程 1也就是许可节点进程 1 对临界资源的访问。(3) 节点进程 1 接到许可信息以后对临界资源进行访问。(4) 节点进程 1 访问完资源以后会向节点进程 2 和节点进程 3 发出 RELEASE 消息这两个进程接收到消息以后会把节点进程 1 从链表中删除此时如果链表中还排列着其他节点进程的请求则会重复第 (2) 步
按照 Lamport 算法的思路在一个含 n节点的分布式系统中访问一次临界资源需要发送 3 (n1) 次消息其中 REQUEST、REPLY 和 RELEASE 消息各发送 n1 条。发送过多的消息容易导致网络堵塞因此 RichardAgrawal 算法对 Lamport 算法进行了改进将 Lamport 算法中的 RELEASE 消息和 REPLY 消息合并为一个这样消息的发送次数就从 3(n1) 降到了 2(n1)。
在 RichardAgrawal 算法中节点进程访问临界资源时发送 REQUEST 消息到其他节点进程其他节点进程接收到请求后做以下动作如果自己没有访问临界资源就直接返回 REPLY 消息允许发送请求的节点进程访问如果自己正在访问临界资源就对自己和发送请求的节点的时间戳进行排序若后者的时间戳排在前面则不回复任何消息否则返回 REPLY 消息允许其访问临界资源。请求节点接收到 REPLY 消息以后对临界资源进行访问访问完成后向请求访问链表中的请求节点发送 REPLY 消息链表中的节点根据优先级发送下一轮的资源访问请求。
由上面两个算法的原理可以看出基于许可的互斥算法是一个会征求每个进程意见的公平算法但随着系统中访问资源的进程增加其他通信成本也会变多。因此这种算法可以用在临界资源使用频率较低且系统规模较小的场景 令牌环互斥算法
令牌环互斥算法中的所有节点进程构成一个环结构每个节点进程都有一个唯一 ID 作为标识且都会记录对应前驱节点和后继节点的地址。令牌作为访问临界资源的许可证会按照一定方向顺时针、逆时针在节点进程之间传递收到令牌的节点进程有权访问临界资源访问完成后将令牌传送给下一个进程若拿到令牌的节点进程不需要访问临界资源则直接把令牌传递给下一个节点进程
令牌环互斥算法示意图 令牌环互斥算法的优点显而易见令牌具有唯一性每个时刻只有一个节点进程可以访问临界资源能够解决分布式系统中临界资源的互斥问题由于令牌在环中传递因此每个节点进程都有获得资源访问权的机会不会出现饥饿的现象保证了公平性在令牌环中一个进程访问临界资源最多需要 n1 条消息n是环上的节点进程数量也就是令牌在环内循环一周发送的消息数
不过该算法同样存在缺点就是令牌一旦丢失恢复起来会比较困难令牌的唯一性导致该算法容错性比较低。而且在令牌环中如果节点进程发生变动例如有节点进程加入或者退出则会导致整个令牌环重构在重构过程中节点进程是不能访问临界资源的。即使环内的节点进程对临界资源访问频率较低令牌也会不断地在环中传递这样的行为会造成较大的资源浪费。因此令牌环互斥算法适用于系统规模较小系统中临界资源使用频率较高、使用时间较短的场景。 1. 集中互斥算法Centralized Mutual Exclusion
集中互斥算法通过引入一个中心节点协调者来管理所有进程对临界资源的请求。所有进程必须向这个中心节点请求资源当中心节点允许某个进程访问资源时它才会进入临界区。
工作原理
每个进程都向协调者发送请求表明自己希望访问临界资源。协调者收到请求后根据一些调度策略通常是先到先服务的顺序决定哪个进程可以进入临界区。当一个进程完成资源访问后协调者会向其他等待的进程发送允许消息允许它们进入临界区。
优缺点
优点 简单易实现集中式管理方式非常直观算法实现简单。通信开销小进程只需与一个协调者进行通信避免了多进程之间复杂的通信。 缺点 单点故障问题如果协调者进程发生故障系统就会失去互斥控制导致整个系统的临界区访问控制失败。扩展性差随着系统规模的增大集中式方案的协调者会成为瓶颈导致性能下降。
适用场景
集中互斥适用于节点数量较少或系统规模较小的分布式系统特别是在故障不常发生的环境中适用于管理资源简单的场景。 2. 基于许可的互斥算法Permission-Based Mutual Exclusion
基于许可的互斥算法通常采用投票机制进程在访问临界资源前必须获得多数或一定数量的“许可”才能进入临界区。这种机制是分布式系统中常见的一种互斥方式常见的基于许可的算法包括Quorum算法和Paxos协议。
工作原理
系统中有多个进程且每个进程有权对请求的进程进行许可投票。当进程需要访问临界资源时它会向其他进程发送请求请求其他进程的许可。一旦进程获得了足够数量的许可通常是全体或多数进程的同意它就可以访问临界区。进程完成对临界资源的访问后释放资源并通知其他进程。
优缺点
优点 容错性高即使某些进程或节点发生故障其他进程仍然可以继续通过投票机制获取许可不会导致系统停止工作。灵活性强可以根据需要设置许可的数量从而灵活控制资源访问。 缺点 通信开销大每次请求都需要向多个进程请求许可可能导致通信延迟和性能瓶颈。复杂性高需要确保在大规模系统中许可机制不会导致过度的冲突和重复请求。
适用场景
适合于节点较多、需要高容错性和灵活配置的分布式系统。常用于高可用、高容错的分布式数据库、分布式锁等应用中。 3. 令牌环互斥算法Token Ring Mutual Exclusion
令牌环算法是一种基于传递令牌的分布式互斥算法。在这种算法中所有进程形成一个环状拓扑结构令牌是控制资源访问的唯一标识。进程必须获得令牌才能访问临界资源。
工作原理
系统中每个进程都有一个唯一的标识并按逻辑顺序排列成一个环。令牌在这些进程之间传递只有持有令牌的进程才能访问临界资源。当一个进程完成资源访问后它将令牌传递给下一个进程或者如果环中的进程都没有请求资源则令牌会继续传递。如果某个进程发生故障系统中的其他进程会通过重新传递令牌来恢复正常的操作。
优缺点
优点 高效令牌传递过程非常简单每次访问临界资源的过程都非常清晰。无需复杂的协调不像集中式互斥那样依赖单个协调者令牌环算法通过自然的环形拓扑减少了协调的复杂性。 缺点 单点故障问题令牌丢失或进程故障时可能导致整个系统无法继续工作尽管可以通过恢复机制解决但依然存在风险。环的管理系统需要维护一个稳定的环结构一旦进程加入或离开环可能需要重新配置。
适用场景
适合于需要简单、可扩展的分布式系统。令牌环算法特别适用于对实时性要求高、系统拓扑比较固定的环境中。
比较分析
算法类型优点缺点适用场景集中互斥算法实现简单通信开销小单点故障扩展性差小规模分布式系统节点故障少的环境基于许可的互斥算法高容错性灵活配置通信开销大复杂性高高可用、高容错的分布式系统令牌环互斥算法高效、无需复杂协调拓扑结构简单单点故障问题环结构管理较复杂需要简单、可扩展的分布式系统
