分布式和云计算(理论)

发表于 | 分类于

第零章：前言(Preface)

研一下半年，选了一门分布式和云计算的专业课，授课是丁箐老师，实验指导是赵振刚老师。通过这门课的学习，感觉还是收获很多的。

于是想写一篇文章整理一下所学的知识，这样方便日后巩固相关的内容，增加一些理解。

本门课程主要由两大部分组成，一是课程的理论学习，二是实验操作。这两部分都很有用，都会整理写出来。

其中，实验总共有四次，对于每次实验，我都是很认真的完成的，并且还比较用功地写了的实验报告。

第一章：分布式的介绍(Introduction)

  • 分布式系统的定义
  • 分布式系统需要完成的目标、为什么需要分布式系统
  • 分布式系统的分类

分布式系统的定义

分布式系统来自：

  • 计算机系统
  • 计算网络

分布式系统是软件，它确保一组独立的计算机对用户而言似乎是一个统一的系统

分布式系统并没有实现操作系统的所有功能，因此不能叫做分布式操作系统。

分布式最主要的特点是：

  • 各种计算机之间的差异以及通信方式之间的差异大部分对用户而言是隐藏的
  • 用户和应用程序以一致且统一的方式与分布式系统交互，无论交互发生在何时何地

分布式系统的目标

资源可用性、连通性

使得资源变得可用、容易、安全

透明性

透明性目标是分布式系统最主要的目标，但是是有限的，它包括

  • 存取透明性： 终端用户不知道资源存在什么位置
  • 迁移透明性： 资源从一个地方迁移到另外一个地方，用户不知道，此时的资源是不在使用的
  • 重定位透明性： 在资源使用时，资源可以从一个地方，移动到另外一个地方，用户不知道
  • 复制透明性： 资源可能是多复制的，解决可靠性。在分布式系统中大量应用，给用户减少工作
  • 并发透明性：终端用户不知道自己可能与其他用户一块并发使用某个资源
  • 错误透明性：即容错系统，能够屏蔽系统可能发生的故障

开放性

开放的分布式系统能够与其他开放系统的服务交互，与底层环境无关，独立于底层环境异构型

  • 硬件
  • 平台
  • 语言

可拓展性

实现拓展性的技术有：隐藏通信延迟、避免等待响应、利用异步通信

规模可拓展：主要在用户数、进程数可以拓展

对于拓展规模来说，如果分布式系统中存在集中式(集中式设备、集中式数据、集中式算法)是非常影响可拓展性的。

为了解决集中式，提出了分散算法的四条原则：

  • 没有机器有系统的完整信息(没有一个节点能通过通讯知道所有节点的状态)
  • 节点做决策仅仅依靠本地信息得到次优解(因为无法得到全局解)
  • 一台机器出故障，不会影响分布式系统(体现算法健壮性)
  • 不能假设有全局时钟的存在来统一时间设定
地理可拓展：是指节点距离可拓展
  • 通信隐藏技术
  • 避免广播
管理域可拓展：管理域(语言不同、底层系统不同)扩大

目前最难的扩展

分布式系统的分类

  • 分布式计算系统
  • 分布式信息系统
  • 分布式普适系统

分布式计算系统

  • HPC:高性能计算系统，主要在CPU能耗上
  • HTC：高性能吞吐系统，主要在IO消耗上

网格计算就是分布式高性能计算系统的一种
特点是：允许异构、跨多个域、广域化

分布式信息系统

主要关注信息交互

  • 事务处理系统(Transaction Processing System)
  • 企业应用程序集成(Enterprise Application Integration)

分布式普适系统

正在出现的下一代分布式系统，其中节点较小、可移动，并且通常嵌入为较大系统的一部分。
物联网、区块链、wifi等等

总结

  • 分布式系统由独立的计算机组成，他们协同工作，形成单个连贯系统的外观
  • 分布式系统通常隐藏与进程、数据和控制相关的许多错综复杂的内容
  • 许多开发人员最初对底层网络做出的假设基本上都是错误的，这一事实使得问题变得更加复杂
  • 存在不同类型的分布式系统，他们可以分类为面向计算、信息处理和普适计算的分布式系统

第二章：分布式系统架构(Architectures)

  • 体系结构样式
  • 系统体系结构
  • 分布式系统中的体系结构与中间件
  • 分布式系统中的自我管理

体系结构样式

architecture style的分类：

  • 分层体系结构(也是目前用得最多的架构)
    • 使用面向对象语言，面向分层的思想来设计
  • 基于对象的体系结构
  • 以数据为中心的体系结构
  • 基于事件的体系结构

分层体系结构

分层样式：使用面向对象语言，面向分层的思想来设计

基于对象的体系结构

面向对象： 对 component 当成一个对象，component之间的联结通过调用实现，呈网状结构

以数据为中心的体系结构

基本思想：进程通过公共(被动或主动)存储库进行通信

基于事件的体系结构

分离空间(“匿名”)和时间(“异步”)的一种结构样式

系统体系结构

系统架构的定义：系统架构决定了软件组织，组件的联系，以及组件的位置

  • 集中式体系结构(单一服务器)
  • 分散体系结构(有多个服务器)
  • 混合体系结构(完全没有服务器)

