Alex的个人Blog

作为数据分析中经常进行的join 操作，传统DBMS 数据库已经将各种算法优化到了极致，而对于hadoop 使用的mapreduce 所进行的join 操作，去年开始也是有各种不同的算法论文出现，讨论各种算法的适用场景和取舍条件，本文讨论hive 中出现的几种join 优化，然后讨论其他算法实现，希望能给使用hadoop 做数据分析的开发人员提供一点帮助.

Facebook 今年在yahoo 的hadoop summit 大会上做了一个关于最近两个版本的hive 上所做的一些join 的优化，其中主要涉及到hive 的几个关键特性: 值分区 , hash 分区 , map join , index ,

Common Join

最为普通的join策略，不受数据量的大小影响，也可以叫做reduce side join ,最没效率的一种join 方式. 它由一个mapreduce job 完成.

首先将大表和小表分别进行map 操作, 在map shuffle 的阶段每一个map output key 变成了table_name_tag_prefix + join_column_value , 但是在进行partition 的时候它仍然只使用join_column_value 进行hash.

每一个reduce 接受所有的map 传过来的split , 在reducce 的shuffle 阶段，它将map output key 前面的table_name_tag_prefix 给舍弃掉进行比较. 因为reduce 的个数可以由小表的大小进行决定，所以对于每一个节点的reduce 一定可以将小表的split 放入内存变成hashtable. 然后将大表的每一条记录进行一条一条的比较.

阅读全文…

Cloudera 的Hadoop World上看到的这个PPT: Hadoop and Performance,介绍了一些现在0.20 和0.23 版本性能优化的技巧，这里做个笔记

Hadoop 性能误区

• Java 很慢 Hadoop 主要的瓶颈在磁盘IO 或者网络传输上，不是cpu

在cpu 热点上，我们可以使用JNI 或者sun.misc.Unsafe

• Java 没有提供足够的系统底层的支持 JNI 跟C一样可以容许我们调用任何系统调用

我们能够集成汇编代码

• Hadoop IO 有太多层了 Linux IO调度器，ext4,XFS 的开发人员的确比我们更了解系统底层IO

每个系统都会有IO调度和文件层，那些绕开操作系统的（比如DBMS)都是为了实现移植性

阅读全文…

Facebook 在2010年4月发表了一篇在Hadoop 里面实现列储存的论文: RCFile: A Fast and Space efficient Data Placement Structure in MapReduce based Warehouse Systems.

CSDN 上面有这篇文章的一部分翻译, 它当时提出这个设想其实就是想做一个列数据库，而实现列数据库的第一步就是实现列储存，本文主要介绍当时Hive 的RCFile 的实现环境与限制，下一代Hadoop的架构对新的RCFile 产生的影响以及将来可能出现的Hadoop 列数据库计算模型的一些相关问题.

RCFile 在实现的时候主要需要满足facebook 在以下4个方面的需求:

最近一直在使用mapr版本的hadoop, 然后用的karmasphere 的eclipse plugin . 突然想找一个eclipse IDE 连接一下Cloudera 版本的方便一下操作，结果就悲剧了.

首先是各个版本的eclipse plugin 不兼容. 网上找的各种编译好的，自己编译的都是家家有本难念的经啊.什么Apache Hadoop 0.20.2 , Apache Hadoop 0.20.3 ,Apache Hadoop 0.20.5 ，Cloudera CDH CDH3 , CDHu1 , CDHu2 , eclipse 的各个版本不兼容. 花了几天的时间查看了网上的各种解决方法之后终于搞明白了到底每个版本怎么回事了.

首先，无论你的服务器上Hadoop 使用的是什么版本，你都需要下载对应的这个版本的源代码包进行编译. 你是Apache Hadoop 0.20.2 就去Apache 下0.20.2 的，你是Apache 0.21 版本的就去下0.21 版本的. 你是Cloudera CHDu.x 版本的，就去Cloudera 网站上下它的CDHu.x  版本对应的tar 包. 确保你要连接的服务器版本和你打算编译的eclipse-plugin版本是一致的.

