大数据培训讲解

大数据培训讲义2013-6大数据培训讲解大数据培训讲义2013-6大数据培训讲解1目录大数据起源Hadoop1.0Hadoop2.0商用环境大数据培训讲解目录大数据起源Hadoop1.0Hadoop2.0商用环境大2大数据起源-Google三篇GoogleMapReduceGoogle分布式文件系统GFSGoolge分布式结构化数据表BigTable大数据培训讲解大数据起源-Google三篇GoogleMapReduce3三个层面上的基本构思如何对付大数据处理：分而治之

对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略上升到抽象模型：Mapper与Reducer

MPI等并行计算方法缺少高层并行编程模型，为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型上升到构架：统一构架，为程序员隐藏系统层细节

MPI等并行计算方法缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢复等诸多细节；为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节GoogleMapReduce的基本模型和处理思想大数据培训讲解三个层面上的基本构思GoogleMapReduce的基本模4GoogleMapReduce的基本模型和处理思想大数据分而治之

大数据计算任务子任务子任务子任务子任务……任务划分计算结果结果合并大数据培训讲解GoogleMapReduce的基本模型和处理思想大数据分5建立Map和Reduce抽象模型典型的流式大数据问题的特征大量数据记录/元素进行重复处理对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息排序和整理中间结果以利后续处理收集整理中间结果产生最终结果输出MapReduce关键思想：为大数据处理过程中的两个主要处理阶段

提炼为一种抽象的操作机制GoogleMapReduce的基本模型和处理思想大数据培训讲解建立Map和Reduce抽象模型MapReduce关键思想：6建立Map和Reduce抽象模型借鉴函数式程序设计语言Lisp中的思想，定义了Map和Reduce两个抽象的操作函数：map:(k1;v1)

[(k2;v2)]reduce:

(k2;[v2])

[(k3;v3)]特点：描述了对一组数据处理的两个阶段的抽象操作GoogleMapReduce的基本模型和处理思想大数据培训讲解建立Map和Reduce抽象模型GoogleMapRedu7上升到构架--自动并行化并隐藏低层细节海量数据存储……数据划分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：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)计算结果(K1,val)(K2,val)(K3,val)GoogleMapReduce的基本模型和处理思想大数据培训讲解上升到构架--自动并行化并隐藏低层细节海量数据存储……数据划8Barrier(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)上升到构架--自动并行化并隐藏低层细节海量数据存储计算结果……数据划分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,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和PartitionerGoogleMapReduce的基本模型和处理思想大数据培训讲解Barrier(good,1)PartitionerPar9GoogleMapReduce并行处理的基本过程

1.有一个待处理的大数据，被划分为大小相同的数据块(如64MB),与与此相应的用户作业程序2.系统中有一个负责调度的主节点(Master),以与数据Map和Reduce工作节点(Worker)GoogleMapReduce的基本模型和处理思想大数据培训讲解GoogleMapReduce并行处理的基本过程1.有一个10GoogleMapReduce并行处理的基本过程

3.用户作业程序提交给主节点4.主节点为作业程序寻找和配备可用的Map节点，并将程序传送给map节点5.主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点GoogleMapReduce的基本模型和处理思想大数据培训讲解GoogleMapReduce并行处理的基本过程3.用户作11GoogleMapReduce并行处理的基本过程