集中式体系结构

具体描述：是有服务器结构，整个系统也是围绕着服务器来做的
优点：简单，易于实现
缺点：造成缺失异常操作时，不知道在哪个地方出问题
举例：C/S架构

分散体系结构

  • 水平分布

    • 客户端和服务器可以在物理上被分成逻辑上等价的部分
    • 但是每个部分都在其自己的完整数据集中上操作，从而平衡负载
    • 支持水平分布的一类现代体系结构称为对等
    • 复制和集群

  • 垂直分布

    • 不同的层直接对应于程序的逻辑组织
P2P

Peer-to-Peer：网络中的节点，既是请求者，又是响应者

P2P网络有什么不同：与以往网络最大的不同点是两层的网络。

  • 物理网络：底层的电缆连接
  • 逻辑网络：网络之间的通信

无结构的p2p系统：结点的邻居是随便选的
有结构的p2p系统：结点的邻居是有规则选的，按照一定的规则进行选择邻居结点

P2P的发展：

  1. Napster
  2. Gunutella
  3. chord
  4. bitTorrent
Napster

Napster是一个音乐分享系统

工作原理：

  • 注册过程：
    • 客户机连接服务器
    • 上传key-value对
    • 服务器维护索引
  • 搜索下载过程：
    • 客户机在服务器查找曲目
    • 服务器返回有主机列表元组
    • 客户机进行ping速率，找到最快传输主机
    • 进行传输

Napster不算是真正意义上的p2p，因为在Napster系统中依然有集中式服务器的存在

所以有集中式架构的那些缺点，传输错误、容易阻塞，单点故障

但是又不同于以往的集中式架构，因为客户机不是从服务器上下载音乐

Gnutella

Gnutella是真正意义上的第一个p2p系统（分散式体系结构）

  • 消除服务器，无服务器的系统
  • 客户端计算机之间进行搜索和检索(搜索检索也是P2P架构)

当在做搜索时，Gnutella是以flooding的方式发出Querry请求，只等待queryhit，因此Gnutella是无结构的P2P系统

Gnutella Query的特点：

  • 泛洪
  • ttl受限
  • 每个query 在每个结点中只会被转发only one

Gnutella也有大量问题，就是50%的时间都是用来做ping、pong操作，用来探知周围结点的变化，进行更新自己的维护列表，导致效率不高

chord

有结构P2P系统，无结构的命名

查找结点的邻居方法是有规律的，把查找的时间复杂度降到O(logn)

bitTorrent

FastTrack 系统：

  • Gnutella 和 Napster的混合体
  • 利用系统中更健康的参与者
  • Kazaa、KazaaLite、Grokster的底层技术
  • 专有协议，但提供一些详细信息
  • 和Gnutella很相似，但是指定了某些节点为超级节点
总结
Name Memory Lookuo Latency(查找延迟) Messages for a lookup(消息复杂度)
Napster O(1)/O(N)@server O(1) O(1)
Gnutella O(N) O(N) O(N)
Chord O(log(N)) O(log(N)) O(log(N))

分布式/混合体系结构

混合式p2p，bittorrent

  1. 客户端先到web上找到torrent文件
  2. 客户端解析torrent文件，得到很多的track，选择一个track server 上 里面有很多的Node iP
  3. 再选择一个IP进行，进行文件共享

分布式系统中的体系结构与中间件

一些关于自适应中间件的内容

分布式系统中的自我管理

  • 自我配置
  • 自我管理
  • 自我修复
  • 自我优化
    …

第三章：进程(Processes)

  • 线程
  • 虚拟化
  • 客户端
  • 服务器
  • 代码迁移

线程

处理器：提供一组指令以及自动执行一系列指令的能力
线程：线程是CPU调度的最小单位（最小的软件处理器）
进程：进程是资源分配的最小单位

上下文切换

  • 处理器上下文：存储在处理器寄存器中的值的最小集合，用来执行命令
  • 线程上下文：存储在处理器寄存器和内存中的值的最小集合，用来执行命令
  • 进程上下文：存储在处理器寄存器中的值的最小集合，用来执行线程命令

一个进程里线程共享数据段、地址段
进程的上下文切换需要涉及到内核，非常耗时间
一般，进程要比线程消耗更多的计算机资源

大量的APP使用进程进行协作完成某项功能，使用进程间通信，这是非常耗费资源的
第一步：从用户空间到内核空间
第二步：进程上下文切换，从A到B
第三步：从OS内核空间到用户空间

线程和操作系统

为了解决耗时间的问题，有两种解决方法：

  • 操作系统内核提供线程
  • 将线程作为用户级软件包的一部分

将线程作为用户级软件包的一部分的优缺点：
优点： 可以在不支持OS的情况下，也可以实现多线程
缺点： 若是某个线程需要调用IO，后面线程因为操作系统不支持多线程，而被阻塞；若操作系统不支持多线程，就不能将一个进程上的多线程在多个核上运行

操作系统内核提供线程的优缺点：
优点： 阻塞线程的操作不再是问题：内核调度另一个线程；外部事件很简单：内核(捕获所有事件)调度与事件相关联的线程
缺点： 低效率

