CyannyLive

AI and Big Data

分布式系统总结Part1

激动哥给了一些点,总结如下吧,算是对分布式的一些理解,希望对朋友们有帮助。

分布式系统系统基本概念

分布式系统是若干独立计算机的集合,这些计算机对于用户来说就像单个相关系统。透明性, 故障透明性。

本质: 硬件上——机器是物理上独立的。软件上——对用户来说它们就像载和单个系统打交道。分布式系统位于用户的应用层和底层操作系统之间,有时也叫做中间件.

分布式系统的目标:资源链接和共享,透明性,开放性,可伸缩性。[more…]

分布式系统作为中间件技术

  1. 中间件在分布式系统中的位置

    中间件:在应用系统和网络系统之间的附加的软件层,隐藏网络操作系统中低层平台集合的异构性,提供一组完整程度不同的服务集,提高分布的透明性。

    中间件的最高目标是透明性。同时也具有开放性、可扩展性和易用性

  2. 中间件模型

  • 基于分布式文件系统:任何东西都是作为文件来处理,只对传统文件支持分布的透明性,比网络操作系统前进了一小步,仍然要求进程显式启动分布式机器,有一定的扩展。
  • 基于RPC:允许进程调用位于远程机器上的过程实现来隐藏网络通信。调用参数透明的传递到远程机器上,看起来就像在调用本地的进程一样,不知道网络通信的发生。
  • 基于分布式对象: 调用分布在远程机器上的对象的接口,通过消息传递调用

3.中间件通信技术

(1) RPC

使用客户端存根和服务器端存根,实现访问的透明性,按值传递,对引用传递的支持比较弱, 基于响应的暂时同步通信。

(2) RMI——远程对象调用

不使用用客户端存根和服务器端存根,使用针对对象的存根。本质上是RPC,但针对远程对象。

(3) MPI:面向消息的通信

RPC和RMI的不足:要求远程机器正在执行; 并且对同步要求高,客户在发出请求后阻塞

通信类型:持久通信,暂时通信;异步通信,同步通信; 两两正交共四种。

•持久异步通信:如邮件系统,消息队列

•持久同步通信

•暂时异步通信:如异步RPC,UDP

•暂时同步通信:基于接收的暂时同步通信:最弱的基于消息接收机制; 基于交付的暂时同步通信;基于响应的暂时同步通信: RMI, RPC。

MPI比套接字提供更多的抽象的消息传递原语,提供持久异步通信,用在RPC和RMI不适用的场合,它们主要用来协助将高度分散的数据库集成进大规模信息系统中。其他的应用还包括电子邮件和工作流。

(4)面向流的通信:

流是一种完全不同的通信方式,它的主要问题是两个连续的消息是否有时间上的联系。如音频流和视频流,同步很关键。

在连续数据流中,每个消息都规定了端到端的最大延迟时间。另外,发送的消息还要受端到端最小延迟时间的约束。

三种传输模式

异步传输模式:数据项是逐个传输的,但是对某一项在何时进行传输并没有进一步的限制。

同步传输模式:数据流中每一个单元都定义了一个端到端最大延迟时间。

等待传输模式:模式中数据单元必须按时传输,也就是数据传输的端到端延迟时间必须同时受到上限和下限的约束,实时系统。

进程迁移

  1. 弱迁移 vs 弱迁移

    弱迁移:即代码的可移植性,只传输代码段以及某些初始化数据,传输过来的程序总是以初始状态重新开始执行,弱可迁移性只要求在目标机器上能执行该代码段,例如Java Applet小程序,这种方法的好处在于简单性。

    强迁移:迁移执行中的进程,先停止运行中的进程,捕捉运行现场,迁移到另一台机器上,从中断处继续运行,强迁移比弱迁移实现难度大,例如D’Agent是支持强可移动性的一个例子(Dartmouth College)

  2. 发送者启动迁移 vs 接收者启动迁移

    发送者启动迁移,代码或正在执行的进程在哪台机器上,就由该机器来启动迁移,例如向Web服务器发送搜索程序运行查询。这种迁移容易实现.

    接收者启动迁移,代码迁移的主动权在目标机器手中,例如Java Applet

    区别:接收者下载代码到客户端,性能好,安全性好,客户端只有少数的资源需要保护,如内存和网络连接等;

    发送者启动迁移,上传代码到服务器端,需要认证用户,需要对服务器资源提供强保护。

  3. 在目标进程内执行迁移代码 vs 在派生进程内执行迁移代码

