云计算技术——分布式计算

LOGO云 计 算 原 理 与 实 践Principles and Practice of Cloud Computing LOGOOutlinel 2.1 分布式计算概述l 2.2 分布式计算的理论基础l 2.3 分布式系统概述l 2.4 分布式系统的进阶l 2.5 典型的分布式系统 Data Science StatisticsMachine Learning Domain expertiseMathematicsData engineering LOGO2.1 分布式计算概述2.1.1 基本概念2.1.2 分布式计算的原理 LOGO2.1.1 基本概念（1）集中式计算集中式计算完全依赖于一台大型的中心计算机的处理能力，这台中心计算机称为主机（Host或mainframe），与中心计算机相连的终端设备具有各不相同非常低的计算能力。实际上大多数终端完全不具有处理能力，仅作为输入输出设备使用。（2）分布式计算 与集中式计算相反，分布式计算中，多个通过网络互联的计算机都具有一定的计算能力，它们之间互相传递数据，实现信息共享，协作共同完成一个处理任务。 LOGO中科院的定义中国科学院对分布式计算有一个定义： 分布式计算就是在两个或多个软件互相共享信息，这些软件既可以在同一台计算机上运行，也可以在通过网络连接起来的多台计算机上运行。 LOGO分布式计算比起其他算法具有以下几个优点。 稀有资源可以共享； 通过分布式计算可以在多台计算机上平衡计算负载； 可以把程序放在最适合运行它的计算机上。 LOGO2.1.2 分布式计算的原理l 分布式计算就是将计算任务分摊到大量的计算节点上，一起完成海量的计算任务。而分布式计算的原理和并行计算类似，就是将一个复杂庞大的计算任务适当划分为一个个小任务，任务并行执行，只不过分布式计算会将这些任务分配到不同的计算节点上，每个计算节点只需要完成自己的计算任务即可，可以有效分担海量的计算任务。而每个计算节点也可以并行处理自身的任务，更加充分利用机器的CPU资源。最后再将每个节点的计算结果汇总，得到最后的计算结果。 LOGO分布式计算一般分为以下几步：1设计分布式计算模型首先要规定分布式系统的计算模型。计算模型决定了系统中各个组件应该如何运行，组件之间应该如何进行消息通信，组件和节点应该如何管理等。2分布式任务分配分布式算法不同于普通算法。普通算法通常是按部就班，一步接一步完成任务。而分布式计算中计算任务是分摊到各个节点上的。该算法着重解决的是能否分配任务，或如何分配任务的问题。3编写并执行分布式程序使用特定的分布式计算框架与计算模型，将分布式算法转化为实现，并尽量保证整个集群的高效运行，难点：（1）计算任务的划分（2）多节点之间的通信方式 LOGO2.2 分布式计算的理论基础2.2.1 ACID 原则2.2.2 CAP理论2.2.3 BASE理论2.2.4 最终一致性2.2.5 一致性散列 LOGO2.2.1 ACID原则ACID是数据库事务正常执行的四个原则，分别指原子性、一致性、独立性及持久性。 LOGO2.2.1 ACID原则1A（Atomicity）原子性原子性很容易理解，也就是说事务里的所有操作要么全部做完，要么都不做，事务成功的条件是事务里的所有操作都成功，只要有一个操作失败，整个事务就失败，需要回滚。例如银行转账，从A账户转100元至B账户，分为两个步骤：从A账户取100元；存入100元至B账户。这两步要么一起完成，要么一起不完成，如果只完成第一步，第二步失败，钱会莫名其妙少了100元。 LOGO2.2.1 ACID原则2C（Consistency）一致性一致性也比较容易理解，也就是说数据库要一直处于一致的状态，事务的运行不会改变数据库原本的一致性约束。例如现有完整性约束a + b = 10，如果一个事务改变了a，那么必须得改变b，使得事务结束后依然满足a + b = 10，否则事务失败。 LOGO2.2.1 ACID原则3I（Isolation）独立性所谓的独立性是指并发的事务之间不会互相影响，如果一个事务要访问的数据正在被另外一个事务修改，只要另外一个事务未提交，它所访问的数据就不受未提交事务的影响。例如交易是从A账户转100元至B账户，在这个交易还未完成的情况下，如果此时B查询自己的账户，是看不到新增加的100元的。 LOGO2.2.1 ACID原则4D（Durability）持久性持久性是指一旦事务提交后，它所做的修改将会永久保存在数据库上，即使出现宕机也不会丢失。这些原则解决了数据的一致性、系统的可靠性等关键问题，为关系数据库技术的成熟以及在不同领域的大规模应用创造了必要的条件。 LOGO2.2.2 CAP理论1CAP理论定义 2000年7月，加州大学伯克利分校的埃里克布鲁尔（Eric Brewer）教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的塞思吉尔伯符（Seth Gilbert）和南希林奇（Nancy Lynch）从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。 一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项，如图2.1所示。 LOGO一致性一致性指“All nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。对于一致性，可以分为从客户端和服务端两个不同的视角来看。 从客户端来看，一致性主要指多并发访问时更新过的数据如何获取的问题。 从服务端来看，则是如何将更新复制分布到整个系统，以保证数据的最终一致性问题。 LOGO 可用性l 可用性是指“Reads and writes always succeed”，即服务一直可用，而且是在正常的响应时间内。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是该系统使用的任何算法必须最终终止。l 当同时要求分区容错性时，这是一个很强的定义：即使是严重的网络错误，每个请求也必须终止。好的可用性主要是指系统能够很好地为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。通常情况下可用性和分布式数据冗余、负载均衡等有着很大的关联。 LOGO 分区容错性 l 分区容错性指“The system continues to operate despite arbitrary message loss or failure of part of the system”，也就是指分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。l 分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求应用虽然是一个分布式系统，但看上去却好像是一个可以运转正常的整体。例如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，或者是机器之间有网络异常，将分布式系统分隔为独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。 LOGO2CAP理论的阐述与证明 图 2.2 CAP的 基 本 场 景 LOGO图 2.3 分 布 式 系 统 正 常 运 转 的 流 程 LOGO图 2.4 断 开 N1和 N2之 间 的 网 络 LOGO3CAP权衡通过CAP理论，知道无法同时满足一致性、可用性和分区容错性这三个特性，那应该如何取舍呢？（1）CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。（2）CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。（3）AP without C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。 LOGO2.2.3 BASE理论l 丹普里切特（Dan Pritchett）在对大规模分布式系统的实践总结过程中，提出了BASE理论，BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consistency）。l BASE是指基本可用（Basically Available）、软状态（Soft State）、最终一致性（Eventual Consistency）。 LOGO1基本可用l 基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。 LOGO2软状态l 软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。l 分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。例如MySQL replication的异步复制就是这种体现。 LOGO3最终一致性l 最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。l 弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。l BASE和ACID的区别与联系是什么呢？ACID是传统数据库常用的设计理念，追求强一致性模型。BASE支持的是大型分布式系统，提出通过牺牲强一致性获得高可用性。ACID和BASE代表了两种截然相反的设计哲学。在分布式系统设计的场景中，系统组件对一致性要求是不同的，因此ACID和BASE又会结合使用。 LOGO2.2.4 最终一致性下面以上面的场景来描述下不同程度的一致性。强一致性（即时一致性）：假如A先写入了一个值到存储系统，存储系统保证后续A、B、C的读取操作都将返回最新值。弱一致性：假如A先写入了一个值到存储系统，存储系统不能保证后续A、B、C的读取操作能读取到最新值。此种情况下有一个“时间窗口”的概念，它特指从A写入值，到后续操作A、B、C读取到最新值这一段时间。“时间窗口”类似时空穿梭门，不过穿梭门是可以穿越到过去的，而一致性窗口只能穿越到未来，方法很简单，就是“等会儿”。最终一致性：是弱一致性的一种特例。假如A首先“写”了一个值到存储系统，存储系统保证如果在A、B、C后续读取之前没有其他写操作更新同样的值的话，最终所有的读取操作都会读取到A写入的最新值。此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中复本的个数。最终一致性方面最出名的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。 LOGO2.2.4 最终一致性还有一些最终一致性的变体如下。 Causal consistency（因果一致性）：如果Process A通知Process B它已经更新了数据，那么Process B的后续读取操作则读取A写入的最新值，而与A没有因果关系的C则可以最终一致性。 Read-your-writes consistency：如果Process A写入了最新的值，那么Process A的后续操作都会读取到最新值。但是其他用户可能要过一会才可以看到。 Session consistency：此种一致性要求客户端和存储系统交互的整个会话阶段保证Read-your- writes consistency。Hibernate的session提供的一致性保证就属于此种一致性。 Monotonic read consistency：此种一致性要求如果Process A已经读取了对象的某个值，那么后续操作将不会读取到更早的值。 Monotonic write consistency：此种一致性保证系统会序列化执行一个Process中的所有写操作。 LOGO2.2.5 一致性散列1基本概念一致性散列算法（Consistent Hashing）最早在论文Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web中被提出。简单来说，一致性散列将整个散列值空间组织成一个虚拟的圆环。假设某散列函数H的值空间为02 321（即散列值是一个32位无符号整形），整个散列空间环如图所示。 LOGO2容错性和扩展性（1）容错性现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般来说，在一致性散列算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间的数据，其他不会受到影响，如图所示。 LOGO2容错性和扩展性（2）扩展性如果在系统中增加一台服务器Node X，如图所示。此时对象A、B、D不受影响，只有对象C需要重定位到新的Node X。一般来说，在一致性散列算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其他数据也不会受到影响。 LOGO2容错性和扩展性（3）虚拟节点一致性散列算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如图所示。 LOGO2.3 分布式系统概述2.3.1 分布式系统的基础知识2.3.2 分布式系统的特性2.3.3 分布式存储系统实例：Apache Hadoop LOGO2.3.1 分布式系统的基础知识l 大数据技术的需求是推动分布式系统发展的一大动力。大数据存储技术的演变最初源于互联网公司的大规模分布式存储系统。与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。互联网的业务发展很快，而且注重成本，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。普通PC服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使系统的处理能力得到线性扩展。 LOGO2.3.2 分布式系统的特性l 乔治库鲁里斯（George Coulouris）是分布式系统：概念与设计（Distributed Systems:Concepts and Design）一书的作者，曾是剑桥大学的高级研究员。他曾经对分布式系统下了一个简单的定义：你会知道系统当中的某台计算机崩溃或停止运行了，但是你的软件却永远不会。这句话虽然简单，但是却道出了分布式系统的关键特性。分布式系统的特性包括容错性、高可扩展性、开放性、并发处理能力和透明性。 LOGO2.3.3 分布式存储系统实例：Apache Hadoopl Hadoop是由Apache基金会开发的分布式存储与计算框架。用户不需要了解底层的分布式计算原理就可以轻松开发出分布式计算程序，可以充分利用集群中闲置的计算资源，将集群的真正威力调动起来。l Hadoop由两个重要模块组成。一个是Hadoop分布式文件系统（Hadoop Distributed File System），顾名思义，就是一个分布式的文件系统，可以将文件数据分布式地存储在集群中的不同节点上。另一个是MapReduce系统，是一个针对大量数据的分布式计算系统。 LOGO图2.13 Hadoop的核心组成 LOGO1关于Apache Hadoopl Hadoop的思路来自谷歌提出的MapReduce分布式计算框架。谷歌的MapReduce框架可以把一个应用程序分解为许多并行计算指令，跨越大量的计算节点运行非常巨大的数据集。而Hadoop的MapReduce则是对谷歌MapReduce的开源实现。另一方面其分布式文件系统则是谷歌的GFS的开源实现。l Hadoop原本是Apache Nutch中的一个子项目。后来Apache将MapReduce模块与Nutch Distributed File System（NDFS）单独抽离出来成为一个顶级项目。l Hadoop已经成为目前世界上最流行的分布式计算框架之一，Apache也建立了不少与Hadoop相关的项目，如HBase、Cassandra、Avro、Hive、Mahout等项目。 LOGO2HDFS分布式文件系统l Hadoop分布式文件系统（HDFS）是一个主从式的分布式文件系统，是GFS的一种开源实现。HDFS可以利用大量廉价存储器组成分布式存储集群，取代昂贵的集中式磁盘存储阵列。而HDFS集群由一个NameNode和多个DataNode组成，除此之外还有用于热备份的Secondary NameNode，防止集群出现单点故障。 LOGO2HDFS分布式文件系统（1）NameNodel NameNode是整个集群的管理者。它并不存储数据本身，而负责存储文件系统的元数据。它负责管理文件系统名称空间，并控制外部客户端对文件系统的访问。l NameNode决定如何将文件内容映射到DataNode的数据块上。此外，实际数据传输并不会经过NameNode，而会让对应的DataNode接收实际数据，并处理分布式存储系统的负载均衡问题。l 整个文件系统只有一个NameNode，因此很明显集群可能会出现单点故障，这点需要利用Secondary NameNode来解决问题。 LOGO2HDFS分布式文件系统（2）Secondary NameNodel Secondary NameNode是NameNode的备份节点，HDFS会将NameNode的数据实时备份到Secondary NameNode上，当NameNode宕机需要重启时，则可以利用Secondary NameNode中的数据加快NameNode的重启恢复速度。 LOGO2HDFS分布式文件系统（3）DataNodel DataNode是实际的数据存储节点，负责相应NameNode创建、删除和复制块的命令。NameNode会读取来自DataNode的心跳信息，以此判断DataNode是否存活。同一份数据会以多份副本存储在不同的DataNode上，一旦某一个DataNode宕机，NameNode会立即采取手段来处理问题。 LOGO2HDFS分布式文件系统（4）MapReduce模型l MapReduce既是Hadoop中的模块，也是一个计算模型。用户需要自己将算法划分成Map和Reduce两个阶段。首先将数据划分为小块的数据，将数据分配到不同计算节点的Map任务中计算，然后将计算结果汇总到Reduce节点中进行合并，得出最终结果。l MapReduce系统也是主从式的计算系统。在使用YARN后，每个集群有一个Resource-Manager，用于管理整个集群。集群中每个计算节点都有一个NodeManager，负责管理某个节点的容器并监视其资源使用。每个应用程序由一个MRAppMaster进行管理。 LOGO3Apache Hadoop特性（1）高可靠性：Apache Hadoop可以可靠地将数据存储到节点上。（2）高可扩展性：Apache Hadoop的存储和计算节点可以快速扩展，并自动进行负载均衡。（3）高效性：一方面Apache Hadoop会自动在各个节点之间动态调动数据，保证每个节点存储均衡，另一方面读取数据时我们可以从不同节点并行读取，提高数据读取的速度。（4）高容错性：Apache Hadoop会将数据冗余存储在不同节点上，保证数据容错性，计算任务失败时也会自动重新分配任务。（5）低成本：Apache Hadoop是开源软件，可以节省商业软件的购买成本。同时，Apache Hadoop可以用廉价节点组成的集群取代昂贵的超级计算机，从而可以节省硬件成本。 LOGO2.4 分布式系统的进阶2.4.1 分布式存储系统2.4.2 分布式计算系统2.4.3 分布式资源管理系统 LOGO2.4.1 分布式存储系统l 分布式存储系统大致可分为5个子方向：结构化存储、非结构化存储、半结构化存储、In-memory 存储及NewSQL。l 除了这5个子方向之外，分布式存储系统还有一系列的理论、算法、技术作为支撑，例如 Paxos、CAP理论、一致性散列、时钟技术、2PC、3PC等。 LOGO1结构化存储结构化存储的历史非常古老，典型的场景就是事务处理系统或者关系型数据库（RDBMS）。传统的结构化存储都是从单机做起的，例如大家耳熟能详的MySQL。MySQL的成长史就是互联网的成长史。除了MySQL之外，PostgreSQL也是近年来势头非常强劲的一个RDBMS。传统的结构化存储系统强调以下内容。 结构化的数据（例如关系表）； 强一致性（例如银行系统，电商系统等场景）； 随机访问（索引、增删查改、SQL）。 LOGO2非结构化存储与结构化存储不同的是，非结构化存储强调的是高可扩展性，典型的系统就是分布式文件系统。分布式文件系统也是一个很老的研究话题，例如20世纪70年代的Xerox Alto，80年代的NFS、AFS，90年代的xFS等。然而，这些早期的分布式文件系统只是起到了网络磁盘的作用，其最大的问题就是不支持容错和错误恢复。而Google在2003年SOSP会议上推出的GFS（Google File System）则走出了里程碑的一步，其开源实现对应为HDFS。 LOGO3半结构化存储l 半结构化存储的提出是为了解决结非结构化存储系统随机访问性能差的问题。我们通常会听到一些流行的名词，例如NoSQL、Key-Value Store，包括对象存储等。这些都属于半结构化存储研究的领域，其中以NoSQL的发展势头最为强劲。NoSQL系统既有分布式文件系统所具有的可扩展性，又有结构化存储系统的随机访问能力（例如随机操作），系统在设计时通常选择简单键值（K-V）进行存储，抛弃了传统RDBMS里复杂SQL查询及ACID事务。 LOGO4In-memory存储l 随着业务的并发越来越高，存储系统对低延迟的要求也越来越高。同时由于摩尔定律以及内存的价格不断下降，基于内存的存储系统也开始普及。顾名思义，In-memory存储就是将数据存储在内存中，从而获得读写的高性能。比较有名的系统包括Memcached和Redis。这些基于K-V键值系统的主要目的是为基于磁盘的存储系统做缓存。还有一些偏向于内存计算的系统，例如Distributed shared memory、RamCloud、Tachyon（Alluxio）项目等。 LOGO5NewSQLl 前面介绍结构化存储时提到，单机RDBMS系统在可扩展性上面临着巨大的挑战，然而NoSQL不能很好的支持关系模型。那有没有一种系统能兼备RDBMS的特性（例如，完整的SQL支持、ACID事务支持），又能像NoSQL系统那样具有强大的可扩展能力呢？2012年Google在OSDI会议上发表的Spanner，以及2013年在SIGMOD会议上发表的F1，让业界第一次看到了关系模型和NoSQL在超大规模数据中心上融合的可能性。不过由于这些系统大都过于复杂，没有工业界大公司的支持还是很难做出来的。 LOGO2.4.2 分布式计算系统分布式计算和并行计算一样吗？可以这样认为： 传统的并行计算的要求：投入更多机器，数据大小不变，计算速度更快。 分布式计算的要求：投入更多的机器，能处理更大的数据。 LOGO1传统基于消息的系统l 这类系统里比较有代表性的就是MPI（Message Passing Interface）。目前比较流行的两个MPI实现是MPICH2和OpenMPI。MPI这个框架非常灵活，对程序的结构几乎没有太多约束，以至于人们有时把MPI称为一组接口API，而不是系统框架。MPI除了提供消息传递接口之外，其框架还实现了资源管理和分配，以及调度的功能。除此之外，MPI在高性能计算里也被广泛使用，通常可以和 Infiniband 这样的高速网络无缝结合。 LOGO2MapReduce家族系统l 这一类系统又称作Dataflow系统，其中以Hadoop MapReduce和Spark为代表。其实在学术界有很多类似的系统，例如Dryad、Twister等。这一类系统的特点是将计算抽象成为高层操作，例如像Map、Reduce、Filter这样的函数式算子，将算子组合成有向无环图DAG，然后由后端的调度引擎进行并行化调度。其中，MapReduce系统属于比较简单的DAG，只有Map和reduce两层节点。MapReduce这样的系统之所以可以扩展到超大规模的集群上运行，就是因为其完备的容错机制。在Hadoop社区还有很多基于MapReduce框架的衍生产品，例如Hive（一种并行数据库OLAP）、Pig（交互式数据操作）等。 LOGO3图计算系统l 图计算系统是分布式计算的另一个分支，这些系统都是把计算过程抽象成图，然后在不同节点分布式执行，例如PageRank这样的任务，很适合用图计算系统来表示。l 大数据图是无法使用单台机器进行处理的，如果对大图数据进行并行处理，对于每一个顶点之间都是连通的图来讲，难以分割成若干完全独立的子图进行独立的并行处理。即使可以分割，也会面临并行机器的协同处理，以及将最后的处理结果进行合并等一系列问题。这需要图数据处理系统选取合适的图分割以及图计算模型来迎接挑战并解决问题。 LOGO4基于状态的系统l 这一类系统主要包括2010年在OSDI会议上推出的Piccolo，以及后来2012年在NIPS会议上 Google推出的开源机器学习系统DistBelief，再到后来被机器学习领域广泛应用的参数服务器（Parameter Server）架构。 LOGO5实时流处理系统l 实时流处理系统是为高效实时地处理流式数据而提供服务的，更关注数据处理的实时性，能够更加快速地为决策提供支持。流处理是由复杂事件处理（CEP）发展而来的，流处理模式包括两种：连续查询处理模式、可扩展数据流模式。 LOGO2.4.3 分布式资源管理系统 从支持离线处理的MapReduce，到支持在线处理的Storm，从迭代式计算框架Spark到流式处理框架S4，各种框架诞生于不同的公司或者实验室，它们各有所长，各自解决了某一类应用问题。而在大部分互联网公司中，这几种框架可能都会采用，例如对于搜索引擎公司，可能的技术方案如下：网页建索引采用MapReduce框架，自然语言处理/数据挖掘采用Spark（网页PageRank计算、聚类分类算法等），对性能要求很高的数据挖掘算法用MPI等。考虑到资源利用率、运维成本、数据共享等因素，公司一般希望将所有这些框架部署到一个公共的集群中，让它们共享集群的资源，并对资源进行统一使用，这样，便诞生了资源统一管理与调度平台，典型的代表是Mesos和YARN。 LOGO资源统一管理和调度平台具有以下特点：1支持多种计算框架2扩展性3容错性4高资源利用率5细粒度的资源分配 LOGO2.5 典型的分布式系统2.5.1 网格系统2.5.2 P2P系统2.5.3 透明计算2.5.4 区块链系统 LOGO2.5.1 网格系统l 网格是一种能够将多组织拥有和管理的计算机、网络、数据库和科学仪器综合协同使用的基础设施。网格应用程序大多涉及需要跨越组织界限的可安全共享的大规模数据和/或计算资源。这使网格应用程序的管理和部署成为一项复杂的任务。在混杂的网格环境中，网格中间件为用户提供了无缝的计算能力和统一访问资源能力。目前，世界范围内已经发展有数个工具包和系统，其中大部分是学术研究项目的成果。 LOGO1. 网格的概念l Globus定义网格为：一种能够整合的合作使用的由多家组织所拥有和管理的高端计算机、网络、数据库、实验设备的基础设施。l 由Gridbus提出一种基于效能的网格定义：网格是一类并行、分布系统，能够在运行时动态分享、选择、聚合地理散布的自治资源，依据它们的可用性、能力、性能、代价以及用户对服务质量的需求。 LOGO2. 网格的组成 LOGO3Globus工具包l Globus是一种研究网格环境中互操作的中间件技术，为科学和工程上的网格计算应用程序提供基本的支撑环境。它定义了构建计算网格的一组基本服务和功能，包括安全、资源管理、通信、目录管理等基本服务，被许多应用网格项目采用。 LOGO2.5.2 P2P系统 对等网络系统（Peer-to-Peer），简称P2P系统，即媒体及公众所称的“点对点系统”，是一种应用在对等者（Peer）之间分配任务和工作负载的分布式应用架构的系统。对等网络的思想是：网络的所有参与者共享他们所拥有的一部分硬件资源，包括处理器资源、存储资源和网络资源等，这些共享资源可以通过网络被其他对等者直接访问并为之提供服务和内容。 LOGOP2P系统性质（1）高度分散化（2）自组织性（3）多管理域 LOGOP2P系统特点（1）部署低门槛（2）有机增长（3）对故障与攻击的恢复力（4）资源的丰富性与多样性 LOGO对等网络应用（1）共享及分发文件（2）流媒体（3）电话（4）志愿计算 LOGO2.5.3 透明计算透 明 计 算 是 一 种 用 户 无 须 感 知 计 算 机 操 作 系统 、 中 间 件 、 应 用 程 序 和 通 信 网 络 的 具 体 所在 ， 只 需 根 据 自 己 的 需 求 ， 通 过 网 络 从 所 使用 的 各 种 终 端 设 备 （ 包 括 固 定 、 移 动 及 家 庭中 的 各 类 终 端 设 备 ） 中 选 择 并 使 用 相 应 服 务（ 例 如 计 算 、 电 话 、 电 视 、 上 网 和 娱 乐 等 ）的 计 算 模 式 。 LOGO图2.20 透明计算模式 LOGO透明计算核心技术（1）透明云架构 LOGO透明计算核心技术（2）元操作系统（Meta OS）（3）客户端实现 图 2.23 HTML5与 传 统 APP的 对 比 LOGO2.5.4 区块链系统区 块 链 （ Blockchain） 是 一 种 去 中 心 化 、 不 可 篡 改 、可 追 溯 、 多 方 共 同 维 护 的 分 布 式 数 据 库 系 统 ， 能 够将 传 统 单 方 维 护 的 仅 涉 及 自 己 业 务 的 多 个 孤 立 数 据库 整 合 在 一 起 ， 分 布 式 地 存 储 在 多 方 共 同 维 护 的 多个 节 点 ， 任 何 一 方 都 无 法 完 全 控 制 这 些 数 据 ， 只 能按 照 严 格 的 规 则 和 共 识 进 行 更 新 ， 从 而 实 现 了 可 信的 多 方 间 的 信 息 共 享 和 监 督 ， 避 免 了 烦 琐 的 人 工 对账 ， 提 高 了 业 务 处 理 效 率 ， 降 低 了 交 易 成 本 。 LOGO区块链的核心特征 块链结构：每一块有时间戳，每一块都含有前面一块的散列加密信息，对每个交易进行验证。 多独立拷贝存储：区块链系统的每个节点都存储同样信息。 拜占庭容错：容忍少于1/3 节点恶意作弊或被黑客攻击，系统仍然能够正常工作。 LOGO区块链模式（1）模式1：、+ P2P + 挖矿。（2）模式2：、+ P2P + 挖矿 + 默克尔-帕特里夏树（Merkel Patricia tree） LOGO区块链体系架构 LOGO区块链应用（1）数字创意的助推器（2）万物互联的万物账簿（3）供应链端到端防伪（4）隐私数据保护的密码机（5）互联网新技术 LOGO 分 布 式 计 算 概 述 分 布 式 计 算 的 理 论 基 础 分 布 式 系 统 概 述 分 布 式 系 统 的 进 阶 典 型 的 分 布 式 系 统小 结 LOGO课内复习1分布式计算的定义和特征是什么？2什么是ACID原则？3什么是CAP理论？4什么是BASE理论？5如何理解最终一致性？6分布式存储与分布式计算的区别与联系是什么？ LOGO课外思考1在日常生活中，为什么我们所接触到的分布式系统越来越多了？2CAP定理中的几个关键因素为什么不能同时保证？不同的组合有什么样的应用场景？3通过了解区块链的背景，说说你所理解的区块链作为一种分布式系统背后的全新理念。 LOGO动手实践1Globus是一个开放源码的网格的基础平台，Globus Toolkit工具包是一个构筑网格计算环境的中间件，提供基本的资源定位、管理、通信和安全等服务。该计算工具包是模块化的，允许用户按自己的需要定制环境。利用这套工具可以建立计算网格，并可以进行网格应用的开发。任务：通过Globus Toolkit的官方网站下载并安装使用Globus Toolkit。 LOGO动手实践2HTCondor是一个专门用于计算密集型作业的负载管理系统，它为用户提供了作业排队机制、调度策略、优先计划、资源监测和资源管理，诞生于美国威斯康星大学麦迪逊分校。任务：通过HTCondor的官方网站下载并安装使用HTCondor，了解它是如何实现大吞吐量计算过程的。