大数据培训讲义

1、大数据培训讲义大数据培训讲义2013-6Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目录目录大数据起源Hadoop1.0Hadoop2.0商用环境Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 大数据起源大数据起源-Google-Google三篇三篇Google MapReduceGoogle MapReduceGoogleGoogle分布式分布式文件系统文件系统GFSGFSGoolgeGoolge分布式结构分布式结构化数据表化数据表BigTableBigTa

2、bleConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 三个层面上的基本构思如何对付大数据处理：分而治之对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略上升到抽象模型：Mapper与ReducerMPI等并行计算方法缺少高层并行编程模型，为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型上升到构架：统一构架，为程序员隐藏系统层细节MPI等并行计算方法缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢

3、复等诸多细节；为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 大数据分而治之大数据分而治之 大数据计算任务子任务子任务子任务子任务任务划分计算结果结果合并Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 建立建立Map和和Reduce抽象模型抽象模型典型的流式大数据问题的特征 大量数据记录/元素进行重复处理 对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息 排序和

4、整理中间结果以利后续处理 收集整理中间结果 产生最终结果输出MapReduce关键思想：为大数据处理过程中的两个主要处理阶段 提炼为一种抽象的操作机制Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 建立建立Map和和Reduce抽象模型抽象模型 借鉴函数式程序设计语言Lisp中的思想，定义了Map和Reduce两个抽象的操作函数：map: (k1; v1) (k2; v2)reduce: (k2; v2) (k3; v3)特点：特点：描述了对一组数据处理的两个阶段的抽象操作描述了对一组数据处理的两个阶段的抽象操作Confiden

5、tial and Proprietary BOCO Inter-Telecom Co.,Ltd. 上升到构架上升到构架-自动并行化并隐藏低层细节自动并行化并隐藏低层细节海量数据存储海量数据存储数据划分MapMapMapMap初始初始kv键值对键值对初始初始kv键值对键值对初始初始kv键值对键值对初始初始kv键值对键值对中 间 结 果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：Aggregation and ShuffleReduceReduceReduce(k1,

6、values)(k2,values)(k3,values)计算结果计算结果(K1,val)(K2,val)(K3,val)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Barrier(good, 1)(good, 1)(good,2)(good,1)PartitionerPartitionerPartitionerPartitioner(is, 1)(is, 1)(is, 1)(has, 1)(weather, 1)(weather, 1)(weather, 1)(the, 1) (today, 1)(today,1)上升到构

7、架上升到构架-自动并行化并隐藏低层细节自动并行化并隐藏低层细节海量数据存储计算结果计算结果数据划分Map初始初始kv键值对键值对初始初始kv键值对键值对初始初始kv键值对键值对初始初始kv键值对键值对MapMapMap中间结果中间结果(the, 1)(weather, 1)(is, 1)(good, 1)CombinerCombinerCombinerCombiner(the, 1)(weather, 1)(is, 1)(good, 1)(today, 1)(is, 1)(good, 1)(good, 1)(weather, 1)(is, 1)(good, 1)(today, 1)(has,

8、1)(good, 1)(weather, 1)(today, 1)(is, 1)(good, 1)(good, 2)(weather, 1)(is, 1)(today, 1)(has, 1)(good, 1)(weather, 1)ReduceReduceReduce(good, 5)(is, 3)(has, 1)(weather, 3)(the, 1) (today, 2)Combiner和PartitionerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行处理的基本过程并行处理的基本过程

9、 1.有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序2.系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行处理的基本过程并行处理的基本过程 3.用户作业程序提交给主节点4.主节点为作业程序寻找和配备可用的Map节点，并将程序传送给map节点 5.主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点 Confidential and

