首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 服务器 > 云计算 >

论文翻阅笔记- Dremel

2012-12-17 
论文阅读笔记- Dremel作者:刘旭晖 Raymond 转载请注明出处Email:colorant at 163.comBLOG:http://blog.csd

论文阅读笔记- Dremel

作者:刘旭晖 Raymond 转载请注明出处

Email:colorant at 163.com

BLOG:http://blog.csdn.net/colorant/

更多论文阅读笔记 http://blog.csdn.net/colorant/article/details/8256145


阅读笔记Dremel: Interactive Analysis ofWebScaleDatasets

 

关键字

列存储

 

==目标问题 ==

在大规模的稀疏型结构化数据上的快速交互式Ad-hoc查询

 

==核心思想 ==

 

首先Dremel面向用户提供了一个类SQL语法的查询语言,但更重要的是它对嵌套式的结构化数据的处理方式

 

  • 使用特定结构的Column Base的存储方案,用一个三元组表示一个数据单元,这个三元组包含了这个数据单元的值,以及它在嵌套的数据结构中的层级和重复级别。结合与数据表关联的Schema定义,可以高效的表达出该数据单元在整个数据结构中的实际存储情况,具体细节请参考论文相关章节。

     

    • 在这种存储方案下,结合巧妙的算法strip部分空数据,在数据稀疏的情况下
      • 能对数据采用更简单的压缩算法
      • 能减少实际存储的数据量
      • 针对Column结构优化的检索,在无需重构数据的前提下能够实现快速检索
      • 在只检索部分域的情况下,因为按需读取(同时巧妙的算法又能构建比全表扫描更简单的扫描流程),能大量减少所需读取的数据。

         

        再有就是集群节点的工作模型

         

        • Serving Tree分层处理模型
          • 每个leaf节点只处理少量的数据,结果分层汇总到上级节点,较少的层级拓扑对于通常的大量输入/中少量输出的检索能有效处理,较多的层级拓扑则有利于处理大量输出的情况。

             

            总体上,个人理解 Dremel能在特定场合比Row base的MapReduce模式的应用快的原因,根本上来至于数据IO量的减少,辅助以大量叶结点的分层汇总结构来最大化并发处理数据。

             

            ==实现 ==

             

            Query Plan的执行不转换成Map-Reduce任务,而是由Serving Tree模型自己处理。

             

            在实现中,除了巧妙的算法实现Record和列式存储模型的快速转换外,还有各种优化,比如定义允许部分结果返回时就提前结束查询的Sample方式,牺牲适当的精度来换取速度等等

             

            适用的场合应该是针对稀疏数据,对部分数据域进行ad-hoc类分析的场合

             

            ==数据 ==

             

            Paper测试的典型数据在20-100T之间,一行(也就是一个Record)包含的域在30-1200个左右,当所需查询处理域在个位数的时候,提升的速度在3-10倍之间,基本上相当于所需读取数据量的比值除2的样子(比如相比完整的Row存储结构,读1/10的域,所花时间是1/5)

             

            当所需处理的域增加到一定程度后,Row base的MR应用的速度则会反超(按Paper的说法,取决于具体的表的结构和稀疏程度,通常在几十个(Dozens of)域(field)的情况下,速度对比会翻转)

             

            ==相关研究,项目等 ==

             

            Apache Drill :http://incubator.apache.org/drill/ Dremel的开源实现版本,看起来还仅仅处于起步阶段,计划了很多功能,但是实现的并不多,目前大概核心的代码大概只有 2K行左右的JAVA code

             

            Open Dremel :合并到Drill项目了


热点排行