---

 

七、海量数据的交互式分析工具Dremel

（一）产生背景

  Google 的团队结合其自身的实际需求，借鉴搜索引擎和并行数据库的一些技术，开发出了实时的交互式查询系统 Dremel。

Dremel支持的典型应用：

• Web 文档的分析
• Android 市场的应用安装数据的跟踪
• Google 产品的错误报告
• Google 图书的光学字符识别
• 欺诈信息的分析
• Google 地图的调试
• Bigtable 实例上的 tablet 迁移
• Google 分布式构建系统的测试结果分析
• 磁盘 I/O 信息的统计
• Google 数据中心上运行任务的资源监控
• Google 代码库的符号和依赖关系分析

（二）数据模型

两方面的技术支撑：

一方面：统一的存储平台

  实现高效的数据存储，Dremel使用的底层数据存储平台是GFS。

另一方面：统一的数据存储格式

  存储的数据才可以被不同的平台所使用。

面向记录和面向列的存储：

  Google 的 Dremel 是第一个在嵌套数据模型基础上实现列存储的系统。

• 好处一：处理时只需要使用涉及的列数据
• 好处二：列存储更利于数据的压缩

嵌套模型的形式化定义：

$$\tau =dom|⟨A_1:\tau [\ast |?],\dots ,A_n:\tau [\ast |?]⟩$$

原子类型（Atomic Type）： 原子类型允许的取值类型包括整型、浮点型、字符串等。

记录类型（Record Type）： 记录类型则可以包含多个域。记录型数据包括三种类型：必须的（Required）、可重复的（Repeated）以及可选的（Optional）。

嵌套结构的模式和实例：

  文档的模式（Schema）定义，利用该数据模型，可以使用 Java 语言，也可以使用 C++ 语言来处理数据，甚至可以用 Java 编写的 MapReduce 程序直接处理 C++ 语言产生的数据集。这种跨平台的优良特性正是 Google 所需要的。

（三）嵌套式的列存储

1、数据结构的无损表示

  如下图示，带有重复深度和定义深度的r1与r2的列存储。

  重复深度主要关注的是可重复类型，而定义深度同时关注可重复类型和可选类型（optional）。每一列最终会被存储为块（Block）的集合，每个块包含重复深度和定义深度且包含字段值。

2、高效的数据编码

  Dremel 利用图中算法创建一个树状结构，树的节点为字段的 writer，它的结构与模式中的字段层级匹配。核心的想法是只在字段 writer 有自己的数据时执行更新，非绝对必要时不尝试往下传递父节点状态。子节点 writer 继承父节点的深度值。当任意值被添加时，子 writer 将深度值同步到父节点。

  下图是计算重复和定义深度的基础算法。

3、数据重组

  Dremel 数据重组方法的核心思想是为每个字段创建一个有限状态机（FSM），读取字段值和重复深度，然后顺序地将值添加到输出结果上。

 

当前FSM	写入值	下一个重复深度值	动作
DocId（开始）	10	0	跳转至Links.Backward
Links.Backward	NULL	0	跳转至Links.Forward
Links.Forward	20	1	停留在Links.Forward
Links.Forward	40	1	停留在Links.Forward
Links.Forward	60	0	跳转至Name.Language.Code
Name.Language.Code	en-us	2	跳转至Name.Language.Country
Name.Language.Country	us	2	跳转至Name.Language.Code
Name.Language.Code	en	1	跳转至Name.Language.Country
Name.Language.Country	NULL	1	跳转至Name.Url
Name.Url	http://A	1	跳转至Name.Language.Code
Name.Language.Code	NULL	1	跳转至Name.Language.Country
Name.Language.Country	NULL	1	跳转至Name.Url
Name.Url	http://B	1	跳转至Name.Language.Code
Name.Language.Code	en-gb	0	跳转至Name.Language.Country
Name.Language.Country	gb	0	跳转至Name.Url
Name.Url	NULL	0	结束

  如果具体的查询中不是涉及所有列，而是仅涉及很少的列的话，上述数据重组的过程会更加便利，下图中仅仅涉及 DocId 和 Name.Language.Country 的有限状态机。

