内存数据仓库集群技术研究

张延松， 王 珊， 周 烜

（1.中国人民大学DEKE实验室，北京 100872；2.中国人民大学 信息学院，北京 100872；3.中国人民大学 中国调查与数据中心，北京 100872）

0 引 言

数据仓库是企业级大数据应用重要的平台，长期以来一直受性能问题的制约而难以在企业级实时分析处理（Real Time Analytics）领域发挥出其应有的作用.随着计算机硬件技术的发展，多核处理器和大内存成为主流配置，如最新的Intel？Xeon？Processor E7－8890

v2处理器拥有15个处理内核、30线程，每插槽最大支持1.5TB内存，而DRAM的价格每12个月下降32%，内存计算技术在内存容量支持、硬件成本和计算性能等几个方面已经能够满足企业级大数据计算的需求，内存计算平台逐渐成为大数据计算新兴的高性能平台.Gartner公司在2013年IT行业十大技术发展趋势中指出内存计算将成为主流［1］，内存数据库技术，已经被越来越多的传统和新兴的数据库厂商所采纳，如MonetDB［2］、Vectorwise［3］、HANA［4］、IWA［5］、Oracle Exadata X3［6］、SQL server2014［7］等，并成为主流产品，内存数据库不仅能够提供传统数据库无法实现的实时分析处理性能，由于内存相对于磁盘能耗更低，内存数据库技术的引入还能够更好地降低数据中心总成本（TCO）［8］.同时，由于内存计算性能更高，不需要依赖存储代价极大的物化视图及索引机制，在列存储和压缩技术的支持下，内存存储相对于传统的磁盘存储具有更高的效率.

在软、硬件技术的支持下，内存数据仓库将会成为新的大数据实时分析处理平台.内存数据仓库需要解决的关键问题主要包括性能和扩展性.内存相对于传统的磁盘，其数据访问性能得到了极大的提升，但内存访问延迟和带宽性能的缓慢提升使大内存相对于高性能多核处理器成为“新硬盘”，仍然是内存数据仓库大数据处理性能的瓶颈因素.性能问题，一方面需要采用多核CPU、GPU、Phi协处理器等新硬件提升数据处理性能；另一方面需要面向Flash、PCM（相变存储）等新的存储硬件技术提高性价比和综合性能.在当前硬件水平下，内存数据仓库集群仍然是扩展内存数据仓库处理能力和性能的有效技术手段，通过中低端内存计算集群构建高性能内存数据仓库平台，降低内存数据仓库的成本并提供高可扩展的并行内存计算能力.

内存数据仓库集需要解决两类关键技术问题：数据分布模型和集群计算模型.数据分布模型需要考虑模式和关系两个层面的分布策略：模式层面的分布策略需要考虑数据仓库中不同类型的表，如维表和事实表，如何在集群中分布存储，分布模型所带来的数据存储代价以及数据更新代价；关系层面的分布模型需要考虑采用基于行还是基于列的分布存储模型等问题.集群计算模型则以数据分布式存储模型为基础，针对不同计算类型实现不同的并行计算.

本文以内存数据仓库集群技术为中心，概要地介绍了我们在内存数据仓库集群技术方面的研究技术、方法和手段，探讨在不同的应用需求和硬件支持下的内存数据仓库集群不同的实现技术及其特点.大体结构是第1节介绍以列相关分布模型和列计算服务为基础的内存数据仓库集群系统ScaMMDB的设计思想和系统实现技术路线；第2节介绍基于水平分片的内存数据仓库集群系统ScaMMDBⅡ及其面向不同类型聚集函数的并行查询处理技术；第3节介绍基于reverse－star schema数据分布模型和向量处理技术的内存数据仓库集群系统MiNT－OLAPCluster系统的实现技术；第4节总结全文并对内存数据仓库集群技术的技术发展趋势进行展望和分析.

1 基于列相关分布模型和列计算服务的ScaMMDB系统

MonetDB是一种基于列存储和BAT algebra列计算的开源数据库系统，是分析型内存数据库最具代表性的系统.MonetDB的高性能构建在充足内存空间的基础上，当数据量超过内存容量时，MonetDB通过虚拟内存进行I／O交换，查询处理性能受到极大的影响.ScaMMDB系统根据网络技术的发展趋势构建了一个基于高速网络平台的可扩展内存数据库集群系统，将数据和计算分布在不同的节点上，通过集群扩展技术保证内存存储和内存计算，其关键技术包括：基于网络传输代价的列分布策略、基于内存块的节点间列复制技术、分布式列计算技术等.

1.1 ScaMMDB系统结构

