云计算1-2章

第1章 分布式计算概述

1.分布式计算的定义

①分布式计算是一门计算机科学，主要研究对象是分布式系统。在介绍分布式计算概念前，首先简单了解一下什么是分布式系统。

简单地说，一个分布式系统是由若干通过网络互联的计算机组成的软硬件系统[1]，且这些计算机互相配合以完成一个共同的目标（往往这个共同的目标称为“项目”）

②分布式计算指在分布式系统上执行的计算。

分布式计算是将一个大型计算任务分成很多部分分别交给其他的计算机处理，并将所有的计算结果合并为原问题的解决方案。

这里与并行计算不同的是，并行计算是使用多个处理器并行执行单个计算。

2.分布式计算的优缺点

优点

?超大规模

?虚拟化

?高可靠性

?通用性

?高可伸缩性 

?按需服务

?极其廉价

?容错性

3.分布式计算相关计算形式

分布式云计算    网格计算 并行计算云计算  

Distributed computing  grid computing parallel computing cloud computing  

Internet of Thing  物联网

BigData 大数据

4.集中计算与分布式计算

最简单的计算形式是，利用单台计算机（如个人计算机）进行计算。多用户也可参与单机计算。

在该计算形式中，并发用户可通过分时技术共享使单台计算机中的资源，往往我们称这种计算方式为集中式计算。

5.串行计算与并行计算

并行计算或称并行运算是相对于串行计算的概念（如图1-2所示），

最早出现于上个世纪六七十年代，指在并行计算机上所作的计算，即采用多个处理器来执行单个指令。

通常并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。

它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。

并行计算可分为时间上的并行和空间上的并行。

并行运算与分布式计算的区别是：分布式计算强调的是任务的分布执行，而并行计算强调的是任务的并发执行

6.云计算概念的提出

l  提出者：     Google工程师，比希利亚，27岁

l  出发点： 推广Google超级强大的计算资源，招贤纳士

l  结果：   蜂拥而至，名噪一时，被视为“云”的起源

7.云计算与网格计算

①网格计算：利用互联网把地理上广泛分布的各种资源（计算、存储、带宽、软件、数据、信息、知识等）连成一个逻辑整体，

就像一台超级计算机一样，为用户提供一体化信息和应用服务（计算、存储、访问等）。

②网格计算强调资源共享，任何节点都可以请求使用其它节点的资源，任何节点都需要贡献一定资源给其他节点。

云计算强调专有，请求或获取的资源是专有的，并且由少数团体提供，使用者不需要贡献自己的资源。

③网格计算侧重并行的计算集中性需求，并且难以自动扩展。

云计算侧重事务性应用，大量的单独的请求，可以实现自动或半自动的扩展。

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

（1）提供在线的计算、存储等服务

（2）超大规模的资源组合

（3）资源的虚拟化

8.云计算与分布式计算

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

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

优点

a.稀有资源可以共享

b.通过分布式计算可以在多台计算机上平衡计算负载

c.可以把程序放在最适合运行它的计算机上

②流行的分布式项目

§  SETI@Home：       寻找外星文明

§  RC-72：           密码分析破解，研究和寻找最为安全的密码系统

§  Folding@home：    研究蛋白质折叠、聚合问题

§  United Devices：  寻找对抗癌症的有效的药物

§  GIMPS：           寻找最大的梅森素数（解决较为复杂的数学问题）

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

（1）通过资源调度和组合满足用户的资源请求

（2）对外提供统一的、单一的接口

9.云计算与并行计算

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

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

并行计算问题的特征

n  将工作分离成离散部分，有助于同时解决

n  随时并及时地执行多个程序指令（多条线同时运行）

n  多计算资源下解决问题的耗时要少于单个计算资源下的耗时

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

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

10.云计算与对等计算

对等计算系统中，每个节点都拥有对等的功能与责任，既可以充当服务器向其他节点提供数据或服务，又可以作为客户机享用其他节点提的供数据或服务，

节点之间的交互可以是直接对等的，任何节点可以随时自由地加入或离开系统。

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

n  预测：将可能以“对等子云”的形式出现在云计算中。

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

n  Google的云计算服务曾出现严重问题，Gmail、Blogger和Spreadsheet等服务均长时间当机。亚马逊S3云计算服务也曾出现问题。而P2P系统则有更强的抗毁能力。

