《分布式计算原理与应用》黄秋颖

课程内容

分布式系统基础：分布式系统特征、分布式计算范型、Socket编程、RMI范型与应用……
云计算原理与技术
大数据技术与实践

1 分布式计算概述

分布式系统是由若干通过网络互联的计算机组成的软硬件系统，且这些计算机互相配合以完成一个共同的目标

分布式系统运行在不具有共享内存的多台机器上，但在用户眼中却像是一台计算机

分布式计算指在分布式系统上执行的计算。分布式计算是将一个大型计算任务分成很多部分分别交给其他计算机处理，并将所有的计算结果合并为原问题的解决方案。与并行计算不同的是，一个是事务密集型，一个是计算密集型

具有共享存储器的通常称为多处理器（multiprocessor），而不具有共享存储器的称为多计算机（multicomputer），多用于分布式系统（松散耦合）

一个分布式系统组织成中间件形式，中间件层分布在多台机器上

分布式计算的特点

资源共享 —— 可共享系统中的硬件、软件、数据等信息资源
分布式透明处理平台 —— 展现给用户的是一个统一的整体系统
高性价比
应用分布性 —— 多数应用本身就是分布式的
高可靠性 —— 容错机制
可扩展性
高度灵活性 —— 能够兼容不同硬件厂商的产品，兼容低配置机器和外设而获得高性能计算

优点：超大规模、虚拟化、高可靠性、通用性、高可伸缩性、按需服务、极其廉价、容错性

弱点

多点故障：一台或多台计算机的故障，或一条或多条网络链路的故障，都会导致分布式系统出现问题
安全性：分布式系统为非授权的用户的攻击提供了更多机会

云计算与网格计算

网格计算：利用互联网把地理上广泛分布的各种资源（计算、存储、带宽、软件、数据、信息、知识等）连成一个逻辑整体，为用户提供一体化信息和应用服务（计算、存储访问等）

网格计算强调资源共享，任何节点都可以请求其他节点的资源，任何节点都需要贡献一定资源给其他节点。云计算强调专有，请求或获取的资源是专有的而且由少数团体提供，使用者不需要共享自己的资源

网格计算侧重并行的计算集中性需求，并且难以自动扩展。云计算侧重事务性应用，大量的单独的请求，可以实现自动/半自动扩展（IaaS、PaaS、SaaS）

IaaS PaaS SaaS 的区别与联系
- IaaS、PaaS、SaaS 是云计算服务模型中的三种主要形式，它们分别代表了基础设施即服务 (Infrastructure as a Service)、平台即服务 (Platform as a Service) 和软件即服务 (Software as a Service)
- IaaS 是指云服务提供商提供基础设施，包括计算资源、网络资源和存储资源，用户可以在这个基础设施上搭建自己的应用环境，有完全的控制权。典型的 IaaS 供应商有 Amazon Web Services (AWS) 和 Microsoft Azure
- PaaS 是在 IaaS 的基础上提供了更高级别的服务，包括应用开发、测试、部署和扩展等，用户只需关注应用程序本身，不需要关心底层基础设施的管理和维护。PaaS 的优势在于可以大幅度减少应用程序的开发和部署成本。典型的 PaaS 供应商有 Heroku 和 Google App Engine
- SaaS 是一种完全托管的服务模型，供应商提供完整的应用程序，用户无需安装、配置、管理软件，只需要通过浏览器或 API 访问即可。典型的 SaaS 供应商包括 Salesforce 和 Dropbox
- 在这三种服务模型中，IaaS 提供的是最基础的服务，需要用户自己搭建应用环境；PaaS 提供了更高层次的服务，用户只需要关注应用程序本身，而 SaaS 则提供了最高层次的服务，用户无需关心任何技术细节，只需要使用即可

云计算包含的网格计算特征：

提供在线的计算、存储等服务
超大规模的资源组合
资源的虚拟化

云计算与分布式计算