ScaMMDB是一种协同计算模式的内存数据库集群，如图1所示，数据库以列为单位在集群节点的内存上进行数据分布.每个节点均可以访问本地内存和其他节点的网络虚拟内存NetMemory，通过轻量数据字典表获取每个列的存储位置信息，将计算下推到列存储节点，完成协同计算任务，只将列操作结果传回查询发起节点.在并发查询处理时，查询任务可以均衡地分布在集群中的所有节点，每个节点负责完成本节点和其他节点的协同式列计算任务.数据列作为存储的基本单位提供列上的计算服务，可以由本地节点调用列计算API，也可以由集群其他节点远程调用，每个节点既是查询服务的提供者又是查询服务的消费者，集群节点通过协同计算完成整个查询任务.当集群规模变化时，即增加或减少集群节点时，通过数据列在节点间的迁移和对轻量数据字典的更新重置列计算API调用的服务位置.

图1 ScaMMDB系统结构Fig.1 Architecture of ScaMMDB

1.2 ScaMMDB的关键技术

ScaMMDB的目标是构建一个可扩展的虚拟内存以支持大数据内存分析，基础的技术假设是高速网络技术的发展使网络带宽的增长速度大大优于磁盘I／O的增长速度.世界超级计算机500强系统中主要采用InfiniBand和千兆以太网技术，这两种技术都能够提供超过100Gbps的数据传输性能.基于高速互联网络的虚拟网络内存NetMemory可以作为本地内存的下一级存储，共享集群中节点内存存储资源.Oracle RAC的内存融合技术（Cache Fusion）实现共享内存访问，将集群节点的内存融合为一个虚拟的大内存.分布式内存技术（distributed shared memory，DSM）是一种将本地和远程节点内存通过虚拟内存地址来访问和处理的技术，也是一种构建集群虚拟内存的技术.与这两种虚拟内存技术不同，ScaMMDB的NetMemory的存储单位是数据列，通过MonetDB底层的BAT访问API将远程数据列上的操作下推到列存储节点，通过远程BAT操作API的调用实现数据列的本地计算，只将较小的列处理结果返回数据请求节点.相对于Cache Fusion和DSM技术，NetMemory提供的不仅仅是虚拟内存上的存储访问服务，还包括远程节点的列计算服务.

ScaMMDB系统的关键技术包括如何实现基于集群节点协同计算模式的查询重写，如何优化数据列的网络传输性能，如何根据查询负载特征实现数据列的关联分布等.

1.2.1 基于集群节点协同计算模式的查询重写

SQL命令在MonetDB内部被转换为MAL命令集，由查询引擎执行.我们通过客户端获得SQL命令，根据MAL命令转换规则将其重写并由MAL引擎执行，完成ExMAL的执行.在将MAL命令序列转换为ExMAL命令执行序列时，我们通过扩展MonetDB底层的mserver.connect（）函数实现集群节点间的远程列计算调用，并开发了节点间列复制接口mserver.PutBat（）和mserver.GetBat（），实现从远程节点中获取BAT和将当前BAT推送到远程节点的操作，通过MonetDB的BBP缓冲池机制实现不同线程之间的列数据共享访问.在扩展的底层BAT接口的支持下，SQL命令能够被改写为面向集群分布式列存储模型的协同计算ExMAL命令集.

如图2所示的TPC－H的Q1测试查询对应的MAL命令序列中，两条MAL命令分别在场地：node1和node2上执行，其中，在node2上执行的MAL命令需要node1上的BAT作为操作数BAT，需要通过线程间数据共享访问机制和GetBAT完成BAT远程复制.

图2所示的例子中，远程MAL命令执行步骤如下：

（1）在主控节点node0上建立与node1的连接；

（2）通过与node1的连接，将BAT的bind命令发送到node1节点上运行；（3）在主控节点node0上建立与node2的连接；

（4）通过与node2的连接，在node2上执行与node1的连接；

（5）node0与node1的连接与node2与node1的连接对应不同的处理线程，通过将node1连接中的BAT变量＿56装入BBP，然后在node2的连接中访问BBP中的共享变量＿56；

（6）通过node1与node2的连接，在node2上执行远程复制node1上的BAT＿56；

（7）通过GetBAT（RemoteBind）在本地生成远程BAT复本；

（8）通过与node2的连接，在node2上执行连接操作.

图2 ScaMMDB的协同计算［9］Fig.2 Co－computing in ScaMMDB［9］

当MAL命令中涉及不同节点上的BAT时，需要通过对BAT大小和数量的估算评估网络传输代价，选择网络传输代价最低的节点作为当前MAL命令的执行节点.

1.2.2 数据列的网络传输优化技术

集群节点间进行列数据传输时，我们在目标节点根据源节点BAT结构通过BAT.new（）函数构造相同结构的BAT，在发送端PutBat（）函数调用时根据BAT的内存结构直接复制列数据块，如图3所示，varchar类型的列需要复制BAT列和数据实际存储内存块，以提高网络传输效率，并在接收端克隆出与源BAT相同的目标BAT，完成BAT在节点间的复制.通过基于内存块的传输优化技术，在千兆以太网中我们能够获得80 MB／s左右的传输速度，接近千兆以太网理论的传输速度.

图3 基于BAT存储结构的网络传输Fig.3 BAT structure oriented BAT transmission

1.2.3 基于查询负载特征的数据列关联分布

