本发明涉及通信技术领域， 尤其涉及一种分布式緩存资源调度的方法、 装置及系统。

背景技术

目前， 分布式緩存是 IT技术领域中， 特别是 Web技术领域中， 普遍使用 的一项緩存技术， 其主要应用于网页页面緩存、 数据库緩存等方面以满足用 户对网络系统响应速度的要求。

在分布式緩存系统中， 緩存客户端的数据需要通过一定的负载均衡算 法 来分布到各个緩存节点上； 目前最常用的负载均衡算法是 hash (哈希）算法， 而一致性 hash算法（ Consistent Hashing )又是 hash算法中使用比较广泛的一 种。

在基于一致性 hash算法的分布式緩存系统中， 所有的緩存节点可以是均 布于一个虚拟圆结构上（以下简称 "圆"；)， 当使用一般的 hash函数时， 物理 服务器的映射点分布非常不均匀， 现有技术中可以通过设置虚拟节点的方法， 为每个物理服务器分配若干个虚拟节点（例如 ， 100〜200 )， 由于所述 100〜200 个虚拟节点均布在所述 "圆" 上而且每个虚拟节点的覆盖范围都很小， 因此 可以起到均衡不同緩存节点上的负载的效果。 但是， 由于需要设置虚拟节点 的数量很大， 会使得緩存客户端的计算量也变得很大， 增重緩存客户端的负 担； 同时， 在布设有虚拟节点的 "圆" 中再次出现负载不均时， 现有技术仍 然无法对緩存节点上的负载进行及时调整。

而针对分布式緩存系统中整体负载过高或者过 低的情况， 目前还没有比 较有效的方式来对分布式緩存系统中的资源分 布进行调度。

发明内容

本发明的实施例提供一种分布式緩存资源调度 的方法、 装置及系统， 用 以实现分布式緩存系统中资源分布的自动化调 度， 使资源分布处于平衡状态。 为达到上述目的， 本发明的实施例采用如下技术方案：

一种分布式緩存资源调度的方法， 在分布式緩存系统中各緩存节点分布 在一个基于一致性哈希算法的虚拟圆上， 所述方法包括：

对分布式緩存系统中的各緩存节点的负载值进 行监控；

根据所述负载值判断当前分布式緩存系统中是 否存在负载异常； 若当前分布式緩存系统中存在负载异常， 则对所述分布式緩存系统中的 緩存节点的布局进行调整。

一种分布式緩存资源调度的方法， 包括：

接收緩存管理装置发送的通知消息， 该消息中包含有分布式緩存系统的 虚拟圆上即将丢失数据的哈希段对应的旧緩存 节点的位置信息；

在当前緩存节点上不存在緩存客户端要读取的 数据时， 根据所述位置信 息访问所述旧緩存节点以获取并保存所述数据 ；

其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

一种緩存管理装置 , 该緩存管理装置所在的分布式緩存系统中各緩 存节 点分布在一个基于一致性哈希算法的虚拟圆上 ， 所述緩存管理装置包括： 监控单元， 用于对分布式緩存系统中的各緩存节点的负载 值进行监控； 判断单元， 用于根据所述负载值判断当前分布式緩存系统 中是否存在负 载异常；

调整单元， 用于在当前分布式緩存系统中存在负载异常时 ， 对所述分布 式緩存系统中的緩存节点的布局进行调整。

一种緩存节点， 包括：

接收单元， 用于接收緩存管理装置发送的通知消息， 该消息中包含有分 布式緩存系统的虚拟圆上即将丢失数据的哈希 段对应的旧緩存节点的位置信 获取单元， 用于在当前緩存节点上不存在緩存客户端要读 取的数据时 , 根据所述位置信息访问所述旧緩存节点以获取 并保存所述数据；

其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

一种分布式緩存系统， 包括緩存客户端、 緩存管理装置及多个緩存节点， 在该分布式緩存系统中所述多个緩存节点分布 在一个基于一致性哈希算法的 虚拟圆上； 其中，

所述緩存客户端 , 用于根据一致性哈希算法将数据分布到所述多 个緩存 节点上；

所述緩存管理装置 , 用于对分布式緩存系统中的各緩存节点的负载 值进 行监控， 并根据所述负载值判断当前分布式緩存系统中 是否存在负载异常； 若存在异常， 则对所述多个緩存节点的布局进行调整； 其中， 所述负载异常 包括负载不均、 负载过高或者负载过低。

本发明实施例提供的分布式緩存资源调度的方 法、 装置及系统， 在当前 分布式緩存系统中存在负载异常时， 通过调整緩存节点之间的布局来改变不 同緩存节点所承担的负载量， 实现分布式緩存系统中资源分布的自动化调度 ， 使所述分布式緩存系统中的资源分布呈一种平 衡状态。

附图说明

为了更清楚地说明本发明实施例或现有技术中 的技术方案， 下面将对实 施例描述中所需要使用的附图作简单地介绍， 显而易见地， 下面描述中的附 图仅仅是本发明的一些实施例， 对于本领域普通技术人员来讲， 在不付出创 造性劳动性的前提下， 还可以根据这些附图获得其他的附图。

图 1为现有的通过一致性 hash算法来实现分布式緩存的原理示意图； 图 2为本发明实施例一中分布式緩存资源调度的� �法的流程图； 图 3为本发明实施例一中緩存管理装置的结构示� �图；

图 4为本发明实施例二中分布式緩存资源调度的� �法的流程图； 图 5为本发明实施例二中緩存节点的结构示意图� �

图 6为本发明实施例三中移动緩存节点位置的方� �流程图；

图 7为本发明实施例三中的分布式緩存系统的虚� �圆结构示意图一； 图 8为本发明实施例三中的分布式緩存系统的虚� �圆结构示意图二； 图 9为本发明实施例四中添加緩存节点的方法流� �图；

图 10为本发明实施例四中的分布式緩存系统的虚� ��圆结构示意图； 图 11为本发明实施例五中移除緩存节点的方法流� ��图；

