《云计算(第三版)》配套PPT之五：第2章-Google云计算原理与应用(四)

of64《云计算》第三版配套PPT课件电子工业出版社《云计算(第三版)》配套课件云计算（第三版）CLOUDCOMPUTINGThirdEdition主编：刘鹏教授第2章Google云计算原理与应用（四）本套PPT下载地址：=20云计算的红宝书书籍购买地址：=1469775685&p=-1电子工业出版社《云计算(第三版)》配套课件（包邮且有刘鹏教授亲笔签名）教授、博导、学科带头人，清华大学博士。现任中国云计算专家咨询委员会秘书长、中国信息协会大数据分会副会长、工业与信息化部云计算研究中心专家。主持完成科研项目25项，发表论文80余篇，出版专业书籍15本。获部级科技进步二等奖4项、三等奖4项。主编了国内第一本云计算教材《云计算》和第一本云计算编程书籍《实战Hadoop》。创办了知名的中国云计算（chinacloud.cn）和中国大数据（thebigdata.cn）网站。曾率队夺得2002PennySort国际计算机排序比赛冠军，两次夺得全国高校科技比赛最高奖，并三次夺得清华大学科技比赛最高奖。荣获“全军十大学习成才标兵”（排名第一）、南京“十大杰出青年”、江苏省“333高层次人才培养工程”中青年科学技术带头人、清华大学“学术新秀”等称号。刘鹏of64《云计算》第三版配套PPT课件目录目录2.1Google文件系统GFS2.2分布式数据处理MapReduce2.3分布式锁服务Chubby2.4分布式结构化数据表Bigtable2.5分布式存储系统Megastore2.6大规模分布式系统的监控基础架构Dapper2.7海量数据的交互式分析工具Dremel2.8内存大数据分析系统PowerDrill2.9Google应用程序引擎数据本身不会产生价值只有经过分析才有可能产生价值of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件7产生背景2.7海量数据的交互式分析工具DremelMapReduce优点：便携缺点：效率低Google的团队结合其自身的实际需求，借鉴搜索引擎和并行数据库的一些技术，开发出了实时的交互式查询系统Dremel。of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具DremelDremel支持的典型应用Web文档的分析Android市场的应用安装数据的跟踪Google产品的错误报告Google图书的光学字符识别欺诈信息的分析Google地图的调试Bigtable实例上的tablet迁移Google分布式构建系统的测试结果分析磁盘I/O信息的统计Google数据中心上运行任务的资源监控Google代码库的符号和依赖关系分析8of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件10两方面的技术支撑两方面的技术支撑一方面：统一的存储平台另一方面：统一的数据存储格式实现高效的数据存储，Dremel使用的底层数据存储平台是GFS存储的数据才可以被不同的平台所使用2.7海量数据的交互式分析工具Dremelof64《云计算》第三版配套PPT课件112.7海量数据的交互式分析工具Dremel面向记录和面向列的存储Google的Dremel是第一个在嵌套数据模型基础上实现列存储的系统。列存储更利于数据的压缩处理时只需要使用涉及的列数据好处一：好处二：of64《云计算》第三版配套PPT课件121dom|A:?,,A:?n2.7海量数据的交互式分析工具Dremel嵌套模型的形式化定义原子类型（AtomicType）原子类型允许的取值类型包括整型、浮点型、字符串等记录类型（RecordType）记录类型则可以包含多个域记录型数据包括三种类型：必须的（Required）、可重复的（Repeated）以及可选的（Optional）of64《云计算》第三版配套PPT课件132.7海量数据的交互式分析工具Dremel嵌套结构的模式和实例文档的模式（Schema）定义符合该模式的两条记录利用该数据模型，可以使用Java语言，也可以使用C++语言来处理数据，甚至可以用Java编写的MapReduce程序直接处理C++语言产生的数据集。这种跨平台的优良特性正是Google所需要的。of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件152.7海量数据的交互式分析工具Dremel数据结构的无损表示带有重复深度和定义深度的r1与r2的列存储重复深度主要关注的是可重复类型，而定义深度同时关注可重复类型和可选类型（optional）每一列最终会被存储为块（Block）的集合，每个块包含重复深度和定义深度且包含字段值。of64《云计算》第三版配套PPT课件162.7海量数据的交互式分析工具Dremel高效的数据编码计算重复和定义深度的基础算法Dremel利用图中算法创建一个树状结构树的节点为字段的writer，它的结构与模式中的字段层级匹配。核心的想法是只在字段writer有自己的数据时执行更新，非绝对必要时不尝试往下传递父节点状态。子节点writer继承父节点的深度值。当任意值被添加时，子writer将深度值同步到父节点。of64《云计算》第三版配套PPT课件172.7海量数据的交互式分析工具Dremel数据重组Dremel数据重组方法的核心思想是为每个字段创建一个有限状态机（FSM），读取字段值和重复深度，然后顺序地将值添加到输出结果上。of64《云计算》第三版配套PPT课件18当前FSM写入值下一个重复深度值动作DocId（开始）100跳转至Links.BackwardLinks.BackwardNULL0跳转至Links.ForwardLinks.Forward201停留在Links.ForwardLinks.Forward401停留在Links.ForwardLinks.Forward600跳转至Name.Language.CodeName.Language.Codeen-us2跳转至Name.Language.CountryName.Language.Countryus2跳转至Name.Language.CodeName.Language.Codeen1跳转至Name.Language.CountryName.Language.CountryNULL1跳转至Name.UrlName.Url跳转至Name.Language.CodeName.Language.Codeen-gb0跳转至Name.Language.CountryName.Language.Countrygb0跳转至Name.UrlName.UrlNULL0结束2.7海量数据的交互式分析工具Dremel数据重组r1的完整数据重组过程of64《云计算》第三版配套PPT课件192.7海量数据的交互式分析工具Dremel数据重组如果具体的查询中不是涉及所有列，而是仅涉及很少的列的话，上述数据重组的过程会更加便利，下图中仅仅涉及DocId和Name.Language.Country的有限状态机。of64《云计算》第三版配套PPT课件202.7海量数据的交互式分析工具Dremel数据重组核心的思想如下：设置t为当前字段读取器的当前值f所返回的下一个重复深度。在模式树中，找到它在深度t的祖先，然后选择该祖先节点的第一个叶子字段n。由此得到一个FSM状态变化(f,t)-n。有限状态机的构造算法of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件222.7海量数据的交互式分析工具Dremel查询语言与执行Dremel的SQL查询输入的是一个或多个嵌套结构的表以及相应的模式，而输出的结果是一个嵌套结构的表以及相应的模式。嵌套子查询记录内聚合top-kjoins自定义函数……of64《云计算》第三版配套PPT课件232.7海量数据的交互式分析工具DremelDremel利用多层级服务树（multi-levelservicetree）的概念来执行查询操作根服务器接受客户端发出的请求，读取相应的元数据，将请求转发至中间服务器。中间服务器负责查询中间结果的聚集叶子服务器负责执行数据来源查询语言与执行of64《云计算》第三版配套PPT课件24查询语言与执行Dremel中的数据都是分布式存储的，因此每一层查询涉及的数据实际都被水平划分后存储在多个服务器上。Dremel是一个多用户系统，因此同一时刻往往会有多个用户进行查询。查询分发器有一个很重要参数，它表示在返回结果之前一定要扫描百分之多少的tablet2.7海量数据的交互式分析工具Dremelof64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件26表名记录数（亿)规模（未压缩，TB）域数目数据中心复制因子T185087270A3T224013530A3T340701200A3T41000010550B3T5100002050B22.7海量数据的交互式分析工具Dremel由于Dremel并不开源，我们只能通过Google论文中的分析大致了解其性能。Google的实验数据集规模如下图：性能分析of64《云计算》第三版配套PPT课件272.7海量数据的交互式分析工具Dremel性能分析MR从面向记录转换到列状存储后性能提升了一个数量级（从小时到分钟），而使用Dremel则又提升了一个数量级（从分钟到秒）of64《云计算》第三版配套PPT课件2.7海量数据的交互式分析工具Dremel2.7.1产生背景2.7.2数据模型2.7.3嵌套式的列存储2.7.4查询语言与执行2.7.5性能分析2.7.6小结of64《云计算》第三版配套PPT课件292.7海量数据的交互式分析工具Dremel小结Dremel和MapReduce并不是互相替代，而是相互补充的技术。在不同的应用场景下各有其用武之地。Drill的设计目标就是复制一个开源的Dremel，但是从目前来看，该项目无论是进展还是影响力都达不到Hadoop的高度。希望未来能出现一个真正有影响力的开源系统实现Dremel的主要功能并被广泛采用。123of64《云计算》第三版配套PPT课件目录目录2.1Google文件系统GFS2.2分布式数据处理MapReduce2.3分布式锁服务Chubby2.4分布式结构化数据表Bigtable2.5分布式存储系统Megastore2.6大规模分布式系统的监控基础架构Dapper2.7海量数据的交互式分析工具Dremel2.8内存大数据分析系统PowerDrill2.9Google应用程序引擎of64《云计算》第三版配套PPT课件2.8内存大数据