盘点SQL on Hadoop中用到的主要技术

执行效率

　　即使有了高效的执行计划，如果在运行过程本身效率较低，那么再好的执行计划也会大打折扣。这里主要关注CPU和IO方面的执行效率。

CPU

　　在具体的计算执行过程中，低效的cpu会导致系统的瓶颈落在CPU上，导致IO无法充分利用。在一项针对Impala和Hive的对比时发现，Hive在某些简单查询上（TPC-H Query 1）也比Impala慢主要是因为Hive运行时完全处于CPU bound的状态中，磁盘IO只有20%，而Impala的IO至少在85%。

　　在SQL on Hadoop中出现CPU bound的主要原因有以下几种：

• 大量虚函数调用：这个问题在多处出现，比如对于a + 2 * b之类的表达式计算，解释器会构造一个expression tree，解释的过程就是递归调用子节点做evaluation的过程。又比如以DAG形式的operator/task在执行的过程中，上游节点会层层调用下游节点来获取产生的数据。这些都会产生大量的调用。
• 类型装箱：由于表达式解释器需要对不同数据类型的变量做解释，所以在Java中需要把这些本来是primitive的变量包装成Object，累积起来也消耗不少资源。这算是上面一个问题附带出来的。
• branch instruction： 现在的CPU都是有并行流水线的，但是如果出现条件判断会导致无法并行。这种情况可能出现在判断数据的类型（是string还是int），或者在判断某一列是否因为其他字段的过滤条件导致本行不需要被读取（列存储情况下）。
• cache miss：每次处理一行数据的方式导致cpu cache命中率不高。（这么说已经暗示了解决方案）

　　一个方法是动态代码生成，也就是不使用解释性的统一代码。比如a + 2 * b这个表达式就会生成对应的执行语言的代码，而且可以直接用primitive type，而不是用固定的解释性代码。具体实现来说，JVM系的如Spark SQL，Presto可以用反射，C++系的Impala则使用了llvm生成中间码。对于判断数据类型造成的分支判断，动态代码的效果可以消除这些类型判断，还可以展开循环，可以对比下面这段代码，左边是解释性代码，右边是动态生成代码。

　　另一个方法是vectorization（向量化），基本思路是放弃每次处理一行的模式，改用每次处理一小批数据（比如1k行），当然前提条件是使用列存储格式。这样一来，这一小批连续的数据可以放进cache里面，cpu不仅减少了branch instruction，甚至可以用SIMD加快处理速度。具体的实现参考下面的代码，对一个long型的字段增加一个常量。通过把数据表示成数组，过滤条件也用selVec装进数组，形成了很紧凑的循环：

[js] view plaincopy

1. add(int vecNum, long[] result, long[] col1, int[] col2, int[] selVec)   
2. {     
3.   if (selVec == null)     
4.      for (int i = 0; i < vecNum; i++)   
5.          result[i] = col1[i] + col2[i];  
6.   else   
7.      for (int i = 0; i < vecNum; i++)   
8.      {  
9.          int selIdx = selVec[i];  
10.          result[selIdx] = col1[selIdx] + col2[selIdx];  
11.      }  
12. }  

IO

　　由于SQL on Hadoop存储数据都是在HDFS上，所以IO层的优化其实大多数都是HDFS的事情，各大查询引擎则提出需求去进行推动。要做到高效IO，一方面要低延迟，屏蔽不必要的消耗；另一方面要高吞吐，充分利用每一块磁盘。目前与这方面有关的特性有：

• short-circuit local reads：当发现读取的数据是本地数据时，不走DataNode（因为要走一次socket连接），而是用DFS Client直接读本地的block replica。HDFS参数是dfs.client.read.shortcircuit和dfs.domain.socket.path。
• zero copy：避免数据在内核buffer和用户buffer之间反复copy，在早期的HDFS中已经有这个默认实现。
• disk-aware scheduling：通过知道每个block所在磁盘，可以在调度cpu资源时让不同的cpu读不同的磁盘，避免查询内和查询间的IO竞争。HDFS参数是dfs.datanode.hdfs-blocks-metadata.enabled。

存储格式

　　对于分析类型的workload来说，最好的存储格式自然是列存储，这已经在关系数据库时代得到了证明。目前hadoop生态中有两大列存储格式，一个是由Hortonworks和Microsoft开发的ORCFile，另一个是由Cloudera和Twitter开发的Parquet。