三种方法相互正交,形成了8中进程迁移方法,如图:

Distributed System20

移动Agent的基本概念

  1. 定义:是一种分布式的应用,移动Agent是一个运行于开放、动态网络环境中的,封装良好的计算实体,可自主地在异构的网络上寻找合适的计算资源,然后移动到资源所在机器上使用这些资源,它代表用户自主地在网络上移动,完成指定的任务。移动Agent由数据、操作、行为规则 封装而成。

  2. 基本特点:

  • 自主移动性:不拘泥于初始执行结点,可再网络各主机间自主移动。移动Agent可以将自身的状态和代码从一个环境迁移到另一个环境,并恢复执行。
  • 协作性:移动Agent可以和其他Agent进行自主通信,协作完成任务。
  • 安全性
  • 移动功能而不移动数据,减少网络负担和延迟

Mogent解决移动通信失效

1.移动通信失效定义

移动Agent最大的特性是移动性,其通信机制要求位置透明性,可靠性,高效性,异步性,自适应性。但在Agent自主移动过程中,常会导致消息发送到某一网络节点但接收者已经离开无法收到消息的情况,这种因为目标Agent的物理位置变化造成通信不正常的现象称为移动Agent通信失效。通信失效与网络和节点故障无关,完全是由Agent的移动性造成的,这是移动Agent协作的致命缺陷。

2. Mogent系统架构

一个完整的移动Agent通信协议至少包括Agent寻址和消息传送两大部分。Mogent系统采用结构化旅行计划模型。

Mogent的架构中有两个重要实体:

  • Mogent: 即移动Agent,可以协同工作。
  • Host:一个物理节点的抽象,由IP地址或域名来标识,每一个Host安装MogentServer,维护管理本地的Mogent,主要由迁移子系统、通信子系统、安全子系统和开发监控子系统构成。

3.Mogent系统的寻址

Mogent-Server中有两个部件Home和Communicator完成Agent的透明寻址。

Home:记录Host上“出生的”Agent的动态信息,Agent每次迁移到另一台Host必须向出生地登记当前的地址和物理名,基于起始位置的定位。

Communicator:记录当前Host上所有agent的信息,Agent迁移时要向Communicator register 和 unregister, 负责agent之间通信的目标寻址、信件转发和通信失效排除等通信细节。

4.通信失效的解决:消息传送

通信失效问题本质上是通信和移动所共享的“位置”信息未同步造成的。
Mogent系统中引入了“状态”的概念,每个Agent的状态分为迁移态和静止态。

同时引入两个信号量进行集中式同步控制策略,通过Home-Communicator集中管理对目标Mogent的地址信息的互斥访问,从根本上避免通信失效的发生,保证通信的可靠性。

  • 迁移状态:由Home构件记录Agent的状态,当Mogent在一个Host上时状态为静止态,当按旅行计划准备迁移时Mogent要通知Home更新状态为迁移态。
  • 在途信件数:保存在Host上,记录当前时刻以该Mogent为通信对象的在途信件数,发出信件,在途信件数增加,信件到达,在途信件数减一

消息发送机制:Mogent通过控制“在途信件数”和“迁移状态”这两个信号量,确保消息发送者仅向处于静止状态的Agent发送消息

Mogent迁移机制:Agent只有在没有消息发送给他的情况下才能移动。

5.Mogent局限性

  • 频繁迁移,Home的地址注册开销大,会拥挤
  • Agent迁移受到信号量的限制,影响Agent的自主性和移动性

两种名称解析方法:递归和迭代

分布式系统中名称用来标识一个实体,有三种类型——名称、标识符、地址,名称解析就是查询名称的过程。

1.迭代名称解析

客户端把需要解析的名称路径发给根服务器root,根服务器解析出下一个服务器server1的地址返回给客户端,客户端再查询server1,server1再解析出server2的地址…

如此迭代直到能解析出所需实体的地址。例如:考虑绝对路径名:root:<nl, vu, cs, ftp, pub, globe, index.txt>的解析,第四章PPT上有详细的说明

