欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2021103719774
申请人: 长春理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-02-28
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种面向负载均衡的动态均衡分区方法,其特征在于,包括:

将传入Map端的任务数据存储至数据链表中;所述数据链表为Sum类型;所述任务数据以元组的形式存储至所述数据链表,所述数据链表中存储每个元组的数据值和对应的数据量;

将所述数据链表中的所有元组按照数据量排序,得到排序后的数据链表;

根据Reduce节点的数量构建相应数量的预分区链表;预分区链表与Reduce节点一一对应;

将所述排序后的数据链表中数据量大于数据量阈值的每个元祖,均按照所述预分区链表的数量进行切分,并平均分配到所有预分区链表中进行存储;所述数据量阈值为数据链表的数据量上限与预分区链表数量的比值;

将所述数据链表中数据量不大于数据量阈值的元组,按照在数据链表中的顺序,基于最佳适应算法的分区分配原则依次分配到不同的预分区链表中进行存储;

当所述数据链表中的所有元组均被分配到所述预分区链表中进行存储时,通过索引将每个预分区链表中的元组分配到对应的Reduce节点上。

2.根据权利要求1所述的面向负载均衡的动态均衡分区方法,其特征在于,所述将传入Map端的任务数据存储至数据链表中,具体包括:在Map阶段构建WordSum()函数依次将传入Map端的任务数据按照元组进行统计;

按照所述数据链表的数据量上限确定待存储的任务数据;所述待存储的任务数据为统计的部分任务数据;

将所述待存储的任务数据存储至所述数据链表。

3.根据权利要求2所述的面向负载均衡的动态均衡分区方法,其特征在于,所述当所述数据链表中的所有元组均被分配到所述预分区链表中进行存储时,通过索引将每个预分区链表中的元组分配到对应的Reduce节点上,之后还包括:根据所述数据链表的数据链上限更新待存储的任务数据;更新后的待存储的任务数据为已被统计但未被存储过的部分任务数据;

将更新后的待存储的任务数据存储至所述数据链表;

返回“将所述数据链表中的所有元组按照数据量排序,得到排序后的数据链表”步骤。

4.根据权利要求1所述的面向负载均衡的动态均衡分区方法,其特征在于,所述将所述排序后的数据链表中数据量大于数据量阈值的每个元祖,均按照所述预分区链表的数量进行切分,并平均分配到所有预分区链表中,具体包括:对于所述排序后的数据链表的第i个元组,判断所述第i个元组的数据量是否大于数据量阈值;

当所述第i个元组的数据量大于数据量阈值时,按照所述预分区链表的数量将所述第i个元组的数据进行平均切分,将切分后的数据平均分配到所有预分区链表中存储;

若所述数据链表中的所有元组按照数据量降序排序,则将i更新为i+1,返回“判断所述第i个元组的数据量是否大于数据量阈值”的步骤;若所述数据链表中的所有元组按照数据量升序排序,则将i更新为i‑1,返回“判断所述第i个元组的数据量是否大于数据量阈值”的步骤;

当所述第i个元组的数据量不大于数据量阈值时,若所述数据链表中的所有元组按照数据量降序排序,则将所述数据链表中第i个元组之后的所有元组确定为数据量不大于数据量阈值的元组;若所述数据链表中的所有元组按照数据量升序排序,则将所述数据链表中第i个元组之前的所有元组确定为数据量不大于数据量阈值的元组。

5.根据权利要求1所述的面向负载均衡的动态均衡分区方法,其特征在于,所述将所述数据链表中数据量不大于数据量阈值的元组,按照在数据链表中的顺序,基于最佳适应算法的分区分配原则依次分配到不同的预分区链表中进行存储,具体包括:第一轮分配时:将所述数据链表中数据量不大于数据量阈值的元组,按照所述预分区链表的数量,依次为每个预分区链表分配一个元组;

在第2‑n轮分配时:按照当前预分区链表的已存储量降序的方式将所有预分区链表进行排序,得到预分区链表序列;n为将所述数据链表中数据量不大于数据量阈值的元组分配完所需的轮数;

判断所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值是否大于差值阈值;

当所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值大于差值阈值时,将当前数据链表中未被分配且数据量不大于数据量阈值的元组中的N‑1个元组依次分配到所述预分区链表序列中第二个预分区链表至第N个预分区链表中;其中,N为预分区链表序列中预分区链表的个数;

当所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值不大于差值阈值时,将当前数据链表中未被分配且数据量不大于数据量阈值的元组中的N个元组依次分配到所述预分区链表序列中的N个预分区链表中;

更新当前数据链表中未被分配且数据量不大于数据量阈值的元组,进入下一轮分配,直至数据链表中未被分配且数据量不大于数据量阈值的元组为零。

6.一种面向负载均衡的动态均衡分区系统,其特征在于,包括:

数据链表存储模块,用于将传入Map端的任务数据存储至数据链表中;所述数据链表为Sum类型;所述任务数据以元组的形式存储至所述数据链表,所述数据链表中存储每个元组的数据值和对应的数据量;

数据链表排序模块,用于将所述数据链表中的所有元组按照数据量排序,得到排序后的数据链表;

预分区链表构建模块,用于根据Reduce节点的数量构建相应数量的预分区链表;预分区链表与Reduce节点一一对应;

第一分配模块,用于将所述排序后的数据链表中数据量大于数据量阈值的每个元祖,均按照所述预分区链表的数量进行切分,并平均分配到所有预分区链表中进行存储;所述数据量阈值为数据链表的数据量上限与预分区链表数量的比值;

第二分配模块,用于将所述数据链表中数据量不大于数据量阈值的元组,按照在数据链表中的顺序,基于最佳适应算法的分区分配原则依次分配到不同的预分区链表中进行存储;

索引模块,用于当所述数据链表中的所有元组均被分配到所述预分区链表中进行存储时,通过索引将每个预分区链表中的元组分配到对应的Reduce节点上。

7.根据权利要求6所述的面向负载均衡的动态均衡分区系统,其特征在于,所述数据链表存储模块,具体包括:任务数据统计单元,用于在Map阶段构建WordSum()函数依次将传入Map端的任务数据按照元组进行统计;

待存储任务数据确定单元,用于按照所述数据链表的数据量上限确定待存储的任务数据;所述待存储的任务数据为统计的部分任务数据;

存储单元,用于将所述待存储的任务数据存储至所述数据链表。

8.根据权利要求7所述的面向负载均衡的动态均衡分区系统,其特征在于,所述数据链表存储模块还包括:待存储任务数据更新单元,用于当所述数据链表中的所有元组均被分配到所述预分区链表中进行存储时,通过索引将每个预分区链表中的元组分配到对应的Reduce节点上之后,根据所述数据链表的数据链上限更新待存储的任务数据;更新后的待存储的任务数据为已被统计但未被存储过的部分任务数据;

所述存储单元,用于将更新后的待存储的任务数据存储至所述数据链表;

返回单元,用于返回所述数据链表排序模块。

9.根据权利要求6所述的面向负载均衡的动态均衡分区系统,其特征在于,所述第一分配模块,具体包括:数据量判断单元,用于对于所述排序后的数据链表的第i个元组,判断所述第i个元组的数据量是否大于数据量阈值;

均分存储单元,用于当所述第i个元组的数据量大于数据量阈值时,按照所述预分区链表的数量将所述第i个元组的数据进行平均切分,将切分后的数据平均分配到所有预分区链表中存储;

元组更新单元,用于当所述数据链表中的所有元组按照数据量降序排序时,将i更新为i+1,返回所述数据量判断单元;当所述数据链表中的所有元组按照数据量升序排序时,将i更新为i‑1,返回所述数据量判断单元;

数据量不大于数据量阈值的元组确定单元,用于当所述第i个元组的数据量不大于数据量阈值时,若所述数据链表中的所有元组按照数据量降序排序,则将所述数据链表中第i个元组之后的所有元组确定为数据量不大于数据量阈值的元组;若所述数据链表中的所有元组按照数据量升序排序,则将所述数据链表中第i个元组之前的所有元组确定为数据量不大于数据量阈值的元组。

10.根据权利要求6所述的面向负载均衡的动态均衡分区系统,其特征在于,所述第二分配模块,具体包括:首轮分配单元,用于第一轮分配时:将所述数据链表中数据量不大于数据量阈值的元组,按照所述预分区链表的数量,依次为每个预分区链表分配一个元组;

预分区链表排序单元,用于在第2‑n轮分配时,按照当前预分区链表的已存储量降序的方式将所有预分区链表进行排序,得到预分区链表序列;n为将所述数据链表中数据量不大于数据量阈值的元组分配完所需的轮数;

已存储量差值判断单元,用于判断所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值是否大于差值阈值;

元组分配单元,用于当所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值大于差值阈值时,将当前数据链表中未被分配且数据量不大于数据量阈值的元组中的N‑1个元组依次分配到所述预分区链表序列中第二个预分区链表至第N个预分区链表中;其中,N为预分区链表序列中预分区链表的个数;当所述预分区链表序列中第一个预分区链表的已存储量与第二个预分区链表的已存储量的差值不大于差值阈值时,将当前数据链表中未被分配且数据量不大于数据量阈值的元组中的N个元组依次分配到所述预分区链表序列中的N个预分区链表中;

未被分配且数据量不大于数据量阈值的元组更新单元,用于更新当前数据链表中未被分配且数据量不大于数据量阈值的元组,进入下一轮分配,直至数据链表中未被分配且数据量不大于数据量阈值的元组为零。