用于发布订阅系统的实现历史事件订阅的缓存方法

摘要

本发明公开了一种用于发布订阅系统的实现历史事件订阅的缓存方法，包括如下步骤：路由表扩充步骤，在路由表中增设缓存路由信息；事件处理步骤，通过哈希函数计算缓存点参考值；事件发布步骤：根据缓存点参考值判断当前代理节点是否作为缓存点并进行缓存，同步更新缓存路由信息；缓存订阅步骤；以及缓存获取步骤。本发明具有以下有益效果：本发明提供的缓存方法实现了订阅者对历史事件的订阅；本发明充分利用了事件分发路径上所有代理及其邻居代理的存储空间，提高了存储资源利用率，增强了发布订阅系统的缓存能力；本发明对缓存冗余做了精简，在访存效率与存储占用率之间做了平衡。

说明书

技术领域

本发明涉及发布订阅系统技术，具体涉及一种实现历史事件订阅的缓存方法。

背景技术

发布订阅系统包含一个分布式的通信网络，即事件代理网络，和一系列相互通信的端点，即订阅者和发布者。订阅者和发布者之间通过事件代理网络互联，采用一种异步的发布-订阅方式来完成数据交换。订阅者通过声明一个过滤条件表达式提交订阅，当发布者发布了一条符合其订阅条件的事件，该事件即经由代理网络路由到订阅者。在时间上，内容的订阅与发布是异步的，而在空间上，订阅者与发布者也不必关心对方位于何处，因此发布订阅系统实现了通信双方在空间、时间和控制流上完全解耦。

在传统的发布订阅系统中，事件通知能够确保最终到达每个感兴趣的订阅者，但前提是每个订阅者都处于在线状态且各自的订阅被整个系统所知。这一前提条件对于动态网络环境来说则是一大限制，因为客户端往往会频繁地加入或离开网络，新加入的订阅者可能会请求一个在其加入网络之前所发布的事件。在传统的发布订阅系统中，这种请求是得不到响应的，因而如何利用事件缓存机制以使新用户能够获知历史事件就成为了发布订阅系统需要解决的一大问题。

发明内容

为了克服现有技术中存在的订阅者无法订阅历史事件的缺陷，本发明提供一种实现历史事件订阅的缓存方法。本发明具体的技术方案如下：

一种用于发布订阅系统的实现历史事件订阅的缓存方法，包括如下步骤：

路由表扩充步骤：在各代理节点的路由表中增设缓存路由信息，所述缓存路由信息用于提供能够定位到缓存点的路由信息；

事件处理步骤：当某一代理节点发出一事件时，通过哈希函数进行计算，得到一缓存点参考值；为所述事件附加一消息头，所述消息头中记录了缓存点信息以及订阅路径信息；所述缓存点信息中包括所述缓存点参考值；

事件发布步骤：根据所述消息头中记录的订阅路径信息，将所述事件向对应的订阅节点进行发布；对于发布路径中的每个代理节点，根据所述缓存点参考值判断当前代理节点是否作为缓存点并进行缓存，同时，当前代理节点同步更新对应于所述事件的缓存路由信息；

缓存订阅步骤：某一代理节点发出一缓存请求，所述缓存请求中包含订阅条件；将所述订阅条件与当前代理节点的路由表中预存的过滤条件进行匹配，确定缓存事件；所述缓存事件是指，与订阅条件匹配成功的过滤条件对应的事件；

缓存获取步骤：若当前代理节点的路由表中包含所述缓存事件对应的缓存路由信息，则直接根据该缓存路由信息找到所述缓存事件对应的缓存点，

将缓存请求转发到缓存点，获取缓存；若当前代理节点的路由表中不包含所述缓存事件对应的缓存路由信息，则根据所述缓存事件对应的订阅路由信息，将缓存请求发送到下一个代理节点，回转执行缓存获取步骤。

作为优化方案，所述哈希函数如公式（1）所示：

该哈希函数的定义域为事件e的取值范围(a，b)，值域为[0，MAX_HOP]；其中MAX_HOP是事件分发路径上的代理节点到其根节点的最大距离。

计算得到的缓存点参考值为一整数值。

