欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2019110447512
申请人: 重庆邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2024-02-26
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,所述策略包括如下步骤:S1.将缓存节点内存大小、处理器内核总数及磁盘大小作为独立信息数据波动赋权法的输入指标,计算各缓存节点性能量化值及性能量化值占比;

S2.设置虚拟节点总数为缓存节点个数的200‑300倍,根据虚拟节点总数和步骤S1中各缓存节点性能量化值占比,计算各缓存节点应分得的虚拟节点数目;

S3.利用Random函数为每个缓存节点生成对应数目的虚拟节点;

S4.计算各缓存节点拥有虚拟节点数的最大公约数m,将一致性哈希环均分为m段弧,通过MD5函数将各缓存节点拥有的虚拟节点均匀映射到一致性哈希环的各段弧上;

S5.请求到达负载均衡器时,负载均衡器更新集群缓存代理负载量和各缓存节点负载上限值;

S6.将请求的URL作为步骤S4中MD5函数的输入,利用有限负载一致性哈希的请求分配策略在一致性哈希环上选择虚拟节点,并利用拥有该虚拟节点的缓存节点进行服务;

所述步骤S1中,独立信息数据波动赋权法计算各缓存节点性能量化值及性能量化值占比的具体过程如下:S11.计算指标j的离差系数Vj,计算公式如下:其中,δj表示指标j的标准差, 表示指标j的均值,j∈[1,3];

S12.遍历所有指标,依次将指标j作为函数输出,其他指标作为输入进行回归运算,得到指标j的决定系数 和独立信息程度Dj;

S13.归一化Vj得到Vj′,归一化Dj得到Dj′;

S14.计算指标j的纯量信息Ij,计算公式如下:Ij=Vj′×Dj′

S15.计算指标j的权重值Wj,计算公式如下:其中,i表示指标个数;

S16.计算指标j的归一化值Qj,计算公式如下:其中,Tj表示指标j包含的样本集,Max(Tj)表示指标j的最大值;

S17.将Qj与该指标权重值Wj线性加权,得到缓存节点n的性能量化值Fn,计算公式如下:其中,n∈[1,s],s表示缓存节点数目;

S18.计算缓存节点n的性能量化值占比θn,计算公式如下:所述步骤S4中利用MD5函数将各缓存节点拥有的虚拟节点均匀映射到一致性哈希环各段弧上的过程具体如下:S41.计算矩阵N中各元素的最大公约数m,将一致性哈希环均分为m段弧;

S42.计算每个缓存节点在每段弧上需要分配的虚拟节点数量,构成集合C,如下所示:S43.计算一致性哈希环上每段弧的长度davg,如下所示:其中,Hmax表示哈希环的最大值;

S44.定位当前弧区间编号k,初始值k=1;

S45.比较当前弧区间编号k是否大于m,如果大于m,则结束执行,虚拟节点映射完成;否则执行步骤S46;

S46.计算当前弧区间起始坐标Bs,如下式所示:S47.循环各缓存节点,参照集合C中各元素值,为每个缓存节点随机取出对应数量的虚拟节点,将各虚拟节点主机号作为MD5函数输入,得到各虚拟节点哈希值,如下所示:Hv=MD5(Sv)

其中,Sv表示第v个虚拟节点的主机号,Hv表示第v个虚拟节点的哈希值,v∈[1,Nt];

S48.将各虚拟节点映射到当前弧区间内;

S49.递增当前弧区间编号k,跳转至步骤S44;

所述步骤S6中,在一致性哈希环上选择虚拟节点的过程如下:S61.将请求的URL作为步骤S47中MD5函数的输入,得到请求的哈希值,如下所示:Hr=MD5(Sr)

其中,Sr表示请求r的URL,Hr表示请求r的哈希值;

S62.将Hr映射到一致性哈希环上,以Hr的位置为起点,找出顺时针方向的首个虚拟节点Vf;

S63.搜索拥有虚拟节点Vf的缓存节点,如果该缓存节点当前负载已达到其负载上限,则用该虚拟节点Vf的值更新Hr的值,并跳转至步骤S62;否则,选择该缓存节点提供服务,如下所示:Hr=Val(Vf)

其中,Val(Vf)表示虚拟节点Vf的哈希值;

S64.如果遍历相邻两段弧上所有虚拟节点均未找到能够提供服务的缓存节点,则结束搜索,直接返回。

2.根据权利要求1所述的一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,步骤S12中所述指标j的决定系数 和独立信息程度Dj获取过程如下:设置s组观察值,每组观察值包含内存大小、处理器内核总数及硬盘大小三个指标,构建评价矩阵As×3,求得指标j的平均值 将指标j作为因变量,其余指标作为自变量,构建多元线性回归模型如下式所示:2

其中,β0~3表示回归系数,ε是均值为0、方差为σ(σ>0)的随机变量,求得回归系数后,带入自变量可以得到自变量与因变量的线性关系如下所示:其中, 为因变量线性回归后的结果;

可得指标j的复相关系数Rj和独立信息程度Dj如下所示:

3.根据权利要求2所述的一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,步骤S2中各缓存节点应分得的虚拟节点数目计算如下:Nn=Nt×θn

其中,Nt表示虚拟节点总数,Nn表示缓存节点n拥有的虚拟节点数。

4.根据权利要求3所述的一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,所述S3步骤具体如下:利用各缓存节点拥有的虚拟节点数构建矩阵N,如下所示:N=(N1 N2 … Nn … Ns‑1 Ns)利用Random函数并参照矩阵N中各元素值,为每个缓存节点随机生成对应数目的唯一虚拟节点主机号(IP:Port)。

5.根据权利要求4所述的一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,步骤S48中将各虚拟节点映射到当前弧区间内,如下所示:其中,Bc(v)表示第v个虚拟节点在当前弧上的位置,如果Bc(v)在当前弧上已被其他虚拟节点占用,则重新生成Sv后,执行步骤S47。

6.根据权利要求5所述的一种基于虚拟节点的有限负载一致性哈希负载均衡策略,其特征在于,步骤S5中,各缓存节点负载上限计算过程如下:S51.新的请求到达负载均衡器后,计算集群缓存代理的总负载量Lt,如下所示:其中,Ln表示当前时刻缓存节点n的负载量,Lnew表示当前时刻的新增负载量;

S52.计算集群缓存代理的平均负载Lavg,如下所示:S53.计算集群缓存代理中各缓存节点的平均性能量化值Favg,如下所示:S54.为每个缓存节点保留1.2倍的负载裕量,更新各缓存节点负载上限,如下所示:其中,Lc(n)表示当前时刻缓存节点n的负载上限。