10、 Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行处理的基本过程并行处理的基本过程 6.主节点启动每个Map节点执行程序，每个map节点尽可能读取本地或本机架的数据进行计算 7.每个Map节点处理读取的数据块,并做一些数据整理工作(combining, sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置 Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行处理的基本过程并行处理的基本过程

11、 8.主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据9.Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行处理的基本过程并行处理的基本过程 完整计算过程Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 存储位置的计算策略存储位置的计算策略策略 MapReduce的master在调度M

12、ap任务时会考虑输入文件的位置信息，尽量将一个Map任务调度在包含相关输入数据拷贝的机器上执行；如果上述努力失败了，master将尝试在保存有输入数据拷贝的机器附近的机器上执行Map任务(例如，分配到一个和包含输入数据的机器在一个switch里的worker机器上执行)。当在一个足够大的cluster集群上运行大型MapReduce操作的时候，大部分的输入数据都能从本地机器读取，因此消耗非常少的网络带宽。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 失效处理失效处理主节点失效 主节点中会周期性地设置检查点(checkpoint

13、)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费。工作节点失效 工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送检测命令，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. CounterCounter MapReduce库使用计数器统计不同事件发生次数。比如，用户可能想统计已经处理了多少个单词、已经索引的多少篇文档。 这些计数器的值周期性的从

14、各个单独的worker机器上传递给master（附加在ping的应答包中传递）。master把执行成功的Map和Reduce任务的计数器值进行累计，当MapReduce操作完成之后，返回给用户代码Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 带宽优化带宽优化问题 大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销。解决方案 每个Map节点处理完成的中间键值队将由combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值。(good, 1)(weather, 1)(is, 1)(good,

15、 1)(good, 2)(weather, 1)(is, 1)combinerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 计算优化计算优化问题 Reduce节点必须要等到所有Map节点计算计算才能开始执行，因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。解决方案 把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果。根据Google的测试，使用了这个冗余Map节点计算方法以后，计算任务性能提高40%多！Confidential and Proprietary BO

16、CO Inter-Telecom Co.,Ltd. 用数据分区解决数据相关性问题用数据分区解决数据相关性问题问题 一个Reduce节点上的计算数据可能会来自多个Map节点，因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起。解决方案 在Map阶段进行了Combining以后，可以根据一定的策略对Map输出的中间结果进行分区(partitioning)，这样既可解决以上数据相关性问题避免Reduce计算过程中的数据通信。例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们

17、可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目录目录Google MapReduceGoogle MapReduce的基本工作原理的基本工作原理分布式文件系统分布式文件系统GFSGFS的基本工作原理的基本工作原理分布式结构化数据表分布式结构化数据表BigTableBigTableConfidential and Proprietary BOC

18、O Inter-Telecom Co.,Ltd. 基本问题基本问题海量数据怎么存储？数据存储可靠性怎么解决？当前主流的分布文件系统有： RedHat的GFS IBM的GPFS Sun的Lustre等主要用于对硬件设施要求很高的高性能计算或大型数据中心；价格昂贵且缺少完整的数据存储容错解决方案如Lustre只对元数据管理提供容错处理，但对于具体的分布存储节点，可靠性完全依赖于这些分布节点采用RAID或存储区域网(SAN)技术提供容错，一旦分布节点失效，数据就无法恢复。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google G

19、FS的的基本设计原则基本设计原则 Google GFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑； GFS是一个构建在分布节点本地文件系统之上的一个逻辑上文件系统，它将数据存储在物理上分布的每个节点上，但通过GFS将整个数据形成一个逻辑上整体的文件。Google GFSGoogle MapReduceMapReduce ApplicationsConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的的基本设计原则基本设计原则 廉价本地磁盘分布存储 各节点本

20、地分布式存储数据，优点是不需要采用价格较贵的集中式磁盘阵列，容量可随节点数增加自动增加 多数据自动备份解决可靠性 采用廉价的普通磁盘，把磁盘数据出错视为常态，用自动多数据备份存储解决数据存储可靠性问题 为上层的MapReduce计算框架提供支撑 GFS作为向上层MapReduce执行框架的底层数据存储支撑，负责处理所有的数据自动存储和容错处理，因而上层框架不需要考虑低层的数据存储和数据容错问题Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的基本构架和工作原理的基本构架和工作原理 Cite from Ghem

21、awat et al. (SOSP 2003)GFS MasterChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理GFS MasterMaster上保存了GFS文件系统的三种元数据 ： 命名空间(Name Space),即整个 分布式文件系统的目录结构 Chunk与文件名的映射表 Chunk副本的位置信息，每一个Chunk默认有3个副本GFS Master前两种元数据可通过操作日志提供容错处理能力；第3个元数据直接保存在ChunkServer上， Master 启动或

22、Chunk Server注册时自动完成在Chunk Server上元数据的生成；因此，当Master失效时，只要ChunkServer数据保存完好，可迅速恢复Master上的元数据。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理GFS ChunkServer 即用来保存大量实际数据的数据服务器。 GFS中每个数据块划分缺省为64MB 每个数据块会分别在3个(缺省情况下)不同的地方复制副本； 对每一个数据块，仅当3个副本都更新成功时，才认为数据保存成功。当某个副本失效时，Master会自动

23、将正确的副本数据进行复制以保证足够的副本数 GFS上存储的数据块副本，在物理上以一个本地的Linux操作系统的文件形式存储，每一个数据块再划分为64KB的子块，每个子快有一个32位的校验和，读数据时会检查校验和以保证使用为失效的数据。ChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk位置信息位置信息 Master服务器并不保存持久化保存哪个Chunk服务器存有指定Chunk的副本的信息。Master服务器只是在启动的时候轮询Chunk服务器以获取这些信息。Ma

24、ster服务器能够保证它持有的信息始终是最新的，因 为它控制了所有的Chunk位置的分配，而且通过周期性的心跳信息监控Chunk服务器的状态。ChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理数据访问工作过程1.在程序运行前，数据已经存储在GFS文件系统中；程序实行时应用程序会告诉GFS Server所要访问的文件名或者数据块索引是什么Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的

25、工作原理的工作原理数据访问工作过程2.GFS Server根据文件名会数据块索引在其文件目录空间中查找和定位该文件或数据块，并找数据块在具体哪些ChunkServer上；将这些位置信息回送给应用程序Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理数据访问工作过程3.应用程序根据GFSServer返回的具体Chunk数据块位置信息，直接访问相应的Chunk ServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Googl

26、e GFS的工作原理的工作原理数据访问工作过程4.应用程序根据GFSServer返回的具体Chunk数据块位置信息直接读取指定位置的数据进行计算处理Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理数据访问工作过程特点：应用程序访问具体数据时部需要经过GFS Master，因此，避免了Master成为访问瓶颈并发访问：由于一个大数据会存储在不同的ChunkServer中，应用程序可实现并发访问Confidential and Proprietary BOCO Inter-Telecom Co

27、.,Ltd. Google GFS的工作原理的工作原理GFS租约租约机制机制 设计租约机制的目的是为了最小化Master节点的管理负担。租约的初始超时设置为60秒。不过，只要Chunk被修改了，主Chunk就可以申请更长的租期，通常会得到Master节点的确认并收到租约延长的时间。这些租约延长请求和批准的信息通常都是附加在Master节点和Chunk服务器之间的心跳消息中来传递。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理数据流数据流 为了提高网络效率，GFS采取了把数据流和控制流分开

28、的措施。在控制流从客户机到主Chunk、然后再到 所有二级副本的同时，数据以管道的方式，顺序的沿着一个精心选择的Chunk服务器链推送。我们的目标是充分利用每台机器的带宽，避免网络瓶颈和高延时的连接，最小化推送所有数据的延时。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理数据完整性数据完整性 GFS把每个Chunk都分成64KB大小的块。每个块都对应一个32位的Checksum。和其它元数据一样，Checksum与其它的用户数据是分开的，并且保存在内存和硬盘上，同时也记录操作日志。对于读

29、操作来说，在把数据返回给客户端或者其它的Chunk服务器之前，Chunk服务器会校验读取操作涉及的范围内的块的Checksum。因此Chunk服务器不会把错误数据传递到其它的机器上。如果发生某个块的Checksum不正确，Chunk服务器返回给请求者一个错误信息，并且通知Master服务器这个错误。作为回应，请求者应当从其它副本读取数据，Master服务器也会从其它副本克隆数据进行恢复。当一个新的副本就绪后，Master服务器通知副本错误的Chunk服务器删掉错误的副本。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Googl

30、e GFS的工作原理的工作原理Chunk副本的副本的3种机制种机制 创建： 当Master节点创建一个Chunk时，它会选择在哪里放置初始的空的副本。Master节点会考虑几个因素。（1）GFS希望在低于平均硬盘使用率的Chunk服务器上存储新的副本。这样的做法最终能够平衡Chunk服务器之间的硬盘使用率。（2）GFS希望限制在每个Chunk服务器上”最近”的Chunk创建操作的次数。虽然创建操作本身是廉价的，但是创建操作也意味着随之会有大量的写入数据的操作，因为Chunk在Writer真正写入数据的时候才被创建，而在我们的”追加一次，读取多次”的工作模式下，Chunk一旦写入成功之后就会变为

31、只读的了。（3）GFS希望把Chunk的副本分布在多个机架之间。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk副本的副本的3种机制种机制 重新复制： 当Chunk的有效副本数量少于用户指定的复制因数的时候，Master节点会重新复制它。这可能是由几个原因引起的：一个Chunk服务器不可用了，Chunk服务器报告它所存储的一个副本损坏了，Chunk服务器的一个磁盘因为错误不可用了，或者Chunk副本的复制因数提高了。每个需要被重新复制的Chunk都会根据几个因素进行排序。一个因素

32、是Chunk现有副本数量和复制因数相差多少。例如，丢失两个副本的Chunk比丢失一个副本的Chunk有更高的优先级。另外，GFS优先重新复制活跃（live）文件的Chunk而不是最近刚被删除的文件的Chunk。最后，为了最小化失效的Chunk对正在运行的应用程序的影响，我们提高会阻塞客户机程序处理流程的Chunk的优先级。 Master节点选择优先级最高的Chunk，然后命令某个Chunk服务器直接从可用的副本”克隆”一个副本出来。选择新副本的位置的策略和创建时类似：平衡硬盘使用率、限制同一台Chunk服务器上的正在进行的克隆操作的数量、在机架间分布副本。为了防止克隆产生的网络流量大大超过客户

33、机的流量，Master节点对整个集群和每个Chunk服务器上的同时进行的克隆操作的数量都进行了限制。另外，Chunk服务器通过调节它对源Chunk服务器读请求的频率来限制它用于克隆操作的带宽。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk副本的副本的3种机制种机制 重新负载均衡： 最后，Master服务器周期性地对副本进行重新负载均衡：它检查当前的副本分布情况，然后移动副本以便更好的利用硬盘空间、更有效的进行负载均衡。而且在这个过程中，Master服务器逐渐的填满一个新的Chu

34、nk服务器，而不是在短时间内用新的Chunk填满它，以至于过载。新副本的存储位置选择策略和上面讨论的相同。另外，Master节点必须选择哪个副本要被移走。通常情况，Master节点移走那些剩余空间低于平均值的Chunk服务器上的副本，从而平衡系统整体的硬盘使用率。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理 过期过期失效的副本失效的副本检测检测 当Chunk服务器失效时，Chunk的副本有可能因错失了一些修改操作而过期失效。Master节点保存了每个Chunk的版本号，用来区分当前的副

35、本和过期副本。无论何时，只要Master节点和Chunk签订一个新的租约，它就增加Chunk的版本号，然后通知最新的副本。Master节点和这些副本都把新的版本号记录在它们持久化存储的状态信息中。这个动作发生在任何客户机得到通知以前，因此也是对这个Chunk开始写之前。如果某个副本所在的Chunk服务器正好处于失效状态，那么副本的版本号就不会被增加。Master节点在这个Chunk服务器重新启动，并且向Master节点报告它拥有的Chunk的集合以及相应的版本号的时候，就会检测出它包含过期的Chunk。如果Master节点看到一个比它记录的版本号更高的版本号，Master节点会认为它和Chun

36、k服务器签订租约的操作失败了，因此会选择更高的版本号作为当前的版本号。 Master节点在例行的垃圾回收过程中移除所有的过期失效副本。在此之前，Master节点在回复客户机的Chunk信息请求的时候，简单的认为那些过期的块根本就不存在。另外一重保障措施是，Master节点在通知客户机哪个Chunk服务器持有租约、或者指示Chunk服务器从哪个Chunk服务器进行克隆时，消息中都附带了Chunk的版本号。客户机或者Chunk服务器在执行操作时都会验证版本号以确保总是访问当前版本的数据。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd.

37、 Google GFS的基本构架和工作原理的基本构架和工作原理GFS的系统管理技术 大规模集群安装技术：如何在一个成千上万个节点的集群上迅速部署GFS，升级管理和维护等 故障检测技术：GFS是构建在不可靠的廉价计算机之上的文件系统，节点数多，故障频繁，如何快速检测、定位、恢复或隔离故障节点 节点动态加入技术：当新的节点加入时，需要能自动安装和部署GFS 节能技术：服务器的耗电成本大于购买成本，Google为每个节点服务器配置了蓄电池替代UPS，大大节省了能耗。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目录目录Google

38、MapReduceGoogle MapReduceGoogleGoogle分布式分布式文件系统文件系统GFSGFSGoogleGoogle分布式结构分布式结构化数据表化数据表BigTableBigTableConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable的基本作用和设计思想的基本作用和设计思想 GFS是一个文件系统，难以提供对结构化数据的存储和访问管理。为此，Google在GFS之上又设计了一个结构化数据存储和访问管理系统BigTable，为应用程序提供比单纯的文件系统更方便、更高层的数据操作能力 Google的

39、很多数据，包括Web索引、卫星图像数据、地图数据等都以结构化形式存放在BigTable中 BigTable提供了一定粒度的结构化数据操作能力，主要解决一些大型媒体数据（Web文档、图片等）的结构化存储问题。但与传统的关系数据库相比，其结构化粒度没有那么高，也没有事务处理等能力，因此，它并不是真正意义上的数据库。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable设计动机和目标设计动机和目标主要动机需要存储多种数据Google提供的服务很多，序处理的数据类型也很多，如URL,网页,图片,地图数据,email,用户的个性

40、化设置等海量的服务请求 Google是目前世界上最繁忙的系统，因此，需要有高性能的请求和数据处理能力商用数据库无法适用 在如此庞大的分布集群上难以有效部署商用数据库系统，且其难以承受如此巨量的数据存储和操作需求Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable设计动机和目标设计动机和目标主要设计目标广泛的适用性:为一系列服务和应用而设计的数据存储系统,可满足对不同类型数据的存储和操作需求很强的可扩展性:根据需要可随时自动加入或撤销服务器节点高吞吐量数据访问:提供P级数据存储能力，每秒数百万次的访问请求高可用性和容错

41、性:保证系统在各种情况下度能正常运转，服务不中断自动管理能力：自动加入和撤销服务器，自动负载平衡简单性：系统设计尽量简单以减少复杂性和出错率Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable数据模型数据模型lBigTable主要是一个分布式多维表，表中的数据通过：l一个行关键字(row key)l一个列关键字(column key)l一个时间戳(time stamp) 进行索引和查询定位的。lBigTable对存储在表中的数据不做任何解释，一律视为字符串，具体数据结构的实现有用户自行定义。lBigTable查询模型

42、 (row:string, column:string,time:int64) 结果数据字符串l支持查询、插入和删除操作Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable数据模型数据模型BigTable数据存储格式l行(Row):大小不超过64KB的任意字符串。表中的数据都是根据行关键字进行排序的。 n.www就是一个行关键字，指明一行存储数据。URL地址倒排好处是：1)同一地址的网页将被存储在表中连续的位置,便于查找；2)倒排便于数据压缩,可大幅提高数据压缩率l子表(Tablet)：一个大表可能太大，不利于存储管