在自己编译eclipse-plugin之前，你需要apache-ant, apache-maven, apache-ivy如果你打算编译整个包括hadoop的服务器版本并生成二进制包，你还需要apache-forrest 用来输出文档. ant,maven,forrest 的安装跟java 的安装没有区别，解压，然后添加对应的bin目录到path 变量. ivy 的安装就是添加一个apache-ivy-xxx.jar 到你的ant  安装目录下的lib 目录. 这些前提工具就算安装好了.

然后从命令行进入你解压的$hadoop_home 源代码目录, 执行ant compile-core , 这个会编译基础的hadoop-core 包. 注意如果你是在linux 下这个命令不会报错，但是如果你是windows 会报can’t run  program mvn , 在对应的build.xml 文件的42 行，你需要进入$Hadoop_home/build.xml 文件的42行，修改

         <exec  executable="mvn"  xxxxxxxxxxxxxxxxxxxxx

改成 <exec  executable="mvn.bat"  xxxxxxxxxxxxxxxxxx

如果你打算编译整个包的话对应的1230  行里面的forrest 在windows 下同样会出现这个错误.

阅读全文…

这篇文章介绍一下几个数据库的Hadoop 适配器的资料：

AsterData 和 Greenplum 虽然在2008年8月期间都宣布自己是第一个在数据库层面实现MapReduce 的厂商，但是之后双方走的路线却不尽相同. AsterData 之后走的路线还是将MapReduce层面的东西交给Hadoop 来做，并在一年之后的2009年10月宣布跟Cloudera 合作推出了第一个Hadoop 连接器. 这个连接器主要有如下特点：

• 双向连接：Hadoop 和 AsterData 互相能够保持数据的同步传输.
• SQL-MapReduce : 通过sql 可以直接调用后面的手写的mapreduce 端代码
• MapReduce 执行的时候会占用尽可能多的内存，尤其是保证中间结果尽量不写入到磁盘.

Greenplum 在今年9月的时候完成了它的第一个Hadoop 适配器，也是和Cloudera 合作开发, 不过它是单向的从HDFS 往Greenplum 导数据，仍然是通过所有集群节点并行加载. 它主要利用了机器的优势装载, 本身技术上并没有优化太多, 速度还算可以. 另外一个特点是它的适配器集成了它的Chorus , 作为数据生命周期管理的一个重要特性.

Vertica 在2009年10月与Cloudera  合作开发出了Vertica-Hadoop 集成适配器，它当时只实现了从Vertica 往Hadoop 导入数据的功能，一年之后它增强了从Hadoop 的HDFS 往Vertica 导数据的功能，从而实现了Vertica 与 Hadoop 的双向连接功能，值得一提的是，Vertica 的适配器有两个很变态的功能，一个是能从在vertica 的客户端通过sql 直接指定sql运行在hadoop 集群上, 这个跟AsterData 的SQL-MapReduce 差不多，这个过程是透明的, 他后台的适配器能自动把SQL 翻译成HiveQL 然后执行返回. 另外一个特性是它的Hadoop 连接器是直接读Vertica 的文件格式和元数据，对，数据只存储一份，不像其他的连接器实际上是数据存两份要你自己确保两份数据是同步的. (更准确的说法应该是Vertica 里面的数据是可以配置mirror的，用来提高IO并行能力和数据高可用性，Hadoop 的HDFS 的其中1到2个复制备份是直接依赖与Vertica 文件系统的, 而不像行数据库Greenplum,AsterData 那样数据在DBMS 里面和Hadoop 里面是完全不同的备份)

阅读全文…

由于列数据库在IO 读取和磁盘利用率上有优势，所以各个行数据库也纷纷提出了自己的向列数据库过度的中间储存模型，即混合储存(Hybrid Column).

在商用的混合储存出现之前，就已经有论文说明了三种不同的储存方式, 行储存，列储存，混合PAX储存.

