Skip to content

Latest commit

 

History

History
263 lines (232 loc) · 16.8 KB

distributed-systems.md

File metadata and controls

263 lines (232 loc) · 16.8 KB

分布式系统

2018A

  1. 分布式系统概念

  2. 物理系统概念

  3. 序列化

  4. 远程过程调用、远程方法调用概念

  5. 远程过程调用

  6. 分布式共享内存

  7. 异步分布式系统

  8. 请求-应答-确认应答

  9. 有序组播

  10. 乐观并发控制的假设和基本过程

  11. 组播和逻辑时钟的分布式互斥算法思想和步骤

  12. 向量时钟状态

  13. 分布式系统的特征和挑战

  14. map reduce框架过程，伪代码/key value图

Summary

  1. 分布式系统概念
  2. 物理系统概念
  3. 进程间通信
  4. 远程过程调用、远程方法调用
  5. 分布式共享内存
  6. 异步分布式系统
  7. 。。。

1. 分布式系统的特征

  1. 分布式系统的挑战：异构性、开放性、安全性、可伸缩性、故障处理、并发性、透明性、服务质量
  2. 分布式系统的趋势：泛在联网和现代互联网、移动和无处不在的计算、分布式多媒体系统、云计算/分布式计算
  3. 分布式系统定义：一个其硬件或软件组件分布在连网的计算机上，组件之间通过消息进行通信或动作协调的系统。
  4. 分布式系统特征：并发、缺乏全局时钟、故障独立性
  5. 分布式系统动力：资源共享
  6. 服务：管理相关资源，提供功能，单独的部分
  7. 服务器：联网计算机上的的进程，接受请求，执行服务，响应
  8. 客户：请求服务的进程

2. 系统模型

  1. 分布式系统困难和威胁：使用模式多样性、系统环境多样性、内部问题、外部威胁
  2. 物理模型：从计算机和所用网络技术的特定细节中抽象出来的分布式系统底层硬件元素的表示 。
  3. 基线物理模型：联网计算机上的硬件和软件组件仅通过消息传递进行通信和协调动作的系统
  4. 体系结构模型：用独立指定的组件以及这些组件之间的关系来表示的结构。元素、模式、中间件
  5. 体系结构模型整体目标：确保结构满足现在和将来的需求
  6. 体系结构模型设计目标：可靠、可管理、适应、性价比
  7. 体系结构元素-通讯实体：进程/结点，线程补充进程
  8. 体系结构元素-面向问题实体：对象、组建、web服务
  9. 体系结构元素-通讯范型：进程间通信、远程调用、间接通信。
  10. 体系结构模式：构建在体系结构元素上，提供组合的、重复出现的结构。模式：
    1. 分层体系结构（服务垂直分层）
    2. 层次化体系结构（组织给定层）
    3. 瘦客户（软件层提供基于窗口的本地用户界面，本地设备简化）
    4. 代理（位置透明）
    5. 业务代理：支持互操作
    6. 反射：动态修改结构
  11. 中间件：软件层，屏蔽异构性，一组计算机上的进程或对象，相互交互实现分布式应用的通信和资源共享支持。为分布式系统的开发提供一个高层的编程抽象，通过分层对底层基础设施中的异构性提供抽象 。
  12. 系统模型特征：有进程组成、进程之间通过消息通信、共享的设计需求（性能、可靠、安全）
  13. 基础模型目的：显式的表示有关我们正在建模的系统的假设，给定这些假设，就什么是可能的、什么是不可能的给出结论
  14. 基础模型：
    1. 交互模型（同步/异步分布式系统）：对进程执行速度、消息传递延迟、时钟漂移率没有限制的系统是异步系统，相反就是同步分布式系统
    2. 故障模型：遗漏（不能完成任务）、随机、时序故障（同步分布式系统）
      1. 故障屏蔽：隐藏故障/转换为一个更能接受的故障类型
    3. 安全模型：保证进程和用于进程交互的通道的安全、保护对象免遭未经授权访问
      1. 敌人：◦潜在敌人的威胁包括对进程的威胁和对通信信道的威胁
      2. 解除安全威胁：密码学和共享秘密、密码学、认证、安全通道
      3. 拒接服务
      4. 移动代码