43、理，将在水平方向上被分为多个子表Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable数据模型数据模型BigTable数据存储格式l列(Column): BigTable将列关键字组织成为“列族”(column family),每个族中的数据属于同一类别,如anchor时一个列族，其下可有不同的表示一个个超链的列关键字。一个列族下的数据会被压缩在一起存放。因此,一个列关键字可表示为: 族名：列名(family:qualifier) content、anchor都是族名；而和my.look.ca则是anchor族中的列名

44、。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable数据模型数据模型BigTable数据存储格式l时间戳(time stamp): 很多时候同一个URL的网页会不断更新，而Google需要保存不同时间的网页数据，因此需要使用时间戳来加以区分。l为了简化不同版本的数据管理，BigTable提供给了两种设置：l保留最近的n个版本数据l保留限定时间内的所有不同版本数据Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架BigTa

45、ble主服务器BigTable客户端BigTable客户端程序库BigTable子表服务器BigTable子表服务器BigTable子表服务器BigTable子表服务器执行元数据操作和负载平衡数据存储和访问操作数据存储和访问操作数据存储和访问操作数据存储和访问操作GFSChubby服务器（分布式锁服务）GoogleWorkQueue负责故障监控和处理子表数据的存储及日志元数据存储及主服务器选择Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架主服务器l新子表分配：当一个新子表产 生时，主服务器通过加

