云计算之分布式计算.ppt

《云计算之分布式计算.ppt》由会员分享，可在线阅读，更多相关《云计算之分布式计算.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三五成群，聚在大树，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩

2、子们却在周下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到围跑跑跳跳，热得满头大汗，不时听到“强子，别跑了，快来我给你扇扇强子，别跑了，快来我给你扇扇”。孩。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，母亲总是，好似生气的样子，边扇边训，“你看热的，跑什么？你看热的，跑什么？”此时这把蒲扇，此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在是那么凉快，那么的温馨幸福，有母亲的味

3、道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人

4、生的轨迹，携带着特有的念想，一年年，一天天，流向长也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅长的时间隧道，袅云计算之分布式计算Outline2.1 分布式计算概述2.2 分布式计算的理论基础2.3 分布式系统概述2.4 分布式系统的进阶2.5 典型的分布式系统Data ScienceStatisticsMachine LearningDomain expertiseMathematicsData engineering分布式计算比起其他算法具有以下几个优点。稀有资源可以共享；通过分布式计算可以在多台计算机上平衡计算负载；可以把程序放在最适合运行它的计

5、算机上。2.1.2 分布式计算的原理分布式计算就是将计算任务分摊到大量的计算节点上，一起完成海量的计算任务。而分布式计算的原理和并行计算类似，就是将一个复杂庞大的计算任务适当划分为一个个小任务，任务并行执行，只不过分布式计算会将这些任务分配到不同的计算节点上，每个计算节点只需要完成自己的计算任务即可，可以有效分担海量的计算任务。而每个计算节点也可以并行处理自身的任务，更加充分利用机器的CPU资源。最后再将每个节点的计算结果汇总，得到最后的计算结果。分布式计算一般分为以下几步：1 1设计分布式分布式计算模型算模型首先要规定分布式系统的计算模型。计算模型决定了系统中各个组件应该如何运行，组件之间应

6、该如何进行消息通信，组件和节点应该如何管理等。2 2分布式任分布式任务分配分配分布式算法不同于普通算法。普通算法通常是按部就班，一步接一步完成任务。而分布式计算中计算任务是分摊到各个节点上的。该算法着重解决的是能否分配任务，或如何分配任务的问题。3 3编写并写并执行分布式程序行分布式程序使用特定的分布式计算框架与计算模型，将分布式算法转化为实现，并尽量保证整个集群的高效运行，难点：（1）计算任务的划分（2）多节点之间的通信方式2.2 分布式计算的理论基础2.2.1 ACID 原则2.2.2 CAP理论2.2.3 BASE理论2.2.4 最终一致性2.2.5 一致性散列2.2.1 ACID原则A

7、CID是数据库事务正常执行的四个原则，分别指原子性、一致性、独立性及持久性。2.2.1 ACID原则1 1A A（AtomicityAtomicity）原子性原子性原子性很容易理解，也就是说事务里的所有操作要么全部做完，要么都不做，事务成功的条件是事务里的所有操作都成功，只要有一个操作失败，整个事务就失败，需要回滚。例如银行转账，从A账户转100元至B账户，分为两个步骤：从A账户取100元；存入100元至B账户。这两步要么一起完成，要么一起不完成，如果只完成第一步，第二步失败，钱会莫名其妙少了100元。2.2.1 ACID原则2 2C C（ConsistencyConsistency）一致性一

8、致性一致性也比较容易理解，也就是说数据库要一直处于一致的状态，事务的运行不会改变数据库原本的一致性约束。例如现有完整性约束a+b=10，如果一个事务改变了a，那么必须得改变b，使得事务结束后依然满足a+b=10，否则事务失败。2.2.1 ACID原则3 3I I（IsolationIsolation）独立性独立性所谓的独立性是指并发的事务之间不会互相影响，如果一个事务要访问的数据正在被另外一个事务修改，只要另外一个事务未提交，它所访问的数据就不受未提交事务的影响。例如交易是从A账户转100元至B账户，在这个交易还未完成的情况下，如果此时B查询自己的账户，是看不到新增加的100元的。2.2.1