核心的思想如下：

  设置t为当前字段读取器的当前值f所返回的下一个重复深度。在模式树中，找到它在深度 t 的祖先，然后选择该祖先节点的第一个叶子字段 n。由此得到一个 FSM 状态变化 (f,t)->n。

有限状态机的构造算法

（四）查询语言与执行

  Dremel 的 SQL 查询输入的是一个或多个嵌套结构的表以及相应的模式，而输出的结果是一个嵌套结构的表以及相应的模式。

  Dremel 的类 SQL 语言支持嵌套子查询、记录内聚合、top-k、joins、自定义函数等操作类型。

  Dremel 利用多层级服务树（multi-level service tree）的概念来执行查询操作。

• 根服务器：接受客户端发出的请求，读取相应的元数据，将请求转发至中间服务器。
• 中间服务器：负责查询中间结果的聚集。
• 叶子服务器：负责执行数据来源。

  Dremel 中的数据都是分布式存储的，因此每一层查询涉及的数据实际都被水平划分后存储在多个服务器上。Dremel 是一个多用户系统，因此同一时刻往往会有多个用户进行查询。查询分发器有一个很重要参数，它表示在返回结果之前一定要扫描百分之多少的 tablet。

（五）性能分析

  由于 Dremel 并不开源，我们只能通过 Google 论文中的分析大致了解其性能。Google 的实验数据集规模如下图：

  MR 从面向记录转换到列状存储后性能提升了一个数量级（从小时到分钟），而使用 Dremel 则又提升了一个数量级（从分钟到秒）。

（六）小结

1. Dremel 和 MapReduce 并不是互相替代，而是相互补充的技术。在不同的应用场景下各有其用武之地。
2. Drill 的设计目标就是复制一个开源的 Dremel，但是从目前来看，该项目无论是进展还是影响力都达不到 Hadoop 的高度。
3. 希望未来能出现一个真正有影响力的开源系统实现 Dremel 的主要功能并被广泛采用。

八、内存大数据分析系统PowerDrill

（一）产生背景与设计目标

两个假设结论：

（1）绝大多数的查询是类似和一致的；
（2）存储系统中的表只有一小部分是经常被使用的，绝大部分的表使用频率不高。

考虑两方面的内容：

（1）如何尽可能在查询中略去不需要的数据分块；
（2）如何尽可能地减少数据在内存中的占用，占用越少意味着越多的数据可以被 加载进内存中处理。

PowerDrill整个系统实际分为三个部分：

（1）Web UI
（2）一个抽象层
（3）列式存储

（二）基本数据结构

  下图阐述了 PowerDrill 采用的数据结构，简单来说就是一个双层数据字典结构。

• 全局字典表：存储全局id和搜索关键字的对应关系
• 3个块的数据：块字典记录的是块 id（chunk-id）和全局 id 的映射关系；块元素记录的是块中存储数据的块 id（注意不是全局id）。

（三）性能优化

1、数据分块

（1）背景

  传统的索引对于 PowerDrill 的查询场景作用不是很大，因此一个很自然的考虑就是对数据进行分块，过滤查询中不需要的数据块来减少数据量。

（2）方法

  常见的分区方法有范围分区、散列分区等。PowerDrill 实际采用的是一种组合范围分区方法。

（3）步骤

  领域专家确定若干个划分的域 → 利用这几个域对数据进行划分 → 每个块的行数达到阈值时就停止划分。

（4）局限

  PowerDrill 采用的数据分块方法简单实用，但是由于域的确定需要领域专家，因此这种方法在实际使用中还有一定的局限性。

2、数据编码的优化

• 对于不同的块，如果我们可以确定块中不同值的数量，那么就可以根据这个数量值来选择可变的比特位来记录块 id。
• 统计一组数中不同值的个数有一个专有名词，称为 “基数估计”。
• 对于小规模的数据集，可以比较容易地统计出精确的基数。但是在大数据的环境下，精确的基数统计非常耗时，因此能保证一定精度的基数估计就可以满足实际的需求。
• 基数估计的方法很多，大多利用了散列函数的一些特性，Google 内部使用的是一种称为 Hyperloglog 的基数估计方法的变种。