46、载命令 将其分配给一个空间足够大的 子表服务；创建新表、表合并 及较大子表的分裂都会产生新 的子表。l子表监控：通过Chubby完成。所有子表服务器基本信息被保存在Chubby中的服务器目录中主服务器检测这个目录可获取最新子表服务器的状态信息。当子表服务器出现故障，主服务器将终止该子表服务器，并将其上的全部子表数据移动到其它子表服务器。l负债均衡：当主服务器发现某个子表服务器负载过重时，将对自动对其进行负载均衡操作。主服务器新子表分配子表服务器间的负载均衡子表服务器状态监控Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigT

47、able基本构架基本构架子表服务器BigTable中的数据都以子表形式保存在子表服务器上，客户端程序也直接和子表服务器通信。分配：当一个新子表产子表服务器的主要问题包括子表的定位、分配、及子表数据的最终存储。l子表的基本存储结构SSTable SSTable是BigTable内部的基本存储结构，以GFS文件形式存储在GFS文件系统中。一个SSTable实际上对应于GFS中的一个64MB的数据块(Chunk) SSTable中的数据进一步划分为64KB的子块，因此一个SSTable可以有多达1千个这样的子块。为了维护这些子块的位置信息，需要使用一个Index索引。Index64K block64

48、K block64K blockSSTableConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架子表服务器l子表数据格式 概念上子表是整个大表的多行数据划分后构成。而一个子表服务器上的子表将进一步由很多个SSTAble构成，每个SSTable构成最终的在底层GFS中的存储单位。Index64K block64K block64K blockSSTableIndex64K block64K block64K blockSSTableTabletStart:aardvarkEnd:appleConfid

