ACM通信

研究突出了

网络尺度数据集的交互分析

文/ Sergey Melnik, Andrey Gubarev, jingjing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis
ACM通信，2011年6月，第54卷第6期，第114-123页
10.1145/1953122.1953148
评论(1)

Dremel是一个可扩展的交互式临时查询系统，用于分析只读嵌套数据。通过结合多级执行树和柱状数据布局，它能够在几秒钟内对万亿行表运行聚合查询。该系统可扩展到数千个cpu和pb级的数据，谷歌上有数千个用户。在本文中，我们描述了Dremel的体系结构和实现，并解释了它如何补充基于mapreduce的计算。我们提出了一种新的用于嵌套记录的柱状存储表示，并讨论了在系统的几千个节点实例上的实验。

回到顶部

1.简介

大规模分析数据处理已经在Web公司和各行各业中得到广泛应用，尤其是由于低成本存储能够收集大量关键业务数据。将这些数据放在分析师和工程师的指尖已经变得越来越重要;交互响应时间通常会在数据探索、监视、在线客户支持、快速原型、数据管道调试和其他任务中产生质的差异。

大规模执行交互数据分析需要高度的并行性。例如，在1秒内从二级存储读取1 tb的压缩数据将需要10,000多个普通磁盘。类似地，cpu密集型查询可能需要在数千个内核上运行才能在几秒钟内完成。在谷歌，大规模并行计算是使用商用机器的共享集群完成的。⁵集群通常承载许多分布式应用程序，这些应用程序共享资源，具有不同的工作负载，并且运行在具有不同硬件参数的机器上。分布式应用程序中的单个工作人员执行给定任务的时间可能比其他工作人员长得多，或者可能由于集群管理系统的失败或抢占而永远无法完成。因此，处理掉队者和失败对于实现快速执行和容错是必不可少的。

Web和科学计算中使用的数据通常是非关系型的。因此，在这些领域中灵活的数据模型是必不可少的。编程语言中使用的数据结构、分布式系统交换的消息、结构化文档等，都很自然地适合于嵌套的表示。在Web规模上对这些数据进行规范化和重组通常是禁止的。在谷歌中，嵌套数据模型是大多数结构化数据处理的基础²²据报道，其他大型网络公司也是如此。

本文描述了一个叫做Dremel的系统^一个它支持在共享的商品机器集群上对非常大的数据集进行交互式分析。与传统数据库不同，它能够操作原地嵌套的数据。原位指的是“就地”访问数据的能力，例如，在分布式文件系统中(如谷歌文件系统(GFS))¹⁴)或其他存储层(例如，Bigtable⁹)．Dremel可以对这样的数据执行许多查询，而这些查询通常需要MapReduce (MR¹²)，但只需要一小部分的执行时间。Dremel并不打算作为MR的替代品，它经常与它一起用于分析MR管道的输出或快速原型大型计算。

Dremel自2006年以来一直在生产，谷歌中有数千个用户。公司中部署了多个Dremel实例，从数万到数千个节点不等。系统使用示例如下:

• 分析爬取的Web文档
• 跟踪Android Market上应用程序的安装数据
• 谷歌产品崩溃报告
• OCR结果来自谷歌Books
• 垃圾邮件分析
• 调试谷歌地图上的贴图
• 托管Bigtable实例中的平板迁移
• 在谷歌的分布式构建系统上运行的测试结果
• 数十万个磁盘的磁盘I/O统计信息
• 在谷歌的数据中心中运行的作业的资源监视
• 谷歌代码库中的符号和依赖项

Dremel基于Web搜索和并行dbms的思想构建。首先，它的架构借鉴了分布式搜索引擎中使用的服务树的概念。¹¹就像Web搜索请求一样，查询被下推到树中并在每一步重新编写。通过聚合从树的较低级别收到的答复来组装查询的结果。其次，Dremel提供了一种高级的、类似sql的语言来表示特别查询。相比之下，像Pig这样的图层¹⁹蜂巢,¹⁶它本机执行查询，而不将它们转换为MR作业。

最后，同样重要的是，Dremel使用了列条纹存储表示，这使它能够从二级存储读取更少的数据，并由于更便宜的压缩而降低CPU成本。列存储用于分析关系数据¹但据我们所知，还没有扩展到嵌套数据模型。我们介绍的柱状存储格式在谷歌上得到了许多数据处理工具的支持，包括MR、Sawzall、²¹和FlumeJava。⁸