分布式计算（狭义）：将待解决的问题分成多个小问题，再分配给许多计算机系统处理，最后将处理结果加以综合

特点：把计算任务分派给网络中的多台独立的机器

优点：稀有资源可以共享、通过分布式计算可以在多台计算机上平衡计算负载、可以把程序放在最适合运行它的计算机上

云计算包含的分布式计算特征：

通过资源调度和组合满足用户的资源请求
对外提供统一的、单一的接口

云计算与并行计算

并行计算：同时使用多种计算机资源解决计算问题的过程。通常指一个程序的多个部分同时运行于多个处理器上

特点：把计算任务分派给系统内的多个运算单元

并行计算问题的特征：

将工作分离成离散部分，有助于同时解决
随时并及时地执行多个程序指令（多条线同时运行）
多计算资源下解决问题的耗时要少于单个计算资源下的耗时

云计算包含的并行计算特征：

用户资源（单一类型和组合类型）请求的同时处理

云计算与对等计算

对等计算系统中，每个节点都拥有对等的功能与责任，既可以充当server向其他节点提供数据或服务，又可以作为client享用其他节点提供的数据或服务，节点之间的交互可以是直接对等的，任何节点可以随时自由地加入或离开系统

对等计算：有可能作为云计算的一个类型

云计算对超大规模、多类型资源的统一管理是困难的；对等计算具有鲁棒性、可扩展性、成本、搜索等方面的优点

P2P系统有更强的抗毁能力

总的来说，这些概念都与计算资源的共享和分布式计算有关，但它们的重点不同。云计算着重于提供可靠、高效、经济的计算服务，而网格计算则是利用分散的计算资源来执行计算密集型任务。分布式计算利用多台计算机协作来解决单个计算机无法处理的问题，而并行计算则是利用多个处理器或计算机同时处理同一个问题。对等计算则是强调节点之间的平等性，通常用于文件共享、通信和数据存储等方面。

分布式系统介绍

分布式系统指通过网络互连，可协作执行某个任务的独立计算机集合。不共享内存或程序执行空间的一系列计算机被认为是相互独立的

可靠性：故障时仍能提供服务的能力
可扩展性：为了持续增长的任务数量可以不断扩展的能力
可用性：尽可能限制系统因故障而暂停的能力
高效性

CAP理论

C 一致性：所有客户端总是有同样的数据视图
A 可用性：每个客户端总是能读和写
P 分区容忍性：当集群中的某些节点无法联系时仍能正常提供服务

CAP理论告诉我们：一个分布式系统不可能满足一致性，可用性和分区容错性这三个需求，最多只能同时满足两个

CA 有一致性和可用性的系统，通常扩展性能不高，最简单的做法是把所有与事务相关的内容都放到同一台机器上，不具有分区容错性，如传统的关系数据库
CP 为了满足一致性，在系统分区期间会停止服务，直到数据恢复一致，当出现网络分区的情况时，受影响的服务需要等待数据一致，因此在等待期间就无法对外提供服务
AP 通常注重系统性能和扩展性，而非强一致性，即允许系统返回不一致的数据

对大型网站，可用性与分区容忍性优先级要高于数据一致性，一般会尽量朝着A、P的方向设计，然后通过其它手段保证对于一致性的商务需求

不同数据对于一致性的要求是不同的

例子：用户评论对不一致是不敏感的，相对较长时间的不一致并不会影响交易和用户体验；产品价格数据则相反

不同程度的一致性处理方式

强一致性（即时一致性）：假如A先写入一个值到存储系统，存储系统保证后续的A，B，C的读操作都返回最新值

在单机环境中，强一致性可以由数据库的事务来保证
在多机环境中，强一致性很难做到

弱一致性：存储系统不能保证A，B，C到读取操作能够读到最新值

这种情况下又一个"不一致性窗口"的概念，特指从A写入值，到后续操作A，B，C读取到最新值这一段时间

