1、云和网络平台的特性

1、1云的功能和平台的特性

1、2 网格和云的公共传统特性

1、2、1 工作流

在真实的应用中工作流按需连接多个云和非云服务。

1、2、2 数据传输

在商业云中（较少程度上，在商业云之外）数据传输的成本（时间和金钱）经常被认为是使用云的一个难点。如果商业云成为一个国家计算机基础设施的重要部分，预期在云和TeraGrid之间将出现一条高带宽链路。

1、2、3 安全、隐私和可用性

使用虚拟集群化来实现用最小的开销成本达到动态资源供应。
使用稳定和持续的数据存储，带有用于信息检索的快速查询。
使用特殊的API来验证用户及使用商业账户发送电子邮件。
使用像HTTPS或者SSL等安全协议来访问云资源。
需要细粒度访问控制来保护数据完整性，阻止侵入者或黑客。
保护共享的数据集，以防恶意篡改、删除或者版权侵犯。

包括增强的可用性和带有虚拟机实时迁移的灾难恢复等特性。

使用信用系统来保护数据中心。这个系统只授权给可信用户，并阻止侵入者。

1、3 数据特性和数据库

1、3、1 程序库

允许方便地部署和配置镜像（即它们支持IaaS）。

1、3、2 blob和驱动

除了blob和S3的服务接口，人们还可以“直接”附加到计算实例中作为Azure驱动和亚马逊的弹性块存储。这个概念类似于共享文件系统。

1、3、3 DPFS

DPFS文件系统是为执行数据密集型应用而精确设计的。

1、3、4 SQL和关系型数据库

亚马逊和Azure云都提供关系型数据库，这可以直接为学术系统提供一个类似的功能，但如果是需要大规模数据，事实上，基于表或MapReduce的方法可能会更合适 。

1、3、5 表格和NOSQL

在简化数据库结构（NOSQL）上已经有了很多重要的进展，典型情况强调了分布式和可扩展性。这些进展体现在三种主要云里：谷歌的BigTable、亚马逊的SimpleDB和Azure的Azure Table 

1、3、6 队列服务

亚马逊和Azure都能提供类似的可扩展、健壮的队列服务，用来在一个应用的组件之间通信。 

1、4 编程和运行时的支持

需要编程和运行时支持来促进并行编程，并为今天的网格和云上的重要功能提供运行时支持。

1、4、1 工作机和WEB角色

Azure引入的角色提供了重要功能，并有可能在非虚拟化环境中保留更好的密切度支持。工作机角色是基本的可调度过程，并能自动启动。注意在云上没有必要进行明显的调度，无论是对个人工作机角色还是MapReduce透明支持的“群组调度”。在这里，队列是一个关键概念。

1、4、2 MapReduce

“数据并行”语言日益受到广泛关注，这种语言主要的目的在于在不同数据样本上执行松耦合的计算。

它支持动态执行、强容错性以及一个容易使用的高层接口。

1、4、3 云编程模型

前面的大多数内容都是描述编程模型特性，但是还有很多“宏观的”架构，并不能作为代码（语言和库）。GAE和Manjrasoft Aneka环境都代表编程模型；都适用于云，但实际上并不是针对这个体系结构的。迭代MapReduce是一个有用的编程模型，它提供了在云、HPC和集群环境之间的可移植性。

1、4、4 软件即服务

服务在商业云和大部分现代分布式系统中以类似的方式使用。我们希望用户能尽可能地封装他们的程序，这样不需要特殊的支持来实现软件即服务。 

2、 并行和分布式编程范式

我们把并行和分布式程序定义为运行在多个计算引擎或一个分布式计算系统上的并行程序。这个术语包含计算机科学中的两个基本概念：分布式计算系统和并行计算。

分布式计算系统：是一系列由网络连接的计算引擎，它们完成一个共同目标：运行一个作业或者一个应用。计算机集群或工作站网络就是分布式计算系统的一个实例。

并行计算：是同时运用多个计算引擎（并不一定需要网络连接）来运行一个作业或者一个应用。

2、1 并行计算和编程范式

由多个网络节点或者工作机组成用并行或分布式方式来运行并行程序，该系统包括以下方面 :

1.分区：分区适用于计算和数据两方面：
 计算分区：计算分区是把一个给定的任务或者程序分割成多个小任务。分区过程很大程度上依靠正确识别可以并发执行的作业或程序的每一小部分。

 数据分区：数据分区是把输入或中间数据分割成更小的部分。类似地，一旦识别出输入数据的并行性，它也可以被分割成多个部分，能在不同的工作机上运行。数据块可由程序的不同部分或者同一程序的副本来处理。