1.分布式系统介绍

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

 

2.分布式系统特征

v  可靠性：   指一个分布式系统在它的某一个或多个硬件的软件组件造成故障时，仍能提供服务的能力。

v  可扩展性： 指一个系统为了支持持续增长的任务数量可以不断扩展的能力。

v  可用性：   指一个系统尽可能地限制系统因故障而暂停的能力。

v  高效性：   指一个分布式系统通过分散的计算资源来实现任务执行的高效率。

3.CAP理论

 

1. 进程间通信

   

 

 

①分布式计算的核心技术是进程间通信（interprocess communication，IPC），

即在互相独立的进程（进程是程序的运行时表示）间通信 及 共同协作以完成某项任务的能力。

②在分布式计算中，两个或多个进程按约定的某种协议进行IPC，此处协议是指数据通信各参与进程必须遵守的一组规则。

③在协议中，一个进程有些时候可能是发送者，在其他时候则可能是接收者。

当一个进程与另一个进程进行通信时，   IPC被称为单播（unicast）；

当一个进程与另外一组进程进行通信时， IPC被称为组播（multicast）。

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

发送（Send）。该操作由发送进程发起，旨在向接收进程传输数据。操作必须允许发送进程识别接收进程和定义待传数据。

接收（Receive）。该操作由接收进程发起，旨在接收发送进程发来的数据操作必须允许接收进程识别发送进程和定义保存数据的内存空间，该内存随后被接收者访问。

连接（Connect）。对面向连接的IPC，必须有允许在发起进程和指定进程间建立逻辑连击的操作：其中以进程发出请求连接操作而另一进程发出接受连接操作。

断开连接（Disconnect）。对面向连接的IPC，该操作允许通信的双方关闭先前建立起来的某一逻辑连接。

3. HTTP进程间通信实例

4. 事件同步

IPC中的一个主要难点是进行IPC的各相关进程是独立执行的，各进程不知道对方进程的情况。

协议涉及的双方必须按特定顺序发起IPC操作，否则可能通信失败。

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

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

另外，IPC操作可以是异步（asynchronous）或非阻塞操作（nonblocking）。进程发起的异步操作不会引起阻塞。

因此，一旦向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解锁

(四)同步send和异步receive情形2

receive操作请求的数据仍未到达；没有数据传递到该进程。

接收进程负责确定已真正接收到数据，如果需要的话，重复receive操作，直到数据到达

（注意，通常由程序使用循环来重复发出receive操作，直到等待的数据全部接收。这种重复尝试技术被称为轮询技术）。

进程1被无限期阻塞，直到进程2重发receive请求，并最终收到主机2 IPC设施的确认消息

 

 

 

 

(五) 同步send和异步receive情形3

receive操作请求的数据仍未到达。

当请求数据到达时，主机2的IPC设施将通告进程2，此时进程2可以继续处理数据。

该情形要求进程2提供一个可以被IPC设施调用的侦听接口或事件号，用于向进程通告请求数据的到达

(六) 异步send和异步receive

如果双方都没有阻塞，数据能传送到接收者的唯一途径就是由IPC设施保留接收到的数据。

接收进程随后可以被通告数据到达了。

另外，接收进程也可以轮询数据是否已经到达，并在所等待的数据到达时，对其进行处理

5. 死锁和超时

u  虽然阻塞提供IPC必要的同步，阻塞以错误的顺序发起是可能会引起死锁（ deadlocks ）。

u  连接和接收操作可能会导致无限期的阻塞（ indefinite blocking ），死锁也可能造成无限期的阻塞。

u      例如，进程Process1和进程Process2因相互等待对方而无限期阻塞，此时，即由无限期阻塞而产生了进程的死锁。见后页的图示说明。

u  我们一般不期望被请求的进程被无期限挂起（即无期限阻塞），无期限阻塞可以通过使用超时或子线程来避免。

 

6. 死锁

尽管阻塞机制为IPC提供了必要的同步，但是同步操作如果按照错误的顺序执行就可能会产生死锁，造成进程被无限期挂起。

7. 用线程实现异步操作

在使用IPC编程接口时，了解该操作是同步操作还是异步操作是非常重要的。

