Dremel: 网络规模的数据集交互分析

概要

Dremel是一个可扩展的，交互式的为了只读的嵌套数据分析的临时查询系统。通过结多个层的执行树和柱状数据布局，它能够运行它能在几秒内对万亿行表的聚合查询。系统可以扩展到上千的CPU和PB级别的数据，在谷歌有上千个用户。在这篇论文中，我们描述了Dremel的实现，然后解释如何与基于Mapreduce进行互补的。我们提出了一种新的用于嵌套的列式存储表示，并讨论了在系统数千个节点实例上的实验。

1 介绍

大尺度的数据分析已经在Web公司和不同的行业广泛的渴求，尤其是因为低的存储成本，它允许收集大量的企业关键数据。把这些数据放到分析人员的以及工程师的手上已经变得越来越重要；交互响应时间通常会对数据探索对数据监控，在线客户支持，快速原型开发，数据流水线的Debug和其他的任务产生质的影响。

执行交互数据分析规模要求高度的并行性。使用今天的通用磁盘在一秒内读取1T的数据需要上千个磁盘。类似的，CPU密集型查询需要上千个核心在1秒内进行计算。在谷歌大规模的并行计算是使用共享的商用机器集群完成的。集群通常托管众多分布式应用，应用共享资源，有着广泛多样的负载，并且在不同硬件参数上的机器运行。分布式应用程序中单个工作节点可能要花费客场的时间来执行给定的任务，或者由于集群管理系统的故障或抢占而永远无法完成。因此实现快速的执行和容错处理掉队者和失败者是必要的。

web中使用的数据和科学计算通常是非关系型的。因此，弹性的数据模型在这个领域是关联。使用程序语言的数据结构，通过分布式系统进行信息交换，结构化文档等。非常适合用嵌套表示。规范化和重组web尺度的这些数据通常是令人望而却步的。在谷歌中，嵌套的数据模型是大多数结构化数据处理的基础，据报道，其他大型互联网公司也是如此。

这篇paper描述的系统叫做Dremel，它支持大数据集跨越商用机器共享集群的内部交互分析。不像传统的数据库，它能够对嵌套数据进行操作。就地（in situ）指的是在原地访问数据的能力，即在分布式文件系统中（GFS）或者其他的存储层（Bigtable）。Dremel可以执行许多这样的数据查询，它通常需要mapreduce的工作序列，但是在执行时间的一小部分。Dremel不是为了替代Mapreduce的位置它通常被用来结合分析Mapreduce流水线的输出或者快速原型更大的计算。

Rremel自从2006年投入生产环境在谷歌内部有上千的用户。Dremel的多个实例被部署在公司，范围从数十个到上千个不等。使用的系统包括了

• 爬取的web文档分析
• 追踪安卓市场应用的安装数据
• 谷歌产品的崩溃报告
• Google Book的RCR结果
• 垃圾邮件分析
• Google Map上地图的贴图调试
• 托管Bigtable实例中的平板迁移
• 测试的结果在谷歌的分布式构建的系统上运行
• 对于十万个磁盘IO统计
• 资源监控的任务运行谷歌数据中心
• 谷歌代码库的代码依赖

在分布式查询系统中，服务树（Service Tree） 是一种用于表示查询请求在分布式系统中如何分解、传递和执行的逻辑结构或拓扑。它描述了查询在不同服务组件之间的依赖关系，通常以树状的层次结构展现。服务树的核心目的是追踪和优化分布式查询的执行过程。

Dremel建立在Web搜索和并行dbms的思想上。首先它的结构借用了在分布式查询工程中服务树的概念。查询的结果是通过从树的较低级别收到的答复来组装的。第二，Dremel提供了工层的类似SQL以表达特别的查询。与Pig和Hive相反，它执行本地查询而不是转换为Mapreduce操作。

最后也是最重要的，Dremel使用了列式存储表示，它允许它读取secondary存储的少部分数据以减少CPU开销，来进行廉价的压缩。列存储已经被用于分析相关的数据，但是据我们所知还没有扩展到数据模型。通过许多谷歌的数据处理工具，包括MR，Sawzall和FlumeJava，我们提供的列式存储的格式是受支持的。

在这个论文中我们做出了如下贡献。