混合式操作线程（依然在用户空间实现线程调度，但是如果发生阻塞后，让内核参加进来进行调度）的优缺点：
优点： 将用户空间的某个线程状态与内核空间内的轻量型进程进行绑定，轻量级线程(LWP)
缺点： 发生系统调用阻塞后，那个被阻塞的LWP一旦完成，需要反向调用上层通知上层事情做完

线程和分布式系统

  • 多线程客户端(主要问题在于网络延迟)
  • 多线程Web客户端：
  • 对其他机器的多个请求-响应调用(RPC)
多线程服务器
  • 提高性能
    • 启动线程处理传入请求比开启一个进程要节约资源
    • 单线程服务器不能利用多处理器
    • 隐藏网络延迟：其他工作可以在请求传入时完成
  • 更好的结构
    • 使用简单的阻塞I/O调用更容易
    • 多线程程序往往更简单
  • 一个有争议的领域
  • 两种线程
    • dispatch thread
    • worker thread
  • 服务器的三种模型
    • 多线程
    • 单线程进程模型
    • 有限状态机

虚拟化

传统计算机：硬件，操作系统，应用
虚拟化后：用主操作系统跑的硬件，虚拟层，虚拟机（虚拟机里有：虚拟硬件，客户操作系统，应用）

虚拟化：一个使软件进行间接调用硬件的层；操作系统运行在虚拟层上面，通过虚拟层来间接的调用下面的硬件

虚拟机定义：可以跑guest OS的软件
GOS定义：一个运行在虚拟环境中的操作系统
VMM：就是虚拟层(Virtual Machine Monitor)

虚拟化的分类

  1. 在应用层
  2. 在函数层
  3. 在操作系统层
  4. 硬件抽象层做虚拟化：对各种硬件去做虚拟化
  5. 在指令架构做虚拟化：把一个指令集翻译成另外一个指令集
在指令架构上进行虚拟化

将一个指令系统拦截翻译成另外一个指令系统
优点：可以兼容大量旧的二进制代码
缺点：性能损失较大

在硬件层上做虚拟化

虚拟机生成虚拟硬件环境，并通过虚拟化来管理硬件,应用的最广
优点：具有较高的性能和良好的应用隔离性
缺点：由于硬件型号的复杂性，实施的成本也很高

操作系统在虚拟化

是传统操作系统和用户位置之间的抽象层，在单个物理服务器和OS实例上创建容器，以利用数据中心的硬件和软件
eg：创建虚拟环境

在函数层进行虚拟化

不用虚拟化整个操作系统了，减少工作量

在应用层做虚拟化

最经典的虚拟化，将应用程序虚拟化为虚拟机
优点：最高的应用程序隔离
缺点：性能低，应用灵活性低，实现复杂

完全虚拟化：不需要修改GOS
半虚拟化：需要修改GOS

客户端

  • 互联网用户界面
    • 胖客户端：在客户机器上安装配置的一个功能丰富的交互式的用户界面，例如Oracle、DB2数据库的客户端管理工具。
    • 瘦客户端：在客户端-服务器网络体系中的一个基本无需应用程序的计算哑终端。
  • 分布式系统客户端软件

服务器

常规设计问题

服务器的定义：一个进程，在特定的传输地址上来等待传入服务请求

服务器的类型：

  • lterative：一次只能处理一个
  • Concurrent：同时处理多个请求
无状态服务器

在处理完请求后，不保存有关客户端状态的准确信息

  • 不记录文件是否已经打开(访问后直接关闭)
  • 不承诺使客户端缓存无效
  • 不跟踪客户端

于是这就导致了：

  • 客户端和服务器完全独立
  • 客户端或服务器崩溃导致的状态不一致减少
  • 可能的性能损失
有状态服务器

跟踪其客户端的状态：

  • 记录文件已经被打开，从而完成预存取
  • 知道客户端缓存了哪些数据，并允许客户端保留共享数据的本地副本

思考：HTTP提供的服务是无状态的，为啥“购物车”却具有状态？
状态的管理在应用层。

包含服务器感兴趣的客户端特定信息的一小段数据

  • 可以用于将当前客户端操作与以前的操作相关联
  • 用来存储状态

服务器集群

集群属于集中式架构
第一层：利用负载平衡器分发请求
第二层：服务器集群
第三层：与数据打交道

管理服务器集群

不是重点，略

代码迁移

  • 代码迁移的方法
  • 迁移和本地资源
  • 异构系统中的迁移

代码迁移的方法

为什么要进行代码迁移？
答：把代码从重载移到轻载上，减小通信成本，有些时候可以把代码移到数据服务器上，而不是把数据移到代码服务器上，因为代码一般很大，数据一般很小

迁移和本地资源

略

异构系统中的迁移

略

第四章：通讯(Communication)

  • 分层协议
  • 远程过程调用
  • 面向消息的通信
  • 面向流的通信
  • 组播通信

分层协议

-分层协议

  • 底层
  • 传输层
  • 应用层
  • 中间件层
    • 通信类型

分层协议

两种类型的协议

  • 面向连接的
  • 面向无连接的
底层
  • 物理层： 包含比特的规范和实现，以及他们在发送器和接收器之间的传输
  • 数据链路层： 规定将一系列比特传输到帧中
  • 网络层： 描述如何路由计算机网络的数据包