在本文中，我们做出了以下贡献:

• 我们为嵌套数据描述了一种新的柱状存储格式。我们介绍了将嵌套记录分解为列并重新组合它们的算法(第4节)。
• 我们概述了Dremel的查询语言和执行。这两种设计都是为了在列条纹嵌套数据上高效地运行，并且不需要重构嵌套记录(第5节)。
• 我们将展示如何将Web搜索系统中使用的执行树应用于数据库处理，并解释它们在高效回答聚合查询方面的好处(第6节)。
• 我们在10004000个节点上运行的系统实例上进行了万亿记录、多tb数据集的实验(章节7)。

本文的结构如下。在第2节中，我们将解释如何将Dremel与其他数据管理工具结合使用进行数据分析。它的数据模型在第3节中介绍。上文所列的主要贡献见第48节。相关工作将在第9节中讨论。第10节为结论部分。

回到顶部

2.背景

我们首先介绍一个场景，演示交互式查询处理如何适用于更广泛的数据管理生态系统。假设谷歌的工程师Alice提出了一个从Web页面中提取新类型信号的新想法。她运行一个MR作业，通过输入数据生成一个包含新信号的数据集，这些数据集存储在分布式文件系统的数十亿条记录中。为了分析她的实验结果，她启动了Dremel并执行了几个交互命令:

她的命令几秒钟就能执行。她检查查询返回的100个最频繁的信号。她运行其他查询，寻找将她的信号集成到Web搜索中的方法。一旦她找到足够的线索，她就会建立一个管道来连续处理输入数据，并将其输入到另一个MR或服务系统。她制定了一些固定的SQL查询，这些查询将管道跨各个维度的结果聚合在一起，并将它们添加到一个交互式仪表板中。最后，她将新数据集注册到一个目录中，以便其他工程师可以快速定位和查询。

上述场景需要查询处理器和其他数据管理工具之间的互操作。第一个成分是常见的存储层．GFS¹⁴就是这样一种广泛应用于公司的分布式存储层。GFS使用复制来保存数据，尽管硬件有故障，并在出现散点时实现快速响应。高性能存储层对于现场数据管理至关重要，因为它允许访问数据而不需要耗时的加载阶段。另外一个好处是，可以使用标准工具方便地操作文件系统中的数据，例如，将数据传输到另一个集群、更改访问权限或根据文件名识别数据子集进行分析。

构建可互操作的数据管理组件的第二个要素是共享的存储格式．列存储被证明对平面关系数据是成功的，但要使它在谷歌上工作，需要使它适应嵌套数据模型。图1说明了主要思想:嵌套字段(如A.B.C)的所有值都是连续存储的。因此，可以在不读取A.E、A.B.D等的情况下检索A.B.C。我们要解决的挑战是如何保存所有的结构信息，并能够从字段的任意子集重建记录。接下来我们讨论我们的数据模型，然后转向算法和查询处理。

回到顶部

3.数据模型

在本节中，我们介绍Dremel的数据模型，并介绍后面使用的术语。数据模型起源于分布式系统的上下文中(这解释了它的名字，“协议缓冲区”)²²)在谷歌上广泛使用，并且可以作为一个开源实现获得。数据模型基于强类型嵌套记录。它的抽象语法由:

在哪里T是原子类型或记录类型。原子类型dom包含整数、浮点数、字符串等。记录由一个或多个字段组成。场我在记录中有一个名字一个_我和多重标签。重复字段(标签“*”)可以在一条记录中出现多次;字段出现的顺序很重要。可选字段(标签“?”)可能从记录中丢失。否则，字段为要求，也就是说，必须恰好出现一次。

为了说明这一点,看看图2．它描述了定义记录类型Document(表示Web文档)的模式。模式定义使用协议缓冲区中的具体语法。²²文档有一个必需的整数Docld和可选的链接，其中包含一个向前和向后条目列表，其中包含其他Web页面的文档。文档可以有多个名称，这些名称是可以引用文档的不同url。Name包含Code和(可选)Country对的序列。图2还显示了两个样本记录，r₁而且r₂，符合图式。记录结构是用缩进勾画的。在下一节中，我们将使用这些示例记录来解释算法。模式中定义的字段形成了一个树层次结构。完整的路径用常用的点表示法表示，例如，Name.Language.Code．