3. 进程间通信

  1. UDP：消息传递抽象、TCP：进程对之间的双向流抽象
  2. 互联网协议
    1. 进程间通信的特征：同步（阻塞）和异步通信（非阻塞）、消息目的地、可靠性（有效性：保证发送+完整性：至多发送一次且无损坏）、排序
    2. socket套接字：独立于具体协议的网络编程接口。流套接字、数据报套接字、原始套接字。
    3. 进程间通讯是在两个进程各自的一个套接字之间传送一个消息
    4. UDP数据报通信：消息大小、阻塞、超时、任意接受（来源）
    5. UDP故障：遗漏、排序
    6. TCP隐藏的特征：消息大小、消息丢失、流控制、重复和排序、目的地
    7. TCP流通信问题：数据项匹配、阻塞、线程
    8. TCP故障：完整性、有效性、中断
  3. 外部数据表示和编码： 不论使用何种通信形式，数据结构在传输时都必须转换成字节序列，到达目的地后再重构
    1. 外部数据表示：表示数据结构和简单值的一致标准
    2. 编码、解码
    3. 方法：
      1. CORBA公共数据表示：4byte一行，string前面要放长度
      2. java对象序列化：序列化、解序列化。类信息：类名、版本号。对象的引用：对象也要序列化（递归过程）。反射：根据类名创建类、构造函数，接着用来创建新的对象。
      3. XML可扩展标记语言
    4. 远程对象引用：是远程对象的标识符，在整个分布式系统中有效。
  4. 组播通信：◦将单个消息从一个进程发送到一组进程的每个成员的操作
    1. 组播具体实现：IP组播（UDP）
    2. 组播的可靠性（遗漏、故障）和排序
    3. 比IP组播更可靠的组播：可靠组播
    4. 对顺序有要求：全排序组播（以相同顺序到达所有成员）
  5. 网络虚拟化：覆盖网络
    1. 网络虚拟化涉及在一个已有的网络之上构造多个不同的虚拟网络，避免改变底层网络的特征
    2. 覆盖网络：◦节点和虚拟链接组成的虚拟网络，位于一个底层网络之上
    3. 好处：不改变底层网络就能定义新的网络服务、面向特定应用特质、多个覆盖网可以同时存在
    4. 不足：引入了额外的间接层
  6. 消息传递接口（MPI）

4. 远程调用

  1. 请求应答协议：描述了一个基于消息传递的范型，支持在客户/服务器计算中遇到的消息双向传输
    1. 请求协议：发送
    2. 请求应答：
  2. 远程过程调用：将传统的过程调用模型扩展到分布式系统中。允许客户程序透明地调用在服务程序中的过程。
    1. 调用语义：或许调用/至少一次调用/之多一次调用
  3. 远程方法调用：基于对象的编程模型扩展，允许不同进程运行的对象通过其彼此通信。是对本地方法调用的扩展
    1. 共性：接口编程、RR、透明性
    2. 分布式对象：
    3. 远程对象引用：指向某一个唯一的远程对象
    4. 伺服器：提供远程对象主体的类的实例

5. 间接调用/通信

  1. 间接通信： 在分布式系统中实体通过中介者进行通信，没有发送者和接收者（们）之间的直接耦合（空间、时间解耦）
  2. 组通信：消息首先被发送到组中，然后该消息被传送到组中的所有成员
    1. 可靠组播：完整性（至多被正确的传输一次）+有效性（最终被传递）+协定（如果消息被传递到一个进程，那么该消息会被传递到本组中所有进程 ）
    2. 有序组播：FIFO、因果、全序
  3. 发布-订阅系统：基于事件的分布式系统 ，发布者发布结构化的事件到事件服务，订阅者通过订阅表达对特定事件感兴趣，其订阅可以是结构化事件之上的任意模式 。系统把订阅和发布事件进行匹配，保证事件通知的正确传递（保证所有事件被有效地传递到有过滤器与事件匹配的所有订阅者 ）。
    1. 特征：异构、异步、为通知提供不同的传递保证
    2. 模式：基于渠道、主体、内容、类型
    3. 代理网络实现
    4. 方法：泛洪、过滤、广告、汇聚
  4. 消息队列： 分布式系统中通过队列进行通信的一种方法 ，生产者进程发送消息到特定队列，其他（消费者）进程从该队列中接受消息
    1. 在不同的机器上：客户渠道
  5. 分布式共享内存：是一种抽象，用于给不共享物理内存的计算机共享数据 。 进程通过读和更新看上去是其他地址空间中普通的内存来访问DSM
  6. 分布式内存多处理器：处理器没有共享内存但是通过一个非常高速的网络来连接。
  7. 元组空间通信： 进程通过在元组空间放置元组间接地进行通信，其他进程可以从该元组读或删除元组。元组没有地址，但是可以通过内容上的模式匹配进行访问
    1. 副本一致性：从相同状态开始，以相同顺序执行时间，每个时间作出确定反应