传输层

传输层为大多数分布式系统提供实际的通信设施

  • TCP： 面向连接、可靠的、面向流的通信
  • UDP： 不可靠(尽力而为)的数据报通信
应用层
  • 会话层： 对话控制，用于长时间传输的检查点
  • 表示层： 比特的含义、定义记录等
  • 应用层： 邮件、文件传输、通信终端等的协议
中间件层

也叫做分布式系统协议，逻辑上位于应用层的中间件，但是提供可由许多不同应用使用的公共服务和协议

通信类型

  • 瞬时通信
  • 持久通信
  • 同步通信
  • 异步通信

远端过程调用：在请求被处理后，一种同步瞬时通信

远程过程调用

分布式进程通讯希望能实现像本地进程间通信一样的操作

  1. 两个进程在同一个管道读取信息
  2. 一个进程调用另外一个进程
    对于方案一，在分布式系统中，这个管道必须是分布式的，具有全局性质，实现的代价很大
    于是考虑方案二，产生了RPC，远端过程调用

RPC协议调用方法：
参数—–打包—–通过TCP、IP协议传送—–网络发送—–接受—–解包—–参数

这种基本的RPC操作有点像 C/S架构

  1. 客户端请求远端过程
  2. 服务端调用本地过程并且返回结构，客户端一直在等待结果
  3. 客户端接受服务端发来的结果

远端过程调用的步骤及stubs在这之中的作用

  1. 将参数打包
  2. 想远端进程发送
  3. 远端解包
  4. 远端调用进程，返回值
  5. 本地得到值

Stubs(存根)

  • 客户端stub： 负责将参数消息打包，将远端调用代理为本地调用
  • server端stub： 负责将参数消息解包，并调用一部分服务器端应用程序实现代码

RPC的种类

  1. 同步RPC：客户端发送请求后，就一直等待
  2. 异步RPC：客户端发送请求后，就去做别的事情，等待服务端发送信息

面向消息的通信

  • 瞬时通信
  • 消息队列系统

瞬时通信

  • 套接字(Sockets)
  • 基于并行编程环境的消息传递接口(Message Passing Interface)

面向流的通信

  • 支持连续媒体
  • 流和服务质量
  • 流同步

组播/多播通信

多播通信的种类有

  1. 应用程序级别多播
  2. 基于Gossip的多播

思考： 为什么不直接使用IP层的IP组播？
因为IP组播在IP层工作，通常难以配置，需要太多的管理支持、协议等

应用程序级别多播

本质： 将分布式系统的节点组织成覆盖网路，并使用该网络传播数据。

基于Gossip的多播

背景

Epidemic Algorithms(流行病算法)
易于部署、健壮且故障恢复能力强，是一种潜在的有效机制

Epidemic Algorithms有时用作Gossip协议，因为Gossip类似于病毒在生物群落中传播的方式来传播信息。

Epidemics 协议的节点是一下之一：

  • 感染： 保存它愿意传播的数据
  • 易感： 尚未看到此数据
  • 移除： 不能或不愿意传播数据

逆熵：
节点P随机选择另一个节点Q，并交换更新，三种交换方式：

  • P只推送Q
  • P只拉取Q
  • P和Q进行信息交换
更新(信息传播)模型

当执行到快速传播更新时，只推送更新被证明是一种糟糕的方式
当许多节点受到感染时，基于拉取的方法效果会更好
轮次是指每个节点都有机会处于活动状态的一段事件
将单个更新传播到所有节点需要O(lgn)轮

  • 在信息传播中：
    • 如果P刚刚更新，它将联系任意节点Q
    • 如果Q已经更新，P将失去兴趣(变为移除节点)，概率为1/K
移除对象

少数节点维护休眠的死亡证书，如果再次感染，该证书将重新唤醒。

应用

略

第五章：命名(Naming)

  • 命名实体
  • 平面命名
  • 结构化命名
  • 基于属性的命名
  • 命名解析(无结构命名)
  • 命名空间实现(有结构命名)

命名的分类：

  • 无结构命名
  • 有结构命名

注意与以下的概念区分：

  • 无结构查找: 查找是没有规则的，例如：泛洪法
  • 有结构查找： 查找是有一定规则的，例如：二分查找

命名实体

  • 名称和地址
    名称用于表示分布式系统中的实体。要在实体上操作，我们需要在接入点访问它。接入点是通过地址命名的实体。

名称和地址是无关的

  • 标识符
    • 每个标识符至多引用一个实体
    • 每个实体至多由一个标识符引用
    • 标识符总是引用同一个实体

平面命名

无结构的命名和有结构的命名的区别：
无结构的命名（也叫flat name）中的标识符就是没有啥意义
有结构的命名中的表示符就有代表你本身的某些信息

Distributed Hash Tables——分布式哈希表(以chord为例)

考虑将多个节点组织成一个逻辑环，使用DHT实现结构化的命名查找

  • 每个节点被分配一个m比特标识符
  • 为每个实体分配唯一的m比特密钥
  • 实体属于具有最小id>=k的节点(称为其后继者)的管辖范围

DHT

拓展阅读：Chord

结构化命名