6.主节点启动每个Map节点执行程序，每个map节点尽可能读取本地或本机架的数据进行计算7.每个Map节点处理读取的数据块,并做一些数据整理工作(combining,sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置GoogleMapReduce的基本模型和处理思想大数据培训讲解GoogleMapReduce并行处理的基本过程6.主节点12GoogleMapReduce并行处理的基本过程

8.主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据9.Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果GoogleMapReduce的基本模型和处理思想大数据培训讲解GoogleMapReduce并行处理的基本过程8.主节点13GoogleMapReduce并行处理的基本过程

完整计算过程GoogleMapReduce的基本模型和处理思想大数据培训讲解GoogleMapReduce并行处理的基本过程完整计算过14存储位置的计算策略策略

MapReduce的master在调度Map任务时会考虑输入文件的位置信息，尽量将一个Map任务调度在包含相关输入数据拷贝的机器上执行；如果上述努力失败了，master将尝试在保存有输入数据拷贝的机器附近的机器上执行Map任务(例如，分配到一个和包含输入数据的机器在一个switch里的worker机器上执行)。当在一个足够大的cluster集群上运行大型MapReduce操作的时候，大部分的输入数据都能从本地机器读取，因此消耗非常少的网络带宽。。GoogleMapReduce的基本模型和处理思想大数据培训讲解存储位置的计算策略GoogleMapReduce的基本模型15失效处理主节点失效主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费。工作节点失效工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送检测命令，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行GoogleMapReduce的基本模型和处理思想大数据培训讲解失效处理GoogleMapReduce的基本模型和处理思想16CounterMapReduce库使用计数器统计不同事件发生次数。比如，用户可能想统计已经处理了多少个单词、已经索引的多少篇文档。这些计数器的值周期性的从各个单独的worker机器上传递给master（附加在ping的应答包中传递）。master把执行成功的Map和Reduce任务的计数器值进行累计，当MapReduce操作完成之后，返回给用户代码GoogleMapReduce的基本模型和处理思想大数据培训讲解CounterGoogleMapReduce的基本模型和处17

带宽优化问题

大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销。解决方案每个Map节点处理完成的中间键值队将由combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值。(good,1)(weather,1)(is,1)(good,1)(good,2)(weather,1)(is,1)combinerGoogleMapReduce的基本模型和处理思想大数据培训讲解带宽优化(good,1)(good,2)combi18

计算优化问题Reduce节点必须要等到所有Map节点计算计算才能开始执行，因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。解决方案把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果。根据Google的测试，使用了这个冗余Map节点计算方法以后，计算任务性能提高40%多！GoogleMapReduce的基本模型和处理思想大数据培训讲解计算优化根据Google的测试，使用了这个冗余Map节点计算19

用数据分区解决数据相关性问题问题

一个Reduce节点上的计算数据可能会来自多个Map节点，因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起。解决方案在Map阶段进行了Combining以后，可以根据一定的策略对Map输出的中间结果进行分区(partitioning)，这样既可解决以上数据相关性问题避免Reduce计算过程中的数据通信。例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果GoogleMapReduce的基本模型和处理思想大数据培训讲解用数据分区解决数据相关性问题例如：有一个巨大的数组,其最终结20目录GoogleMapReduce的基本工作原理分布式文件系统GFS的基本工作原理分布式结构化数据表BigTable大数据培训讲解目录GoogleMapReduce的基本工作原理分布式文件21基本问题海量数据怎么存储？数据存储可靠性怎么解决？当前主流的分布文件系统有：RedHat的GFSIBM的GPFSSun的Lustre等主要用于对硬件设施要求很高的高性能计算或大型数据中心；价格昂贵且缺少完整的数据存储容错解决方案如Lustre只对元数据管理提供容错处理，但对于具体的分布存储节点，可靠性完全依赖于这些分布节点采用RAID或存储区域网(SAN)技术提供容错，一旦分布节点失效，数据就无法恢复。GoogleGFS文件系统大数据培训讲解基本问题GoogleGFS文件系统大数据培训讲解22GoogleGFS的基本设计原则GoogleGFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑；GFS是一个构建在分布节点本地文件系统之上的一个逻辑上文件系统，它将数据存储在物理上分布的每个节点上，但通过GFS将整个数据形成一个逻辑上整体的文件。……GoogleGFSGoogleMapReduceMapReduceApplicationsGoogleGFS文件系统大数据培训讲解GoogleGFS的基本设计原则……GoogleGFSG23GoogleGFS的基本设计原则廉价本地磁盘分布存储

各节点本地分布式存储数据，优点是不需要采用价格较贵的集中式磁盘阵列，容量可随节点数增加自动增加多数据自动备份解决可靠性

采用廉价的普通磁盘，把磁盘数据出错视为常态，用自动多数据备份存储解决数据存储可靠性问题为上层的MapReduce计算框架提供支撑GFS作为向上层MapReduce执行框架的底层数据存储支撑，负责处理所有的数据自动存储和容错处理，因而上层框架不需要考虑低层的数据存储和数据容错问题GoogleGFS文件系统大数据培训讲解GoogleGFS的基本设计原则GoogleGFS文件系24GoogleGFS的基本构架和工作原理

CitefromGhemawatetal.(SOSP2003)GFSMasterChunkServerGoogleGFS文件系统大数据培训讲解GoogleGFS的基本构架和工作原理Citefrom25GoogleGFS的工作原理GFSMasterMaster上保存了GFS文件系统的三种元数据

：命名空间(NameSpace),即整个分布式文件系统的目录结构

Chunk与文件名的映射表Chunk副本的位置信息，每一个Chunk默认有3个副本GFSMaster前两种元数据可通过操作日志提供容错处理能力；第3个元数据直接保存在ChunkServer上，Master启动或ChunkServer注册时自动完成在ChunkServer上元数据的生成；因此，当Master失效时，只要ChunkServer数据保存完好，可迅速恢复Master上的元数据。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GFSMaster前两种元数26GoogleGFS的工作原理GFSChunkServer即用来保存大量实际数据的数据服务器。GFS中每个数据块划分缺省为64MB每个数据块会分别在3个(缺省情况下)不同的地方复制副本；对每一个数据块，仅当3个副本都更新成功时，才认为数据保存成功。当某个副本失效时，Master会自动将正确的副本数据进行复制以保证足够的副本数GFS上存储的数据块副本，在物理上以一个本地的Linux操作系统的文件形式存储，每一个数据块再划分为64KB的子块，每个子快有一个32位的校验和，读数据时会检查校验和以保证使用为失效的数据。ChunkServerGoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理当某个副本失效时，Master27GoogleGFS的工作原理Chunk位置信息Master服务器并不保存持久化保存哪个Chunk服务器存有指定Chunk的副本的信息。Master服务器只是在启动的时候轮询Chunk服务器以获取这些信息。Master服务器能够保证它持有的信息始终是最新的，因为它控制了所有的Chunk位置的分配，而且通过周期性的心跳信息监控Chunk服务器的状态。ChunkServerGoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理ChunkServerGoog28GoogleGFS的工作原理数据访问工作过程1.在程序运行前，数据已经存储在GFS文件系统中；程序实行时应用程序会告诉GFSServer所要访问的文件名或者数据块索引是什么GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理1.在程序运行前，数据已经存储29GoogleGFS的工作原理数据访问工作过程2.GFSServer根据文件名会数据块索引在其文件目录空间中查找和定位该文件或数据块，并找数据块在具体哪些ChunkServer上；将这些位置信息回送给应用程序GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理2.GFSServer根据文30GoogleGFS的工作原理数据访问工作过程3.应用程序根据GFSServer返回的具体Chunk数据块位置信息，直接访问相应的ChunkServerGoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理3.应用程序根据GFSServ31GoogleGFS的工作原理数据访问工作过程4.应用程序根据GFSServer返回的具体Chunk数据块位置信息直接读取指定位置的数据进行计算处理GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理4.应用程序根据GFSServ32GoogleGFS的工作原理数据访问工作过程特点：应用程序访问具体数据时部需要经过GFSMaster，因此，避免了Master成为访问瓶颈并发访问：由于一个大数据会存储在不同的ChunkServer中，应用程序可实现并发访问GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理特点：应用程序访问具体数据时部33GoogleGFS的工作原理GFS租约机制设计租约机制的目的是为了最小化Master节点的管理负担。租约的初始超时设置为60秒。不过，只要Chunk被修改了，主Chunk就可以申请更长的租期，通常会得到Master节点的确认并收到租约延长的时间。这些租约延长请求和批准的信息通常都是附加在Master节点和Chunk服务器之间的心跳消息中来传递。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大34GoogleGFS的工作原理数据流为了提高网络效率，GFS采取了把数据流和控制流分开的措施。在控制流从客户机到主Chunk、然后再到所有二级副本的同时，数据以管道的方式，顺序的沿着一个精心选择的Chunk服务器链推送。我们的目标是充分利用每台机器的带宽，避免网络瓶颈和高延时的连接，最小化推送所有数据的延时。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大35GoogleGFS的工作原理数据完整性

GFS把每个Chunk都分成64KB大小的块。每个块都对应一个32位的Checksum。和其它元数据一样，Checksum与其它的用户数据是分开的，并且保存在内存和硬盘上，同时也记录操作日志。对于读操作来说，在把数据返回给客户端或者其它的Chunk服务器之前，Chunk服务器会校验读取操作涉与的范围内的块的Checksum。因此Chunk服务器不会把错误数据传递到其它的机器上。如果发生某个块的Checksum不正确，Chunk服务器返回给请求者一个错误信息，并且通知Master服务器这个错误。作为回应，请求者应当从其它副本读取数据，Master服务器也会从其它副本克隆数据进行恢复。当一个新的副本就绪后，Master服务器通知副本错误的Chunk服务器删掉错误的副本。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大36GoogleGFS的工作原理Chunk副本的3种机制创建：当Master节点创建一个Chunk时，它会选择在哪里放置初始的空的副本。Master节点会考虑几个因素。（1）GFS希望在低于平均硬盘使用率的Chunk服务器上存储新的副本。这样的做法最终能够平衡Chunk服务器之间的硬盘使用率。（2）GFS希望限制在每个Chunk服务器上”最近”的Chunk创建操作的次数。虽然创建操作本身是廉价的，但是创建操作也意味着随之会有大量的写入数据的操作，因为Chunk在Writer真正写入数据的时候才被创建，而在我们的”追加一次，读取多次”的工作模式下，Chunk一旦写入成功之后就会变为只读的了。（3）GFS希望把Chunk的副本分布在多个机架之间。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大37GoogleGFS的工作原理Chunk副本的3种机制重新复制：当Chunk的有效副本数量少于用户指定的复制因数的时候，Master节点会重新复制它。这可能是由几个原因引起的：一个Chunk服务器不可用了，Chunk服务器报告它所存储的一个副本损坏了，Chunk服务器的一个磁盘因为错误不可用了，或者Chunk副本的复制因数提高了。每个需要被重新复制的Chunk都会根据几个因素进行排序。一个因素是Chunk现有副本数量和复制因数相差多少。例如，丢失两个副本的Chunk比丢失一个副本的Chunk有更高的优先级。另外，GFS优先重新复制活跃（live）文件的Chunk而不是最近刚被删除的文件的Chunk。最后，为了最小化失效的Chunk对正在运行的应用程序的影响，我们提高会阻塞客户机程序处理流程的Chunk的优先级。Master节点选择优先级最高的Chunk，然后命令某个Chunk服务器直接从可用的副本”克隆”一个副本出来。选择新副本的位置的策略和创建时类似：平衡硬盘使用率、限制同一台Chunk服务器上的正在进行的克隆操作的数量、在机架间分布副本。为了防止克隆产生的网络流量大大超过客户机的流量，Master节点对整个集群和每个Chunk服务器上的同时进行的克隆操作的数量都进行了限制。另外，Chunk服务器通过调节它对源Chunk服务器读请求的频率来限制它用于克隆操作的带宽。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大38GoogleGFS的工作原理Chunk副本的3种机制重新负载均衡：最后，Master服务器周期性地对副本进行重新负载均衡：它检查当前的副本分布情况，然后移动副本以便更好的利用硬盘空间、更有效的进行负载均衡。而且在这个过程中，Master服务器逐渐的填满一个新的Chunk服务器，而不是在短时间内用新的Chunk填满它，以至于过载。新副本的存储位置选择策略和上面讨论的相同。另外，Master节点必须选择哪个副本要被移走。通常情况，Master节点移走那些剩余空间低于平均值的Chunk服务器上的副本，从而平衡系统整体的硬盘使用率。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大39GoogleGFS的工作原理过期失效的副本检测当Chunk服务器失效时，Chunk的副本有可能因错失了一些修改操作而过期失效。Master节点保存了每个Chunk的版本号，用来区分当前的副本和过期副本。无论何时，只要Master节点和Chunk签订一个新的租约，它就增加Chunk的版本号，然后通知最新的副本。Master节点和这些副本都把新的版本号记录在它们持久化存储的状态信息中。这个动作发生在任何客户机得到通知以前，因此也是对这个Chunk开始写之前。如果某个副本所在的Chunk服务器正好处于失效状态，那么副本的版本号就不会被增加。Master节点在这个Chunk服务器重新启动，并且向Master节点报告它拥有的Chunk的集合以与相应的版本号的时候，就会检测出它包含过期的Chunk。如果Master节点看到一个比它记录的版本号更高的版本号，Master节点会认为它和Chunk服务器签订租约的操作失败了，因此会选择更高的版本号作为当前的版本号。Master节点在例行的垃圾回收过程中移除所有的过期失效副本。在此之前，Master节点在回复客户机的Chunk信息请求的时候，简单的认为那些过期的块根本就不存在。另外一重保障措施是，Master节点在通知客户机哪个Chunk服务器持有租约、或者指示Chunk服务器从哪个Chunk服务器进行克隆时，消息中都附带了Chunk的版本号。客户机或者Chunk服务器在执行操作时都会验证版本号以确保总是访问当前版本的数据。GoogleGFS文件系统大数据培训讲解GoogleGFS的工作原理GoogleGFS文件系统大40GoogleGFS的基本构架和工作原理GFS的系统管理技术大规模集群安装技术：如何在一个成千上万个节点的集群上迅速部署GFS，升级管理和维护等故障检测技术：GFS是构建在不可靠的廉价计算机之上的文件系统，节点数多，故障频繁，如何快速检测、定位、恢复或隔离故障节点节点动态加入技术：当新的节点加入时，需要能自动安装和部署GFS节能技术：服务器的耗电成本大于购买成本，Google为每个节点服务器配置了蓄电池替代UPS，大大节省了能耗。GoogleGFS文件系统大数据培训讲解GoogleGFS的基本构架和工作原理GoogleGFS41目录GoogleMapReduceGoogle分布式文件系统GFSGoogle分布式结构化数据表BigTable大数据培训讲解目录GoogleMapReduceGoogle分布式文件系42BigTable的基本作用和设计思想

GFS是一个文件系统，难以提供对结构化数据的存储和访问管理。为此，Google在GFS之上又设计了一个结构化数据存储和访问管理系统—BigTable，为应用程序提供比单纯的文件系统更方便、更高层的数据操作能力Google的很多数据，包括Web索引、卫星图像数据、地图数据等都以结构化形式存放在BigTable中BigTable提供了一定粒度的结构化数据操作能力，主要解决一些大型媒体数据（Web文档、图片等）的结构化存储问题。但与传统的关系数据库相比，其结构化粒度没有那么高，也没有事务处理等能力，因此，它并不是真正意义上的数据库。GoogleBigTable大数据培训讲解BigTable的基本作用和设计思想GoogleBigTa43BigTable设计动机和目标主要动机需要存储多种数据 Google提供的服务很多，序处理的数据类型也很多，如URL,网页,图片,地图数据,email,用户的个性化设置等海量的服务请求Google是目前世界上最繁忙的系统，因此，需要有高性能的请求和数据处理能力商用数据库无法适用

在如此庞大的分布集群上难以有效部署商用数据库系统，且其难以承受如此巨量的数据存储和操作需求GoogleBigTable大数据培训讲解BigTable设计动机和目标GoogleBigTable44BigTable设计动机和目标主要设计目标广泛的适用性:为一系列服务和应用而设计的数据存储系统,可满足对不同类型数据的存储和操作需求很强的可扩展性:根据需要可随时自动加入或撤销服务器节点高吞吐量数据访问:提供P级数据存储能力，每秒数百万次的访问请求高可用性和容错性:保证系统在各种情况下度能正常运转，服务不中断自动管理能力：自动加入和撤销服务器，自动负载平衡简单性：系统设计尽量简单以减少复杂性和出错率GoogleBigTable大数据培训讲解BigTable设计动机和目标GoogleBigTable45BigTable数据模型BigTable主要是一个分布式多维表，表中的数据通过：一个行关键字(rowkey)一个列关键字(columnkey)一个时间戳(timestamp)进行索引和查询定位的。BigTable对存储在表中的数据不做任何解释，一律视为字符串，具体数据结构的实现有用户自行定义。BigTable查询模型

(row:string,column:string,time:int64)

结果数据字符串支持查询、插入和删除操作GoogleBigTable大数据培训讲解BigTable数据模型GoogleBigTable大数据46BigTable数据模型BigTable数据存储格式行(Row):大小不超过64KB的任意字符串。表中的数据都是根据行关键字进行排序的。n.www就是一个行关键字，指明一行存储数据。URL地址倒排好处是：1)同一地址的网页将被存储在表中连续的位置,便于查找；2)倒排便于数据压缩,可大幅提高数据压缩率子表(Tablet)：一个大表可能太大，不利于存储管理，将在水平方向上被分为多个子表GoogleBigTable大数据培训讲解BigTable数据模型GoogleBigTable大数据47BigTable数据模型BigTable数据存储格式列(Column):BigTable将列关键字组织成为“列族”(columnfamily),每个族中的数据属于同一类别,如anchor时一个列族，其下可有不同的表示一个个超链的列关键字。一个列族下的数据会被压缩在一起存放。因此,一个列关键字可表示为:

族名：列名(family:qualifier)content、anchor都是族名；而和my.look.ca则是anchor族中的列名。GoogleBigTable大数据培训讲解BigTable数据模型GoogleBigTable大数据48BigTable数据模型BigTable数据存储格式时间戳(timestamp):很多时候同一个URL的网页会不断更新，而Google需要保存不同时间的网页数据，因此需要使用时间戳来加以区分。为了简化不同版本的数据管理，BigTable提供给了两种设置：保留最近的n个版本数据保留限定时间内的所有不同版本数据GoogleBigTable大数据培训讲解BigTable数据模型GoogleBigTable大数据49BigTable基本构架BigTable主服务器BigTable客户端BigTable客户端程序库BigTable子表服务器BigTable子表服务器BigTable子表服务器BigTable子表服务器……执行元数据操作和负载平衡数据存储和访问操作数据存储和访问操作数据存储和访问操作数据存储和访问操作GFSChubby服务器（分布式锁服务）GoogleWorkQueue负责故障监控和处理子表数据的存储与日志元数据存储与主服务器选择GoogleBigTable大数据培训讲解BigTable基本构架BigTableBigTable客户50BigTable基本构架主服务器新子表分配：当一个新子表产

生时，主服务器通过加载命令

将其分配给一个空间足够大的