2.映射：映射是把更小的程序部分或者更小的数据分块分配给底层的资源。这个过程的目的在于合理分配这些部分或者分块，使它们能够同时在不同的工作机上运行。映射通常由系统中的资源分配器来处理。

3.同步：因为不同工作机可以执行不同的任务，工作机之间的同步和协调就很有必要。这样可以避免竞争条件，不同工作机之间的数据依赖也能被恰当地管理。不同工作机多路访问共享资源可能引起竞争条件。然而，当一个工作机需要其他工作机处理的数据时会产生数据依赖。

4.通信：因为数据依赖是工作机之间通信的一个主要原因，当中间数据准备好在工作机之间传送时，通信通常就开始了。

5.调度：对于一项作业或一个程序，当计算部分（任务）或数据块的数量多于可用的工作机数量时，调度程序就会选择一个任务或数据块的序列来分配给工作机。值得注意的是，资源分配器完成计算或数据块到工作机的实际映射，而调度器只是基于一套称为调度策略的规则，来从没有分配的任务队列中选择下一个任务。对于多作业或多程序，调度器会选择运行在分布式计算系统上的一个任务或程序的序列。

上述这种方式的缺点:耗时、效率低、可能影响产品上线。

所以引入编程范式，编程范式的动机：

1、提供并行和分布式编程范式或模型来抽象用户数据流的多个部分。
2、编写并行程序的简单性是度量并行和分布式编程范式的重要标准。并行和分布式编程模型背后的其他动机还有：（1）提高程序员的生产效率，（2）减少程序进入市场的时间，（3）更有效地利用底层资源，（4）提高系统的吞吐量，（5）支持更高层的抽象。
3、MapReduce、Hadoop和Dryad是最近提出的三种并行和分布式编程模型。这些模型是为信息检索应用而开发的，不过已经显示出它们也适用于各种重要应用 。

2、2 MapReduce、Twister、和迭代MapReduce

2、2、1 MapReduce的形式化定义

MapReduce是一个软件框架，可以支持大规模数据集上的并行和分布式计算。

提供给用户两个接口：Map(映射)和Reduce（化简）。用户可以重载这两个函数以实现交互和操纵运行其程序的数据流。

MapReduce软件框架向用户提供了一个具有数据流和控制流的抽象层，并隐藏了所有数据流实现的步骤，比如，数据分块、映射、同步、通信和调度。这里，虽然在这样的框架中数据流已被预定义，但抽象层还提供两个定义完善的接口，这两个接口的形式就是Map和Reduce这两个函数。这两个主函数能由用户重载以达到特定目标。

2、2、2 MapReduce的逻辑数据流

Map和Reduce函数的输入数据有特殊的结构。输出数据也一样。

Map函数的输入数据是以（key, value）对的形式出现。

首先是对中间(key, value)对排序，然后以相同的key来把value分组。

Reduce函数处理每个(key, [set of values])群组，并产生(key, value)对集合作为输出。

单词计数问题： 

单词计数问题的数据流，以级联操作方式使用MapReduce函数（Map，Sort，Group和Reduce）

2、2、3 MapReduce数据流的形式化符号

2、2、4 解决MapReduce问题的策略

  将所有中间数据分组之后，出现相同key的value会排序并组合在一起。结果是，分组之后所有中间数据中每一个key都是唯一的。

问题1：计算一批文档中每个单词的出现次数。
解：唯一“key”——每个单词；中间“value”——出现次数。

问题2：计算一批文档中相同大小、相同字母数量的单词的出现次数。
解：唯一“key”——每个单词；中间“value”——单词大小。

问题3：计算一批文档中变位词（anagram）出现的次数。变位词是指字母相同但是顺序不同的单词（例如，单词“listen”和“silent”）。
解：唯一“key”——每个单词中按照字母顺序排列的字母（如“eilnst”）；中间“value”——出现次数。

2、2、5 MapReduce真实数据和控制流

1.数据分区：MapReduce库将已存入GFS的输入数据（文件）分割成M部分，M也即映射任务的数量。

2.计算分区：计算分块通过强迫用户以Map和Reduce函数的形式编写程序，（在MapReduce框架中）被隐式地处理。所以，MapReduce库只生成用户程序的多个复制（例如，通过fork系统调用），它们包含了Map和Reduce函数，然后在多个可用的计算引擎上分配并启动它们。