名称空间

  • 组织成名称空间
  • 名称空间由特定服务识别的有效名称的集合
  • 如果分层名称空间，则名称可以具有表示其位置的内部结构

优点：

  • 名称的每一个部分相对于单独的上下文进行解析
  • 潜力无限
  • 由不同实体管理的不同上下文

名称解析

根据名字解析含义

思考：怎么对名字进行解析？
答：采用就近原则，就是一层一层往上迭代找

名称空间的实现

名称空间始终将名称映射到某个对象

考虑分层命名图，并区别三个级别：

  • Global level：由高级目录节点组成。主要方面是这些目录节点必须由不同的管理机构共同管理
  • Administrational level： 包含可以以这样的方式分组的中级目录节点，使得每个组可以被分配给单独的管理机构
  • Managerial level： 由单个管理内的低级目录节点组成。主要问题是有效地将目录节点映射到本地名称服务器

示例：域名系统(最大的分布式系统)

略

基于属性的命名

略

第六章：同步(Synchronization)

  • 时钟同步
  • 互斥
  • 节点地全局定位
  • 选举算法

时钟同步

  • 物理时钟
  • 逻辑时钟
  • 矢量时间戳

思考： 为什么时钟同步很重要？

  • 需要精确地度量
  • 算法依赖
  • 分布式系统地正确性往往取决于全局系统不变量地满足程度

回顾一下之前提到过的在分布式系统中地四条原则：

  1. 没有一个节点知道整个系统的信息
  2. 节点决策仅仅依靠局部信息
  3. 一台机器故障不会影响系统
  4. 没有全局时钟的概念

物理时钟

时间标准

  • International Atomic Time(国际原子时)
  • Universal Coordinated Time(UTC)

时钟同步算法：

  • 外部时钟同步算法
    • Cristian’s Algorithm：有一个时间服务器，服务器是被动的
    • 网络时间协议： Network Time Protocol(RFC 1305)
  • 内部时钟同步算法
    • Berkeley Algorithm: 时间服务器是主动的
Cristian’s Algorithm

典型一个集中式服务器，把时间当成一个信息，想知道时间，就去time server上去请求一下

优点：简单，好部署，集中式服务器的特点都有
缺点：信息传输过程中是有延迟，发过来的时间不是当前时间

逻辑时钟

不再关心物理上现实中的时间，而是关心时间先后

在分布式系统中进行物理时钟同步的代价很高
因为每一个节点，都有自己的物理时钟，分布式系统里的节点数太大了，去同步成一个时钟，有点不太现实
因此，在每次的操作前，对操作的参与节点，标上逻辑前后顺序关系，这样做将问题简化了许多

使用happen-before来表示这种逻辑关系
如果e1发生在e2之前，就叫e1 happen before e2 记做$e_1 –> e_2$

也正如前面所说的操作参与了，才能标记逻辑顺序
如果两个节点没有信息交互，此时就没有顺序而言，标记顺序也没有用，所有这也是物理时钟同步代价高的原因，没必要进行大量无意义的时钟同步

$a$事件与$e$事件并发，没有事件先后顺序，记做$a || e$

假设$C(e)$表示事件e的时间戳，那么$e_1 –> e_2$，则有$C(e_1) < C(e_2)$，但反之不成立

每个进程都会维护自己的逻辑时钟
进程本身的事件好维护，每发生一个事件，逻辑时钟+1
产生进程间通信时，就直接把让接收消息的进程进行逻辑时钟和消息携带的时间戳进行比较，取二者的最大值+1

对排序按时间的严格性分为

  • 全序更新：全部事件都要排序
  • 因果序更新：有因果关系才排序
  • FIFO：有先后顺序的才排序

这里在逻辑时钟（lamport时钟）就有疑问了，对于数据库和备选数据库来说，update1和update2两个操作是并发的，不好来规定逻辑时钟，但是这两操作必须要有先后顺序，不然不能保证两个数据库的数据一致，

矢量/向量时间戳

向量时间戳用在因果序系统中，因为全序在分布式系统中非常消耗时间

每个进程Pi都有一个数组VCi[1..n]，其中VCi[j]表示进程Pi知道在进程Pj发生的事件数。
当Pi发送消息m时，它将1添加到VCi[i]，并将VCi与m一起作为向量时间戳vt（m）发送。结果：到达后，接收者知道Pi的时间戳。
当进程Pj传递它从Pi接收的带有向量时间戳ts（m）的消息m时，它
（1） 将每个VCj[k]更新为max{VCj[k]，ts（m）[k]}
（2） 将VCj[j]增加1。

互斥

防止同时访问资源

评价分布式系统的时候增加两个指标
MC：每个CS条目进程交换的信息数
SD：经过多少个消息才进入临界区

两种不同的类别：

  • 基于权限的方法
    • 集中式算法优点：容易部署，简单；缺点：容易阻塞，节点崩溃
    • 分散式算法:增加协调器，进行多数表决
    • 分布式算法
  • 基于令牌的方法
    • 令牌环算法:把资源在节点环上循环，不想访问丢给下一家，想访问就去访问;比较适合大家都想访问的那种资源，比较公平且高效

分布式互斥算法