ScaMMDB系统的协同计算模式能够将OLAP查询中选择率低的操作下推到列存储节点执行，降低网络数据传输代价，但在普通的千兆以太网环境下，网络数据传输代价仍然占较高的比例.图4列出了TPC－H中部分测试查询在千兆以太网中的列传输代价占查询总代价的比例，以及模拟10 Gbps和Tbps以太网的数据传输代价.我们可以看到，在未来的Tbps高速网络传输技术的支持下，BAT传输延迟将低于0.5%，能够更好地发挥ScaMMDB的可扩展查询处理性能.

图4 不同网络性能下的网络传输代价比例Fig.4 Network transmission cost ratio in different networks

除了依赖高速网络技术的发展来降低虚拟内存访问延迟之外，我们进一步通过提高列分布的关联性减少协同计算时的数据传输.我们采用属性距离矩阵（Attribute Distance Matrix，ADM）来评估并量化分析出属性之间相关性的强弱，优先分布相关性高的属性集合.系统数据分布策略分为三个阶段：① 根据相对固定的OLAP查询命令集和统计信息生成ADM；② 根据属性相关性度量值进行属性聚类，根据节点数量将相关性强的属性集聚类为节点数量个相关属性集合，确定高访问频率的属性的分布策略；③ 根据第二阶段的部分数据分布策略和节点内存容量（内存占用低于75%时性能较优）调整其余属性的分布策略，保证全部属性分布在系统节点上并保证每个节点上的数据负载相对均衡.

在列存储数据库中，查询处理的最小单位是属性列，即任何查询都最终被分解为一系列的列操作，关联性体现在属性列之间的协同访问关系上，所以在列存储数据库中，关联性定义为属性与属性之间是否存在关联访问关系，如在MAL命令“＿21｛rows＝4：lng｝：＝algebra.join（＿18，＿19）；”中，BAT ＿18、＿19对应的属性存在关联性.根据 BAT 代数的特点，我们确定了属性关联性规则：① 出现在同一谓词表达式中的属性具有属性关联性；②GROUP BY、ORDER BY属性为关联性属性；③ 代数表达式中的属性为关联性属性；④ 逻辑运算符连接的所有属性具有关联性.通过属性关联性的定义，我们将MAL命令中BAT操作的多元操作数尽量集中在相同节点上，减少BAT操作时的网络传输代价.我们通过关联矩阵聚类算法将TPC－H的列聚类到n个节点上，并通过节点内存容量进行调整，生成最优数据分布策略.图5（b）图为不同数据分布策略在TPC－H查询中所产生的网络传输数据量，基于统计和聚类算法的分布策略能够有效地降低查询处理时的网络传输代价.图5（a）显示了ScaMMDB集群计算模式相对于集中式计算模式的性能提升，内存数据库集群能够有效地消除I／O代价，发挥出内存计算的优越性能.

ScaMMDB是一个可扩展的内存数据库系统，系统的各个节点可以同时接受用户的查询请求并在各个节点的协同下输出最终的结果，系统吞吐量将大于单节点内存数据库系统.

我们在2007—2008年期间开展内存数据库集群ScaMMDB的研究工作，当时还没有内存数据库集群系统和产品，2012年，Vectorwise系统上进行了一些集群并行的研究工作［18］，但并没有形成独立的产品.我们在ScaMMDB性能测试时没有可对比的内存数据库系统，因此我们采用了通过TPC－H测试基准中的吞吐量指标Throughput＠Size来衡量ScaMMDB的吞吐量的方法来测量ScaMMDB系统的加速比指标，在一个3节点的内存数据库集群中，ScaMMDB的吞吐量是单节点MonetDB的近3倍.

1.3 ScaMMDB的应用场景

图5 数据传输性能和查询性能［10］Fig.5 Network transmission and query processing performance［10］

ScaMMDB是一种以列存储和列计算为中心的集群协同计算模型，它实现简单，能够在MonetDB底层API的基础上通过扩展网络传输与远程计算调用API实现系统功能，能够支持全部复杂的TPC－H查询处理任务.在数据分布策略上，基于列的聚类分布策略相对于基于表的数据分布策略更加细粒度且操作性更强，结合数据挖掘的功能能够自动对系统负载进行监测并更好地实现负载均衡.

ScaMMDB不适用于访问负载集中于少数列的应用场景，也不适合较大的集群规模.ScaMMDB的每个节点都能够独立地接受查询请求，适合于并发查询处理场景.ScaMMDB依赖于对MonetDB底层API的扩展，随着MonetDB版本的升级和MAL命令集的不断扩充，增加了ScaMMDB系统实现的成本.

2 基于水平分片的内存数据仓库集群系统ScaMMDBⅡ

TPC－H是一个用3NF实现的数据仓库，是一个双事实表雪花形结构，其中事实表lineitem和orders表构成订单事实数据集，事实表lineitem和partsupp表构成订单零件供应事实.这两部分事实数据集占整个TPC－H数据量的95%以上（如SF＝100时，linteitem：68.24%；orders：14.74%；partsupp：12.28%，而其余5个维表数据量仅占4.74%），而这些巨大的事实表之间的连接操作代价成为影响TPC－H性能的关键因素，当采用集群处理模式时，跨节点的查询处理任务产生巨大的网络数据访问延迟.