总之迭代名称解析是客户端发起迭代查询。

2.递归名称解析

客户端把需要解析的名称路径发给根服务器root,根服务器解析出server1的地址后,不把结果返回给客户端,直接把名称传给server1,由server1解析后,再传给server2…不断递归,最后将解析出的实体地址返回给根服务器,根服务器再将实体地址返回给客户端。

3.两种解析的比较
递归名称解析的缺陷:要求每台服务器具有较高的性能,根服务器要完成完整的名称解析,开销较大,一般在名称空间的全局层中,采用迭代名称解析。

优点:与迭代名称解析相比,递归解析可以有效的使用缓存提高性能;减少了通信开销,通信开销取决于客户主机和服务器之间的信息交换。

而在DNS解析中:从客户机到本地DNS的查询是递归查询,从本地DNS到到其他DNS服务器之间的查询是迭代查询

移动实体的定位

移动实体的定位方法:使用与位置无关的标识符有效地实现定位。

1.广播和多播

原理:包含该实体所用标识符的消息会广播到每台机器上,并且请求每台机器查看它是否拥有该实体。只有能够为实体提供访问点的机器才会发送回复消息,回复消息中包含访问点的地址。类比ARP

缺点:扩展性不好,随着网络的膨胀,广播变得更加低效。

可以采用多播向特定的一组主机发送标识符,使用多播查找最近的复制实体,但实践证明,选择最近的复制实体没有那么容易。

2.转发指针

原理:每当一个实体转移到另一个位置时,他就会留下一个指针,说明它下一步所在的位置。 例如:当实体从A移动到B时,它将在A中留下一个指针,这个指针指向它在B中的新位置。

定位实体需要遍历转发指针形成的路线。为了避免形成太长的指针链,定期缩短指针链很重要。

优点:简便,一旦找到一个实体,就可以顺着转发指针链查找到实体当前的地址。

缺点:链可能特别长,定位实体的开销较大。链很脆弱,容易断开,只要一个转发指针丢失,就无法定位实体。一个解决办法是让指针链相对短一些,确保转发指针链的健壮性。
链中所有中间位置就必须维护它们的那一部分指针链。

3.基于起始位置的方法

原理:每当实体转移到一个地方时,他会通知起始位置,告诉起始位置自己当前的位置,在定位实体时,首先询问起始位置,以便了解实体的当前位置。起始位置就是创建实体的位置。

优点:大型网络中进行实体定位,如Mogent

缺点:为了与移动实体通信,需要先和起始位置通信,而起始位置和实体本身的位置处于完全不同的位置,增加了通信延迟。 使用起始位置,必须保证起始位置始终存在,否则将无法定位实体。起始位置如果转移到另一个网络,将会无法定位实体。一种解决的办法是:注册起始位置,客户先查找起始位置所在的位置,起始位置相对稳定,可以缓存它。

4.分层方法——创建一颗搜索树

原理: 网络划分成不重叠的分层域。只有一个顶级域,它覆盖了整个网络,每个域又可以划分为更多的子域。最低层的域叫做叶域,与网络中的局域网向对应。

每个层次的每个域都有关联的目录节点,目录节点会持续跟踪实体,形成目录节点树。

顶级域拥有每个实体的位置记录(指针),其中每条位置记录都存储一个指向更低层子域目录节点的指针

优点:查询操作是在局部进行,最差情况下,搜索会从叶域一直查到根域,再从根域到达包括该实体地址的子域。更新,插入和删除操作是局部进行:从叶节点到根节点。

缺点:第一, 定位实体的开销较大,从叶节点到根节点,再到叶节点。一种解决方法是采用指针缓存。第二,扩展性问题: 根节点需要存储所有实体的位置记录, 并为每个实体处理请求, 太多的查询和更新请求会成为瓶颈。解决办法是把根节点和其他高层目录节点划分成多个子节点,每个子节点处理实体的定位请求。
这些子节点最好均匀的扩散到网络中

资源

分布式系统总结part1 中间件,进程迁移,移动通信失效,名称解析,移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳,两大选举算法,三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性),容错(拜占庭将军问题,两阶段与三阶段提交)

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题

Copyright
© 2022 Cyanny Liang