分布式系统复习纲要-2016秋
整理者@吃瘪王
分布式系统模型
什么是分布式系统?
分布式系统是若干独立计算机的集合,它们对于用户来说就像单个一致的系统。
A distributed system is a collection of autonomous computing elements that appears to its
users as a single coherent system.
分布式系统的目标?分布式系统透明性和
开放性的含义。
Making resources available 资源可访问
Distribution transparency 透明性
访问透明性:隐藏数据表示形式以及访问方式的不同。
位置透明性:隐藏数据所在位置。
迁移透明性:隐藏资源是否已移动到另一个位置。
重定位透明性:隐藏资源是否在使用中已移动到另一个位置。
复制透明性:隐藏资源是否已被复制。
并发透明性:隐藏资源是否由若干相互竞争的用户共享。
故障透明性:隐藏资源的故障和恢复。
持久性透明性:隐藏资源(软件)位于内存里或在磁盘上。
Openness 开放性
能够与其他通过服务交互而不用考虑底层环境
符合明确定义的接口
支持应用的可移植性
易于互操作
屏蔽底层环境的区别
Scalability 可扩展性
为什么要分布式?
Economics(经济性)
Speed(速度)
Inherent distribution(固有的分布性)
微处理器能提供比大型机更好的性价比
分布式系统能提供比大型机更强的计算能力
有一些应用包含物理上分布的机器
Reliability(可靠性)
Incremental growth(可扩展性)
当某台机器崩溃时,整个系统仍能正常工作
计算能力逐步增加
分布式系统的种类
分布式操作系统
分布式操作系统具有较好的透明性和易用性,但没有对相互独立的计算机集合的操
作处理能力。
网络操作系统
网络操作系统有良好的可扩展性和开放性,但对透明性和易用性比较差。
基于中间件的系统。
在网络操作系统之上增加一个中间层,屏蔽各底层平台之间的异构性,从而增加分
布式系统的透明性
分布式系统的类型
分布式计算系统
集群计算
单个节点管理
节点集中,几乎相同
网格计算
节点分散,异构
分布式信息系统
目前使用的大量分布式系统是传统信息系统的形式,现在集成了遗留系统。
例如:事务处理系统
分布式普适系统
新兴的下一代分布式系统,其中节点小,移动,并且经常嵌入在更大的系统中,其
特征在于系统自然地混合到用户的环境中。
分布式系统架构
分布式系统架构风格
分层体系结构(layered architectures)。
在该风格中,组件被组织成若干个层次,第 L 层的组件允许请求 L-1 层以及更低层
次组件的服务,但却不能请求更高层次组件的服务;第 L 层的组件向更高层组件提
供服务。这种风格广泛应用与互联网中。
基于对象的体系结构(object based architectures)。
这种体系结构大概是面向对象程序设计的结果。在这种风格中,对象对应于我们前
面提到的“组件”,一个对象通过远程方法调用请求另一个对象的服务。对象之间没
有明显地层次关系和层次约束。
以数据为中心的体系结构(data-centered architectures)。
在这种风格中,存在一个共用的数据仓库(基于文件系统的或者基于数据库的),
组件主要通过这个数据仓库进行通讯、协作(如通过读写文件、文件锁或者读写数
据库表)。很多基于 web 的系统都采用了这种方式。
基于事件的体系结构(event-based architectures)。
在这种风格中,组件主要是事件驱动的,组件间的通讯主要通过事件的传播进行(事
件中可能携带某些数据)。在这种风格中,通常伴随着事件的 publish/subscribe
系统,使得某个组件可以发布(广播)事件,而这个事件会被自动传播到订阅了它
的那些组件那里。基于事件的体系结构常常和以数据为中心的体系结构配合使用。
分布式系统组织形式(Organization)
中心化体系结构 Centralized Architecture
基于 C/S 模型
系统中含有某些“中央节点“
中心化有多种情况
中心化的数据(如,所有的客户数据都在一个节点上)
中心化的服务(如目录服务只有一个节点提供)
中心化的算法(如,某个算法的完成,必须首先收集系统中所有的相关信息到
一个节点,由该节点完成计算后再分发结果)
对于系统的可扩展性有较大的影响,”中心“很可能会成为瓶颈,单点故障,扩展困难
无中心化体系结构 Decentralized Architecture
不再存在某类中央节点,每个节点的功能都是类似的或者说对称的
结构化 P2P
节点组织按照特定的分布式数据结构
非结构化 P2P
节点随意选择邻居
混合 P2P
一些节点以有序的方式被指定特殊功能
混合体系结构 Hybrid Architecture
客户端服务器端用 P2P 方式结合
边缘服务器结构, 用于 CDN(content delivery networks)
客户-服务器模式(C/S)和对等模式(P2P)
略
分布式系统组织为中间件
进程与线程
进程和线程
Processes vs. Threads
A process is different than a thread
Thread: “Lightweight process” (LWP)
An execution stream that shares an address space
Multiple threads within a single process
Example:
Two processes examining memory address 0xffe84264 see different values (I.e.,
different contents)
Two threads examining memory address 0xffe84264 see same value (I.e., same
contents)
代码迁移
代码迁移方法
迁移内容
代码部分 Code segment: contains the actual code
数据部分 Data segment: contains the state
执行状态 Execution state: contains context of thread executing the object’s
code
弱迁移
只迁移代码部分和数据部分,最后被目标进程或者另外一个独立的进程执行。
强迁移
移动组件,包括迁移执行部分(execution segment)
要么复制进程(正在执行的进程停下来,移动后再恢复)
要么克隆(所有数据完全复制到另外一台机器上,和原来的进程并行)
迁移和本地资源
对象可能使用在目标站点可用或不可用的本地资源
资源类型
固定资源 Fixed:资源不能迁移,如本地硬件
捆绑资源 Fastened:资源原则上可以迁移,但成本很高
独立资源 Unattached:资源可以轻松地随对象一起移动(例如缓存)
对象到资源绑定
通过标识符:对象需要资源的特定实例(例如特定数据库)
按值:对象需要资源的值(例如,缓存实体集合)
按类型:对象要求只有一种类型的资源可用(例如,颜色监视器)
在异构系统中的迁移
主要问题
目标计算机可能不适合执行迁移的代码
进程/线程/处理器上下文的定义高度依赖于本地硬件,操作系统和运行时系统
利用在不同平台上实现的抽象机
解释语言,有效地拥有自己的 VM
虚拟机(如前所述)
通信
通信的类型
持久与非持久(瞬时)
持久通信
通信机制本身会对消息进行持久存储,直到它被传递给目的。
消息的发送者和接收这不必同时存在(同时处于执行状态)。例如,电子
邮件是典型的持久通信。
非持久(瞬时)通信
消息的发送者和接收者必须同时存在才能进行,传输服务仅仅提供临时的对消
息的存储。
一旦发送者退出或者接收者退出,传输就会失败。例如,电话是典型的瞬
时通信。
同步与异步
同步通信
发信方在到达同步点前保持阻塞
异步通信
发信方发信后立即继续,消息存储在发信方主机或者通信服务器的缓冲区中
一次消息发送的过程中,可能存在若干同步点
消息提交
消息的发送者会阻塞,直到消息被成功提交给传输服务
消息交付
消息的发送者会阻塞,直到消息被接收者成功接收
消息请求结束
消息的发送者会阻塞,直到消息的接收者接收、处理消息、并且处理的结
果返回到发送者
离散消息和流式数据
离散消息
每个消息都是相对独立的
流式数据
一组消息按照指定的顺序排序后构成一个有意义的数据流
远程过程调用 RPC
RPC 的工作过程
1. 客户端代码获得 client stub 的一个实例,并调用该实例的服务方法 hello();
2.
client stub 的服务函数会创建一个消息,该消息包括调用的方法名、参数等相关信
息;
client stub 将创建好的消息通过 OS 的网络接口发送给服务器主机,阻塞等待服务
器主机返回结果;
server stub 接收到服务请求的消息,取出消息中的方法名、调用参数,实际调用服
务端该方法的实现;
3.
4.
5. 服务端该方法的实际实现完成相应的服务请求,并将结果返回给 server stub,在服
6.
7.
务端实现看来,这完全是一次本地的调用;
server stub 创建一个响应消息,并将结果放在这个消息中,通过 OS 的网络接口,
发送给客户主机;
client stub 获得响应消息,从中取得结果,并以方法 hello()的返回值的方式返回给
调用该方法的客户端代码;
8. 客户端代码继续执行,就好像调用了一个本地的方法一样。
故障处理
1. 客户无法定位服务器
使用特定的返回值(error)/异常处理;
让错误引发异常或信号
2. 客户发给服务器的请求消息丢失
设置一个计时器,超时重发;
3. 服务器发给客户的应答消息丢失
设置一个计时器,对于不幂等的请求,为客户请求分配序号,服务器区别不同的
请求;
4. 服务器在收到消息后崩溃(接受后执行前崩溃或者执行后发送前崩溃)
等待服务器启动,然后重发请求/立即放弃并报告失败/不做任何保证;
5. 客户机在发送消息后崩溃
消除 extermination: client stub 发送 RPC 前在日志文件中记录 RPC 请求,重启
后清除孤儿。
再生 reincarnation: 按时间顺序编号不同的时间段。当客户端重启时,广播一
条消息宣布新的时间段开始,当广播到达时终止所有远程计算。无需日志。
温和再生 gentle reincarnation: 与再生相似,但是当广播到达时,每台机器会
寻找远程计算的所有者,仅当找不到所有者时,计算才会被终止。
过期 expiration: 赋予每个 RPC 一个标准时间配额,未完成任务则明确申请额
外配额。
动态绑定
当客户端第一次调用其中一个远程过程,比如 read
客户端 stub 看到它还没有绑定到服务器,因此它发送消息到绑定程序请求导
入版本 x 的服务器接口
绑定程序检查一个或多个服务器是否已导出具有此名称和版本号的接口。
如果没有当前运行的服务器愿意支持此接口,则读取调用失败
如果存在合适的服务器,则绑定器将其句柄和唯一标识符提供给客户端
stub
客户端 stub 使用句柄作为向其发送请求消息的地址。该消息包含参数和唯一
标识符,服务器的内核使用该标识符将传入消息定向到正确的服务器
优点
灵活性
可以支持多个支持同一接口的服务器,例如:
绑定程序可以随机地在均衡负载的服务器分配客户端
绑定程序可以定期轮询服务器,自动取消注册失败的服务器,以达到一定
的容错能力
绑定程序可以帮助身份验证
绑定程序可以验证客户端和服务器都使用相同版本的接口
缺点
导出/导入接口的额外开销花费时间
绑定程序可能成为大型分布式系统中的瓶颈
基于消息的通信
略
命名
命名方式和命名需求
Three Kinds of Naming
Human-friendly name: f1, cs.nju.edu.cn
may refer to several identities
Address: name of an access point, entity’s address
202.119.32.6
May be moved;
An entity can offer more than one access points.
Identifier: a name has properties:
an identifier refers to at most one entity
each entity is referred to by at most one identifier
an identifier is never reused
Ethernet address?