图 12为本发明实施例五中的分布式緩存系统的虚� ��圆结构示意图； 图 13为本发明实施例六中的緩存管理装置的结构� ��意图；

图 14为本发明实施例六提供的緩存管理装置中移� ��模块的结构示意图； 图 15为本发明实施例六提供的緩存管理装置中增� ��模块的结构示意图； 图 16为本发明实施例六提供的緩存管理装置中移� ��模块的结构示意图； 图 17为本发明实施例六提供的緩存节点的结构示� ��图；

图 18为本发明实施例六提供的分布式緩存系统的� ��构示意图。

具体实施方式

下面将结合本发明实施例中的附图， 对本发明实施例中的技术方案进行 清楚、 完整地描述， 显然， 所描述的实施例仅仅是本发明一部分实施例， 而 不是全部的实施例。 基于本发明中的实施例， 本领域普通技术人员在没有做 出创造性劳动前提下所获得的所有其他实施例 ， 都属于本发明保护的范围。

在基于一致性 hash算法的分布式緩存系统中， 所有的緩存节点均根据其 分别对应的哈希值而分布于一个虚拟圆结构上 （以下简称 "圆"；)， 该 "圆" 一般由緩存管理装置生成并保存。 所述緩存管理装置可以是一个緩存管理节 点。

在所述 "圆"上的一段数据范围（如 "圆"上 1000〜20000的 hash值范围） 将称为一个 "hash段"。

在所述分布式緩存系统中， 緩存客户端一般会从緩存管理装置中下载 "圆" 上所有緩存节点的信息， 以供緩存客户端进行一致性 hash运算。

一般情况下， 都是以数据的键到保存该数据的緩存节点的方 向作为 "圆" 的正方向； 其体现在 "圆" 上可以是顺时针， 也可以是逆时针。 在本发明的 实施例中， 将顺时针方向定义为正方向来作为示例； 也就是说， "圆" 上的数 据会按照顺时钟方向来选择緩存节点， 而緩存客户端在读取数据时也会根据 所述数据的键对应的 hash值在 "圆" 的顺时针方向上寻找最近的緩存节点进 行操作。

结合图 1所示， 通过一致性 hash算法来实现分布式緩存的基本原理大致 如下：

首先， 将多个緩存节点配置到 0 ~ 2 ³² 的 "圆" （continuum, 这里的 "圆" 是由负载均衡设备生成的虚拟圆， 其实质上是一种闭联集）上； 在这里， 2 ³² 只是一个示例， "圆" 的大小当然还可以是其它值， 而将所述緩存节点配置到 "圆" 上的方法可以是将多个緩存节点平均排布在所 述 "圆" 上， 当然也可 以是参照适合某些具体场景的其它规则来进行 配置；

然后，求出需存储数据对应的键的哈希值 ,例如通过 md5 ( Message-Digest Algorithm 5 , 信息-摘要算法 5 )算法， 并将计算得到的哈希值对 2 ³² 取余； 根 据取余的结果将所述需存储的数据映射到所述 "圆" 上；

之后， 从所述需存储的数据对应的键映射到 "圆" 上的位置开始顺时针 查找， 并将所述需存储的数据保存到查找到的第一个 緩存节点（服务器）上。

在分布式緩存系统中存在有多个緩存节点， 而不同的緩存节点所承担的 负载大小也各有不同。 一般情况下， 以一个緩存节点的多项负载数据中的最 大值作为该緩存节点的负载值， 例如某一緩存节点当前的内存使用率为 50%, 带宽使用率为 80%, 其它的负载数据也均小于 80%, 则该緩存节点的负载值 即为 80%。 如果最高负载节点和最低负载节点之间的负载 差距超过阔值（例 如 15% )， 或者所有緩存节点的整体负载高于上限值 (例如 80% )或整体负载 低于下限值（例如 40% ), 那么就认为当前分布式緩存系统中存在緩存负 载异 常。

下面结合附图对本发明实施例提供的分布式緩 存资源调度的方法、 装置 及系统进行详细描述。

实施例一：

如图 2所示， 本实施例提供的分布式緩存资源调度的方法， 包括以下步 骤：

201、 对分布式緩存系统中的各緩存节点的负载值进 行监控； 这里的负载 值可以包含但不限于各个緩存节点的内存占用 率、 带宽占用率等。

202、 根据所述负载值判断当前分布式緩存系统中是 否存在负载异常； 所 述负载异常包括负载不均、 负载过高或者负载过低。

一般情况下， 如果当前分布式緩存系统中， 所有緩存节点的负载值中的 最大值和最小值之差超过一阔值（比如， 15% )时， 就认为当前分布式緩存系 统中存在负载不均；

如果所有緩存节点的整体负载高于上限值（例 如 80% )或者所有节点的 负载值中的最小值高于某一预设值 (比如 60% )， 那么就认为当前分布式緩存 系统中存在负载过高的问题， 也就是系统过载；

而如果所有緩存节点的整体负载低于下限值（ 例如 40% )， 则认为当前分 布式緩存系统中存在负载过低的问题；

在本实施例中， 所谓整体负载是由所有緩存节点的负载值的平 均值来表 示， 当然也可以是通过其它方式来表示。

203、 若当前分布式緩存系统中存在负载异常， 则对所述分布式緩存系统 中的緩存节点的布局进行调整。

在本实施例中， 针对上述三种负载异常的情况， 对緩存节点的布局进行 调整的方式分别为：

1 )针对负载不均的情况， 可以通过移动所述 "圆" 上的緩存节点的位置 的方式来改变緩存节点的覆盖范围， 从而改变緩存节点上的负载值大小； 2 )针对负载过高的情况， 可以在所述 "圆" 中添加新的緩存节点， 通过 新增的緩存节点来分担邻近的緩存节点上的负 载；