作为优化方案，根据所述缓存点参考值判断当前代理节点是否作为缓存点并进行缓存具体为：

当前代理节点收到事件后先将所述缓存点参考值t减1，然后根据缓存点参考值进行判断，若t=0，则将当前代理节点做为缓存点。

作为优化方案，所述路由表扩充步骤具体为：

在各代理节点的路由表中增加cache_nexthops字段，使得所述路由表的结构为：

<filter|sub_nexthops|cache_nexthops>

其中，filter是指过滤条件，sub_nexthops记录了与filter匹配成功的事件向订阅节点方向转发的下一跳代理，cache_nexthops记录了与filter匹配成功的缓存请求向缓存点方向转发的下一跳代理。

作为优化方案，所述事件发布步骤中，对于事件在发布过程中的当前代理节点，其缓存路由信息的更新方法具体为：

若当前代理节点在缓存点的后方，则将缓存路由信息中的下一跳设置为前驱的代理节点；

若当前代理节点正好为缓存点，则将缓存路由信息中的下一跳设置为当前代理节点自身；

若当前代理节点在缓存点的前方，则将缓存路由信息中的下一跳设置为后继的代理节点。

作为优化方案，所述缓存获取步骤中，将缓存请求转发到缓存点获取缓存的方法具体为：

在缓存请求转发到缓存点的过程中依次记录沿途经过的代理节点，记为缓存请求路径；缓存请求到达缓存点后，缓存点将请求的缓存沿缓存请求路径的逆序发送给发出缓存请求的代理节点。

作为优化方案，所述事件发布步骤中，若当前代理节点作为缓存点并进行缓存时，进行判断：若当前代理节点的存储空间耗尽，则询问该事件发布路径之外的直接邻居是否尚有可用存储空间；若该邻居有可用存储空间，则将事件转发给该邻居进行缓存。

作为优化方案，所述缓存点信息还包括缓存点位置、缓存副本数目以及缓存时间戳，所述缓存点位置、缓存副本数目以及缓存时间戳的初值均为空；对于发布路径中的每个代理节点，若当前代理节点作为缓存点并进行缓存时，更新事件的消息头中记录的缓存点位置、缓存副本数目以及缓存时间戳，同时更新当前代理节点内存储的缓存点位置、缓存副本数目以及缓存时间戳。

作为优化方案，在事件在发布过程中，沿途比较各代理节点的缓存时间戳，获得最旧缓存的位置，当事件抵达订阅节点时，若整条发布路径上的存储空间耗尽，则转回至最旧缓存的位置替换最旧的缓存。

作为优化方案，所述事件发布步骤中，对于每个代理节点，采用冗余精简方法对事件进行缓存，所述冗余精简方法具体为：

设代理节点为b_i，其包含若干子节点b_ij，设g_ij为每个子节点b_ij对应的子树；根据目标函数确定将缓存的副本分派到缓存点的哪些子树，如公式（2）所示：

其中，d_ij表示代理节点b_i距离子树g_ij末端用户的最大距离，r_ij表示代理节点b_i接收到来自子树g_ij的用户请求总数，s_ij表示子树g_ij中所有节点总的存储空闲率，t为缓存点参考值；目标函数的分子表示将事件的一个副本放置在子树g_ij上时，用户获取该副本的总开销；其中，分子的第一项为子树g_ij末端的用户请求该副本时的开销，分子的第二项则表示其余子树(g_i-g_ij)上的用户请求该副本时的总开销；

代理节点b_i为每个子节点b_ij各计算一个目标选择其值最小的m=min(k,n_i)棵子树g_i1,g_i2,...,g_im分派副本，并相应地将发往子节点b_i1,b_i2,...,b_im的事件的副本数目k根据公式（3）进行修改：

将发往其他子节点b_ij的事件的副本数目k设为k_l=0(m＜l≤n_i)，相应的t值归0。

与现有技术相比，本发明具有以下有益效果：

（1）本发明提供的缓存方法实现了订阅者对历史事件的订阅；

（2）本发明充分利用了事件分发路径上所有代理及其邻居代理的存储空间，提高了存储资源利用率，增强了发布订阅系统的缓存能力；