分布式互斥

  1. 0号，2号都想要访问资源，所以0号，2号都要把访问资源时间发出去，1号不想访问资源，就不用发送时间戳
  2. 1号接收别人请求资源的消息且自己不需要访问资源，就都回了个OK，
  3. 2号因为访问资源的时间戳比0号小，所以就给0号发送OK，说0号节点，你先访问
  4. 0号节点在都收到其他节点的OK后，就去访问资源，并且也记下了2号也是访问资源的，所以在访问完资源后，就对2号发送OK，叫2号节点去访问资源

四种算法的比较

算法的比较

节点地全局定位

略

选举算法

略

分布式死锁

略

第七章：一致性(Consistency)与复制(Replication)

严格的一致性在分布式是不存在的，如果采用一定模型标准设定，就可以认为是一致性的

简介

复制：

  • 数据复制
  • 计算复制

为什么要进行复制：

  • 提高可靠性：数据存活率、可用性；增加信心
  • 提高性能： 拓展数量；减少地理区域内的访问时间

可能的问题：

  • 更新副本
  • 副本的管理
  • 重定向/路由

冲突操作：有写操作参与的操作才有可能冲突，所以维护一致性，必须保证对多个复制部分进行的冲突操作必须都是相同的操作

在分布式系统中，系统会引导进程在不同的数据块上进行存储操作，这数据块上的数据是相同的

以数据为中心的一致性

严格一致性

对数据项X的任何读取都返回对应于X的最近一次写入的结果的值

严格一致性

顺序一致性

数据存储上的所有进程的操作以某种顺序执行，并且每个单独进程操作按其程序指定的顺序出现在此序列中

顺序一致性

因果一致性

所有进程必须以相同的顺序看到潜在因果相关的写入，不同进程可能会以不同的顺序看到并发写入

因果一致性

以客户为中心的一致性

  • 单调读
  • 单调写
  • 读后写
  • 写后读

复制副本管理

  • 副本服务器放置
  • 内容复制和放置
  • 内容分发

一致性协议

  • Continuous consistency
  • Primary-Based Protocols
  • Replicated-Write Protocols

第八章： 容错(Fault Tolerance)

基本概念

设计一个分布式系统，它可以在不影响正确性或者显著影响整体的性能的情况下从部分故障中恢复

  • 故障预防：防止故障的发生
  • 容错： 构建一个组件，使其能够在出现故障的情况下满足其规范
  • 故障删除：减少故障的存在、数量和严重性
  • 故障预测：估计当前的数量、未来发生率以及故障的后果

故障类型一般分为：

  • 瞬态：出现一次，然后消失
  • 间歇性：发生，然后消失，然后重新出现
  • 永久性：持续存在

如何处理故障以获得容错能力：冗余。

  • 信息冗余
  • 时间冗余
  • 物理冗余

Process resilience

防止出现故障的进程： 进程组

  • 复制和分发组中的计算
  • 为流程集合提供抽象
  • “完全相同”的过程
  • 所有成员都会接收发送到群组的所有消息

拜占庭将军问题

动机： 在有故障部件的情况下建立可靠的系统

  • 有多个(潜在故障)组件计算同一功能
  • 对产出进行多数表决，以获得”正确”结果

f个故障，f+1个良好组件 ==> 总计2f+1

拜占庭将军的错误有几个？

  1. 输出任意值
  2. 不知道自己叛变了
  3. 坏节点恶意协同

实现 K 容错：

  • 集中口头消息： 2k+1
  • 分布式口头消息： 3k+1
  • 签名消息： k+2

可靠的客户端-服务端通信

略

可靠的组通信

略

分布式提交

  • 两阶段提交
    两阶段提交
  • 三阶段提交
    三阶段提交

恢复

简介

当系统发送故障时，需要使系统进入无错状态

  • 前向错误恢复：找到系统可以继续运行的新状态
  • 后向错误恢复：使系统返回到以前的无错误状态

检查点

当系统提供可靠的通信时，发送的消息也应当以一致的状态接收

级联回滚： 如果检查点是在”错误的”时刻进行的，则恢复线可能位于系统启动时

消息日志记录

不使用(昂贵的)检查点，而是尝试从最近的检查点重放通信行为 ===> 将消息存储到log中

第九章： 云计算

云计算的内容主要围绕了Google、Microsoft、Amazon三家展开讲解，分别介绍了各自的特点以及原理

着重讲解的是 Google 的云计算

Google 云计算原理

  • 概念回顾
  • Google云计算背景
  • 分布式文件系统GFS
  • 并行数据处理模型MapReduce
  • 分布式锁服务Chubby
  • 分布式数据库BigTable
  • Google AppEngine
  • Google 云计算技术小结

概念回顾

  • 网格计算
    • 在动态变化、由多个机构组成的虚拟组织中协调资源共享和求解问题
    • 实现跨组织平台异构资源的共享
  • 云计算
    • 一种商业计算模型
    • 将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需求获取计算力、存储空间以及信息服务
网格计算与云计算的比较
网格计算 云计算
异构资源 同构资源
不同规格 单一规格
虚拟组织 虚拟机
科学计算为主 数据处理为主
高性能计算机 服务器、PC
紧耦合 松耦合
免费 按量计算
标准化 尚无标准
科学界 商业社会
云计算的分类
  • 将软件服务(SaaS)：租赁人工智能、人脸识别软件、地图等
  • 将平台作为服务(PaaS):提供一层API，更加针对程序员提供编程环境
  • 将基础架构作为服务(IaaS): 租赁主机、所有环境自己搭建，更灵活

