海量数据的交互式分析工具Dremel，内存大数据分析系统PowerDrill，Google应用程序引擎
海量数据的交互式分析工具Dremel
产生背景
MapReduce：
- 优点：便携
- 缺点：效率低
Google的团队结合其自身的实际需求，借鉴搜索引擎和并行数据库的一些技术，开发出了实时的交互式查询系统Dremel。
Dremel支持的典型应用
- Web文档的分析
- Android市场的应用安装数据的跟踪
- Google产品的错误报告
- Google图书的光学字符识别
- 欺诈信息的分析
- Google地图的调试
- Bigtable实例上的tablet迁移
- Google分布式构建系统的测试结果分析
- 磁盘I/O信息的统计
- Google数据中心上运行任务的资源监控
- Google代码库的符号和依赖关系分析
数据模型
技术支持
- 统一的存储平台：实现高效的数据存储，Dremel使用的底层数据存储平台是GFS
- 统一的数据存储格式：存储的数据才可以被不同的平台所使用
面向记录和面向列的存储
Google的Dremel是第一个在嵌套数据模型基础上实现列存储的系统。
- 好处1：处理时只需要使用涉及的列数据
- 好处2：列存储更利于数据的压缩
嵌套模型的形式化定义
- 原子类型（Atomic Type）：原子类型允许的取值类型包括整型、浮点型、字符串等
- 记录类型（Record Type）：记录类型则可以包含多个域
- 记录型数据包括三种类型：必须的（Required）、可重复的（Repeated）以及可选的（Optional）
嵌套结构的模式和实例
嵌套式的列存储
数据结构的无损表示
重复深度主要关注的是可重复类型，而定义深度同时关注可重复类型和可选类型（optional）
每一列最终会被存储为块（Block）的集合，每个块包含重复深度和定义深度且包含字段值。
带有重复深度和定义深度的r1与r2的列存储:
高效的数据编码
- Dremel利用图中算法创建一个树状结构
- 树的节点为字段的writer，它的结构与模式中的字段层级匹配。
- 核心的想法是只在字段writer有自己的数据时执行更新，非绝对必要时不尝试往下传递父节点状态。
- 子节点writer继承父节点的深度值。
- 当任意值被添加时，子writer将深度值同步到父节点。
计算重复和定义深度的基础算法:
数据重组
Dremel数据重组方法的核心思想是为每个字段创建一个有限状态机（FSM），读取字段值和重复深度，然后顺序地将值添加到输出结果上。
如果具体的查询中不是涉及所有列，而是仅涉及很少的列的话，上述数据重组的过程会更加便利，下图中仅仅涉及DocId和Name.Language.Country的有限状态机。
核心思想
设置t为当前字段读取器的当前值f所返回的下一个重复深度。
在模式树中，找到它在深度 t 的祖先，然后选择该祖先节点的第一个叶子字段 n。
由此得到一个FSM状态变化(f,t)->n。
查询语言与执行
Dremel的SQL查询输入的是一个或多个嵌套结构的表以及相应的模式，而输出的结果是一个嵌套结构的表以及相应的模式。
查询语言与执行
Dremel利用多层级服务树（multi-level service tree）的概念来执行查询操作
- 根服务器：接受客户端发出的请求，读取相应的元数据，将请求转发至中间服务器。
- 中间服务器：负责查询中间结果的聚集
- 叶子服务器：负责执行数据来源
规则及原理
- Dremel中的数据都是分布式存储的，因此每一层查询涉及的数据实际都被水平划分后存储在多个服务器上。
- Dremel是一个多用户系统，因此同一时刻往往会有多个用户进行 查询。
- 查询分发器有一个很重要参数，它表示在返回结果之前一定要扫描百分之多少的tablet
性能分析
由于Dremel并不开源，我们只能通过Google论文中的分析大致了解其性能。Google的实验数据集规模如下图：
MR从面向记录转换到列状存储后性能提升了一个数量级（从小时到分钟），而使用Dremel则又提升了一个数量级（从分钟到秒）
小结
- Dremel和MapReduce并不是互相替代，而是相互补充的技术。在不同的应用场景下各有其用武之地。
- Drill的设计目标就是复制一个开源的Dremel，但是从目前来看，该项目无论是进展还是影响力都达不到Hadoop的高度。
- 希望未来能出现一个真正有影响力的开源系统实现Dremel的主要功能并被广泛采用。
PowerDrill
产生背景与设计目标
两个假设结论：
- 绝大多数的查询是类似和一致的；
- 存储系统中的表只有一小部分是经常被使用的，绝大部分的表使用频率不高。
考虑两方面的内容：
- 如何尽可能在查询中略去不需要的数据分块；
- 如何尽可能地减少数据在内存中的占用，占用越少意味着越多的数据可以被 加载进内存中处理。
PowerDrill整个系统实际分为三个部分：
- Web UI
- 一个抽象层
- 列式存储
基本数据结构
下图阐述了PowerDrill采用的数据结构，简单来说就是一个双层数据字典结构。
性能优化
数据分块
- 背景：传统的索引对于PowerDrill的查询场景作用不是很大，因此一个很自然的考虑就是对数据进行分块，过滤查询中不需要的数据块来减少数据量
- 方法：常见的分区方法有范围分区、散列分区等。PowerDrill实际采用的是一种组合范围分区方法。
- 步骤
- 领域专家确定若干个划分的域
- 利用这几个域对数据进行划分
- 每个块的行数达到阈值时就停止划分
- 局限：PowerDrill采用的数据分块方法简单实用，但是由于域的确定需要领域专家，因此这种方法在实际使用中还有一定的局限性
数据编码的优化
- 对于不同的块，如果我们可以确定块中不同值的数量，那么就可以根据这个数量值来选择可变的比特位来记录块id
- 统计一组数中不同值的个数有一个专有名词，称为“基数估计”
- 对于小规模的数据集，可以比较容易地统计出精确的基数。但是在大数据的环境下，精确的基数统计非常耗时，因此能保证一定精度的基数估计就可以满足实际的需求。
- 基数估计的方法很多，大多利用了散列函数的一些特性，Google内部使用的是一种称为Hyperloglog的基数估计方法的变种。
全局字典优化
两个特性：
- 全局字典是有序的
- 排序后的数据常常有共同的前缀
实际使用中为了进一步减少查询中需要加载到内存的全局字典，对全局字典又进行了分块
对每个全局字典块还会维护一个布隆过滤器（bloom filter）来快速确定某个值是否在字典中。
压缩算法
Google曾经对一些主流的压缩算法做过简单的测试，如下图：
- 不管压缩算法的解压速度多快，总会消耗一定的物理资源与时间。对此PowerDrill采用了一种冷热数据分别对待的策略。
- 在冷热数据切换策略中，比较常用的是LRU算法。PowerDrill开发团队采用了启发式的缓存策略来代替原始的LRU算法。
行的重排
数据压缩的算法有很多，比较常用的一种称为游程编码（Run-Length Encoding，RLE），又称行程长度编码，其好处是压缩和解压缩都非常快。
性能分析与对比
我们比较关注的两组数据
在查询过程中，平均92.41%的数据被略去
5.02%的数据会直接被缓存命中
一般仅须扫描2.66%的数据即可得到查询结果
超过70%的查询是不需要从磁盘访问任何数据的
这些查询的平均访问延迟大约是25秒
96.5%的查询需要访问的磁盘量不超过1GB
性能分析与对比
PowerDrill与Dremel的对比
Google应用程序引擎
Google App Engine简介
Google App Engine是一个由Python应用服务器群、Bigtable数据库及GFS数据存储服务组成的平台，它能为开发者提供一体化的可自动升级的在线应用服务。
- Google App Engine可以让开发人员在Google的基础架构上运行网络应用程序。
- 在Google App Engine中，用户可以使用appspot.com域上的免费域名为应用程序提供服务，也可以使用Google企业应用套件从自己的域为它提供服务。
- 可以免费使用Google App Engine。注册一个免费账户即可开发和发布应用程序，而且不需要承担任何费用和责任。
Google App Engine的整体架构
应用程序环境
- 动态网络服务功能。能够完全支持常用的网络技术。
- 具有持久存储的空间。在这个空间里平台可以支持一些基本操作，如查询、分类和事务的操作。
- 具有自主平衡网络和系统的负载、自动进行扩展的功能。
- 可以对用户的身份进行验证，并且支持使用Google账户发送邮件。
- 个功能完整的本地开发环境，可以在自身的计算机上模拟Google App Engine环境。
- 支持在指定时间或定期触发事件的计划任务。
沙盒的限制
- 用户的应用程序只能通过Google App Engine提供的网址抓取API和电子邮件服务API来访问互联网中其他的计算机，其他计算机如请求与该应用程序相连接，只能在标准接口上通过HTTP或HTTPS进行
- 应用程序无法对Google App Engine的文件系统进行写入操作，只能读取应用程序代码上的文件，并且该应用程序必须使用Google App Engine的Data Store数据库来存储应用程序运行期间持续存在的数据
- 应用程序只有在响应网络请求时才运行，并且这个响应时间必须极短，在几秒之内必须完成。与此同时，请求处理的程序不能在自己的响应发送后产生子进程或执行代码
Google App Engine服务
一些问题
Google云计算技术包括哪些内容？
Google分布式文件系统GFS, 分布式计算编程模型MapReduce, 分布式锁服务Chubby， 分布式结构化数据表Bigtable， 分布式存储系统Megastore， 分布式监控系统Dapper， 数据交互分析工具Dremel和PowerDrill。
当前主流分布式文件系统有哪些？各有什么优缺点？
RedHat. IBM、 Sun 等公司都有分布式文件系统的解决方案，这些解决方案依靠RAID技 术、SAN存储区域网来容错(是基于硬件的容错)，对构建分布式文件系统的硬件有较高的 要求，存储成本高。Google 的GFS 是使用软件的方式，在文件系统上实现容错，可以使用 廉价的机器构建，存储成本低。相对于传统的分布式文件系统，Google 的GFS分布式文件 系统的容错性能在可靠性和存储成本上，都具有优势。
GFS采用了哪些容错措施来确保整个系统的可靠性？
(1) Master 容错。， Master上保存着GFS的元数据(包括命名空间(Name)和Chunk映射表等)，这些元数据 及Master的操作日志保存在磁盘中，Master 出错时而磁盘数据完好时，可以通过磁盘数据 恢复Master. GFS对Master进行远程实时备份，如果Master彻底死机，另外一台Master可以迅速接替其 工作。 (2) Chunk Server容错。 Chunk是GFS的数据块，一个Chunk默认存储3个位于不同Chunk Server的副本，Master 会检查Chunk的副本数，在出现Chunk副本丢失或不可恢复时，Master 自动将该副本复制 到其他Chunk Server. 另外，Chunk 以文件的形式保存在Chunk Server, Chunk 文件以Block (64K)来划分，每一 个Block对应–个32位的校验和，ChunkServer会检查数据和检验和，如果不匹配就返回错 误。
MapReduce与传统的分布式程序设计相比有何优点？
与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。
Chubby的设计目标是什么？Paxos算法在Chubby中起 什么作用？
设计目标： 高可用性和高可靠性 高扩展性 支持粗粒度的建议性锁服务 服务信息的直接存储 支持缓存机制 支持通报机制
作用： Paxos算法在Chubby中起到保证副本之间数据一致的作用 (ChubbyCell (单元)中的所有副 本都要保持完全一致)。
阐述Bigtable的数据模型和系统架构。
答: Bigtable 的数据模型是一一个多维映射表，通过行关键字、列关键字和时间戳进行索引(定 位数据): (1) 行。行关键字用于标识Bigtable 中不同的行，可以是任意字符串，大小不能 超过64KB。Bigtable 中的数据是通过行关键字按字典序进行排序的。(2)列。Bigtable 中的 列，以列族进行组织，-一个列关键字以“族名:列名”的形式表示，每个列族中的列属于同 种数据类型，并且访问控制(Access Control)是在列族上进行定义的。(3)时间戳。用于在 区别Bigtable中数据的版本，同-一个行、列定位的数据，可以根据设置保存具有不同时间戳 的数据值。 Bigtable主要由三个部分组成:主服务器Master Server、子表服务器Tablet Server 和客户端 程序库(Client Library)。主服务器主要进行- -些元数据操作以及子表服务器之间的负载调度 问题，子表服务器则以子表的形式(通过GFS以SSTable类型文件)保存Bigtable的数据， 一个子表服务器负责存储若千个(通常100个左右)子表。访问Bigtable服务需要使用Bigtable 的客户端。
分布式存储系统Megastore的核心技术是什么？
复制
大规模分布式系统的监控基础架构Dapper关键技术是什么？
轻量级核心功能库 二次抽样技术
相比于行存储，列存储有哪些优点？
相对于行存储，列存储以属性为单位，每次存储一一个属性。 列存储的主要好处在于处理 时只需要使用涉及的列数据，且列存储更有利于数据的压缩。
为什么MapReduce不适合实时数据处理？
MapReduce 是一种面向批处理的框架，在编写完成代码后，要提交到集群运行后才能 验证代码的正确性。如果代码有误需要修改，则需要返利修改——运行——验证。 这种数据 探索(Data Exploration)的方式比较耗时。而传统的SQL查询则是交互式的，用户提交完自 己的请求后就可以在相对可以接受的时间内得到返回结果。
简单阐述Dremel如何实现数据的无损表示。
Dremel 采用嵌套模型，采用列存储，因此需要把存储的数据进行重组才能还原为记录 的形式。Dremel的每–列会被存储为块的集合，每个块又包含重复深度和定义深度，根据 重复深度和定义深度确定相应块的字段值属于哪条记录的哪个字段。
PowerDrill能实现高效的数据处理，在存储部分主要依赖哪两方面的技术？
(1)列式存储。(2)内存计算。
Google App Engine提供了哪些服务？
(1)图像操作API。(2)邮件API。(3) Memcache API。(4) 用户API。(5)数据库API。
Google App Engine的沙盒对开发人员有哪些限制？
沙盒将用户应用程序隔离在自身的安全可靠的环境中，该环境和网络服务器的硬件、系 统及物理位置完全无关，并且沙盒仅提供对基础操作系统的有限访问权限。
Google App Engine的沙盒对开发人员有哪些限制？
沙盒将用户应用程序隔离在自身的安全可靠的环境中，该环境和网络服务器的硬件、系 统及物理位置完全无关，并且沙盒仅提供对基础操作系统的有限访问权限。