9、ACID原则4 4D D（DurabilityDurability）持久性持久性持久性是指一旦事务提交后，它所做的修改将会永久保存在数据库上，即使出现宕机也不会丢失。这些原则解决了数据的一致性、系统的可靠性等关键问题，为关系数据库技术的成熟以及在不同领域的大规模应用创造了必要的条件。2.2.2 CAP理论1 1CAPCAP理理论定定义2000年7月，加州大学伯克利分校的埃里克布鲁尔（Eric Brewer）教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的塞思吉尔伯符（Seth Gilbert）和南希林奇（Nancy Lynch）从理论上证明了CAP。之后，CAP理论正式成为分

10、布式计算领域的公认定理。一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项，如图2.1所示。一致性一致性指“All nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。对于一致性，可以分为从客户端和服务端两个不同的视角来看。从客户端来看，一致性主要指多并发访问时更新过的数据如何获取的问题。从服务端来看，则是如何将更新复制分布到整个系统，以保证数据的最终一致性问题。可用性l可用性是指

11、“Reads and writes always succeed”，即服务一直可用，而且是在正常的响应时间内。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是该系统使用的任何算法必须最终终止。l当同时要求分区容错性时，这是一个很强的定义：即使是严重的网络错误，每个请求也必须终止。好的可用性主要是指系统能够很好地为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。通常情况下可用性和分布式数据冗余、负载均衡等有着很大的关联。分区容错性 分区容错性指“The system continues to operate despite arbitrary mess

12、age loss or failure of part of the system”，也就是指分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求应用虽然是一个分布式系统，但看上去却好像是一个可以运转正常的整体。例如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，或者是机器之间有网络异常，将分布式系统分隔为独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。2CAP理论的阐述与证明图2.2

13、CAP的基本场景 图2.3 分布式系统正常运转的流程图2.4 断开N1和N2之间的网络3CAP权衡通过CAP理论，知道无法同时满足一致性、可用性和分区容错性这三个特性，那应该如何取舍呢？（1）CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。（2）CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。（3）AP without C：

14、要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。2.2.3 BASE理论丹普里切特（Dan Pritchett）在对大规模分布式系统的实践总结过程中，提出了BASE理论，BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consistency）。BASE是指基本可用（Basically Available）、软状态（Sof

15、t State）、最终一致性（Eventual Consistency）。1基本可用基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。2软状态软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。例如MySQL replication的异步复制就是这种体现。3最终一致性最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性

16、和强一致性相反，最终一致性是弱一致性的一种特殊情况。BASE和ACID的区别与联系是什么呢？ACID是传统数据库常用的设计理念，追求强一致性模型。BASE支持的是大型分布式系统，提出通过牺牲强一致性获得高可用性。ACID和BASE代表了两种截然相反的设计哲学。在分布式系统设计的场景中，系统组件对一致性要求是不同的，因此ACID和BASE又会结合使用。2.2.4 最终一致性下面以上面的场景来描述下不同程度的一致性。强一致性（即一致性（即时一致性）一致性）：假如A先写入了一个值到存储系统，存储系统保证后续A、B、C的读取操作都将返回最新值。弱一致性弱一致性：假如A先写入了一个值到存储系统，存储系统

17、不能保证后续A、B、C的读取操作能读取到最新值。此种情况下有一个“时间窗口”的概念，它特指从A写入值，到后续操作A、B、C读取到最新值这一段时间。“时间窗口”类似时空穿梭门，不过穿梭门是可以穿越到过去的，而一致性窗口只能穿越到未来，方法很简单，就是“等会儿”。最最终一致性一致性：是弱一致性的一种特例。假如A首先“写”了一个值到存储系统，存储系统保证如果在A、B、C后续读取之前没有其他写操作更新同样的值的话，最终所有的读取操作都会读取到A写入的最新值。此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中复本的个数。最终一致性方面最出名