数据仓库在存储模式设计时需要考虑其查询处理的类型和未来计算平台上的性能问题，现实中数据仓库通常采用星形或雪花形模型，使用一个巨大的事实表和多个较小的维表，消除庞大事实表之间的连接操作，简化集群并行处理.图6所示的SSB基准是对TPC－H基准面向OLAP的多维处理特性而进行的模式优化，数据仓库中只有一个事实表，在SF＝100时事实表数据量占整个数据库98%以上，较小的维表使多维OLAP查询优化更加简单，也适合大数据集群处理模式.图6所示的HANA技术白皮书中示例的星形模型数据仓库是一个高维结构，维表数量众多但非常小，位于中心的事实表非常庞大，这种数据量极端倾斜的多／高维星形结构能够采用多种优化技术，并且能够简化集群分布模型和集群计算模型，提高大数据分析处理效率.

图 6 星 形模型数据 仓库［11－12］Fig.6 Star schema data warehouses［11－12］

ScaMMDBⅡ针对星形模型为特征的数据仓库集群技术而设计，根据维表数据量极小和OLAP查询结果集极小（在SSB中结果集为1－800行）的特征采用事实表水平分片，维表全复制的简单数据分布策略，集群的任意节点可以充当动态的协调者（coordinator），将查询任务分派给各个工作节点并行执行，并对各执行节点返回的OLAP查询结果集进行聚集归并.

2.1 ScaMMDBⅡ系统结构

我们提出了基于sibling cube的可扩展内存数据库系统ScaMMDBⅡ（ParaCube），如图7所示，数据仓库的完整数据集被划分为多个数据仓库子集，其中事实表被划分为不相交的n个数据子集分布在n个MMDB节点上，维表在n个数据节点上被全复制，每个节点上运行一个middle ware（ParaCube mediator）作为OLAP客户端软件，各个数据库节点中数据是同构的但各节点上的数据库可以是异构的，可以根据应用的需要选择不同的数据库，对节点上的数据访问通过标准的数据库访问接口JDBC来实现，屏蔽系统之间的差异，在ParaCube mediator上需要记录每个数据节点的元数据.ParaCube mediator的功能是接受用户的查询请求，根据查询内容完成查询重写，通过JDBC将查询任务下推并返回查询处理结果子集，然后通过多路归并算法将聚集结果子集归并为最终的查询结果.系统中可以有唯一的ParaCube mediator也可以维护多个ParaCube mediator来提高系统的并发查询处理能力.

图7 基于ParaCube mediator的ScaMMDBⅡ系统Fig.7 ParaCube mediator oriented ScaMMDBⅡsystem

2.2 ScaMMDBⅡ关键技术

ScaMMDBⅡ是以数据为中心的并行OLAP查询处理模型，根据OLAP查询处理中数据量大、数据粒度大、查询复杂度高、查询目标为聚集结果、高输入低输出的特点，优化传统的并行查询处理技术，提高并行查询处理过程中的并行性，优化OLAP性能.ScaMMDBⅡ是一种开放的结构，支持异构数据库的集成，因此系统能够根据应用中数据量和查询负载的变化动态扩展系统处理规模，同时也支持不同类型系统的集成，支持将事务型数据库与分析型数据库从逻辑上组织为统一的系统，支持操作型BI（Operational Business Intelligence）的应用需求.

2.2.1 数据分布策略

如图8所示，在SF＝100的TPC－H中5个维表数据量低于5%，SSB中4个维表数据量仅占1%左右，当集群规模较小时，维表全复制策略能够最大化本地计算，最小化网络数据传输代价，维表全复制所带来的存储空间开销能够控制在可接受的范围之内，维表全复制策略或者维表广播策略是面向数据仓库模式特征而广泛采用的简单有效的数据分布技术.从数据量分布特征我们也可以看到，将TPC－H满足3NF的模式设计转换为星形模式设计能够使其更加适合集群并行计算，简化并行计算模型.

图8 TPC－H和SSB测试集事实表、维表数据分布Fig.8 Data distribution of fact tables and dimension tables in TPC－H and SSB

2.2.2 并行聚集计算技术

OLAP计算的特征是聚集计算，即将连接后的记录按维层次分组后计算出聚集值.聚集计算是一个数据收敛的过程，在人机交互的ad－hoc OLAP应用中，用户通常以低势集的多维数据集为目标，因此，当聚集计算可以在集群节点间并行处理时，每个节点只产生非常小的聚集结果集，网络传输代价能够被极大地降低.

