分布式系统——课程总结

本节内容:2016年秋南京大学计算机系分布式系统课程总结。

分布式系统模型

1 分布式系统定义:

一个分布式系统是一些独立的计算机集合,但是对这个系统的用户来说,系统就像一台计算机一样。 这个定义有两方面的含义:第一,从硬件角度来讲,每台计算机都是自主的;第二,从软件角度来讲,用户将整个系统看做是一台计算机。这两者都是必需的,缺一不可。

2 涉及到的技术:网络、处理器、内存、存储、协议。

3 需要分布式的原因

  • 相对于集中系统,分布式系统的优点
优点 解释
Economics(经济性) 微处理器能提供比大型机更好的性价比
Speed(速度) 分布式系统能提供比大型机更强的计算能力
Inherent distribution(固有的分布性) 有一些应用包含物理上分布的机器
Reliability(可靠性) 当某台机器崩溃时,整个系统仍能正常工作
Incremental growth(可扩展性) 计算能力逐步增加
  • 相对于独立的PC,分布式系统的优点
优点 解释
数据共享 允许用户共享一个数据库
外设共享 允许用户共享昂贵的外设,如彩色打印机
通信 使得个人与个人之间的通信更为方便,如Email
灵活性 将工作负载更有效的分派到合适的机器上
  • 缺点
缺点 解释
软件 分布式系统的软件开发困难
通信网络 网络可能饱和或有损传输
安全 数据共享造成机密数据容易被窃取

4 分布式系统的目标

  • 资源可用性:系统资源被所有计算机共享
  • 分布透明:Access,Location,Migration,Relocation,Replication,Concurrency,Failure
  • 开放性:能够与其他开放系统进行服务交互,能够使分布式系统独立于底层环境的异构性
  • 可扩展:用户、处理可扩展(大小扩展性),节点之间最大距离(地理可扩展性),管理主机的数目(管理可扩展性)

5 分布式系统透明性和开放性

透明性:将它的进程和资源实际上在多台计算机上分布这样一个事实隐藏起来,如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统,这样的分布式系统就称为是透明的。

  • 访问透明性:对不同数据表示形式以及资源访问方式的隐藏。
  • 位置透明性:用户无法判别资源在系统中的物理位置。
  • 迁移透明性:如果一个分布式系统中的资源移动不会影响该资源的访问方式,就可以说这种分布式系统能够提供迁移透明性。
  • 重定位透明性:如果资源可以在接受访问的同时进行重新定位,而不引起用户和应用程序的注意,拥有这种资源的系统无疑会更加强壮。
  • 复制透明性:对同一个资源存在多个副本这样一个事实的隐藏。
  • 并发透明性:让任何一个用户都不会感觉到他人也在使用自己所使用的资源。
  • 故障透明性:意味着用户不会注意到某个资源无法正常工作,以及系统随后从故障中恢复的过程。

开放性:一个开放的分布式系统,它根据一系列准则来提供服务,这些准则描述了所提供服务的语法和语义。

  • 能够与其他通过服务交互而不用考虑底层环境:
    • 符合明确定义的接口
    • 支持应用的可移植性
    • 易于互操作
    • 屏蔽底层环境的区别
  • 开放性要求分布式系统的策略与机制分离:
    • 单一系统趋向于封闭
    • 为分离提供相对应的开放接口

6 分布式系统类型

  • 分布式计算系统:集群计算、网格计算
  • 分布式信息系统:事务处理系统(ACID:原子性、一致性、隔离性、持久性)
  • 分布式普适系统:普适计算、移动计算、传感器网络

分布式系统架构

1 分布式系统架构风格

  • 组织成逻辑上的不同组件,并分发这些组件到各个机器上:分层样式用于客户端-服务器系统、基于对象样式的分布式对象系统

  • 空间(匿名)和时间(异步)的解耦过程导致多种风格:发布/订阅模式(空间解耦)、共享空间(时间和空间解耦)

或:

  • 分层体系结构
  • 基于对象的体系结构
  • 以数据为中心的体系结构
  • 基于事件的体系结构

2 分布式系统组织形式

  • 中心化:
    • 基本的客户端-服务器模式:服务器提供服务,客户端使用服务,客户端和服务器端可以位于不同的机器上,客户端遵从请求/响应模式来使用服务。
    • 多客户端-服务器模式:服务器形成瓶颈,容易产生单点故障,系统调用困难。
    • 多客户端-多服务器:Web代理,Web Applets
    • 应用分层(应用于传统分布式信息系统):传统三层视图:用户接口层,处理层,数据层
    • 多层架构(User interface, Application, DataBase):单层(哑终端/主机配置)、两层(客户端-单服务器配置)、三层(每一层都在一个独立的机器上)
  • 去中心化:
    • 结构化的P2P系统:将节点组织成一个结构化覆盖网络,例如一个逻辑环或超立方体,并创建负责仅基于其ID的服务的特定节点。
    • 非结构化的P2P系统:组织成一个随机的覆盖层,两个节点连接的概率是p,因而不能够确定性地查找信息,而不不得不求助于搜索:洪泛发送信息到周围节点;以及随机游走:随机选择一个邻居。
    • 混合P2P:有时选择一些特殊节点来做一些特殊事务(保存索引,监控网络状态,建立连接)有助于系统性能。
  • 混合模式:客户端-服务器端结合P2P;边缘服务器架构,通常用来实现内容分发网络。

