review for distributed systems

复习的时候的提纲_(:3J

一些失误:

  • RPC没有看。包括动态绑定错误恢复
  • 容错的系统恢复、全局一致检查点的选择
  • Openstack还是瞎编的
  • 社交网络没有看。包括三种模型和那个什么最优化问题
  • 命名中的同步。集中式和分布式

分布式系统模型

什么是分布式系统?

一组匿名计算元素的集合,它使得在用户看来是一个单一连续(single coherent)系统一样

分布式系统的目标?

  • 使资源可用
  • 透明性
  • 开放性
  • 可扩展性

为什么要分布式

  1. 对于集中式系统的优点

    • 经济性 – 微处理器提供比大型机更好的性价比
    • 速度 – 分布式系统提供比大型机更强的运算能力
    • 固有的分布性 – 有一些应用需要空间上分割的机器
    • 可靠性 – 当某台机器崩溃时整个系统仍能正常工作
    • 可扩展性 – 计算能力可调节
  2. 对于独立PC的优点

    • 数据共享
    • 外设共享
    • 通信
    • 灵活性

透明性的含义

如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统,而不是独立的组件的集合,这样的分布式系统就成为透明的。
包括:

  • 访问透明性
  • 位置透明性
  • 迁移透明性
  • 资源分配透明性
  • 复制透明性
  • 并发透明性
  • 失效透明性

开放性的含义

  • 能够与来自其他开放系统的服务互动,而无关底层环境
    – systems 服从一致的接口
    – systems 支持应用的portability
    – systems 能够容易地interoperate
  • 至少使得分布式系统独立于异构的(各种不同的)底层环境

分布式操作系统、网络操作系统和基于中间件的系统

System Description Main Goal
DOS 紧耦合操作系统,用于多处理器系统和同构式多计算机系统 隐藏和管理硬件资源
NOS 松耦合操作系统,用于异构式多计算机系统(LAN&WAN) 向远程客户端提供本地服务
Middleware 在NOS之上的一个额外layer,实现一般意图的服务 提供分布透明性
  • DOS: 多处理器操作系统通过信号量和监控器两个同步原语保护数据不在同一时刻受到多个访问并访问共享存储器;而同构式多计算机系统由于系统范围内的资源管理所需的数据结构无法放置在物理上共享的存储器中(即不提供共享存储器),唯一的通信方法是消息传递,每个节点的内核负责管理本地资源和处理节点间通信;多计算机操作系统一般假定底层硬件是同构的,而且受到完全控制,而分布式系统却常常构建在现有操作系统之上
  • NOS: 大都构建在一组单处理器系统的基础上,每个系统都拥有自己的操作系统,因此缺乏透明性,难以统一管理和使用。优点是添加或者删除系统非常方便,具有可扩展性和开放性。
  • Middleware: DOS不是管理一组独立的计算机,NOS也没有提供单个一致的系统,因此都不是分布式系统。在网络操作系统中使用附加软件层用来隐藏网络操作系统中底层平台的异构性,所以针对不同结点提供一组不同完整性的服务集,但是结点的管理工作由本地操作系统而不是中间件负责。

分布式系统的类型

  • 分布式计算系统
  • 分布式信息系统
  • 分布式pervasive系统

分布式系统架构

分布式系统架构风格

  • 组成不同的逻辑组件,并将这些组件分布到多种的机器上
    – 分层风格用于客户端-服务器系统
    – 基于对象的风格用于分布式对象系统
  • 在空间(匿名)和时间(异步)上的解耦和过程会导向不同的风格
    – Publish/Subscribe (space)
    – 共享数据空间 (space and time)

分布式系统组织形式

  • 中心化
  • 去中心化
  • 混合式

客户-服务器模式和对等模式

  • 在服务器提供服务的进程
  • 在客户端使用服务的进程
  • 客户端和服务器可以在不同的机器上
  • 客户端遵从 请求/回复 模型来使用服务

Multiple-Client / Single-Server

  • 服务器形成瓶颈
  • 服务器的单点failure
  • 系统扩展困难

Decentralized Architecture

  • Structured P2P: 节点被组织成服从某种特定的分布式数据结构
  • Unstructured P2P: 节点随机地选择邻居
  • Hybrid P2P: 在一种良组织的风格中,某些节点被指定了某种功能

分布式系统组织为中间件

在很多情况下,分布式系统/应用是根据某种特定架构风格开发的。这种风格或许并不在所有情况下都是最优。所以我们需要动态地适配中间件的行为。

进程与线程

进程与线程

代码迁移

将正在执行的程序迁移到轻负荷的机器上运行。

  • 有助于开发并行程序而没有并行编程的复杂性
  • 提高灵活性

划分代码部分、确定不同部分在何处执行。若代码可迁移,则可动态配置分布式系统。动态配置分布式系统的优点是客户不需要预先安装所有程序即可与服务器会话,缺点是安全问题。

  • 代码段
  • 数据段
  • 执行状态(e.g. 线程上下文)

强迁移与弱迁移

  • 仅移动代码和数据段(和重启执行):
    – 相对简单。特别是代码portable的时候
    – Distinguish code shipping (push) from code fetching (pull)
  • 移动组件(包括执行状态)
    – 迁移:整个对象从一个机器迁移到另一个机器
    – 克隆:开启一个克隆体,将其设置为同样的执行状态

通信

通信的类型

  • 临时通信与持久通信
  • 异步通信与同步通信

RPC

当机器A上的一个进程调用机器B上的一个过程,则调用进程挂起,被调用进程在B上执行。信息可通过参数从调用者传递到被调用者,和通过结果从被调用者返回。消息传递对程序员透明。

RPC的工作过程

故障处理

动态绑定

Server先向本地OS请求一个端点(endpointt),然后在DCE daemon中注册该端点,记录在端点表中。Server再向一个目录Server注册自己的网络地址和一个名字。Client以Server提供的服务名字为key在目录Server中查找对应的网络地址,然后向Server上的DCE daemon请求服务端点。这些信息都具备后,执行RPC操作。

基于消息的通信

持久性/非持久性

  • 非持久性:消息送不到就丢失
  • 持久性:消息储存在某个通信服务器,直到被送达

同步/异步

  • 同步:发信者阻塞,直到它的消息接收或者进入接收者的buffer
  • 异步:不阻塞。消息存在发信者的buffer或者第一个通信服务器中

流数据

分布式系统应该为与时间有关的(即连续媒体)信息(如声音流和视频流)提供怎样的机制?

数据流:数据单元的序列。离散数据流(如UNIX的管道,TCP/IP的连接)和连续数据流(如播放音频文件时文件和设备之间的音频流)。

异步传输模式:流中的数据项一个接一个传输,对传输时间没有限制,一般用于离散数据流。
同步传输模式:对数据流中每个单元有一个端到端的最大延迟。
简单流(只有一个数据序列)和复杂流(有多个相关的简单流)。

– QoS(Quality of Service)

与时间相关的要求。可以通过提供对流精确的描述来指定QoS。

流的同步

保持流之间的时间关系。一种是离散数据流与连续数据流之间的同步,一种是连续流之间的同步。在发送时进行同步比在接收端同步简单。
同步机制有:一个进程执行对多个简单流的读写操作,保证这些操作满足时间和同步限制;或为应用程序提供一个接口,允许它更简单的控制流和设备。

命名

命名方式和命名需求

  • human-friendly name: cs.nju.edu.cn
  • address: 192.168.1.1
  • identifier

#

  • usage of unique naming conventions
  • 可扩展性
  • 一致性
  • 性能及可用性
  • 对变化的适配性
  • fault isolation

移动实体的定位

4种方式定位

  • 广播和多播:谁的孩子?
  • 转发指针:移动的轨迹
  • 基于起始位置
  • 建立搜索树分层

命名解析

DNS

同步与资源管理

同步问题

时钟同步机制

Cristian’s Algorithm
Berkeley Algorithm

逻辑时钟

lamport算法

  • 每个进程有个本地时钟
  • 发信时带上本地时钟
  • 收信者
  • 每两个事件之间滴答一次

向量时间戳

  1. 每个进程都有一个数列表示进程知道进程发生了多少个事件。
  2. 当进程发送消息的时候,它将加一,并将作为一个向量时间戳一起发送出去。
  3. 收到的消息和向量时间戳的时候,它 (1) ; (2) 将加一。

逻辑时钟与物理时钟

  • 并不需要绝对的时钟同步性
    – 两个不交互的进程不需要同步时钟
    – 重要的不是时间,而是事件的顺序
  • 对于只有内部时钟一致性问题有意义的算法,我们说逻辑时钟
  • 对于时钟不仅要相同,而且要不与现实偏离的算法,我们说物理时钟

分布式系统中的互斥访问

  • 集中管理者
  • 完全去中心化,p2p
  • 完全分布式,无拓扑结构
  • 完全分布式,逻辑环

分布式系统中的选举机制

  • bully algorithm
  • ring algorithm

复制与一致性

复制的优势与不足

advantages

  • 可靠性:avoid single points of failure
  • 性能: 数据和地理位置可伸缩

disadvantages

  • 复制透明性
  • 一致性问题
    – 更新昂贵
    – 不小心会导致可用性问题

数据一致性模型

一致性 描述
Strict 每个读写都有个绝对时间戳
Linearizability 全序
Sequential 偏序
Causal 保证潜在的RW因果关系
FIFO 单一进程的操作FIFO,不同进程之间不一定
Weak* 不同进程的RW由同步操作同步
Relase* 退出临界区时一致
Entry* 进入临界区时一致

*需要同步化操作(synchronization operations)

数据一致性协议实例

基于法定数量的协议

基本思路:要求客户在写或读一个复制的数据项签向多个服务器提出请求。

每个副本文件与一个版本号关联,更新后文件与新的版本号相关联。

对于一个N个副本的文件,必须组织Nr个服务器的读团体,Nw个服务器的写团体

条件:
Nr+Nw > N
Nw >N/2

第一个条件:防止读写冲突,第二个防止读读冲突。

客户端中心一致性

类型 描述
最终一致性 在没有更新操作时最终会一致。事实上只保证更新操作会被传播到所有地方
单调读 一个进程看到x=a之后,不会看到x=a之前的值
单调写 单一进程的写操作有序
RAW 单一进程的写总是被后续的读所看见
WAR

容错

可信系统的特征

  • 可靠
  • 可用
  • 安全
  • 可维护

提高系统可信性的途径

  • 由冗余来掩盖failure
    – 信息冗余
    – 时间冗余
    – 物理冗余
    – 进程冗余
  • 不需要多个关键组件的实体同时工作的设计

K-容错系统

如果在最多k个部件同时出错时系统仍能正常工作,那么这个系统就称之为k容错的

拜占庭问题

系统恢复

回退恢复

前向恢复

检查点

什么是结构化P2P?简述优缺点

在结构化P2P中,节点被组织成服从某种特定的分布式数据结构。如logically ring或hypercube。

易于维护
高效寻址

single points failure
拜占庭怎么看啊!

简要说明bittorrent如何工作。并解释这是何种p2p系统

客户端通过种子文件找到tracker服务器。服务器reply其他下载者的IP。各下载者由此组成unstructured P2P。
这是混合式p2p。

云计算&虚拟化

云计算提供三种类型的服务,解释这三种。

服务 解释
IaaS,基础设施作为服务 提供虚拟的计算和数据中心。把计算单元、IO、存储设施、带宽等基础设施集中起来作为一个虚拟资源池提供服务
PaaS,平台作为服务 将服务器平台或开发环境作为服务
SaaS,软件作为服务 一种基于互联网提供软件服务的应用模式

说明系统虚拟化的含义,并解释系统虚拟化技术与上述云计算服务的关系。

虚拟化是位于下层的软件模块,将其封装或抽象,提供一个物理或软件的接口,使得上层软件可以直接运行在这个虚拟的环境,和运行在原来的环境一样。

虚拟化特点 给云计算的好处
封装与隔离 保证每个用户都有安全可信的工作环境
多实例 保证较高的资源利用率。为服务器合并提供基础
硬件无关性 整合异构资源。可实现虚拟机迁移,使资源调度、平衡负载容易实现
特权功能 入侵检测、病毒检测
动态调度资源 细粒度的可扩展性

Openstack

以openstack为代表的这一类云计算平台的基本功能?

IaaS

应用场景

  1. 单位a中多个部门都需要使用某个模拟软件进行化学模拟实验。这些模拟实验对计算资源消耗极大,但这些实验往往不是同时进行的。
  2. 单位b中多个部门都需要不同类型的桌面系统处理日常事物,并且需求往往不是同时出现的。

哪个场景下适合openstack并说明理由

给出对应场景下openstack的一般化系统解决方案

(描述部署方案,无需关心硬件数量)

设计向量逻辑时间的目的是?给出向量逻辑时间的定义,并证明

我们不需要绝对的时钟同步性

  • 两个没有交互的进程之间不需要时钟同步
  • 重要的不是时间,而是事件发生的顺序

#

  1. 每个进程都有一个数列表示进程知道进程发生了多少个事件。
  2. 当进程发送消息的时候,它将加一,并将作为一个向量时间戳一起发送出去。
  3. 收到的消息和向量时间戳的时候,它 (1) ; (2) 将加一。

byzantine failure

考虑有2个节点(k=2)的GBP以达到interactive consistency为目标,讨论下列情况的具体要求并解释

  1. 已知commander是叛徒
  2. 已知commander忠诚
  3. 什么都不知道

给出一个分布式系统的BGP实例

  • IC1 所有忠诚的将军遵从同样的命令
  • IC2 如果发令的将军是忠诚的,那么每个忠诚的将军遵从命令

OM(0):

  • 发令者广播它的值
  • 所有接收者使用收到的值,没收到就使用0

OM(m):

  • 发令者广播它的值
  • 表示接收者收到的值,没收到就调用OM(m-1),向其余(n-2)个人广播
  • 表示收到的的值,没收到就采用majority。

Lemma 1
对于任意m和k,如果有超过2m+k的将军和最多k个叛徒,那么OM(m)满足IC2

OM(0)时成立。由OM(m-1)归纳OM(m)。

  1. 忠诚的发令者发送

  2. 2.1. 每个将军调用OM(m-1)
    2.2. 忠诚的将军收到
    2.3 n-1个将军中大多数忠诚大部分收到的
  3. 对于每个忠诚的将军majority

Lemma 2
对于任意m,如果有多于3m个将军和最多m个叛徒,那么OM(m)满足IC1和IC2

OM(0)成立。由OM(m-1)归纳OM(m)。
case 1: 发令者忠诚

  • 由Lemma 1,令k=m,OM(m)满足IC2。
  • 当发令者忠诚时,IC2IC1。

case 2: 发令者叛徒

  • 最多m个叛徒,发令者是其中之一
  • 最多m-1个接收者是叛徒
  • 最少3m-1个接收者

  • 应用已经满足IC1和IC2的OM(m-1)

设计一个用于分布式互斥的token-based算法,以改进token-ring算法,避免token空转导致的性能损耗

要求

  1. 拥有token是进入CS的唯一途径。各进程可以申请、拥有、释放token。token自身没有运动能力,也没有专有运动路径——ring
  2. 没有集中管理token的进程
  3. 达到ME1和ME2

解题步骤请包括

  1. 分析问题并指出特别要考虑的难点
  2. 给出解决思路,包括使用的数据结构和操作方法

#

  • ME1(safety) 任何时候只有一个进程在临界区
  • ME2(liveness)任何进程最终都能进入并退出临界区

CC BY-SA 4.0 review for distributed systems by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.