3 )针对负载过低的情况， 可以从所述 "圆" 中移除一个或者多个緩存节 点， 使所述移除的緩存节点上的负载转移到邻近的 緩存节点上， 从而提高分 布式緩存系统的整体负载。

上述步骤的执行主体可以是緩存管理装置， 即分布式緩存系统中的緩存 管理节点。

为了更好地实现上述方法， 本实施例中还提供了一种緩存管理装置， 如 图 3 所示， 该緩存管理装置所在的分布式緩存系统中各緩 存节点分布在一个 基于一致性哈希算法的虚拟圆上， 所述緩存管理装置包括：

监控单元 31，用于对分布式緩存系统中的各緩存节点的� ��载值进行监控； 判断单元 32, 用于根据所述负载值判断当前分布式緩存系统 中是否存在 负载异常；

调整单元 33 , 用于在当前分布式緩存系统中存在负载异常时 ， 对所述分 布式緩存系统中的緩存节点的布局进行调整。

上述緩存管理装置， 可以是分布式緩存系统中的緩存管理节点。

本发明实施例中提供的分布式緩存资源调度的 方法及装置， 通过对当前 分布式緩存系统中各緩存节点的负载值进行监 控 , 并在当前分布式緩存系统 中存在负载异常时， 自动调整緩存节点之间的布局来改变不同緩存 节点所承 担的负载量， 实现分布式緩存系统中资源分布的自动化调度 ， 使所述分布式 緩存系统的资源分布处于一种平衡状态。

实施例二：

如图 4所示， 本实施例提供的分布式緩存资源调度的方法， 包括以下步 骤：

401、 接收緩存管理装置发送的通知消息， 该消息中包含有分布式緩存系 统的虚拟圆上即将丢失数据的哈希段对应的旧 緩存节点的位置信息。 其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

402、 在当前緩存节点上不存在緩存客户端要读取的 数据时， 根据所述位 置信息访问所述旧緩存节点以获取并保存所述 数据。

上述各步骤的执行主体可以是分布式緩存系统 中的緩存节点， 且该緩存 节点是所述即将丢失数据的哈希段所对应的新 緩存节点。

为了更好地实现上述分布式緩存资源调度的方 法， 本实施例中还提供了 一种緩存节点， 如图 5所示， 该緩存节点包括：

接收单元 51 , 用于接收緩存管理装置发送的通知消息， 该消息中包含有 分布式緩存系统的虚拟圆上即将丢失数据的哈 希段对应的 1曰緩存节点的位置 信息；

获取单元 52，用于在当前緩存节点上不存在緩存客户端� ��读取的数据时， 根据所述位置信息访问所述旧緩存节点以获取 并保存所述数据；

其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

本实施例中提供的分布式緩存资源调度的方法 及緩存节点， 通过将所述 即将丢失数据的哈希段对应的旧緩存节点的位 置信息告知其对应的新緩存节 点， 使得所述新緩存节点在发现自身不具备緩存客 户端需要的数据时， 可以 根据所述位置信息访问所述旧緩存节点以获取 相应的数据， 从而减少了数据 的丢失。

实施例三：

在本实施例中， 将以一具体实例来进一步说明通过移动緩存节 点在所述 "圆" 上的位置， 来实现分布式緩存系统中资源调度的方法。

首先， 判断当前分布式緩存系统中是否存在负载不均 ， 具体的判断方式 在前面已有描述， 此处不再赞述； 如果当前分布式緩存系统中存在负载不均， 则可以通过移动緩存节点在所述 "圆" 上的位置的方式来对分布式緩存系统 中的緩存节点的布局进行调整。

具体地， 移动緩存节点在所述 "圆" 上的位置的过程， 如图 6所示， 包 括：

601、 选取所述 "圆" 上负载差距最大的至少一对相邻緩存节点。

在选取 "圆" 上负载差距最大的相邻緩存节点时， 可以是选取其中负载 差距最大的一对， 这种方式比较适合緩存节点较少的分布式緩存 系统； 也可 以是按照负载差距值从大到小的顺序选取多对 緩存节点， 这种方式比较适合 緩存节点较多的分布式緩存系统； 当然还可以是其它选择方式。

602、 对所选出的每对相邻緩存节点中的两个緩存节 点的负载值进行比 较。

以其中一对相邻緩存节点为例， 如果位于正方向 （顺时针） 的緩存节点 的负载值较大， 则执行步骤 603; 如果位于反方向（逆时针）的緩存节点的负 载值较大， 则执行步骤 604。

603、 将位于反方向的緩存节点沿正方向移动。

参看图 7所示的分布式緩存系统中的 "圆" 结构， 其中负载值最大的緩 存节点是节点 5 ( 98% ), 负载值最小的緩存节点是节点 2 ( 20% ), 它们之间 的负载差为 78%, 高于阔值（比如 15% ), 因此当前的分布式緩存系统中存在 负载不均， 而且此时负载差距最大的一对相邻緩存节点是 节点 3和节点 4。 由 于节点 4上的负载值比节点 3上的负载值要大， 因此为了使节点 3和节点 4 上的负载趋向于均衡化， 需要将节点 3沿顺时针方向移动。

如果当前节点 4上的负载值为 a, 其所覆盖的 hash段的长度为 A; 节点 3 上的负载值为 b, 其所覆盖的 hash段的长度为 B, 且节点 3的负载能力是节 点 4的 X倍（负载能力与节点的硬件条件有关， 一般 X > 0; 如果节点 3和节 点 4选用的是相同硬件或者虚拟硬件， 则 X为 1 ); 则， 节点 3在 "圆" 上沿 顺时针方向移动的距离为： 1 + X a

这样， 节点 3在 "圆" 上的覆盖范围变大， 所承担的负载也变大； 同时， 节点 4所承担的负载则变小， 从而使节点 3和节点 4之间的负载趋向均衡。

504、 将位于反方向的緩存节点沿反方向移动。