如果阻塞操作仅仅是发送或接收，那么编程人员就可以使用子进程或线程来提供阻塞，让程序的主线程或父进程继续执行其他的任务，

而子进程或线程将被挂起，直到接收到响应为止，这就是所说的异步处理。

 

 

 

 

 

8. 事件状态图

一个包括两个并发进程A和B的请求-响应协议的事件状态图。  每个进程随事件变化的执行情况用垂直线表示，时间沿垂直线向下增加。

执行线上的实线段表示进程处于活动状态的时间段，虚线段表示进程被阻塞的时间段。

 

9. HTTP顺序状态图

 

 

 

 

10. HTTP会话期间的对话

11. IPC范型

在最低抽象层，IPC利用底层的串行或并行数据传输机制，在连接上传输二进制流。例如，这种IPC范型可以用于编写网络驱动软件。

这种形式的IPC属于网络或操作系统编程领域。

下一个抽象层是众所周知的一种范型，称作socket应用程序接口（socket API）。在socket范型中，两个进程使用名为socket的逻辑构造交换数据，每一方都要建立一个socket。待发送数据被写入socket。在另一端，接收进程从自身的socket中读取或提取数据。

远程过程调用（remote procedure call）或远程方法调用（remote method invocation）范型通过允许向远程进程发送过程调用或方法调用，来提供更高层次的抽象。这是，数据作为参数和返回值，在两个进程间进行传递。

 

 

第2章 分布式计算范型概述

1.消息传递

一个进程发送代表请求的消息，该消息被传送到接受者；接受者处理该请求，并发送一条应答消息。

随后，该应答可能触发下一个请求，并导致下一个应答消息。

如此不断反复传递消息,实现两个进程间的数据交换.

基于该范型的开发工具有Socket应用程序接口（Socket API）和信息传递接口（Message Passing Interface，MPI）等

2. 客户-服务器范型

客户-服务器范型（简称CS范型）是网络应用中使用最多一种分布式计算范型，该模型将非对称角色分配给两个协作进程。

其中，服务器进程扮演服务提供者角色，被动地等待请求的到达。

另一个客户进程向服务器发起请求，并等待服务器响应。

  当前最流行的互联网应用WWW（或称为WEB）是基于客户-服务器范型的一个典型分布式应用。

 

 

 

 

 

 

 

 

3. Peer-to-Peer范型

peer-to-peer范型源于P2P网络（又称为对等计算网络），简称为P2P范型。             P2P网络是无中心服务器。

在peer-to-peer范型中，各参与进程的地位是平等的，都具有相同的性能和责任（因此，称它们为peer）。 每个参与者（进程）都可以向另一个参与者发起请求和接收响应。

在一个基于P2P范型的分布式应用中，每一个参与的进程往往既承担的服务器进程的角色（资源提供者），又承担了客户进程的角色（资源请求者）。

4. Peer-to-Peer范型典型应用

 

 

 

5. 消息系统

消息系统充当了一些相当独立的进程之间的中介。不同的进程以非耦合的方式，通过消息系统异步地交换消息。消息发送者（进程）在发送消息时，将一条消息放入消息系统中，后者接着将该消息转发到与各个接受者（进程）相应的消息接收队列中，一旦消息发送出去，发送者即可执行其他任务了

u  消息系统模型可以进一步划分为两种子类型：点对点消息模型（Point-to-point message model）和发布订阅消息模型（Public/Subscribe message model）。

u  在这种模型中，消息系统将来自发送者的一条消息转发到接收者的消息队列中。

与基本的消息传递模型不同的是，这种中间件模型提供了消息暂存的功能，从而可以将消息的发送和接受分离。

与基本的消息传递模型相比，点对点消息模型为实现异步消息操作提供了额外的一层抽象。

如果要在基本的消息传递模型中达到同样的结果，就必须借助于线程或者子进程技术。

u  在该模型中，每条消息都与某一主体或事件相关。对某个事件感兴趣的应用程序可以订阅与该事件相关的消息。

当订阅者等待的时间发生时，触发该事件的进程将发布一条消息来宣布该事件或主题。

中间件消息系统将这条消息分发给该消息的所有订阅者。