（3）本发明对缓存冗余做了精简，在访存效率与存储占用率之间做了平衡。

附图说明

图1为本发明提供的缓存方法的总流程图；

图2为实施例1中发布订阅系统的网络示意图。

具体实施方式

下面结合附图以实施例的方式详细描述本发明。

实施例1：

如图1所示，一种用于发布订阅系统的实现历史事件订阅的缓存方法，包括如下步骤：

步骤S1，路由表扩充步骤：在各代理节点的路由表中增设缓存路由信息，所述缓存路由信息用于提供能够定位到缓存点的路由信息。

传统的发布订阅系统中，各代理节点的路由表中已包含订阅路由信息，用于定位到事件对应的订阅者；为了使发布订阅系统支持缓存，在此基础上，增设缓存路由信息，对路由表进行扩展。

现有的路由表结构为<filter|sub_nexthops>，其中filter是过滤条件，sub_nexthops则记录了与filter匹配成功的事件向订阅节点方向转发的下一跳代理节点；该sub_nexthops字段即对应于订阅路由信息。

在现有的路由表结构中增加cache_nexthops字段，使得所述路由表的结构为：

<filter|sub_nexthops|cache_nexthops>

其中，cache_nexthops记录了与filter匹配成功的缓存请求向缓存点方向转发的下一跳代理，该cache_nexthops字段即对应于缓存路由信息。该cache_nexthops字段在事件发布过程中沿分发路径逐跳构造，作用是为用户的缓存请求提供路由信息，使其能够找到缓存点，正如sub_nexthops帮助事件找到订阅者一样。

步骤S2，事件处理步骤：当某一代理节点发出一事件时，通过哈希函数进行计算，得到一缓存点参考值；为所述事件附加一消息头，所述消息头中记录了缓存点信息以及订阅路径信息；所述缓存点信息中包括所述缓存点参考值。

本步骤是发布者向订阅者发送事件之前，为了实现缓存而进行的处理。假设事件e的取值范围为e.value∈(a，b)，发布者通过以下哈希函数来决定将事件缓存在路径上的哪些节点，如公式（1）所示：

其中，该哈希函数的定义域即为事件e取值范围(a，b)，值域则是[0，MAX_HOP]，其中MAX_HOP是事件分发路径上的代理节点到其根节点的最大距离（可通过事先发送探索消息获得），以跳数计。当事件e不存在分发路径时，它被映射到第0跳，即根节点。

计算得到缓存点参考值，该缓存点参考值为一整数值。哈希映射的结果即得到的缓存点参考值并非缓存点的代理标识符，而是一个类似减法计数器的跳数变量t，记录的是该事件的缓存点与当前代理节点的距离。进行哈希运算之后，并不能立刻确定哪个代理节点是缓存点，需要在事件发布过程中，由发布路径上的各代理节点根据缓存点参考值确定自身是否做为缓存点。将计算出的缓存点参考值记录在事件的消息头中，随事件一起发布。订阅路径信息记录了事件从发布者发送到订阅者所要经过的路径信息。

步骤S3，事件发布步骤：根据所述消息头中记录的订阅路径信息，将所述事件向对应的订阅节点进行发布；对于发布路径中的每个代理节点，根据所述缓存点参考值判断当前代理节点是否作为缓存点并进行缓存，同时，当前代理节点同步更新对应于所述事件的缓存路由信息。

在本步骤中，根据缓存点参考值判断当前代理节点是否作为缓存点并进行缓存具体为：

当前代理节点收到事件后先将缓存点参考值t减1，然后根据其值进行判断，若t=0，则当前代理节点即做为缓存点。

在进行缓存时，有可能当前代理节点会出现存储空间已满的情况，为了充分利用网络中的存储空间，在进行缓存之前，进行如下判断：若当前代理节点的存储空间耗尽，则询问该事件发布路径之外的直接邻居是否尚有可用存储空间；若该邻居有可用存储空间，则将事件转发给该邻居进行缓存。采用此方法可以提高整个系统的存储空间的利用率。