参看图 8所示的分布式緩存系统中的 "圆" 结构， 此时负载差距最大的 一对相邻緩存节点是节点 1和节点 2。由于节点 1上的负载值比节点 2上的负 载值要大， 因此为了使节点 1和节点 2上的负载趋向于均衡化， 需要将节点 1 沿逆时针方向移动。

如果当前节点 1上的负载值为 c, 其所覆盖的 hash段的长度为 C; 节点 2 上的负载值为 d, 其所覆盖的 hash段的长度为 D, 且节点 2的负载能力是节 点 1的 X倍（负载能力与节点的硬件条件有关， 一般 X > 0; 如果节点 1和节 点 2选用的是相同硬件或者虚拟硬件， 则 X为 1 ); 则， 节点 1在 "圆" 上沿 顺时针方向移动的距离为：

1 + X c

这样， 节点 1在 "圆" 上的覆盖范围变小， 所承担的负载也变小； 同时， 节点 2所承担的负载则变大， 从而使节点 1和节点 2之间的负载趋向均衡。

上面的描述， 只是以其中一对相邻的緩存节点作为示例来介 绍本实施例 所提供的分布式緩存负载均衡的方法。 如果在对所述一对相邻緩存节点的布 局进行调整后， 当前分布式緩存系统中仍然存在负载不均的问 题， 那么就重 复上述操作， 直至分布式緩存系统中各緩存节点的负载值中 的最大值和最小 值之差低于阔值。

通过上述方法， 对 "圆" 上的緩存节点的布局进行调整， 可以使整个分 布式緩存系统中的总负载在各个緩存节点上重 新分配， 从而达到负载均衡的 目的。 不过， 在所述分布式緩存系统中， 只要存在緩存节点位置的变动， 就会 出现所述 "圆" 中的一段 hash段的数据会在访问时丢失的情况。

