OceanBase中基于布隆过滤器的连接算法

茅潇潇,段惠超,高明

(华东师范大学数据科学与工程研究院,上海200062)

OceanBase中基于布隆过滤器的连接算法

茅潇潇,段惠超,高明

(华东师范大学数据科学与工程研究院,上海200062)

在大数据时代,“去IOE”运动的推进以及“双11”等活动的兴起对分布式数据库系统提出了更高的要求.OceanBase是阿里巴巴集团自主研发的开源分布式数据库,支持海量数据跨行跨表事务,但是对复杂查询的处理性能仍有待提高,其中连接操作带来的网络传输严重影响了数据库的性能.本文提出了一种基于布隆过滤器的连接算法,通过构建布隆过滤器对右表数据进行过滤,减少了不必要的数据传输开销,降低了数据处理带来的内存资源的消耗.本文在OceanBase上实现了该算法,并通过实验证明,该算法极大提高了连接操作的效率.

OceanBase;连接操作;布隆过滤器

0 引言

为了应对数据规模和业务规模的爆发式增长,以阿里巴巴公司为代表的互联网行业开始推进“去IOE”运动,如何选择数据库产品至关重要.近几年来,随着“双11”活动的发展、“秒杀”应用的兴起、以及云数据服务的推广,更是对目前开源的分布式数据库系统提出了挑战.为此,阿里巴巴集团自主研发了支持海量数据跨行跨表事务的分布式数据库OceanBase[1],以低成本、高可扩展性、高可用性和高可靠性著称,已经支持了阿里巴巴集团包括支付宝在内的许多业务.

但是作为主要面向OLTP应用的数据库系统,OceanBase对于复杂查询的处理性能并不高.当数据量非常庞大时,连接操作带来的大量数据交互会产生巨大的网络传输开销,严重影响数据库的性能.因此,对于连接操作的优化,就成为OceanBase中查询优化的重点.

迄今为止,大量的研究学者对分布式数据库中连接操作的查询优化进行了许多研究工作,¢憾的是,分布式查询优化技术还很不成熟,经典的理论不是只局限于某一方面,就是太过复杂无法应用到实际中.OceanBase中采用的是经典的排序归并连接算法,但是它也存在着一些缺陷.假设,我们要对关系R和关系S进行连接操作,当我们在存储关系R数据的节点上进行操作时,传统的排序归并连接算法要求关系S中的所有元组(或者至少为全部元组的一个垂直子集)被发送到该节点上进行计算.但是在实际的连接计算中,我们只需要关系R和关系S中可能产生连接结果的元组,不符合连接条件的数据传输浪费了不必要的网络资源,而且大量数据的排序操作需要较大的内存资源.因此,只要拥有足够的信息来判断关系S中各条元组是否符合连接条件,通过这些信息对关系S中的全部元组进行过滤,仅仅把这个符合条件的子集发送给计算节点,那么网络通讯代价将会大大减少,在过滤后的数据集上进行排序操作所消耗的内存资源也会下降.为此,布隆过滤器是一个理想的选择.

针对这一问题,本文在OceanBase中实现了一种基于布隆过滤器的连接优化算法.该算法并不将右表的全部数据发送到计算节点,而是使用布隆过滤器对右表数据进行过滤,再对过滤后的数据进行排序归并连接.本文的贡献点如下:

(1)在开源的分布式数据库OceanBase上实现了该算法;

(2)通过一系列测试证明了该算法的高效性;

(3)提供了一种在OceanBase中提高连接操作性能的思路.

本文第1节介绍了三种传统的连接算法及其在分布式数据库中的优化技术;第2节形式化定义了该算法所解决的问题,提出了算法的整体设计并对性能进行了分析;第3节介绍了该算法在开源数据库OceanBase上的详细实现;第4节通过一系列实验验证了该算法的性能;第5节总结了论文所做的工作并阐述了未来研究的方向.

1 相关工作

传统的连接算法主要有三种:嵌套循环连接算法、排序归并连接算法和哈希连接算法,这三种算法有着各自的特点和使用场景.随着分布式数据库的产生和发展,对这三种传统连接算法在分布式数据库中的应用优化技术也被逐渐提出.下面简要介绍一下这三种连接算法及优化技术.

1.1 嵌套循环连接算法