嵌套数据模型支持平台无关的、可扩展的机制，用于在谷歌上序列化结构化数据。代码生成工具为编程语言(如c++或Java)生成绑定。跨语言互操作性是通过使用记录的标准二进制在线表示实现的，其中字段值在记录中出现时按顺序排列。通过这种方式，用Java编写的MR程序可以使用通过c++库公开的数据源中的记录。

回到顶部

4.嵌套列存储

见图1，我们的目标是连续存储给定字段的所有值，以提高检索效率。然而，列数据最终可能会被诸如mr这样的面向记录的工具所使用。因此，我们需要一种方法从任何给定的列子集有效地组装记录。在本节中，我们将解决以下挑战:以柱状格式(第4.1节)无损表示记录结构，快速编码(第4.2节)和高效的记录组装(第4.3节)。

4.1.重复和定义级别

在图2，我们看到两份文件被表示为记录。对比那些图3．它以柱状格式描述相同的数据。每个字段的值按顺序存储为一个单独的条带。对于每个值，我们保留额外的信息a重复水平和一个定义水平(图中简称为r和d)。这些信息编码了记录的结构。

我们使用的例子来解释我们的编码的名字。语言。代码在图4．图的右侧显示了记录的扁平表示r₁而且r₂获得如下。首先，除去Name以外的所有字段，语言,代码．其次，我们将剥离的记录表示为根到叶路径的列表。下标表示各自字段在其外围记录中的位置。

(重复级，定义级)对表示δ在两条连续的路径之间p_我1而且p_我．的重复级编码公共前缀的长度pⁱ¹和p_我，定义级别编码的长度p_我的长度p_我的后缀)。例如，前两条路径的公共前缀图4是r₁. name₁长度是2。

路径长度编码紧凑如下。两个连续路径的公共前缀总是以一个重复字段结束，因此我们将重复级别定义为公共前缀中重复字段的数量(包括标识记录的第一个路径元素)。定义级别指定路径中可选和重复字段的数量(不包括第一个路径元素)。我们不计算必需字段，因为它们总是存在的。小于路径中重复和可选字段的最大数量的定义级别表示NULL。例如，的最大定义级别Name.Language.Code是2。

上面概述的编码无损地保留了记录结构。由于篇幅的原因，我们省略了证明。

平板电脑布局:一张桌子被储存为一组药片。一个平板电脑是一个独立的水平分区的表。图5演示平板电脑的布局。除了实际数据之外，平板还包含模式和额外的元数据，其中包括键的规范、排序顺序、值范围等。

每一列都存储为一组块。每个块包含重复和定义级别(从今以后简称为级别)和压缩字段值。null不显式存储，因为它们是由定义级别确定的。定义级别不会为始终定义的值存储。类似地，重复级别只在需要时才存储;例如，定义级别0意味着重复级别0，因此后者可以省略。事实上,在图3，没有存储的级别Docld．关卡被包装成位序列。我们只使用必要的比特数;例如，如果最大定义级别为3，则每个定义级别使用2位。

4.2.将记录拆分为列

在上面，我们以柱状格式给出了记录结构的编码。我们要解决的下一个挑战是如何有效地生成具有重复和定义级别的列条纹。

Melnik等人给出了计算重复和定义级别的算法。¹⁸该算法重复到记录结构中，并为每个字段值计算级别。如前所述，即使缺少字段值，也可能需要计算重复和定义级别。谷歌使用的许多数据集都是稀疏的;具有数千个字段的模式并不罕见，但在给定的记录中只使用其中的100个字段。因此，我们试图尽可能便宜地处理缺失的字段。要生成列条纹，我们创建的树领域的作家，其结构与模式中的字段层次结构相匹配。基本思想是只有当字段编写器有自己的数据时才更新字段编写器，除非绝对必要，否则不要尝试沿着树传播父状态。

4.3.记录装配

高效地从柱状数据组装记录对于面向记录的数据处理工具(如MR)至关重要。给定一个字段子集，我们的目标是重建原始记录，就好像它们只包含所选的字段，去掉所有其他字段一样。关键思想是我们创建一个有限状态机(FSM)，它读取每个字段的字段值和级别，并按顺序将值附加到输出记录。FSM状态对应于每个选中字段的字段读取器。状态转换用重复级别标记。一旦读取器获取了一个值，我们就查看下一个重复级别，以决定下一个读取器要使用什么。对于每个记录，FSM从开始状态遍历到结束状态一次。

