数据组织核心技术

要高效地使用数据，就必须要有组织，因此业界对数据的结构化组织有很多探索。

1）Cube技术概念

OLAP的目标是满足决策支持或者满足在多维环境下特定的查询和报表需求，它的技术核心是“维”这个概念。“维”（Dimension）是人们观察客观世界的角度，是一种高层次的类型划分。“维”一般包含着层次关系，这种层次关系有时会相当复杂。通过把一个实体的多项重要属性定义为多个维，使用户能对不同维上的数据进行比较。因此，OLAP也可以说是多维数据分析工具的集合。OLAP的基本多维分析操作有钻取、切片和切块，以及旋转等。

• 钻取是为了改变维的层次，变换分析的粒度。它包括向上钻取（rollup）和向下钻取（drilldown）。rollup是在某一维上将低层次的细节数据概括到高层次的汇总数据，或者减少维数；而drilldown则相反，它从汇总数据深入到细节数据进行观察，或增加维数。
• 切片和切块是在一部分维上选定值后，观察数据在剩余维上的分布。如果剩余的维只有两个，则是切片；如果有三个，则是切块。
• 旋转是为了变换维的方向，即在表格中重新安排维的放置（如行列互换）。

OLAP有多种实现方法，根据存储数据的方式不同可以分为ROLAP、MOLAP、HOLAP。ROLAP表示基于关系型数据库的OLAP实现（Relational OLAP）。以关系型数据库为核心，以关系型结构进行多维数据的表示和存储。ROLAP将多维数据库的多维结构划分为两类表：一类是事实表，用来存储数据和维关键字；另一类是维表，即对每个维至少使用一张表来存放维的层次、成员类别等维的描述信息。维表和事实表通过主关键字和外关键字联系在一起，形成了“星形模式”。对于层次复杂的维，为避免冗余数据占用过大的存储空间，可以使用多张表来描述，这种星形模式的扩展称为“雪花模式”。其特点是将细节数据保留在关系型数据库的事实表中，聚合后的数据也保存在关系型数据库中。这种方式查询效率最低，不推荐使用。

MOLAP表示基于多维数据组织的OLAP实现（Multidimensional OLAP）。以多维数据组织方式为核心，也就是说，MOLAP使用多维数组存储数据。多维数据在存储中将形成“立方块（Cube）”的结构，在MOLAP中对“立方块”的“旋转”、“切块”、“切片”是产生多维数据报表的主要技术。其特点是将细节数据和聚合后的数据均保存在Cube中，所以以空间换效率，查询时效率高，但生成Cube时需要大量的时间和空间。

HOLAP表示基于混合数据组织的OLAP实现（Hybrid OLAP）。如低层是关系型的，高层是多维矩阵型的。这种方式具有更好的灵活性。其特点是将细节数据保留在关系型数据库的事实表中，但是聚合后的数据保存在Cube中，聚合时需要比ROLAP更多的时间，查询效率比ROLAP高，但低于MOLAP。

Cube是典型的以空间换时间的技术。为了提高查询效率，提前以各种维度把数据组织好，如图10.14所示。

图10.14

2）Kylin

Apache Kylin是由eBay开源的分布式分析引擎，提供基于Hadoop的SQL查询接口及多维分析（OLAP）能力，以支持超大规模数据。Kylin的架构如图10.15所示。

kylin核心思路是给数据建cube，然后将结果cube结果存储在HBASE上提供对外查询使用。

图10.15

3）ORCFile

ORCFile（Optimized Row Columnar）是Hive 0.11版本中引入的新的存储格式，是对之前的RCFile存储格式的优化，是HortonWorks开源的。ORCFile的存储格式如图10.16所示。

图10.16

可以看到，每个ORC文件由一个或多个Stripe组成，每个Stripe的大小为250MB，这个Stripe实际上相当于RCFile里的RowGroup，不过大小由4MB扩展到250MB，能够提升顺序读的吞吐率。

每个Stripe都包含IndexData、RowData及StripeFooter三部分。StripeFooter包含流位置的目录；RowData在表扫描的时候会用到；IndexData包含每列的最大值和最小值及每列所在的行。行索引里提供了偏移量，它可以跳到正确的压缩块位置。

通过行索引，可以在Stripe快速读取的过程中跳过很多行。在默认情况下，最多可以跳过10 000行。

因为可以通过过滤预测跳过很多行，因而可以在表的SecondaryKeys进行排序，从而可以大幅地减少执行时间。

每个文件都有一个FileFooter，里面存放的是每个Stripe的行数、每个Column的数据类型等信息；每个文件的尾部是一个PostScript，里面记录了整个文件的压缩类型及FileFooter的长度信息等。在读取文件时，会跳到文件尾部读PostScript，从里面解析到FileFooter长度；再读FileFooter，从里面解析到各个Stripe信息；再读各个Stripe，即从后往前读。

ORCFile的主要特点如下：