最终一致性：存储系统保证如果在A，B，C后续读取之前没有其他写操作更新同样的值的话，最终所有读操作都会读取到A写入的最新的值

是弱一致性的一种特例
通过提交处理的半同步、半异步或全异步，取得最终一致性效果
最终一致性使得数据的提交具有延时性，而在一定范围的延时性范围内（比如一秒），应用的可用性是OK的
如果没有失败发生的话，"不一致性窗口"的大小依赖以下几个因素：
- 交互延迟
- 系统的负载
- 复制架构中replica的个数（可以理解为master/slave模式中，slave的个数）
例子：DNS系统 —— 更新一个域名解析后，根据配置策略以及缓存控制策略的不同，最终所有客户都可以看到最新的映射

服务器一致性

N：节点的个数
W：更新时需要确认已被更新的节点的个数
R：读数据时读取数据的节点个数

如果W+R>N，那么分布式系统就会提供强一致性的保证，因为读取数据节点和被写入的节点是有重叠的

如果N=W,R=1，任何一个写节点失效，都会导致写失败，因此可用性会降低，但是由于数据分布的N个节点是同步写入的，因此可以保证强一致性

在一个RDBMS的复制模型中(Master/Slave)，假如N=2，那么W=2，R=1，此时是一种强一致性，但是这样造成的问题就是可用性的减低，因为要想写操作成功，必须要等2个节点都完成以后才可以

例子：在分布式系统中，一般都要有容错性，因此一般N都大于3的，此时根据CAP理论，一致性，可用性和分区容错性最多只能满足两个，那么我们就需要在一致性和分区容错性之间做一个平衡
- 如果要高的一致性，那么就配置为N=W，R=1，这个时候可用性就会大大降低
- 如果想要高的可用性，那么此时就需要放松一致性的要求，此时可以配置W=1，这样使得写操作延迟最低，同时通过异步的机制更新剩余的N-W个节点

当存储系统保证最终一致性时，存储系统的配置一般是W+R<=N，此时读取和写入操作是不重叠的,则是弱一致性

例子：W = 1，R = N，对写操作要求高性能高可用；R = 1，W = N, 对读操作要求高性能高可用，比如类似cache之类业务

ACID

一个数据库事务具有ACID四性

A - Atomicity 原子性，是指事务必须是原子工作单元，对于其数据修改，要么全都执行，要么全都不执行
C - Consistency 一致性，是指事务在完成时，必须使所有的数据都保持一致状态
I - Isolation 隔离性，是指由并发事务所做的修改必须与任何其它并发事务所做的修改隔离
D - Durability 持久性，是指事务完成之后，它对于系统的影响是永久性的，该修改即使出现致命的系统故障也将一直保持

BASE

BASE的基本含义是基本可用（basically availble）、软状态（soft-state）和最终一致性（eventual consistency）

基本可用：指一个分布式系统的一部分发生问题变得不可用时，其他部分仍然可以正常使用，也就是允许分区失败的情形出现
软状态：与硬状态（hard-state）相对，指状态可以有一段时间不同步，具有一定的滞后性

BASE模型完全不同于ACID模型，它通过牺牲高一致性，获得可用性和可靠性（容错性）

BASE思想主要强调基本的可用性，如果你需要高可用性，也就是纯粹的高性能，那么就要以一致性或容错性为牺牲，BASE思想的方案在性能上还是有潜力可挖的。

分布式系统设计中的关键问题

透明性

种类	含义
位置透明	用户不知道资源位于何处
迁移透明	资源可以不改名地随意移动
复制透明	用户不知道有多少个拷贝存在
并发透明	多个用户可以自动的共享资源
并行透明	系统活动可以在用户没有感觉的情况下并行发生

灵活性

微内核不提供文件系统、目录系统、全部的进程管理，或系统调用