针对这一问题， 在本实施例中， 由緩存管理装置向即将丢失数据的 hash 段对应的新緩存节点发送一通知消息， 该通知消息中包含有所述即将丢失数 据的 hash段对应的旧緩存节点的位置信息。 所述位置信息中包含有旧緩存节 点的 IP ( Internet Protocol, 因特网协议）地址和端口号， 当然还可以包含其它 一些用于表征位置的信息。

结合图 Ί的情况， 节点 3沿 "圆" 的顺时针方向移动至节点 3'的位置。 对于节点 3和节点 3'之间的 hash段 M, 其原属于节点 4的覆盖范围； 在节点 3移动后， 所述 hash段 M归属到节点 3'的覆盖范围。 此时， 緩存客户端在请 求获取 hash段 M上的数据时， 会向节点 3'发起该读操作请求， 而实际上 hash 段 M上的数据仍然保存在节点 4中而非节点 3'中 , 因此就会造成 hash段 M 上的数据丢失。

在本实施例中， 在移动了节点 3 的位置之后， 分布式緩存系统中的緩存 管理装置就会向节点 3'发送一通知消息， 该通知消息中包含有节点 4的位置 信息（一般指 IP地址和端口号）。 这样， 在緩存客户端向节点 3'请求获取 hash 段 M上的数据时， 如果在节点 3'中没有相应的数据， 那么节点 3'会根据所述 位置信息去访问节点 4以获 目应的数据 (例如通过图 Ί中所示的 T1接口）， 并将获取到的数据保存在节点 3'中， 同时将所述数据返回给发起读操作请求 的緩存客户端。

在上述通知消息中， 还可以携带有超时时间 timeout的信息； 这样， 就可 以将节点 3'访问节点 4以获取数据的操作限定在 timeout之内。 如果上述获取 数据的操作在超出所述 timeout后仍未完成， 节点 3'也会停止继续访问节点 4 来获取数据的过程。

更进一步地， 还可以在上述通知消息中添加 hash段 M的范围 （例如： 10001-20200 );这样，在緩存客户端向节点 3'请求获取数据而在节点 3'中并没 有相应数据的时候， 节点 3'会对所述数据的键进行一致性哈希运算（这� ��进 行一致性哈希运算的算法同緩存客户端中保存 的一致性哈希算法是一样的 )， 并将运算得到的哈希值跟所述通知消息中携带 的 hash段 M的范围进行比对， 判断所述由节点 3'计算得到哈希值是否属于 hash段 M的范围； 如果属于， 节 点 3'才可以访问节点 4以获取相应的数据。 通过在通知消息中添加 hash段 M 的范围信息， 可以更加明确节点 3'需要从节点 4 中获取的数据是即将丢失数 据的 hash段 M所对应的数据， 而非其它 hash段的数据， 这样可以减少信令 消耗、 节省资源。

上面的描述中仅以緩存客户端向节点 3'发起读操作请求为例， 如果所述 节点 3'接收到的是计数请求， 而本节点中又没有相应的计数值时， 同样可以 通过访问节点 4来获取以往记录的计数值； 该处理过程同上述处理读操作请 求的过程基本原理一致， 此处不再赘述。

结合图 8的情况， 节点 1沿 "圆" 的逆时针方向移动至节点 1'的位置。 对于节点 1和节点 Γ之间的 hash段 N, 其原属于节点 1的覆盖范围； 在节点 1移动后， 所述 hash段 N归属到节点 2的覆盖范围。 此时， 緩存客户端在请 求获取 hash段 N上的数据时， 会向节点 2发起该读操作请求， 而 hash段 N 上的数据实际保存在节点 Γ (也就是移动后的节点 1 )中而非节点 2中， 因此 就会造成 hash段 N上的数据丢失。

在本实施例中， 在移动了节点 1 的位置之后， 分布式緩存系统中的緩存 管理装置就会向节点 2发送一通知消息， 该通知消息中包含有节点 Γ的位置 信息（一般指 IP地址和端口号）。这样，在緩存客户端向节� �� 2请求获取 hash 段 N上的数据时， 如果在节点 2中没有相应的数据， 那么节点 2会根据所述 位置信息去访问节点 Γ以获 目应的数据 (例如通过图 8中所示的 T1接口）， 并将获取到的数据保存在节点 2 中， 同时将所述数据返回给发起读操作请求 的緩存客户端。

在上述通知消息中， 还可以携带有超时时间 timeout的信息； 这样， 就可 以将节点 2访问节点 Γ以获取数据的操作限定在 timeout之内。 如果上述获取 数据的操作在超出所述 timeout后仍未完成， 节点 2也会停止继续访问节点 1' 来获取数据的过程。

更进一步地， 还可以在上述通知消息中添加 hash段 N的范围 （例如： 10001-20200 ); 这样， 在緩存客户端向节点 2请求获取数据而在节点 2中并 没有相应数据的时候， 节点 2会对所述数据的键进行一致性哈希运算（这� � 进行一致性哈希运算的算法同緩存客户端中保 存的一致性哈希算法是一样 的） , 并将运算得到的哈希值跟所述通知消息中携带 的 hash段 N的范围进行 比对， 判断所述由节点 2计算得到哈希值是否属于 hash段 N的范围； 如果属 于，节点 2才可以访问节点 Γ以获取相应的数据。通过在通知消息中添加 hash 段 N的范围信息， 可以更加明确节点 3'需要从节点 4中获取的数据是即将丢 失数据的 hash段 N所对应的数据， 而非其它 hash段的数据，这样可以减少信 令消耗、 节省资源。

上面的描述中仅以緩存客户端向节点 2发起读操作请求为例， 如果所述 节点 2接收到的是计数请求， 而本节点中又没有相应的计数值时， 同样可以 通过访问节点 1'来获取以往记录的计数值； 该处理过程同上述处理读操作请 求的过程基本原理一致， 此处不再赘述。

本实施例提供的分布式緩存资源调度的方法， 在当前分布式緩存系统中 存在负载不均时， 通过移动緩存节点在分布式緩存系统的虚拟圆 结构上的位 置来改变不同緩存节点所承担的负载量 , 使得不同緩存节点之间的负载值差 异逐渐变小， 进而使所述分布式緩存系统达到负载均衡的状 态；

而且， 在本实施例中还提供了一种减少緩存数据丢失 的方案， 通过将某 一段即将丢失数据的 hash段对应的旧緩存节点的位置信息告知该 hash段对应 的新緩存节点， 使得所述新緩存节点能够根据所述位置信息访 问旧緩存节点 以获取相应的数据， 进而减少数据丢失的情况。

实施例四： 在本实施例中， 将以一具体实例来进一步说明通过在分布式緩 存系统中 添加緩存节点， 来实现分布式緩存系统中资源调度的方法。

首先， 判断当前分布式緩存系统中是否存在负载过高 ， 具体的判断方式 在前面已有描述， 此处不再赞述； 如果当前分布式緩存系统中存在负载过高， 则可以通过在所述 "圆" 上增加緩存节点的方式来对分布式緩存系统中 的緩 存节点的布局进行调整。

具体地， 在所述 "圆" 上增加緩存节点的过程， 如图 9所示， 包括：

901、 选取所述 "圆" 上负载值最高的緩存节点， 例如图 10中的节点 5。

902、在所述负载值最高的緩存节点所对应的 hash段的中间位置增设一緩 存节点。

参看图 10所示的分布式緩存系统中的 "圆" 结构， 负载值最高的緩存节 点是节点 5 , 而节点 5所覆盖的 hash段即为位于节点 5的逆时针方向上的节 点 4和节点 5之间的 hash段。 此时， 在节点 5所覆盖的 hash段的中间位置增 设一节点 5'； 由于该节点 5'位于节点 5的顺时针方向而且正位于所述 hash段 的中间位置， 因此节点 5'将 hash段均分为 P1和 P2两段， 使得 hash段 P1仍 然归属于节点 5 , 而 hash段 P2则归属到节点 5', 从而降低节点 5上的负载， 同时也降低了当前分布式緩存系统中所有节点 的平均负载。

如果在所述 "圆" 上增加了一个节点之后， 当前分布式緩存系统中仍然 存在负载过高的问题， 那么可以重复上述操作， 直至分布式緩存系统中的整 体负载低于上限值。

通过上述方法， 在 "圆" 上增设新的緩存节点， 可以对原来负载值较高 的緩存节点上的负载进行分流， 进而降低分布式緩存系统的整体负载， 解决 系统过载的问题。

在本实施例中， 需要注意的是， 在增加緩存节点前， 首先要确保已有足 够数量的緩存节点服务器是处于启动状态 （可以是正在运行中或者待机中 )， 这样才能顺利地将新的緩存节点加入到所述虚 拟圆结构中， 以分担其它緩存 节点上的负载。

然而， 在所述分布式緩存系统中， 只要存在緩存节点布局上的变动， 就 会出现所述 "圆" 中的一段 hash段的数据会在访问时丢失的情况。

针对这一问题， 在本实施例中， 由緩存管理装置向即将丢失数据的 hash 段对应的新緩存节点发送一通知消息， 该通知消息中包含有所述即将丢失数 据的 hash段对应的旧緩存节点的位置信息。 所述位置信息中包含有旧緩存节 点的 IP地址和端口号， 当然还可以包含其它一些用于表征位置的信息 。

结合图 10的情况，在节点 4和节点 5之间的 hash段的中间位置增设节点 5'。 对于节点 4和节点 5'之间的 hash段 P2, 其原属于节点 5的覆盖范围； 在 增设了节点 5'之后， 所述 hash段 P2归属到节点 5'的覆盖范围。 此时， 緩存客 户端在请求获取 hash段 P2上的数据时，会向节点 5'发起该读操作请求， 而实 际上 hash段 P2上的数据仍然保存在节点 5中而非节点 5'中 , 因此就会造成 hash段 P2上的数据丢失。