发布/订阅消息模型提供了一种用于组播或组通信的强大抽象机制。

6. 远程过程调用

如果进程A希望向另一个进程B发出请求，就可以向进程B发出一个过程调用，同时传递的还有一组参数值。与本地过程调用的情况一样，该远程过程调用也会触发进程B所提供的某一过程中预定义的动作。过程执行完毕后，进程B将返回一个值给进程A。

 

图2-7 远程过程调用

 

 

 

 

 

 

 

 

 

在分布式系统中，数据库一般驻存在服务器上，客户机（进程）通过远程数据库服务功能访问数据库服务器（如图所示），现有的远程数据库服务是使用RPC模式的，

例如Oracle数据库提供了存储过程机制，系统与用户定义的存储过程在数据库服务器上，用户在客户端使用RPC模式调用存储过程获取数据。

7. 分布式对象

远程方法调用（Remote Method Invocation，RMI）是面向对象版本的RPC。

在该范型中，进程可以调用对象方法，而该对象可驻留于某远程主机中。与RPC一样，参数可随方法调用传递，也可提供返回值

8. 对象请求代理

对象请求代理范型由对象请求者（Object Requestor）、对象提供者（Object）和对象请求代理（Object Request Broker，ORB）组成。

在对象请求代理范型中，进程向对象请求代理发出请求，对象请求代理将请求转发给能提供预期服务的适当对象。

对象请求代理范型与RMI范型非常相似。两者的主要区别在于，对象请求代理范型多了一个对象请求代理，对象请求代理充当中间件角色，作为对象请求者的应用程序可访问多个远程（或本地）对象。对象代理还可以作为异构对象之间的协调者，允许由不同API实现的对象及运行于不同平台上的对象进行交互。

 

 

9. 网络服务

网络服务范型由服务请求者、服务提供者（对象）和目录服务三者组成。

网络服务范型的工作原理为：服务提供者将自身注册到网络上的目录服务器；

当服务请求者（进程）需访问服务时，则在运行时与目录服务器联系；

然后，如果请求的服务可用，则目录服务器将向目录服务进程提供一个有关该服务的引用；

最后，进程利用该引用来与所需的服务进行交互。

 

网络服务范型本质上是对远程方法调用范型的扩展，区别在于服务对象在全局目录服务中注册，允许联邦网络中的服务请求者查询和访问这些服务。

在理想情况下，可以采用全局惟一标志符注册和访问服务，在这种情况下，范型将提供额外的一种抽象：位置透明性。

位置透明性允许软件开发者在访问对象或服务时，无需知道对象或服务所在的具体位置。

一个网络服务的应用系统实例——WebXml，提供很多实用web服务

10. 移动代理范型

·      A mobile agent is a transportable program or object. 

·      In this model, an agent is launched from an originating host.

·       The agent travels from host to host according to an itinerary(路线) that it carries. 

·      At each stop, the agent accesses the necessary resources or services, and performs the necessary tasks to accomplish its mission.

·     The paradigm offers the abstraction for a transportable program or object. 

·     In place of message exchanges, data is carried by the program/object as the program is transported among the participants.

 (代替消息交换，传递数据和程序)

·      Commercial packages which support the mobile agent paradigm include:

IBM’s Aglet system.

          http://www.trl.ibm.com/aglets/

11. 云服务范型

 

 

12. IaaS

IaaS在技术是通过创建虚拟的计算、存储中心，使得其能够把计算单元、存储器、I/O设备、带宽等计算机基础设施，集中起来成为一个虚拟的资源池来对外提供服务。

通过虚拟化技术，解决了资源灵活调度，提高资源利用率

13. PaaS

PaaS是通过互联网以服务的形式把计算环境、开发环境等平台提供给用户使用的一种范型。

 

14. SaaS

SaaS是Software as a Service的缩写，即软件即服务。  是通过互联网以服务的形式,把软件及应用程序按需提供给用户使用的一种范型。

云计算的关键技术概述 Overview Core Technologies of Cloud Computing

一.IaaS Amazon亚马逊网络书店

Amazon研发了弹性计算云EC2（Elastic Computing Cloud）和简单存储服务S3（Simple Storage Service）为企业提供计算和存储服务。

·诞生两年时间，Amazon上的注册开发人员就多达44万人，其中包括为数众多的企业级用户。