49、ential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架子表服务器l子表数据格式 一个SSTable还可以为不同的子表所共享，以避免同样数据的重复存储。 SSTableSSTableSSTableSSTableTabletaardvarkappleTabletapple_two_EboatConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架子表服务器l子表寻址 子表地址以3级B+树形式进行索引；首先从Chubby 服务器中取

50、得根子表，由根子表找到二级索引 指标，最后获取最终的 SSTable的位置 Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架子表服务器lMinor Compaction 随着写操作的执行，memtable的大小不断增加。当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一个新的memtable；被冻结住memtable会被转换成SSTable，然后写入GFS。Confidential and Proprietary BOCO Inter-Telecom Co.,

51、Ltd. BigTable基本构架基本构架子表服务器lMerging Compaction 每一次Minor Compaction都会创建一个新的SSTable。通过定期在后台执行Merging Compaction过程合并文件，限制这类文件的数量。Merging Compaction过程读取一些SSTable和memtable的内容，合并成一个新的SSTable。lMajor Compaction Major Compaction过程生成的SSTable不包含已经删除的信息或数据。Bigtable循环扫描它所有的Tablet，并且定期对它们执行Major Compaction。Major C

52、ompaction机制允许Bigtable回收已经删除的数据占有的资源，并且确保BigTable能及时清除已经删除的数据。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架优化l压缩 每个SSTable的块（块的大小由局部性群组的优化参数定）都使用用户指定的压缩格式来压缩。虽然分块 压缩浪费了少量空间（相比于对整个SSTable进行压缩，分块压缩压缩率较低），但是，在只读取SSTable的一小部分数据的时候就不必解压整个文件了。使用了“两遍”的、可定制的压缩方式。第一遍采用Bentley and M