在本实施例中， 在增加了节点 5'之后， 分布式緩存系统中的緩存管理装 置就会向节点 5'发送一通知消息，该通知消息中包含有节点 5的位置信息（一 般指 IP地址和端口号）。 这样， 在緩存客户端向节点 5'请求获取 hash段 P2上 的数据时，如果在节点 5'中没有相应的数据，那么节点 5'会根据所述位置信息 去访问节点 5 以获取相应的数据， 并将获取到的数据保存在节点 5'中， 同时 将所述数据返回给发起读操作请求的緩存客户 端。

在上述通知消息中， 还可以携带有超时时间 timeout的信息； 这样， 就可 以将节点 5'访问节点 5以获取数据的操作限定在 timeout之内。 如果上述获取 数据的操作在超出所述 timeout后仍未完成， 节点 5'也会停止继续访问节点 5 来获取数据的过程。

更进一步地， 还可以在上述通知消息中添加 hash段 P2的范围； 这样， 在 緩存客户端向节点 5'请求获取数据而在节点 5'中并没有相应数据的时候，节点 5'会对所述数据的键进行一致性哈希运算，并� ��运算得到的哈希值跟所述通知 消息中携带的 hash段 P2的范围进行比对，判断所述由节点 5'计算得到哈希值 是否属于 hash段 P2的范围； 如果属于， 节点 5'才可以访问节点 5以获取相应 的数据。 通过在通知消息中添加 hash段 P2的范围信息， 可以更加明确节点 5'需要从节点 5中获取的数据是即将丢失数据的 hash段 P2所对应的数据， 而 非其它 hash段的数据， 这样可以减少信令消耗、 节省资源。

上面的描述中仅以緩存客户端向节点 5'发起读操作请求为例， 如果所述 节点 5'接收到的是计数请求， 而本节点中又没有相应的计数值时， 同样可以 通过访问节点 5来获取以往记录的计数值； 该处理过程同上述处理读操作请 求的过程基本原理一致， 此处不再赘述。

本实施例提供的分布式緩存资源调度的方法， 在当前分布式緩存系统中 存在负载过高时， 通过增加新的緩存节点来改变不同緩存节点所 承担的负载 量， 并降低所有緩存节点的平均负载， 也就是降低分布式緩存系统的整体负 载， 使所述分布式系统处于一种平衡的状态；

而且， 在本实施例中还提供了一种减少緩存数据丢失 的方案， 通过将某 一段即将丢失数据的 hash段对应的旧緩存节点的位置信息告知该 hash段对应 的新緩存节点， 使得所述新緩存节点能够根据所述位置信息访 问旧緩存节点 以获取相应的数据， 进而减少数据丢失的情况。

实施例五：

在本实施例中， 将以一具体实例来进一步说明通过从分布式緩 存系统中 移除緩存节点， 来实现分布式緩存系统中资源调度的方法。

首先， 判断当前分布式緩存系统中是否存在负载过低 ， 具体的判断方式 在前面已有描述， 此处不再赞述； 如果当前分布式緩存系统中存在负载过低， 则可以通过从所述 "圆" 上移除緩存节点的方式来对分布式緩存系统中 的緩 存节点的布局进行调整。

具体地， 在所述 "圆" 上增加緩存节点的过程， 如图 11所示， 包括：

1101、 选取所述 "圆" 上总负载值最低的一对相邻緩存节点， 例如图 12 中的节点 2和节点 3。

1102、 将所述总负载值最低的一对相邻緩存节点中位 于反方向上的负载 节点从所述分布式緩存系统中移除。 在经过一定时长之后， 被移除的緩存节 点就会被置为关机、 待机或者待命等状态。

参看图 12所示的分布式緩存系统中的 "圆" 结构， 总负载值最低的一对 相邻緩存节点是节点 2和节点 3 , 且节点 2位于节点 3的逆时针方向上。在移 除了节点 2之后， 原本属于节点 2的覆盖范围内的 hash段 Q全部归属到了节 点 3 的覆盖范围。 这样， 由于緩存节点数量的减少， 当前分布式緩存系统中 所有节点的平均负载升高， 也就是当前分布式緩存系统的整体负载升高， 使 得当前系统维持在一定的平衡状态。

如果在从所述 "圆" 上移除了一个节点之后， 当前分布式緩存系统中仍 然存在负载过低的问题， 那么可以重复上述操作， 直至分布式緩存系统中的 整体负载高于下限值。

不过， 在所述分布式緩存系统中， 只要存在緩存节点布局上的变动， 就 会出现所述 "圆" 中的一段 hash段的数据会在访问时丢失的情况。

针对这一问题， 在本实施例中， 由緩存管理装置向即将丢失数据的 hash 段对应的新緩存节点发送一通知消息， 该通知消息中包含有所述即将丢失数 据的 hash段对应的旧緩存节点的位置信息。 所述位置信息中包含有旧緩存节 点的 IP地址和端口号， 当然还可以包含其它一些用于表征位置的信息 。

结合图 12的情况， 在移除了节点 2之后， 原本属于节点 2的覆盖范围内 的 hash段 Q全部归属到了节点 3的覆盖范围。 此时， 緩存客户端在请求获取 hash段 Q上的数据时，会向节点 3发起该读操作请求， 而实际上 hash段 Q上 的数据仍然保存在节点 2中而非节点 3中 , 因此就会造成 hash段 Q上的数据 丢失。

在本实施例中， 在移除了节点 2之后， 分布式緩存系统中的緩存管理装 置就会向节点 3发送一通知消息，该通知消息中包含有节点 2的位置信息（一 般指 IP地址和端口号）。 这样 , 在緩存客户端向节点 3请求获取 hash段 Q上 的数据时， 如果在节点 3中没有相应的数据， 那么节点 3会根据所述位置信 息去访问节点 2以获 目应的数据（虽然节点 2从所述 "圆" 中移除， 但还 是可以根据位置信息对其进行寻址的）， 并将获取到的数据保存在节点 3中， 同时将所述数据返回给发起读操作请求的緩存 客户端。

