分布式缓存协同中避免内容重复存储的方法和装置的制造方法
分布式缓存协同中避免内容重复存储的方法和装置的制造方法
【技术领域】
[0001] 本发明设及网络存储和内容分发技术领域，尤其设及一种分布式缓存协同中避免 内容重复存储的方法和装置。
【背景技术】
[0002] 目前，用户对互联网的访问已经从点对点通信为主转为内容获取为主。而传统的 TCP/IP网络仅传输内容，并不感知内容，从而造成了网络上大量的冗余流量传输。为了解决 由于内容获取而引发的内容爆炸，无论是目前的互联网还是研究界提出的未来网络，都把 缓存作为基本的手段，来满足用户对内容的具有重尾特征的异步访问。例如，互联网采用的 透明的Web化ch，P2P内容分发网络中的PP化che、CDN中的内容缓存，W及研究界提出的信 息/内容中屯、网络NDN，DONA等。无论是内容提供商还是网络运营商，都倾向于在网络内部 署泛在的缓存系统来降低网络流量、提高用户体验。
[0003] 但是，现在的内容在缓存中WU化为标识，而同样的内容在不同的内容提供商处 会采用不同的U化标识，导致缓存节点依据U化难W识别实际内容相同的对象，从而会在缓 存中重复存储，导致了缓存利用率的低下。因此，在泛在缓存缓存的前提下，亟需提出一种 分布式缓存环境下避免缓存内容重复存储的方法。
【发明内容】
[0004] 本发明为解决上述技术问题，提供一种分布式缓存协同中避免内容重复存储的方 法和装置，能有效地避免内容的重复存储、降低网络流量、提高用户体验。所述技术方案如 下：
[0005] 一方面，本发明提出了一种分布式缓存协同中避免内容重复存储的方法，所述方 法包括：
[0006] 采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识；
[0007] 基于二元标识建立两级逻辑映射来组织缓存内容，并W分布式哈希进行缓存协 同。其中第一级映射建立提供商依赖标识和提供商独立标识之间的映射关系，第二级映 射《建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射表项还记录了 勺逆映射关系1^1，iri(pi(id) = {PA(id)IMPA(id) =pi(id))}，即对于所给定表项 的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提供商独立标识； [000引 由网络域的边缘内容路由器将从域外到达的请求经过两级路由转发到负责存储 该内容的域内节点；
[0009] 负责内容数据块的节点将对应的数据块发送给边缘内容路由器；
[0010] 更新两级逻辑映射对应表项的缓存替换控制状态信息；
[0011] 由网络域的边缘内容路由器在收到某个内容数据块时做出是否要缓存所述内容 数据块的决定；
[0012] 当需要缓存所述内容数据块时，所述边缘内容路由器将内容数据块经过两级路由 转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的二级映射关 系。
[0013] 进一步地，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数 据块在不同的内容提供商可能具有不同的标识；
[0014] 进一步地，所述提供商独立的标识指内容的标识与提供商无关，因此同样的内容 数据块具有相同的内容标识；
[0015] 进一步地，所述的内容请求包含对所请求内容数据块的提供商依赖标识；
[0016] 进一步地，所述由网络域的边缘内容路由器R。将从域外到达的请求Q经过两级路 由转发到负责存储该内容的域内节点，包括：
[0017] 步骤201;对所述请求Q的提供商依赖标识PA<^(id)执行第一变换操作，将其变换 为分布式哈希空间中的一个可路由标识IDi;
[0018] 步骤202 ;将所述的对提供商依赖标识PA^id)执行第一变换操作后的IDi作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节 点Ni;
[0019] 步骤203 请求中的提供商依赖标识PA^id)作为键值查询该负责节点Ni的一 级映射表MTi;
[0020] 步骤204-1;若未找到对应表项，则向所述边缘内容路由器R。发送一级映射表项 不存在的消息，结束流程；
[002U步骤204-2 ;若找到对应的表项，则取得对应的提供商独立标识PI。(id)= MTi(PAQ(id));
[0022]步骤205;对所述的提供商独立标识Pl0(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇2;
[002引步骤206 ;将提供商独立标识Pl^id)作为请求的一个属性包含在请求中，同时W所述的对提供商独立标识执行第二变换操作后的1化作为分布式哈希的路由目标，由底层 的分布式哈希路由机制将请求路由到对应的负责该ID的节点馬；
[0024] 步骤207 请求中的提供商独立标识Plg(id)作为键值查询该负责节点馬的二 级映射表MT2;
[0025] 步骤208-1;若未找到对应表项，则向所述边缘内容路由器R。发送二级映射表项 不存在的消息，同时请求删除对应的一级映射表项MTi(PA<^ (id))，结束流程；
[0026] 步骤208-2;若找到对应的表项，则取得与提供商独立标识PI<^(id)关联的缓存数 据块；
[0027] 其中，所述的第一变换操作和第二变换操作可W是相同的变换操作，也可W是不 相同的变换操作；所述第二变换操作也可W是恒等变换。
[0028] 其中，所述请求删除对应的一级映射表项MTi(PAe(id))，由馬构造一级映射表项 删除消息，所述删除消息包括待删除表项的键值PA^id)。W对PA^id)执行第一变换操作 后的IDi作为路由目标，由N2依据底层的分布式哈希路由机制将所述一级映射表项删除消 息路由到所述负责该一级映射表项的节点Ni，并由Ni执行相应的删除操作；
[0029] 进一步地，所述更新两级逻辑映射对应表项的缓存替换状态控制信息，包括：更新 对应二级映射表项MT2 (Pig(id))和一级映射表项MTi(PAg(id))的缓存替换状态控制信息；
[0030] 其中，所述更新对应二级映射表项MT2(PIe(id))的缓存替换状态控制信息，由所 述节点馬本地完成更新PIg(id)键值对应的表项；
[003U 其中，所述更新对应一级映射表项MTi(PA^id))的缓存替换状态控制信息，由馬 构造缓存替换状态控制消息，所述消息包括待更新表项的键值PA0(id)和更新操作。W对PA^id)执行第一变换操作后的IDi作为路由目标，由N2依据底层的分布式哈希路由机制将 所述一级映射表项更新消息路由到所述负责该一级映射表项的节点N。并由Ni执行相应的 更新操作；
[0032] 进一步地，所述边缘内容路由器将内容数据块D经过两级路由转发到负责存储该 内容的域内节点，并建立对应的两级映射关系，包括：
[0033] 步骤301;对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其 变换为分布式哈希空间中的一个可路由标识1〇3;
[0034] 步骤302 ;将所述的对提供商依赖标识PAD(id)执行第一变换操作后的作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID 的节点N3;
[0035] 步骤303 内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点Ns 的一级映射表MTi;
[0036] 步骤304-1;若未找到对应表项，则在N3建立一级映射表项MT1(PAd(id))= PlD(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PlD(id)为内容数据块的 提供商独立标识，可W存储在内容数据块本身并随之在网络中传输，也可W由节点对内容 数据块依据某种一致的算法计算而得；
[0037] 步骤304-2;若找到对应的表项，则停止转发，结束流程；
[003引步骤305;对所述的提供商独立标识PId(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识104;
[0039] 步骤306 ;W所述的对提供商独立标识执行第二变换操作后的1〇4作为分布式哈 希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节 点N4;
[0040] 步骤307 ;W内容数据块的提供商独立标识PlD(id)作为键值查询该负责节点N4 的二级映射表MT2;
[004U步骤308-1 ;若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加 键值PlD(id)与内容数据块D的映射关系，初始化PlD(id)和提供商依赖标识的逆映射集合 为{PAd(id)}，初 始化对应表项的缓存替换状态控制信息；
[00创步骤308-2 ;若找到对应的表项，则在PId(id)和提供商依赖标识的逆映射集合中 添加PAd(id),结束流程；
[0043] 其中，所述在Ns建立一级映射表项MTi(PAD(id)) =PlD(id)时，若表项已满，则Ns 依据第一预设规则选取某个一级映射表项进行替换；
[0044] 假设被替换的一级映射表项为MTi(PAK(id)) =PlK(id)，Ns构造一级映射表项删除 消息，W对Plc(id)执行第二变换操作后得到的化作为路由目标，将所述一级映射表项删 除消息路由到负责Plc(id)二级映射的节点也NgW键值PIc(id)查询二级映射表项对应的 逆映射集合iri(PlK(id))，并执行iri(PlK(id)) =iri(PlK(id))-{PAK(id)}操作，若该操 作执行后iri(PlK(id)) = 4,即为空集，则删除二级映射表项MT2(PlK(id))及对应的内容 数据块。
[0045] 其中，所述在二级映射表项中增加键值PlD(id)与内容数据块D的映射关系，若缓 存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；
[0046] 假设被替换的二级映射表项为MT2(Pic(id))=化则N4构造二级映射表项删除通 告消息，对于似))，对PA(id)执行第一变换操作，并W对PA(id)执行第 一变换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负 责PA(id)的节点，由所述节点删除WPA(id)为键值的一级映射表项。
[0047] 其中，所述第一预设规则和第二预设规则可W采用相同的规则，也可W采用不同 的规则。
[0048] 另一方面，本发明提出一种分布式缓存协同中避免内容重复存储的内容路由器装 置，包括；分布式哈希维持模块、路由转发模块、一级映射表、二级映射表、内容块缓存库、一 级映射表替换模块、二级映射表替换模块、第一变换模块、第二变换模块。可选地，内容路由 器装置还可W包含一个提供商独立标识生成模块。
[0049] 其中，所述分布式哈希维持模块用于维持分布式哈希路由表；所述路由转发模块 用于依据消息的分布式哈希路由标识和分布式哈希路由表对消息进行路由转发；所述一级 映射表用于存储内容的提供商依赖标识和提供商独立标识的映射关系；所述二级映射表用 户存储内容的提供商独立标识和内容数据块的映射关系，同时存储所述的提供商独立标识 对应的一级映射的逆映射；所述内容块缓存库用于缓存实际的内容数据块；所述一级映射 表替换模块用于根据预设的第一替换策略选择合适的一级映射表项予W替换；所述二级映 射表替换模块用于根据预设的第二替换策略选择合适的二级映射表项予W替换，并从内容 块缓存库中删除对应的内容数据块；所述第一变换模块用于对内容的提供商依赖标识执行 变换操作，生成分布式哈希路由空间中的一个可路由标识；所述第二变换模块用于对内容 的提供商独立标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识。所述提 供商独立标识生成模块可W基于内容数据块生成仅与内容数据相关的提供商独立标识。
[0050] 本发明采用W上技术方案与现有技术相比，具有W下技术效果：
[0051] 通过在域内实现基于二级映射的分布式缓存协同，能有效地避免相同内容的重 复存储，降低网络域间流量，提升用户体验。
【附图说明】
[0052] 图1示出了依据本发明一实施方式的分布式缓存域对内容请求的处理流程； [0化3] 图2示出了依据本发明一实施方式的分布式缓存域对到达的内容数据块的处理 流程；
[0化4]图3示出了依据本发明一实施方式的对内容请求的两级映射和路由示意图。
[0055] 图4示出了依据本发明一实施方式的对数据块的两级映射和路由示意图。
【具体实施方式】
[0化6] 本实施例公开了一种基于分布式缓存协同中避免内容重复存储的方法，包括下述 步骤：
[0化7]SlOl.采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识。其 中，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数据块在不同的内 容提供商可能具有不同的标识，例如U化标识；所述提供商独立的标识指内容的标识与提 供商无关，因此同样的内容数据块具有相同的内容标识，例如可W采用MD2、MD4、MD5和 SHA-1等现有的哈希算法对内容数据块执行哈希操作，得到的哈希摘要可W作为提供商独 立标识。
[0化引 S102.基于内容的二元标识建立两级逻辑映射来组织缓存内容，并W分布式哈希 进行缓存协同。其中第一级映射建立提供商依赖标识和提供商独立标识之间的映射关 系，第二级映射《建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射 表项还记录了 1]^ 的逆映射关系 1^1，iri(PI(id) = (PA(id)lMPA(id) =PI(id))}，即 对于所给定表项的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提 供商独立标识。
[0化9] S103.当边缘内容路由器从域外接收到对某个内容数据块的请求时，将请求经过 两级路由转发到负责存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送 给边缘内容路由器，同时通知更新两级映射对应表项的缓存替换控制状态信息。
[0060]S104.当边缘内容路由器从域外接收到某个内容数据块时，将内容数据块经过两 级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的两级 映射关系。
[0061] 图1给出了所述步骤S103的请求在域内进行转发处理的流程图，包括：
[0062] 步骤201 ;对所述请求Q的提供商依赖标识PA<^(id)执行第一变换操作，将其变换 为分布式哈希空间中的一个可路由标识IDi;
[0063] 步骤202 ;将所述的对提供商依赖标识PA^id)执行第一变换操作后的IDi作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节 点Ni;
[0064] 步骤203 请求中的提供商依赖标识PA^id)作为键值查询该负责节点Ni的一 级映射表MTi;
[00化]步骤204-1 ;若未找到对应表项，则向所述边缘内容路由器R。发送一级映射表项 不存在的消息，结束流程；
[0066] 步骤204-2 ;若找到对应的表项，则取得对应的提供商独立标识PI。(id)= MTi(PAQ(id));
[0067] 步骤205 ;对所述的提供商独立标识Pl0(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇2;
[0068] 步骤206;将提供商独立标识Pl^id)作为请求的一个属性包含在请求中，同时W 所述的对提供商独立标识执行第二变换操作后的1化作为分布式哈希的路由目标，由底层 的分布式哈希路由机制将请求路由到对应的负责该ID的节点馬；
[0069] 步骤207 请求中的提供商独立标识Plg(id)作为键值查询该负责节点馬的二 级映射表MT2;
[0070] 步骤208-1;若未找到对应表项，则由于二级映射表项不存在必然导致对应的一 级映射表项无效，因此需向所述边缘内容路由器R。发送二级映射表项不存在的消息，请求 删除对应的一级映射表项MTi(PA<^(id))，结束流程。具体地，所述删除过程如下；首先由N2构造一级映射表项删除消息，所述删除消息包括待删除表项的键值PA^id)，然后，馬W对 PA^id)执行第一变换操作后的IDi作为路由目标，依据底层的分布式哈希路由机制将所 述一级映射表项删除消息路由到所述负责该一级映射表项的节点Ni，最后由Ni执行相应的 删除操作。
[0071] 步骤208-2 ;若找到对应的表项，则取得与提供商独立标识PI<^(id)关联的缓存数 据块；
[0072] 步骤209;负责内容数据块的节点根据数据块构造响应报文，并将响应报文发送 给边缘内容路由器；
[0073] 步骤210 ;更新两级逻辑映射对应表项的缓存替换控制状态信息，包括更新对应 二级映射表项MT2(PIg(id))和一级映射表项MTi(PAe(id))的缓存替换状态控制信息。缓 存替换所需的具体状态控制信息依赖于所采用的缓存替换算法，例如LRU替换算法需要 内容的最近访问时刻，而LFU替换算法则需要内容的访问频次。更新对应二级映射表项 MT2(Pig(id))的缓存替换状态控制信息，由所述节点馬本地完成更新PIg(id)键值对应的 表项；而所述更新对应一级映射表项MTi(PA<^(id))的缓存替换状态控制信息，应由对应的 一级映射 节点Ni完成。具体地，首先由N,构造缓存替换状态控制消息，所述消息包括待更 新表项的键值PA<^(id)和更新操作，然后，对PA^id)执行第一变换操作后的IDi作为 路由目标，依据底层的分布式哈希路由机制将所述一级映射表项更新消息路由到所述负 责该一级映射表项的节点Ni，最后，由Ni执行相应的更新操作。所述的更新操作可W包括 更新内容的访问时间、更新内容的访问频次等。
[0074] 图2给出了所述步骤S104的内容数据块D到达后在域内进行缓存处理的流程图， 包括：
[0075] 步骤301;对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其 变换为分布式哈希空间中的一个可路由标识1〇3;
[0076] 步骤302;将所述的对提供商依赖标识PAD(id)执行第一变换操作后的作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID 的节点N3;
[0077] 步骤303 内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点Ns 的一级映射表MTi;
[OO7引步骤304-1 ;若未找到对应表项，则在的建立一级映射表项MT1(PAd(id))=PlD(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PlD(id)为内容数据块的 提供商独立标识，可W存储在内容数据块本身并随之在网络中传输，也可W由节点对内容 数据块依据某种一致的算法计算而得；
[0079] 步骤304-2;若找到对应的表项，则停止转发，结束流程；
[0080] 步骤305 ;对所述的提供商独立标识PId(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇4;
[0081] 步骤306 ;W所述的对提供商独立标识执行第二变换操作后的1〇4作为分布式哈 希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节 点N4;
[0082] 步骤307;W内容数据块的提供商独立标识PlD(id)作为键值查询该负责节点N4 的二级映射表MT2;
[0083] 步骤308-1;若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加 键值PlD(id)与内容数据块D的映射关系，初始化PlD(id)和提供商依赖标识的逆映射集合 为{PAd(id)}，初始化对应表项的缓存替换状态控制信息；
[0084] 步骤308-2 ;若找到对应的表项，则在PId(id)和提供商依赖标识的逆映射集合中 添加PAd(id),结束流程；
[00化]其中，所述在Ns建立一级映射表项MTi(PAD(id)) =PlD(id)时，若表项已满，则Ns依据第一预设规则选取某个一级映射表项进行替换；
[0086] 假设被替换的一级映射表项为MTi(PAK(id)) =PlK(id)，Ns构造一级映射表项删除 消息，W对Plc(id)执行第二变换操作后得到的化作为路由目标，将所述一级映射表项删 除消息路由到负责Plc(id)二级映射的节点也NgW键值PIc(id)查询二级映射表项对应的 逆映射集合iri(PlK(id))，并执行iri(PlK(id)) =iri(PlK(id))-{PAK(id)}操作，若该操 作执行后iri(PlK(id)) =d)，即为空集，则删除二级映射表项MT2(PlK(id))及对应的内容 数据块。
[0087] 其中，所述在二级映射表项中增加键值PlD(id)与内容数据块D的映射关系，若缓 存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；
[00蝴假设被替换的二级映射表项为MT2(Pic(id))=化则N4构造二级映射表项删除通 告消息，对于V尸易V/)e<// |(户/,,、,树))，对PA(id)执行第一变换操作，并W对PA(id)执行第 一变换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负 责PA(id)的节点，由所述节点删除WPA(id)为键值的一级映射表项。
[0089] 其中，所述第一预设规则和第二预设规则可W采用相同的规则，也可W采用不同 的规则，例如第一预设规则和第二预设规则可W采用LRU、LFU、随机替换等多种缓存替换策 略。
[0090] 图3给出了依据本发明一实施例的分布式缓存协同中的对内容请求的两级映射 和请求处理过程示意图。图3中，nl-n8该8个域内节点逻辑上构成了一个分布式哈希空 间，例如可W采用化ord，化stry等现有的分布式哈希算法，并由各自节点的分布式哈希维 持模块维护哈希路由表。在本实施例中，哈希路由的标识空间为32比特的二进制整数。当 某个边缘内容路由器，如n8接收到了一个对提供商依赖标识为http://examplel.com/ a的请求后，首先对该标识进行第一变换，将其变换分布式哈希路由空间中的一个可路由标 识，接着根据底层的哈希路由将该请求转发到负责该提供商依赖标识一级映射的节点nl。 nl查询自身的一级映射表后，得出对应的提供商独立标识为5E754D34。在本实施例中，提 供商独立标识空间和哈希路由标识空间是一致的，因此，无需实施第二变换。n2依据底层的 哈希路由将该请求路由转发到负责该提供商独立标识的节点n4。n4查询二级映射表，找到 对应的内容数据块1，构造响应消息，返回给节点n8。同时，n4还需要更新自身的缓存替换 状态控制信息，并构造缓存替换状态控制消息发送给对应的一级映射节点nl。
[0091] 图4示出了依据本发明一实施例的分布式缓存协同中对数据块的两级映射和路 由示意图。图4(a)表示初始状态，即分别有两个提供商依赖的标识http://examplel.com/ a和ht化://example2.com/b映射到同一个提供商独立的标识祀754D34。当某个边缘内容 路由器接收到提供商依赖标识PA(id) =http://example3.com/foo，PI (id)=祀754D34 的内容数据块时，首先对提供商依赖标识进行第一变换操作，将其变换成一个与哈希路由 空间一致的标识，然后依据底层哈希路由将该数据块路由到负责该标识的节点n8。在本例 中，由于n8并不存在对应的一级映射表项，因此建立对应的一级映射表项。此后，依据提供 商独立标识，将该数据块路由到对应的二级映射节点n4。n4查找后发现该内容已经在该节 点缓存，因此将提供商依赖的标识http://eaxmple3.com/foo添加到与该提供商独立标识 祀754D34关联的提供商依赖标识集中，如图4(b)所示。
[0092]假设在图4(b)的状态下，由于某个数据块的到达导致n4决定替换键值为 祀754D34的二级映射表项，则，对于每个与祀754D34关联的提供商依赖标识集合中的提供 商依赖标识，n4执行第一变换操作，并W变换后的可路由标识为路由目标，将二级映射表项 删除通告消息发送给对应的节点。在本例中，n4需要将二级映射表项删除通告消息发送给 nl,n7,n8。当nl,n7,n8接收到上述消息后，删除对应的一级映射表项，如图4(c)所示。
【主权项】
1. 一种分布式缓存协同中避免内容重复存储的方法，包括下述步骤： 51, 采用二元标识法对内容数据块进行二元标识； 52, 基于内容数据块的二元标识建立两级逻辑映射表以组织缓存内容，并基于分布式 哈希对缓存内容进行缓存协同； 53, 边缘内容路由器从域外接收对某个内容数据块的请求，经过两级路由转发到负责 存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送给边缘内容路由器， 同时通知更新两级映射对应表项的缓存替换控制状态信息； 54, 边缘内容路由器从域外接收某个内容数据块，经过两级路由转发到负责存储该内 容的域内内容路由节点，并在路由转发过程中建立对应的两级映射关系。2. 如权利要求1所述的方法，其特征在于，所述二元标识法包括： 提供商依赖标识PA(id)，表示内容的标识与提供商相关，从而同样的内容数据块在不 同的内容提供商具有不同的标识； 提供商独立标识PI (id)，表示内容的标识与提供商无关，从而同样的内容数据块具有 相同的内容标识。3. 如权利要求1所述的方法，其特征在于，所述两级逻辑映射包括： 第一级映射Φ，用于建立提供商依赖标识和提供商独立标识之间的映射关系； 第二级映射ω，用于建立提供商独立标识和内容数据块本身的映射关系； 其中，第二级映射表的表项还记录Φ的逆映射关系IT1， it_1(PI(id) = {PA(id) I Φ (PA(id) =PI (id))} 公式 I 通过公式1将提供商依赖标识映射到提供商独立标识集合。4. 如权利要求1所述的方法，其特征在于，所述步骤S3进一步包括： 假设某个请求表示为Q，与该请求Q对应的提供商依赖 标识表示为PAq (id)，与该请求Q 对应的提供商独立标识表示为PIq (id)，那么， 对所述请求Q的提供商依赖标识PAQ(id)执行第一变换操作，将其变换为分布式哈希 空间中的第一可路由标识ID1; 将第一可路由标识ID1作为分布式哈希的路由目标，通过分布式哈希路由机制将请求Q 路由到对应的负责ID1的节点N 1; 以请求Q中的提供商依赖标识PAq (id)作为键值查询负责ID1的节点N i的第一级映射 表 MT1; 若未找到对应表项，贝1J向所述边缘内容路由器发送一级映射表项不存在的消息，若找 到对应的表项，则取得对应请求Q的提供商独立标识PIq(id) = MT1 (PAq(id)); 对所述的提供商独立标识PIQ(id)执行第二变换操作，将其变换为分布式哈希空间中 的第二可路由标识ID2; 将提供商独立标识PIQ(id)作为请求Q的一个属性包含在请求中，同时第二可路由标 识ID2作为分布式哈希的路由目标，通过分布式哈希路由机制将请求Q路由到对应的负责 ID2的节点N2; 以请求Q中的提供商独立标识PIq (id)作为键值查询负责ID2的节点N2的第二级映射 表 MT2; 若未找到对应表项，则向所述边缘内容路由器发送第二级映射表项不存在的消息，同 时请求删除对应的第一级映射表项MT1 (PAq(id))，若找到对应的表项，则取得与提供商独立 标识PIq (id)关联的缓存数据块。5. 如权利要求4所述的方法，其特征在于，所述的第一变换操作和第二变换操作可以 是相同的变换操作或不相同的变换操作；所述第二变换操作是恒等变换。6. 如权利要求4所述的方法，其特征在于，所述请求删除对应的第一级映射表项 MT1 (PAq (id))，进一步包括： 由节点队构造第一级映射表项删除消息，所述删除消息包括：待删除表项的键值 PAq(id); 以第一可路由标识ID1作为路由目标，由节点\通过分布式哈希路由机制将所述第一 级映射表项删除消息路由到所述负责该第一级映射表项的节点N1，并由节点N1执行相应的 删除操作。7. 如权利要求1所述的方法，其特征在于，所述更新两级逻辑映射对应表项的缓存替 换状态控制信息，包括： 更新对应第二级映射表的表项MT2 (PIQ (id))和第一级映射表的表项MT1 (PAq (id))的缓 存替换状态控制信息。8. 如权利要求7所述的方法，其特征在于，所述更新对应第二级映射表的表项 MT2(PIQ(id))的缓存替换状态控制信息，进一步包括： 通过节点N2本地完成更新PIQ (id)键值对应的表项MT2 (PIQ (id))。9. 如权利要求7所述的方法，其特征在于，所述更新第一级映射表的表项MT i (PAq (id)) 的缓存替换状态控制信息，进一步包括： 通过节点N2构造缓存替换状态控制消息，所述消息包括待更新表项的键值PAQ(id)和 更新操作； 通过节点N2以对PAQ(id)执行第一变换操作后的第一可路由标识^^作为路由目标， 通过分布式哈希路由机制将所述第一级映射表项更新消息路由到所述负责该第一级映射 表项的节点N1; 由&执行相应的更新操作。10. 如权利要求1所述的方法，其特征在于，所述步骤S4,进一步包括： 假设某个内容数据块表示为D，与该内容数据块D对应的提供商依赖标识表示为 PAd (id)，与该请求Q对应的提供商独立标识表示为PId (id)，那么， 对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其变换为分布式 哈希空间中的第三可路由标识ID3; 将第三可路由标识ID3作为分布式哈希的路由目标，通过分布式哈希路由机制将内容 数据块路由到对应的负责ID3的节点N3; 以内容数据块D中的提供商依赖标识PAd (id)作为键值查询负责ID3的节点N 3的第一 级映射表MT1; 若未找到对应表项，则在节点N3建立第一级映射表项MT i (PAd (id) )= PId (id)，并初始 化所述表项的缓存替换状态控制信息，若找到对应的表项，则停止转发； 对所述的内容数据块D的提供商独立标识PID(id)执行第二变换操作，将其变换为分 布式哈希空间中的第四可路由标识ID4; 以第四可路由标识ID4作为分布式哈希的路由目标，通过分布式哈希路由机制将内容 数据块D路由到对应的负责ID4的节点N4; 以内容数据块D的提供商独立标识PID(id)作为键值，查询该负责节点N4的第二级映 射表MT2; 若未找到对应表项，则缓存内容数据块D，并在第二级映射表项中增加键值PId (id)与 内容数据块D的映射关系，初始化PID(id)和提供商依赖标识的逆映射集合为{PAD(id)}， 初始化对应表项的缓存替换状态控制信息； 若找到对应的表项，则在PID(id)和提供商依赖标识的逆映射集合中添加 PAD(id)，结 束流程。11. 如权利要求10所述的方法，其特征在于，所述在节点N 3建立第一级映射表项 MT1 (PAd (id) )= PId (id)时，若表项已满，则节点N3依据第一预设规则选取某个第一级映射 表项进行替换，进一步包括下述步骤： 节点队构造第一级映射表项删除消息，以对待替换的提供商独立标识PI K(id)执行第 二变换操作后得到的第五路由标识ID5作为路由目标，将所述第一级映射表项删除消息路 由到负责PIk(id)的第二级映射的节点N5; 节点N5以键值PI K(id)查询第二级映射表项对应的逆映射集合ιΤ1 (PIK(id))，并执行 irHpijid)) = irHpijidD-iPAjid)}操作，若该操作执行后！^(pijid)) = φ，即为 空集，则删除第二级映射表项MT2(PIJid))及对应的内容数据块。12. 如权利要求10所述的方法，其特征在于，所述在第二级映射表项中增加键值 PID(id)与内容数据块D的映射关系，若缓存空间已满，或表项已满，则节点N4依据第二预 设规则选取某个第二级映射表项MT2 (PIK(id))进行替换，进一步包括： 节点N4构造第二级映射表项删除通告消息，对于1M/,办/))，对PA(id)执 行第一变换操作，并以对PA(id)执行第一变换操作后得到的ID为路由目标，将所述第二级 映射表项删除通告消息路由到对应的负责PA(id)的节点，所述第二级映射表项删除通告 消息包括：提供商依赖标识PA(id); 所述节点接收到第二级映射表项删除通告消息后，删除以PA(id)为键值的第一级映 射表项。13. -种分布式缓存协同中避免内容重复存储的内容路由器装置，其特征在于，包括： 分布式哈希维持模块、路由转发模块、一级映射表、二级映射表、内容块缓存库、一级映 射表替换模块、二级映射表替换模块、第一变换模块、第二变换模块； 内容路由器装置还包含一个提供商独立标识生成模块； 其中，所述分布式哈希维持模块用于维持分布式哈希路由表；所述路由转发模块用于 依据消息的分布式哈希路由标识和分布式哈希路由表对消息进行路由转发；所述一级映射 表用于存储内容的提供商依赖标识和提供商独立标识的映射关系；所述二级映射表用户存 储内容的提供商独立标识和内容数据块的映射关系，同时存储所述的提供商独立标识对应 的一级映射的逆映射；所述内容块缓存库用于缓存实际的内容数据块；所述一级映射表替 换模块用于根据预设的第一替换策略选择合适的一级映射表项予以替换；所述二级映射表 替换模块用于根据预设的第二替换策略选择合适的二级映射表项予以替换，并从内容块缓 存库中删除对应的内容数据块；所述第一变换模块用于对内容的提供商依赖标识执行变换 操作，生成分布式哈希路由空间中的一个可路由标识；所述第二变换模块用于对内容的提 供商独立标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识；所述提供商 独立标识生成模块可以基于内容数据块生成仅与内容数据相关的提供商独立标识。
【专利摘要】本发明公开了一种分布式缓存协同中避免内容重复存储的方法：采用二元标识法对内容数据块进行二元标识；基于内容数据块的二元标识建立两级逻辑映射表以组织缓存内容，并基于分布式哈希对缓存内容进行缓存协同；边缘内容路由器从域外接收对某个内容数据块的请求，经过两级路由转发到负责存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送给边缘内容路由器，同时通知更新两级映射对应表项的缓存替换控制状态信息；边缘内容路由器从域外接收某个内容数据块，经过两级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的两级映射关系。本发明的方法能有效地避免内容的重复存储，降低网络流量，提高用户体验。
【IPC分类】H04L29/08
【公开号】CN104901996
【申请号】CN201510020722
【发明人】张国强
【申请人】南京师范大学
【公开日】2015年9月9日
【申请日】2015年1月15日
【技术领域】
[0001] 本发明设及网络存储和内容分发技术领域，尤其设及一种分布式缓存协同中避免 内容重复存储的方法和装置。
【背景技术】
[0002] 目前，用户对互联网的访问已经从点对点通信为主转为内容获取为主。而传统的 TCP/IP网络仅传输内容，并不感知内容，从而造成了网络上大量的冗余流量传输。为了解决 由于内容获取而引发的内容爆炸，无论是目前的互联网还是研究界提出的未来网络，都把 缓存作为基本的手段，来满足用户对内容的具有重尾特征的异步访问。例如，互联网采用的 透明的Web化ch，P2P内容分发网络中的PP化che、CDN中的内容缓存，W及研究界提出的信 息/内容中屯、网络NDN，DONA等。无论是内容提供商还是网络运营商，都倾向于在网络内部 署泛在的缓存系统来降低网络流量、提高用户体验。
[0003] 但是，现在的内容在缓存中WU化为标识，而同样的内容在不同的内容提供商处 会采用不同的U化标识，导致缓存节点依据U化难W识别实际内容相同的对象，从而会在缓 存中重复存储，导致了缓存利用率的低下。因此，在泛在缓存缓存的前提下，亟需提出一种 分布式缓存环境下避免缓存内容重复存储的方法。
【发明内容】
[0004] 本发明为解决上述技术问题，提供一种分布式缓存协同中避免内容重复存储的方 法和装置，能有效地避免内容的重复存储、降低网络流量、提高用户体验。所述技术方案如 下：
[0005] 一方面，本发明提出了一种分布式缓存协同中避免内容重复存储的方法，所述方 法包括：
[0006] 采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识；
[0007] 基于二元标识建立两级逻辑映射来组织缓存内容，并W分布式哈希进行缓存协 同。其中第一级映射建立提供商依赖标识和提供商独立标识之间的映射关系，第二级映 射《建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射表项还记录了 勺逆映射关系1^1，iri(pi(id) = {PA(id)IMPA(id) =pi(id))}，即对于所给定表项 的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提供商独立标识； [000引 由网络域的边缘内容路由器将从域外到达的请求经过两级路由转发到负责存储 该内容的域内节点；
[0009] 负责内容数据块的节点将对应的数据块发送给边缘内容路由器；
[0010] 更新两级逻辑映射对应表项的缓存替换控制状态信息；
[0011] 由网络域的边缘内容路由器在收到某个内容数据块时做出是否要缓存所述内容 数据块的决定；
[0012] 当需要缓存所述内容数据块时，所述边缘内容路由器将内容数据块经过两级路由 转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的二级映射关 系。
[0013] 进一步地，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数 据块在不同的内容提供商可能具有不同的标识；
[0014] 进一步地，所述提供商独立的标识指内容的标识与提供商无关，因此同样的内容 数据块具有相同的内容标识；
[0015] 进一步地，所述的内容请求包含对所请求内容数据块的提供商依赖标识；
[0016] 进一步地，所述由网络域的边缘内容路由器R。将从域外到达的请求Q经过两级路 由转发到负责存储该内容的域内节点，包括：
[0017] 步骤201;对所述请求Q的提供商依赖标识PA<^(id)执行第一变换操作，将其变换 为分布式哈希空间中的一个可路由标识IDi;
[0018] 步骤202 ;将所述的对提供商依赖标识PA^id)执行第一变换操作后的IDi作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节 点Ni;
[0019] 步骤203 请求中的提供商依赖标识PA^id)作为键值查询该负责节点Ni的一 级映射表MTi;
[0020] 步骤204-1;若未找到对应表项，则向所述边缘内容路由器R。发送一级映射表项 不存在的消息，结束流程；
[002U步骤204-2 ;若找到对应的表项，则取得对应的提供商独立标识PI。(id)= MTi(PAQ(id));
[0022]步骤205;对所述的提供商独立标识Pl0(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇2;
[002引步骤206 ;将提供商独立标识Pl^id)作为请求的一个属性包含在请求中，同时W所述的对提供商独立标识执行第二变换操作后的1化作为分布式哈希的路由目标，由底层 的分布式哈希路由机制将请求路由到对应的负责该ID的节点馬；
[0024] 步骤207 请求中的提供商独立标识Plg(id)作为键值查询该负责节点馬的二 级映射表MT2;
[0025] 步骤208-1;若未找到对应表项，则向所述边缘内容路由器R。发送二级映射表项 不存在的消息，同时请求删除对应的一级映射表项MTi(PA<^ (id))，结束流程；
[0026] 步骤208-2;若找到对应的表项，则取得与提供商独立标识PI<^(id)关联的缓存数 据块；
[0027] 其中，所述的第一变换操作和第二变换操作可W是相同的变换操作，也可W是不 相同的变换操作；所述第二变换操作也可W是恒等变换。
[0028] 其中，所述请求删除对应的一级映射表项MTi(PAe(id))，由馬构造一级映射表项 删除消息，所述删除消息包括待删除表项的键值PA^id)。W对PA^id)执行第一变换操作 后的IDi作为路由目标，由N2依据底层的分布式哈希路由机制将所述一级映射表项删除消 息路由到所述负责该一级映射表项的节点Ni，并由Ni执行相应的删除操作；
[0029] 进一步地，所述更新两级逻辑映射对应表项的缓存替换状态控制信息，包括：更新 对应二级映射表项MT2 (Pig(id))和一级映射表项MTi(PAg(id))的缓存替换状态控制信息；
[0030] 其中，所述更新对应二级映射表项MT2(PIe(id))的缓存替换状态控制信息，由所 述节点馬本地完成更新PIg(id)键值对应的表项；
[003U 其中，所述更新对应一级映射表项MTi(PA^id))的缓存替换状态控制信息，由馬 构造缓存替换状态控制消息，所述消息包括待更新表项的键值PA0(id)和更新操作。W对PA^id)执行第一变换操作后的IDi作为路由目标，由N2依据底层的分布式哈希路由机制将 所述一级映射表项更新消息路由到所述负责该一级映射表项的节点N。并由Ni执行相应的 更新操作；
[0032] 进一步地，所述边缘内容路由器将内容数据块D经过两级路由转发到负责存储该 内容的域内节点，并建立对应的两级映射关系，包括：
[0033] 步骤301;对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其 变换为分布式哈希空间中的一个可路由标识1〇3;
[0034] 步骤302 ;将所述的对提供商依赖标识PAD(id)执行第一变换操作后的作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID 的节点N3;
[0035] 步骤303 内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点Ns 的一级映射表MTi;
[0036] 步骤304-1;若未找到对应表项，则在N3建立一级映射表项MT1(PAd(id))= PlD(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PlD(id)为内容数据块的 提供商独立标识，可W存储在内容数据块本身并随之在网络中传输，也可W由节点对内容 数据块依据某种一致的算法计算而得；
[0037] 步骤304-2;若找到对应的表项，则停止转发，结束流程；
[003引步骤305;对所述的提供商独立标识PId(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识104;
[0039] 步骤306 ;W所述的对提供商独立标识执行第二变换操作后的1〇4作为分布式哈 希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节 点N4;
[0040] 步骤307 ;W内容数据块的提供商独立标识PlD(id)作为键值查询该负责节点N4 的二级映射表MT2;
[004U步骤308-1 ;若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加 键值PlD(id)与内容数据块D的映射关系，初始化PlD(id)和提供商依赖标识的逆映射集合 为{PAd(id)}，初 始化对应表项的缓存替换状态控制信息；
[00创步骤308-2 ;若找到对应的表项，则在PId(id)和提供商依赖标识的逆映射集合中 添加PAd(id),结束流程；
[0043] 其中，所述在Ns建立一级映射表项MTi(PAD(id)) =PlD(id)时，若表项已满，则Ns 依据第一预设规则选取某个一级映射表项进行替换；
[0044] 假设被替换的一级映射表项为MTi(PAK(id)) =PlK(id)，Ns构造一级映射表项删除 消息，W对Plc(id)执行第二变换操作后得到的化作为路由目标，将所述一级映射表项删 除消息路由到负责Plc(id)二级映射的节点也NgW键值PIc(id)查询二级映射表项对应的 逆映射集合iri(PlK(id))，并执行iri(PlK(id)) =iri(PlK(id))-{PAK(id)}操作，若该操 作执行后iri(PlK(id)) = 4,即为空集，则删除二级映射表项MT2(PlK(id))及对应的内容 数据块。
[0045] 其中，所述在二级映射表项中增加键值PlD(id)与内容数据块D的映射关系，若缓 存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；
[0046] 假设被替换的二级映射表项为MT2(Pic(id))=化则N4构造二级映射表项删除通 告消息，对于似))，对PA(id)执行第一变换操作，并W对PA(id)执行第 一变换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负 责PA(id)的节点，由所述节点删除WPA(id)为键值的一级映射表项。
[0047] 其中，所述第一预设规则和第二预设规则可W采用相同的规则，也可W采用不同 的规则。
[0048] 另一方面，本发明提出一种分布式缓存协同中避免内容重复存储的内容路由器装 置，包括；分布式哈希维持模块、路由转发模块、一级映射表、二级映射表、内容块缓存库、一 级映射表替换模块、二级映射表替换模块、第一变换模块、第二变换模块。可选地，内容路由 器装置还可W包含一个提供商独立标识生成模块。
[0049] 其中，所述分布式哈希维持模块用于维持分布式哈希路由表；所述路由转发模块 用于依据消息的分布式哈希路由标识和分布式哈希路由表对消息进行路由转发；所述一级 映射表用于存储内容的提供商依赖标识和提供商独立标识的映射关系；所述二级映射表用 户存储内容的提供商独立标识和内容数据块的映射关系，同时存储所述的提供商独立标识 对应的一级映射的逆映射；所述内容块缓存库用于缓存实际的内容数据块；所述一级映射 表替换模块用于根据预设的第一替换策略选择合适的一级映射表项予W替换；所述二级映 射表替换模块用于根据预设的第二替换策略选择合适的二级映射表项予W替换，并从内容 块缓存库中删除对应的内容数据块；所述第一变换模块用于对内容的提供商依赖标识执行 变换操作，生成分布式哈希路由空间中的一个可路由标识；所述第二变换模块用于对内容 的提供商独立标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识。所述提 供商独立标识生成模块可W基于内容数据块生成仅与内容数据相关的提供商独立标识。
[0050] 本发明采用W上技术方案与现有技术相比，具有W下技术效果：
[0051] 通过在域内实现基于二级映射的分布式缓存协同，能有效地避免相同内容的重 复存储，降低网络域间流量，提升用户体验。
【附图说明】
[0052] 图1示出了依据本发明一实施方式的分布式缓存域对内容请求的处理流程； [0化3] 图2示出了依据本发明一实施方式的分布式缓存域对到达的内容数据块的处理 流程；
[0化4]图3示出了依据本发明一实施方式的对内容请求的两级映射和路由示意图。
[0055] 图4示出了依据本发明一实施方式的对数据块的两级映射和路由示意图。
【具体实施方式】
[0化6] 本实施例公开了一种基于分布式缓存协同中避免内容重复存储的方法，包括下述 步骤：
[0化7]SlOl.采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识。其 中，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数据块在不同的内 容提供商可能具有不同的标识，例如U化标识；所述提供商独立的标识指内容的标识与提 供商无关，因此同样的内容数据块具有相同的内容标识，例如可W采用MD2、MD4、MD5和 SHA-1等现有的哈希算法对内容数据块执行哈希操作，得到的哈希摘要可W作为提供商独 立标识。
[0化引 S102.基于内容的二元标识建立两级逻辑映射来组织缓存内容，并W分布式哈希 进行缓存协同。其中第一级映射建立提供商依赖标识和提供商独立标识之间的映射关 系，第二级映射《建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射 表项还记录了 1]^ 的逆映射关系 1^1，iri(PI(id) = (PA(id)lMPA(id) =PI(id))}，即 对于所给定表项的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提 供商独立标识。
[0化9] S103.当边缘内容路由器从域外接收到对某个内容数据块的请求时，将请求经过 两级路由转发到负责存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送 给边缘内容路由器，同时通知更新两级映射对应表项的缓存替换控制状态信息。
[0060]S104.当边缘内容路由器从域外接收到某个内容数据块时，将内容数据块经过两 级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的两级 映射关系。
[0061] 图1给出了所述步骤S103的请求在域内进行转发处理的流程图，包括：
[0062] 步骤201 ;对所述请求Q的提供商依赖标识PA<^(id)执行第一变换操作，将其变换 为分布式哈希空间中的一个可路由标识IDi;
[0063] 步骤202 ;将所述的对提供商依赖标识PA^id)执行第一变换操作后的IDi作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节 点Ni;
[0064] 步骤203 请求中的提供商依赖标识PA^id)作为键值查询该负责节点Ni的一 级映射表MTi;
[00化]步骤204-1 ;若未找到对应表项，则向所述边缘内容路由器R。发送一级映射表项 不存在的消息，结束流程；
[0066] 步骤204-2 ;若找到对应的表项，则取得对应的提供商独立标识PI。(id)= MTi(PAQ(id));
[0067] 步骤205 ;对所述的提供商独立标识Pl0(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇2;
[0068] 步骤206;将提供商独立标识Pl^id)作为请求的一个属性包含在请求中，同时W 所述的对提供商独立标识执行第二变换操作后的1化作为分布式哈希的路由目标，由底层 的分布式哈希路由机制将请求路由到对应的负责该ID的节点馬；
[0069] 步骤207 请求中的提供商独立标识Plg(id)作为键值查询该负责节点馬的二 级映射表MT2;
[0070] 步骤208-1;若未找到对应表项，则由于二级映射表项不存在必然导致对应的一 级映射表项无效，因此需向所述边缘内容路由器R。发送二级映射表项不存在的消息，请求 删除对应的一级映射表项MTi(PA<^(id))，结束流程。具体地，所述删除过程如下；首先由N2构造一级映射表项删除消息，所述删除消息包括待删除表项的键值PA^id)，然后，馬W对 PA^id)执行第一变换操作后的IDi作为路由目标，依据底层的分布式哈希路由机制将所 述一级映射表项删除消息路由到所述负责该一级映射表项的节点Ni，最后由Ni执行相应的 删除操作。
[0071] 步骤208-2 ;若找到对应的表项，则取得与提供商独立标识PI<^(id)关联的缓存数 据块；
[0072] 步骤209;负责内容数据块的节点根据数据块构造响应报文，并将响应报文发送 给边缘内容路由器；
[0073] 步骤210 ;更新两级逻辑映射对应表项的缓存替换控制状态信息，包括更新对应 二级映射表项MT2(PIg(id))和一级映射表项MTi(PAe(id))的缓存替换状态控制信息。缓 存替换所需的具体状态控制信息依赖于所采用的缓存替换算法，例如LRU替换算法需要 内容的最近访问时刻，而LFU替换算法则需要内容的访问频次。更新对应二级映射表项 MT2(Pig(id))的缓存替换状态控制信息，由所述节点馬本地完成更新PIg(id)键值对应的 表项；而所述更新对应一级映射表项MTi(PA<^(id))的缓存替换状态控制信息，应由对应的 一级映射 节点Ni完成。具体地，首先由N,构造缓存替换状态控制消息，所述消息包括待更 新表项的键值PA<^(id)和更新操作，然后，对PA^id)执行第一变换操作后的IDi作为 路由目标，依据底层的分布式哈希路由机制将所述一级映射表项更新消息路由到所述负 责该一级映射表项的节点Ni，最后，由Ni执行相应的更新操作。所述的更新操作可W包括 更新内容的访问时间、更新内容的访问频次等。
[0074] 图2给出了所述步骤S104的内容数据块D到达后在域内进行缓存处理的流程图， 包括：
[0075] 步骤301;对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其 变换为分布式哈希空间中的一个可路由标识1〇3;
[0076] 步骤302;将所述的对提供商依赖标识PAD(id)执行第一变换操作后的作为分 布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID 的节点N3;
[0077] 步骤303 内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点Ns 的一级映射表MTi;
[OO7引步骤304-1 ;若未找到对应表项，则在的建立一级映射表项MT1(PAd(id))=PlD(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PlD(id)为内容数据块的 提供商独立标识，可W存储在内容数据块本身并随之在网络中传输，也可W由节点对内容 数据块依据某种一致的算法计算而得；
[0079] 步骤304-2;若找到对应的表项，则停止转发，结束流程；
[0080] 步骤305 ;对所述的提供商独立标识PId(id)执行第二变换操作，将其变换为分布 式哈希空间中的一个可路由标识1〇4;
[0081] 步骤306 ;W所述的对提供商独立标识执行第二变换操作后的1〇4作为分布式哈 希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节 点N4;
[0082] 步骤307;W内容数据块的提供商独立标识PlD(id)作为键值查询该负责节点N4 的二级映射表MT2;
[0083] 步骤308-1;若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加 键值PlD(id)与内容数据块D的映射关系，初始化PlD(id)和提供商依赖标识的逆映射集合 为{PAd(id)}，初始化对应表项的缓存替换状态控制信息；
[0084] 步骤308-2 ;若找到对应的表项，则在PId(id)和提供商依赖标识的逆映射集合中 添加PAd(id),结束流程；
[00化]其中，所述在Ns建立一级映射表项MTi(PAD(id)) =PlD(id)时，若表项已满，则Ns依据第一预设规则选取某个一级映射表项进行替换；
[0086] 假设被替换的一级映射表项为MTi(PAK(id)) =PlK(id)，Ns构造一级映射表项删除 消息，W对Plc(id)执行第二变换操作后得到的化作为路由目标，将所述一级映射表项删 除消息路由到负责Plc(id)二级映射的节点也NgW键值PIc(id)查询二级映射表项对应的 逆映射集合iri(PlK(id))，并执行iri(PlK(id)) =iri(PlK(id))-{PAK(id)}操作，若该操 作执行后iri(PlK(id)) =d)，即为空集，则删除二级映射表项MT2(PlK(id))及对应的内容 数据块。
[0087] 其中，所述在二级映射表项中增加键值PlD(id)与内容数据块D的映射关系，若缓 存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；
[00蝴假设被替换的二级映射表项为MT2(Pic(id))=化则N4构造二级映射表项删除通 告消息，对于V尸易V/)e<// |(户/,,、,树))，对PA(id)执行第一变换操作，并W对PA(id)执行第 一变换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负 责PA(id)的节点，由所述节点删除WPA(id)为键值的一级映射表项。
[0089] 其中，所述第一预设规则和第二预设规则可W采用相同的规则，也可W采用不同 的规则，例如第一预设规则和第二预设规则可W采用LRU、LFU、随机替换等多种缓存替换策 略。
[0090] 图3给出了依据本发明一实施例的分布式缓存协同中的对内容请求的两级映射 和请求处理过程示意图。图3中，nl-n8该8个域内节点逻辑上构成了一个分布式哈希空 间，例如可W采用化ord，化stry等现有的分布式哈希算法，并由各自节点的分布式哈希维 持模块维护哈希路由表。在本实施例中，哈希路由的标识空间为32比特的二进制整数。当 某个边缘内容路由器，如n8接收到了一个对提供商依赖标识为http://examplel.com/ a的请求后，首先对该标识进行第一变换，将其变换分布式哈希路由空间中的一个可路由标 识，接着根据底层的哈希路由将该请求转发到负责该提供商依赖标识一级映射的节点nl。 nl查询自身的一级映射表后，得出对应的提供商独立标识为5E754D34。在本实施例中，提 供商独立标识空间和哈希路由标识空间是一致的，因此，无需实施第二变换。n2依据底层的 哈希路由将该请求路由转发到负责该提供商独立标识的节点n4。n4查询二级映射表，找到 对应的内容数据块1，构造响应消息，返回给节点n8。同时，n4还需要更新自身的缓存替换 状态控制信息，并构造缓存替换状态控制消息发送给对应的一级映射节点nl。
[0091] 图4示出了依据本发明一实施例的分布式缓存协同中对数据块的两级映射和路 由示意图。图4(a)表示初始状态，即分别有两个提供商依赖的标识http://examplel.com/ a和ht化://example2.com/b映射到同一个提供商独立的标识祀754D34。当某个边缘内容 路由器接收到提供商依赖标识PA(id) =http://example3.com/foo，PI (id)=祀754D34 的内容数据块时，首先对提供商依赖标识进行第一变换操作，将其变换成一个与哈希路由 空间一致的标识，然后依据底层哈希路由将该数据块路由到负责该标识的节点n8。在本例 中，由于n8并不存在对应的一级映射表项，因此建立对应的一级映射表项。此后，依据提供 商独立标识，将该数据块路由到对应的二级映射节点n4。n4查找后发现该内容已经在该节 点缓存，因此将提供商依赖的标识http://eaxmple3.com/foo添加到与该提供商独立标识 祀754D34关联的提供商依赖标识集中，如图4(b)所示。
[0092]假设在图4(b)的状态下，由于某个数据块的到达导致n4决定替换键值为 祀754D34的二级映射表项，则，对于每个与祀754D34关联的提供商依赖标识集合中的提供 商依赖标识，n4执行第一变换操作，并W变换后的可路由标识为路由目标，将二级映射表项 删除通告消息发送给对应的节点。在本例中，n4需要将二级映射表项删除通告消息发送给 nl,n7,n8。当nl,n7,n8接收到上述消息后，删除对应的一级映射表项，如图4(c)所示。
【主权项】
1. 一种分布式缓存协同中避免内容重复存储的方法，包括下述步骤： 51, 采用二元标识法对内容数据块进行二元标识； 52, 基于内容数据块的二元标识建立两级逻辑映射表以组织缓存内容，并基于分布式 哈希对缓存内容进行缓存协同； 53, 边缘内容路由器从域外接收对某个内容数据块的请求，经过两级路由转发到负责 存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送给边缘内容路由器， 同时通知更新两级映射对应表项的缓存替换控制状态信息； 54, 边缘内容路由器从域外接收某个内容数据块，经过两级路由转发到负责存储该内 容的域内内容路由节点，并在路由转发过程中建立对应的两级映射关系。2. 如权利要求1所述的方法，其特征在于，所述二元标识法包括： 提供商依赖标识PA(id)，表示内容的标识与提供商相关，从而同样的内容数据块在不 同的内容提供商具有不同的标识； 提供商独立标识PI (id)，表示内容的标识与提供商无关，从而同样的内容数据块具有 相同的内容标识。3. 如权利要求1所述的方法，其特征在于，所述两级逻辑映射包括： 第一级映射Φ，用于建立提供商依赖标识和提供商独立标识之间的映射关系； 第二级映射ω，用于建立提供商独立标识和内容数据块本身的映射关系； 其中，第二级映射表的表项还记录Φ的逆映射关系IT1， it_1(PI(id) = {PA(id) I Φ (PA(id) =PI (id))} 公式 I 通过公式1将提供商依赖标识映射到提供商独立标识集合。4. 如权利要求1所述的方法，其特征在于，所述步骤S3进一步包括： 假设某个请求表示为Q，与该请求Q对应的提供商依赖 标识表示为PAq (id)，与该请求Q 对应的提供商独立标识表示为PIq (id)，那么， 对所述请求Q的提供商依赖标识PAQ(id)执行第一变换操作，将其变换为分布式哈希 空间中的第一可路由标识ID1; 将第一可路由标识ID1作为分布式哈希的路由目标，通过分布式哈希路由机制将请求Q 路由到对应的负责ID1的节点N 1; 以请求Q中的提供商依赖标识PAq (id)作为键值查询负责ID1的节点N i的第一级映射 表 MT1; 若未找到对应表项，贝1J向所述边缘内容路由器发送一级映射表项不存在的消息，若找 到对应的表项，则取得对应请求Q的提供商独立标识PIq(id) = MT1 (PAq(id)); 对所述的提供商独立标识PIQ(id)执行第二变换操作，将其变换为分布式哈希空间中 的第二可路由标识ID2; 将提供商独立标识PIQ(id)作为请求Q的一个属性包含在请求中，同时第二可路由标 识ID2作为分布式哈希的路由目标，通过分布式哈希路由机制将请求Q路由到对应的负责 ID2的节点N2; 以请求Q中的提供商独立标识PIq (id)作为键值查询负责ID2的节点N2的第二级映射 表 MT2; 若未找到对应表项，则向所述边缘内容路由器发送第二级映射表项不存在的消息，同 时请求删除对应的第一级映射表项MT1 (PAq(id))，若找到对应的表项，则取得与提供商独立 标识PIq (id)关联的缓存数据块。5. 如权利要求4所述的方法，其特征在于，所述的第一变换操作和第二变换操作可以 是相同的变换操作或不相同的变换操作；所述第二变换操作是恒等变换。6. 如权利要求4所述的方法，其特征在于，所述请求删除对应的第一级映射表项 MT1 (PAq (id))，进一步包括： 由节点队构造第一级映射表项删除消息，所述删除消息包括：待删除表项的键值 PAq(id); 以第一可路由标识ID1作为路由目标，由节点\通过分布式哈希路由机制将所述第一 级映射表项删除消息路由到所述负责该第一级映射表项的节点N1，并由节点N1执行相应的 删除操作。7. 如权利要求1所述的方法，其特征在于，所述更新两级逻辑映射对应表项的缓存替 换状态控制信息，包括： 更新对应第二级映射表的表项MT2 (PIQ (id))和第一级映射表的表项MT1 (PAq (id))的缓 存替换状态控制信息。8. 如权利要求7所述的方法，其特征在于，所述更新对应第二级映射表的表项 MT2(PIQ(id))的缓存替换状态控制信息，进一步包括： 通过节点N2本地完成更新PIQ (id)键值对应的表项MT2 (PIQ (id))。9. 如权利要求7所述的方法，其特征在于，所述更新第一级映射表的表项MT i (PAq (id)) 的缓存替换状态控制信息，进一步包括： 通过节点N2构造缓存替换状态控制消息，所述消息包括待更新表项的键值PAQ(id)和 更新操作； 通过节点N2以对PAQ(id)执行第一变换操作后的第一可路由标识^^作为路由目标， 通过分布式哈希路由机制将所述第一级映射表项更新消息路由到所述负责该第一级映射 表项的节点N1; 由&执行相应的更新操作。10. 如权利要求1所述的方法，其特征在于，所述步骤S4,进一步包括： 假设某个内容数据块表示为D，与该内容数据块D对应的提供商依赖标识表示为 PAd (id)，与该请求Q对应的提供商独立标识表示为PId (id)，那么， 对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其变换为分布式 哈希空间中的第三可路由标识ID3; 将第三可路由标识ID3作为分布式哈希的路由目标，通过分布式哈希路由机制将内容 数据块路由到对应的负责ID3的节点N3; 以内容数据块D中的提供商依赖标识PAd (id)作为键值查询负责ID3的节点N 3的第一 级映射表MT1; 若未找到对应表项，则在节点N3建立第一级映射表项MT i (PAd (id) )= PId (id)，并初始 化所述表项的缓存替换状态控制信息，若找到对应的表项，则停止转发； 对所述的内容数据块D的提供商独立标识PID(id)执行第二变换操作，将其变换为分 布式哈希空间中的第四可路由标识ID4; 以第四可路由标识ID4作为分布式哈希的路由目标，通过分布式哈希路由机制将内容 数据块D路由到对应的负责ID4的节点N4; 以内容数据块D的提供商独立标识PID(id)作为键值，查询该负责节点N4的第二级映 射表MT2; 若未找到对应表项，则缓存内容数据块D，并在第二级映射表项中增加键值PId (id)与 内容数据块D的映射关系，初始化PID(id)和提供商依赖标识的逆映射集合为{PAD(id)}， 初始化对应表项的缓存替换状态控制信息； 若找到对应的表项，则在PID(id)和提供商依赖标识的逆映射集合中添加 PAD(id)，结 束流程。11. 如权利要求10所述的方法，其特征在于，所述在节点N 3建立第一级映射表项 MT1 (PAd (id) )= PId (id)时，若表项已满，则节点N3依据第一预设规则选取某个第一级映射 表项进行替换，进一步包括下述步骤： 节点队构造第一级映射表项删除消息，以对待替换的提供商独立标识PI K(id)执行第 二变换操作后得到的第五路由标识ID5作为路由目标，将所述第一级映射表项删除消息路 由到负责PIk(id)的第二级映射的节点N5; 节点N5以键值PI K(id)查询第二级映射表项对应的逆映射集合ιΤ1 (PIK(id))，并执行 irHpijid)) = irHpijidD-iPAjid)}操作，若该操作执行后！^(pijid)) = φ，即为 空集，则删除第二级映射表项MT2(PIJid))及对应的内容数据块。12. 如权利要求10所述的方法，其特征在于，所述在第二级映射表项中增加键值 PID(id)与内容数据块D的映射关系，若缓存空间已满，或表项已满，则节点N4依据第二预 设规则选取某个第二级映射表项MT2 (PIK(id))进行替换，进一步包括： 节点N4构造第二级映射表项删除通告消息，对于1M/,办/))，对PA(id)执 行第一变换操作，并以对PA(id)执行第一变换操作后得到的ID为路由目标，将所述第二级 映射表项删除通告消息路由到对应的负责PA(id)的节点，所述第二级映射表项删除通告 消息包括：提供商依赖标识PA(id); 所述节点接收到第二级映射表项删除通告消息后，删除以PA(id)为键值的第一级映 射表项。13. -种分布式缓存协同中避免内容重复存储的内容路由器装置，其特征在于，包括： 分布式哈希维持模块、路由转发模块、一级映射表、二级映射表、内容块缓存库、一级映 射表替换模块、二级映射表替换模块、第一变换模块、第二变换模块； 内容路由器装置还包含一个提供商独立标识生成模块； 其中，所述分布式哈希维持模块用于维持分布式哈希路由表；所述路由转发模块用于 依据消息的分布式哈希路由标识和分布式哈希路由表对消息进行路由转发；所述一级映射 表用于存储内容的提供商依赖标识和提供商独立标识的映射关系；所述二级映射表用户存 储内容的提供商独立标识和内容数据块的映射关系，同时存储所述的提供商独立标识对应 的一级映射的逆映射；所述内容块缓存库用于缓存实际的内容数据块；所述一级映射表替 换模块用于根据预设的第一替换策略选择合适的一级映射表项予以替换；所述二级映射表 替换模块用于根据预设的第二替换策略选择合适的二级映射表项予以替换，并从内容块缓 存库中删除对应的内容数据块；所述第一变换模块用于对内容的提供商依赖标识执行变换 操作，生成分布式哈希路由空间中的一个可路由标识；所述第二变换模块用于对内容的提 供商独立标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识；所述提供商 独立标识生成模块可以基于内容数据块生成仅与内容数据相关的提供商独立标识。
【专利摘要】本发明公开了一种分布式缓存协同中避免内容重复存储的方法：采用二元标识法对内容数据块进行二元标识；基于内容数据块的二元标识建立两级逻辑映射表以组织缓存内容，并基于分布式哈希对缓存内容进行缓存协同；边缘内容路由器从域外接收对某个内容数据块的请求，经过两级路由转发到负责存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送给边缘内容路由器，同时通知更新两级映射对应表项的缓存替换控制状态信息；边缘内容路由器从域外接收某个内容数据块，经过两级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的两级映射关系。本发明的方法能有效地避免内容的重复存储，降低网络流量，提高用户体验。
【IPC分类】H04L29/08
【公开号】CN104901996
【申请号】CN201510020722
【发明人】张国强
【申请人】南京师范大学
【公开日】2015年9月9日
【申请日】2015年1月15日
最新回复(0)