3.决定主服务器（master）和服务器（worker）：MapReduce体系结构是基于主服务器-服务器模式的。所以一个用户程序的复制变成了主服务器，其他则是服务器。主服务器挑选空闲的服务器，并分配Map和Reduce任务给它们。典型地，一个映射/化简服务器是一个计算引擎，例如集群节点，通过执行Map/Reduce函数来运行映射/化简任务。步骤4～7描述了映射服务器。

4.读取输入数据（数据分发）：每一个映射服务器读取其输入数据的相应部分，即输入数据分割，然后输入至其Map函数。虽然一个映射服务器可能运行多个Map函数，这意味着它分到了不止一个输入数据分割；通常每个服务器只分到一个输入分割。

5.Map函数：每个Map函数以（key，value）对集合的形式收到输入数据分割，来处理并产生中间（key, value）对。

6.Combiner函数：Combiner函数是映射服务器中一个可选的本地函数，适用于中间(key, value)对。用户可以在用户程序里调用Combiner函数。用户可以在用户程序里调用Combiner函数。Combiner函数运行用户为Reduce函数所写的相同代码，因为它们的功能是一样的。Combiner函数合并每个映射服务器的本地数据，然后送到网络传输，以有效减少通信成本。正如我们在逻辑数据流的讨论中提到的，MapReduce框架对数据进行排序并分组，然后数据被Reduce函数处理。类似地，如果用户调用Combiner函数，MapReduce框架也会对每个映射服务器的本地数据排序并分组。

7.Partitioning函数：正如在MapReduce数据流中提到的，具有相同键值的中间(key, value)对被分组到一起，因为每个组里的所有值都应只由一个Reduce函数来处理产生最终结果。

正如在MapReduce数据流中提到的，具有相同键值的中间(key, value)对被分组到一起，因为每个组里的所有值都应只由一个Reduce函数来处理产生最终结果。然而在实际实现中，由于有M个map和R个化简任务，有相同key的中间(key, value)对可由不同的映射任务产生，尽管它们只应由一个Reduce函数来一起分组并处理。

由每一个映射服务器产生的中间(key, value)对被分成R个区域，这和化简任务的数量相同。分块是由Partitioning（分区）函数完成，并能保证有相同键值的所有(key, value)对都能存储在同一区域内。因此，由于化简服务器i读取所有映射服务器区域i中的数据，有相同key的所有(key, value)对将由相应的化简服务器i收集。

8.同步：MapReduce使用简单的同步策略来协调映射服务器和化简服务器，当所有映射任务完成时，它们之间的通信就开始了。

9.通信：Reduce服务器i已经知道所有映射服务器的区域i的位置，使用远程过程调用来从所有映射服务器的各个区域中读取数据。由于所有化简服务器从所有映射服务器中读取数据，映射和化简服务器之间的多对多通信在网络中进行，会引发网络拥塞。这个问题是提高此类系统性能的一个主要瓶颈。

10.排序和分组：当化简服务器完成读取输入数据的过程时，数据首先在化简服务器的本地磁盘中缓冲。然后化简服务器根据key将数据排序来对中间(key, value)对进行分组，之后对出现的所有相同key进行分组。注意，缓冲数据已经排序并分组，因为一个映射服务器产生的唯一key的数量可能会多于R个区域，所以在每个映射服务器区域中可能有不止一个key。

11.Reduce函数：化简服务器在已分组的(key, value)对上进行迭代。对于每一个唯一的key，它把key和对应的value发送给Reduce函数。然后，这个函数处理输入数据，并将最后输出结果存入用户程序已经指定的文件中。

2、2、6 计算-数据密切度

MapReduce软件框架最早是由谷歌提出并实现的。首次实现是用C语言编码的。该实现是将谷歌文件系统 (GFS)的优势作为最底层。MapReduce可以完全适用于GFS。GFS是一个分布式文件系统，其中文件被分成固定大小的块，这些块被分发并存储在集群节点上。
如前所述，MapReduce库将输入数据（文件）分割成固定大小的块，理想状态下是在每个块上并行地执行Map函数。在这种情况下，由于GFS已经将文件保存成多个块，MapReduce框架只需要将包含Map函数的用户程序复制发给已经存有数据块的节点。这就是将计算发向数据，而不是将数据发给计算。注意，GFS块默认为64MB，这和MapReduce框架是相同的。

2、2、7 Twister和迭代MapReduce

并行开销的两个主要来源是负载不均衡和通信
在所有“经典并行的”松散同步应用中可以看到同样的现象，典型地需要在计算阶段加入一个迭代结构，然后是通信阶段。可以通过两个重要的改变来解决性能问题：
    1.在各个步骤之间的流信息，不把中间结果写入磁盘。
    2.使用长期运行的线程或进程与δ（在迭代之间）流进行通信。