子表服务；创建新表、表合并

与较大子表的分裂都会产生新

的子表。子表监控：通过Chubby完成。所有子表服务器基本信息被保存在Chubby中的服务器目录中主服务器检测这个目录可获取最新子表服务器的状态信息。当子表服务器出现故障，主服务器将终止该子表服务器，并将其上的全部子表数据移动到其它子表服务器。负债均衡：当主服务器发现某个子表服务器负载过重时，将对自动对其进行负载均衡操作。GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据51BigTable基本构架子表服务器BigTable中的数据都以子表形式保存在子表服务器上，客户端程序也直接和子表服务器通信。分配：当一个新子表产子表服务器的主要问题包括子表的定位、分配、与子表数据的最终存储。子表的基本存储结构SSTable

SSTable是BigTable内部的基本存储结构，以GFS文件形式存储在GFS文件系统中。一个SSTable实际上对应于GFS中的一个64MB的数据块(Chunk)SSTable中的数据进一步划分为64KB的子块，因此一个SSTable可以有多达1千个这样的子块。为了维护这些子块的位置信息，需要使用一个Index索引。Index64Kblock64Kblock64KblockSSTableGoogleBigTable大数据培训讲解BigTable基本构架Index64Kblock64K52BigTable基本构架子表服务器子表数据格式