18、的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。2.2.4 最终一致性还有一些最终一致性的变体如下。Causal consistency（因果一致性）：如果Process A通知Process B它已经更新了数据，那么Process B的后续读取操作则读取A写入的最新值，而与A没有因果关系的C则可以最终一致性。Read-your-writes consistency：如果Process A写入了最新的值，那么Process A的后续操作都会读取到最新值。但是其他用户可能要过一会才可以看到。Session consisten

19、cy：此种一致性要求客户端和存储系统交互的整个会话阶段保证Read-your-writes consistency。Hibernate的session提供的一致性保证就属于此种一致性。Monotonic read consistency：此种一致性要求如果Process A已经读取了对象的某个值，那么后续操作将不会读取到更早的值。Monotonic write consistency：此种一致性保证系统会序列化执行一个Process中的所有写操作。2.2.5 一致性散列1 1基本概念基本概念一致性散列算法（Consistent Hashing）最早在论文Consistent Hashing a

20、nd Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web中被提出。简单来说，一致性散列将整个散列值空间组织成一个虚拟的圆环。假设某散列函数H的值空间为02321（即散列值是一个32位无符号整形），整个散列空间环如图所示。2容错性和扩展性（1）容错性现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般来说，在一致性散列算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行

21、走遇到的第一台服务器）之间的数据，其他不会受到影响，如图所示。2容错性和扩展性（2）扩展性如果在系统中增加一台服务器Node X，如图所示。此时对象A、B、D不受影响，只有对象C需要重定位到新的Node X。一般来说，在一致性散列算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其他数据也不会受到影响。2容错性和扩展性（3）虚拟节点一致性散列算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如图所示。2.3 分布式系统概述2.3.1 分布式系统的基础知识2.3.2

22、分布式系统的特性2.3.3 分布式存储系统实例：Apache Hadoop2.3.1 分布式系统的基础知识大数据技术的需求是推动分布式系统发展的一大动力。大数据存储技术的演变最初源于互联网公司的大规模分布式存储系统。与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。互联网的业务发展很快，而且注重成本，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。普通PC服务器性价比高，故

23、障率也高，需要在软件层面实现自动容错，保证数据的一致性。另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使系统的处理能力得到线性扩展。2.3.2 分布式系统的特性乔治库鲁里斯（George Coulouris）是分布式系统：概念与设计（Distributed Systems:Concepts and Design）一书的作者，曾是剑桥大学的高级研究员。他曾经对分布式系统下了一个简单的定义：你会知道系统当中的某台计算机崩溃或停止运行了，但是你的软件却永远不会。这句话虽然简单，但是却道出了分布式系统的关键特性。分布式系统的特性包括容错性、高可扩展性、开放性、并发处理能力和透明性。2

24、.3.3 分布式存储系统实例：Apache HadoopHadoop是由Apache基金会开发的分布式存储与计算框架。用户不需要了解底层的分布式计算原理就可以轻松开发出分布式计算程序，可以充分利用集群中闲置的计算资源，将集群的真正威力调动起来。Hadoop由两个重要模块组成。一个是Hadoop分布式文件系统（Hadoop Distributed File System），顾名思义，就是一个分布式的文件系统，可以将文件数据分布式地存储在集群中的不同节点上。另一个是MapReduce系统，是一个针对大量数据的分布式计算系统。图2.13 Hadoop的核心组成1关于关于Apache HadoopHa

25、doop的思路来自谷歌提出的MapReduce分布式计算框架。谷歌的MapReduce框架可以把一个应用程序分解为许多并行计算指令，跨越大量的计算节点运行非常巨大的数据集。而Hadoop的MapReduce则是对谷歌MapReduce的开源实现。另一方面其分布式文件系统则是谷歌的GFS的开源实现。Hadoop原本是Apache Nutch中的一个子项目。后来Apache将MapReduce模块与Nutch Distributed File System（NDFS）单独抽离出来成为一个顶级项目。Hadoop已经成为目前世界上最流行的分布式计算框架之一，Apache也建立了不少与Hadoop相关的