3 分布式系统组织为中间件

在通常情况下,分布式系统/应用依照具体的架构风格开发,所选择的分布式系统架构风格在所有的案例下可能不是最佳的,因而需要动态地适应中间件的行为。

拦截器:当激发一个远程调用对象时拦截普通的控制流。

分布式中间件

进程与线程

1 进程

  • 进程: 进程状态上下文中的执行流
  • 执行流:执行指令流、运行的一块代码、顺序指令序列、控制的线程
  • 进程状态:运行的代码能够影响或被影响的一切
  • 进程与程序:程序是静态的代码和静态的数据,进程是代码和数据的动态实例,进程和代码间不存在一对一的映设,同一份程序能对应多个进程实例,一个程序能调用多个进程。
  • 进程运行过程中的三种状态:运行态(仅在CPU里的一个核里)、准备状态(等待CPU)、阻塞状态(睡眠状态,等待IO或同步来完成)
  • 进程的性能低下:资源管理(创建进程需要分配空间,拷贝数据)、调度(上下文切换:CPU和存储上下文)、协作(IPC,内部通信,共享内存)

2 线程

  • 线程:是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务。
  • 上下文切换:处理器上下文(寄存器:栈指针,地址寄存器,程序计数器)、线程上下文(寄存器和内存中:处理器上下文,状态)、进程上下文(寄存器和内存中:线程上下文,MMU寄存器值)
  • 上下文切换:线程共享地址空间,线程上传下文切换能够独立于操作系统完成;进程切换上下文的代价更高,涉及到在循环中获取系统信息,陷入到系统内核;创建和销毁线程的代价比进程要便宜。
  • 用户级线程:所有的线程在用户地址空间创建,优点是所有的操作能在单个进程中完全处理,实现起来效率高,缺点是很难获取系统以及块的支持。
  • 系统级线程:系统内核包含线程包的实现,所有的操作都返回一个系统调用:阻塞一个线程的操作将不再是问题,处理外部事件变得简单,缺点是损失一些效率,因为每一个线程操作都陷入到内核里面了。
  • 总结:尽量融合用户级和内核级线程到一个概念中,然而然而性能的增加并没有抵消复杂度的增加。

3 线程和分布式系统

  • 隐藏了网络延时:多个线程预取文件同时响应一个HTTP请求
  • 对其他机器的多个请求-响应调用(RPC):客户端同时做多个调用,每个调用由一个不同的线程完成
  • 提高性能:启动线程比启动进程代价低,单个线程服务器禁止简单扩容到一个多处理器系统,客户端:当前一个请求应用后通过响应下一个请求隐藏了网络延时
  • 更好的结构:IO请求多时能有效简化整个结构,由于简化的控制流多线程程序会更小和更容易理解

4 多线程下的分布式C/S架构:

  • 客户端软件:完全透明:获取透明性、位置/迁移透明性、错误透明性、复制透明性
  • 服务端软件:端口和服务间一对一映设,组织成dispatcher/worker模型
  • 服务器类型:超级server:监听多个端口,提供多个独立的服务
  • 有状态:保持跟踪客户端状态:记录文件打开情况以及缓存情况,性能好,客户端能保存本地缓存
  • 无状态:服务器不保存客户端的处理请求状态,客户端和服务器端完全独立,它们之间的状态不一致性以及冲突避免了,可能丢失一些性能

多线程服务器

5 代码迁移:代码段、数据段、执行状态

  • 强弱移动性:
    • 仅移动代码段和数据段:相对简单,区分代码推送和拉取
    • 移动所有组件,包括执行状态:迁移:将整个对象从一台机器迁移到另一台机器;拷贝:开始拷贝,并设置成相同的执行状态
  • 管理本地资源

    • 使用本地资源的对象的资源在目标点可能不可用
    • 资源类型:固定资源(资源不能迁移,如本地硬件),紧固资源(理论上能够迁移,但代价高昂),未附加的(能轻易地移动资源,例如缓存)
    • 对象和资源间的绑定:identifier(对象需要一个具体资源的实例,如特定的数据库)、value(对象需要资源的内容,如缓存的入口)、 type(仅需要一种类型的资源是可用的,如彩色显示器) 管理本地资源
  • 异构系统中的迁移问题

    • 目标机器可能不适合执行迁移的代码
    • 进程/线程/处理器上下文强烈依赖于本地硬件,操作系统和运行系统
    • 解决方案:充分利用在不同平台上的抽象机器的实现