8. 时间和全局状态

  1. 时钟便宜、时钟漂移
  2. 外部同步：用权威的外部时间源同步进程的时钟 、内部同步：时钟同步到一个已知的精度，那么我们就能通过本地时钟度量在不同计算机上发生的两个事件的间隔 
  3. 时间正确性：硬件时钟H的漂移率在一个已知的范围ρ>0内
  4. 同步系统的同步u=max-min，误差最多为u/2
  5. 异步系统：变化量为min+x
  6. 同步时钟的cristian方法：使用一个时间服务器，它连接到一个接收UTC信号的设备上，用于实现外部同步 。 在接收到请求后，服务器S根据它的时钟提供时间。最大偏差是来回时间的一半
    1. 单个时间服务器
    2. 多个时间服务器，通过组播发出请求，使用第一个应答
  7. 同步时钟的berkeley算法：主机把slaves的时间平均，把修改量发给每个slave
  8. 网络时间协议NTP： 定义了时间服务的体系结构和在互联网上发布时间信息的协议。
    1. 模式：组播、过程调用、对称模式
  9. lamport逻辑时钟
    1. 普通
    2. 全序逻辑时钟（标号一样的时候，进程id小的先发生）
    3. 向量时钟
  10. 全局状态必要性：无用单元回收、死锁检测、终止检测、分布式调试
  11. 全局状态：我们可以取单个进程状态的任一集合来形成一个全局状态 。 一个全局状态相当于单个进程历史的初始前缀
  12. 一致全局状态：对于一致割集的状态
  13. “走向”（run）是全局历史中所有事件的全序 ，并且它与每个本地历史排序ài(i=1,2,…,N)是一致的
  14. 所有线性化走向只经历一致的全局状态。如果有一个经过S和S’的线性化走向，我们说状态S’是从状态S可达的
  15.  全局状态谓词是一个从系统P的进程全局状态集映射到{Ture, False}的函数。与对象成为无用、系统死锁、系统终止的状态相关的谓词是稳定 的，一旦系统进入谓词值为True的状态，它将在所有可从该状态可达的状态中一直保持True。
  16. lamport快照算法：目的是记录进程集pi(i=1, 2, …, N)的进程状态和通道状态集（快照） ，即使所记录的状态组合可能从没有在同一时间发生，但所记录的全局状态还是一致的
    1.  算法有如下假设：
      1. 不论通道还是进程都不会出现故障，通信是可靠的。
      2. 通道是单向的，提供FIFO顺序的消息传递。
      3. 描述进程和通道的图是强连接的（任意两个进程之间有一条路径）
      4. 任一进程可在任一事件开始一个全局快照
      5. 在拍快照时，进程可以继续它们的执行，并发送和接收消息
  17. 分布式调试
    1. 可能的phai、明确的phai
    2. 如何判断

9. 协调和协定

  1. 故障检测器：不可靠（有可能故障）、可靠（确定有故障）
  2. 协调和协定：分布式系统中进程如何协调它们的动作或对一个或多个值达成协定
  3. 分布式互斥：◦如果一组进程共享一个或一组资源，那么访问这些资源时，常需要互斥来防止干扰并保证一致性。需要一个仅基于消息传递的分布式互斥问题解决方案
    1. 中央服务器算法
    2. 基于环的算法
    3. 使用组播和逻辑时钟的算法：
      1. 思想：进入CS前要所有其他进程同意：组播请求+应答。并发控制，采用lamport时间错避免死锁
    4. maekawa投票算法：基于上一种，不过只需要选举集中的程序应答了就可以。选举集的交集不是空的。可能有死锁
  4. 选举：选择一个唯一的进程来扮演特定角色的算法
    1. 基于环
    2. 霸道算法：选举消息、应答消息、协调消息（宣布自己当选了）
  5. 组通信中的协调和协定
    1. 组播：发送一个消息给进程组中的每个进程
    2. 基本组播：一个正确的进程最终会传递消息（有效性）
    3. 可靠组播：完整（至多穿一次）、有效（最终会穿）、协定（组中所有进程都传递）
    4. 有序组播：FIFO、因果、全排序
  6. 共识
    1. 公式问题：•一个或多个进程提议了一个值后，应达成一致意见
    2. 要求：终止性、协定性、完整性
    3. 同步系统：拜占庭，广播值，取majority
    4. 异步系统的不可能性：没有算法能保证共识、故障屏蔽、故障检测器达到共识、随机化达到共识

