一种分布式系统热点数据的管理方法转让专利
申请号 : CN202110270811.3
文献号 : CN112988892B
文献日 : 2022-04-29
发明人 : 胡凯 , 王子凯
申请人 : 北京航空航天大学
摘要 :
权利要求 :
1.一种分布式系统热点数据的管理方法,其特征在于包括:步骤1,输入一段数据访问请求流,基于三阶段流式热点数据探测算法进行数据抽样、数据过滤以及数据统计,获得所述请求流中的热点数据集合;
步骤2,基于集群负载均衡法对任意时刻所述分布式系统的整个集群负载情况进行分析;
步骤3,根据所述步骤2的分析结果确定是否建立所述热点数据集合的副本,如果确定建立,则基于副本自适应方法建立符合数据访问请求流的时间特征的所述热点数据集合的副本;所述步骤1中所述三阶段流式热点数据探测算法的所述数据抽样采用简单随机抽样;
所述步骤1中所述三阶段流式热点数据探测算法的所述数据过滤采用改良多重布隆过滤器,在传统的布隆过滤器基础上,将过滤器的数量从1个拓展至k个,并且将传统布隆过滤器中的0/1标志位替换为整数计数器,过滤器上任意位置被访问一次,则对应的计数器值加一,当请求被抽样后,对一个数据请求进行分析时,由k个哈希函数对数据对象的key进行计算,生成k个不同的值组成数组P=[p1,p2,…pk],对应k个不同的位置;在拓展至k个过滤器的计数器数组中,依次从数组P中取出值,作为对应计数器数组的对应位置,获取该位置计数器的值,得到计数器值数组V[v1,v2,…vk];对于数组V中的元素,若最小的元素值大于多重布隆计数器的阈值Threshold,则此数据对象通过过滤,通过过滤的数据作为频繁数据进入下一个阶段;所述步骤1中所述三阶段流式热点数据探测算法的所述数据统计基于时间窗口进行热点数据探测,在经历了数据抽样和数据过滤后,仍然留存的数据为频繁数据,所述频繁数据有成为热点数据的可能,为了体现所述热点数据的强时间特征,数据统计阶段将频繁数据对应的请求序列按照时间窗口划分,通过设定时间窗口的长度s,将发生时间相近的数据请求归为同一个处理集合sr,对于某一个sr集合,其中的任意一个数据请求r将会计算一个衡量参数f,计算公式如下:
f=df+pf
其中df代表了当前数据内容在当前时间窗口的访问次数,pf代表了当前数据内容在上一个时间窗口的访问次数,当数据请求r中的数据内容的衡量参数f大于数据统计阶段的Threshold‑3,则将其判断为热点数据;数据统计阶段维护了一个长度为k的计数器池C;当出现了新的热点数据后,如果数据对象不在计数器池中,而且当前计数器池中数据对象的数目小于计数器池的最大长度k,则将当前数据对象放入计数器池中;如果数据对象不在计数器池中而且当前计数器池中数据对象的数目已经达到计数器池的最大长度,则对于当前计数器池中的所有数据对象,对应的计数器值减1,如果出现某个数据对象对应的计数器值为0,则将该数据对象移出计数器池,为了将时间参数与数据的访问情况向匹配,计数器池C中的计数器数字在每进行一轮新的数据统计阶段时,将减少为之前的1/2,向下取整。
2.根据权利要求1所述的一种分布式系统热点数据的管理方法,其特征在于:所述步骤
2中所述集群负载均衡法包括:
对任意时刻集群负载的情况作出评估,当集群完全负载均衡时,所有数据服务器节点的负载均等于平均负载量,通过考察集群不均衡系数avg衡量集群负载是否均衡,在本系统的集群负载均衡法中,所述avg的值等于各个数据服务器的负载量与集群平均负载量之差的绝对值之和占总负载的比率,计算公式如下:其中,loadi表示每一个机器的负载量,l为集群负载量的平均值,n为集群机器个数;当负载不均衡系数avg大于系统设定的阈值时,从热点数据挖掘方法中得到的热点数据开始进行副本创建和副本分配;否则不进行任何与数据副本相关的操作,从而节约了整个系统的资源消耗。
3.根据权利要求1所述的一种分布式系统热点数据的管理方法,其特征在于所述步骤3中所述副本自适应方法包括:当一次热点数据的挖掘结束后,检查每一个当前挖掘出的热点数据对象,如果数据对象在之前的热点数据挖掘中没有被判定为热点数据,则该热点数据的副本创建数量为1;如果数据对象在之前的热点数据挖掘中已经被判定为热点数据,则将该数据对应的副本创建数量加倍;之后对已经存在副本的数据对象进行检查,如果存在数据对象在本次热点数据挖掘中并没有被判断为热点数据,当本次时间窗口该数据未被访问,则将该数据设置为未访问状态,否则不改变其副本创建数量;当已创建副本的数据对象在多个时间窗口中均为未访问状态时,每经过一个时间窗口,该数据对象的副本创建数量以之前增长的方式减少,直到其副本创建数量小于1时,该数据不再拥有副本。
说明书 :
一种分布式系统热点数据的管理方法
技术领域
背景技术
群负载不均衡的重要原因。由于实际的生成环境中,互联网内数据请求随时间表现出连续
不断且不均匀不规律的特性,因此热点数据挖掘的方法也必须具有实时性和准确性。当前
的热点数据挖掘方法均存在着各自的缺陷:如无法实时获得热点数据,或无法保证热点数
据的准确性等。
发明内容
点数据探测的实时性和高效性,以解决上述背景技术中提出的问题。
合的副本。
传统布隆过滤器中的0/1标志位替换为整数计数器,过滤器上任意位置被访问一次,则对应
的计数器值加一,当请求被抽样后,对一个数据请求进行分析时,由k个哈希函数对数据对
象的key进行计算,生成k个不同的值组成数组P=[p1,p2,…pk],对应k个不同的位置;在拓
展至k个过滤器的计数器数组中,依次从数组P中取出值,作为对应计数器数组的对应位置,
获取该位置计数器的值,得到计数器值数组V[v1,v2,…vk];对于数组V中的元素,若最小的
元素值大于多重布隆计数器的阈值Threshold,则此数据对象通过过滤,通过过滤的数据作
为频繁数据进入下一个阶段。
所述频繁数据有成为热点数据的可能,为了体现所述热点数据的强时间特征,数据统计阶
段将频繁数据对应的请求序列按照时间窗口划分,通过设定时间窗口的长度s,将发生时间
相近的数据请求归为同一个处理集合sr,对于某一个sr集合,其中的任意一个数据请求r将
会计算一个衡量参数f,计算公式如下:
的Threshold‑3,则将其判断为热点数据;数据统计阶段维护了一个长度为k的计数器池C。
当出现了新的热点数据后,如果数据对象不在计数器池中,而且当前计数器池中数据对象
的数目小于计数器池的最大长度k,则将当前数据对象放入计数器池中;如果数据对象不在
计数器池中而且当前计数器池中数据对象的数目已经达到计数器池的最大长度,则对于当
前计数器池中的所有数据对象,对应的计数器值减1,如果出现某个数据对象对应的计数器
值为0,则将该数据对象移出计数器池,为了将时间参数与数据的访问情况向匹配,计数器
池C中的计数器数字在每进行一轮新的数据统计阶段时,将减少为之前的1/2,向下取整。
系统的集群负载均衡法中,所述avg的值等于各个数据服务器的负载量与集群平均负载量
之差的绝对值之和占总负载的比率,计算公式如下:
开始进行副本创建和副本分配;否则不进行任何与数据副本相关的操作,从而节约了整个
系统的资源消耗。
定为热点数据,则该热点数据的副本创建数量为1;如果数据对象在之前的热点数据挖掘中
已经被判定为热点数据,则将该数据对应的副本创建数量加倍。之后对已经存在副本的数
据对象进行检查,如果存在数据对象在本次热点数据挖掘中并没有被判断为热点数据,当
本次时间窗口该数据未被访问,则将该数据设置为未访问状态,否则不改变其副本创建数
量;当已创建副本的数据对象在多个时间窗口中均为未访问状态时,每经过一个时间窗口,
该数据对象的副本创建数量以之前增长的方式减少,直到其副本创建数量小于1时,该数据
不再拥有副本。
附图说明
附图未必是按比例绘制的。本发明的目标及特征考虑到如下结合附图的描述将更加明显,
附图中:
具体实施方式
段、数据过滤阶段和数据统计分析阶段。流程如图1所示。
过多,本算法对整个数据访问请求使用了随机抽样的方式。由于随机抽样不改变整个数据
访问请求流的统计特征的情况,本算法在不影响输出结果正确性的基础上,保证了热点数
据探测的效率。
每一个数据请求有a的概率被抽样。参数a的值可以在应用场景中进行调整,防止抽样数据
量过大或过小,影响本算法的实际表现。
中的0/1标志位替换为整数计数器。过滤器上任意位置被访问一次,则对应的计数器值加
一。
k个过滤器的计数器数组中,依次从数组P中取出值,作为对应计数器数组的对应位置,获取
该位置计数器的值,得到计数器值数组V[v1,v2,…vk]。对于数组V中的元素,若最小的元素
值大于多重布隆计数器的阈值Threshold,则此数据对象通过过滤。通过过滤的数据被称为
频繁数据,进入下一个阶段。图2为从数据对象的key获取计数器值数组的过程。
请求序列按照时间窗口划分。通过设定时间窗口的长度s,将发生时间相近的数据请求归为
同一个处理集合sr。
的Threshold‑3,则将其判断为热点数据。
于计数器池的最大长度k,则将当前数据对象放入计数器池中;如果数据对象不在计数器池
中而且当前计数器池中数据对象的数目已经达到计数器池的最大长度,则对于当前计数器
池中的所有数据对象,对应的计数器值减1,如果出现某个数据对象对应的计数器值为0,则
将该数据对象移出计数器池。
下的创建和回收,从而使得集群负载不均衡的问题得到解决。本实施例相比于现有的副本
管理方法有着以下的特点:
数据的副本创建数量为1;如果数据对象在之前的热点数据挖掘中已经被判定为热点数据,
则将该数据对应的副本创建数量加倍。之后对已经存在副本的数据对象进行检查,如果存
在数据对象在本次热点数据挖掘中并没有被判断为热点数据,当本次时间窗口该数据未被
访问,则将该数据设置为未访问状态,否则不改变其副本创建数量。当已创建副本的数据对
象在多个时间窗口中均为未访问状态时,每经过一个时间窗口,该数据对象的副本创建数
量以之前增长的方式减少,直到其副本创建数量小于1时,该数据不在拥有副本。图3为某数
据的副本自适应过程实例:
直至16(设该集群的最大机器数为16)。在时间窗口10中,由于从时间窗口9开始,系统未访
问该数据,则回收副本直至副本剩余数为2。之后重新开始以数据访问情况建立副本
节约了宝贵的系统资源。
统的负载均衡算法决定的。在集群负载完全均衡的场景下,比如热点数据完全平均的存在
于每一个数据服务器节点上,若每一个作为数据服务器节点的真实机器性能相同,则进行
热点数据挖掘和副本创建并不能提高整个集群的性能。而热点数据副本被创建到哪一个数
据服务器节点,将会导致整个热点数据访问请求改变之前的分布情况,从而对整个集群的
性能产生至关重要的影响。
的方案为考察集群不均衡系数avg,在本系统的集群负载均衡方法中,avg的值等于各个数
据服务器的负载量与集群平均负载量之差的绝对值之和占总负载的比率。计算公式如下:
系统设定的阈值时,从热点数据挖掘方法中得到的热点数据开始进行副本创建和副本分
配;否则不进行任何与数据副本相关的操作,从而节约了整个系统的资源消耗。
保护范围和精神的情况下对本发明的实施例能够进行改动和修改。