　　ORCFile顾名思义，是在RCFile的基础之上改造的。RCFile虽然号称列存储，但是只是“按列存储”而已，将数据先划分成row group，然后row group内部按照列进行存储。这其中没有列存储的一些关键特性，而这些特性在以前的列式数据库中（比如我以前用过的Infobright）早已用到。好在ORCFile已经弥补了这些特性，包括：

• 块过滤与块统计：每一列按照固定行数或大小进一步切分，对于切分出来的每一个数据单元，预先计算好这些单元的min/max/sum/count/null值，min/max用于在过滤数据的时候直接跳过数据单元，而所有这些统计值则可以在做聚合操作的时候直接采用，而不必解开这个数据单元做进一步的计算。
• 更高效的编码方式：RCFile中没有标注每一列的类型，事实上当知道数据类型时，可以采取特定的编码方式，本身就能很大程度上进行数据的压缩。常见的针对列存储的编码方式有RLE（大量重复数据），字典（字符串），位图（数字且基数不大），级差（排序过的数据，比如日志中用户访问时间）等等。

　　ORCFile的结构如下图，数据先按照默认256M分为row group，也叫strip。每个strip配一个index，存放每个数据单元（默认10000行）的min/max值用于过滤；数据按照上面提到的编码方式序列化成stream，然后再进行snappy或gz压缩。footer提供读取stream的位置信息，以及更多的统计值如sum/count等。尾部的file footer和post script提供全局信息，如每个strip的行数，各列数据类型，压缩参数等。

       

　　Parquet的设计原理跟ORC类似，不过它有两个特点：

• 通用性：相比ORCFile专门给Hive使用而言，Parquet不仅仅是给Impala使用，还可以给其他查询工具使用，如Hive、Pig，进一步还能对接avro/thrift/pb等序列化格式。
• 基于Dremel思想的嵌套格式存储：关系数据库设计模式中反对存储复杂格式（违反第一范式），但是现在的大数据计算不仅出现了这种需求（半结构化数据），也能够高效的实现存储和查询效率，在语法上也有相应的支持（各种UDF，Hive的lateral view等）。Google Dremel就在实现层面做出了范例，Parquet则完全仿照了Dremel。

　　对嵌套格式做列存储的难点在于，存储时需要标记某个数据对应于哪一个存储结构，或者说是哪条记录，所以需要用数据清楚的进行标记。 在Dremel中提出用definition level和repetition level来进行标记。definition level指的是，这条记录在嵌套结构中所处于第几层，而repetition level指的是，这条记录相对上一条记录，在第几层重复。比如下图是一个二级嵌套数组。图中的e跟f在都属于第二层的重复记录（同一个level2），所以f的r值为2，而c跟d则是不同的level2，但属于同一个level1，所以d的r值为1。对于顶层而言（新的一个嵌套结构），r值就为0。

     

　　但是仅仅这样还不够。上图说明了r值的作用，但是还没有说明d值的作用，因为按照字面解释，d值对于每一个字段都是可以根据schema得到的，那为什么还要从行记录级别标记？这是因为记录中会插入一些null值，这些null值代表着他们“可以存在”但是因为是repeated或者是optional所以没有值的情况，null值是用来占位的（或者说是“想象”出来的），所以他们的值需要单独计算。null的d值就是说这个结构往上追溯到哪一层（不包括平级）就不是null（不是想象）了。在dremel paper中有完整的例子，例子中country的第一个null在code = en所在的结构里面，那么language不是null（不考虑code，他跟country平级），他就是第二层；又比如country的第二个null在url = http://B 所在的结构里面，那么name不是null（不考虑url，因为他跟本来就是null的language平级），所以就是第一层。

　　通过这种方式，就对一个树状的嵌套格式完成了存储。在读取的时候可以通过构造一个状态机进行遍历。

　　有意思的是，虽然parquet支持嵌套格式，但是Impala还没有来得及像Hive那样增加array，map，struct等复杂格式，当然这项功能已经被列入roadmap了，相信不久就会出现。

　　在最近我们做的Impala2.0测试中，顺便测试了存储格式的影响。parquet相比sequencefile在压缩比上达到1:5，查询性能也相差5-10倍，足见列存储一项就给查询引擎带来的提升。