53、cIlroys方式，这种方式在一个很大的扫描窗口里对常见的长字符串进行压缩；第二遍是采用快速压缩算法，即在一个16KB的小扫描窗口中寻找重复数据。两个压缩的算法都很快，在现在的机器上，压缩的速率达到100-200MB/s，解压的速率达到400-1000MB/s。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架优化lBloom filter 一个读操作必须读取构成Tablet状态的所有SSTable的数据。如果这些SSTable不在内存中，那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组

54、的SSTable指定Bloom过滤器，来减少硬盘访问的次数。我们可以使用Bloom过滤器查询一个SSTable是否包含了特定行和列的数据。对于某些特定应用程序，我们只付出了少量的、用于存储Bloom过滤器的内存的代价，就换来了读操作显著减少的磁盘访问的次数。使用Bloom过滤器也隐式的达到了当应用程序访问不存在的行或列时，大多数时候我们都不需要访问硬盘的目的。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架Bloom filterl原理如需要判断一个元素是不是在一个集合中，我们通常做法是把所有元素

55、保存下来，然后通过比较知道它是不是在集合内，链表、树都是基于这种思路，当集合内元素个数的变大，我们需要的空间和时间都线性变大，检索速度也越来越慢。 Bloom filter 采用的是哈希函数的方法，将一个元素映射到一个 m 长度的阵列上的一个点，当这个点是 1 时，那么这个元素在集合内，反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突，解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不在集合内。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。Confidential and P

