一种海量数据场景下的数据全局合并方法转让专利
申请号 : CN202110731698.4
文献号 : CN113177024B
文献日 : 2021-09-14
发明人 : 汪洋 , 王磊 , 陶泽军 , 陈煌 , 卢兴杨
申请人 : 南京烽火星空通信发展有限公司
摘要 :
权利要求 :
1.一种海量数据场景下的数据全局合并方法,其特征在于,所述方法包括:步骤一、minor合并,将N个小文件作为一个批次进行归并排序,产生1个或多个文件大小合标的文件;
所述minor合并过程中,对输入文件的大小进行排序,将符合设定阈值大小的一批文件进行归并排序,使得更小的文件最先被合并;
步骤二、桶合并,经过步骤一后,件大小达标的文件会进入桶合并的候选队列,桶合并逻辑中对队列中的文件再次进行任务构造并进行多路归并排序;
所述桶合并过程中,所述桶分为两层,分别为level0与level1层,level0中存储桶合并后生成的文件,level1层存储major合并后生成的文件;
所述桶合并指的是在排序的过程中根据排序字段的范围,将数据分别写入到对应的桶内的新文件中;
步骤三、major合并,经过步骤二桶合并后的文件将进入major合并的候选队列进行major合并;
步骤四、经过步骤一至步骤三的三级合并完成之后,对现有桶进行平衡判断,若桶内数据不均匀,则执行桶的再平衡操作。
2.如权利要求1所述的一种海量数据场景下的数据全局合并方法,其特征在于:所述minor合并过程中,输入文件包括实时接入的小文件同时,也包括minor合并后产生的未达阈值的小文件,minor合并阈值由用户自己配置。
3.如权利要求1所述的一种海量数据场景下的数据全局合并方法,其特征在于:当minor合并生成的文件大小超过设置阈值时,会启动文件分片策略,使最终进入桶合并的minor文件大小相近;
所述分片策略指的是通过估算找到最有可能达到分片条件的数据条数N,当写入数据量达到N时,获取文件实际大小,若此时文件达不到分片条件,则修正N的值,使得N逐渐增大,直到文件大小达到分片条件。
4.如权利要求1所述的一种海量数据场景下的数据全局合并方法,其特征在于:经过多轮桶合并后,当桶内的level0层的文件个数达到阈值,即触发major合并;major合并首先计算level1层中与level0中所有文件存在交集的文件,然后将所有level0层和level1层有交集的文件集合作为一个批次进行归并排序,生成N个level1层的彼此之间有序的新文件。
5.如权利要求1所述的一种海量数据场景下的数据全局合并方法,其特征在于:所述桶的再平衡分为两个步骤:
步骤(1)、桶的分裂,所述桶的分裂指的是将原先的桶分裂成多个彼此不相交的,不可分割的最小子集;
步骤(2)、桶的合并,所述桶的合并指的是首先基于所有文件计算出新桶的平均大小,然后基于分裂后的桶集合,进行两两合并,直到合并后的新桶达到平均大小。
说明书 :
一种海量数据场景下的数据全局合并方法
技术领域
背景技术
统扫描多个文件,产生大量随机读请求,尤其对于机械硬盘来说,大量的随机读请求无疑会
极大地降低整个系统的吞吐量。其次,由于海量数据大都存储于HDFS(Hadoop Distributed
File System)上,海量小文件的存在会给整个Hadoop集群性能带来严重的性能问题。最后,
由于数据是实时接入的,通过一条带条件的SQL查询语句来查询数据时,若数据整体无序,
则查询的命中结果集很可能存在于多个文件之中,会使系统的查询变慢。因此,对数据库设
计者而言,面对海量数据的小文件,优化数据存储,提高数据有序性是提高实时查询效率最
有效的手段之一。
时任务对分区内小文件进行周期性合并,根据任务规则将多个分区中的多个文件合并成1
个文件,降低小文件散落数量,从结果上看确实降低了磁盘读取负荷与网络传输消耗,并且
有效的提高了数据的查询效率,但是对于海量数据而言,当积压数据量大时,对分区内小文
件进行一次性合并,系统资源消耗较大,耗时较长,合并期间,数据实时查询性能受影响,同
时,该专利合并期间未对数据进行全局排序,数据查询性能提高有限。
堆积,实时查询速度仍受到影响,专利号CN111562898A中提出了一种基于FPGA实现的多级
归并排序方法,该算法中将排序操作分为多级,前一级的输出作为下一级的输入,支持任意
长度排序队列以及大数据量数据排序,在满足时序要求的同时,满足海量离线数据的高效
快速数据排序,需要注意的是,该算法基于FPGA实现,不适用主流CPU处理器环境,同时该算
法不适用于海量数据实时入库场景。因此,数据库设计中需要考虑一种高效,快速并能支持
实时数据的排序及合并方法。
发明内容
地,考虑到文件可能存储于Hadoop集群上,为防止文件分片可设置为256M。
的数据条数N,当写入数据量达到N时,获取文件实际大小,若此时文件达不到分片条件,则
修正N的值,使得N逐渐增大,直到文件大小达到分片条件。
述桶合并指的是在排序的过程中根据排序字段的范围,将数据分别写入到对应的桶内的新
文件中。
层和level1层有交集的文件集合作为一个批次进行归并排序,生成N个level1层的彼此之
间有序的新文件。
场景下的数据全局合并方法,将合并阶段分为三级,其中前两级为过渡阶段,耗时较短,可
有效提高数据的查询效率。
一种海量数据场景下的数据全局合并方法,对数据进行分级排序,当桶内数据不均匀时,其
自带的再平衡算法可保证数据排序不会发生数据偏移,提高了海量数据排序效率。
的参考价值。
附图说明
具体实施方式
考附图描述的实施方式是示例性的,仅用于解释本发明,而不能解释为对本发明的限制。
序算法作为三级多路归并算法的实现,下述两个实施例中均利用败者树排序算法作为说
明。
件格式为orc文件,数据范围在1 4000之间。将本发明所提出的三级多路归并排序合并方法
~
运用于spark分布式系统架构,整体架构图如图1所示,从图中可以看出,本发明提出的三级
合并在merge‑drive端中构造任务,并在merge‑excutor端执行任务。在本实施例中,三级多
路归并排序所需参数设置如下表所示:
分区A,B中是否有正在运行的minor任务,若有,则退出,保证同一时间,每个分区的minor合
并任务只有一个。如图2所示,当分区内part文件和minor命名开头的小文件数量大于阈值
100时,或者文件总大小大于256M时,启动minor合并,合并之前对分区中A,B中的数据文件
的按大小进行排序并分批次构造合并任务,以便优先合并更小的part文件,每个合并任务
合并文件数量可由实际情况动态调整,合并过程中读取part文件中数据并通过败者树排序
算法对每批次数据文件进行排序,并生成以minor命名开头的大文件。将小文件合并为大文
件时,检测生成的文件是否大于256M,若文件大小接近256M时,启动分片策略,生成一个或
多个接近256M的大文件和一个小文件,文件命以minor开头,其中生成的大文件进入桶合并
的候选队列,小文件与后续实时生成的part小文件重新进入minor合并的候选队列,分片策
略的具体判断逻辑流程图如图8所示。至此minor合并结束并释放资源,周期线程继续扫描
分区文件,等待分区文件数量达到阈值时,重新启动合并。
批次桶合并任务构造,合并任务启动之前判断当前分区是否有正在运行的桶合并任务,若
有则退出,保证同一时间每个分区只存在一个桶合并任务。桶合并过程中,程序读写读取
minor数据文件通过败者树排序算法对数据进行排序并将数据写入不同的桶中,生成的新
文件以bucket命名开头,文件存储于桶的level0层,如图3所示,1 4000的数据被均匀写入
~
到图中所示的八个桶中。桶合并中是否创建新桶的逻辑如图7所示。可以看出桶合并生成的
文件只是文件内部有序,但桶内文件中的数据均在该桶的数据范围之内。
并任务,若有则退出,保证同一时间每个分区只存在一个major合并任务。每个major合并任
务负责一个桶内的文件合并,合并过程中读取bucket和major文件中数据并通过败者树排
序算法对每批次数据文件进行排序,并生成以major命名开头的大文件。如图4所示,major
合并中将桶的level0层中的bucket文件与level1中的数据范围为1 200的major文件进行
~
合并,显然生成的文件数据范围也在1 200之间,将桶内文件合并为major大文件时,检测生
~
成的文件是否大于1G,若文件大小接近1G时,启动分片策略,生成一个或多个接近1G的大文
件和一个小文件。分片策略与步骤一中的分片策略一致,不过分片阈值为1G,major合并后,
生成的文件都将进入下轮major或桶合并的获选队列,可以看出,桶level1层的major文件
是全局有序的。
如图5所示,桶1中数据大小大于是桶4的2倍以上,桶的再平衡逻辑执行,桶1,2,3,4分裂成
桶1,2,3,4,5,6,7,新桶之间无交集,分裂完成之后,桶1与桶2合并成新的桶1,桶3,4,5合并
成新的桶2,桶6,7合并成新的桶3。从图5以看出,桶的再平衡操作完成后,桶内数据分布均
匀。
并排序方式可以提高合并效率。当然,三级多路归并排序合并算法也可以串行合并基于实
施例一的数据场景。将本发明的合并排序方式转为串行,即,对同一分区而言,同一时间只
存在一种合并方式。步骤如下:
minor合并任务,合并逻辑与实施例一中minor合并逻辑一致,minor合并结束后生成已排序
的minor开头文件,并将合并生成的新文件列表传入桶合并逻辑,桶合并逻辑中筛选文件列
表中的达到阈值大小的minor文件, 当文件数据达到阈值时,进行分批次桶合并任务构造,
桶合并逻辑中通过归并算法生成的新文件存入桶的level0层,major合并扫描桶内level0
和level1层的文件并进行合并排序,生成的新文件存放桶的level1层,major合并完成后执
行桶的再平衡逻辑,至此,一个合并周期任务结束,三级多路归并合并线程继续执行下个周
期任务。三级多路归并排序串行执行流程图如图6所示。
做出各种变化。
员,在不脱离本发明技术方案范围内,当可利用上述揭示的技术内容做出些许更动或修饰
为等同变化的等效实施例,但凡是未脱离本发明技术方案内容,依据本发明的技术实质,在
本发明的精神和原则之内,对以上实施例所作的任何简单的修改、等同替换与改进等,均仍
属于本发明技术方案的保护范围之内。