通信

1 通信的类型

  • 瞬间通信(数据无法传送就丢弃)与持久通信(数据被暂存在通行服务器上直到被传送出去)、异步通信与同步通信

2 远程过程调用

  • RPC的工作过程:客户端过程调用客户端stub;Stub 构建消息,调用本地OS;OS发送消息到远程OS;远程OS接收消息至stub;Stub解包参数并调用服务器;服务器生成本地调用并返回结果至stub;Stub构建消息,调用OS;OS发送消息到客户端OS;客户端OS传送消息至stub;客户端Stub解压结果并返回给客户端。
  • 故障处理:

    • 客户端无法定位服务器:可能原因:服务器关闭,服务器使用了新版本的存根而客户端使用了较旧版本的存根;解决方法:使用一个特殊码,例如-1作为过程的返回值来指示失败;让错误触发一个异常或信号。
    • 客户端向服务器端发送的请求消息丢失:当发送一个消息的时候内核开启一个计时器:在响应或ACK到来之前定时器过期,则内核重发;如果消息真的丢失:服务器不会区分原始和重传的消息,一切正常;如果许多请求都丢失,内核放弃并假装服务器已经关闭了。
    • 服务器端向客户端发送的应答消息丢失:当发送一个消息的时候内核开启一个计时器:在回复到来之前定时器过期则重传请求;如果服务器速度很慢,则该过程被执行多次;使用序列数字标志请求号,让服务器内核区分是重传消息还是原始消息。
    • 服务器端接收到一个消息后崩溃:等待服务器重启后继续重复该操作;立即放弃并报告故障;客户端得不到任何帮助。
    • 客户端发送请求后崩溃:客户端发送请求后崩溃:客户端stub发送RPC之前先写log,重启后检查log然后杀死孤立进程;把时间划分成连续的时隙,客户端重启后广播一个新的时隙,所有的计算都被杀死;每一个RPC都给定了一个标准的时间T来完成工作,如果不能完成则需要明确地向其他法官申请额外配额。
  • 动态绑定

  • 优点:

    • 灵活性
    • 能支持多个支持同一接口的服务器
      • 绑定程序(binder)可以随机地将服务器上的客户端传播到均匀负载
      • 绑定程序(binder)可以定期轮询服务器,自动取消注册失败的服务器,以达到一定的容错能力
      • 绑定程序(binder)可以帮助身份验证
    • 绑定程序(binder)可以验证客户端和服务器都使用相同版本的接口
  • 缺点
    • 导出/导入接口的额外开销花费时间
    • 绑定程序(binder)可能成为大型分布式系统中的瓶颈

3 基于消息的通信

  • 持久性/非持久性通信
    • 持久性通信:通信机制本身会对消息进行持久存储,直到它被传递给目的。
    • 非持久性通信:消息的发送者和接收者必须同时存在才能进行,传输服务仅仅提供临时的对消息的存储。
  • 同步/异步
    • 同步通信:发信方在到达同步点前保持阻塞
    • 异步通信:发信方发信后立即继续,消息存储在发信方主机或者通信服务器的缓冲区中
  • 流数据
    • 流式数据:一组消息按照指定的顺序排序后构成一个有意义的数据流

命名

1 命名方式

  • Human-friendly name
  • Address
  • Identifier

2 移动实体的定位

  • 广播(Broadcasting)
  • 转发指针(Forwarding Pointers)
  • 基于家(Home-based)的方法
  • 分布式哈希表(Distributed Hash Table)

3 命名解析

  • 迭代命名解析:每次解析一个节点以后都会把结果返回给客户名称解析程序,然后将由客户重新向下一级服务器发送请求。
  • 递归命名解析:直接把解析的中间结果传递给下一级服务器,并且逐级解析直到返回指定文件结果:要求名称服务器都具有较高性能,增加了额外负担,减少通信开销,而且可以更好地使用缓存来提高性能

同步与资源管理

1 同步问题

2 时钟同步机制

3 逻辑时钟

  • Lamport时钟
  • 向量时戳

4 分布式系统中的互斥访问

5 分布式系统中的选举机制

复制与一致性

1 复制的优势与不足

2 数据一致性模型

3 数据一致性协议

  • 基于法定数量的一致性

容错

1 可信系统的特征

2 提高系统可信性的途径

3 K容错系统

4 拜占庭问题

5 系统恢复

  • 回退恢复
  • 前向恢复

6 检查点

云计算

OpenStack