• 我们描述了嵌套数据的新的客户存储格式。我们提出了算法以解刨嵌套记录到行以及再次组装它们。（章节4）
• 我们概述了Dremel的查询语言和执行。俩者都被设计为在有效的在列式的条带化嵌套数据以及不需要构造嵌套记录（章5）
• 我们展示了如何使用web查询系统执行树，可以应用到数据库处理，并解释它们对于有效地回答聚合查询的好处。
• 我们展示了万亿条记录的经历，几TB的数据集，运行在1000-4000个节点上（章7）

本文的结构如下。在第2节中，我们将解释如何Dremel用于结合其他数据管理工具进行数据分析。其数据模型将在第3节中介绍。上面列出的主要贡献将在第4-8节中介绍。相关工作将在第9节讨论。第10部分是结论

2 背景

我们通过一个场景开始，它描述了查询进程如何交互来满足数据管理生态系统。假设Alice是谷歌的一个工程师，想出来一个新的注意从web页面提取信息。她运行Mapreduce来处理输入数据并且生成一个包含新信号的数据集，存储十亿条数据在分布式文件系统中。为了分析她实验的结果，她使用Dremel并且执行几个交互式的命令

DEFINE TABLE t AS /path/to/data/*
SELECT TOP(signal1, 100), COUNT(*) FROM t

她的命令几秒钟就能执行。她运行了其他几个查询来说服自己，她的算法是有效的。她在信号1中发现了不规律并且通过编写FlumeJava程序进行深入挖掘，这会执行更复杂的的分析计算在她输出的数据集上。一旦问题被解决了，它就会建立一个管道，连续处理传入的数据。她制定了几个固定的SQL查询，这些SQL在不同的维度汇聚她的结果，并且将它们添加到交互式仪表盘中。最后，它注册她新数据集到目录中，所以其他工程师可以定位和很快的进行查询。

上述的场景需要查询处理器和机器他句管理工具之间的相互操作。第一个要素是公共存储层。谷歌文件系统是一个这样的分布式存储层广泛的被使用在企业中。GFS使用复制来保存数据，尽管硬件有故障，并在存在掉队者时实现快速响应。搞性能存储层对于原位（in situ）数据管理至关重要。它允许访问数据而不需要耗时的加载阶段，在分析数据过程中这是一个使用数据库的主要障碍，在DBMS能够加载数据和执行信号查询之前，通常可以运行几十个MR分析。作为额外的好处，文件系统中的数据可以使用标准的工具方便的操纵，即为了传输到另一个集群，修改访问授权，或者根据文件名确定要分析的数据子集。

Flat relational data（扁平关系型数据）是一种简单的数据组织形式。在关系型数据库的语境中，它是指数据存储在二维表结构中，没有复杂的嵌套关系。每一行代表一个记录，每一列代表一个属性。

构建可操作数据管理组件的第二个要素是共享存储格式。列存储被证明对于平面关闭数据是成功的，但是让他为谷歌工作需要适应嵌套数据模型。图1展示了主要的想法：嵌套字段的所有制，比如A.B.C被连续的存储。因此A.B.C可以被检索而无需读取A.E，A.B.D等。我们面对的挑战是如何保存所有的结构信息，并且能够从任意列的子集中进行重建。下面我们讨论我们的数据模型以及转向算法和查询处理。

3 数据模型

在这一章节我们提出了Dremel的数据模型并且介绍了一些在之后使用的数据。数据模型起源于分布式系统的上下文中（这解释了它的名字，protocol buffer），这被广泛的用在谷歌中，并且可以作为开源实现获得。数据摸基于强类型的嵌套记录。其抽象语法为：

$$ \tau = \text{dom} | \langle A_1 : \tau{[*|?]}, \ldots, A_n : \tau{[*|?]} \rangle $$

其中$\tau$是一个院子类型或者记录类型。dom中的原子类型包括证书，浮点树，字符串等。记录包括了一个或多个的字段。记录中的字段i有一个名字$A_i$和一个可选的多重标签。重复字段(*)可能在一条记录中出现多次。它们被解释为一系列的值，即字段中出现的顺序很重要。记录中的可选字段(?)可能是缺少的。否则，一个字段是必须的，即必须出只出现一次。

为了描述，考虑图2。它描述了 定义记录类型的Document的模式，代表一个web文档。模式定义使用了具体的语法。问的那个有必须的整数DocId和可选的Links，包含其他网页的DocId的forward和backward条目。一个问的那个有多个名字，它可以是引用文档的不同URL。一个名字包含一个序列代码和（可选的）国家对。图2也展示了俩个简单的记录r1和r2，遵守模式。使用缩进概述记录结构。我们将会在下一个章节使用简单的缩进概述结构。模式中定义的字段成树形层次结构。嵌套字段的晚餐路径使用通常的点符号表示，即Name.Language.Code

嵌套的数据模型支持一种平台无关的，可扩展的机制用于在规格上序列化结构化数据。代码生成工具为编程语言（C++或Java生成绑定）。跨语言互操作性是通过使用记录的标准二进制线上表示形式来实现的。其中字段值在记录中处显示按顺序排列。其中字段值在记录中出现时按顺序排列。这样，用Java编写的MR程序可以使用来自通过C++公开数据源的记录。因此，如果记录以列式存储，快速组装它们对MR和其他数据处理工具操作非常重要。

4 嵌套的列式存储

如图1所述，我们的目标是连续的存储给定字段的所有值以提高检索效率。在这一章节中，我们解决了如下挑战：列式格式无损地表示记录结构（4.1章）。快速编码（4.2章），有效的记录组装（4.2章）。

4.1 重复和定义级别

值本身不能体现记录结构。给定一个重复字段的俩个值，我们不知道该值在什么级别重复（这些值是来自两个不同的记录，还是来自同一记录中的两个重复值）。给定一个缺失的可选字段，我们不知道哪些记录是显式定义的。因此我们引入了重复定义层次的概念，它们定义如下。作为参考，参见图3，其中总结了示例记录中所有原子字段的重复和定义级别。

复制级别。考虑图2中的字段Code它在r1中出现了三次。en-us和en出现在第一个name中，而en-gb在第三个name中。为了消除这些歧义，我们为每一个值附加一个重复级别。它告诉我们，哪个重复的字段在哪个字段路径中重复了。字段路径Name.Language.Code包含了俩个重复的字段Name和Language。因此，代码的重复级别在0-2之间；级别0表示新记录的开始。现在假设我们从上到下扫描记录r1。当我们相遇en-us，我们没有看到任何重复的字段，即重复级别为0。当我们看en，字段Language已经重复，因此重复级别为2。最后，当我们遇到‘ en-gb ’时，Name最近重复了一次（Language只在Name后面出现一次）所以重复级别是1。因此代码的重复级别r1中的值是0,2,1

可选（optional）：字段可以出现也可以不出现。

重复（repeated）：字段可以出现多次，形成一个数组。

必需（required）：字段必须出现一次。

注意r1中第二个名字，不包含任意的Code值，要确定‘ en-gb ’出现在第三个Name中而不是第二个Name中，我们在en和en-gb中添加了NULL值（见图3）。Code是Language的必须字段，所以它的确实意味着Language没有被定义。一般来说，确定嵌套记录存在的级别需要额外的信息。

定义级别：每个字段（field）在路径 p 中的值，尤其是每个 NULL 值，都有一个定义级别，用来指定路径 p 中有多少个可能未定义（因为它们是可选或重复的）的字段实际上在记录中是存在的。为了演示，观察r1没有Backward links，然而域Link已经被定义了（在级别1）。为了保护这个信息，我们添加了NULL值和定义级别1到Links.Backward列。同样地，在 r2 中，缺失的 Name.Language.Country 具有定义级别为 1，而在 r1 中，缺失的 Name.Language.Country 分别具有定义级别 2（位于 Name.Language 内）和定义级别 1（位于 Name 内）。

我们使用整数定义级别而不是is-null位以便叶子字段（如Name.Language.Country）的数据包含有关父字段出现的信息；关于这些信息如何使用的例子在4.3章。上面概述的编码保留了记录结构。我们出于篇幅原因省略了证明。

简单来说就是使用列式方式存储嵌套数据，r是重复级别，d是定义级别

编码。每个列作为一组块进行存储。每个块包含重复和定义级别（之后简称级别）和压缩字段值。NULL不是显式存储的，因为它们是由定义级别决定的。任意小于字段路径中重复和可选字段数量的定义级别都表示为NULL。定义级别不会为始终定义的值存储。类似的重复级别只有需要的时候才存储；例如，定义级别0意味着重复级别0，所以之后可以省略。事实上，图3中，DocID不需要存储级别。级别别打包成位序列。我们只是用必要的比特；例如，如果最大定义级别是3，我们使用3比特每个定义级别。

4.2 将记录拆分为列

上面我们使用列式给出了记录结构的编码。下一个我们解决的是如何有效的生产柱状条带和重复与定义级别。计算重复和定义级别的基本算法在附录A给出。该算法递归到目录结构中，并且计算每个值的级别。如之前所述，级别在字段值没有的情况下，重复和定义级别可能需要倍计算。在谷歌使用的许多数据集是洗漱的；拥有数千个字段并不罕见。给定的记录只用其中的数百个。因此我们尝试去处消失的字段越廉价越好。为了生产列条带，我们创建一个字段写入器树，其结构与模式中的字段层次结构匹配。基本思想是，只有当字段写入器有自己的数据时，才更新字段写入器，除非绝对必要，否则不要尝试在树上传播父状态。为了做到这一点子写入器从父写入器那边继承了级别。每当添加新值时，子写入器将同步到其父写入器的级别。

4.3 记录组装

对于面向记录的数据处理工具来说，有效的从列式数据中组装数据是至关重要的（即MR）。给定字段的子集，我们的目标是重建原记录，就好像它只包含选定的字段一样，所有其他的字段都被剥离了。基础的想法是这样：我们创建有限状态机（FSM）它读取字段值和每个字段的级别， 并且连续的追加值到输出记录。一个有限状态机状态对应于一个字段读取器。状态机转换被标记为重复级别。一旦读取器获取了一个值，我们查看下一个重复级别来决定下一个读取器的使用。对于每个记录，FSM从开始状态到结束状态遍历一次。

图4展示了有限状态机，它在我们运行的例子中重建了完整的记录。开始的状态是DocId。一旦DocId值读取，有限状态机转换到Links.Backward。在所有重复的Backward值都被抽干后，FSM跳向Link.Forward,等。记录的组装算法见附录B。

为了描述FSM转换是如何构建的，设l为当前字段读取器为字段f返回的下一个重复级别。从模式树的f开始，我们找到它在第l层重复的祖先，并选择该祖先中的第一个叶子字段n。这给了我们有限状态机转换$(f,l)\rightarrow n$。例如，通过让Name.Language.Country，让l=1作为下一个级别的读取。它的重复级别为1的祖先是Name，其第一个叶字段为n=Named.Url。FSM的构建算法详见附录C

如果只有字段自己需要查询，我们构建一个简单的有限状态机，它的执行更廉价。图5描述了读取字段DocId改和Name.Language.Country的FSM。图片展示了输出记录s1和s2被自动机产出。主要我们的编码和组合算法保留了字段Country原始的结构。这对于需要访问的应用程序非常重要，即第二个Name的第一个Language出现的Country。在Xpath中，这将对应于计算如下表达式的能力/Name[2]/Language[1]/Country。

5 查询语言

Dremel的查询语言是基于SQL的，被设计为有效的实现列嵌套存储。语言的定义形式不在这篇论文的范围；相反我们描述了它的特征。每个SQL语句（以及它转换成的代数运算符）接收一个或多个嵌套的表作为输入，它计划和生成嵌套的表和它的输出模式。图6展示了简单的查询它执行投射，查询和记录内的聚合。查询在图2中的表t={r1,r2}求值。使用路径表达式引用字段。虽然查询中没有记录构造函数，查询差生嵌套的结果。

为了解释查询做了什么，考虑查询操作（WHERE 子句）。把嵌套记录视为有标签的树，其中每个标签对应一个字段名。因此只有这些嵌套的记录是保留的，其中Name.URL以HTTP定义为开头。接着考虑一个投影。SELECT子句中每个标量表达式发出的值与该表达式中使用重复次数最多的输入字段嵌套级别相同。因此字符串连接表达式在输入模式中发出Name.Language.Code级别的Str值。计数表达描述了记录内的聚合。聚合已经完成，WITHIN每个Name的子记录，并且提交每个Name的Name.Language.Code的出现数量为非负64位整数（uint64）。

语言支持聚合子查询，记录和记录间聚合Top-k，连接，用户定义函数等。实验部分举例说明了一些特性。

6 查询执行

为了简化，我们讨论只读系统上下文中核心的想法。许多Dremel查询是一次聚合；因此，在下一节中，我们重点解释这些方法并将其用于实验。我们将连接，索引，更新等推迟到以后的工作中。

树架构。 Dremel使用了多级服务树来执行查询（见图7）。根服务器接收传入的查询，从表中读取元数据，路由查询到服务树中下一个级别。叶子服务和存储层好沟通或者访问磁盘上的数据。考虑一个简单的聚合查询如下。

SELECT A, COUNT(B) FROM T GROUP BY A

当跟服务接受到如上查询，它确定所有的表，即表的水平分区，它包含T并且按照如下的方式进行重写。

$$ SELECT A, SUM(c) FROM (R^1_1 UNION ALL...R_n^1)GROUP BY A $$

表$R_1^1...,R^1_n$是查询的结果，发送到节点1,...,n在服务树的第一级别：

$$ R_i^1= \text{SELECT A, COUNT(B) AS c FROM }T^1_i \text{GROUP BY A} $$

$T_i^1$是T中表的不想交划分被层级1的服务i处理。每个服务级别执行相似的写入。最终，查询达到叶子，它并行的扫描T中的tablet。在此过程中，中间服务对部分结果执行并行聚合。上面给出的执行模型非常适合返回中小型结果的聚合查询，这是非常常见的交互查询方式。大型聚合和其他查询类可能需要依赖于并行dbms和MR中已知的执行机制。

查询调度器 Dremel是一个多用户系统，即通常几个查询同时执行。一个查询调度器基于它的优先级和均衡负载来调度查询。它其他提供的重要规则是提供了容错性，当一个服务查询变得较慢于其他服务，或者tablet副本变得不可达。

每个查询数据的生产量通常大于可用于执行处理单元数，这被我们叫做槽。一个槽对应叶子服务上的执行线程。例如，一个3000个叶子节点的系统系统每个使用8个线程有24000槽。因此表跨越100000tablet，可以指派大概五个tablet到每个槽进行处理。在查询执行时，如果tablet任务需要很长的时间来处理，它会被重新调度到另一个服务。一些tablet可能需要重新调度多次。

叶子服务读取列表示中嵌套数据的条带。每个条带中的块是异步预取的；读取缓存通常达到95%的命中率。Tablet通常是三个方式复制。当叶子服务不能访问一个tablet副本，它落到了另一个副本上。

查询调度器程序使用最小tablet百分比，在返回结果之前必须对其进行扫描。我们很快就会演示，将参数设置为较低的值（98%而不是100%），通常可以明显的加速特别是使用小的复制因子时。

每个服务有内部的执行树，如图7草图中的右侧。内部的树对应着物理的查询计划，包括标量表达式评估。为大多数标量函数生成优化的、特定于类型的代码。映射-查询-聚合的执行计划包括了由一组迭代器组成，这些迭代器会同步扫描输入列并且发出聚合与带有准确的重复/定义级别注释标量函数，在查询掐尖完全绕过记录组装。细节件附录D。

• “one - pass algorithms”（单程算法、单遍算法）是一种算法设计策略。它是指在处理数据时，算法只对数据进行一次完整的遍历就能完成所需的操作或计算，而不需要多次反复地访问同一组数据。

一些Dremel查询，如top-k和count-distinct，使用已知的一次通过算法返回近似结果。

7 实验

8 观察

Dremel每个月扫描千万亿的记录。图15展示了Dremel系统一个月工作量中查询的响应时间分布，在对数尺度。如图所示，大部分的查询在10秒内执行，在交互的范围之内。一些查询达到的吞吐量接近1000亿记录每分钟在共有的集群上，在专有机器上甚至更高。上述的实验数据表明了以下结果：

• 基于扫描的查询可以在多达一万亿条记录的磁盘驻留数据集上以交互速度执行。
• 对于包含数千个数量的系统列和服务器数量的线性可伸缩性时可以实现的
• MR可以从列存储中收益就像DBMS
• 记录组装和解析是昂贵的，软件层（查询处理层之下）需要优化到直接的消费面向列的数据
• MR和查询处理可以以互相补充的方式使用；一层的输出可以作为另一层的输入。
• 在多用户环境下，大的系统可以享受到扩展的好处，它提供了更号的用户体验
• 如果教育速度相比于准确性是可以接受的，那么查询可以更早的终止，但仍然可以看到大部分的数据。
• 大规模的网络数据集可以被快速扫描。在有限的时间完成最后的百分之几是很难的。
• Dremel的代码库很密，它包括不到10w行C++，java和python代码。

9 相关工作

10 结论

我们提出了Dremel，一个用于大数据交互式分析的分布式系统。Dremel是一个定制的，可扩展的数据管理解决方案，基于简单的组件。它补充了MR范例。我们在万亿的数据，几TB的真实数据集下讨论它的性能。我们概述了Dremel的关键方面，包括存储格式，查询语言，和 执行。在未来，我们计划进行更深入的报道，如形式代数规范等领域，连接，延展机制等。