对于满足结合律的可分布式聚集函数（SUM、COUNT、MAX、MIN、FIRST、LAST等），以SUM为例，即若A＝A1∪A2∪…An并且φ＝A1∩A2∩…An则有SUM （A）＝SUM（SUM （A1），SUM （A2），…，SUM （An））.将数据集划分为多个不相交的数据子集后，使用聚集函数的OLAP查询可以直接下推到数据子集上独立执行，最后将查询结果子集合并.对于代数可分布聚集函数，如AVERAGE可以通过SUM和COUNT聚集结果计算得出，方差函数可通过如下公式转换为SUM（A）、SUM（A2）、COUNT（A）三个聚集函数的代数表达式计算得出.

对于不可分布式聚集函数，如MEDIAN、PERCENTILE等则需要将集群中的数据传输到一个节点上集中处理，增加了网络传输代价.我们在文献［13］中提出了一种迭代式中值计算技术，如图9所示.通过在集群节点本地排序数据集上求出各自的中值，然后通过网络汇集各节点边界值并根据最小边界值在各节点上对排序数据集进行剪枝，逐渐缩减中值候选窗口，最后只对较小候选窗口中的数据进行集中式的中值处理以得到全局中值结果.实验结果表明，由于事实表数据的分布具有数据随机性，而且group－by属性随着查询而动态变化，因此排序记录子集一般分布较为均匀，迭代剪裁能够有效缩减并行中值计算的网络传输代价.

2.2.3 面向Operational BI需求的ScaMMDBⅡ模型

现代大型企业每天产生大量的事务数据，用户的决策支持越来越多地依赖于对及时性数据的分析结果，需要数据仓库支持更短的更新周期.我们提出在事务型系统和分析型数据仓库系统之间建立一个中等规模的分析型数据缓存层，提供高性能的ad－hoc查询处理能力.为保证查询处理的性能，采用MMDB查询处理引擎的ScaMMDBⅡ（ParaCube）来实现高性能OLAP查询处理.如图10所示，全部的数据被分为三个层次：Fresh data表示前端OLTP数据，数据量较小，支持数据的更新操作，采用OLTP引擎，OLAP查询处理性能的保证是较小的数据集；Buffer data是OLTP和OLAP系统之间的缓存数据，它接受来自OLTP系统的较短时间间隔的更新操作，一般是批量的追加和数据迁移，缓存数据量的大小取决于数据仓库的更新策略和物化cube的更新代价.一般来说，从OLTP系统向缓存数据层的更新以天为单位，从缓存数据层向数据仓库的更新以月或年为单位.在数据分析时，最近的数据往往具有更高的分析权重，因此OLTP系统和数据缓存层的查询负载相对较高，数据缓存层的数据量动态变化，因此需要ScaMMDBⅡ的可扩展性提供支持.对于可分布聚集计算函数来说，将OLAP查询任务下推到OLTP系统、Buffer data（ParaCube）和数据仓库层，各个层次独立完成在其数据集上的OLAP查询处理任务，生成查询处理结果子集并由系统进行查询结果子集归并，产生最终的查询结果.通过可分布聚集计算OLAP的并行处理，能够构建一个异构的OLAP系统，并且将OLTP系统与OLAP系统从逻辑上组织为统一的系统，提高分析数据的及时性，增加分析结果的操作性，提高系统分析任务的有效性.

图9 迭代式中值计算Fig.9 Iterative Median computing

图10 Operational BI三层模型Fig.10 3－level operational BI model

相对于Vertica的WOS和ROS机制以及SAP的OLTP＆OLAP技术，我们采用的是一种异构数据库平台上的逻辑集成技术，降低系统的复杂性.我们同时提出异步更新通道模型以实现将OLTP系统中的数据在后台以异步方式增量更新到内存OLAP数据库集群，减少集群节点间的数据更新代价.

2.3 ScaMMDBⅡ的应用场景

ScaMMDB采用基于列的数据分布策略，面向只读型的数据仓库应用.ScaMMDBⅡ采用的维表全复制机制和事实表异步更新通道机制支持insert－only更新类型的数据仓库应用，维表的存储和更新的代价较大.

基于水平分片的并行OLAP机制对于基础的SPJGA（S：选择，P：投影，J：连接，G：分组，A：聚集）操作只需要简单的查询重写和查询结果归并处理，非常适合SSB数据集上的OLAP应用.对于带有复杂子查询的TPC－H查询则需要将查询转换为SPJGA查询树才能实现并行处理，系统实现复杂度较高.

3 基于向量技术的内存数据仓库集群系统MiNT－OLAPCluster

ScaMMDB采用与Oracle RAC的Cache Fusion技术类似的NetMemory扩展内存数据仓库的内存容量以支持大数据内存计算.ScaMMDBⅡ采用与HadoopDB类似的集群并行计算技术构建基于SQL的异构内存数据仓库集群.系统实现技术以MonetDB为基础，虽然能够利用MonetDB优秀的性能和丰富的API支持，但受MonetDB系统设计的限制，难以对内存数据仓库集群进行更加深入的优化.

