基于频繁项集的数据关联性分析和预读取方法

基于频繁项集的数据关联性分析和预读取方法
【技术领域】
[0001] 本发明设及一种分布式系统中数据关联性分析W及数据预读取技术领域，具体 的，设及一种通过挖掘频繁项集找到数据的关联性，提前读取数据，从而提升整个系统的运 行速度。
【背景技术】
[0002] 在分布式系统中，一个文件通常被分割为多个等大的数据块，分布在集群中的各 台机器上，在进行计算时，系统会将一个大的作业拆分为多个子任务，部署到不同的机器上 同时运行，每个子任务通常会处理一至多个数据块。在任务执行过程中，需要读取相应的数 据块，按照任务所在节点与数据所在节点二者的位置关系，读取方式可W分为=类：
[0003] (i)二者在同一节点上，通过本地磁盘I/O读取数据；
[0004] (ii)二者不在同一节点但在同一机架上，通过机架内的网络传输数据；
[0005] (iii)二者不在同一机架上，通过机架间的网络传输数据。
[0006] 在数据密集型作业中，数据的读取往往成为系统效率的瓶颈，由于上述=种读取 方式的速度依次递减，因此如何降低网络传输所占的比例，将成为提升系统性能的关键所 在。
[0007] W目前广泛使用的分布式计算平台化doop为例，它的文件系统皿FS化adoop DistributedFileSystem)会将一个文件拆分为多个等大的数据块炬lock)分布在集群中 的各个节点上，数据块大小通常为64MB。为了保证数据的可用性，在默认情况下每个数据块 有S个备份，其中两个在同一机架的不同节点上，第S个在其他机架上，皿FS现有的解决方 案是根据磁盘的负载情况选择存放的节点。
[000引然而，该种选择方式并没有考虑到数据之间的关联性，有些数据在逻辑上关系很 紧密，在同一个子任务中往往会被一起处理，如果在物理位置上将他们分开存放，在执行过 程中需要将数据迁移到子任务所在的节点，从而影响整个系统的吞吐率。

【发明内容】

[0009] 针对现有技术中的缺陷，本发明的目的是提供一种基于频繁项集的数据关联性分 析和预读取方法。本发明的目的在于克服现有技术中的不足，针对云计算中数据分布的独 特性，在频繁项集的基础上，提供一种数据预读取的机制，可W有效解避免数据传输成为计 算的瓶颈，从而加快计算的速度。
[0010] 根据本发明提供的一种基于频繁项集的数据关联性分析和预读取方法，包括如下 步骤：
[0011] 步骤1 ;对于用户提交到云平台中的第i个作业化bi，云平台根据作业化bi中的每 个子任务化sky设及到的数据块生成一条记录TU，并将记录Tu存入资料库D中；
[001引其中，Tasku表示作业化bi的第j个子任务；i为正整数，j为正整数；所述记录Ty，是指作业化bi中的子任务化skU设及到的数据块的集合；
[001引步骤2 ;每隔时间间隔Interval,对资料库D中的数据进行挖掘，找到频繁项集中 所有的关联规则L关联规则L中大小为m的子规则集合记为Lm，关联子规则集合Lm中的子 规则Lmk的支持度定义为SuppoK(Lmk);
[0014] 其中，;Lmk表示关联子规则集合Lm中的第k条记录；Suppod(Lmk) =|Lmkl/|D|，其 中，iLmkI表示关联规则L中的子规则Lmk出现的次数，|D|表示资料库D中关联规则L的数 量；时间间隔Interval根据资料库D的变化速率进行调整，Interval |D|/| AD|，其中， ADI表示单位时间内关联规则L变化的数量；
[0015] 步骤3、在作业化bi的执行过程中，每个子任务化skU根据已经处理过的数据块 集合A，依照关联规则以预测在接下来的计算中可能用到的数据块集合B，并提前加载进内 存；按照如下方式决定预测是否可信：
[0016]预测置信度的计算方式为Confidence (A-B)=Suppo;rt (A U B)/Support炬）
[0017] 其中，Confidence(A-B)表示处理数据块集合A后，在接下来的计算中会使 用到数据块集合B的置信度，Support炬）表示关联规则L中出现数据块集合B的次数， Suppod(A U B)表示关联规则L中同时出现数据块集合A和数据块集合B的次数；
[001引设置S个置信度阔值Csa^eNode、CsameKack、〔global，分别表示数据块集合B所在节 点Nodee与子任务化skU所在节点Node 两者之间的位置关系为两者在同一节点、 两者不在同一节点但在同一机架、两者不在同一机架上时应该选取的置信度阔值，并有 CsameNode〈CsameRack〈Cgl0bal;
[0019]根据节点Nodee与节点Nodet。日巧者之间的位置关系在C日。ucWDde、及CgiDb。！ 中选取对应的置信度阔值作为阔值C，当且仅当Confidence(A-B) >C时，认为该预测有 效，并进行数据的预读取。
[0020] 优选地，所述对资料库D中的数据进行挖掘，采用的如下频繁项集挖掘算法： [002U步骤AO;设置阔值目，其中，0< 0 <1;设置缓冲区Buffer与关联规则L，并将缓冲 区Buffer与关联规则L的初始状态均设置为空集；其中Buffer为一个集合，用于存储最近 使用的记录；
[00巧对资料库D中的每一条记录Tu执行如下步骤：
[0023] 步骤A1 ;将一记录放入缓冲区Buffer中；
[0024] 步骤A2 ;使用该记录更新关联规则L ;
[0025] 将在关联规则L中出现频率高于阔值0的记录认定为频繁项集；如果关联规则L 中设及到的数据块个数为2的频繁项集的数量大于P/gl，则进入步骤3,否则返回步骤1对 下一条记录进行处理；
[0026] 步骤A3 ;令m=2,对关联规则L进行约简；
[0027] 步骤A4 ;设置m初始值为2,反复执行如下步骤A4. 1至A4. 3,直到Lm为空集时进 入步骤A5 ;
[00測步骤A4. 1 ;将m的值增加1 ;
[0029] 步骤A4. 2 ;使用缓冲区Buffer中的每一条记录更新关联规则L ;
[0030] 步骤A4. 3 ;对关联规则L进行约简；
[0031] 步骤A5;清空缓冲区。
[0032] 优选地，所述更新关联规则以具体如下：
[003引对记录T。每一个大小为m的子集subsetmT。执行如下步骤；
[0034]-如果子集subsetmTy在关联子规则集合Lm中，则令该子集subset 的计数变量 countSet的值增加1 ;其中，记录Ty的任意子集subsetTU包含一个计数变量countSet，计 数变量countSet表示子集subsetTy在关联规则L中出现的次数；
[00对-如果子集subsetmT。不在关联子规则集合Lm中且m《2,则将该子集subsetmT。 加入关联子规则集合Lm中；
[0036]-如果subsetmT。的任意大小为m-1的子集均在关联子规则集合1。_冲，则将该子 集subsetmTy加入关联子规则集合Lm中；其中，Lm_i表示表示关联规则L中大小为m-1的子 规则集合。
[0037] 优选地，所述对关联规则L进行约简，具体为：
[003引对关联子规则集合Lm中每一条子规则Lmk执行如下步骤：
[0039] 令该子规则Lmk的计数变量countRecord的值减1，如果计数变量countRecord归 零，则将该子规则Lmk在关联子规则集合L m中删除；其中，关联子规则集合L m中的每一个子 规则Lmk包含一个计数变量countRecord,计数变量countRecord表示子规则Lmk在关联规 则L中出现的次数。
[0040] 与现有技术相比，本发明具有如下的有益效果：
[0041] 1、本发明只需对资料库进行一遍扫描，占用额外内存小，避免了影响集群的整体 性能。
[0042] 2、本发明可W方便的找出数据块之间的关联性，提前将逻辑关系比较紧密的数据 读取到同一节点中，从而有效减少数据迁移占用的时间，提升整个系统的吞吐率。
【具体实施方式】
[0043] 下面结合具体实施例对本发明进行详细说明。W下实施例将有助于本领域的技术 人员进一步理解本发明，但不W任何形式限制本发明。应当指出的是，对本领域的普通技术 人员来说，在不脱离本发明构思的前提下，还可W做出若干变化和改进。该些都属于本发明 的保护范围。
[0044] 本发明公开一种基于频繁项集的数据关联性分析和预读取方法，包括步骤如下： 云平台每处理一个作业，将该次作业中每一个子任务处理的数据块作为一条记录存入资料 库中；每隔一定时间利用集群的空闲资源对资料库中的频繁项集进行挖掘，找出数据块之 间的关联性；在之后作业的执行过程中，根据预测的置信度，结合数据与任务所在节点的位 置关系，提前读取所需要的数据块，从而达到提升整个集群吞吐率的目的。
[0045] 本发明所提供的方法，具体如下：
[0046]步骤1、云平台每处理一个作业化bi，则根据该次作业化bi中的每个子任务化skU 设及到的数据块生成一条记录T。，并将记录T。存入资料库D中，其中，化sk。G化bi，T。= (BlockklBlockkG化sky}，Blockk为数据块在文件系统中的唯一标识符。
[0047] 所述作业化bi，是指用户提交到云平台中的第i个特定应用（即作业），它通常可 W分解为一个或多个子任务化sky,化sky表示作业化bi的第j个子任务，该些子任务经过 调度器的调度后分布在多个节点上并行执行，其中每个子任务负责处理指定的数据块。
[0048]所述数据块，是指在云平台的文件系统中，通常把一个大文件拆分成多个等大的 数据块，分布的存储在集群中不同节点上，为了提高数据的可用性，每个数据块可w有多个 备份。按照子任务所在节点与数据块所在节点的物理位置关系，可W分为=种：
[0049] (i)二者在同一节点上，通过本地磁盘I/O读取数据；
[0050] (ii)二者不在同一节点但在同一机架上，通过机架内的网络传输数据；
[0化1] (iii)二者不在同一机架上，通过机架间的网络传输数据。
[0052] 在该=种位置关系中，程序读取数据的速率依次递减。
[0化3] 所述的一条记录Tu，是指一个子任务设及到的数据块的集合；资料库为一个二维 数据结构，长度为所有子任务数量之和，用来存储产生的所有记录。
[0化4] 步骤2、每隔时间间隔Interval,根据资料库D中的数据使用下面提出的频繁项集 挖掘算法进行挖掘，找到频繁项集中所有的关联规则以每个关联规则L都具有相应的支持 度，关联规则L中的子规则Lmk的支持度定义为Suppod(Lmk)，其中，Lm表示关联规则L中大 小为m的关联子规则集合，LmCLmk表示关联子规则集合Lm中的第k条记录，LmkGLm。 Support(Lmk)=ILmkI/IDI，其中ILmkI表示关联规则L中的子规则Lmk出现的次数，IDI表示 资料库D中规则的数量。为了不影响云平台的用户体验，该项操作通常在集群中有空闲资 源时进行，时间间隔Interval根据资料库的变化速率进行调整，IntervalOCIDI/IADI，其 中，IAD|表示单位时间内规则变化的数量，即资 料库变化的越快，进行挖掘的时间间隔越 短，避免资料库未更新时进行冗余的计算，同时可W尽快根据资料库的变化调整关联规则。 [0055] 所述频繁项集，是指在挖掘布尔关联规则的过程中，产生的所有支持度大于最小 支持度的项集，它不关屯、项目的次序，仅考虑项目的组合。
[0化6] 步骤3、在作业的执行过程中，每个子任务根据已经处理过的数据块集合A，依照 关联规则以预测在接下来的计算中可能用到的数据块集合B，并提前加载进内存。按照如 下方式决定预测是否可信：
[0057]预测置信度的计算方式为Confidence(A-B) =Suppo;rt(AUB)/Support炬） [0化引其中，Confidence(A-B)表示处理数据块A后，在接下来的计算中会使用到数据 块B的置信度，[email protected])表示关联规则中出现B的次数，Suppod(AUB)表示关联规则 中同时出现A和B的次数；
[0059] 设置S个置信度阔值C,"gw<Kle、CsMetoek和Cglobd，分别表不数据块集合B所在节点 Nodee与子任务所在节点Node 两者之间，两者为同一节点、两者不在同一节点但在同一 机架、两者不在同一机架上时应该选取的置信度阔值，并有(；"6w<，de<C；"eKaek<Cgl"bd。
[0060] 根据节点Nodee与节点Nodet。日k两者位置关系在C日。meNode、C日ameKaek和Cglobal选取合适 者作为阔值C，当且仅当Confidence(A-B) >C时，认为该预测有效，并进行数据的预读 取。
[0061] 所述预测置信度，是指根据频繁项集的结果推导出的关联规则的可信程度，只有 在该值高于一定阔值的情况下，才会进行数据的预读取。
[0062] 本发明采用的频繁项集挖掘算法，具体如下：
[0063] 输入；资料库DW及阔值e，其中0< 0 <1，出现频率高于阔值0表示该记录T。为 频繁项集
[0064] 输出；关联规则L，其中Lm表示关联规则L中大小为m的子规则集合
[00化]数据结构；该频繁项集挖掘算法需要维护两个变量，缓冲区Buffer与关联规则L 其中Buffer为一个集合，存储最近使用的记录
[0066] 初始状态；Buffer与L均为空集
[0067] 对资料库中的每一条记录Tu执行如下步骤：
[0068]步骤 1;将记录T。.放入缓冲区Buffer中，Buffer=BufferU(T
[0069] 步骤2 ;使用记录Ty更新关联规则L，L=update(TU,。
[0070] 如果关联规则L中数据块个数为2的频繁项集的数量大于p/el，则继续执行步骤 3至步骤5,否则返回步骤1对下一条记录进行处理；
[007"1] 步骤3 ;对关联规则L进行约简，L=eliminate似 [007引步骤4 ;初始时m= 2,当Lm不为空集时，反复执行如下步骤 [007引步骤4. 1 ;令m的值增加1 ;
[0074] 步骤4. 2 ;使用缓冲区Buffer中的每一条记录T。.更新L，L=update(TU,。；
[0075] 步骤4. 3 ;对关联规则L进行约简，L=eliminate(m);
[0076]步骤5;清空缓冲区Buffer,Buffer二 0;
[0077] 上述步骤中提到的更新关联规则L的子程序update具体如下：
[007引输入；一条记录TyW及数据块个数m
[0079] 数据结构；记录Ty的任意子集subsetTU包含一个计数变量countSet，计数变量 countSet表示subsetTy在关联规则L中出现的次数
[0080] 对记录Ty每一个大小为m的子集subsetmTy执行如下步骤；
[OOW] 如果subsetmTu在关联规则Lm中，那么该子集的计数变量countSet的值增加1 ;[00間如果subsetmTu不在关联规则Lm中且m《2,将该子集加入Lm中，Lm= L"UsubsetJij
[008引如果subsetmTy的任意大小为m-1的子集均在关联规则Lm_i中，那么将该子集加入Lm中，Lm=LmUsubsetmT。.，其中，Lm_康示表示关联规则L中大小为m-1的子规则集合。 [0084] 上述步骤中提到的对关联规则L进行约简的子程序eliminate具体如下：
[00化]输入；数据块个数m
[0086] 数据结构：关联子规则集合Lm中的每一个子规则Lmk包含一个计数变量 countRecord，计数变量countRecord表示子规则Lmk在关联规则L中出现的次数
[0087] 对关联子规则集合Lm每一条记录Lmk执行如下步骤：
[008引令该子规则Lmk的计数变量countRecord的值减1，如果计数变量countRecord归零，则将该子规则Lmk在关联子规则集合Lm中删除。
[0089]W上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述 特定实施方式，本领域技术人员可W在权利要求的范围内做出各种变化或修改，该并不影 响本发明的实质内容。
【主权项】
1. 一种基于频繁项集的数据关联性分析和预读取方法，其特征在于，包括如下步骤： 步骤1 :对于用户提交到云平台中的第i个作业Jobi,云平台根据作业Jobi中的每个子 任务Taskj#及到的数据块生成一条记录T u，并将记录Tij存入资料库D中； 其中，了&81^表示作业Job i的第j个子任务；i为正整数，j为正整数；所述记录T u，是 指作业Jobi中的子任务Task u涉及到的数据块的集合； 步骤2 :每隔时间间隔Interval，对资料库D中的数据进行挖掘，找到频繁项集中所有 的关联规则L，关联规则L中大小为m的子规则集合记为Lm，关联子规则集合Lm中的子规则 L mk的支持度定义为Support (Lmk); 其中，Lmk表示关联子规则集合L m中的第k条记录；Support (L mk) = I Lmk I / ID I，I Lmk I表 示关联规则L中的子规则Lmk出现的次数，|D|表示资料库D中关联规则L的数量；时间间 隔Interval根据资料库D的变化速率进行调整，Interval | D|/| ad|，其中，I AD|表示 单位时间内关联规则L变化的数量； 步骤3、在作业Jobi的执行过程中，每个子任务Taskjg据已经处理过的数据块集合A， 依照关联规则L，预测在接下来的计算中可能用到的数据块集合B，并提前加载进内存；按 照如下方式决定预测是否可信： 预测置信度的计算方式为 Confidence (A - B) = Support (A U B)/Support (B) 其中，Conf idence (A - B)表示处理数据块集合A后，在接下来的计算中会使用 到数据块集合B的置信度，Support (B)表示关联规则L中出现数据块集合B的次数， Support(A U B)表示关联规则L中同时出现数据块集合A和数据块集合B的次数； 设置三个置信度阈值CsanieN()de、 CsameRack、Cgiobal^ 分别表示数据块集合B所在节点 此(1%与子任务Task i」所在节点Node task两者之间的位置关系为两者在同一节点、两 者不在同一节点但在同一机架、两者不在同一机架上时应该选取的置信度阈值，并有 p /n /n I LsameNode、LsameRack、^global， 根据节点NodeB与节点Node task两者之间的位置关系在C sameNode ^ ^sameEack 以及C global 中选 取对应的置信度阈值作为阈值C，当且仅当Conf idence (A - B)彡C时，认为该预测有效，并 进行数据的预读取。2. 根据权利要求1所述的基于频繁项集的数据关联性分析和预读取方法，其特征在 于，所述对资料库D中的数据进行挖掘，采用的如下频繁项集挖掘算法： 步骤AO :设置阈值Θ，其中，〇〈 Θ〈1 ;设置缓冲区Buffer与关联规则L，并将缓冲区 Buffer与关联规则L的初始状态均设置为空集；其中Buffer为一个集合，用于存储最近使 用的记录； 对资料库D中的每一条记录执行如下步骤： 步骤Al :将一记录放入缓冲区Buffer中； 步骤A2 :使用该记录更新关联规则L ; 将在关联规则L中出现频率高于阈值Θ的记录认定为频繁项集；如果关联规则L中涉 及到的数据块个数为2的频繁项集的数量大于Ρ/θ I，则进入步骤3,否则返回步骤1对下一 条记录进行处理； 步骤A3 :令m = 2,对关联规则L进行约简； 步骤A4 :设置m初始值为2,反复执行如下步骤A4. 1至A4. 3,直到LmS空集时进入步 骤A5 : 步骤A4. 1 :将m的值增加1 ; 步骤A4. 2 :使用缓冲区Buffer中的每一条记录更新关联规则L ; 步骤A4. 3 :对关联规则L进行约简； 步骤A5:清空缓冲区。3. 根据权利要求2所述的基于频繁项集的数据关联性分析和预读取方法，其特征在 于，所述更新关联规则L，具体如下： 对记录Tij每一个大小为m的子集subset Jij执行如下步骤： -如果子集SubsetJij在关联子规则集合1^中，则令该子集subset Jij的计数变量 countSet的值增加1 ;其中，记录Tij的任意子集subsetT u包含一个计数变量countSet，计 数变量countSet表示子集SubsetTij在关联规则L中出现的次数； -如果子集SubsetJij不在关联子规则集合Lm中且2,则将该子集subset Jij加入 关联子规则集合Lni中； -如果SubsetmTij的任意大小为m-Ι的子集均在关联子规则集合L ^中，则将该子集 SUbsetmIu加入关联子规则集合Lm中；其中，Lnrl表示表示关联规则L中大小为m-Ι的子规 则集合。4. 根据权利要求2所述的基于频繁项集的数据关联性分析和预读取方法，其特征在 于，所述对关联规则L进行约简，具体为： 对关联子规则集合1^中每一条子规则Lmk执行如下步骤： 令该子规则Lmk的计数变量countRecord的值减1，如果计数变量countRecord归零， 则将该子规则Lmk在关联子规则集合L _"中删除；其中，关联子规则集合L _"中的每一个子规 则Lmk包含一个计数变量countRecord，计数变量countRecord表示子规则L mk在关联规则 L中出现的次数。
【专利摘要】本发明提供了一种基于频繁项集的数据关联性分析和预读取方法，包括步骤如下：云平台每处理一个作业，将该次作业中每一个子任务处理的数据块作为一条记录存入资料库中；每隔一定时间利用集群的空闲资源对资料库中的频繁项集进行挖掘，找出数据块之间的关联性；在之后作业的执行过程中，根据预测的置信度，结合数据与任务所在节点的位置关系，提前读取所需要的数据块，从而达到提升整个集群吞吐率的目的。
【IPC分类】G06F17/30
【公开号】CN104881467
【申请号】CN201510275426
【发明人】唐飞龙, 张健桐, 栾志坤, 张杨, 王玉凤, 房新宇, 唐灿, 过敏意
【申请人】上海交通大学
【公开日】2015年9月2日
【申请日】2015年5月26日