大数据新型存储格式CarbonData研究

验“金”室

作者

中国工商银行

大数据与人工智能实验室 翁晓俊

CarbonData是一种Hadoop生态下完全开源的新型文件格式，使用了先进的列式存储、多级索引等技术，以提高计算与查询效率，有助于提升超过PB数量级数据查询的速度，满足更快的交互查询需求。CarbonData期望实现一份数据存储同时满足多种业务需求，结合Spark等计算引擎后形成一套通用的大数据分析查询解决方案，实现一份数据可以同时满足批量和联机、批量和流处理访问的需要。图1是一份数据满足OLAP、Big/Small Scan 查询、点查询的示意。

图1 一份数据满足OLAP、Big/Small Scan 

查询、点查询

一、技术原理

CarbonData的核心技术原理主要涉及“独特的目录与文件格式”“多级索引”“支持更新与删除操作”。通过与Spark计算引擎深度集成，在处理数据时利用CarbonData独特的文件格式设计，获得性能提升。

1.独特的目录与文件格式

CarbonData数据表的目录组织形式如图2所示，数据表（user_table）中会有两个子目录。其中Metadata目录存放表的元数据相关信息，例如schema文件存放表结构信息，tablestatus文件存放segment相关的元数据信息（segment name、加载时间等）；其中Fact目录存放表的数据文件CarbonData和索引文件carbonindex。CarbonData支持分区表，如图2所示，Part0就是一个分区。在分区目录下还有一层segment目录管理数据文件。每次批量数据加载都会新增1个segment目录，后续通过compact操作减少segment数量。具体来说，一次批量数据加载过程中，会调度多个task到不同的节点上运行，在HDFS上会产生一个segment目录，最终在该目录下生成多个CarbonData文件和1个carbonindex文件。在加载过程中，通过HDFS文件锁的形式管理segment状态，保证只有当加载任务全部完成后，新segment才对用户可见。

图2 CarbonData数据表的目录组织形式

segment目录下的CarbonData数据文件格式如图3所示，一个文件主体分为File Header、Blocklets、File Footer三部分。File Header中存放了文件格式版本号（v1/v2/v3）、该数据表每一列的scheme信息以及文件生成时间戳。File Footer存放了该数据文件包含的记录数（Number Of Rows）、每一个Blocklet的信息（List<BlockletInfo>）以及每一个Blocklet的索引信息（List<BlockletIndex>，MDK索引，每一个Blocklet每一列的最大、最小值）。Blocklets以列式存储的形式存放了表数据。一个文件会有多个Blocklet，每个Blocklet包含数据表所有列的Page Group，每个Page Group包含多个Colum Page，每个Colum Page包含三种类型的Page（data page、rowid page可选、RLE page可选），一个data page至多存放32000条数据。从File Footer的List<BlockletInfo>和List<BlockletInfoIndex>可构建出文件级的Blocklet索引，以便快速定位目标列数据所在Blocklet。

segment目录下会有1个carbonindex文件，其内容是从所有该segment目录下CarbonData文件footer中抽取整合的，通过扫描所有segment下的carbonindex文件，Spark driver进程就可以快速在内存中完成文件级全局索引的构建，实现全局文件过滤。

图3 CarbonData文件格式

2.多级索引

CarbonData通过“多级索引”实现了目标数据的快速定位，过滤了大量不必要扫描的文件与内容，减少了IO，提升了整体读取效率。

如图4所示，在每一个CarbonData数据文件的尾部（File Footer）会存放Blocklet索引数据，其中最重要的是MDK（Multi-Dimensional Keys）索引。MDK索引需要用户通过DDL语句指定sort columns，sort columns指定的每一列都会被编码，然后再根据sort columns列的编码值进行数据排序，从而得到每一个Blocklet的MDK编码值的Start Key和End Key，同Blocklet每一列的最大值、最小值一同写入File Footer中。在数据查询的时候，可以读取File Footer快速在内存中构建一个B树索引（即MDK索引），此时使用MDK中的列查询条件来查询时，通过MDK索引，Min、Max列索引，就可以快速地定位数据文件中的Blocklet。

图4 MDK索引

CarbonData数据表可选指定inverted columns，指定后该column在data page 中的数据是独立排序的，例如col1 data page和col2 data page中同一个row的数据在不同的位置，所以需要额外记录col1 rowid page和col2 rowid page。这样独立排序的好处是column都是有序的，有更好的压缩率，查询时可使用Binary Search快速得到rowid范围，根据rowid范围快速获取数据记录（如图5所示）。

图5 Inverted Index

3.与Spark深度集成

通过扩展Spark SQL Catalyst框架中的解释器、优化器和执行计划，在作业运行时可以最大程度地发挥CarbonData多级索引、字典编码的性能优势（如图6所示）。

图6 与Spark深度集成

图7是一个Spark SQL访问CarbonData数据表的示例。Spark Driver进程会访问指定分区下所有segment目录里的carbonindex文件，在内存中构建一个全局索引，从而能够过滤掉多数文件。每一个Spark Executor会读取CarbonData文件的Footer，在内存中构建Blocklet索引，从而能够快速定位到Blocklet，因指定了查询列为Inverted Index，所以可以使用Binary Search快速过滤数据列，最终将数据记录解码后返回。

图7 一个Spark查询使用了

Inverted Index的例子

4.支持删除与更新操作

CarbonData支持删除与更新操作（如图8所示），操作完成后数据立即可见。删除数据时，会在数据所在的segment目录下新增一个bitmap文件，查询数据的时候，通过bitmap文件可以快速标注出已被删除的数据记录，不在查询结果中返回。更新数据时，会在数据所在segment目录下新增一个bitmap文件，一个新的delta数据文件，查询数据的时候，通过bitmap文件快速标记出已被修改过的数据记录，并合入新的delta数据，在查询结果中返回。

因CarbonData每次进行删除与更新操作都会生成新文件刷盘，适合以批量形式进行删除与更新，而且其不具备表级事务能力，故不建议作为OLTP交易型数据库使用。

图8 更新与删除操作

5.相比Impala+Kudu的优势

Impala+Kudu核心技术原理同CarbonData有较多相似的地方，都是通过列式存储、多级索引来加快查询速度。CarbonData的优势在于其是Hadoop原生的，能够和Hadoop生态紧密结合在一起，仅保存一份数据格式，供各类场景访问。而Kudu是独立的存储引擎，涉及数据ETL，会造成额外的数据冗余。

二、总结

综合考虑数据更新频度与分析查询频度两个维度（如图9所示），Hive计算引擎结合ORC存储格式适合批量场景，HBase计算引擎结合HFile存储格式适合联机场景，而Spark计算引擎结合CarbonData存储格式填补了前两者之间的空缺，在需要批量加工后数据即刻联机访问的场景下，可以通过统一的计算引擎和存储格式即可满足批量和联机两方面的需求。

图9 CarbonData适用场景

Spark计算引擎结合CarbonData存储格式具有如下优势：

Ø 由于CarbonData伴随索引的数据存储特性，对比ORC，在数据查询场景下具有明显优势，查询效率呈倍数增长。

Ø 支持update操作，逐条update性能与F2-merge算法性能相当，批量update性能高出F2-merge算法一个数量级。

基于上述两点，在部分场景下CarbonData+Spark弥补了原先ORC+Hive只能满足批量访问场景的不足，CarbonData目前在业界开始大范围使用。

FCC30+

长按左边二维码

关注我们不迷路