1977年,Blasgen提出了嵌套循环连接算法[2].嵌套循环连接算法是一种较简单、稳定的连接算法.它使用两层嵌套循环,对于被驱动表的每一行记录,驱动表的所有记录都会与其进行比较,最终得到连接结果.该算法适用于两表的数据量较小并且内存可以存放的情况,但如果数据量超过内存大小,则驱动表就需要进行多次扫描,扫描的次数为被驱动表大小与可用内存大小的比值.因此当两表的数据量较大时,嵌套循环连接算法的效率较为低下.

1.2 排序归并连接算法

针对嵌套循环连接算法的这一缺点,Blasgen还提出了排序归并连接算法[2].在排序归并连接算法中,两表先根据连接列进行排序,然后进行顺序扫描,在扫描的过程中将满足连接条件的元组合并得到最终结果.该算法适用于大数据量的情况,曾经被认为是最好的连接算法[3],但是由于需要对两表进行排序,排序过程中数据对比操作时间较长,内存资源消耗也较大.随着哈希连接算法的提出,证明排序归并连接算法的优势不一定成立.

1.3 哈希连接算法

第一个以哈希函数为基础的连接算法在1979年被E.Babb提出[4].简单的哈希连接算法的流程如下:首先选择一张小表作为驱动表,对小表的连接列使用特定的哈希函数进行计算,并在内存里产生一张哈希表.然后,使用相同的哈希函数对大表(即被驱动表)的连接列进行计算,将计算的结果在哈希表中进行探测.如果探测成功,则一条新的记录将被创建.在大多数情况下,哈希连接算法比其他连接算法(如排序归并连接算法)的性能要好[5].

1.4 分布式连接优化技术

分布式查询优化的一个重要目标是减少节点间的数据传输代价.尽管传统的连接算法的有效性已经在集中式数据库中得到了验证,但是在分布式环境下,节点间的数据传输代价是制约查询性能的重要因素.传统的连接算法在分布式数据库中的应用和优化成为了研究热点.

一种典型的优化方案是采用半连接策略[6]来减少网络传输代价,降低通信开销.但是,半连接需要将驱动表中连接列的值全部传送到被驱动表所在节点,并且需要在该节点上执行一次额外的连接.

针对以上问题,Chen等人把布隆过滤器[7]的思想应用到连接算法中[8].基于布隆过滤器的连接算法进行了两方面的优化:首先将驱动表中连接列的值根据不同哈希函数映射到位数组中,仅将这个位数组进行传输;其次在被驱动表上执行无序扫描,不再需要连接操作.L. F.Mackert等人在论文中指出,基于布隆过滤器的连接算法比基本的半连接算法性能更为优秀[9].因此本文使用了基于布隆过滤器的连接算法,更好地提高了分布式数据库OceanBase连接操作的处理性能.

2 问题定义和算法设计

2.1 问题定´

现有S表存储在节点Snodei(i=1,2,···,x),R表存储在节点Rnodej(j=1,2,···,y).现将S表和R表在连接属性a上做自然连接:select*from S inner join R on S.a=R.a.

2.2 算法设计

本算法基于分布式架构,使用布隆过滤器对传统的连接算法进行了优化.优化后的算法流程如下:

(1)将S表的全部数据从节点Snode1,Snode2,···,Snodex发送到计算节点M;

(2)根据S表连接列上的数据构建布隆过滤器BFS,并将BFS分别发送到R表数据所在的节点Rnode1,Rnode2,···,Rnodey;

(3)在Rnode1,Rnode2,···,Rnodey每个节点上对R表的数据进行过滤,并把R表中经过过滤的数据发送到计算节点;

(4)在计算节点上对两表的数据进行排序归并连接,并把最终结果返回给客户端.

2.3 性能分析

与传统的排序归并连接算法相比,基于布隆过滤器的连接算法极大地提高了连接效率.

假设S表中元组数为card(S),元组的长度为size(S),R表中元组的个数为card(R),元组的长度为size(R),则可得到传统的排序归并连接算法下的网络传输开销T为:

假设布隆过滤器BFS包含k个相互独立的哈希函数和一个m位长的位向量.布隆过滤器在判断一个元素是否属于它所代表的集合时会存在误判:由于存在哈希冲突,某一个对应于元素a的哈希位可能由于元素b的插入被设置为1,因此减小误称率是非常重要的.可以通过公式推导得出误称率perr最小的条件为:

此时,假设连接选择率为α,R表经过布隆过滤器过滤后缩减为R′表,基于布隆过滤器的连接算法下的网络传输开销T为:

由于布隆过滤器中位向量的大小m相比于Tnew中的其他两项,可以忽略不计,从公式(3)可以看出,基于布隆过滤器的连接算法的网络传输开销明显小于传统的排序归并连接算法下的网络传输开销,并且连接选择率α越小,基于布隆过滤器的连接算法节省的网络传输代价越大.

3 算法实现

3.1 OceanBase架构

Oceanbase系统架构由四种类型的节点服务器组成:

·RootServer:主控服务器,负责数据的负载均衡以及集群节点状态管理等.

·ChunkServer:基线数据服务器,提供分布式数据存储服务,负责存储基线数据.

·UpdateServer:更新服务器,实现事务处理,负责存储一段时间内的增量数据.

·MergeServer:查询处理服务器,负责接收和解析SQL请求、生成和执行查询计划以及

将所有节点的查询结果合并并返回给客户端.

本算法实际分为四个阶段:

(1)将左表即S表的所有数据发送到一台MergerServer上,其中Q包括ChunkServer存储的基线数据又包括UpdateServer存储的增量数据;

(2)在MergerServer上根据S表的数据在连接属性S.a上生成布隆过滤器BFS,并将该布隆过滤器BFS传入右表即R表所在的ChunkServer;

(3)R表所在的ChunkServer通过合并UpdateServer上的增量数据获得R表的全部数据后,使用BFS对数据进行过滤,并将过滤后的数据发送到MergerServer;

(4)MergerServer对两张表的数据根据连接类型进行等值连接操作,再根据不等值条件进行过滤,并把最终结果返回给客户端.

3.2 布隆过滤器构建

在算法的第二阶段,S表的数据全部发送到MergerServer后,MergerServer会根据这些数据构建一个能够表示S表所有元组的布隆过滤器BFS.通过公式,我们可以根据设定的误称率和数据量的大小计算出BFS中位数组的大小和哈希函数的个数.

布隆过滤器的一个重要问题在于如何使用正确的哈希函数来确保过滤器生效.在哈希函数的选择方面,本算法采用了MurmurHash函数来提高布隆过滤器的性能和效率. MurmurHash由Austin Appleby于2008年创立,是一种非加密型哈希函数,适用于一般的哈希检索操作,具有高运算性能和低碰撞率的特点.在Google的Guava开源项目[10]和LevelDB高效键值数据库[11]中,BloomFilter(布隆过滤器)类就是基于MurmurHash函数来实现的.它的好处在于,不需要根据计算得出的k的大小来确定具体的哈希函数,仅需要对一个哈希函数迭代k次,就能获得有效的布隆过滤器.布隆过滤器的构建算法如下:

算法1布隆过滤器构建算法输入：S表元组集合S,|S|=n输出：布隆过滤器BFS1根据误称率perr和元素个数n计算MurmurHash函数的迭代次数k和位数组大小m 2生成一个m位的位数组BFS,并将每一位初始化为0 3for读取S表的一条记录s do 4if s不为空then 5 for i from 1 to k step 1 do 6将s代入MurmurHash函数,计算hi(s)的值Vi; 7将BFS位数组的Vi位设为1; 8 end for 9end if 10end for 11布隆过滤器构建结束

如第1行所示,先根据设定的误称率perr和元素个数n,计算布隆过滤器所需位数组的大小m以及MurmurHash函数的迭代次数k;然后如第3行至第10行所示,对S表的每一条记录s依次作判断,如果s不为空,则如第5行至第8行所示,将s依次代入MurmurHash函数迭代k次,h1(s),h2(s),···,hk(s)得到k个值V1,V2,···,Vk;再将BFS位数组的V1,V2,···,Vk位设为1,其余位维持初始化的0状态.当把S表的所有记录遍历过后,布隆过滤器的构建完成. 3.3布隆过滤器查找

当算法进行到第三阶段,R表所在ChunkServer上的基线数据经过与UpdateServer上的增量数据合并获得R表的全部数据后,需要使用BFS对数据进行过滤,找出有可能符合等值连接条件的记录.布隆过滤器的查找算法如下:

算法2布隆过滤器查找算法输入：R表元组集合R,布隆过滤器BFS输出：符合等值条件的R表记录集合R′1生成空集R′2对于R表中的每一条记录,执行如下流程3for读取R表的一条记录r do 4if r不为空then 5 for i from 1 to k step 1 do 6将r代入MurmurHash函数,计算hi(r)的值Vi; 7检查BFS位数组的Vi位是否为1; 8 end for 9 if BFS位数组的V1位至Vk位均为1 then 10R′=R′∪{r} 11end if 12end if 13 end for 14布隆过滤器查找结束

如第3行至第13行所示,依次读取R表的一条记录r,如果r不为空,则如第5行至第8行所示,将r依次带入MurmurHash函数迭代k次,h1(r),h2(r),···,hk(r)得到k个值V1,V2,···, Vk,再检查BFS位数组的V1,V2,···,Vk位是否为1,如第9行至第11行所示,如果全部k个位都为1,则将记录r添加到集合R′中.当遍历完R表的所有记录后,输出符合等值条件的R表记录集合R′.

3.4 等值连接

在算法的最后一个阶段,将经过布隆过滤器BFS过滤的R表记录集合R′发送到Merge-Server后,由于布隆过滤器存在误判,因此这时获得的R表数据是R表最终可以进行等值连接操作的元组集合的超集,所以MergeServer还必须对数据进行一次过滤,以获得最终结果集.本算法选择使用经典的排序归并连接算法,在MergeServer的内存里对两张表的数据根据连接列排序,然后对排完序的结果做归并连接,最后再根据其余不等值条件进行过滤,并把最终结果返回给客户端.

4 实验评估

为了验证本算法的效率,本文设计了三组实验,从选择率、连接列和数据分布对性能的影响三个方面,通过观察对相同查询语句的处理时间,分析了基于布隆过滤器的连接算法的性能,并得出了结论.

4.1 实验环境

实验使用的OceanBase集群测试环境是在OceanBase开源的0.4.2版本上实现上述算法经过优化的版本,本文使用4台虚拟机组成的集群作为测试环境,每台虚拟机的配置相同,包括4核1.2 GHz主频CPU、100 GB内存、3 000 GB磁盘,虚拟机上安装了CentOS release 6.5系统,相互之间通过千兆以太网连接.集群中的一台虚拟机被配置为RootServer、MergeServer和UpdateServer,另外三台虚拟机被配置为ChunkServer.实验采用的数据是使用数据生成器随机生成的数据.

4.2 实验结果

4.2.1 选择率对性能的影响

该实验对比查询语句中连接列的选择率对OceanBase中传统的排序归并连接算法与基于布隆过滤器的连接算法的性能影响.测试左表包含10万条记录,右表的数据量从10万到1 000万条记录不等,两表连接列均为［1,MAX］的整数,MAX为记录数.

图1 选择率对性能的影响结果Fig.1Effect of the selectivity on performance

从图1中可以看出,当右表的数据量较小,即左表对右表的选择率较高时,布隆过滤器的构建和查找增加了计算开销,右表数据传输的网络开销降低得并不明显,基于布隆过滤器的连接算法的处理时间比传统的排序归并连接算法的处理时间要多.但是当右表的数据量达到100万行以上,即左表对右表的选择率越来越低时,传统的排序归并连接算法的处理时间大大增加,而使用布隆过滤器的连接算法的处理时间则呈近似线性增长.这是因为在选择率较小时,数据传输的网络代价将会占查询处理时间的主要部分.布隆过滤器以极低的计算代价,极大地降低了网络开销,提高了连接操作的性能.

4.2.2 连接列对性能的影响

该实验对比查询语句中连接列的个数对OceanBase中传统的排序归并连接算法和基于布隆过滤器的连接算法的性能影响.测试左表包含100万条记录,右表包含1 000万条记录,连接列的个数从1到7个不等,两表连接列均为［1,MAX］的整数,MAX为记录数.

图2 连接列对性能的影响结果Fig.2Effect of the number of join columns on performance

图2表明,查询语句中的连接列个数增多时,基于布隆过滤器的连接算法优势更加明显.布隆过滤器将多个连接列映射到一组对应的位数组,随着连接列的增多,布隆过滤器对数据的描述更加准确,对数据的过滤也更加有效.

4.2.3 不同数据分布对性能的影响

