分布式技术原理与算法解析之分布式互斥 学习笔记 （3）

• 2021 年 1 月 28 日
• AI
• 深度学习

• 背景：

对于同一个共享资源（什么是共享资源？），一个程序使用的时候不希望被其他程序打扰，即同一时刻只能有一个程序访问这种资源，这种共享资源称为临界资源（Critical Resource）,这种访问方式称之为分布式互斥（Distributed Mutual Exclusion）。

• 我们需要考虑的方面，（1）公平性（2）实时性（3）信息通信效率/沟通成本（4)健壮性
• 几种分布式互斥算法
  • 集中式算法（中央服务器算法）
    • 特点：唯一协调者，代表着集中程序或中央服务器。
    • 优势：（1）简单、直观、信息量少、易于实现（2）程序之间无需通信，效率高。
    • 劣势：（1）协调者性能瓶颈（2）单点故障问题（性能可靠性高的服务器很有必要）
    • 应用注意事项：中央服务器计算能力强、故障率低/注意时刻备份。
    • 三次信息交互：程序发送请求——>协调者发放授权信息——>程序释放授权信息。
  • 分布式算法（使用组播和逻辑时钟的算法）
  • 特点：程序之间互相平等，请求消息（请求的资源；请求者ID；请求发起的时间）需所有程序同一方可访问临界资源。
  • 优势：简单粗暴，易于实现，公平访问。
  • 劣势：若有n个程序需要访问临界资源，则会产生2n(n-1)次信息交互，特别不适合在大型系统中使用分布式算法，消息数量指数级增加，沟通成本高昂。
  • 应用注意事项：（1）实际可用性极低
  • 访问请求过多容易产生“信令风暴”。
  • 某一程序发生故障，无法发送同意信息，导致系统停滞。

（2）适合节点数目少且变动不频繁，由于每个程序都需要通信交互，适合P2P结构的系统。

（3）改进：程序故障直接忽略，但故障检测带来复杂性

• 典型场景：Hadoop中的分布式文件系统HDFS文件修改。
  

• 令牌环算法

  • 特点：令牌在由程序构成的环结构中传递（不管你需不需要，都得问你一句要不要），令牌在手，天下我有。
    

• 优点：（1）更高的通信效率，不用征求其他程序意见。（2）公平性很好。
  （3）健壮性好，令牌会跳过故障程序。

• 劣势：（1）无效通信（不管你需不需要，都得问你一句要不要）（2）实时性差，等待时间长。

• 应用注意事项：（1）适用于系统规模小且使用临界资源使用频率高且使用时间短的系统。（2）系统支持广播/组播通信模式，算法会更加高效。

• 典型场景：移动自组织网络系统（无人机之间的通信）

• 大规模系统中的分布式互斥算法（两层结构的分布式令牌环算法）

  • 特点：把整个广域网（多个局域网组成）系统中的节点组织成两层结构，在全局环与局域环存在两个令牌， 分别作用且局域环与局域环之间通过各自的协调进程进行通信。