高度模块化：对于每个服务都有一个定义好的接口，每个客户都能访问所有服务，而与位置无关
系统易于实现、安装和调试新的服务，添加、删除或更改服务无需停止现有系统和启动新内核，使得微内核具有很好的灵活性
不满足于现有系统服务的用户可以自己编写服务

可靠性

可用性 availability：系统可用时间的比例
- 备份保持一致性
安全性：资源不被非法用户使用
- 身份认证、入侵监测
容错性
- 硬软件冗余
- 恢复和接管

性能

响应时间、吞吐量、系统的利用率、网络容量消耗程度
并行粒度

可伸缩性 scalability

避免：集中式硬件/集中式算法/集中式数据结构

可扩性技术

没有一台机器上存放着关于系统状态的全部信息
机器只是基于本地信息作出决定
一个机器出故障不会破坏算法
不一定存在全局时钟

分布式计算基础技术

进程间通信 IPC

在互相独立的进程间通信及共同协作以完成某项任务的能力

当一个进程与另一个进程进行通信时，IPC被称为单播 unicast
当一个进程与另一组进程进行通信时，IPC被称为组播 multicast

IPC程序接口的四种基本操作

发送 send：该操作由发送进程发起，旨在向接收进程传输数据。操作必须允许发送进程识别接收进程和定义待传数据
接收 receive：该操作由接收进程发起，旨在接收发送进程发来的数据。操作必须允许接收进程识别发送进程和定义保存数据的内存空间，该内存随后被接受者访问
连接 connect：对面向连接的IPC，必须有允许在发起进程和指定进程间建立逻辑连接的操作：其中以进程发出请求连接操作而另一进程发出接受连接操作
断开连接 disconnect：对面向连接的IPC，该操作允许通信的双方关闭先建立起来的某一逻辑连接

事件同步

IPC中的一个主要难点是进行IPC的各相关进程是独立执行的，各进程不知道对方进程的情况。协议涉及的双方必须按特定顺序发起IPC操作，否则可能通信失败。

因此，参与通信的两个进程需要同步他们的操作，由一方发送数据，另一方则需要等待所有数据发送完成时，开始接收数据

IPC设施提供事件同步的最简单的方式是使用阻塞机制或同步（synchronous），即挂起某一进程的执行，直到该进程发起的某个操作之行结束。

另外，IPC可以异步（asynchronous）或非阻塞操作。进程发起的异步操作不会引起阻塞。因此，一旦向IPC设施发出异步操作后，进程可以继续执行。当该异步操作完成后，进程才会随后得到IPC设施的通知。

同步send & 同步receive

receive操作的发出导致该发起进程挂起，直到接收完成该操作的所有数据。同样地，send操作的发出导致发送进程挂起。当发送的数据被进程2接收后，主机2的IPC设施向主机1的IPC设施发送一条确认信息，进程1随后可被解锁。注意，消息确认由两台主机的IPC设施处理，并且对两个进程是透明的。

异步send & 同步receive

receive操作的发出将导致接收进程挂起，直到接收到满足操作的所有数据为止。然而，send操作的发出不会导致发送进程挂起。发送进程不会被阻塞，因此，进程2所在主机的IPC设施不必发送确认消息

同步send & 异步receive

情形1

接收操作请求的数据在receive操作发出时已经到达，在这种情况下，数据被立刻传送到进程2，主机2的IPC设施返回的确认消息将进程1解锁。

情形2

receive操作请求的数据仍未到达；没有数据传递到该进程。接收进程负责确定已真正接收到数据，如果需要的话，重复receive操作，直到数据到达（注意，通常由程序使用循环来重复发出receive操作，直到等待的数据全部接收。这种重复尝试技术被称为轮询技术）。进程1被无限期阻塞，直到进程2重发receive请求，并最终收到主机2 IPC设施的确认消息。（发送可能早于接收，采用轮询技术）

情形3

receive操作请求的数据仍未到达。当请求数据到达时，主机2的IPC