图6在我们运行的例子中显示了一个重建完整记录的FSM。启动状态为Docld．一次Docld值时，FSM转换为链接。落后的．毕竟重复落后的值已被清空时，FSM跳转到链接。向前等。

如果只需要检索字段的子集，我们构造一个执行成本更低的更简单的FSM。图7描述了一个用于读取字段Docld和的FSM的名字。语言。国家．该图显示了输出记录s₁和s₂由机器人生产。注意，我们的编码和汇编算法保留了字段Country的封闭结构。这对于需要访问的应用程序很重要，例如，要访问以第二个名称的第一语言显示的国家。在XPath中，这对应于计算/Name[2]/Language[1]/Country这样的表达式的能力。

记录组装和FSM构造的细节见Melnik等人。¹⁸

回到顶部

5.查询语言

Dremel的查询语言基于SQL，并设计为可在柱状嵌套存储上高效实现。正式定义语言超出了本文的讨论范围;相反，我们说明了它的味道。每个SQL语句(以及它转换为的代数运算符)都将一个或多个嵌套表及其模式作为输入，并生成一个嵌套表及其输出模式。图8描述执行投影、选择和记录内聚合的示例查询。查询在表上求值t= {r₁，r₂}从图2．使用路径表达式引用字段。查询产生一个嵌套的结果，尽管查询中没有记录构造函数。

为了解释查询的功能，考虑选择操作(WHERE子句)。可以将嵌套记录看作标记树，其中每个标签对应一个字段名。选择操作符删除树中不满足指定条件的分支。因此，只有那些嵌套的记录被保留在那里的名字。Url定义并以http开始。接下来,考虑投影。SELECT子句中的每个标量表达式发出的值与该表达式中使用的最重复输入字段的嵌套级别相同。因此，字符串连接表达式发出Str的价值水平Name.Language.Code在输入模式中。COUNT表达式演示了记录内聚合。聚合是在每个Name子记录内进行的，并发出出现的次数Name.Language.Code每个Name作为非负的64位整数(uint64)。

该语言支持嵌套子查询、记录间和记录内聚合、top-k、连接、用户定义函数等;其中一些特性在实验部分进行了举例说明。

回到顶部

6.查询执行

为了简单起见，我们将在只读系统的上下文中讨论核心思想。许多Dremel查询是一遍聚合;因此，我们将重点解释这些内容，并在下一节的实验中使用它们。我们将联接、索引、更新等的详细讨论推迟到以后的工作中进行。

树架构:Dremel使用服务树执行查询(参见图9)．它的目的有两个:

1. 使查询调度和聚合并行化
2. 提供容错能力并处理掉队者

根服务器接收传入的查询，从表中读取元数据，并将查询路由到服务树中的下一层。叶子服务器与存储层通信或访问本地磁盘上的数据。

考虑下面一个简单的聚合查询:

当根服务器接收到上述查询时，它将确定包含的所有平板电脑T并将查询重写如下:

表R¹₁.．.R¹_n查询的结果是否发送到节点1，…，n在服务树的第1层:

T¹_我片剂是否有不连贯的分区T处理服务器我在1级。每个服务级别执行类似的重写。最终，查询到达树叶，树叶扫描平板电脑T并行执行。在上升过程中，中间服务器执行部分结果的并行聚合。上面介绍的执行模型非常适合于返回小型和中型结果的聚合查询，这是一种非常常见的交互式查询。该模型还可以很好地使用已知的单遍算法计算近似结果，如top-k和count-distinct算法(例如，参见Bar-Yossef等人)。⁴)．

在一次走刀聚合:Dremel支持超越一次聚合的查询处理机制。设计这些机制也是为了利用服务树体系结构。例如，执行连接大型分区表与小型用户定义表的查询的一种方法是向每个叶服务器发送小表的副本。这种策略称为广播连接。服务树通过在树中并行地传播小表来有效地支持这种查询。

另一个例子是，重新分区数据的连接(类似于MR的“洗牌”阶段)维持了大量的分布式执行状态。服务树有助于有效地聚合它们的执行状态。最后但并非最不重要的是，SELECT-INTO操作将查询结果作为新表保存在DFS中。服务树监视分布式写操作并确保成功完成。我们发现，服务树是一个有用的构建块，可以补充现有的分布式查询处理算法。