26、项目，如HBase、Cassandra、Avro、Hive、Mahout等项目。2HDFS分布式文件系分布式文件系统Hadoop分布式文件系统（HDFS）是一个主从式的分布式文件系统，是GFS的一种开源实现。HDFS可以利用大量廉价存储器组成分布式存储集群，取代昂贵的集中式磁盘存储阵列。而HDFS集群由一个NameNode和多个DataNode组成，除此之外还有用于热备份的Secondary NameNode，防止集群出现单点故障。2HDFS分布式文件系分布式文件系统（1）NameNodeNameNode是整个集群的管理者。它并不存储数据本身，而负责存储文件系统的元数据。它负责管理文件系统名称

27、空间，并控制外部客户端对文件系统的访问。NameNode决定如何将文件内容映射到DataNode的数据块上。此外，实际数据传输并不会经过NameNode，而会让对应的DataNode接收实际数据，并处理分布式存储系统的负载均衡问题。整个文件系统只有一个NameNode，因此很明显集群可能会出现单点故障，这点需要利用Secondary NameNode来解决问题。2HDFS分布式文件系分布式文件系统（2）Secondary NameNodeSecondary NameNode是NameNode的备份节点，HDFS会将NameNode的数据实时备份到Secondary NameNode上，当Nam

28、eNode宕机需要重启时，则可以利用Secondary NameNode中的数据加快NameNode的重启恢复速度。2HDFS分布式文件系分布式文件系统（3）DataNodeDataNode是实际的数据存储节点，负责相应NameNode创建、删除和复制块的命令。NameNode会读取来自DataNode的心跳信息，以此判断DataNode是否存活。同一份数据会以多份副本存储在不同的DataNode上，一旦某一个DataNode宕机，NameNode会立即采取手段来处理问题。2HDFS分布式文件系分布式文件系统（4）MapReduce模型MapReduce既是Hadoop中的模块，也是一个计算模

29、型。用户需要自己将算法划分成Map和Reduce两个阶段。首先将数据划分为小块的数据，将数据分配到不同计算节点的Map任务中计算，然后将计算结果汇总到Reduce节点中进行合并，得出最终结果。MapReduce系统也是主从式的计算系统。在使用YARN后，每个集群有一个Resource-Manager，用于管理整个集群。集群中每个计算节点都有一个NodeManager，负责管理某个节点的容器并监视其资源使用。每个应用程序由一个MRAppMaster进行管理。3Apache Hadoop特性特性（1）高可靠性：Apache Hadoop可以可靠地将数据存储到节点上。（2）高可扩展性：Apache

30、Hadoop的存储和计算节点可以快速扩展，并自动进行负载均衡。（3）高效性：一方面Apache Hadoop会自动在各个节点之间动态调动数据，保证每个节点存储均衡，另一方面读取数据时我们可以从不同节点并行读取，提高数据读取的速度。（4）高容错性：Apache Hadoop会将数据冗余存储在不同节点上，保证数据容错性，计算任务失败时也会自动重新分配任务。（5）低成本：Apache Hadoop是开源软件，可以节省商业软件的购买成本。同时，Apache Hadoop可以用廉价节点组成的集群取代昂贵的超级计算机，从而可以节省硬件成本。2.4 分布式系统的进阶2.4.1 分布式存储系统2.4.2 分布

31、式计算系统2.4.3 分布式资源管理系统2.4.1 分布式存储系统分布式存储系统大致可分为5个子方向：结构化存储、非结构化存储、半结构化存储、In-memory 存储及NewSQL。除了这5个子方向之外，分布式存储系统还有一系列的理论、算法、技术作为支撑，例如 Paxos、CAP理论、一致性散列、时钟技术、2PC、3PC等。1结构化存构化存储结构化存储的历史非常古老，典型的场景就是事务处理系统或者关系型数据库（RDBMS）。传统的结构化存储都是从单机做起的，例如大家耳熟能详的MySQL。MySQL的成长史就是互联网的成长史。除了MySQL之外，PostgreSQL也是近年来势头非常强劲的一个R