Google云计算背景

历史背景

略

Google 如何实现云计算的

Google 云计算平台技术架构

  • 文件存储： Google Distributed File System，GFS
  • 并行数据处理：MapReduce
  • 分布式锁：Chubby
  • 结构化数据表：BigTable

Google云计算架构

分布式文件系统GFS

假设与目标
  • 硬件出错是正常而非异常
    • 系统应当由大量廉价、易损的硬件组成
    • 必须保证文件系统整体的可靠性
    • 由软件来保证硬件的可靠性
  • 主要负载流数据的读写
    • 主要用于程序处理批量数据，而非与用户的交互或随机读写
    • 数据写主要是“追加写”，“插入写”非常少
  • 需要存储大尺寸的文件
    • 存储的文件尺寸可能是GB或TB量级，而且应当能支持存储成千上万的大尺寸文件
设计思路
  • 将文件划分为若干块(Chunk)存储
    • 每个块固定大小(64M)
  • 通过冗余来提高可靠性
    • 每个数据至少在3个数据块服务器上冗余
    • 数据块损坏的概率
  • 通过单个master来协调数据访问、元数据存储
    • 结构简单，容易保持元数据一致性
  • 无缓冲
    • 在客户端产生缓存，对于GFS而已，无局部性原则，实现缓存无意义
GFS的架构

  • 单一Master， 若干ChunkServer

  • 问题

    • 单点故障
    • 性能瓶颈
  • 解决方法：
    • 单点故障：采用多个影子Master节点进行热备，一旦主节点损坏，立刻选举一个新的主节点服务
    • 性能瓶颈： 尽量减少数据存取中Master的参与度
      • 不使用Master读取数据，仅用于保存元数据
      • 客户端缓存元数据
      • 采用大尺寸的数据块(64M)
      • 数据修改顺序交由Primary Chunk Server完成
Master 节点任务
  • 存储元数据
  • 文件系统目录管理与加锁
  • 与 ChunkServer 进行周期性通信
    • 发送指令、搜索状态，跟踪数据块的完好性
  • 数据块创建、复制以及负载均衡
    • 对ChunkServer的空间使用和访问速度进行负载均衡，平滑数据存储和访问请求的负载
    • 对数据块进行复制、分散到ChunkServer上
    • 一旦数据块冗余小于最低数，就发起复制操作
  • 垃圾回收
    • 在日志中记录删除操作，并将文件改名隐藏
    • 缓慢地回收隐藏文件
    • 与传统文件删除相比更简单、更安全
  • 陈旧数据块删除
    • 探测陈旧的数据块，并删除
GFS 架构的特点
  • 采用中心服务器模式
    • 可以方便地增加Chunk Server
    • Master掌握系统内所有Chunk Server的情况，方便进行负载均衡
    • 不存在元数据的一致性问题，因为采用的是集中式
  • 不缓存数据
  • 在用户态下实现
    • 直接利用Chunk Server的文件系统存取Chunk，实现简单
    • 用户态应用调试简单，利于开发
    • 用户态的GFS不会影响Chunk Server 的稳定性
  • 提供专用的访问接口
    • 未提供标准的POSIX访问接口
    • 降低GFS的实现复杂度
GFS 的容错方法

-

  • Chunk Server 容错
    • 每个Chunk有多个存储副本(通常是三个)，分别存储于不同的服务器上
    • 每个Chunk又划分为若干个Block(64KB)，每个Block对应一个32bit的校验码，保证数据正确
    • 若某个Block错误，则转移至其他Chunk副本
  • Master容错机制
    • 三类元数据：命名空间(目录结构)、Chunk与文件名的映射以及Chunk副本的位置信息
    • 前两类通过日志提供容错，Chunk副本信息存储于Chunk Server，Master出现故障时可恢复

并行数据处理模型MapReduce

并行计算模式：
把编程分为两个部分，Worker负责对数据的处理，Master负责对数据的切分，对Worker拷贝复制到每一份数据，分配Worker参数，接收返回的参数

  • 为什么要MapReduce？
    计算问题简单，但求解困难
    • 待处理数据量巨大(PB级别)，只有分布在成百上千个节点上并行计算才能在可接受的时间内完成
MapReduce
  • 一个软件架构，是一种处理海量数据的并行编程模式
  • 用于大规模数据集(通常大于1TB)的并行运算
  • MapReduce实现Map和Reduce两个功能
    • Map把一个函数应用于集合中所有成员，然后返回一个基于这个处理的结果集
    • Reduce对结果集进行分类和归纳
    • Map和Reduce两个函数可能会并行执行
文件存储位置
  • 源文件：GFS
  • Map处理结果：本地存储
  • Reduce处理结果：GFS
  • 日志：GFS
MapReduce的容错
  • Worker故障
    • Master周期性的ping每个Worker，如果master在一个确定的时间段内没有收到worker返回的信息，那么就把这个Worker标记为失败节点
    • 重新执行该节点上已经执行或尚未执行的Map任务
    • 重新执行该节点上未完成的Reduce任务，已经完成的不再执行(因为文件保存在GFS，全部看得到)
  • Master故障
    • 定期写入检查点数据
    • 从检查点恢复