虚拟服务器：Amazon EC2

-Small (Default) $0.085 per hour(L) -$0.12 per hour(W)

-All Data Transfer $0.15 per GB

· 储存服务：Amazon S3

-$0.15 per GB –first 50 TB / month of storage used

-$0.15 per GB –all data transfer in

-$0.01 per 1,000 PUT, COPY, POST, or LIST requests

· 观念：Paying for What You Use                    每个服务器租用1小时为0.1美元

应用案例：纽约时报

·使用亚马逊云计算服务在不到24个小时的时间里处理了1100万篇文章

·累计花费240美元

·如果用自己的服务器，需要数月和多得多的费用

 

二. Google谷歌

Google搜索引擎建立在分布在30多个站点、超过200万台服务器构成的云计算设施的支撑之上，这些设施的数量正在迅猛增长。

·Google的一系列成功应用，包括Google地球、地图、Gmail、Docs等也同样使用了这些基础设施。

·目前，Google已经允许第三方在Google的云计算中通过Google App Engine运行大型并行应用程序。

·Hadoop模仿了Google的实现机制。

 

Google的Dalles（达尔斯）数据中心

位于俄勒冈州的波特兰以东约80英里，旁边是哥伦比亚河，河上有座大坝——Dalles大坝，大坝为数据中心提供便宜的电力。数据中心有2座4层楼高的冷却塔

3个超大机房，每个机房有45个集装箱，每个集装箱可以放置1160台服务器，故Dalles数据中心可以存放约15万台服务器

 

 

 

 

 Google App Engine (GAE)

·让开发者可自行建立网络应用程序于Google 平台之上。

·提供：

-500MB of storage

-up to 5 million page views a month

-10 applications per developer account

限制：

-程序设计语言只能用Python 或Java

· 计费标准：

–连出频宽$0.12 美元/GB, 连入频宽$0.10 美元/GB

–CPU 时间$0.10 美元/时

–储存的数据$0.15 美元/GB-每月

–电子邮件收件者$0.0001 美元/每个收件者

Google 在一些会议分享他们的三大关键技术

· Google shared their design of web-search engine

–SOSP 2003 :

–“The Google File System”

–http://labs.google.com/papers/gfs.html

–OSDI 2004 :

–“MapReduce : Simplifed Data Processing on Large Cluster”

–http://labs.google.com/papers/mapreduce.html

–OSDI 2006 :

–“Bigtable: A Distributed Storage System for Structured Data”

–http://labs.google.com/papers/bigtable-osdi06.pdf

  

IBM

·IBM在2007年11月推出了“改变游戏规则”的“蓝云”计算平台，为客户带来即买即用的云计算平台。

·IBM正在与17个欧洲组织合作开展名为RESERVOIR云计算项目，以“无障碍的资源和服务虚拟化”为口号。欧盟提供了1.7亿欧元作为部分资金。

·2008年8月，IBM宣布将投资约4亿美元用于其设在北卡罗来纳州和日本东京的云计算数据中心改造。IBM计划在2009年在10个国家投资3亿美元建13个云计算中心。

 

Microsoft

1.云计算

云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务。

云计算将计算变成了大众用得上和用得起的“水和电”

2.云计算的特点

超大规模

虚拟化

高可靠性

通用性

高可扩展性

按需服务

极其廉价

3. National Definition of Cloud Computing

美国国家标准局NIST给云端运算所下的定义

 

5 Characteristics五大基础特征

1. On-demand self-service   .随需自助服务

2. Broad network access      随时随地用任何网络装置存取

3. Resource pooling         多人共享资源池

4. Rapid elasticity           快速重新布署灵活度

  5. Measured Service         可被监控与量测的服务

4 Deployment Models 四个布署模型

①混合云  Hybrid Cloud

私有云动态根据计算需求调用公云端的资源    Dynamic Resource Provisioning between public and private cloud

 

②私有云     Private Cloud

以大型企业为主要客户             Enterprise is key market

③  公用云   Public Cloud

主要客户为中小企业 Target Market is S.M.B.

④ 社群云     Community Cloud

学术为主                 Academia

3 Service Models 三个服务模式

①IaaS  Infrastructure as a Service 架构即服务

