云计算关键技术.ppt

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

1、云计算关键技术郑伟平2011-7-26Page 2虚拟化技术内容n1 虚拟化定义n2 虚拟化分类n3 全虚拟化与半虚拟化n4虚拟化实现n5虚拟化技术比较与选型n6虚拟化带来的好处n7虚拟化带来的问题n8虚拟化适用范围n9服务器虚拟化过程nMapReduce MapReduce是一个简单易用的并行编程模型，它极大简化了大规模数据处理问题的实现Page 3Divide and Conquer“Work”w1w2w3r1r2r3“Result”“worker”“worker”“worker”PartitionCombineParallelization ChallengesnHow do we as

2、sign work units to workers?nWhat if we have more work units than workers?nWhat if workers need to share partial results?nHow do we aggregate partial results?nHow do we know all the workers have finished?nWhat if workers die?What is the common theme of all of these problems?Common Theme?nParallelizat

3、ion problems arise from:nCommunication between workers(e.g.,to exchange state)nAccess to shared resources(e.g.,data)nThus,we need a synchronization mechanismManaging Multiple WorkersnDifficult becausenWe dont know the order in which workers runnWe dont know when workers interrupt each othernWe dont

4、know the order in which workers access shared datanThus,we need:nSemaphores(lock,unlock)nConditional variables(wait,notify,broadcast)nBarriersnStill,lots of problems:nDeadlock,livelock,race conditions.nDining philosophers,sleepy barbers,cigarette smokers.nMoral of the story:be careful!Current Toolsn

5、Programming modelsnShared memory(pthreads)nMessage passing(MPI)nDesign PatternsnMaster-slavesnProducer-consumer flowsnShared work queuesMessage PassingP1P2P3P4P5Shared MemoryP1P2P3P4P5Memorymasterslavesproducer consumerproducer consumerwork queueBut,now Mapreduce!nMapreduce:Parallel/Distributed Comp

6、uting Programming ModelInput split shuffle output Typical problem solved by MapReducen读入数据:key/value 对的记录格式数据nMap:从每个记录里extract somethingnmap(in_key,in_value)-list(out_key,intermediate_value)n处理input key/value pair n输出中间结果key/value pairsnShuffle:混排交换数据n把相同key的中间结果汇集到相同节点上nReduce:aggregate,summarize,