概念上子表是整个大表的多行数据划分后构成。而一个子表服务器上的子表将进一步由很多个SSTAble构成，每个SSTable构成最终的在底层GFS中的存储单位。Index64Kblock64Kblock64KblockSSTableIndex64Kblock64Kblock64KblockSSTableTabletStart:aardvarkEnd:appleGoogleBigTable大数据培训讲解BigTable基本构架Index64Kblock64K53BigTable基本构架子表服务器子表数据格式

一个SSTable还可以为不同的子表所共享，以避免同样数据的重复存储。

SSTableSSTableSSTableSSTableTabletaardvarkappleTabletapple_two_EboatGoogleBigTable大数据培训讲解BigTable基本构架SSTableSSTableSSTa54BigTable基本构架子表服务器子表寻址子表地址以3级B+树形式进行索引；首先从Chubby

服务器中取得根子表，由根子表找到二级索引

指标，最后获取最终的SSTable的位置

GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据55BigTable基本构架子表服务器MinorCompaction随着写操作的执行，memtable的大小不断增加。当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一个新的memtable；被冻结住memtable会被转换成SSTable，然后写入GFS。GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据56BigTable基本构架子表服务器MergingCompaction每一次MinorCompaction都会创建一个新的SSTable。通过定期在后台执行MergingCompaction过程合并文件，限制这类文件的数量。MergingCompaction过程读取一些SSTable和memtable的内容，合并成一个新的SSTable。MajorCompaction