• 混合存储结构，先按行存储，一组行数据叫Stripes，Stripes内部按列存储。
• 支持各种复杂的数据类型。
• 在文件中存储了一些轻量级的索引数据。
• 基于数据类型的块模式压缩：Integer类型的列用行程长度编码（Run-Length Encoding，RLE）；String类型的列用字典编码。

4）Parquet

开源项目Parquet是Hadoop上一种支持列式存储的文件格式，起初只是Twitter和Coudera在合作开发，发展到现在已经有包括Criteo公司在内的许多其他贡献者了。Parquet用Dremel的论文中描述的方式，把嵌套结构存储为扁平格式。

尽管Parquet是一个面向列的文件格式，但不要期望每列一个数据文件。Parquet在同一个数据文件中保存一行中的所有数据，以确保在同一个节点上进行处理时，一行的所有列都可用。Parquet所做的是设置HDFS块大小和最大数据文件大小为1GB，以确保I/O和网络传输请求适用于大批量数据。

在一个大小为1GB的HDFS文件中，一组行的数据会重新排列，以便第一行的所有值被重组为一个连续的块；然后是第二行的所有值，以此类推。

为了在列式存储中可以表达嵌套结构，用definitionlevel和repetitionlevel两个值来描述，分别表达某个值在整个嵌套格式中的最深嵌套层数，以及在同一个嵌套层级中的第几个值。

Parquet使用一些自动压缩技术，如行程长度编码（Run-Length Encoding，RLE）和字典编码（Dictionary Encoding），基于实际数据值进行分析。通过字典使数据值被编码成紧凑的格式，同时使用压缩算法，编码的数据可能会被进一步压缩。Impala创建的Parquet数据文件可以使用Snappy、Gzip进行压缩，或不进行压缩；Parquet文件还支持LZO压缩，但是目前Impala不支持LZO压缩的Parquet文件。

除了应用到整个数据文件的Snappy或Gzip压缩外，RLE和字段编码是Impala自动应用到Parquet数据值群体的压缩技术。

综合来看，ORCFile和Parquet本质上都是列式存储，大同小异。Parquet的主要特点是支持嵌套格式，ORCFile的主要特点是Strips中有轻量级的IndexData，所以这两种数据存储格式完全可以相互借鉴融合。另外，列式存储不是Hadoop首创的，而是从传统数据库中发展而来的。

5）Google Mesa数据模型

Google发表了一篇有关大数据系统的论文，讨论了一个名为Mesa的数据仓库系统，它能处理近实时数据，即使在整个数据中心断线后还能正常工作。

Mesa是一个高度可扩展的分析数据仓库系统，能存储与Google广告业务有关的关键测量数据。Mesa能满足复杂和具有挑战性的用户与系统需求，包括近实时数据提取和查询，同时在海量数据和查询量中保持高可用性、可靠性、容错率和扩展性。Mesa每秒能处理数百万行更新，每天能进行数十亿次查询，抓取数万亿行数据。Mesa能进行跨数据中心复制，即使在整个数据中心发生故障时，也能以低延迟返回一致和可重复的查询结果。

针对数分钟更新吞吐量、跨数据中心等严苛需求，已有的商业数据仓库系统（处理周期往往以天和周来计算）和Google的解决方案包括BigTable、MegaStore、Spanner和F1都无法满足要求。BigTable无法提供必要的原子性，MegaStore、Spanner和F1无法满足峰值更新需求。此外，Google自己开发的Tenzing、Dremel，以及Twitter开发的Scribe、LinkedIn的Avatara、Facebook的Hive及Hadoop DB等Web规模数据仓库处理的都是批量负载。

Mesa的主要特点如下：

• 近实时地更新吞吐量。支持持续更新，每秒支持数百万行更新。
• 同时支持低时延查询性能和批量大量查询。99%的查询在几百毫秒之内返回。
• 跨数据中心备份。

HDFS最早设定的是数据不更新，只增量叠加。传统数据仓库（如Greenplum、Treadata、Oracle RAC）通常会遇到两个问题：

• 更新的throughput不高。
• 更新影响查询。

为了解决这两个问题，Google的Mesa系统设计了一个MVCC的数据模型，通过增量更新和合并技术，将离散的更新I/O转变成批量I/O，平衡了查询和更新的冲突，提高了更新的吞吐量。

Mesa设计了一个多版本管理技术来解决更新的问题：

• 使用二维表来管理数据，每张表都要制定Schema，类似于传统的数据库。
• 每个字段用Key/Value来管理。Schema就是Key的集合。
• 每个字段指定一个聚合函数F（最常见的是SUM）。
• 数据更新进来的时候，按照MVCC增量更新，并给增量更新指定一个版本号N和谓词P。
• 查询进来的时候，自动识别聚合函数，把所有版本的更新按照聚合函数自动计算出来。
• 多版本如果永远不合并，则存储的代价会非常大。而且因为每次查询需要遍历所有版本号，所以版本过多会影响查询。因此，定期合并是必需的。
• Mesa采用两段更新的策略。更新数据按版本号实时写入，每10个版本自动合并；每天全量合并一遍，合并成一个基础版本。