当前数据仓库技术的发展趋势是及时性（just－in－time）分析处理需求越来越高，甚至将前端业务系统与后端分析系统相结合，将OLTP与OLAP系统融合在一起，代表性技术包括SAP HANA、ScyPer［14］等系统.因此，在内存数据仓库集群的设计中需要将数据更新代价作为一个重要的设计因素.MiNT－OLAPCluster系统根据数据仓库模型和负载特征采用反星形（reverse－star schema）模式存储策略，即将较小的维表集中存储，消除冗余副本的存储代价和网络更新代价，事实表则采用水平分片存储于集群节点，形成以维表为中心，事实表分片为分支的星形分布式存储.在OLAP查询处理中我们采用基于位图或向量的星形过滤技术，在维表上生成较小的向量数据结构并广播到各工作节点，在事实表分片上完成本地化SPJGA计算，并将各工作节点的OLAP结果集在中心节点进行全局聚集归并，生成最终的查询处理结果.

3.1 MiNT－OLAPCluster系统结构和关键技术

与ScaMMDB、ScaMMDBⅡ采用 MonetDB查询处理引擎不同，MiNT－OLAPCluster系统的OLAP查询处理以我们自己设计的DDTA－JOIN算法为核心，通过向量计算模型简化OLAP查询处理过程，将OLAP查询处理中维表与事实表之间的数据传输最小化为位图或向量，从而最小化集群计算时的网络传输代价.

图11显示了DDTA－JOIN（Directly Dimensional Tuple Accessing，DDTA）算法对于典型SPJGA模式的OLAP查询处理过程.首先SQL命令中维表上的过滤操作按维表进行划分，在维表上过滤后生成与维表等长的过滤位图；通过事实表外键与维表主键之间的地址映射（address mapping）在事实表扫描时将维表外键映射到维表过滤位图进行过滤操作，满足星形过滤（star－filtering）的记录通过外键映射到维表分组属性列中抽取分组属性，与事实表度量属性组合为输出记录进行哈希分组聚集计算.

Oracle Exadata X3采用的SmartScan技术通过where谓词筛选和JOIN联接筛选在存储服务器节点上过滤掉大部分不符合查询条件的记录，只将少量记录返回给数据库服务器完成查询处理.类似的Bloom filter过滤技术也大量被数据库系统所采用，通过增加额外的连接过滤处理消减连接操作的记录数量，从而降低连接计算代价.数据仓库的星形模型中维表较小且增长缓慢，以SSB数据集为例，即使SF＝1 000时，4个维表过滤位图总大小为4.08 MB，过滤位图的存储和网络广播代价极小.对于低选择率的维表过滤操作，位图还可以进一步通过压缩技术减少位图存储和网络广播代价.

图11 DDTA－JOIN 算法示例［15］Fig.11 Example of DDTA－JOIN algorithm［15］

当OLAP查询的选择率较高时（如SSB中选择率最高为3.4%），SmartScan技术仍然需要传输大量的数据到数据库节点进行查询处理，而这些数据本地分组聚集后的结果集非常小，因此在OLAP集群计算时，将分组聚集计算下推到存储节点能够极大地提高集群并行计算性能.如图12所示，我们进一步将SQL中维表上的谓词和分组操作整合，即根据维表谓词条件投影出维表分组属性组（可以是单一分组属性，也可以是维表上多个分组属性的组合值）并对其进行编码，然后生成基于分组属性编码的维表过滤分组向量（predicate vector），虽然相对于维表过滤位图，维表过滤分组向量增加了向量宽度，但由于能够通过维表过滤分组向量在事实表分片节点完成完整的SPJGA操作，只需要返回非常小的分组聚集结果集，能够进一步降低集群OLAP并行处理时的网络传输代价.

图12 谓词向量Fig.12 Predicate vector

基于DDTA－JOIN算法的MiNT－OLAPCluster系统结构如图13所示，整个内存数据仓库集群由一个中心节点和若干个处理节点组成，维表集存储于中心节点，支持维表上的实时更新操作，事实表水平分片均衡分布于各工作节点以保证负载均衡，事实表是历史数据，其特征决定了主要支持insert－only类型的更新操作.在星形模型数据仓库中，事实表分片以数据量为主要考虑因素，简化数据分布模型.

图13 MiNT－OLAPCluster系统结构［16］Fig.13 Architecture of MiNT－OLAPCluster［16］

MiNT－OLAPCluster的集群OLAP处理分为三种不同的方式.

（1）star－filtering only.中心节点仅将维表过滤位图广播到工作节点，工作节点完成事实表谓词过滤和维表连接过滤后将筛选的事实表记录传输给中心节点完成OLAP查询处理.此种处理方式类似于SmartScan技术，但采用维表位图过滤能够准确地过滤出所有满足条件的记录，不存在bloom filter过滤的误判断问题.当OLAP查询的选择率很低且查询处理任务难以并行处理（如不可分布的聚集计算或复杂子查询处理）时，各工作节点提供分布式的记录筛选功能，中心节点负责集中式的复杂查询处理任务.