这些改变将会导致重大的性能提升，代价是较差的容错能力，同时更容易支持动态改变，如可用节点的数量。这个概念已经在多个项目中应用。

图6-7 Twister：一个迭代的MapReduce编程范式，用于重复的MapReduce运行 

2、3 来自Apache的Hadoop软件库

Hadoop内核分为两个基本层：MapReduce 引擎和HDFS。MapReduce 引擎是运行在HDFS之上的计算引擎，使用HDFS作为它的数据存储管理器。

HDFS: HDFS是一个源于GFS的分布式文件系统，是在一个分布式计算系统上管理文件和存储数据。

HDFS体系结构：HDFS有一个主从体系结构，包括一个单个NameNode作为master以及多个DataNodes作为工作机(slave)。为了在这个体系结构中存储文件，HDFS将文件分割成固定大小的块（例如64MB），并将这些块存到工作机(DataNodes)中。从块到DataNodes的映射是由NameNode决定的。NameNode (master)也管理文件系统的元数据和命名空间。在这个系统中，命名空间是维护元数据的区域，而元数据是指一个文件系统存储的所有信息，它们是所有文件的全面管理所需要的。例如，元数据中的NameNode存储了所有DataNodes上关于输入块位置的所有信息。每个DataNode，通常是集群中每个节点一个，管理这个节点上的存储。每个DataNode负责它的文件块的存储和检索 。

HDFS特性：分布式文件系统为了能高效地运作，会有一些特殊的需求，比如性能、可扩展性、并发控制、容错能力和安全需求[62]。然而，因为HDFS不是一个通用的文件系统，即它仅执行特殊种类的应用，所以它不需要一个通用分布式文件系统的所有需求。例如，HDFS系统从不支持安全性。下面的讨论着重突出HDFS区别于其他一般分布式文件系统的两个重要特征。

HDFS容错能力：HDFS的一个主要方面就是容错特征。由于Hadoop设计时默认部署在廉价的硬件上，系统硬件故障是很常见的。所以，Hadoop考虑以下几个问题来达到文件系统的可靠性要求：

块复制：为了能在HDFS上可靠地存储数据，在这个系统中文件块被复制了。换句话说，HDFS把文件存储为一个块集，每个块都有备份并在整个集群上分发。

备份布置：备份的布置是HDFS实现所需要的容错功能的另一个因素。虽然在整个集群的不同机架的不同节点上(DataNodes)，存储备份提供了更大的可靠性，但这有时会被忽略，因为不同机架上两个节点之间的通信成本要比同一个机架上两个不同节点之间的通信相对要高。

Heartbeat和Blockreport消息：Heartbeats和Blockreports是在一个集群中由每个DataNode传给NameNode的周期性消息。收到Heartbeat 意味着DataNode正运行正常，而每个Blockreport包括了DataNode上所有块的一个清单。

HDFS高吞吐量访问大规模数据集（文件）：因为HDFS主要是为批处理设计的，而不是交互式处理，所以HDFS数据访问吞吐量比延时来的更为重要。

HDFS操作：HDFS操作（比如读和写）的控制流能正确突出在管理操作中NameNode和DataNodes的角色。

读取文件：为了在HDFS中读取文件，用户先发送一个“open”请求给NameNode以获取文件块的位置信息。

写入文件：为了在HDFS中写入文件，用户发送一个“create”请求给NameNode，来在文件系统命名空间里创建一个新的文件。

考点：

过程详见：点击打开链接

2、3、1 Hadoop上的MapReduce体系结构

Hadoop的顶层是MapReduce引擎，管理着分布式计算系统上MapReduce作业的数据流和控制流。

类似于HDFS，

MapReduce引擎也有一个主/从（master/slave）体系结构，由一个单独的JobTracker作为主服务器并由许多的TaskTracker作为服务器(slaves)。

JobTracker职责：在一个集群上管理MapReduce作业，并负责监视作业和分配任务给TaskTracker。

TaskTracker职责：管理着集群上单个计算节点的映射和化简任务的执行。

每个TaskTracker节点都有许多同时运行槽，每个运行是映射任务或者化简任务。插槽是由TaskTracker 节点的CPU支持同时运行的线程数量来确定的。

比如，一个带有N个CPU的TaskTracker节点，每个都支持M个线程，共有M×N个同时运行的槽。需要注意的是，每个数据块都是由运行在单独的一个槽上的映射任务处理的。