7、filter,etc.nreduce(out_key,list(intermediate_value)-list(out_value)n归并某一个key的所有values，进行计算n输出合并的计算结果(usually just one)n输出结果Mapreduce FrameworkMapreduce FrameworkShuffle ImplementationPartition and Sort Group Partition function:hash(key)%reducer numberGroup function:sort by keyExample uses:distribute

8、d grepdistributed sort web link-graph reversal term-vector/hostweb access log stats inverted index construction document clustering machine learning statistical machine translation.Model is Widely ApplicableMapReduce Programs In Google Source Tree Google MapReduce ArchitectureSingle Master nodeMany

9、worker beesMany worker beesMapReduce OperationInitial data splitinto 64MB blocksComputed,resultslocally storedM sends datalocation to R workersFinal output writtenMaster informed ofresult locationsExecution overview1.Input files are split into M pieces(16 to 64 MB)Many worker copies of the program a

10、re forked.2.One special copy,the master,assigns map and reduce tasks to idle slave workers3.Map workers read input splits,parse(key,value)pairs,apply the map function,create buffered output pairs.4.Buffered output pairs are periodically written to local disk,partitioned into R regions,locations of r

11、egions are passed back to the master.5.Master notifies reduce worker about locations.Worker uses remote procedure calls to read data from local disks of the map workers,sorts by intermediate keys to group same key records together.Execution overview cont6.Reduce worker passes key plus corresponding

12、set of all intermediate data to reduce function.The output of the reduce function is appended to the final output file.7.When all map and reduce tasks are completed the master wakes up the user program,which resumes the user code.Fault Tolerance:workers master保持一些数据结构。它为每个map和reduce任务存储它们的状态(空闲，工作中，

13、完成)，和worker机器(非空闲任务的机器)的标识。nMaster pings workers periodically.No response:worker marked as failed.nCompleted map tasks are reset to idle state,so that they can be restarted,because their results(local to failed worker)are lost.nCompleted reduce tasks do not need to be re-started(output stored in glo

14、bal file system).Reduce tasks are notified of the new map tasks,so they can read unread data from the new locations.Fault Tolerance:MasternMaster writes checkpointsnOnly one master,less chance of failurenIf master failes,MapReduce task aborts.Refinement:Redundant ExecutionnSlow workers significantly

15、 delay completion time nOther jobs consuming resources on machine nBad disks w/soft errors transfer data slowly nSolution:Near end of phase,spawn backup tasks nWhichever one finishes first wins nDramatically shortens job completion time Refinement:Locality OptimizationnMaster scheduling policy:nAsks

16、 GFS for locations of replicas of input file blocks nMap tasks typically split into 64MB(GFS block size)nMap tasks scheduled so GFS input block replica are on same machine or same rack nEffectnThousands of machines read input at local disk speed nWithout this,rack switches limit read rateRefinement:

17、Skipping Bad RecordsnMap/Reduce functions sometimes fail for particular inputs nBest solution is to debug&fixnNot always possible third-party source libraries nOn segmentation fault:nSend UDP packet to master from signal handler nInclude sequence number of record being processed nIf master sees two

18、failures for same record:nNext worker is told to skip the record nCompression of intermediate data nCombinern“Combiner”functions can run on same machine as a mappernCauses a mini-reduce phase to occur before the real reduce phase,to save bandwidthnLocal execution for debugging/testing nUser-defined

19、countersOther RefinementsHadoop MapReduce ArchitectureMaster/Worker ModelLoad-balancing by polling mechanismHistory of Hadoopn2004-Initial versions of what is now Hadoop Distributed File System and Map-Reduce implemented by Doug Cutting&Mike Cafarella nDecember 2005-Nutch ported to the new framework

20、.Hadoop runs reliably on 20 nodes.nJanuary 2006-Doug Cutting joins Yahoo!nFebruary 2006-Apache Hadoop project official started to support the standalone development of Map-Reduce and HDFS.nMarch 2006-Formation of the Yahoo!Hadoop team nMay 2006-Yahoo sets up a Hadoop research cluster-300 nodes nApri

21、l 2006-Sort benchmark run on 188 nodes in 47.9 hours nMay 2006-Sort benchmark run on 500 nodes in 42 hours(better hardware than April benchmark)nOctober 2006-Research cluster reaches 600 Nodes nDecember 2006-Sort times 20 nodes in 1.8 hrs,100 nodes in 3.3 hrs,500 nodes in 5.2 hrs,900 nodes in 7.8 nJ

22、anuary 2006-Research cluster reaches 900 node nApril 2007-Research clusters-2 clusters of 1000 nodes nSep 2008-Scaling Hadoop to 4000 nodes at Yahoo!nApril 2009 release 0.20.0,many improvements,new features,bug fixes and optimizations.分布式文件系统n分布式文件系统特点和基本要求缓存容错和可扩展性Page 28292022/11/18分布式文件系统的特点和基本要求

23、n分布式文件系统的特点 为整个网络上的文件系统资源提供了一个逻辑树结构，用户可以抛开文件的实际物理位置，仅通过一定的逻辑关系就可以查找和访问网络的共享资源。用户能够像访问本地文件一样，访问分布在网络中多个服务器上的文件。n分布式文件系统的顾客、服务员和存储设备分散在各机器上，服务活动必须跨网完成。n存储设备不是单一的集中数据存储器。n分布式文件系统的具体配置和实现可以有很大的不同，有的服务员运行在专用的服务器上，有的机器既是服务员又是顾客。302022/11/18分布式文件系统的特点和基本要求n分布式文件系统的基本要求n透明性n位置透明性：服务员和存储器的多重性和分散性对顾客透明。n移动透明性

24、：用户意识不到资源的移动。n性能透明性：当服务负载在一定范围内变化时，客户程序可以保持满意的性能。n扩展透明性：文件服务可以扩充，以满足负载和网络规模的增长。n性能分布式文件系统比常规文件系统类似（有时更好）的性能和可靠性312022/11/18n容错n为了处理暂时的通信错误，容错设计可以基于最多一次性语义n无状态的服务器:崩溃重启时不需恢复n安全性n身份验证，访问控制，安全通道n效率：应提供比传统文件系统相同或更强的性能和可靠性分布式文件系统的特点和基本要求322022/11/18分布式文件系统的缓存缓存方案的设计需要考虑的问题：n缓存的单位问题n存储部分文件的位置n如何决定各个顾客缓存中的

25、数据是否一致332022/11/18分布式文件系统的缓存n缓存的粒度和地点n缓存的粒度：如果数据单元(即粒度)愈大，则下次访问的数据在顾客方的本地找到的可能性愈大，但传送数据的时间和一致性问题也增加了。反之，粒度太小，通信的开销也随之增加。n缓存的地点在一个各自有主存和磁盘的客户-服务器系统中，有四个地方可以用来存储文件或存储部分文件：服务器磁盘、服务器主存、客户磁盘（如果可用的话）或者客户主存。342022/11/18分布式文件系统的缓存n更新策略、缓存有效性检验和一致性 判定本地缓存的数据副本是否与原本一致，有两个基本方法验证其有效性：n顾客发动的方法。顾客与服务员联系，检查本地数据与原本

26、是否一致。这个方法的关键是有效性检验的频度。n服务员发动的方法。服务员为每个顾客登记被该顾客缓存的文件或文件的某个部分。当服务员检测出可能不一致时，必须做出反应。服务员发动方法的一个问题是违背顾客/服务员模型352022/11/18容错和可扩充性n可用性与文件复制n可恢复性：当对某个文件的操作失败，或由顾客夭折此操作时，如果文件能转换到原来的一致状态，则说此文件是可恢复的。n坚定性：如果当某个存储器崩溃和存储介质损坏时某个文件能保证完好，则说此文件是坚定的。n可用性：如果无论何时一旦需要就可访问，甚至在某个机器和存储器崩溃，或者在发生通信失效的情况下，某个文件仍然可被访问，则这种文件叫做是可用

27、的。362022/11/18容错和可扩充性n可用性与文件复制n文件复制：文件复制是一个冗余措施。这里指的是不同机器上的文件复制，而不是同一机器上不同介质上的文件复制(如镜像磁盘)。n文件复制的原因n通过对每个文件的独立备份来增加系统的可靠性。n当一个文件服务器出现问题时，仍允许进行文件访问；n将工作量分配到多个服务器上，避免运行性能上的瓶颈。372022/11/18容错和可扩充性n可用性与文件复制 用户需要了解文件复制到何种程度吗？在文件复制进程中需要达到什么要求呢？n文件复制的要求：n应对用户隐匿复制细节。把一份复制件名字变换成指定的复制件是命名方案的任务。n与复制件有关的主要问题是它们的更

28、新。从用户观点看，文件的所有复制品代表同一逻辑实体，所以对任何复制件的更新必须反映到所有其他复制件。n大多数情况下，不能放弃文件数据的一致性，因此使用复制来增加可用性时还要使用复杂的更新传播协议。382022/11/18容错和可扩充性n可扩充性设计大规模系统要考虑的问题：n首先是有界资源(bounded resources)原理：“从系统的任何部分来的服务要求应该限于一个常数，此常数和系统中的节点数无关”。负载和系统规模成比例的任何服务员，一旦系统扩充到超过某一范围则必然阻塞，再增加资源也缓解不了这个问题。n广播是一种使网络中的每个机器都参加的活动。在广播基础上建立的机构对超大型系统很明显不实

29、际。n网络拥挤和延迟是大规模系统的主要障碍。使用缓存和实施放松的共享语义，使跨机器的交互作用最少。392022/11/18容错和可扩充性n可扩充性设计大规模系统要考虑的问题：n不应当使用集中控制方案和集中的资源建立可扩充的和容错的系统。n分散化的一个重要方面是系统的管理。分配管理职责时，应有利于自治性和对称性，不干扰分布式系统的连贯性和一致性。n将系统划分为若干半自治的小组。每个小组包括一些机器和一个专用的小组服务员。为了尽量减少跨越小组的文件访问，大多数时间，每个机器的请求应由其小组服务员满足。HDFS（Hadoop Distributed File System）nHadoop分布式文件系

30、统(HDFS)被设计成适合运行在通用硬件(commodity hardware)上的分布式文件系统。n它和现有的分布式文件系统有很多共同点。但同时，它和其他的分布式文件系统的区别也是很明显的。nHDFS是一个高度容错性高度容错性的系统，适合部署在廉价的机器上。nHDFS能提供高吞吐量高吞吐量的数据访问，适合大规模数据集上的应用。nHDFS放宽了一部分POSIX约束，来实现流式读取实现流式读取文件系统数据的目的。Page 40Goals of HDFSnVery Large Distributed File System 10K nodes,100 million files,10 PBn As

31、sumes Commodity Hardware Files are replicated to handle hardware failure Detect failures and recovers from themnOptimized for Batch Processing Data locations exposed so that computations can move to where data resides Provides very high aggregate bandwidthnUser Space,runs on heterogeneous OS nHDFS采用

32、master/slave架构。一个HDFS集群是由一个Namenode和一定数目的Datanodes组成。nNamenode是一个中心服务器，负责管理文件系统的名字空间(namespace)以及客户端对文件的访问。nNamenode执行文件系统的名字空间操作，比如打开、关闭、重命名文件或目录。它也负责确定数据块到具体Datanode节点的映射。n集群中的Datanode一般是一个节点一个，负责管理它所在节点上的存储。HDFS暴露了文件系统的名字空间，用户能够以文件的形式在上面存储数据。从内部看，一个文件其实被分成一个或多个数据块，这些块存储在一组 Datanode上。nDatanode负责处理

33、文件系统客户端的读写请求。在Namenode的统一调度下进行数据块的创建、删除和复制。Page 43Distributed File SystemnSingle Namespace for entire clusternData Coherency Write-once-read-many access model Client can only append to existing files nFiles are broken up into blocks Typically 128 MB block size Each block replicated on multiple DataN

34、odesnIntelligent Client Client can find location of blocks Client accesses data directly from DataNodeNameNode MetadatanMeta-data in Memory The entire metadata is in main memory No demand paging of meta-datanTypes of Metadata List of files List of Blocks for each file List of DataNodes for each bloc

35、k File attributes,e.g creation time,replication factornA Transaction Log Records file creations,file deletions.EtcnNamenode全权管理数据块的复制，它周期性地从集群中的每个Datanode接收心跳信号和块状态报告(Blockreport)。n集群中单一Namenode的结构大大简化了系统的架构。Namenode是所有HDFS元数据的仲裁者和管理者，这样，用户数据永远不会流过 Namenode。DataNodenA Block Server Stores data in the

36、 local file system(e.g.ext3)Stores meta-data of a block(e.g.CRC)Serves data and meta-data to ClientsnBlock Report Periodically sends a report of all existing blocks to the NameNodenFacilitates Pipelining of Data Forwards data to other specified DataNodesBlock PlacementnCurrent Strategy-One replica o

37、n local node-Second replica on a remote rack-Third replica on same remote rack-Additional replicas are randomly placednClients read from nearest replicanWould like to make this policy pluggablePage 48n在大多数情况下，副本系数是3nHDFS的存放策略是将一个副本存放在本地机架的节点上，一个副本放在同一机架的另一个节点上，最后一个副本放在不同机架的节点上。n这种策略减少了机架间的数据传输，这就提高了

38、写操作的效率。机架的错误远远比节点的错误少，所以这个策略不会影响到数据的可靠性和可用性。于此同时，因为数据块只放在两个（不是三个）不同的机架上，所以此策略减少了读取数据时需要的网络传输总带宽。在这种策略下，副本并不是均匀分布在不同的机架上。三分之一的副本在一个节点上，三分之二的副本在一个机架上，其他副本均匀分布在剩下的机架中，这一策略在不损害数据可靠性和读取性能的情况下改进了写的性能。Data CorrectnessnUse Checksums to validate data Use CRC32nFile Creation Client computes checksum per 512 b

39、yte DataNode stores the checksumnFile access Client retrieves the data and checksum from DataNode If Validation fails,Client tries other replicasNameNode FailurenA single point of failurenTransaction Log stored in multiple directories A directory on the local file system A directory on a remote file

40、 system(NFS/CIFS)Page 51HDFS未实现的功能总结：1、文件追加写入，这个功能近期内不会实现，没有这个功能会引起当文件尚未关闭的时候，数据服务器死机或者目录服务器死机，会引起文件文件丢失，并且不可后续恢复写入。2、系统快照，一个全系统的快照功能，如果没有这个功能就不能实现文件系统的回滚操作。3、集群负载均衡，均衡策略暂时没有实现，有几个策略十分有用，比如在某台数据机可能磁盘过低的时候，把该数据机上面的一些数据转移到还有很多空间剩余的数据机上；当某个文件突然被大量读写的时候，动态增加该文件的冗余因子，并且数据块复制到更多的数据机上面，以提高读取性能。4、文件系统的用户权限，

41、这个也是近期内不会实现的了。5、访问权限，现在是无限制访问的，没有访问权限控制。分布式数据库技术n定义n特点n分类n体系结构n分片与分布n模式结构n事务模型分布式数据库的定义n分布式数据库的定义通俗地说是物理上分散而逻辑上集中的数据库系统。使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一个统一的数据库系统。可以看作是数据处理即数据库系统和计算机网络技术的结合。n分布式数据库的特点物理分布性逻辑整体性，不同于分散式数据库，有全局数据库和局部数据库的概念。站点自治性：场地自治，各站点数据由本地DBMS管理，具有自治处理能力，完成本地应用。这一点与多机系统

42、不同。数据分布透明性：分片透明、数据复制透明、数据位置透明。集中与自治相结合的控制机制：局部共享和全局共享一定的数据冗余：可靠、可用，单个站点故障不会影响整体。不利于更新，维护成本高，查询速度快。事务管理的分布性：全局事务可以分解为若干子事务。事务的ACID特性受到考验。分布式数据库的特点n分布式数据库的12条准则本地自治性不依赖于中心站点可连续操作性位置独立性数据分片独立性数据复制独立性分布式查询处理分布式事务处理硬件独立性操作系统独立性网络独立性数据库管理系统独立性n单个DBMS的本地运算不受多数据库系统中其它DBMS的加入而影响。n单个DBMS处理查询和优化查询的方式不受访问多数据库的全

43、局查询执行的影响。n系统已执行或操作在单个DBMS加入或离开多数据库联盟时不受危害。n分布式数据库的分类按局部数据库管理系统的数据模型分类n同构型（homogenous）DDBS：数据模型相同同构同质型：各站点上的数据模型（关系、网状、层次）相同，且都是同一种DBMS。同构异质性：各站点上的数据模型（关系、网状、层次）相同，但不是同一种DBMS。n异构型（heterogenous）DDBS：各站点上的数据模型不同。分布式数据库的分类按分布式数据库系统的全局控制类型分类全局控制集中型DDBS：全局控制机制和全局数据字典位于一个中心点，中心点完成全局事务的协调和局部数据库的转换全局控制分散型DDB

44、S：全局控制机制和全局数据字典位于各个站点上，每个站点都能完成全局事务的协调和局部数据库的转换，每个站点既是全局事务的协调者，也是参与者。全局控制可变型DDBS：主从型DDBS，站点有两类：主站点和从站点，主战点上包含全局控制机制和全局数据字典；辅助站点不包含全局控制机制和全局数据字典分布式数据库系统的体系结构全局用户局部用户GDD GDBLDD LDBCMGDBMSLDBMS全局用户局部用户GDD GDBLDD LDBCMGDBMSLDBMS全局用户局部用户GDD GDBLDD LDBCMGDBMSLDBMS网络包括：n局部DB、全局DBn局部DBMS和全局DBMSn局部DBA和全局DBAn

45、局部数据字典LDD和全局数据字典GDDn通信模块CMn分片：又称为数据分割，有三种分片方式水平分片：按特定条件将全局关系划分成若干互不相交的片段。通过对全局关系进行选择运算得到。垂直分片：把全局关系的属性集分成若干子集。通过对全局关系进行投影运算获得。混合分片：上述两种方法的混合。n分片规则完备性条件：不多，即全局关系的所有数据必须映射到各个片段中，不允许有属于全局关系的数据不属于它的任何一个片段。可重构条件：不少，即必须保证能够由同一个全局关系的各个片段来重构该全局关系。水平：合并垂直：连接不相交条件：一个全局关系被分割后所得的各个数据片段不重叠。分布式数据库中的分片与分布n分布：根据需要将

46、数据划分成逻辑片段，按照某种策略将这些片段分散存储在各个站点上，策略：集中式：所有数据片段放在同一个站点上。对数据控制和管理容易数据一致性和完整性能够得到保证系统对数据站点依赖过重数据站点故障将导致整个系统崩溃检索效率低分割式：所有数据只有一份，经过逻辑分割后形成多个片段，每个片段放在某个特定的站点上。充分利用各个站点的存储能力每个站点可自治检索和修改数据，并发能力强部分站点故障，系统仍能运行，可靠性高全局查询和修改，响应时间长，网络通信代价较大n全复制式：全局数据有多个副本，每个站点上都有一个完整的数据副本。可靠性高查询速度快数据同步困难系统冗余大n混合式：全部数据被分为若干个子集，每个子集

47、安置在不同的站点上，但任一站点都不保存全部数据。灵活性好系统效率高复杂分布式数据库系统的模式结构全局DBMSDB局部内模式局部概念模式DB局部内模式局部概念模式局部DBMS分配模式分片模式全局概念模式全局外模式全局外模式全局外模式集中式数据库分布式数据库n全局外模式：全局应用的用户视图。n全局概念模式：描述分布式数据库中全局数据的逻辑结构和数据特性，是分布式数据库的全局概念视图。n分片模式：描述全局数据的逻辑划分。n分配模式：根据选定的数据分配策略，定义各片段的物理存放位置，确定是否冗余及冗余的程度。n局部概念模式：是全局概念模式的子集，由分配在同一站点上的一个或多个逻辑片段组成n局部内模式：

48、是分布式数据库关于物理数据库的描述，跟集中式内模式类似，但是不仅包含本站点数据的存储描述，还包括全局数据在本站点的存储描述全局关系R的逻辑片段与物理影像67n分布式事务模型n事务的ACIDn局部事务、全局事务n局部事务管理器保证本地节点上执行的事务的ACID本次事务可能是全局事务的一部分维护一个易于恢复的日志参与适当的并发控制n事务协调器协调该节点上发起的事务（全局或局部）的执行启动事务的执行分发事务协调事务的终止（在所有节点上提交或中止）分布式事务模型68TC1TCnTMnTM1事务管理器事务协调器69n故障n节点故障n消息丢失n网络故障n提交n原子性事务T必须要么在所有节点上提交，要么在所

49、有节点上都中止n两阶段提交n三阶段提交70两阶段提交阶段1（决定阶段）协调器 prepare T节点事务管理器 ready T 或 abort T阶段2（执行阶段）收到有一个abort T,则abort T收到所有ready T,则commit T节点commit T并写Log后，发出acknowledge T收到所有acknowledge，则complete T阻塞：协调器发出prepare T 后故障，处于不定状态双方针对超时均可重发71三阶段提交阶段1同两阶段方式阶段2收到有一个abort T,则abort T收到所有ready T,则precommit T节点precommit T之后

50、，写Log，发出acknowledge T阶段3收到所有ack，则commit T 节点commit 后，发出ack T收到所有ack T后，complete T恢复只要有一个具有commit T,则提交只要有一个precommit T,已ready T，可提交都没有收到precommit T，则回滚72n协议的比较n两阶段提交n有阻塞的可能，使用较广n三阶段提交n对于网络链路故障的处理能力偏弱HbasenHbase是一个分布式开源数据库，基于Hadoop分布式文件系统，模仿并提供了基于Google文件系统的Bigtable数据库的所有功能。为什么需要为什么需要HBASEn数据库系统已无法适应