MajorCompaction过程生成的SSTable不包含已经删除的信息或数据。Bigtable循环扫描它所有的Tablet，并且定期对它们执行MajorCompaction。MajorCompaction机制允许Bigtable回收已经删除的数据占有的资源，并且确保BigTable能与时清除已经删除的数据。GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据57BigTable基本构架优化压缩每个SSTable的块（块的大小由局部性群组的优化参数定）都使用用户指定的压缩格式来压缩。虽然分块压缩浪费了少量空间（相比于对整个SSTable进行压缩，分块压缩压缩率较低），但是，在只读取SSTable的一小部分数据的时候就不必解压整个文件了。使用了“两遍”的、可定制的压缩方式。第一遍采用BentleyandMcIlroy’s方式，这种方式在一个很大的扫描窗口里对常见的长字符串进行压缩；第二遍是采用快速压缩算法，即在一个16KB的小扫描窗口中寻找重复数据。两个压缩的算法都很快，在现在的机器上，压缩的速率达到100-200MB/s，解压的速率达到400-1000MB/s。GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据58BigTable基本构架优化Bloomfilter一个读操作必须读取构成Tablet状态的所有SSTable的数据。如果这些SSTable不在内存中，那么就需要多次访问硬盘。我们通过允许客户程序对特定局部性群组的SSTable指定Bloom过滤器，来减少硬盘访问的次数。我们可以使用Bloom过滤器查询一个SSTable是否包含了特定行和列的数据。对于某些特定应用程序，我们只付出了少量的、用于存储Bloom过滤器的内存的代价，就换来了读操作显著减少的磁盘访问的次数。使用Bloom过滤器也隐式的达到了当应用程序访问不存在的行或列时，大多数时候我们都不需要访问硬盘的目的。GoogleBigTable大数据培训讲解BigTable基本构架GoogleBigTable大数据59BigTable基本构架Bloomfilter原理如需要判断一个元素是不是在一个集合中，我们通常做法是把所有元素保存下来，然后通过比较知道它是不是在集合内，链表、树都是基于这种思路，当集合内元素个数的变大，我们需要的空间和时间都线性变大，检索速度也越来越慢。Bloomfilter采用的是哈希函数的方法，将一个元素映射到一个m长度的阵列上的一个点，当这个点是1时，那么这个元素在集合内，反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突，解决方法就是使用k个哈希函数对应k个点，如果所有点都是1的话，那么元素在集合内，如果有0的话，元素则不在集合内。初始状态时，BloomFilter是一个包含m位的位数组，每一位都置为0。GoogleBigTable大数据培训讲解BigTable基本构架初始状态时，BloomFilter60BigTable基本构架Bloomfilter为了表达S={x1,x2,…,xn}这样一个n个元素的集合，BloomFilter使用k个相互独立的哈希函数（HashFunction），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个falsepositive。GoogleBigTable大数据培训讲解BigTable基本构架在判断y是否属于这个集合时，我们对y61目录大数据起源Hadoop1.0Hadoop2.0商用环境大数据培训讲解目录大数据起源Hadoop1.0Hadoop2.0商用环境大62hadoopHadoop是一个开源的软件框架，它支持数据密集型的分布式应用，许可授权隶属于Apachev2license.可以在成千上万台独立的计算机上运行。Hadoop源自于Google的MapReduce和GoogleFileSystem(GFS)两篇论文。现在通常认为完整的ApacheHadoop‘平台’由Hadoop内核、MapReduce和HDFS组成，以与若干相关的项目——包括ApacheHive、ApacheHbase等等Hadoop介绍

大数据培训讲解hadoopHadoop是一个开源的软件框架，它支持数据密集63HDFS基本构架对等于GFS

Master对等于GFS

ChunkServer应用程序HDFS客户端文件名或数据块号数据块号，数据块位置HDFSNameNodeDataNode数据DataNode数据DataNode数据Hadoop的分布式文件系统HDFS大数据培训讲解HDFS基本构架对等于GFSMaster对等于GFSCh64HadoopMapReduce基本构架与工作过程2.HadoopMapReduce的基本工作原理对等于GoogleMapReduce中的Master对等于GoogleMapReduce中的Worker大数据培训讲解HadoopMapReduce基本构架与工作过程2.Ha65datanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodenamenodenamenodedaemonjobsubmissionnodejobtrackerHadoop介绍

HadoopMapReduce和HDFS数据存储与计算节点构架大数据培训讲解datanodedaemonLinuxfilesyst66Hadoop1.0X86PC集群本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘数据节点Datanode数据节点Datanode数据节点Datanode数据节点Datanode数据节点Datanode管理节点Datanode备份管理节点Datanode万兆交换万兆交换数据查询（Hbase）运算与处理（Map-Reduce)数据提取（HIVE）ETLOozieTaskTracker(MapTask)TaskTracker(MapTask)中间结果中间结果TaskTracker(ReduceTask)JobTracker任务调度任务调度状态监控状态监控任务管理调度管理Hadoop处理层-设备与拓扑处理层-软件技术架构SQL-Script列式存储Hive架构转化为Map-Reduce程序列式索引大数据培训讲解Hadoop1.0X86PC集群本机硬盘本机硬盘本机硬盘67Hadoop1.0架构下的混搭处理中心X86PC集群本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘本机硬盘数据节点Datanode数据节点Datanode数据节点Datanode数据节点Datanode数据节点Datanode管理节点Namenode备份管理节点Namenode万兆交换万兆交换数据查询（Hbase）运算与处理（Map-Reduce)数据提取（HIVE）ETL数据存储：磁盘阵列数据计算：

