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

大家好，欢迎来到IT知识分享网。

• 数据本身不会产生价值只有经过分析才有可能产生价值

产生背景

• MapReduce特点是便携，但缺点是批量处理、效率低下，无法满足用户希望提交完请求后，在一个相对可接受的合理时间内收到返回结果的需求。
• Google的团队结合其自身的实际需求，借鉴搜索引擎和并行数据库的一些技术，开发出了实时的交互式查询系统Dremel。

Dremel简介

• Dremel 是 Google 内部开发的一个强大的交互式数据查询系统，它允许对海量数据（存储在其分布式存储系统中）进行快速而高效的分析。Dremel 能支持对 petabytes 级别的数据进行秒级响应的查询，这对于需要快速深入分析和生成报告的数据分析师和工程师来说是一个非常有用的工具。

Dremel 的一些关键特性：

1. 列式存储：Dremel 使用列式存储格式（如其开源等价物 Parquet 和 ORC），这允许它在磁盘读取方面非常高效，因为只需要读取用于查询的列而不是整行数据。
2. 分布式架构：Dremel 能够在成千上万的服务器上并行运行查询，这提供了极高的扩展性和查询性能。
3. 多级执行树：Dremel 使用一个复杂的多级执行树来分配和优化查询，这意味着查询可以分解成多个部分，在不同的服务器上并行执行，然后再将结果汇总起来。
4. 兼容SQL查询：Dremel 可以接受标准的 SQL 查询，这使得它对于有 SQL 经验的用户来说非常容易上手。
5. 即时分析：尽管处理的是海量数据，Dremel 可以提供接近实时的查询响应，这对于需要快速迭代和探索数据集的用户来说是非常宝贵的。
6. 高度优化：Dremel 的查询执行引擎进行了高度优化，包括查询计划和数据压缩，使其能够快速处理大型数据集。
7. 与其他服务的整合：Dremel 能与 Google 的其他服务和工具（如 BigQuery）紧密整合，为用户提供了一个强大的数据分析平台。

• Dremel不开源。然而，Dremel 的设计理念和技术已经激发其他类似工具的开发，比如 Apache Drill，这是一个开源的分布式系统，它采取了与 Dremel 相似的多层查询执行框架和列式数据格式。
• Google 的 BigQuery 服务在公共云上提供类似于 Dremel 的功能，使用户可以利用类似的技术进行大数据分析。

数据模型

两方面的技术支撑

• Google的数据平台需要满足通用性，不同平台之间能够很好地实现数据的交互处理
• 一方面：统一的存储平台：实现高效的数据存储，Dremel使用的底层数据存储平台是GFS
• 另一方面：统一的数据存储格式：存储的数据才可以被不同的平台所使用

面向记录和面向列的存储

• Google的Dremel是第一个在嵌套数据模型基础上实现列存储的系统。
  
  
  好处：
• 处理时只需要使用涉及的列数据
• 列存储更利于数据的压缩

嵌套模型的形式化定义

• 字符$\tau$是一个数据类型的定义，可以是原子类型，也可以是记录类型$A_i$ 代表该τ的命名，即$A_i$ 就是某个$\tau$类型的变量

• 原子类型（Atomic Type）：原子类型允许的取值类型包括整型、浮点型、字符串等
• 记录类型（Record Type）：记录类型则可以包含多个域，是使用递归方式定义的，即$\tau$能够由其余以前定义好的τ组成，就像c中的结构体，与结构体不大相同的是，每一个包含的τ的值能够有多个（*，repeated，相似c中的数组），还能够是可选的（?，optional，以前那个数组能够不包含任何元素）

嵌套结构的模式和实例

• $r1和r2$中的属性通过完整的路径表示，如Name.Language.Code
• 利用该数据模型，可以使用Java语言，也可以使用C++语言来处理数据，甚至可以用Java编写的MapReduce程序直接处理C++语言产生的数据集。这种跨平台的优良特性正是Google所需要的。

嵌套式的列存储

数据结构的无损表示

• 采用列存储有其便利之处，因为在不同列中相同位置的数据必然属于原数据库中的同一行，因此我们可以直接将每一列的值按顺序排列下来，不用引入其他的概念，也不会丢失数据信息。
  
• 嵌套式数据结构的列存储，数据本身之间的关系很复杂。存储后的数据本身反映不出任何结构上的信息，因此存储中除了记录值，还要记录结构。另外，所有的列存储在应用时往往要涉及多个列，如何按照正确的顺序快速地进行数据重组也是列存储需要解决的。

• 为了准确地在存储中反映出嵌套的结构，Dremel定义两个变量：r（Repetition Level，重复深度）和d（Definition Level，定义深度）
• 重复深度：主要关注的是可重复类型，记录该列的值是在哪一个级别上重复的
• 定义深度：同时关注可重复类型和可选类型（optional），表示“值的路径中有多少可以不被定义（因为是可重复类型或可选类型）的字段实际是有定义的”。
• 每一列最终会被存储为块（Block）的集合，每个块包含重复深度和定义深度且包含字段值。
  
• Name.Language.code的可重复深度取值为0、1和2
  0：没有重复
  1：Name重复
  2：Language重复
• 【注意】重复深度skip掉所有的非repeated类型的字段，即只有repeated类型才算作一级深度。如Links.Forward中，Forward这一级的重复深度是1。
• 带有重复深度和定义深度的r1与r2的列存储
  

高效的数据编码

• 计算重复和定义深度的基础算法
  
• Dremel利用图中算法创建一个树状结构

• 树的节点为字段的writer，它的结构与模式中的字段层级匹配。

• 核心的想法是只在字段writer有自己的数据时执行更新，非绝对必要时不尝试往下传递父节点状态。
• 子节点writer继承父节点的深度值
• 当任意值被添加时，子writer将深度值同步到父节点。

数据重组

• 数据重组：将查询涉及的列取出，然后将其按照原始记录的顺序组装起来，让用户感觉好像数据库中仅存在这些查询涉及的列一样。

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

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

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

查询语言与执行

• Dremel的SQL查询输入的是一个或多个嵌套结构的表以及相应的模式，而输出的结果是一个嵌套结构的表以及相应的模式。
  
• Dremel利用多层级服务树（multi-level service tree）的概念来执行查询操作
• 根服务器：接受客户端发出的请求，读取相应的元数据，将请求转发至中间服务器。
• 中间服务器：负责查询中间结果的聚集
• 叶子服务器：负责执行数据来源
  
• Dremel中的数据都是分布式存储的，因此每一层查询涉及的数据实际都被水平划分后存储在多个服务器上。
• Dremel是一个多用户系统，因此同一时刻往往会有多个用户进行查询。
• 查询分发器有一个很重要参数，它表示在返回结果之前一定要扫描百分之多少的tablet

性能分析

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

小结

1. Dremel和MapReduce并不是互相替代，而是相互补充的技术。在不同的应用场景下各有其用武之地。
2. Drill的设计目标就是复制一个开源的Dremel，但是从目前来看，该项目无论是进展还是影响力都达不到Hadoop的高度。