32、DBMS。传统的结构化存储系统强调以下内容。结构化的数据（例如关系表）；强一致性（例如银行系统，电商系统等场景）；随机访问（索引、增删查改、SQL）。2非非结构化存构化存储与结构化存储不同的是，非结构化存储强调的是高可扩展性，典型的系统就是分布式文件系统。分布式文件系统也是一个很老的研究话题，例如20世纪70年代的Xerox Alto，80年代的NFS、AFS，90年代的xFS等。然而，这些早期的分布式文件系统只是起到了网络磁盘的作用，其最大的问题就是不支持容错和错误恢复。而Google在2003年SOSP会议上推出的GFS（Google File System）则走出了里程碑的一步，其开源实

33、现对应为HDFS。3半半结构化存构化存储半结构化存储的提出是为了解决结非结构化存储系统随机访问性能差的问题。我们通常会听到一些流行的名词，例如NoSQL、Key-Value Store，包括对象存储等。这些都属于半结构化存储研究的领域，其中以NoSQL的发展势头最为强劲。NoSQL系统既有分布式文件系统所具有的可扩展性，又有结构化存储系统的随机访问能力（例如随机操作），系统在设计时通常选择简单键值（K-V）进行存储，抛弃了传统RDBMS里复杂SQL查询及ACID事务。4In-memory存存储随着业务的并发越来越高，存储系统对低延迟的要求也越来越高。同时由于摩尔定律以及内存的价格不断下降，基于

34、内存的存储系统也开始普及。顾名思义，In-memory存储就是将数据存储在内存中，从而获得读写的高性能。比较有名的系统包括Memcached和Redis。这些基于K-V键值系统的主要目的是为基于磁盘的存储系统做缓存。还有一些偏向于内存计算的系统，例如Distributed shared memory、RamCloud、Tachyon（Alluxio）项目等。5NewSQL前面介绍结构化存储时提到，单机RDBMS系统在可扩展性上面临着巨大的挑战，然而NoSQL不能很好的支持关系模型。那有没有一种系统能兼备RDBMS的特性（例如，完整的SQL支持、ACID事务支持），又能像NoSQL系统那样具有强

35、大的可扩展能力呢？2012年Google在OSDI会议上发表的Spanner，以及2013年在SIGMOD会议上发表的F1，让业界第一次看到了关系模型和NoSQL在超大规模数据中心上融合的可能性。不过由于这些系统大都过于复杂，没有工业界大公司的支持还是很难做出来的。2.4.2 分布式计算系统分布式计算和并行计算一样吗？可以这样认为：传统的并行计算的要求：投入更多机器，数据大小不变，计算速度更快。分布式计算的要求：投入更多的机器，能处理更大的数据。1传统基于消息的系基于消息的系统这类系统里比较有代表性的就是MPI（Message Passing Interface）。目前比较流行的两个MPI实现

36、是MPICH2和OpenMPI。MPI这个框架非常灵活，对程序的结构几乎没有太多约束，以至于人们有时把MPI称为一组接口API，而不是系统框架。MPI除了提供消息传递接口之外，其框架还实现了资源管理和分配，以及调度的功能。除此之外，MPI在高性能计算里也被广泛使用，通常可以和 Infiniband 这样的高速网络无缝结合。2MapReduce家族系家族系统这一类系统又称作Dataflow系统，其中以Hadoop MapReduce和Spark为代表。其实在学术界有很多类似的系统，例如Dryad、Twister等。这一类系统的特点是将计算抽象成为高层操作，例如像Map、Reduce、Filter