56、roprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本构架基本构架Bloom filter为了表达S=x1, x2,xn这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到1,m的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1ik）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果

57、所有hi(y)的位置都是1（1ik），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目录目录大数据起源Hadoop1.0Hadoop2.0商用环境Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. hadoopHadoop是一个开源的软件框架，它支持数据密集型的分布式应用，许可授权隶属于Apache v2 li

58、cense.可以在成千上万台独立的计算机上运行。Hadoop源自于Google的MapReduce 和 Google File System (GFS) 两篇论文。现在通常认为完整的Apache Hadoop平台由Hadoop内核、MapReduce 和HDFS组成，以及若干相关的项目包括Apache Hive 、Apache Hbase等等Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. HDFS基本构架基本构架对等于GFS Master对等于GFS ChunkServer应用程序HDFS客户端客户端文件名或数据块号数据块号，数

59、据块位置HDFS NameNodeDataNode数据DataNode数据DataNode数据Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop MapReduce基本构架与工作过程基本构架与工作过程对等于Google MapReduce 中的Master对等于Google MapReduce 中的WorkerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. datanode daemonLinux file systemtasktrackerslave

60、nodedatanode daemonLinux file systemtasktrackerslave nodedatanode daemonLinux file systemtasktrackerslave nodenamenodenamenode daemonjob submission nodejobtrackerHadoop MapReduce和和HDFS数据存储与计算节点构架Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop 1.0Hadoop 1.0X86 PC集群本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘数据节点Datanod