在上述通知消息中， 还可以携带有超时时间 timeout的信息； 这样， 就可 以将节点 3访问节点 2以获取数据的操作限定在 timeout之内。 如果上述获取 数据的操作在超出所述 timeout后仍未完成， 节点 3也会停止继续访问节点 2 来获取数据的过程。

更进一步地， 还可以在上述通知消息中添加 hash段 Q的范围； 这样， 在 緩存客户端向节点 3请求获取数据而在节点 3 中并没有相应数据的时候， 节 点 3会对所述数据的键进行一致性哈希运算， 并将运算得到的哈希值跟所述 通知消息中携带的 hash段 Q的范围进行比对， 判断所述由节点 3计算得到哈 希值是否属于 hash段 Q的范围； 如果属于， 节点 3才可以访问节点 2以获取 相应的数据。 通过在通知消息中添加 hash段 Q的范围信息， 可以更加明确节 点 3需要从节点 2中获取的数据是即将丢失数据的 hash段 Q所对应的数据， 而非其它 hash段的数据， 这样可以减少信令消耗、 节省资源。

上面的描述中仅以緩存客户端向节点 3发起读操作请求为例， 如果所述 节点 3接收到的是计数请求， 而本节点中又没有相应的计数值时， 同样可以 通过访问节点 2来获取以往记录的计数值； 该处理过程同上述处理读操作请 求的过程基本原理一致， 此处不再赘述。

本实施例提供的分布式緩存资源调度的方法， 在当前分布式緩存系统中 存在负载过低时， 通过移除某一緩存节点来改变不同緩存节点所 承担的负载 量， 并提高所有緩存节点的平均负载， 也就是提高分布式緩存系统的整体负 载， 使所述分布式系统处于一种平衡的状态；

而且， 在本实施例中还提供了一种减少緩存数据丢失 的方案， 通过将某 一段即将丢失数据的 hash段对应的旧緩存节点的位置信息告知该 hash段对应 的新緩存节点， 使得所述新緩存节点能够根据所述位置信息访 问旧緩存节点 以获取相应的数据， 进而减少数据丢失的情况。

在对实际的分布式緩存系统进行负载均衡操作 时， 上述实施例三、 实施 例四和实施例五中提供的方案都不是孤立的， 可以优选地采用其中一种方案， 也可以是采用其中两种或者三种的结合 , 这样可以达到更好的效果。

此外， 在上述实施例三、 实施例四和实施例五中， 如果涉及到写操作请 求的话， 那么所述緩存管理装置在将即将丢失数据的 hash段对应的旧緩存节 点的位置信息告知新緩存节点的同时， 也需要将所述新緩存节点的位置信息 告知旧緩存节点。

这样， 在緩存客户端向所述新緩存节点发起写操作请 求时， 所述新緩存 节点会接收并保存所述緩存客户端要求写入的 数据； 然后判断所接收的数据 是否属于所述即将丢失数据的 hash段； 如果数据， 则所述新緩存节点会根据 所述旧緩存节点的位置信息将所述数据再转发 给所述旧緩存节点以进行同 步。 同样的， 所述旧緩存节点在接收到属于所述即将丢失数 据的 hash段的数 据时， 也会根据所述新緩存节点的位置信息将数据转 发给所述新緩存节点以 进行同步， 从而实现同一段 hash段对应的新、 旧緩存节点之间的写同步。

当然， 上述写同步的过程也可以是限定在超时时间 timeout内进行； 如果 超过了 timeout, 对数据进行写同步的操作仍未完成， 所述新緩存节点也会停 止数据同步的过程。

通过对同一 hash段对应的新、 旧緩存节点进行写同步， 可以避免緩存节 点位置变更后， 对同一个 "键" 的读写不在同一个緩存节点的问题。

在上述实施例中， 均是以 "圆" 的顺时针作为正方向来对本发明实施例 中提供的方案加以阐述的。 不过， 需要说明的是， 以顺时针作为 "圆" 的正 方向只是本发明实施例中的一个示例； 如果以逆时针方向作为所述 "圆" 的 正方向的话， 即按照逆时针方向来选择保存数据的緩存节点 ， 其进行负载均 衡的过程同上述以顺时针方向作为正方向时的 方案的基本原理一致 , 因此， 同样属于本发明的保护范围之内。

实施例六：

对应于上述方法的实施例， 一方面， 在本实施例中提供了一种用于分布 式緩存资源调度的緩存管理装置， 如图 13所示， 包括判断单元 131、 调整单 元 132以及监控单元 133; 其中，

监控单元 133 ,用于对所述分布式緩存系统中的各緩存节点� �负载值进行 监控；

判断单元 131 ,用于根据所述负载值判断当前分布式緩存系� �中是否存在 负载异常； 所述负载异常包括负载不均、 负载过高或者负载过低；

调整单元 132, 用于在当前分布式緩存系统中存在负载异常时 ， 对所述分 布式緩存系统中的緩存节点的布局进行调整。

同前述的方法实施例中一样 , 在本实施例的分布式緩存系统中各緩存节 点分布在一个基于一致性哈希算法的 "圆" 上， 并以数据的键到保存所述数 据的緩存节点的方向作为所述虚拟圆的正方向 ； 则， 所述调整单元 132包括： 移动模块 1321 , 用于移动緩存节点在所述虚拟圆上的位置； 和 /或， 增加模块 1322, 用于在所述虚拟圆上增加緩存节点； 和 /或，

移除模块 1323 , 用于从所述虚拟圆中移除緩存节点。

具体地， 如图 14所示， 所述移动模块 1321可以包括：

第一选取子模块 141 ,用于选取所述虚拟圆上负载差距最大的至少� �对相 邻緩存节点；

比较子模块 142,用于对所选出的每对相邻緩存节点中的两� �緩存节点的 负载值进行比较；