当前代理节点在完成缓存点判断之后，需要同步更新当前代理节点的路由表中该事件对应的缓存路由信息。缓存路由信息的更新方法具体为，包括三种情况：并相应构造缓存路由：

情况一：若t＜0，即事件的转发已经过缓存点，当前代理节点位于缓存点的下游，则将缓存路由信息中的下一跳设置为前驱的代理节点；

情况二：若t＝0，即当前代理节点正好为缓存点，则将缓存路由信息中的下一跳设置为当前代理节点自身；

情况三：若t＞0，即事件的转发还未到达缓存点，当前代理节点在缓存点的前方，则将缓存路由信息中的下一跳设置为后继的代理节点。

在事件发布过程中的每一个代理节点都进行上述缓存点的判断和缓存路由信息更新的操作。当事件发送到订阅者时，所有的缓存点均已确定并进行缓存，发布路径中的所有代理节点均已更新缓存路由信息。

步骤S4，缓存订阅步骤：某一代理节点发出一缓存请求，所述缓存请求中包含订阅条件；将所述订阅条件与当前代理节点的路由表中预存的过滤条件进行匹配，确定缓存事件；所述缓存事件是指，与订阅条件匹配成功的过滤条件对应的事件。

在本步骤中，当订阅者接入发布订阅系统后，若要对历史事件进行订阅，即是要从缓存的事件中订阅所需的内容。类似于订阅事件时发送的订阅请求，订阅缓存时通过发送一缓存请求实现。设缓存请求为Request(Δf)，其中的Δf为订阅条件。

步骤S5，缓存获取步骤：若当前代理节点的路由表中包含所述缓存事件对应的缓存路由信息，则直接根据该缓存路由信息找到所述缓存事件对应的缓存点，将缓存请求转发到缓存点，获取缓存；若当前代理节点的路由表中不包含所述缓存事件对应的缓存路由信息，则根据所述缓存事件对应的订阅路由信息，将缓存请求发送到下一个代理节点，回转执行缓存获取步骤。

具体地说，在本步骤中，获取缓存包括两种情况：

（1）路由表中包含缓存事件对应的缓存路由信息，即订阅历史事件的用户出现在其兴趣事件的分发路径上。这时缓存请求可以直接依据cache_nexthops找到事件缓存点。在缓存请求逐跳转发到缓存点的过程中依次记录沿途经过的代理节点，记为缓存请求路径；缓存请求到达缓存点后，缓存点将请求的缓存沿缓存请求路径的逆序发送给发出缓存请求的代理节点。

（2）路由表中不包含缓存事件对应的缓存路由信息，即订阅历史事件的用户不在其兴趣事件的分发路径上。根据缓存事件对应的sub_nexthops，将缓存请求发送到下一个代理节点。下一个代理节点重复上述操作，直至找到事件缓存点。

下面举一个实例对本实施例提供的缓存方法进行详细的说明，图2给出了发布订阅系统的网络示意图，其中，A～E代表5个代理节点，P代表发布者所在的代理节点，S₁代表用户（订阅者）所在的代理节点。

假设用户S₁的过滤条件是f₁，发布者P发布了一条符合过滤条件f₁的事件e₁并选择代理D作为缓存点，e₁携此缓存点信息沿分发路径A→B→D→E由发布者向订阅者逐跳匹配转发。代理A将事件与f₁匹配成功，读取事件消息头中的缓存点信息并发现其缓存点位于自己下游，于是将匹配成功的订阅路由下一跳节点（代理B）添加至cache_nexthops字段，表明将来接收到的缓存查找请求会转发给B。B也会进行类似的操作并将后继节点D作为缓存查找的下一跳。D接收到事件后发现自己被选为缓存点，则将事件存储于本地并将自己添加至缓存路由下一跳。代理E则根据事件消息头中的缓存点信息得知e₁被缓存在了事件分发路径中的上游，于是将前趋节点D作为缓存路由下一跳。从而逐跳完成了缓存路由信息的构造。

假设一个新用户S₂连接到代理E并请求事件e₁，由于新用户S₂出现在事件e₁的发布路径上，E查找路由表并与f₁匹配成功后，根据cache_nexthops将请求转发给缓存下一跳（代理D），从而找到事件缓存，即是步骤S5中提到的第（1）种情况。