查询调度程序:Dremel是一个多用户系统，也就是说，通常会同时执行几个查询。查询调度程序根据查询的优先级调度查询并平衡负载。它的另一个重要作用是提供容错当一个服务器变得比其他服务器慢很多，或者一个平板电脑副本变得不可访问。

每个查询中处理的数据量通常大于可执行的处理单元的数量，我们称之为槽．插槽对应于叶服务器上的执行线程。例如，一个由3,000个叶服务器组成的系统，每个叶服务器使用8个线程，它有24,000个插槽。因此，一个包含100,000片药片的表可以通过将大约5片药片分配到每个槽位来处理。在查询执行期间，查询调度程序计算片剂处理时间的直方图。如果一台平板电脑的处理时间过长，它就会在另一台服务器上重新调度。有些平板电脑可能需要多次重新调度。

叶服务器以柱状表示方式读取嵌套数据的条纹。每个条带中的块是异步预取的;预读缓存通常达到95%的命中率。平板电脑通常有三种复制方式。当叶子服务器无法访问一个平板副本时，它将切换到另一个副本。

查询调度程序遵循一个参数，该参数指定在返回结果之前必须扫描的药片的最小百分比。我们很快就会演示，将该参数设置为较低的值(例如，98%而不是100%)通常可以显著加快执行速度，特别是在使用较小的复制因子时。

每个服务器都有一个内部执行树，如右侧所示图9．内部树对应于一个物理查询执行计划，包括标量表达式的求值。为大多数标量函数生成优化的特定于类型的代码。项目选择-聚合查询的执行计划由一组迭代器组成，这些迭代器同步扫描输入列，并发出带有正确重复和定义级别注释的聚合和标量函数的结果，在查询执行期间完全绕过记录程序集。详情请参见梅尔尼克等人。¹⁸

回到顶部

7.实验

在本节中，我们将评估Dremel在谷歌中使用的几个数据集上的性能，并检查用于嵌套数据的柱状存储的有效性。数据集的性质总结在图10．在未压缩、未复制的形式下，它们约占1拍字节的空间。除了一个双向复制表外，所有表都是三向复制的，并且包含100K到800K的片剂。我们首先检查单台机器上的数据访问特性，然后展示柱状存储如何有利于MR执行，最后关注Dremel的性能。实验是在两个数据中心中运行的系统实例上进行的，旁边是许多其他应用程序，在正常的业务操作期间。除非另有说明，否则执行时间是五次运行的平均值。下面使用的表和字段名是匿名的。

本地磁盘:在第一个实验中，我们通过扫描表的1GB片段，研究了柱状存储与面向记录存储的性能权衡T₁包含约300K行(参见图11)．数据存储在本地磁盘上，以压缩柱状表示约占用375MB。面向记录的格式使用更重的压缩，但在磁盘上产生的大小大致相同。实验是在一台双核Intel机器上进行的，磁盘提供70MB/s的读带宽。所有报告的时间都是冰冷的;每次扫描前都刷新操作系统缓存。

该图显示了五个图形，说明了为字段的一个子集读取和解压缩数据、组装和解析记录所需的时间。图(a)(c)概述了柱状存储的结果。这些图中的每个数据点是通过30次运行的测量结果的平均值得到的，在每一次运行中，随机选择一组具有给定基数的列。图(a)显示了读取和解压缩时间。图(b)添加了从列组装嵌套记录所需的时间。图(c)显示了将记录解析为强类型c++数据结构所需的时间。图(d)和(e)描述了从面向记录的存储中访问数据所需的时间，有或没有解析。

该实验的主要结论如下:当读取的列数很少时，柱状表示的增益约为一个数量级。柱状嵌套数据的检索时间随字段的数量线性增长。记录程序集和解析都是昂贵的，每一个都可能使执行时间加倍。我们在其他数据集中也观察到类似的趋势。一个自然要问的问题是，记录型存储何时开始优于列型存储。根据我们的经验，交叉点通常位于几十个字段，但它在不同的数据集上不同，并取决于是否需要记录汇编。

上钻和小孔先生:接下来，我们演示了柱状数据和面向记录数据的MR和Dremel执行。我们考虑访问单个字段的情况，即性能提高最显著。的结果可以推断多个列的执行时间图11．在这个实验中，我们计算一个字段中术语的平均数量txtField的表T₁．MR执行是使用以下Sawzall完成的²¹计划:

记录的数量存储在变量中numRecs．对于每条记录，numWords都按中的术语数量递增input.txtField返回的CountWords函数。程序运行后，平均术语频率可以计算为numWords/numRecs。在SQL中，这个计算表示为:

图12显示了两个MR作业和Dremel在对数尺度上的执行时间。两个MR工作都需要3000名工人。类似地，一个3000节点的Dremel实例用于执行Query问₁．Dremel和列上mr读取压缩柱状数据约0.5TB，而记录上mr读取87TB。如图所示，MR通过从面向记录的存储切换到柱状存储(从小时切换到分钟)，获得了一个数量级的效率。另一个数量级(从分钟到秒)是通过使用Dremel实现的，它消除了启动MR作业、调度50万个任务和组装记录的开销。

服务拓扑树:在下一个实验中，我们将展示服务树深度对查询执行时间的影响。我们考虑表上的两个GROUP BY查询T₂，它有240亿个嵌套记录。每个记录都有一个重复的字段项，其中包含一个数字数量。场项目。一个mount occurs about 40 billion times. The first query sums up the item amount by country:

它返回几百条记录并读取大约60GB的压缩数据。第二个查询在具有选择条件的文本字段域中执行GROUP BY。它的读取容量约为180GB，产生约110万个不同的域:

图13显示每个查询的执行时间作为服务器拓扑的函数。在每个拓扑中，叶服务器的数量保持在2900，以实现相同的累积扫描速度。在两级拓扑(1:19 00)中，单个根服务器直接与叶子服务器通信。对于三个级别，我们使用1:100:2900设置，即额外的100个中间服务器级别。四级拓扑为1:10:100:2900。

实验表明，返回许多群体的聚集从更深的服务树中受益。使用两个级别不是很有效，因为根服务器需要几乎按顺序聚合从数千个节点接收到的结果。添加第四个关卡将使执行时间减半问_3.由于增加了并行性，但没有好处问₂，它返回一个小的结果。

每片直方图:为了更深入地研究查询执行期间发生的事情，请考虑以下问题图14．该图显示了叶服务器在特定运行时处理平板电脑的速度问₂而且问_3.．时间是从计划在可用插槽中执行平板电脑的点开始测量的，也就是说，不包括在作业队列中等待的时间。这种度量方法排除了同时执行的其他查询的影响。每个直方图下的面积对应100%。如图所示，99%的问₂(或问_3.)片在1 s(或2 s)内加工。

Within-Record聚合:作为另一个实验，我们检查Query的性能问₄在表上运行T_3.．该查询说明了记录内的聚合:它计算记录中出现的a.b.c.d值的总和大于a.b.p.q.r值的总和的所有记录。这些字段在不同的嵌套级别重复。由于列分条，只从磁盘读取13GB(从70TB中读取)，查询在15秒内完成。如果不支持嵌套，则在T_3.会非常昂贵。

可伸缩性:下面的实验演示了系统在万亿记录表上的可伸缩性。查询问₅下图选择了表中出现次数最多的20个辅助T₄．该查询扫描4.2TB的压缩数据。

该查询是使用系统的四个配置执行的，范围从1000到4000个节点。执行时间到了图15．在每次运行中，总CPU时间几乎相同，大约为300K秒，而用户感知的时间随着系统大小的增长而几乎线性地减少。这一结果表明，就资源使用而言，较大的系统可以与较小的系统一样有效，但允许更快的执行。

流浪汉:我们最后的实验展示了掉队者的影响。查询问₆下面是在一个万亿行表上运行的T₅．与其他数据集相比，T₅是双向复制。因此，掉队者减慢执行的可能性更高，因为重新安排工作的机会更少。

查询问₆读取超过1TB的压缩数据。检索字段的压缩比约为10。表示在图16， 99%的片剂每个槽的处理时间在5秒以下。然而，当在一个2500节点的系统上执行时，一小部分平板电脑花费的时间要长得多，将查询响应时间从不到一分钟降低到几分钟。下一部分总结了我们的实验发现和我们得到的教训。

回到顶部

8.观察

德雷梅尔每月扫描千万亿的记录。图17以对数尺度显示了一个Dremel系统的典型月工作负载中的查询响应时间分布。如图所示，大多数查询在10秒内处理，处于交互范围内。某些查询在共享集群上实现了接近每秒1000亿条记录的扫描吞吐量，在专用机器上甚至更高。以上实验数据表明:

• 基于扫描的查询可以在磁盘驻留数据集上以交互速度执行，数据集最多可达一万亿条记录。
• 对于包含数千个节点的系统，列和服务器数量上的近似线性可伸缩性是可以实现的。
• MR可以像DBMS一样从柱状存储中受益。
• 极端规模的并行dbms可以像搜索引擎一样从服务树体系结构中受益。
• 记录汇编和解析是昂贵的。软件层(超出查询处理层)需要进行优化，以直接使用面向列的数据。
• MR和查询处理可以互补使用;一层的输出可以提供另一层的输入。
• 在多用户环境中，更大的系统可以从规模经济中受益，同时提供质量更好的用户体验。
• 大量web规模的数据集可以快速扫描。在有限的时间内完成最后的百分之几是很困难的。

Dremel的代码库非常密集;它由少于100K行的c++、Java和Python代码组成。第一个版本由Andrey Gubarev作为20%的项目建造。

回到顶部

9.相关工作

的先生¹²框架的设计是为了在长时间运行的批处理作业上下文中解决大规模计算的挑战。与MR一样，Dremel提供了容错执行、灵活的数据模型和现场数据处理功能。MR的成功带来了广泛的第三方实现(尤其是开源Hadoop)¹⁵)，以及许多将并行dbms与MR结合起来的混合系统，由Aster、Cloudera、Greenplum和Vertica等供应商提供。HadoopDB,^3.是这个混合范畴中的一个研究系统。最近的文章^13，23对比MR和并行dbms。我们的工作强调了两种范式的互补性。

德梅尔是为大规模运作而设计的。尽管可以想象并行dbms可以扩展到数千个节点，但我们还不知道有任何已发表的工作或行业报告尝试这样做。我们也不熟悉以往研究磁流变柱状存储的文献。

我们对嵌套数据的柱状表示建立在可以追溯到几十年前的思想之上:将结构与内容分离，并将表示转换。Abadi等人最近对列存储(包括压缩和查询处理)的工作进行了回顾。¹许多商业dbms支持使用XML存储嵌套数据(例如O’neil等人)。^20.)．XML存储模式试图将结构与内容分离，但由于XML数据模型的灵活性，它面临更多挑战。使用柱状XML表示的一个系统是XMill。¹⁷XMill是一个压缩工具。它存储所有组合字段的结构，不适合对列进行选择性检索。

Dremel中使用的数据模型是Abiteboul等人讨论的复杂值模型和嵌套关系模型的变体。²德梅尔的查询语言建立在Colby，¹⁰它引入了一种在访问嵌套数据时避免重构的语言。相比之下，在XQuery和面向对象的查询语言中通常需要重构，例如，使用嵌套的for循环和构造函数。我们不知道Colby的实际实现。¹⁰最近一种用于嵌套数据的类sql语言是Pig Latin。¹⁹用于并行数据处理的其他系统包括Scope⁷DryadLINQ,²⁴钱伯斯等人对此进行了更详细的讨论。⁸

回到顶部

10.结论

我们提出了Dremel，一个用于大型数据集交互分析的分布式系统。Dremel是由更简单的组件构建的自定义、可伸缩的数据管理解决方案。它是MR范式的补充。我们讨论了它在万亿记录、多tb的真实数据集上的性能。该系统在谷歌被广泛使用，并作为BigQuery的基础，⁶以预览模式启动的产品。我们概述了Dremel的关键方面，包括其存储格式、查询语言和执行。未来，我们计划更深入地讨论形式化代数规范、连接、可扩展性机制等领域。

回到顶部

鸣谢

Dremel从谷歌的许多工程师和实习生的投入中获益匪浅，特别是Craig Chambers, Ori Gershoni, Rajeev Byrisetti, Leon Wong, Erik Hendriks, Erika Rice Scherpelz, Charlie Garrett, Idan Avraham, Rajesh Rao, Andy Kreling, Li Yin, Madhusudan Hosaagrahara, Dan Belov, Brian Bershad, Lawrence You, Rongrong Zhong, Meelap Shah, Nathan Bales, Ju-yi Kuo, Ovidiu Platon, Nick Kline, Matthew Weaver, Dan Delorey和Jinyuan Li。我们感谢Gerhard Weikum对通信篇文章。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2011 ACM, Inc.

---

评论

---

显示1评论