数据服务器HadoopRDB&内存库RDB内存数据库处理层-设备与拓扑处理层-软件技术架构。主ID，亿级查询，毫秒级。次级索引查询，秒级。外部提供noSql查询方式。使用CoprocessorMR程序，满足临时性分析。。亿级数据，支持秒级查询。支持SQL方式提取数据。支持数据汇总，数据提取的快速开发。通过MR开发，满足绝大部分数据处理需求。支持十亿级，百亿级的数据分析与开发。结合Mahout，满足对大数据的分析需求。通过结合文本处理技术，满足非结构化文本数据需求。OLTP与数据量较小的OLAP管理节点备份保证安全数据冗余参数设置，保障基础数据安全实时数据查询（Impala）。Jdbc/ODBC列式存储HRegion-Server混搭架构解决各类数据访问需求基础存储（HDFS）满足万分之一秒访问并行查询调度查询优化器本机硬盘本机硬盘MPP万兆交换ODSLinux：FSDW&DMDB-File。Jdbc/ODBC。支持SQL方式提取数据。支持关联性查询。对内存有效利用。对网络带宽有依赖大数据培训讲解Hadoop1.0架构下的混搭处理中心X86PC集群本机68Hbase&HiveHBase原理复杂查询和二级索引HBase与Hive集成大数据培训讲解Hbase&HiveHBase原理复杂查询和二级索引HB69HBase简介HBase是分布式的、面向列的开源数据库HBase是GoogleBigtable的开源实现底层基于Hadoop，HDFS为HBase提供高可靠性的底层存储支持，MapReduce为HBase提供高性能的计算能力Zookeeper为HBase提供了稳定服务和failover机制大数据培训讲解HBase简介HBase是分布式的、面向列的开源数据库大数据70HBase简介HBase中有两张特殊的Table，-ROOT-和.META..META.：记录了用户表的Region信息，.META.可以有多个regoin-ROOT-：记录了.META.表的Region信息，-ROOT-只有一个regionØZookeeper中记录了-ROOT-表的locationClient访问用户数据之前需要首先访问zookeeper，然后访问-ROOT-表，接着访问.META.表，最后才能找到用户数据的位置去访问，中间需要多次网络操作，不过client端会做cache缓存。ZookeeperQuorum中除了存储了-ROOT-表的地址和HMaster的地址，HRegionServer也会把自己以Ephemeral方式注册到Zookeeper中，使得HMaster可以随时感知到各个HRegionServer的健康状态。HMaster没有单点问题，HBase中可以启动多个HMaster，通过Zookeeper的MasterElection机制保证总有一个Master运行当HRegionServer意外终止后，HMaster会通过Zookeeper感知到大数据培训讲解HBase简介HBase中有两张特殊的Table，-ROOT71HBase数据模型RowKeycontentsanchorCMy.look.caTimestampvalueTimestampvalueTimestampvalueCn.wwwt3<html>…t8CNNt9CNN.comt5<html>…t6<html>…RowKey：table主键，HBase中记录按照RowKey排序Timestamp：时间戳，HBase可以保存多版本的数据ColumnFamily，列簇，HBase中的集中存储单元ColumnQualifier，与ColumnFamily一起标记某一列大数据培训讲解HBase数据模型RowKeycontentsanchor72HFile结构名称字节数说明keyLength4表示Key所占的总字节数valueLength4表示Value所占的总字节数rowLength2表示rowKey所占的字节数rowrowLength数据的rowKeycolumnFamilyLength1表示列族名称所占的字节数columnFamilycolumnFamilyLength列族名称columnQualifier

列名与columnFamily一起标记唯一列timestamp8时间戳type1Key类型，比如是新增(Put)，还是删除(Delete)valuevalueLength列值KeyValue结构说明Hfile结构：KeyValue结构：大数据培训讲解HFile结构名称字节数说明keyLength73列存储RowKey基本信息成绩名字性别语文数学TimestampvalueTimestampvalueTimestampvalueTimestampvalue小明keyt1小明t2男t580t990t483t893t385t795文件1文件21724小明key4成绩语文t5180大数据培训讲解列存储RowKey基本信息成绩名字性别语文数学Timest74HBase系统架构Client通过zookeeper与master通信进行管理类操作client与regionserver通信进行数据读写操作存储-ROOT-表地址存储HMaster的地址协调多个HMaster防止单点问题管理用户对表的操作调整Region分布，负载均衡管理Regionsplit后的region重分布RegionServer宕机后region的迁移工作响应用户的I/O请求，向HDFS中读写文件大数据培训讲解HBase系统架构Client通过zookeeper与mas75HBase数据访问流程clientzookeeper关键文件：/hbase/hbaseid集群ID，跟存储在HDFS上的hbase.id文件中的一致/hbase/master服务器名称/hbase/root-region-server持有-ROOT-表regions的regionserver的服务器名称-ROOT-表记录.META.的Region信息，该region永远不split，只会有一个Region。表数据结构：rowkey：

存储.META.的region的名称columnFamily：共一个，为“info”columnQualifier共三个包含：regioninfo：保存region的信息，包括name、startkey、 endkey等信息server：该region所在RegionServerserverstartcord：region所在RegionServer启动时间RowKeyinforegioninfoserverserverstartcord.META.,,1NAME=>'.META.,,1',STARTKEY=>'',ENDKEY=>'',ENCODED=>1028785192,}cloud204:600201371430827702UserTable,100,1371430844857.de0b50NAME=>UserTable,100,1371430844857.de0b50',STARTKEY=>‘100',ENDKEY=>‘200',ENCODED=>de0b50,}cloud199:600201371430844857.META.表记录用户表的Region信息：表数据结构与-ROOT-相似：rowkey：