所以， 在TaskTracker 上的映射任务和在各个DataNode上的数据块之间存在一一对应关系。

2、3、2 在Hadoop里运行一个作业

 在这个系统中有三个部分共同完成一个作业的运行：用户节点、JobTracker和数个TaskTracker。

数据流最初是在运行于用户节点上的用户程序中调用runJob(conf)函数，其中conf是MapReduce 框架和HDFS中一个对象，它包含了一些调节参数。runJob(conf)函数和conf如同谷歌MapReduce第一次实现中的MapReduce(Spec, &Results) 函数和Spec。

图6-12  在不同的TaskTracker上使用Hadoop库运行一个MapReduce作业的数据流

作业提交：每个作业都是由用户节点通过以下步骤提交给JobTracker节点，此节点可能会位于集群内一个不同的节点上：
一个用户节点从JobTracker请求一个新的作业ID，并计算输入文件分块。
用户节点复制一些资源，比如用户的JAR文件、配置文件和计算输入分块，至JobTracker文件系统。

用户节点通过调用submitJob()函数提交任务至JobTracker。

任务分配：JobTracker为用户节点的每个计算输入块建立一个映射任务，并分配给TaskTracker的执行槽。当分配映射任务给TaskTracker时，JobTracker会考虑数据的定位。JobTracker也会创建化简任务，并分配给TaskTracker。

任务执行：把作业JAR（就是我们写的java应用程序export后得到的）文件复制到其文件系统之后，在TaskTracker执行一个任务（不管映射还是化简）的控制流就开始了。在启动Java虚拟机（Java Virtual Machine，JVM）来运行它的映射或化简任务后，就开始执行作业JAR文件里的指令。

任务运行校验：通过接收从TaskTracker到JobTracker的周期性心跳监听消息来完成任务运行校验。每个心跳监听会告知JobTracker传送中的TaskTracker是可用的，以及传送中的TaskTracker是否准备好运行一个新的任务。 

3、物联网的关键技术

3、1 实现普适计算的物联网

3、1、1 普适计算

普适计算是人机交互的后桌面模式，信息的处理融入到日常物体和活动中。

在日常生活中，人们会同时使用多个普适设备，但并不一定知道这些交互设备的存在。

这种思想虽然简单，但实现很难。如果世界上所有物体都装备有很小的识别系统，那么我们的日常生活将会发生一次重大变革。

 物联网系统必须有系统设计、系统工程和用户接口。

命令行、菜单驱动或者基于GUI的现代人机交互模式都无法满足普适计算的需求。适用于普适计算的物联网模式已经显现，能够支持普适计算的设备有智能手机、平板电脑、传感器网络、RFID标识、智能卡、GPS设备等。

3、1、2 物联网的发展

3、1、3 关键技术和增效技术

3、1、4 物联网的体系结构

3、2 射频标识（RFID）

RFID对带有电子标签或者RFID标签的物体进行监测和跟踪。

标签可以应用在任意物体上，如商品、工具、智能电话、计算机、动物或者人，目的是通过射频波或者感知信号识别和跟踪物体。

某些标签可以从数十或者数百米以外被无线读取器所读取。

RFID标识至少包含两个主要部分：

一部分是集成电路，用来存储和处理信息，调制和解调射频信号等；

另一部分是接受和传输无线信号的天线。

3、2、1 RFID标签和设备组件

三类：

RFID主动标签：带电池供电，自动输出信号。

RFID被动标签：不带电池，外部源激发信号传输。

电子辅助的被动RFID标签：外部源唤醒电池，但有更高的传输能力。

RFID标签：附有天线的微型芯片。

读取天线：发信号，接受标签返回信号。

读取器：和标签交互的设备，可能支持一个或则多个天线。

3、2、2 RFID如何工作的

3、3 传感器网络和ZigBee技术

3、3、1 无线传感器网络

目前传感器网络大部分是无线的，也称为无线传感器网络（Wireless Sensor Network，WSN）。

3、3、2 支持普适计算的无限网络

3、3、3 传感器网络的发展

3、3、4 ZigBee网络

三类：

ZigBee协调器

ZigBee路由器

ZigBee终端设备

ZigBee网络是一种高级通信协议，由IEEE 802.15.4标准描述。Zigbee设备体积较小，是低能耗和基于无线电的传感器节点。

3、3、5 无线传感器网络用电管理

3、4 全球定位系统

3、4、1 GPS工作原理

三个部分组成：空间部分、控制部分、用户部分

3、4、2 主动和被动的GPS比较

3、4、3 GPS操作原理

3、4、4 三角定位计算法

3、4、5 全球部署状况