②PaaS  Platform as a Service    平台即服务

③SaaS  Software as a Service  软件即服务

 

 

深入解析虚拟化技术   

Deep Dive into Virtualization Technologies

 

 

 

虚拟化：去耦合

虚拟化是将底层物理设备与上层操作系统、软件分离的一种去耦合技术

虚拟化的目标是实现IT资源利用效率和灵活性的最大化

 

Part 3 :深入解析云大量资料分析技术

Deep Dive into Data Science Technologies

并行计算的基础

1.摩尔定律

–集成电路芯片上所集成的电路的数目，每隔18个月就翻一番，同时性能也提升一倍

–经验总结，12个月-18个月-24个月

Gordon Moore

 

2. “免费的性能大餐”？

–Andy giveth, and Bill taketh away

–软件算法、数据结构似乎不再重要，因为处理器性能不断提升

免费的午餐已经结束！！

Intel   Microsoft

 

3. 摩尔定律正在走向终结…

–单芯片容纳晶体管的增加，对制造工艺提出要求

–CPU制造18nm技术，电子泄漏问题

–CPU主频已达3GHz时代，难以继续提高

·散热问题（发热太大，且难以驱散）

·功耗太高

未来的发展：多核

4. 在多核时代生存，必须考虑并发问题

·不存在解决多核编程问题的银弹，不存在可以简单地将并发编程问题化解掉的工具，开发高性能的并行程序必须要求开发者从根本上改变其编程方法

·从某种意义上来说，这不仅仅是要改变50年来顺序程序设计的工艺传统，而且是要改变数百万年来人类顺序化思考问题的习惯

串行编程

–早期的计算里，程序一般是被串行执行的

–程序是指令的序列，在单处理器的机器里，程序从开始到结束，这些指令一条接一条的执行

·并行编程

–一道处理可以被划分为几部分,然后它们可以并发地执行

–各部分的指令分别在不同的CPU上同时运行，这些CPU可以存在于单台机器中,也可以存在于多台机器上,它们通过连接起来共同运作

 

5. 什么样的问题适合并行计算？

–如果有大量结构一致的数据要处理，且数据可以分解成相同大小的部分，那我们就可以设法使这道处理变成并行

 

为什么需要MapReduce

1.Google拥有海量数据，并且需要快速处理

对爬虫获取的网页进行倒排索引

计算网站的PageRank

分析搜索趋势(Google Trends)

计算网页的访问量

找出一个词语在Google搜索目录中出现的次数；一系列网页中特定词语出现的频率；链接到某个特定网站的所有网站数量

 

2. 计算问题简单，但求解困难

–待处理数据量巨大（PB级），只有分布在成百上千个节点上并行计算才能在可接受的时间内完成

–如何进行并行分布式计算？

–如何分发待处理数据？

–如何处理分布式计算中的错误？

简单的问题，计算并不简单！

3.Google MapReduce架构设计师

Jeffery Dean设计一个新的抽象模型，使我们只要执行的简单计算，而将并行化、容错、数据分布、负载均衡的等杂乱细节放在一个库里，使并行编程时不必关心它们,这就是MapReduce

4. 一个软件架构，是一种处理海量数据的并行编程模式

·用于大规模数据集（通常大于1TB）的并行运算

·MapReduce实现了Map和Reduce两个功能

–Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集

–Reduce对结果集进行分类和归纳

–Map()和Reduce() 两个函数可能会并行运行，即使不是在同一的系统的同一时刻

 

      

 

MapReduce

一个软件架构，是一种处理海量数据的并行编程模式

·用于大规模数据集（通常大于1TB）的并行运算

·MapReduce实现了Map和Reduce两个功能

–Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集

–Reduce对结果集进行分类和归纳

–Map()和Reduce() 两个函数可能会并行运行，即使不是在同一的系统的同一时刻

 

2004年MapReduce运行了2.9万个工作任务，2007年已有220万个工作由MapReduce来完成用于大规模数据集（通常大于1TB）的并行运算

·MapReduce对于一个工作的平均运行响应时间从634秒下降到了395秒，MapReduce任务的数据产出量从193 上升到了14018 terabytes

·在任何一天，Google运行有大约10万个MapReduce工作任务；每项任务大约会占用4百台服务器，时间大约是5到10分钟