37、这样的函数式算子，将算子组合成有向无环图DAG，然后由后端的调度引擎进行并行化调度。其中，MapReduce系统属于比较简单的DAG，只有Map和reduce两层节点。MapReduce这样的系统之所以可以扩展到超大规模的集群上运行，就是因为其完备的容错机制。在Hadoop社区还有很多基于MapReduce框架的衍生产品，例如Hive（一种并行数据库OLAP）、Pig（交互式数据操作）等。3图计算系算系统图计算系统是分布式计算的另一个分支，这些系统都是把计算过程抽象成图，然后在不同节点分布式执行，例如PageRank这样的任务，很适合用图计算系统来表示。大数据图是无法使用单台机器进行处理的，如

38、果对大图数据进行并行处理，对于每一个顶点之间都是连通的图来讲，难以分割成若干完全独立的子图进行独立的并行处理。即使可以分割，也会面临并行机器的协同处理，以及将最后的处理结果进行合并等一系列问题。这需要图数据处理系统选取合适的图分割以及图计算模型来迎接挑战并解决问题。4基于状基于状态的系的系统这一类系统主要包括2010年在OSDI会议上推出的Piccolo，以及后来2012年在NIPS会议上 Google推出的开源机器学习系统DistBelief，再到后来被机器学习领域广泛应用的参数服务器（Parameter Server）架构。5实时流流处理系理系统实时流处理系统是为高效实时地处理流式数据而提

39、供服务的，更关注数据处理的实时性，能够更加快速地为决策提供支持。流处理是由复杂事件处理（CEP）发展而来的，流处理模式包括两种：连续查询处理模式、可扩展数据流模式。2.4.3 分布式资源管理系统 从支持离线处理的MapReduce，到支持在线处理的Storm，从迭代式计算框架Spark到流式处理框架S4，各种框架诞生于不同的公司或者实验室，它们各有所长，各自解决了某一类应用问题。而在大部分互联网公司中，这几种框架可能都会采用，例如对于搜索引擎公司，可能的技术方案如下：网页建索引采用MapReduce框架，自然语言处理/数据挖掘采用Spark（网页PageRank计算、聚类分类算法等），对性能要

40、求很高的数据挖掘算法用MPI等。考虑到资源利用率、运维成本、数据共享等因素，公司一般希望将所有这些框架部署到一个公共的集群中，让它们共享集群的资源，并对资源进行统一使用，这样，便诞生了资源统一管理与调度平台，典型的代表是Mesos和YARN。资源统一管理和调度平台具有以下特点：1 1支持多种支持多种计算框架算框架2 2扩展性展性3 3容容错性性4 4高高资源利用率源利用率5 5细粒度的粒度的资源分配源分配2.5 典型的分布式系统2.5.1 网格系统2.5.2 P2P系统2.5.3 透明计算2.5.4 区块链系统2.5.1 网格系统网格是一种能够将多组织拥有和管理的计算机、网络、数据库和科学仪器

41、综合协同使用的基础设施。网格应用程序大多涉及需要跨越组织界限的可安全共享的大规模数据和/或计算资源。这使网格应用程序的管理和部署成为一项复杂的任务。在混杂的网格环境中，网格中间件为用户提供了无缝的计算能力和统一访问资源能力。目前，世界范围内已经发展有数个工具包和系统，其中大部分是学术研究项目的成果。1.网格的概念Globus定义网格为：一种能够整合的合作使用的由多家组织所拥有和管理的高端计算机、网络、数据库、实验设备的基础设施。由Gridbus提出一种基于效能的网格定义：网格是一类并行、分布系统，能够在运行时动态分享、选择、聚合地理散布的自治资源，依据它们的可用性、能力、性能、代价以及用户对服

