分布式缓存协同中避免内容重复存储的方法和装置

暂无

分布式缓存协同中避免内容重复存储的方法和装置\n技术领域\n[0001] 本发明涉及网络存储和内容分发技术领域，尤其涉及一种分布式缓存协同中避免内容重复存储的方法和装置。\n背景技术\n[0002] 目前，用户对互联网的访问已经从点对点通信为主转为内容获取为主。而传统的TCP/IP网络仅传输内容，并不感知内容，从而造成了网络上大量的冗余流量传输。为了解决由于内容获取而引发的内容爆炸，无论是目前的互联网还是研究界提出的未来网络，都把缓存作为基本的手段，来满足用户对内容的具有重尾特征的异步访问。例如，互联网采用的透明的Web Cach,P2P内容分发网络中的PPCache、CDN中的内容缓存，以及研究界提出的信息/内容中心网络NDN，DONA等。无论是内容提供商还是网络运营商，都倾向于在网络内部署泛在的缓存系统来降低网络流量、提高用户体验。\n[0003] 但是，现在的内容在缓存中以URL为标识，而同样的内容在不同的内容提供商处会采用不同的URL标识，导致缓存节点依据URL难以识别实际内容相同的对象，从而会在缓存中重复存储，导致了缓存利用率的低下。因此，在泛在缓存缓存的前提下，亟需提出一种分布式缓存环境下避免缓存内容重复存储的方法。\n发明内容\n[0004] 本发明为解决上述技术问题，提供一种分布式缓存协同中避免内容重复存储的方法和装置，能有效地避免内容的重复存储、降低网络流量、提高用户体验。所述技术方案如下：\n[0005] 一方面，本发明提出了一种分布式缓存协同中避免内容重复存储的方法，所述方法包括：\n[0006] 采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识；\n[0007] 基于二元标识建立两级逻辑映射来组织缓存内容，并以分布式哈希进行缓存协同。其中第一级映射ψ建立提供商依赖标识和提供商独立标识之间的映射关系，第二级映射ω建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射表项还记录了ψ的逆映射关系ψ-1，ψ-1(PI(id)＝{PA(id)|ψ(PA(id)＝PI(id))},即对于所给定表项的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提供商独立标识；\n[0008] 由网络域的边缘内容路由器将从域外到达的请求经过两级路由转发到负责存储该内容的域内节点；\n[0009] 负责内容数据块的节点将对应的数据块发送给边缘内容路由器；\n[0010] 更新两级逻辑映射对应表项的缓存替换控制状态信息；\n[0011] 由网络域的边缘内容路由器在收到某个内容数据块时做出是否要缓存所述内容数据块的决定；\n[0012] 当需要缓存所述内容数据块时，所述边缘内容路由器将内容数据块经过两级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的二级映射关系。\n[0013] 进一步地，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数据块在不同的内容提供商可能具有不同的标识；\n[0014] 进一步地，所述提供商独立的标识指内容的标识与提供商无关，因此同样的内容数据块具有相同的内容标识；\n[0015] 进一步地，所述的内容请求包含对所请求内容数据块的提供商依赖标识；\n[0016] 进一步地，所述由网络域的边缘内容路由器Re将从域外到达的请求Q经过两级路由转发到负责存储该内容的域内节点，包括：\n[0017] 步骤201：对所述请求Q的提供商依赖标识PAQ(id)执行第一变换操作，将其变换为分布式哈希空间中的一个可路由标识ID1；\n[0018] 步骤202：将所述的对提供商依赖标识PAQ(id)执行第一变换操作后的ID1作为分布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节点N1；\n[0019] 步骤203：以请求中的提供商依赖标识PAQ(id)作为键值查询该负责节点N1的一级映射表MT1；\n[0020] 步骤204-1：若未找到对应表项，则向所述边缘内容路由器Re发送一级映射表项不存在的消息，结束流程；\n[0021] 步骤204-2：若找到对应的表项，则取得对应的提供商独立标识PIQ(id)＝MT1(PAQ(id))；\n[0022] 步骤205：对所述的提供商独立标识PIQ(id)执行第二变换操作，将其变换为分布式哈希空间中的一个可路由标识ID2；\n[0023] 步骤206：将提供商独立标识PIQ(id)作为请求的一个属性包含在请求中，同时以所述的对提供商独立标识执行第二变换操作后的ID2作为分布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节点N2；\n[0024] 步骤207：以请求中的提供商独立标识PIQ(id)作为键值查询该负责节点N2的二级映射表MT2；\n[0025] 步骤208-1：若未找到对应表项，则向所述边缘内容路由器Re发送二级映射表项不存在的消息，同时请求删除对应的一级映射表项MT1(PAQ(id))，结束流程；\n[0026] 步骤208-2：若找到对应的表项，则取得与提供商独立标识PIQ(id)关联的缓存数据 块；\n[0027] 其中，所述的第一变换操作和第二变换操作可以是相同的变换操作，也可以是不相同的变换操作；所述第二变换操作也可以是恒等变换。\n[0028] 其中，所述请求删除对应的一级映射表项MT1(PAQ(id))，由N2构造一级映射表项删除消息，所述删除消息包括待删除表项的键值PAQ(id)。以对PAQ(id)执行第一变换操作后的ID1作为路由目标，由N2依据底层的分布式哈希路由机制将所述一级映射表项删除消息路由到所述负责该一级映射表项的节点N1,并由N1执行相应的删除操作；\n[0029] 进一步地，所述更新两级逻辑映射对应表项的缓存替换状态控制信息，包括：更新对应二级映射表项MT2(PIQ(id))和一级映射表项MT1(PAQ(id))的缓存替换状态控制信息；\n[0030] 其中，所述更新对应二级映射表项MT2(PIQ(id))的缓存替换状态控制信息，由所述节点N2本地完成更新PIQ(id)键值对应的表项；\n[0031] 其中，所述更新对应一级映射表项MT1(PAQ(id))的缓存替换状态控制信息，由N2构造缓存替换状态控制消息，所述消息包括待更新表项的键值PAQ(id)和更新操作。以对PAQ(id)执行第一变换操作后的ID1作为路由目标，由N2依据底层的分布式哈希路由机制将所述一级映射表项更新消息路由到所述负责该一级映射表项的节点N1,并由N1执行相应的更新操作；\n[0032] 进一步地，所述边缘内容路由器将内容数据块D经过两级路由转发到负责存储该内容的域内节点，并建立对应的两级映射关系，包括：\n[0033] 步骤301：对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其变换为分布式哈希空间中的一个可路由标识ID3；\n[0034] 步骤302：将所述的对提供商依赖标识PAD(id)执行第一变换操作后的ID3作为分布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节点N3；\n[0035] 步骤303：以内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点N3的一级映射表MT1；\n[0036] 步骤304-1：若未找到对应表项，则在N3建立一级映射表项MT1(PAD(id))＝PID(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PID(id)为内容数据块的提供商独立标识，可以存储在内容数据块本身并随之在网络中传输，也可以由节点对内容数据块依据某种一致的算法计算而得；\n[0037] 步骤304-2：若找到对应的表项，则停止转发，结束流程；\n[0038] 步骤305：对所述的提供商独立标识PID(id)执行第二变换操作，将其变换为分布式哈希空间中的一个可路由标识ID4；\n[0039] 步骤306：以所述的对提供商独立标识执行第二变换操作后的ID4作为分布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节点N4；\n[0040] 步骤307：以内容数据块的提供商独立标识PID(id)作为键值查询该负责节点N4的二级映射表MT2；\n[0041] 步骤308-1：若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加键值PID(id)与内容数据块D的映射关系，初始化PID(id)和提供商依赖标识的逆映射集合为{PAD(id)}，初始化对应表项的缓存替换状态控制信息；\n[0042] 步骤308-2：若找到对应的表项，则在PID(id)和提供商依赖标识的逆映射集合中添加PAD(id)，结束流程；\n[0043] 其中，所述在N3建立一级映射表项MT1(PAD(id))＝PID(id)时，若表项已满，则N3依据第一预设规则选取某个一级映射表项进行替换；\n[0044] 假设被替换的一级映射表项为MT1(PAR(id))＝PIR(id),N3构造一级映射表项删除消息，以对PIR(id)执行第二变换操作后得到的ID5作为路由目标，将所述一级映射表项删除消息路由到负责PIR(id)二级映射的节点N5,N5以键值PIR(id)查询二级映射表项对应的逆映射集合ψ-1(PIR(id))，并执行ψ-1(PIR(id))＝ψ-1(PIR(id))-{PAR(id)}操作，若该操作执行后ψ-1(PIR(id))＝φ，即为空集，则删除二级映射表项MT2(PIR(id))及对应的内容数据块。\n[0045] 其中，所述在二级映射表项中增加键值PID(id)与内容数据块D的映射关系，若缓存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；\n[0046] 假设被替换的二级映射表项为MT2(PIR(id))＝D,则N4构造二级映射表项删除通告消息，对于 对PA(id)执行第一变换操作，并以对PA(id)执行第一变\n换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负责PA(id)的节点，由所述节点删除以PA(id)为键值的一级映射表项。\n[0047] 其中，所述第一预设规则和第二预设规则可以采用相同的规则，也可以采用不同的规则。\n[0048] 另一方面，本发明提出一种分布式缓存协同中避免内容重复存储的内容路由器装置，包括：分布式哈希维持模块、路由转发模块、一级映射表、二级映射表、内容块缓存库、一级映射表替换模块、二级映射表替换模块、第一变换模块、第二变换模块。可选地，内容路由 器装置还可以包含一个提供商独立标识生成模块。\n[0049] 其中，所述分布式哈希维持模块用于维持分布式哈希路由表；所述路由转发模块用于依据消息的分布式哈希路由标识和分布式哈希路由表对消息进行路由转发；所述一级映射表用于存储内容的提供商依赖标识和提供商独立标识的映射关系；所述二级映射表用户存储内容的提供商独立标识和内容数据块的映射关系，同时存储所述的提供商独立标识对应的一级映射的逆映射；所述内容块缓存库用于缓存实际的内容数据块；所述一级映射表替换模块用于根据预设的第一替换策略选择合适的一级映射表项予以替换；所述二级映射表替换模块用于根据预设的第二替换策略选择合适的二级映射表项予以替换，并从内容块缓存库中删除对应的内容数据块；所述第一变换模块用于对内容的提供商依赖标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识；所述第二变换模块用于对内容的提供商独立标识执行变换操作，生成分布式哈希路由空间中的一个可路由标识。所述提供商独立标识生成模块可以基于内容数据块生成仅与内容数据相关的提供商独立标识。\n[0050] 本发明采用以上技术方案与现有技术相比，具有以下技术效果：\n[0051] 通过在域内实现基于二级映射的分布式缓存协同,能有效地避免相同内容的重复存储，降低网络域间流量，提升用户体验。\n附图说明\n[0052] 图1示出了依据本发明一实施方式的分布式缓存域对内容请求的处理流程；\n[0053] 图2示出了依据本发明一实施方式的分布式缓存域对到达的内容数据块的处理流程；\n[0054] 图3示出了依据本发明一实施方式的对内容请求的两级映射和路由示意图。\n[0055] 图4示出了依据本发明一实施方式的对数据块的两级映射和路由示意图。\n具体实施方式\n[0056] 本实施例公开了一种基于分布式缓存协同中避免内容重复存储的方法，包括下述步骤：\n[0057] S101.采用提供商依赖标识和提供商独立标识的二元标识法对内容进行标识。其中，所述提供商依赖标识指内容的标识与提供商相关，因此同样的内容数据块在不同的内容提供商可能具有不同的标识，例如URL标识；所述提供商独立的标识指内容的标识与提供商无关，因此同样的内容数据块具有相同的内容标识，例如可以采用MD2、MD4、MD5和SHA-1等现有的哈希算法对内容数据块执行哈希操作，得到的哈希摘要可以作为提供商独立标识。\n[0058] S102.基于内容的二元标识建立两级逻辑映射来组织缓存内容，并以分布式哈希进行缓存协同。其中第一级映射ψ建立提供商依赖标识和提供商独立标识之间的映射关系，第二级 映射ω建立提供商独立标识和内容数据块本身的映射关系，其中第二级映射表项还记录了ψ的逆映射关系ψ-1，ψ-1(PI(id)＝{PA(id)|ψ(PA(id)＝PI(id))},即对于所给定表项的提供商独立标识PI(id)，当前哪些提供商依赖标识PA(id)映射到该提供商独立标识。\n[0059] S103.当边缘内容路由器从域外接收到对某个内容数据块的请求时，将请求经过两级路由转发到负责存储该内容的域内节点，由负责对应内容数据块的节点将数据块发送给边缘内容路由器，同时通知更新两级映射对应表项的缓存替换控制状态信息。\n[0060] S104.当边缘内容路由器从域外接收到某个内容数据块时，将内容数据块经过两级路由转发到负责存储该内容的域内内容路由节点，并在路由转发过程中建立对应的两级映射关系。\n[0061] 图1给出了所述步骤S103的请求在域内进行转发处理的流程图，包括：\n[0062] 步骤201：对所述请求Q的提供商依赖标识PAQ(id)执行第一变换操作，将其变换为分布式哈希空间中的一个可路由标识ID1；\n[0063] 步骤202：将所述的对提供商依赖标识PAQ(id)执行第一变换操作后的ID1作为分布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节点N1；\n[0064] 步骤203：以请求中的提供商依赖标识PAQ(id)作为键值查询该负责节点N1的一级映射表MT1；\n[0065] 步骤204-1：若未找到对应表项，则向所述边缘内容路由器Re发送一级映射表项不存在的消息，结束流程；\n[0066] 步骤204-2：若找到对应的表项，则取得对应的提供商独立标识PIQ(id)＝MT1(PAQ(id))；\n[0067] 步骤205：对所述的提供商独立标识PIQ(id)执行第二变换操作，将其变换为分布式哈希空间中的一个可路由标识ID2；\n[0068] 步骤206：将提供商独立标识PIQ(id)作为请求的一个属性包含在请求中，同时以所述的对提供商独立标识执行第二变换操作后的ID2作为分布式哈希的路由目标，由底层的分布式哈希路由机制将请求路由到对应的负责该ID的节点N2；\n[0069] 步骤207：以请求中的提供商独立标识PIQ(id)作为键值查询该负责节点N2的二级映射表MT2；\n[0070] 步骤208-1：若未找到对应表项，则由于二级映射表项不存在必然导致对应的一级映射表项无效，因此需向所述边缘内容路由器Re发送二级映射表项不存在的消息，请求删除对应的一级映射表项MT1(PAQ(id))，结束流程。具体地，所述删除过程如下：首先由N2构造一级映射表项删除消息，所述删除消息包括待删除表项的键值PAQ(id)，然后，N2以对PAQ(id) 执行第一变换操作后的ID1作为路由目标，依据底层的分布式哈希路由机制将所述一级映射表项删除消息路由到所述负责该一级映射表项的节点N1,最后由N1执行相应的删除操作。\n[0071] 步骤208-2：若找到对应的表项，则取得与提供商独立标识PIQ(id)关联的缓存数据块；\n[0072] 步骤209：负责内容数据块的节点根据数据块构造响应报文，并将响应报文发送给边缘内容路由器；\n[0073] 步骤210：更新两级逻辑映射对应表项的缓存替换控制状态信息，包括更新对应二级映射表项MT2(PIQ(id))和一级映射表项MT1(PAQ(id))的缓存替换状态控制信息。缓存替换所需的具体状态控制信息依赖于所采用的缓存替换算法，例如LRU替换算法需要内容的最近访问时刻，而LFU替换算法则需要内容的访问频次。更新对应二级映射表项MT2(PIQ(id))的缓存替换状态控制信息，由所述节点N2本地完成更新PIQ(id)键值对应的表项；而所述更新对应一级映射表项MT1(PAQ(id))的缓存替换状态控制信息，应由对应的一级映射节点N1完成。具体地，首先由N2构造缓存替换状态控制消息，所述消息包括待更新表项的键值PAQ(id)和更新操作，然后，N2以对PAQ(id)执行第一变换操作后的ID1作为路由目标,依据底层的分布式哈希路由机制将所述一级映射表项更新消息路由到所述负责该一级映射表项的节点N1,最后，由N1执行相应的更新操作。所述的更新操作可以包括更新内容的访问时间、更新内容的访问频次等。\n[0074] 图2给出了所述步骤S104的内容数据块D到达后在域内进行缓存处理的流程图，包括：\n[0075] 步骤301：对所述内容数据块的提供商依赖标识PAD(id)执行第一变换操作，将其变换为分布式哈希空间中的一个可路由标识ID3；\n[0076] 步骤302：将所述的对提供商依赖标识PAD(id)执行第一变换操作后的ID3作为分布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节点N3；\n[0077] 步骤303：以内容数据块中的提供商依赖标识PAD(id)作为键值查询该负责节点N3的一级映射表MT1；\n[0078] 步骤304-1：若未找到对应表项，则在N3建立一级映射表项MT1(PAD(id))＝PID(id)，并初始化所述表项的缓存替换状态控制信息。其中，所述PID(id)为内容数据块的提供商独立标识，可以存储在内容数据块本身并随之在网络中传输，也可以由节点对内容数据块依据某种一致的算法计算而得；\n[0079] 步骤304-2：若找到对应的表项，则停止转发，结束流程；\n[0080] 步骤305：对所述的提供商独立标识PID(id)执行第二变换操作，将其变换为分布式 哈希空间中的一个可路由标识ID4；\n[0081] 步骤306：以所述的对提供商独立标识执行第二变换操作后的ID4作为分布式哈希的路由目标，由底层的分布式哈希路由机制将内容数据块路由到对应的负责该ID的节点N4；\n[0082] 步骤307：以内容数据块的提供商独立标识PID(id)作为键值查询该负责节点N4的二级映射表MT2；\n[0083] 步骤308-1：若未找到对应表项，则缓存内容数据块D，并在二级映射表项中增加键值PID(id)与内容数据块D的映射关系，初始化PID(id)和提供商依赖标识的逆映射集合为{PAD(id)}，初始化对应表项的缓存替换状态控制信息；\n[0084] 步骤308-2：若找到对应的表项，则在PID(id)和提供商依赖标识的逆映射集合中添加PAD(id)，结束流程；\n[0085] 其中，所述在N3建立一级映射表项MT1(PAD(id))＝PID(id)时，若表项已满，则N3依据第一预设规则选取某个一级映射表项进行替换；\n[0086] 假设被替换的一级映射表项为MT1(PAR(id))＝PIR(id),N3构造一级映射表项删除消息，以对PIR(id)执行第二变换操作后得到的ID5作为路由目标，将所述一级映射表项删除消息路由到负责PIR(id)二级映射的节点N5,N5以键值PIR(id)查询二级映射表项对应的逆映射集合ψ-1(PIR(id))，并执行ψ-1(PIR(id))＝ψ-1(PIR(id))-{PAR(id)}操作，若该操作执行-1\n后ψ (PIR(id))＝φ，即为空集，则删除二级映射表项MT2(PIR(id))及对应的内容数据块。\n[0087] 其中，所述在二级映射表项中增加键值PID(id)与内容数据块D的映射关系，若缓存空间已满，或表项已满，则N4依据第二预设规则选取某个二级映射表项进行替换；\n[0088] 假设被替换的二级映射表项为MT2(PIR(id))＝D,则N4构造二级映射表项删除通告消息，对于 对PA(id)执行第一变换操作，并以对PA(id)执行第一变\n换操作后得到的ID为路由目标，将所述二级映射表项删除通告消息路由到对应的负责PA(id)的节点，由所述节点删除以PA(id)为键值的一级映射表项。\n[0089] 其中，所述第一预设规则和第二预设规则可以采用相同的规则，也可以采用不同的规则，例如第一预设规则和第二预设规则可以采用LRU、LFU、随机替换等多种缓存替换策略。\n[0090] 图3给出了依据本发明一实施例的分布式缓存协同中的对内容请求的两级映射和请求处理过程示意图。图3中，n1-n8这8个域内节点逻辑上构成了一个分布式哈希空间，例如可以采用Chord，Pastry等现有的分布式哈希算法，并由各自节点的分布式哈希维持模块维护哈希路由表。在本实施例中，哈希路由的标识空间为32比特的二进制整数。当某个边缘内容 路由器,如n8接收到了一个对提供商依赖标识为http://example1.com/a的请求后，首先对该标识进行第一变换，将其变换分布式哈希路由空间中的一个可路由标识，接着根据底层的哈希路由将该请求转发到负责该提供商依赖标识一级映射的节点n1。n1查询自身的一级映射表后，得出对应的提供商独立标识为5E754D34。在本实施例中，提供商独立标识空间和哈希路由标识空间是一致的，因此，无需实施第二变换。n2依据底层的哈希路由将该请求路由转发到负责该提供商独立标识的节点n4。n4查询二级映射表，找到对应的内容数据块1，构造响应消息，返回给节点n8。同时，n4还需要更新自身的缓存替换状态控制信息，并构造缓存替换状态控制消息发送给对应的一级映射节点n1。\n[0091] 图4示出了依据本发明一实施例的分布式缓存协同中对数据块的两级映射和路由示意图。图4(a)表示初始状态，即分别有两个提供商依赖的标识http://example1.com/a和http://example2.com/b映射到同一个提供商独立的标识5E754D34。当某个边缘内容路由器接收到提供商依赖标识PA(id)＝http://example3.com/foo，PI(id)＝5E754D34的内容数据块时，首先对提供商依赖标识进行第一变换操作，将其变换成一个与哈希路由空间一致的标识，然后依据底层哈希路由将该数据块路由到负责该标识的节点n8。在本例中，由于n8并不存在对应的一级映射表项，因此建立对应的一级映射表项。此后，依据提供商独立标识，将该数据块路由到对应的二级映射节点n4。n4查找后发现该内容已经在该节点缓存，因此将提供商依赖的标识http://eaxmple3.com/foo添加到与该提供商独立标识5E754D34关联的提供商依赖标识集中，如图4(b)所示。\n[0092] 假设在图4(b)的状态下，由于某个数据块的到达导致n4决定替换键值为5E754D34的二级映射表项，则，对于每个与5E754D34关联的提供商依赖标识集合中的提供商依赖标识，n4执行第一变换操作，并以变换后的可路由标识为路由目标，将二级映射表项删除通告消息发送给对应的节点。在本例中，n4需要将二级映射表项删除通告消息发送给n1,n7,n8。\n当n1,n7,n8接收到上述消息后，删除对应的一级映射表项，如图4(c)所示。