·假设服务器只完成MapReduce工作，每台服务器一次只完成一项任务，那么大约要耗时24小时，

如果这些工作任务每个耗时5分钟，这意味着MapReduce任务要占用大约13.9万台服务器。

如果耗时7.5分钟，那么需要的服务器数量增加到20.8万台；如果需要10分钟，服务器的数量增加至27.8万台

 

文件存储位置

源文件：GFS

Map处理结果：本地存储

Reduce处理结果：GFS

日志：GFS

 

Google MapReduce计算架构有什么问题？

MapReduce的容错

Worker故障

–Master 周期性的ping每个worker。如果master在一个确定的时间段内没有收到worker返回的信息，那么它将把这个worker标记成失效

–重新执行该节点上已经执行或尚未执行的Map任务

–重新执行该节点上未完成的Reduce任务，已完成的不再执行

·Master故障

–定期写入检查点数据

–从检查点恢复

实践是检验真理的唯一标准

实践证明，MapReduce是出色的分布式计算模型

–Google宣布，其对分布于1000台计算机上的1TB数据进行排序仅仅需要68s

–对4000台计算机上的1PB数据进行排序处理仅需要6小时2分钟（每次测试至少会损坏1块硬盘）

–在08年1月份，Google MapReduce平均每天的数据处理量是20PB，相当于美国国会图书馆当年5月份存档网络数据的240

Building PaaS with Open Source

用自由软件打造PaaS云端服务

1.应用软件Application

Social Computing, Enterprise, ISV,…                   eyeOS, Nutch, ICAS, X-RIME, ...

2. 程序语言Programming

Web 2.0界面, Mashups, Workflows, …           Hadoop (MapReduce),Sector/Sphere, AppScale

3. 控制管理Control

Qos Neqotiation, Ddmission Control,

Pricing, SLA Management, Metering…                       OpenNebula, Enomaly,Eucalyptus , OpenQRM, ...

4. 虚拟化Virtualization

VM, VM management and Deployment                             Xen, KVM, VirtualBox,QEMU, OpenVZ, ...

5. 硬件设施Hardware

Infrastructure: Computer, Storage, Network

Hadoop

http://hadoop.

Hadoop 是Apache Top Level 开发项目

Hadoop is Apache Top Level Project

目前主要由Yahoo! 资助、开发与运用

Major sponsor is Yahoo!

创始者是Doug Cutting ，参考Google Filesystem

Developed by Doug Cutting, Reference from Google Filesystem

以Java 开发，提供HDFS 与MapReduce API 。

Written by Java, it provides HDFS and MapReduce API

2006 年使用在Yahoo 内部服务中

Used in Yahoo since year 2006

已布署于上千个节点。

It had been deploy to 4000+ nodes in Yahoo

处理Petabyte 等级资料量。

Design to process dataset inPetabyte

 

Facebook、Last.fm、Joost are also powered by Hadoop

What is Hadoop? 用一句话解释Hadoop是什么??

Hadoop is a software platform that lets one easily write and run applications that process vast amounts of data.

Hadoop是一个让使用者简易撰写并执行处理海量数据应用程序的软件平台。

也可以想象成一个处理海量数据的生产线，只须学会定义Map跟Reduce工作站该做哪些事情。

Two Key Elements of Operating System

操作系统两大关键组成元素

Scheduler程序调度   

File System文件系统

 

Distributed Operating System of Hadoop

Hadoop建构成一个分布式操作系统

 

Different Roles of Hadoop Architecture

Hadoop软件架构中的不同角色

 

 

 

 

 

 

 

 

 

Two Key Roles of HDFS    HDFS软件架构的两种关键角色

名称节点NameNode

·Master

·管理HDFS的名称空间

·控制对文件的读/写

·配置副本策略

·对名称空间作检查及纪录

·只能有一个

数据节点DataNode

·Workers

·执行读/写动作

·执行Namenode的

副本策略

·可多个

Two Key Roles of Job Scheduler

程序调度的两种关键角色

MapReduce is suitable to ....

MapReduce合适用于....

大规模数据集

·Large Data Set

· 可拆解，并行化

·Parallelization

Text tokenization

Indexing and Search

Data mining

machine learning