MapReduce的优化
  • 任务备份机制
    • 慢的Worker会严重地拖延整个执行完成的时间
      • 由于其他任务占用了资源
      • 磁盘损坏
    • 解决方案：在临近结束的时候，启动多个进程来执行尚未完成的任务
  • 本地处理
    • Master调度策略
  • 跳过有问题的记录

分布式锁服务Chubby

  • 主要用于解决分布式一致性的问题
    • 在一个分布式系统中，有一组的Process，它们需要确定一个Value。
    • 于是每个Process都提出一个Value，一致性就是指只有其中一个Value能够被选中作为最后确定的值
    • 并且这个值被选出来后，所有Process都需要被通知到
  • 粗粒度的分布式锁服务
    • Chubby是Google为解决分布式一致性问题而设计的提供粗粒度锁服务的文件系统(Chubby就是GFS文件的一种)
    • 其他分布式系统可以使用它对共享资源的访问进行同步

粗粒度：

  • 文件系统相对内存颗粒度大
  • 时间上，支持长时间加锁
Chubby的设计目标
  • 需要实现的特性
    • 高可用
    • 高可靠
    • 支持粗粒度的建议性锁服务(支持长时间加锁)
    • 支持小规模文件直接存储
  • 不作为考虑的特性
    • 高性能
    • 存储能力
Chubby文件系统
  • Chubby 系统本质上就是一个分布式的、存储大量小文件的文件系统
  • Chubby 中的锁就是文件
  • 在GFS中，创建文件就是进行“加锁”操作，创建文件成功就是那个server抢占到了“锁”
  • 用户通过打开、关闭和存取文件，获取共享锁或者独占锁；并且通过通信机制，向用户发送更新信息
Chubby的应用
  • 主节点选举
  • 独占式锁
  • 共享锁
  • 数据存取应用

分布式数据库BigTable

BigTable：基于GFS和Chubby的分布式存储系统，对数据进行结构化存储和管理

设计目标
  • 具有广泛的适应性
    • 支持Google系列产品的存储需求
  • 具有很强的可拓展性
    • 根据需要随时加入或撤销服务器
    • 应对不断增多的访问需求
  • 高可用性
    • 单个节点易损，但要确保几乎所有的情况下系统都可用
  • 简单性
    • 简单的底层系统可减少系统出错概率，为上层开发带来便利
数据模型
  • 行
    • 每行数据有一个可排序的关键字和任意列项
    • 字符串、整数、二进制串甚至可串行化的结构都可以作为行键
    • 表按照行键“逐字节排序”顺序对行进行有序化处理
    • 表内数据非常稀疏，不同的行的列数完全目可以大不相同
    • URL是较为常见的行键，存储时需要倒排
  • 列
    • 特定含义的数据的集合，如图片、链接等
    • 可将多个列归并为一组，称为簇(family)
    • 同一个簇的数据被压缩一起保存
    • 簇是必须的，是BigTable中访问控制的基本单元
  • 时间戳
    • 保存不同时期的数据，比如网页快照
  • “A big table”
    • 表中的列可以不限制地增长
    • 表中的行可以不限制地增长
  • 无数据校验
    • 每一行可存储任意数目的列
    • 任意类型的数据均可存储
    • 数据的有效性校验由构建于其上的应用系统完成
  • 一致性
    • 针对同一行的多个操作可以分组合并
    • 不支持对多个进行修改的操作
物理视图
  • 逻辑上的“表”被划分成若干个子表(Tablet)
    • 每个Tablet由多个SSTable文件组成
    • SSTable文件存储在GFS之上
  • 每个子表存储了table的一部分行
    • 元数据：起始行键、终止行键
    • 如果子表体积超过了阈值(如200M)，会进行分割
主节点的职责
  • 为每个子表服务器分配子表，对外提供服务
  • 与GFS垃圾回收进行交互，收回废弃的SSTable
  • 探测子表服务器的故障与恢复
  • 负载均衡
子表服务器故障恢复
  • 新的故障
    • 子表服务器内存中的memtable丢失
  • 恢复方法
    • 按照tablet将该服务器对应的日志分片
    • 为每个失效的tablet分配新的子表服务器
    • 新子表服务器读取对应的分段commit log，并按照日志修改tablet
    • 删除commit log中已实施的内容
    • 重新对外提供服务
性能优化
  • 局部性群组(Locality Group)
    • 根据需要，将原本不存储在一起的数据，以列族为单位存储至单独的子表
    • 如用户对网站排名、语言等分析信息感兴趣，那么可以将这些列族放至单独的子表，减少无用信息读取，改善存取效率
  • 布隆过滤器(Bloom Filter)
    • 布隆过滤器是判断某个元素是否隶属于集合
    • 优点：误判率低，其存储空间仅为Hash表的1/8至1/4
    • 用于判断列键是否位于SSTable中，快速确定某个列键的位置

Google AppEngine

略

Google 云计算技术小结

略

第十章：微软、亚马逊云计算

没精力了。。。。写不动了。。。。