存储用户表的region的名称columnFamily：共一个，为“info”columnQualifier共三个包含：regioninfo：保存region的信息，包括name、startkey、 endkey等信息server：该region所在RegionServerserverstartcord：region所在RegionServer启动时间大数据培训讲解HBase数据访问流程clientzookeeper关键文件76HRegionServer结构每个HRegion对应Table中的Region，由多个HStore组成HBase中的集中的存储单元，对应Table中的ColumnFamily，由MemStore和StoreFile组成HRegionServer：包含多个HRegion大数据培训讲解HRegionServer结构每个HRegion对应Tabl77HRegionServer结构大数据培训讲解HRegionServer结构大数据培训讲解78Region合并和分割HStore存储是HBase存储的核心了，其中由两部分组成，一部分是MemStore，一部分是StoreFiles。1.MemStore是SortedMemoryBuffer，用户写入的数据首先会放入MemStore，当MemStore满了以后会Flush成一个StoreFile（底层实现是HFile）.2.当StoreFile文件数量增长到一定阈值，会触发Compact合并操作，将多个StoreFiles合并成一个StoreFile，合并过程中会进行版本合并和数据删除，因此可以看出HBase其实只有增加数据，所有的更新和删除操作都是在后续的compact过程中进行的，这使得用户的写操作只要进入内存中就可以立即返回，保证了HBaseI/O的高性能。3.当StoreFilesCompact后，会逐步形成越来越大的StoreFile，当单个StoreFile大小超过一定阈值后，会触发Split操作，同时把当前RegionSplit成2个Region，父Region会下线，新Split出的2个孩子Region会被HMaster分配到相应的HRegionServer上，使得原先1个Region的压力得以分流到2个Region上。大数据培训讲解Region合并和分割HStore存储是HBase存储的核心79HStore中数据写入流程PUTFlushCompactSplitClient端PUT数据数据写入MemStore中MemStore写满后执行flush数据被flush为StoreFileStoreFile数量增长到阀值，触发Compact操作多个StoreFile合并成一个StoreFile版本合并，数据删除Region大小达到阀值，执行Split操作一个Region会Split成成两个Master上线新的两个Region旧的Region下线大数据培训讲解HStore中数据写入流程PUTFlushCompactSp80HBaseCoprocessorHBaseCoprocessor实现目的：HBase0.92版本新增加特性，为了解决如下问题HBase无法轻易建立“二级索引”执行求和、计数、排序等操作比较困难，必须通过mapreduce实现，对于简单的统计或聚合计算时，可能会因为网络开销大而带来性能问题灵感来源：灵感来源于bigtable的协处理器，包含如下特性每个表服务器的任意子表都可以运行代码客户端能够直接访问数据表的行，多行读写会自动分片成多个并行的RPC调用提供接口：RegionObserver：提供客户端的数据操纵事件钩子：Get、Put、Delete、Scan等WALObserver：提供WAL相关操作钩子MasterObserver：提供DDL-类型的操作钩子。如创建、删除、修改数据表等Endpoint：终端是动态RPC插件的接口，它的实现代码被安装在服务器端，能够通过HBaseRPC调用唤醒应用范围：通过使用RegionObserver接口可以实现二级索引的创建和维护通过使用Endpoint接口，在对数据进行简单排序和sum，count等统计操作时，能够极大提高性能大数据培训讲解HBaseCoprocessorHBase实现目的81RegionObserver工作原理RegionObserver提供客户端的数据操纵事件钩子，Get、Put、Delete、Scan，使用此功能能够解决主表以与多个索引表之间数据一致性的问题大数据培训讲解RegionObserver工作原理RegionObserv82CoprocessorEndpoint2.客户端通过调用count方法查询，等待查询结果1.操作region上数据的代码，需要先安装到服务器端，客户端通过接口调用3.HBase通过RPC唤醒安装在服务器端的实现代码（CountProtocol），等待执行结果返回，然后通过callback回调汇聚函数4.汇聚每个region上的返回数据，更新最终结果5.返回最终查询结果大数据培训讲解CoprocessorEndpoint2.客户端通过调用c83目录HBase原理复杂查询和二级索引HBase与Hive集成大数据培训讲解目录HBase原理复杂查询和二级索引HBase与Hive集成84HBase二级索引HBase二级索引HBase索引需求：HBase只支持针对与主键key的高性能查询HBase本身不支持快速的复杂查询和join索引的实现目标：高性能的数据检索数据的低冗余数据的一致性索引的实现方式：基于表的索引，多个索引时每个索引建一个表或者建组合索引基于列的索引，所有索引存单张表，每个索引字段为一个列簇第三方工具框架：ITHbase，HBase索引的事务行解决方案，0.92版本以后的HBase已经可以通过Coprocessor实现其功能Lily，基于HBase和SOLR实现，能够提供快速的检索和模糊查询大数据培训讲解HBase二级索引HBaseHBase索引需求：索引85表索引实现原理发挥HBase基于主键查询效率高的特点，添加索引表，把基于索引字段的查询转换为基于HBase主键的查询业务表key101101…………key102102…………key103103…………

基于column1字段的查询先查Index表Index表101key101102key102103key103rowkeycolumn1column2……大数据培训讲解表索引实现原理发挥HBase基于主键查询效率高的特点，添加索86表索引的使用和维护索引表的维护索引表的使用

CoprocessorUserTableIndexTablePut/DeletepostPut/postDelete