（2）位图广播和分组属性缓存.当维表上的分组属性更新率较低时，我们可以将查询中常用的维表分组属性列缓存于工作节点内存，OLAP查询处理时只广播维表过滤位图，在工作节点与维表分组属性列共同完成本地化的分组聚集计算.当中心节点的维表分组属性列更新时，工作节点上缓存的分组属性列需要重新加载或更新.

（3）维表过滤分组向量广播.查询处理时在中心节点实时生成维表过滤分组向量，并广播到各工作节点完成分布式的分组聚集计算.维表过滤分组向量广播的网络传输代价有所提高，但由于维表行数较少，其网络传输代价有限，而且这种机制能够支持维表上的实时更新.

DDTA－JOIN算法将维表上的查询处理与事实表上的计算划分为独立的两个阶段，OLAP查询在中心节点上的处理过程和工作节点上的分组聚集计算可以流水并行，即当查询Q1在中心节点生成维表过滤分组向量并广播给工作节点进行集群并行处理时，中心节点可以继续执行查询Q2在维表上的处理任务.由于维表较小且生成维表过滤分组向量的操作比较简单，我们可以在工作节点进行OLAP查询处理时创建查询组Q的维表过滤分组向量组，在下一个工作节点OLAP查询处理时执行查询组Q上的并发查询处理任务，进一步提高查询吞吐性能.

进一步地，我们将内存数据仓库集群技术扩展到Hadoop平台，如图14所示.我们在Hadoop多复本机制的基础上将一个副本升级为内存列存储副本，支持内存副本上的集群并行内存OLAP查询处理，其余复本作为容错副本，将内存OLAP集群技术与Hadoop集群技术相结合，发挥内存OLAP集群的高性能和Hadoop集群的高可扩展性和高可靠性.

图14 基于Hadoop平台的内存OLAP集群［17］Fig.14 In－memory OLAP cluster on Hadoop［17］

3.2 MiNT－OLAPCluster性能验证

我们在核高基重大专项“大型通用数据库管理系统与套件研发及产业化”的子课题“国产数据库高性能高安全关键技术研究（2010ZX01042－001－002－002）”中采用 MiNT－OLAPCluster技术实现内存数据仓库集群系统.我们在集群测试中使用14个节点（每节点2个6核处理器，48GB内存，SSB测试集在SF＝100时内存占用45.8GB），一个节点作为主节点，用于查询解析、任务调度和查询结果归并，13个工作节点用于并行查询处理.整个集群测试数据集大小SF＝100×13，事实表分片均匀分布到13个工作节点上.由于我们没有SF＝1 300的内存做集中式的内存OLAP性能基准测试，因此采用通过单个数据分片查询处理时间×节点数来近似获得（由DDTA－JOIN算法的线性特征决定），集群并行查询处理时间为系统实际执行测试时间，集群的并行处理加速比SR≈13×单分片执行时间／集群并行执行时间，实验中平均并行加速比为12.64.见图15所示.

图15 内存数据仓库系统集群并行性能Fig.15 In－memory Data Warehouse cluster parallel performance

3.3 MiNT－OLAPCluster的应用场景

我们当前的研究工作以图6所示的星形模型为目标，以基础的SPJGA操作符的集群并行处理技术为对象，提供一个内存数据仓库的基础平台，在此基础上可以构建以SPJGA操作符树为基础的更加复杂的查询处理任务.也就是说，我们的实现技术能够完全解决SSB测试基准类型的OLAP负载，也可以作为内存数据仓库集群的SPJGA操作API提供给更加复杂的OLAP查询处理任务调用.

多事实表的TPC－H数据集也可以采用 MiNT－OLAPCluster的实现技术.事实表lineitem与orders表存在主外键参照完整性引用约束关系，而且lineitem表的orderkey与orders表的orderkey存在偏序关系，我们可以采用orders（orderkey）→lineitem（orderkey）的分片策略将lineitem表和orders表按orderkey划分为不相交的数据分片存储于不同的集群节点上.Partsupp事实表在集群上独立进行水平分片，TPC－H查询中Q2、Q11、Q16、Q20查询中，part表、supplier表和partsupp事实表之间的星形OLAP操作遵循MiNTOLAPCluster实现技术.TPC－H查询中包含lineitem？orders？partsupp操作的查询Q9中，partsupp表上的查询子集在经过集群并行生成后需要广播到各工作节点参与连接操作.因此，TPC－H数据集在事实表协同分片策略下也可以使用MiNT－OLAPCluster实现技术，但相对于SSB标准的SPJGA查询，TPC－H需要将更为复杂的查询转换为SPJGA查询树并对MiNT－OLAPCluster的集群SPJGA操作API进行调用.表1对三种内存数据仓库集群技术进行了综合对比.

表1 内存数据仓库集群技术对比Tab.1 Comparison for different in－memory data warehouse cluster technologies

4 结 论

本文概括地描述了我们在内存数据仓库集群研究上的技术路线，不同原型系统所面对的问题及解决方案.在三个原型系统的研究过程中，我们最大的感受是需要建立自己的内存OLAP查询执行框架，并使之平台化，掌握自己的关键技术，提高对系统实现的掌控能力.