3、全局字典优化

优化中主要利用两个特性：

（1）全局字典是有序的
（2）排序后的数据常常有共同的前缀

  实际使用中为了进一步减少查询中需要加载到内存的全局字典，对全局字典又进行了分块。对每个全局字典块还会维护一个布隆过滤器（bloom filter）来快速确定某个值是否在字典中。

4、压缩算法

  Google 曾经对一些主流的压缩算法做过简单的测试，如下图：

• 不管压缩算法的解压速度多快，总会消耗一定的物理资源与时间。对此PowerDrill采用了一种冷热数据分别对待的策略。
• 在冷热数据切换策略中，比较常用的是LRU算法。PowerDrill开发团队采用了启发式的缓存策略来代替原始的LRU算法。

5、行的重排

  数据压缩的算法有很多，比较常用的一种称为游程编码（Run-Length Encoding，RLE），又称行程长度编码，其好处是压缩和解压缩都非常快。

  数据重排的过程等效于著名的 TSP（旅行商）问题。两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。PowerDrill 在实际生产环境中对数据分块时选定的那几个域按照字典序进行排序来得到重排的结果。

（四）性能分析与对比

我们比较关注的两组数据：

（1）在查询过程中，平均92.41%的数据被略去，5.02%的数据会直接被缓存命中，一般仅须扫描2.66%的数据即可得到查询结果。
（2）超过70%的查询是不需要从磁盘访问任何数据的，这些查询的平均访问延迟大约是25，96.5%的查询需要访问的磁盘量不超过1GB。

性能分析与对比：

PowerDrill与Dremel的对比：

	PowerDrill	Dremel
设计目标	处理非常大量的数据集	分析少量的核心数据集
设计理念	处理的数据来自外存	处理的数据尽可能地存于内存
	未进行数据分区，分析时要扫描所有需要的列	使用了组合范围分区，分析时可以跳过很多不需要的分区
	数据通常不需要加载，增加数据很方便	数据需要加载，增加数据相对不便

九、Google应用程序引擎

（一）Google App Engine简介

什么是 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的整体架构：

• 应用管理节点 ：主要负责应用的启停和计费。
• 前端和静态文件 ：负责将请求转发给应用服务器并进行负载均衡和静态文件的传输。
• 应用服务器 ：能同时运行多个应用的运行时（Runtime）。
• 服务器群 ：提供了一些服务，主要有Memcache、Images、URLfetch、E-mail和Data Store等。

（二）应用程序环境

应用程序环境的特性：

（1）动态网络服务功能。能够完全支持常用的网络技术。
（2）具有持久存储的空间。在这个空间里平台可以支持一些基本操作，如查询、分类和事务的操作。
（3）具有自主平衡网络和系统的负载、自动进行扩展的功能。
（4）可以对用户的身份进行验证，并且支持使用 Google 账户发送邮件。
（5）有一个功能完整的本地开发环境，可以在自身的计算机上模拟 Google App Engine 环境。
（6）支持在指定时间或定期触发事件的计划任务。

沙盒的限制：

（1）用户的应用程序只能通过 Google App Engine 提供的网址抓取 API 和电子邮件服务 API 来访问互联网中其他的计算机，其他计算机如请求与该应用程序相连接，只能在标准接口上通过 HTTP 或 HTTPS 进行。
（2）应用程序无法对 Google App Engine 的文件系统进行写入操作，只能读取应用程序代码上的文件，并且该应用程序必须使用 Google App Engine 的 Data Store 数据库来存储应用程序运行期间持续存在的数据。
（3）应用程序只有在响应网络请求时才运行，并且这个响应时间必须极短，在几秒之内必须完成。与此同时，请求处理的程序不能在自己的响应发送后产生子进程或执行代码。

（三）Google App Engine服务