移动子模块 143 ,用于在所选出的每对相邻緩存节点中位于正� �向的緩存 节点的负载值较大时， 将位于反方向的緩存节点沿正方向移动； 在位于反方 向的緩存节点的负载值较大时 , 将该緩存节点沿反方向移动。 如图 15所示， 所述增加模块 1322可以包括：

第二选取子模块 151， 用于选取所述虚拟圆上负载值最高的緩存节点 ； 增设子模块 152,用于在所述负载值最高的緩存节点所对应� �哈希段的中 间位置增设一緩存节点。

如图 16所示， 所述移除模块 1323可以包括：

第三选取子模块 161 ,用于选取所述虚拟圆中总负载值最低的一对� �邻緩 存节点；

移除子模块 162,用于将所述总负载值最低的一对相邻緩存� �点中位于反 方向上的负载节点从所述分布式緩存系统中移 除。

另一方面， 本实施例中还提供了一种緩存节点， 如图 17所示， 该緩存节 点包括：

接收单元 171 , 用于接收緩存管理装置发送的通知消息， 该消息中包含有 分布式緩存系统的虚拟圆上即将丢失数据的哈 希段对应的 1曰緩存节点的位置 信息；

获取单元 172， 用于在当前緩存节点上不存在緩存客户端要读 取的数据 时， 根据所述位置信息访问所述旧緩存节点以获取 并保存所述数据；

其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

进一步地， 所述接收单元 171接收到的通知消息中还包括： 所述即将丢 失数据的哈希段的范围； 那么， 所述获取单元 172， 可以包括：

判断模块 1721 , 用于在当前緩存节点上不存在緩存客户端要读 取的数据 时， 判断所述緩存客户端要读取的数据的键对应的 哈希值是否属于所述即将 丢失的数据的哈希段；

获取模块 1722， 用于在所述判断模块的判断结果为是时， 根据所述位置 信息访问所述旧緩存节点以获取并保存所述数 据。

如果当前分布式緩存系统还涉及到写操作的话 , 那么本实施例中的緩存 节点中还可以包括：

保存单元 173，用于接收并保存所述緩存客户端或者所述 旧緩存节点要求 写入的数据；

判断单元 174,用于判断所述緩存客户端要求写入的数据� �键对应的哈希 值是否属于所述即将丢失的数据的哈希段；

同步单元 175 , 用于在所述判断单元的判断结果为是时， 将所述緩存客户 端要求写入的数据同步写入到所述旧緩存节点 上。

此外， 如果所述接收单元 171接收到的通知消息中还包括超时时间； 那 么， 本实施例中的緩存节点还包括：

停止单元 176, 用于在超出所述超时时间后， 停止数据获取或者数据同步 的操作。

此外， 本实施例中还提供了一种分布式緩存系统， 如图 18所示， 该分布 式緩存系统包括：緩存管理装置 181、緩存客户端 182以及多个緩存节点 183 , 在该分布式緩存系统中所述多个緩存节点 183分布在一个基于一致性哈希算 法的虚拟圆上； 其中，

所述緩存客户端 182，用于根据一致性哈希算法将数据分布到所 述多个緩 存节点 183上;

所述緩存管理装置 181，用于对分布式緩存系统中的各緩存节点 183的负 载值进行监控， 并根据所述负载值判断当前分布式緩存系统中 是否存在负载 异常； 若存在异常， 则对所述多个緩存节点 183 的布局进行调整； 其中， 所 述负载异常包括负载不均、 负载过高或者负载过低。

进一步地， 所述緩存管理装置 181 , 还用于在完成緩存节点 183的布局调 整后， 向分布式緩存系统的虚拟圆上即将丢失数据的 哈希段对应的新緩存节 点发送一通知消息， 该通知消息中包含有分布式緩存系统的虚拟圆 上即将丢 失数据的哈希段对应的旧緩存节点的位置信息 ； 这样， 所述新緩存节点在当 前緩存节点上不存在緩存客户端要读取的数据 时， 就能够根据所述位置信息 访问所述旧緩存节点以获取并保存所述数据；

其中， 所述即将丢失数据的哈希段是所述分布式緩存 系统的虚拟圆上出 现緩存节点布局的调整后， 所归属的緩存节点有改变的哈希段。

本实施例中提供的分布式緩存资源调度的装置 及系统， 在当前分布式緩 存系统中存在负载异常时， 通过移动緩存节点在分布式緩存系统的虚拟圆 结 构上的位置、 或者在所述虚拟圆结构上添加或移除緩存节点 来改变不同緩存 节点所承担的负载量， 实现分布式緩存系统中资源分布的自动化调度 ， 使所 述分布式緩存系统的资源分布处于一种平衡状 态； 而且， 在本实施例所提供 的方案中， 通过将某一段即将丢失数据的哈希段对应的旧 緩存节点的位置信 息告知该哈希段对应的新緩存节点， 使得所述新緩存节点能够根据所述位置 信息访问旧緩存节点以获取相应的数据， 进而减少数据丢失的情况。

通过以上实施方式的描述， 本领域的技术人员可以清楚地了解到本发明 可借助软件加必需的硬件平台的方式来实现， 当然也可以全部通过硬件来实 施。 基于这样的理解， 本发明的技术方案对背景技术做出贡献的全部 或者部 分可以以软件产品的形式体现出来， 该计算机软件产品可以存储在存储介质 中， 如 ROM/RAM、 磁碟、 光盘等， 包括若干指令用以使得一台计算机设备 (可以是个人计算机， 服务器， 或者网络设备等）执行本发明各个实施例或 者实施例的某些部分所述的方法。

以上所述， 仅为本发明的具体实施方式， 但本发明的保护范围并不局限 于此， 任何熟悉本技术领域的技术人员在本发明揭露 的技术范围内， 可轻易 想到的变化或替换， 都应涵盖在本发明的保护范围之内。 因此， 本发明的保 护范围应以权利要求的保护范围为准。