10. 事务和并发控制

  1. 事务：以原子方式执行的一系列操作，不受其他并发操作影响，所有操作全做或者全不做
    1. 目标：  在多个事务访问对象以及服务器面临故障的情况下，保证所有由服务器管理的对象始终保持一个一致的状态。
  2. 嵌套食物：◦嵌套事务：允许事务由其它事物构成
  3. 锁： 互斥锁是一种简单的事务串行化实现机制，事务访问对象前请求加锁。若对象已被其它事务锁住，则请求被挂起，直至对象被解锁
    1. 两阶段加锁：增长阶段、衰减阶段
    2. 死锁检测：等待图又换、锁超时
  4. 乐观并发控制：
    1. 假设：◦在大多数应用中，两个客户事务访问同一个对象的可能性很低。
    2. 方法：访问对象时不作检查操作 ，事务提交时检测冲突 ，若存在冲突，则放弃一些事务
    3. 过程：三个阶段（工作阶段拥有临时版本、验证阶段判断有无冲突、更新阶段提交食物）
    4. 向后延症：◦检查它的读集是否和其它较早重叠事务的写集是否重叠
    5. 向前验证：◦比较Tv的写集合和所有重叠的活动事务的读集合
    6. 验证失败：放弃验证的任务、放弃其他冲突的事务、推迟验证
  5. 时间戳排序：每个事务在启动时被赋予一个唯一的时间戳 ，时间戳定义了该事务在事务时间序列中的位置
    1. 接受写操作：时间晚于最大读时间 && 时间晚于提交版本写时间
    2. 接受读操作：时间晚于提交版本写时间
  6. 并发控控制方法比较

11. 分布式文件系统

  1. 基本分布式文件系统：主要目的是在多个远程计算机系统上模拟非分布式文件系统的功能
    1. 共享存储信息
    2. 在一致性、性能、可扩展性上进行折中
  2. 文件系统特点
    1. 是操作系统所提供的基础设施
    2. 文件系统：文件的组织、存储、检索、命名、共享和保护 ，◦提供描述文件抽象的程序接口
    3. 文件：数据和属性
    4. 目录：特殊的文件
    5. 访问控制
  3. 需求：
    1. 透明性：访问、位置、移动、性能、伸缩
    2. 并发文件更新
    3. 文件复制
    4. 硬件和操作系统异构性
    5. 容错
    6. 一致
    7. 安全
    8. 效率
  4. 文件服务体系结构
    1. 三个组成：平面文件服务器、目录服务器、客户端
    2. 访问控制、目录服务接口、层次文件系统、文件组
  5. NFS、AFS、GFS

12. “大型”网站架构设计

  1. 大型网站结构的目标与挑战
    1. 目标：高可用性、高性能、可伸缩性
  2. 网站架构的演变和技术脉络
    1. 基于lamp的webserver
    2. web动静态资源分离，与DB物理分离、动态页面静态化
    3. 缓存处理：客户端缓存、前端页面缓存、页面片段缓存、本地数据缓存、
    4. 负载均衡
    5. 增加机器做HA、数据库读写分离
    6. CDN、分布式缓存、分库
    7. 多个数据中心、向分布式存储和计算的架构体系迈进
  3. 架构设计理论与原则
    1. 数据一致性—ACID vs BASE 基本可用+软状态+最终一致性
    2. 分布式系统—CAP理论 一致性+可用性+分区容忍性
    3. 无共享架构
    4. 事件驱动，面向服务架构
    5. 架构进化与退化--奥卡姆剃刀原理
    6. 考量成本，先硬后软原则