倘若S₂出现在代理C处，由于新用户S₂不在事件e₁的发布路径上，C匹配成功的f₁表项中不存在缓存路由信息（NIL），这时它会根据sub_nexthops将缓存请求向订阅者方向转发，即转发给代理B，而B恰好处于e₁的分发路径上，可以根据缓存路由cache_nexthops将请求转发给D，这样最终也找到了缓存，即是步骤S5中提到的第（2）种情况。Request消息转发过程中会依次记录沿途所经节点的ID，用户的缓存请求最终到达代理D时，其中包含了一条节点链路：S₂→C→B，即缓存请求路径。代理D将用户所请求的事件内容和这条链路一起封装成响应消息Response(e₁，S₂→C→B)，沿链路的逆向回发给用户，完成缓存请求的响应。

实施例2：

本实施例与实施例1的区别在于，事件消息头中的缓存点信息还包括缓存点位置、缓存副本数目以及缓存时间戳，每个事件缓存对应一个缓存时间戳。

在事件发布之前，所述缓存点位置、缓存副本数目以及缓存时间戳的初值均为空。在事件发布过程中，对于发布路径中的每个代理节点，若当前代理节点作为缓存点并进行缓存时，更新事件的消息头中记录的缓存点位置、缓存副本数目以及缓存时间戳，同时更新当前代理节点内存储的缓存点位置、缓存副本数目以及缓存时间戳。

在实际应用中，有可能会出现发布订阅网络中的存储空间耗尽的情形，因此，此时需要删除一些旧的缓存，释放出存储空间提供给新的缓存。在本实施例中，具体采用如下方法：在事件在发布过程中，沿途比较各代理节点的缓存时间戳，获得最旧缓存的位置，当事件抵达订阅节点时，若整条发布路径上的存储空间耗尽，则转回至最旧缓存的位置替换最旧的缓存。

实施例3：

为了对缓存冗余进行精简，在访存效率与存储占用率之间进行平衡，本实施例在实施例1的基础上加入了缓存精简的方法，具体方法如下：

在事件发布步骤中，对于每个代理节点，采用冗余精简方法对事件进行缓存，所述冗余精简方法具体为：

令表示事件分发树中所有代理节点的集合，表示事件分发树中的一个代理节点，其中，表示节点b_i的所有子节点集合，其中，每个代理节点为包含若干子节点b_ij，g_ij为每个子节点所对应的一棵子树，其中j=1,2,...,n_i；表示n_i棵子树共同构成的b_i的子树集合。

根据目标函数确定将缓存的副本分派到缓存点的哪些子树，如公式（1）所示

其中，d_ij表示代理节点b_i距离子树g_ij末端用户的最大距离，r_ij表示代理节点b_i接收到来自子树g_ij的用户请求总数，s_ij表示子树g_ij中所有节点总的存储空闲率，t为缓存点参考值；目标函数的分子表示将事件的一个副本放置在子树g_ij上时，用户获取该副本的总开销；其中，分子的第一项为子树g_ij末端的用户请求该副本时的开销，分子的第二项则表示其余子树(g_i-g_ij)上的用户请求该副本时的总开销。

这里的距离d_ij-t和d_il+t只是一个近似值，每个代理节点无法得知子树的确切拓扑结构，故而近似认为每个用户到缓存点距离等同。缓存请求的总开销越小，或子树上总存储空间空闲率越大，则目标函数值越小。

代理节点b_i为每个子节点b_ij各计算一个目标选择其值最小的m=min{k,n_i}棵子树g_i1,g_i2,...,g_im分派副本，并相应地将发往子节点b_i1,b_i2,...,b_im的事件的副本数目k根据公式（2）进行修改：

将发往其他子节点b_il的事件的副本数目k设为k_l=0(m＜l≤n_i)，相应的t值归0。

每一个做为缓存点的代理节点都进行上述处理，从而由各代理节点分布式地完成缓存副本的存放。

以上公开的仅为本申请的一个具体实施例，但本申请并非局限于此任何本领域的技术人员能思之的变化，都应落在本申请的保护范围内。