该实验对比连接列中数据不同的分布情况对基于布隆过滤器的连接算法的性能影响.测试左表包含10万条记录,右表的数据量从10万到1 000万条记录不等.为避免数据分布情况对两表连接结果的大小产生影响,控制三种数据分布下两表连接的结果集大小相等.

图3 不同数据分布对性能的影响结果Fig.3Effect of the data distribution on performance

如图3所示,数据的分布情况对布隆过滤器的性能几乎没有影响.布隆过滤器构建和查找的性能主要由前表和后表的元组数决定,因此在不同的数据分布下,布隆过滤器的性能是较为稳定的.

通过以上实验得出,改进后的连接算法极大地减少了OceanBase对连接操作的处理时间,并且随着选择率的降低和连接列个数的增加,性能的提高也更加明显.

5 总结

本文实现了一种分布式数据库中基于布隆过滤器的连接算法,并在开源数据库OceanBase上进行了实验验证.该算法充分利用了布隆过滤器低空间代价和快速响应的特点,通过对右表数据使用布隆过滤器进行过滤,减少了分布式环境下不必要数据的网络传输代价,降低了数据操作带来的内存资源的消耗,在连接列的选择率较低的情况下显著提高了连接操作的处理性能.

本文基于目前OceanBase数据库的架构,使用了布隆过滤器对连接算法进行了优化,但该算法仍有优化空间.如何对传统的布隆过滤器模型进行拓展,如何进一步使用MPP架构,将布隆过滤器的计算和数据的连接任务并行地分散到多个节点上,以及如何根据统计信息选择具体的连接算法,都是以后对连接优化算法研究工作的重点.

［1］杨传辉.大规模分布式存储系统:原理解析与架构实战[M].北京:机械工业出版社,2013.

［2］BLASGEN M W,ESWARAN K P.Storage and access in relational data bases[J].IBM Systems Journal,1977, 16(4):363-377.

［3］MERRETT T H.Why sort-merge gives the best implementation of the natural join[J].ACM SIGMOD Record, 1983,13(2):39-51.

［4］BABB E.Implementing a relational database by means of specialized hardware[J].ACM Transactions on Database Systems,1979,4(1):1-29.

［5］SCHNEIDER D A,DEWITT D J.A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment[C]//Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data.ACM,1989:110-121.

［6］BERNSTEIN P A,GOODMAN N,WONG E,et al.Query processing in a system for distributed databases (SDD-1)[J].ACM Transactions on Database Systems,1981,6(4):602-625.

［7］BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970, 13(7):422-426.［8］CHEN M S,HSIAO H I,YU P S.On applying hash filters to improving the execution of multi-join queries[J]. The VLDB journal,1997,6(2):121-131.

［9］MACKERTLF,LohmanGM.R*optimizer validationandperformance evaluationfordistributed queries[C]//Proceedings of the 12th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc,1986:149-159.

［10］BACON D F,STROM R E,TARAFDAR A.Guava:A dialect of Java without data races[C]//Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming,Systems,Languages,and Applications. 2000:382-400.

［11］GHEMAWAT S,DEAN J.Level DB[DB/OL].[2011-5-12].http://code.google.com/p/leveldb/.

(责任编辑:林磊)

A join algorithm based on bloom filter in OceanBase

MAO Xiao-xiao,DUAN Hui-chao,GAO Ming
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

In the era of big data,the movement of“de-IOE”campaign and the development of activities such as Double 11 have put forward higher request of the performance of distributed database.OceanBase is an open sourced distributed database implemented by Alibaba.It supports for cross-table relational query of massive data but the performance for complex queries remains to be improved.The network transmission overheads caused by join operator seriously influenced the performance of distributed database.This paper proposes a join algorithm based on bloom filter.It filters the data of the right table by constructing a bloom filter on the join column of the left table.The key point of this algorithm is that it reduces the overhead of unnecessary data transmission and the consumption of memory resources by data processing.We implement this algorithm in OceanBase and the experiment results show that the algorithm can greatly improve the efficiency of join operator.

OceanBase;join operation;bloom filter

TP311

A

10.3969/j.issn.1000-5641.2016.05.008

1000-5641(2016)05-0067-08

2016-05

国家863计划项目(2015AA015307)

茅潇潇,女,硕士研究生,研究方向为分布式数据库.E-mail:jsntmxx@gmail.com.

高明,男,副教授,研究方向为高可用事务处理优化、数据挖掘等. E-mail:mgao@sei.ecnu.edu.cn.