本文给出了当前大内存发展趋势下内存数据仓库集群实现技术的框架结构.与具有高可扩展性的key／value存储类似，当采用极大事实表、多个极小维表的星形或雪花形模型时，数据仓库具有良好的可扩展性.在事实表－维表地址映射技术和向量计算技术的支持下，多维／高维OLAP查询处理具有较高的效率，通过对OLAP查询命令在维表和事实表上的分而治之处理技术，数据仓库能够较好地支持OLTP任务，实现实时分析处理.

随着CPU和内存技术的发展，大数据内存实时分析相对于传统的数据仓库技术具有更高的性能和性价比，随着实时分析性能的提升，OLAP的应用将逐渐从少数决策管理用户层扩展到大量业务处理的普通用户层，因此实时OLAP查询响应性能和高并发查询吞吐性能将成为未来内存数据仓库重要的性能指标，需要结合多核／众核并行处理技术及新的存储硬件技术方面的最新成果不断提高大数据实时OLAP分析处理性能.数据仓库也将逐渐从只读型分析处理向OLTP＆OLAP相结合的需求发展，需要提高OLTP负载与OLAP负载并发时的综合性能.大数据处理对集群技术的需求需要重新考虑和设计面向集群处理特征的数据仓库模式设计，高密度事实表（事实表数据量占比高）和高维模式设计将简化集群并行计算模型并且提高数据仓库的扩展性能.基于SPJGA操作符的OLAP查询树优化技术能够将高收敛性的聚集计算下推到数据存储节点，相对于传统的基于关系操作符的查询树优化技术能够更好地适应数据仓库集群计算.

［1］ Gartner Identifies the Top 10 Strategic Technology Trends for 2013［EB／OL］.（2012－10－23）［2013－04－12］.http：／／www.gartner.com／newsroom／id／2209615.

［2］ BONCZ P A，KERSTEN M L，MANEGOLD S.Breaking the memory wall in MonetDB.Commun［J］.ACM51，2008（12）：77－85.

［3］ ZUKOWSKI M，BONCA P A.Vectorwise：Beyond Column Stores［J］.IEEE Data Eng Bull，2012，35（1）：21－27.

［4］ SIKKA V，FÄRBER F，LEHNER W，et al.Efficient transaction processing in SAP HANA database：the end of a column store myth［C］／／SIGMOD Conference.2012：731－742.

［5］ IBM Informix Warehouse Accelerator－Performance is everything http：／／public.dhe.ibm.com／common／ssi／ecm／en／imw14587usen／IMW14587USEN.PDF.

［6］ Overview of ExaData.http：／／www.oracle.com／us／products／database／exadata／overview／index.html.

［7］ DIACONU C，FREEDMAN C，ISMERT E，et al.Hekaton：SQL server＇s memory－optimized OLTP engine［C］／／SIGMOD，2013：1243－1254.

［8］ ELLIOTT T.Why In－Memory Computing Is Cheaper And Changes Everything［EB／OL］.（2013－04－17）［2014－06－18］.http：／／timoelliott.com／blog／2013／04／why－in－memory－computing－is－cheaper－and－changes－everything.html.

［9］ 张延松.大规模可扩展数据分析技术研究［D］.北京：中国人民大学信息学院，2010.

［10］ 黄云奎.可扩展内存数据库ScaMMDB数据分布策略研究［D］.北京：中国人民大学信息学院，2009.

［11］ RABL T，POESS M，JACOBSEN H A，et al.Variations of the star schema benchmark to test the effects of data skew on query performance［C］／／ICPE，2013：361－372.

［12］ HANA S.Performance Efficient Speed and Scale－Out for Real－Time Business Intelligence［EB／OL］.（2012－4－28）［2013－04－12］http：／／www.saphana.com／docs／DOC－1647.

［13］ ZHANG Y，WANG S，HUANG W.ParaCube：a scalable OLAP model based on distributed aggregate computing with Sibling Cubes［C］／／APWEB，2010：323－329.

［14］ MÜHLBAUER T，RÖDIGER W，REISER A，et al.ScyPer：A Hybrid OLTP＆OLAP Distributed Main Memory Database System for Scalable Real－Time Analytics［C］／／BTW，Magdeburg，Germany，2013.

［15］ 张延松，焦敏，王占伟，等.海量数据分析的 One－size－fits－all OLAP技术［J］.计算机学报，2011（10）：1936－1947.

［16］ JIAO M，ZHANG Y S，WANG Z W，et al.MiNT－OLAP cluster：minimizing network transmission cost in OLAP cluster for main memory analytical database［J］.Frontiers of Computer Science，2012，6（6）：668－676.

［l7］ 张延松，王珊.面向数据库与 Hadoop混合平台的OLAP查询处理方法：中国，201210114112.0.2［P］.2013－11－20.

［l8］ Costea A，Ionescu A.Query Optimization and Execution in Vectorwise MPP［D］.Amsterdam：Vrije Universiteit Amsterdam（＠VectorWise），2012.