本文将介绍三种混合存储的方式: Oracle 的混合储存，Greenplum,AsterData,Teradata的混合储存, Vertica 的混合储存.

Oracle 11g Hybrid

Oracle 在09年7月左右推出Exadata 的时候推出的新压缩模式, 也是唯一一个最接近PAX 的压缩模式. 它将数据分为Compression Unit (简写CU）, 一个CU 一般是一个Oracle 里面的extend 区块. 由16个Block 组成（可以配置大小), 然后在每个CU 的第一个Block 的头部放入压缩数值, 将所有的列中出现频率最高的数值放入Block 头部, 默认好像是只有在Oracle 自己的Exadata 里面才能用(为了赚钱嘛), 有两种压缩级别，压缩级别高的收益更小，压缩时间更长, 解压缩无影响. 如下图:

oracle 的混合压缩并不算是真正意义上的混合储存，它在读取数据的时候IO 并没有大幅减少, 它只是将更多的块放在一起提高了一点压缩率，它并不像其他的混合储存或者列储存得到的好处那么多.

阅读全文…

传统的行数据库使用的基本都是数据字典算法(Data Dictionary) 算法，或者叫标记化(tokenization)算法, 将Block 里面经常出现的相同值写在Block的头部，在实际储存值的地方用1,2,3,A,B 这种符号代替.这种算法将不同的列放在一起，所以出现相同值的概率非常低. 而行式数据库在每一列分开储存，可以针对每一列的特征使用不同的算法. 这篇文章就是介绍列数据库常用的压缩算法.

最早的列式数据库Sybase IQ  使用的是一种Decomposed 模型, 简单的将每一列分开，然后用rowid 来标记每一行的位置. 如下所示

后来的列式数据库基本上都不用rowid 来标记每一列的位置, 并且对于每一个Block 的数据一定是先计算那一列具有最高选择性（唯一值最少），然后依次以选择性来排序从而可以不使用rowid 标记行的位置.

而由于排序之后相同的值在一起的机会更大，所以压缩率也就比普通的简单列储存(也即上面介绍的Decompose模型) 的压缩率大很多倍.

阅读全文…

最早的商业列式数据库是在1995年发布的Sybase IQ , 但是一直到1999年左右才慢慢稳定到能够投入生产环境. 现在的大多数分析型数据库都是在2003-2005年从Postgresql 分支出来的. 其中尤其是Vertica 为代表的列数据库已经在大规模数据仓库环境中证明其特别为数据仓库环境设计的思路在一些领域具有竞争优势. 这篇文章解释介绍列式数据库的几大特点.

• 高效的储存空间利用率 传统的行式数据库由于每个列的长度不一，为了预防更新的时候不至于出现一行数据跳到另一个block 上去, 所以往往会预留一些空间. 而面向列的数据库由于一开始就完全为分析而存在，不需要考虑少量的更新问题，所以数据完全是密集储存的.

行式数据库为了表明行的id 往往会有一个伪列rowid 的存在. 列式数据库一般不会保存rowid.

列式数据库由于其针对不同列的数据特征而发明的不同算法使其往往有比行式数据库高的多的压缩率，普通的行式数据库一般压缩率在3：1 到5：1 左右，而列式数据库的压缩率一般在8：1到30：1 左右. (InfoBright 在特别应用可以达到40:1 , Vertica 在特别应用可以达到60:1 , 一般是这么高的压缩率都是网络流量相关的)

列式数据库由于其特殊的IO 模型所以其数据执行引擎一般不需要索引来完成大量的数据过滤任务(Sybase IQ 除外) . 这又额外的减少了数据储存的空间消耗.

列式数据库不需要物化视图,行式数据库为了减少IO 一般会有两种物化视图，常用列的不聚合物化视图和聚合的物化视图. 列式数据库本身列是分散储存所以不需要第一种，而由于其他特性使其极为适合做普通聚合操作.(另外一种物化视图是不能实时刷新的，比如排名函数,不规则连接connect by 等等，这部分列数据库不包括.)

阅读全文…