42、务质量的需求。2.网格的组成3Globus工具包Globus是一种研究网格环境中互操作的中间件技术，为科学和工程上的网格计算应用程序提供基本的支撑环境。它定义了构建计算网格的一组基本服务和功能，包括安全、资源管理、通信、目录管理等基本服务，被许多应用网格项目采用。2.5.2 P2P系统 对等网络系统（Peer-to-Peer），简称P2P系统，即媒体及公众所称的“点对点系统”，是一种应用在对等者（Peer）之间分配任务和工作负载的分布式应用架构的系统。对等网络的思想是：网络的所有参与者共享他们所拥有的一部分硬件资源，包括处理器资源、存储资源和网络资源等，这些共享资源可以通过网络被其他对等者直接

43、访问并为之提供服务和内容。P2P系统性质（1）高度分散化（2）自组织性（3）多管理域P2P系统特点（1）部署低门槛（2）有机增长（3）对故障与攻击的恢复力（4）资源的丰富性与多样性对等网络应用（1）共享及分发文件（2）流媒体（3）电话（4）志愿计算2.5.3 透明计算透明计算是一种用户无须感知计算机操作系统、中间件、应用程序和通信网络的具体所在，只需根据自己的需求，通过网络从所使用的各种终端设备（包括固定、移动及家庭中的各类终端设备）中选择并使用相应服务（例如计算、电话、电视、上网和娱乐等）的计算模式。图2.20 透明计算模式透明计算核心技术（1）透明云架构透明计算核心技术（2）元操作系统（M

44、eta OS）（3）客户端实现图2.23 HTML5与传统APP的对比2.5.4 区块链系统区块链（Blockchain）是一种去中心化、不可篡改、可追溯、多方共同维护的分布式数据库系统，能够将传统单方维护的仅涉及自己业务的多个孤立数据库整合在一起，分布式地存储在多方共同维护的多个节点，任何一方都无法完全控制这些数据，只能按照严格的规则和共识进行更新，从而实现了可信的多方间的信息共享和监督，避免了烦琐的人工对账，提高了业务处理效率，降低了交易成本。区块链的核心特征 块链结构：每一块有时间戳，每一块都含有前面一块的散列加密信息，对每个交易进行验证。多独立拷贝存储：区块链系统的每个节点都存储同样信

45、息。拜占庭容错：容忍少于1/3 节点恶意作弊或被黑客攻击，系统仍然能够正常工作。区块链模式（1）模式1：、+P2P+挖矿。（2）模式2：、+P2P+挖矿+默克尔-帕特里夏树（Merkel Patricia tree）区块链体系架构区块链应用（1）数字创意的助推器（2）万物互联的万物账簿（3）供应链端到端防伪（4）隐私数据保护的密码机（5）互联网新技术分布式计算概述分布式计算的理论基础分布式系统概述分布式系统的进阶典型的分布式系统小结课内复习1分布式计算的定义和特征是什么？2什么是ACID原则？3什么是CAP理论？4什么是BASE理论？5如何理解最终一致性？6分布式存储与分布式计算的区别与联系是

46、什么？课外思考1在日常生活中，为什么我们所接触到的分布式系统越来越多了？2CAP定理中的几个关键因素为什么不能同时保证？不同的组合有什么样的应用场景？3通过了解区块链的背景，说说你所理解的区块链作为一种分布式系统背后的全新理念。动手实践1Globus是一个开放源码的网格的基础平台，Globus Toolkit工具包是一个构筑网格计算环境的中间件，提供基本的资源定位、管理、通信和安全等服务。该计算工具包是模块化的，允许用户按自己的需要定制环境。利用这套工具可以建立计算网格，并可以进行网格应用的开发。任务：通过Globus Toolkit的官方网站下载并安装使用Globus Toolkit。动手实践2HTCondor是一个专门用于计算密集型作业的负载管理系统，它为用户提供了作业排队机制、调度策略、优先计划、资源监测和资源管理，诞生于美国威斯康星大学麦迪逊分校。任务：通过HTCondor的官方网站下载并安装使用HTCondor，了解它是如何实现大吞吐量计算过程的。