面向社交网络密集图数据存储的缓存置换算法

王大伟 郑佳 杨岩

摘 要：为了缓解社交网络热点话题生成的密集图数据导致存储的频繁读取和缓存空间浪费等问题，针对话题产生与消亡的演化更新规律，提出了基于话题热度演化加速度的缓存置换算法（cache replacement algorithm based on topic heat evolution acceleration，THEA-CR）。该算法首先对社交网络数据进行话题簇的实体划分，识别锚定目标。其次，计算话题热度演化加速度，对热点数据的优先级进行研判；最后设计双队列缓存置换策略，针对话题关注度和访问频率进行缓存空间的置换和更新。在新浪微博数据集中与经典的缓存置换算法进行大量对比实验，验证了所提算法具有较好的可行性与有效性。结果表明提出的THEA-CR算法能够在社交网络密集图数据的不同图查询操作中平均提升约31.4%的缓存命中率，并且缩短了约27.1%的查询响应时间。

关键词：密集图数据； 话题演化加速度； 缓存置换； 空间利用率

中图分类号：TP391   文献标志码：A

文章编号：1001-3695（2023）09-010-2729-07

doi：10.19734/j.issn.1001-3695.2023.01.0008

Research on cache replacement algorithm for

social network intensive graph data storage

Wang Dawei， Zheng Jia， Yang Yan

（Institute of Scientific & Technical Information of China， Beijing 100038，China）

Abstract：In order to alleviate the problems of frequent I/O of storage and space waste caused by dense graph data generated by hot topics in social networks， this paper proposed a THEA-CR according to the evolution and update law of topic generation and death. Firstly， this algorithm divided the social network data into some topic clusters to identify anchor targets. Secondly， this paper calculated the topic heat evolution acceleration to evaluate and judge the priority of hot data. Finally， this paper designed a dual queue cache replacement strategy to replace and update the cache space according to topic concern and access frequency. Massive comparative experiments verify the feasibility and effectiveness of the proposed algorithm in Sina Weibo dataset with the baselines cache replacement algorithms. The results show that the proposed THEA-CR can improve the cache hit rate by about 31.4% on average and shorten the query response time by about 27.1% in different query operations of social network dense graph data.

Key words：dense graph data; topic evolution acceleration; cache replacement; space utilization

0 引言

近年来，图结构数据呈现爆炸式的增长，其作为计算机领域中的一类最为复杂的数据结构，能够抽象表示这些实体数据之间的关联性，可以适用于诸如社交网络［1］、知识图谱［2］、甚至生物蛋白结构等众多实际应用场景［3～6］。图数据中复杂的拓扑结构在有效展示关联关系的同时，会引起图数据组织、管理和存储的相关问题［7］。特别地，对于社交网络图数据，其通常出现由热点话题引发的结构聚簇现象，生成由大量重复的强关联实体组成的话题簇结构［8］，且社交互动产生频繁的磁盘读取操作更会严重影响图数据模型的空间利用率以及图计算的处理速度。因此，针对社交网络图数据的分割与存储，面对结构紧凑、复杂的图数据拓扑结构和数据时，如何在保证密集图数据局部性的前提下，减少磁盘交互并提高缓存命中率是图数据模型亟待解决的难题。

社交网络图数据往往存在一些具有大量邻居节点的聚焦节点［9～11］，作为热點数据受到了广泛的关注和评论，需要被频繁读取。因此，该类数据影响着图数据模型在图计算操作中迭代执行的速度［12，13］。同时，社交网络消息具有快速更新的特点，在一段时间内会有新的热点话题出现，并且用户所关注的热点会随着时间而发生变化。通常在迭代操作的整个周期内，第一轮迭代只有少数的节点参与了计算更新。在进一步的迭代中每个节点的邻居节点会依次加入到计算中来，因此参与计算的节点会逐渐增多。当计算中的数据节点达到一个峰值后，参与过计算的节点会慢慢从内存中被置换出去，即在整个的图计算过程中会有一个阶段的迭代轮次，只有较少一部分的节点参与了计算更新的操作。针对社交网络热点数据不断更新演化的特性和缓存空间对数据的管理方式，需要根据社交网络热点话题的使用时间与热度，对缓存空间进行有效的分配和置换，从而避免大量没有参与计算的节点数据加载导致的缓存污染现象，以及交互操作量的增加问题。本文提出针对话题关注度和访问频率的双队列缓存空间置换和更新策略，可以在缓存队列中长时间锚定某一热点话题，使其在某段时间内被频繁读取时，增加其在缓存空间的命中率，同时缩短查询响应时间。

在存储机制中，为了进一步提高缓存空间的利用率和数据的读取效率，需要对缓存空间内的数据进行筛选和淘汰，这有利于一段时间内被频繁调用的数据能够快速地加载到缓存中，并实现缓存空间的实时更新置换，从而进一步提高缓存空间的利用率和缓存空间数据查询操作的效率。目前，常用的缓存置换算法根据空间内数据的到达顺序以及数据使用时间、访问频率等因素，对缓存空间的内存进行分配管理，如随机算法（RND）、先进先出置换算法（first input first output，FIFO）、最少使用频率缓存置换算法（LFU）和最近最少使用缓存置换算法（LRU）等，其均具有简单、易实现的特点，从而被广泛应用。然而，由于社交网络消息的更新速度快，热点话题的传播范围广，导致现有的缓存置换算法出现缓存污染等问题。针对社交网络数据实时发布的特征，海量用户的传播和共享使数据具有不断热度更迭的性质。因此在不同的时间段内，受欢迎和频繁被读取的话题会随时间发生变化，即社交网络内的热点话题具有一定的传播热度和演化规律。如何对图数据中代表性的节点（热点话题）进行热度的评估，从而提高缓存空间的有效分配，是进一步提升社交网络图数据存储有效性的关键性问题。

綜上所述，大多数缓存淘汰算法和内存分配的相关研究没有根据数据本身的热度和演化规律进行分析，因此，需要对社交网络图数据的聚集性特点进行热度演化加速度的度量。根据社交网络数据更新的速度，对缓存空间数据的重要性进行评估，动态更新并置换存储数据，研究更为有效的、具有较高缓存命中率的缓存置换算法。因此，本文提出基于话题热度演化加速度的缓存置换算法THEA-CR，作为一种新的缓存置换策略，减轻了密集图结构在加载中的负担。首先，在整个数据集内识别THEA-CR算法在缓存空间内需要锚定的目标数据，并对其设置不同的优先级，以区别并减少不常使用、非热点数据对存储空间的占用；然后，由于空间聚类实体是由一个热点话题触发的数据节点，其在社交网络内将保持一段时间的关注热度，所以，提出话题热度演化加速度的定义，进一步对缓存空间的数据进行重要性和优先级的评估；最后，基于THEA-CR算法实现了缓存空间数据的迭代更新和有效置换，从而提升了缓存空间的命中率和图数据模型的处理速度。

本文主要贡献归纳如下：

a）通过对社交网络热点话题在网络传播中的特性，对话题簇进行实体划分，从而锚定缓存置换中的目标实体。

b）提出话题热度演化加速度，挖掘话题时间演化规律，对话题簇实体进行热度优先级比较，实现话题的热度研判。

c）设置双队列缓存置换策略，针对热点话题的关注度和访问频率进行缓存空间的置换和更新，从而将不被关注和失去热度的数据在缓存中进行淘汰，锚定新产生的热点话题，极大地提高了图数据存储机制的空间利用率。

d）实验结果表明，THEA-CR算法保证了缓存空间的更新速度，从而实现了对缓存空间的有效利用，提高了通用图操作中的缓存命中率，并加速了图数据模型的处理速度。

1 相关工作

缓存置换是通过一些优化的指令或者算法，使得计算程序或者一个持有硬件的结构能统一、有秩序的管理缓存信息［14～16］。其通常根据临时性、频率、重用距离、分类等性质将其分为粗粒度和细粒度两类。典型的缓存置换算法通常被广泛应用于数据库缓存、网络缓存和磁盘缓存等方面。现有的缓存置换算法包括RND、FIFO、LRU和LFU及其相应的改进算法。文献［17］提出了一种基于流行度的置换策略。文献［18］在此基础上进一步提出了一种RUF缓存置换策略。此外，文献［19］基于缓存置换率指标，设计了动态缓存借调方法，使处于繁忙的节点能够借调空闲节点的缓存资源。目前，结合LRU算法与流行度因素的新置换算法，主要应用于在内容中心网络集群节点间进行缓存置换，为单机数据管理中的缓存置换算法提供了新的思路。此外，典型的LRU和LFU算法均将近期用户频繁关注的内容尽可能地保留在缓存中，间接体现了内存空间对用户热度话题偏好的管理，并隐性地增加了高热度话题内容在内存中的锚定概率。社交网络图数据，由消息之间的频繁转发等交互操作而形成［6］。针对某一时间爆发的热点话题，会出现相关内容的重复讨论，进而导致数据在存储过程中被频繁读取。由于社交网络中的图数据具有高速更新的特点，所以适用于社交网络的置换策略应该具备阶段性置换的特点。针对密集图数据面临的困难，频繁的磁盘交互加上极低的磁盘访问效率，成为了图数据系统性能的瓶颈。为了降低从磁盘中载入数据对系统性能的影响，现有的处理方式通常分为以下两种：

a）采用分布式图处理技术，将完整的图数据一次性加载到内存中实现内存计算。为了使内存的容量能够达到计算需求，通常通过分布式的方式横向扩展内存的总容量，但这将引起巨额的硬件成本和复杂的管理操作。这种方案侧重于图结构数据的分区优化、负载均衡和图计算方法的并行化处理。

b）使用单机有限内存处理大规模图数据的方案，每次计算只将图数据的小部分加载到内存中，未使用的图数据保存在外存内。为了有效地将数据规模增大的弊端转移到外存容量上，通过纵向扩展的方式增大单个机器的内存容量以及优化图分割算法的处理方式来处理大规模的图数据。这种方案仅依赖于一台计算机就可以完成图计算的任务，同时避免了分布式计算的通信开销与硬件的成本开销，因此，更侧重于图数据访问过程中缓存置换算法的性能与效率优化的问题。

针对第二种方法，其关键点在于如何保证用于内存交互的子图状态的稳定性。该过程包含了图结构数据从外存加载到内存的操作、内存查找匹配与排序的操作，以及计算结果写回外存的操作。每一次的迭代过程均会包含上述操作，因此大量的I/O开销是该方法的瓶颈。选择合理的缓存策略，可以有效地减少磁盘读取的频率从而提升系统性能，而科学的缓存置换算法则可以影响用户访问的命中率。目前普遍使用的缓存置换算法主要有RND、FIFO、LFU、LRU等经典算法，其中LRU算法是最常使用的缓存置换算法。针对大规模图数据处理的问题，存在很多LRU算法的改进算法。如Wang等人［20］提出了一种结合逻辑回归的算法LR与LRU的智能缓存替换策略LR-LRU。Kathavate等人［21］提出了PR-LRU算法，通过从N个LRU的模块中择优选择获取更好的置换结果。Jia等人［22］提出了一种新的缓存策略Hybrid-LRU，其可以使用多种LRU缓存策略来区分优化不同的存储介质。然而这些缓存置换算法均没有考虑数据被访问的热度因素。

2 THEA-CR算法

本章提出TEHA-CR算法，通过评估社交网络中热点话题的热度演化规律，提高图数据模型存储空间的有效利用和管理。其主要目标是改善单机上社交网络图数据在图查询中内容的命中率，减少热点话题内容的频繁磁盘交互，实现高效的缓存淘汰策略。话题簇内的缓存是社交网络图数据交互操作的主要特征，因此，提出一种新的缓存置换策略改进密集图读取的性能。具体地，提出了基于话题热度演化加速度的缓存置换算法THEA-CR。该算法设计维持两个队列，分别对数据的使用频率和热度进行置换管理。根据热度演化加速度将代表性节点在内存中锚定一个热度持续的周期。通过淘汰热度消退的数据，提高了图数据模型的命中率。通过评估话题热度演化规律，对缓存空间进行了有效的更新和替换，进一步减少了I/O操作的次数。社交网络图数据模型中基于话题热度演化加速度的缓存置换算法框架如图1所示。

THEA-CR算法首先将本地数据建模为多个社区［23～25］，聚集属于同一热点话题的节点，建立较为独立的社交网络话题簇。在每个话题簇中，筛选代表性热度节点作为锚定目标。然后，定义话题热度演化加速度，判定热度实体优先级。最后，通过双队列缓存置换策略，实现热点话题数据的有效管理。根据节点所表示话题的使用时间间隔和热度，对数据进行两个维度的重要性评价，通过对社交网络内话题热度演化加速度的评估，设置节点优先级，从而对缓存空间实现有效的利用，减轻了图数据模型的负担，并加速了图数据处理的效率。

2.1 社交网络话题簇实体划分与锚定目标识别

由于社交网络用户时刻活跃在社交平台上，其持续发布和分享着各种新鲜的资讯，并且随着新消息的不断产生，用户的注意力和关注偏好会发生转移。所以，热点话题通常是相对某一固定时间段而言的。针对社交网络消息的转发量、评论数量以及关注者的人数，同一数据在不同时间内将体现出不同的热度。根据热点话题受关注度的差异，社交网络图数据在不同的热点话题周围呈现出多个密集的子图结构。由于话题簇内实体密集、簇间实体稀疏的现象，需要将社交网络图数据划分为多个簇结构。下面对密集型话题簇结构进行分类和形式化定义。

设Ep表示描述热点话题的节点，Me是Ep中包含的节点属性内容的长度、Re表示Ep被转发的数量、Ce和Le分别表示Ep获得的评论数和点赞数。如果消息内容的大小超过32 Byte，则该内容数据无法被编码成为属性记录文件的内联值，在标签属性图中需要调用并占用动态存储记录的存储空间［26］。设置社交网络节点属性内容大小的阈值Γl=32 Byte，交互作用次数的阈值分别表示为Γk和γk。

a）如果Me>Γl，并且Re>Γk，Ce +Le>γk，那么Ep是超大实体节点，用EΘp表示；

b）如果Me>Γl，并且Re>Γk，但是Ce+Le<γk，那么Ep为社交网络内的大实体，用Eθp表示；

c）如果Me>Γl，但是Re<Γk，Ce +Le<γk，那么Ep是宽实体，用E+p表示；

d）如果Me<Γl，则Ep是短实体，用E－p表示。

概括上述四类社交网络实体类型，可以将社交网络密集簇中的实体表示为

Ep=EΘp Me>Γl，Re>Γk & Ce+Le>γk

EθpMe>Γl，Re>Γk & Ce+Le<γk

E+pMe>Γl，Re<Γk & Ce+Le<γk

E－pMe<Γl，Re<Γk & Ce+Le<γk（1）

針对以上实体，分析如下：

a）超大实体EΘp属性信息的内容量和社交网络消息交互的数量（包括转发、点赞和评论）均超过了给定的阈值，大量数据无法编码为内联值，并且这些数据会经常被刷新到内存中。因此，该类数据很容易增加I/O操作的负担，从而降低数据库的吞吐量。

b）大实体Eθp属性信息的内容量和转发数均超过了预设的阈值，而点赞和评论的数量没有超过阈值。其不能被编码为内联值，但是这些数据无须在内存中被频繁刷新。因此，该数据对图数据处理中的吞吐量影响较小。

c）宽实体E+p文本容量超过了给定的阈值，但交互次数较少，未超过阈值，表明该类数据在社交网络中不属于热数据，因此对存储模型影响不大。

d）短实体E－p分散在簇结构的最外层结构，可以在存储时内联编码到存储记录中，不会额外占用存储空间。

根据社交网络话题簇实体的划分，对社交网络图数据中的热点话题查询概率进行规范化定义。

定义1 热点话题查询概率。根据对话题簇实体的分析，假设将社交网络图数据内属性信息的热度均匀地划分为四种不同的实体类别，则社交网络用户对第k类内容的请求概率表示为qk，如式（2）所示。

qk=ckα 1≤k≤K（2）

其中：设置K=4，参数α代表节点内容属性热度分布的集中性程度。α取值越大，节点所代表话题在社交网络中的热度越集中于k取值较小时的内容。根据有关机构关于消息流行度分布和网络流量的分析工作［27，28］中得出的结论，本文设置α为0.8。此外，c值计算如式（3）所示。

∑Kk=1ckα=1c=1∑Kk=11kα（3）

针对话题簇子图划分以及热点话题的查询概率，分析对存储空间造成一定影响的实体数据，并对其在图模型存储中进行热度的评估。随机给定一个节点作为起始节点，搜索与之直接相连的所有节点，并计算相邻节点的度。选择具有最大度的节点作为root，并开始执行广度优先遍历。在下一轮遍历中，如果root仍然是最大度的节点，则将r放入根节点的堆栈Sr中。此外，将root放入节点队列Ln（以度进行排序），同时作为队列的头节点。对于Sr中的每个root，其子节点根据标签和度迭代遍历并存储到一个新的关于r的队列Ln中。当存在节点的度高于Sr的当前头节点时，检查该节点的内容与头节点内容的相似性。若两个节点属于同一热点话题，将度数较大的节点作为Sr中新的头节点，并删除另一节点；否则，将节点作为一个新的热点话题直接放入Sr中作为头节点。最后，算法在遍历所有节点后终止，得到一个根堆栈Sr和一个或多个节点队列Ln，其中多个节点队列是以Sr栈中的根节点作为队列头节点生成的。Ln包含具有多层次的结构树，每棵树均属于相同的热点话题，由其根节点决定。确定根堆栈中的节点是否满足话题簇实体的条件，如果满足，根节点对应的节点队列将被识别为话题簇，否则将其删除。识别过程如算法1所示。

算法1 锚定目标识别算法identifyTC（G，v0）

输入： 图G，开始节点v0。

输出： 话题簇根队列Sr，节点队列集合{Ln}。

1. while 图G中的节点没有全部被访问 then

2.  LN←查找节点v0的所有未被方位的一阶邻居；

2.  root←maxDegree（v0， V（LN）） and status［root］=traversed；

3.  if root不在以Sr.top节点为队首的队列Ln中 then

4.    if root与Sr的头节点具有很高的相似度 then

5.     if degree（root）>degree（Sr.top） then

6.       Sr.pop（top） and Sr.push（root）;

7.       Ln←insertSort（root）;

8.       identifyTC（G， root）

9.    else

10.     Sr.push（root）;

11.     创建一个以当前root为队首的节点队列Ln；

12.     Ln←insertSort（V（LN））；

13.     for v in Ln and status［v］ ！=traversed then

14.      identifyTC（G， v）

15.  else Ln←insertSort（V（LN））；

16. if Sr中的节点不是话题簇实体then

17.  删除以该节点生成的节点队列Ln；

18. 返回Sr，{Ln}。

在算法1中，identifyTC（G，v0）是一个递归算法，其时间复杂度在图的邻接表上为O（|V|+|E|）。identifyTC内包含两个核心操作，即节点队列的遍历（第13行）和插入排序（第16行）。前一个操作可以在O（|V|）时间内执行，而后一个操作需要时间O（|V（Ln）|2），其中Ln表示一个节点邻居的集合。因此，整个算法的时间复杂度为O（（|V|+|E|）×（|V|+|V（Ln）|2））。identifyTC的迭代次数与Ln的大小成反比，即整个算法的迭代次数越多，每个节点的邻居就越少。因此在最坏情况下的迭代運算中，identifyTC（G，v0）算法时间复杂度约为O（|V|2+|V|×|E|）。根据筛选出的话题簇Sr，进一步定义和识别内存置换策略中处理的锚定目标。

定义2 锚定目标。针对社交网络话题簇实体的前两种类型实体，其在标签属性图模型的存储中会导致建模的大量节点中存在重复性的冗余数据，这些数据降低了存储空间利用率，影响了图计算的处理效率。因此，将EΘp和Eθp定义为THEA-CR算法的锚定目标，是缓存置换优化的对象。该实体表示为EΘp∪Eθp={Me>Γl & Re>Γk}。基于统计分析，将Γk设置为数据集中每个事件内消息转发时间的平均值。

2.2 话题热度演化加速度

本节分析从磁盘加载到内存中的所有节点、联系等数据的受欢迎程度。社交网络内的热点数据是由被转发、评论和点赞的数量决定的。选择代表话题的热度持续时间较长的节点，并将其锚定在内存中，可以减少缓存的频繁刷新，从而能够提高命中率。THEA-CR算法考虑话题热度，对锚定目标进行实时更新。首先，评估置换数据的优先级。设置锚定目标的优先级最高，向下依次降低。根据社交网络话题簇结构的类型，定义每个元素的优先级如式（4）所示。

P（EΘp）=P（ρEΘp）=5，P（Eθp）=P（ρEθp）=4，P（E+p）=P（ρE+p）=3

P（E－p）=P（ρE－p）=2，P（EN）=P（ρEN）=1（4）

其中：ρ表示实体的属性;EN表示除话题簇实体以外的普通节点。优先级对比决定了缓存中动态置换演化的规律，将每个数据结构的优先级关系进行形式化，如式（5）所示。

P（EΘp）=P（ρEΘp），>P（Eθp）=P（ρEθp），>P（E+p）=P（ρE+p）

>P（E－p）=P（ρE－p），>P（EN）=P（ρEN）（5）

根据相关统计，社交网络上热点话题的传播时间通常为一周左右。因此，THEA-CR算法将话题热度的持续时间设置为一周，表示为T。热点话题的热度维持时间服从正态分布或偏态分布。无论服从正态分布还是偏态分布，在其生命周期T内均不是常数。为了测量热度变化状态，定义话题热度演化加速度，计算如式（6）所示。

αφ（i）=△v△t=logIDt2－IDt1t2－t1+1（6）

其中：ID=Re+（Ce+Le）;t1和t2是周期中的任意两个时间点，t2>t1;IDt1和IDt2分别代表热点话题在t1和t2时间点下的热度，它们受节点转发次数、评论数和点赞数的影响。

针对某一热点话题，话题热度演化加速度处于该话题在社交网络上持续时间的半个周期时，共存在以下三种情况：

a）αT/2=0时，表示热点话题服从正态分布；

b）αT/2>0时，表明热点话题服从负偏态分布；

c）αT/2<0时，表示热点话题服从正偏态分布。

根据以上三种情况，对话题簇实体数据进行热度更新计算。

2.3 双队列缓存置换策略

THEA-CR算法维护两个队列，即LRU和THEA-CR队列。它们分别从使用时间间隔、话题热度两个维度实现代表性数据在内存中的不断更新置换。在数据查询操作中，将同时对LRU和THEA队列进行查询匹配，任何一个队列的命中均会终止查询操作，直接输出数据。当两个队列均不包含查询数据时，将会从外存中加载数据插入到LRU队列，此时会对加载数据进行优先级判断，将优先级大于等于4的数据转储到THEA队列中。加载的数据需要优先级达到5或4时才会转储到THEA队列中，因此THEA队列的更新置换频率会明显地低于LRU队列。围绕数据的局部性查询时，热点数据会被频繁的读取到，将其置换到THEA队列中可以在缓存中锚定较长的时间，降低了磁盘的反复读取，提升了命中率。THEA-CR算法的双队列查询示意图如图2所示。

随着缓存空间内数据加载量的增加，LRU和THEA队列加载满之后，两个队列需要进行并行化的排序淘汰。LRU队列使用时间间隔进行排序，队列满后优先淘汰最近最少被使用的数据。THEA队列使用话题热度演化加速度进行排序，当在满队列的状态下插入新数据时，计算队尾数据的加速度，若此时αφ变为负值，便将该数据从队列中淘汰。关于话题加速度计算的方法，已在本文第2.2节中详细阐述。双队列缓存置换策略的工作流程如下：

给定社交网络图数据，针对话题簇实体提取缓存置换算法的锚定目标，调用identifyTC算法生成包含锚定目标的序列Sr，并对相应的实体进行优先级标记。根据式（6）计算话题热度演化加速度。最后，在双队列缓存置换的过程中，根据话题关注度和访问频率分别进行数据的锚定和置换，双队列缓存置换策略的整个过程包含数据从外存加载到内存、查找匹配与排序、缓存数据淘汰置换以及数据写回操作。流程如图3所示。

具体地，双队列缓存置换策略维持两个队列，分别是基于使用时间间隔的LRU队列和使用热度演化加速度的THEA队列。當有数据查询操作时，两个队列同时进行查找匹配，以获取命中的数据。当查询的数据在两个队列中均不存在时，需要从磁盘中加载数据到LRU队列中，并同时进行优先级的判断。若加载数据的优先级小于4时，数据将存储在LRU队列中，根据其使用时间的间隔进行队列排序。当加载数据的优先级为5或4时，则直接将其存储到THEA队列中。缓存队列THEA在每次数据插入的过程中，根据热度演化加速度的变化在话题生命周期内排序。当LRU队列已满时，将LRU队尾的最近最少使用的数据淘汰掉。当THEA队列已满时，将THEA队尾热度演化加速度最小的数据淘汰。下面对双队列缓存置换策略进行概括，伪代码如算法2所示。

算法2 双队列缓存置换策略流程

输入：LRU和THEA队列。

输出：重排序后的LRU和THEA队列。

1. 通过使用时间间隔、优先级和热度加速度，决定数据锚定在缓存中的时间长度;

2. Lookup（）：

3. for each i in G do

4.   在LRU和THEA队列中分别进行i的匹配；

5.   if 存在数据i then

6.    return 命中的数据i；

7.   else 从磁盘中加载数据i；

8.   调用函数InsertData（）。

9. InsertData（）：

10. for each i in G do

11.   if P（i）==5 then

12.    将i放入队列THEA中；

13.    使用式（6）计算所有数据的加速度αφ；

14.    更新THEA队列；

15.    if THEA队列满载 then

16.     delete Min（αφ）;

17.   else

18.     将i放入LRU队列；

19.     标记i的使用时间；

20.     更新LRU队列;

21.    if LRU队列存储已满 then

22.     删除最近最少使用的数据。

双队列缓存置换策略是在经典算法LRU的启发下提出的。LRU算法在一个队列中基于访问历史列表置换数据，复杂度为O（1）。LRU-K在LRU的基础上，维护多个队列从而提高了命中率，并解决了缓存污染的问题，其中K为大于2的任意整数。LRU-K的系列算法中，LRU-2是使用率最高且效率最高的算法，其需要维持的两个队列分别是FIFO和LRU队列。LRU-K根据数据被访问的频率K将访问历史队列中的数据置换到缓存队列中。然而，THEA-CR算法通过判断数据的优先级、使用时间间隔和热度维持了一个LRU队列和一个THEA队列，并且在队列中不记录数据的访问次数，减少了开销。因此复杂度大小为LRU-K>THEA-CR>LRU。在双队列缓存置换策略中，将某个数据块从LRU队列首部移动到尾部的平均时间为t1，从THEA队列首部移动到尾部的平均时间为t2，因此THEA-CR缓存置换算法的时间复杂度为O（t1+t2）。

3 实验与评估

3.1 实验环境与数据集

1）实验环境

本节设置的所有实验均运行在内核为Kernel-4.4.110的64位CentOS 7操作系统平台上，其CPU为3.40 GHz 8-core i7-6700，内存为16 GB，并配备ext4文件系统的7200转1 TB容量的西部数字机械硬盘（HDD）。由于HDD只有一个线程，且仅受I/O的约束，所以在HDD上进行了串行实验，为算法提供了公平有效的实验平台。

2）数据集

采用来自数据堂（http：//www.datatang.com/data/46758）的新浪微博数据集进行实验，其下载的数据格式为json.bz。该数据集包含来自社交网络的13个热点话题，共84 168条微博信息、63 641条用户信息和27 759条转发关系信息。首先，在不影响消息语义的前提下进行数据的预处理，删除部分标点及特殊符号，并根据微博ID爬取每条消息的点赞数、评论数和转发数量的字段信息；然后，处理微博的内容信息和转发关系信息，通过社交网络中节点之间的转发关系创建消息节点之间的连接边。

3.2 对比算法及评价指标

）对比算法

为了验证THEA-CR算法的性能，选择四种经典的缓存置换算法进行对比分析，其中包括RND、FIFO、LFU和LRU算法。所有对比算法的核心思想介绍如下。

a）RND算法。其核心原则是不利用主存储器中页面调度情况的历史信息，也不反映程序的局部性，仅通过随机数生成器来确定缓存中被替换的数据，算法简单但具有一定的随机性。

b）FIFO算法。其根据数据进入缓存的先后顺序，先淘汰和置换掉最早进入队列的数据，即当缓存空间存储已满时，对最先进入缓存的数据进行优先淘汰，并置换新的数据。

c）LFU算法。该算法基于数据被访问的次数实现缓存空间的更新置换，即当缓存空间存储数据已满时，对缓存队列中最少被访问到的数据进行优先淘汰和置换。

d）LRU算法。该缓存置换算法基于数据被访问的时间间隔对数据进行淘汰置换，即当缓存队列已满时，对缓存队列中最长时间未被访问到的数据进行优先淘汰。

2）评价指标

数据缓存的目标是通过合理存放预取数据，使得未来用户能够高效地获取所需数据。在对缓存算法的研究过程中，选择最常用的两个评价指标，分别为命中率和查询响应时间。

命中率是指数据库缓存系统在运行时，总的用户请求数和缓存命中数目的比值。缓存命中率越高表示缓存置换算法的性能越好。假设用户发出数据库访问数目为n，βi代表用户的请求被命中或者没有命中的值，如果访问数据被命中，则βi=1，否则βi=0。计算如式（7）所示。

H=∑ni=1βin（7）

查询响应时间是间接反映缓存置换算法对缓存空间数据锚定与淘汰策略有效性的指标。本文采用查询执行时间与最短路径距离来评估算法的性能，其中查找最短路径长度越短，说明查找响应时间越小。

3.3 THEA队列大小对缓存性能的影响

针对THEA-CR算法涉及到的两个队列，本节验证两个队列大小对THEA-CR算法缓存性能的影响。由于两个队列共同占用缓存空间，所以两个队列长度的比例对于提高缓存置换的效率和有效性起到了决定性的作用。在实验中，不考虑缓存中其他配置对缓存的占用，设单机缓存的大小为l，根据系统内核以及部分应用守护进程的占用，初始化的系统内存会占用3 GB左右，实验中设置l=12 GB。队列LRU的长度大小为l1、队列THEA的长度为l2，则l=l1+l2。当队列LRU较小时，缓存可以很快的进行响应，但是在大量的随机查询中，其平均命中率会下降；相反地，当队列LRU较大时，一段时间过后缓存的命中率能够达到一个相对较高的水平。为了验证最优队列的比值，图4展示了当缓存为空时，两个队列陆续加载数据时缓存置换的变换情况。其中，命中率越高，越有利于社交网络中热点话题动态变化的查询。

从图4的实验结果中可以看出，THEA-CR算法维护的两个缓存队列的长度比值并没有一个固定的最优值。若一段时间内查询的数据都属于某一热点话题的局部查询操作时，队列THEA越小越有利于提高缓存的命中率；相反地，若一段时间内查询的数据属于多个热点话题的查询時，队列THEA与LRU的比值在上限为2的范围内越大越好。所以，在聚簇型密集的社交网络中，采用队列LRU与THEA较小的比值设置缓存策略，往往能够达到效果更好的缓存命中率。此外，缓存置换算法会随着缓存内加载的节点数量的增多而有效提高命中率，但是当加载节点数量达到一定的范围后，命中率将不再明显提升，这也证明了缓存命中率不仅受到缓存内加载的节点数量的影响，同时还与缓存内队列长度的比值密切相关。

3.4 THEA-CR算法与对比算法缓存置换性能的比较

为了验证THEA-CR算法在缓存置换中的有效性，本节基于社交网络聚簇密集型数据对THEA-CR算法与四种常用的缓存置换算法的缓存效果进行比较。选择三种图查询操作进行比较，分别为邻居查找（FindNeighbours）、相邻节点查询（FindAdjacentNodes）和最短路径查询（FindShortestPath）。

3.4.1 缓存命中率对比与分析

以下三组实验分别记录了缓存算法从开始启动的状态下，缓存命中率随时间的变化情况。表1展示了五组缓存置换算法在遍历邻居FindNeighbours操作中的命中率对比，表2展示了在查找相邻节点FindAdjacentNodes过程中命中率的对比，表3为缓存置换算法在查找最短路径FindShortestPath过程中命中率的对比。其中数据量加载比例表示随着时间变化的数据量百分比。各算法命中率为在不同容量的节点集合块中的平均值。

在FindNeighbours操作中数据库需要通过宽度优先遍历，查找每个节点的一阶邻居，该过程中查找效率和缓存命中率很大程度上依赖于图数据的局部性。如表1所示，在数据加载比例较小的情况下，RND与FIFO算法的缓存置换效果与LFU和LRU算法没有明显区别，甚至在置换效率上优于LFU和LRU置换算法。然而，随着节点数据量的增加，LFU和LRU算法的命中率显著提升。但是在数据量较小时，命中率与RND和FIFO算法并没有明显的差距。随着数据量的增大，LFU和LRU算法的优势才逐渐体现出来。THEA-CR缓存置換算法是专门针对社交网络中的聚集型密集数据设计的，在围绕一个热点话题进行加载的过程中，充分考虑了数据项的使用频率和热度演化的因素，并通过两个队列进行维护。在查找邻居的操作中体现出了较高的命中率，充分证明了THEA-CR缓存置换算法在社交网络热点话题压缩存储的基础上，能够对缓存空间进行有效的置换和更新。

在FindAdjacentNodes操作中，数据库需要遍历每一条边，每条边的开始节点与终止节点为相邻的节点。如表2所示，RND、FIFO、LFU和LRU在节点数量较小时的命中率没有明显的区别。随着数据量的不断增大，LFU和LRU算法的命中率开始显著提升，但是在数据量增大到一定程度时，上升的趋势逐渐开始缓慢。而THEA-CR算法在查找相邻节点的过程中，由于可以将热点话题数据锚定在第二个队列中，在查找相邻节点时，有效地较少了缓存的置换频率，所以始终保持了较高的命中率，使其显著优于其他缓存置换算法。该结果验证了THEA-CR算法在社交网络聚集型数据中缓存置换的有效性。

在FindShortestPath操作中，需要遍历两个节点形成的路径间的所有节点。在该过程中，很多节点需要被多次遍历。如表3所示，RND和FIFO算法完全没有考虑数据的特性，仅针对随机性和队列的性质作出简单的数据加载和数据剔除的工作，整体的命中率并不高。LFU和LRU算法考虑了数据项的频率因素和时间因素，整体的命中率相比RND和FIFO算法得到了有效的提升。与此同时，THEA-CR缓存置换算法通过队列THEA锚定热度生命周期内的数据，而队列LRU维护了该数据局部内的相邻数据，有利于节点的遍历，因此使其命中率整体上受数据量的影响较小，能够一直保持相对较高的命中率，优于所有对比算法。该实验结果表明，在FindShortestPath查询下，由于节点需要被多次遍历，THEA-CR算法设计的双队列缓存置换策略能够有效地将需要被频繁操作的数据根据热度进行锚定，相较于基准算法能够取得较高的缓存命中率。

3.4.2 查询响应时间对比与分析

采用FindShortestPath操作找出给定起始节点与随机选择的100个节点之间的最短路径。随机选定起始节点id=1 926 965，该节点与随机100个节点之间的最短路径长度主要为10个不同的值，分别为{2、3、4、5、6、7、8、9、10、11}。随机100个节点与给定节点之间的最短路径分布如图5所示。从统计结果中可以发现，THEA-CR算法下100个节点中的大多数节点与起始节点之间的距离为3，说明THEA-CR算法在查询过程中的遍历路径较短，具有较短的相应查询响应时间。

为了证明本文算法引入话题热度演化加速度的有效性，本节实验选取目前被广泛采用的LRU算法进行查询响应时间的对比，三种常见图查询的总执行时间如表4所示。在三次查询操作中，THEA-CR的查询具有较小的时间消耗。这是因为THEA-CR在LRU的基础上，专门针对话题热度演化加速度设计了一个缓存队列，其可以在话题热度期间锚定其数据，节省往返查找的时间。在热度管理中，有效地对缓存空间进行更新和置换，从而加速了图查询操作的速度。因此，与LRU算法相比，从查询工作负载的结果中可以发现，本文算法THEA-CR能够显著提高查询效率。

4 结束语

基于社交网络热点话题的受欢迎程度与热度演化规律，对社交网络话题簇实体的存储在缓存空间内进行了有效的热度对比与置换。首先，对社交网络话题簇实体进行划分;然后通过对缓存锚定目标进行识别，发现具有压缩和缓存置换价值的数据，对其进行热度与优先级的判断;最后，定义话题热度演化加速度，根据社交网络内话题的不断更新和热度演化，对缓存空间内的数据进行评估，进而动态分配缓存空间。实验结果验证了THEA-CR算法能够动态地锚定内存中的数据，有效地对存储空间进行更新。数据表明，THEA-CR算法提高了缓存空间的利用率和图数据的处理速度。

由于社交网络图数据的增量和数据形式的多样性，本文算法仍具有一定的局限性。在未来的工作中，笔者将考虑社交网络数据的图像等多模态形式以及存储机制的改进应用。

参考文献：

[1]侯艳辉，孟帆，王家坤，等.考虑群组结构的在线社交网络竞争性舆情信息传播模型研究［J］.计算机应用研究，2022，39（4）：1054-1059.（Hou Yanhui， Meng Fan， Wang Jiakun， et al. Research on competitive public opinion information dissemination model in online social networks considering group structure［J］.Application Research of Computers，2022，39（4）：1054-1059.）

［2]Jin Jiahui， Luo Junzhou， Khemmarat K， et al. GStar： an efficient framework for answering top-k star queries on billion-node knowledge graphs［J］.World Wide Web，2019，22（4）：1611-1638.

［3]Mahdavinejad M S， Rezvan M， Barekatain M，et al. Machine learning for Internet of Things data analysis： a survey［J］.Digital Communications and Networks，2018，4（3）：161-75.

［4]Botta A， De Donato W， Persico V， et al. Integration of cloud computing and Internet of Things：a survey［J］.Future Generation Computer Systems，2016，56：684-700.

［5]Meng L， Striegel A， Milenkovic＇ T. Local versus global biological network alignment［J］.Bioinformatics，2016，32（20）：3155-64.

［6]Kim J， Hastak M. Social network analysis： characteristics of online social networks after a disaster［J］.International Journal of Information Management，2018，38（1）：86-96.

［7]鄭鑫.面向分布式图存储的图遍历框架的设计与实现［D］.成都：电子科技大学，2022.（Zheng Xin. Design and implementation of graph traversal framework for distributed graph storage［D］.Chengdu：University of Electronic Science and Technology，2022.）

［8]李茜.基于话题生命周期的社交网络热点信息传播机制研究［D］.北京：北京邮电大学，2021.（Li Qian. Research on hot information dissemination mechanism of social network based on topic life cycle［D］.Beijing：Beijing University of Posts and Telecommunications，2021.）

［9]Chierichetti F， Kumar R， Lattanzi S， et al. On compressing social networks［C］//Proc of the 15th ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.New York：ACM Press，2009：219-228.

［10]Kwak H， Lee C， Park H， et al. What is Twitter， a social network or a news media？［C］//Proc of the 19th International Conference on World Wide Web.New York：ACM Press，2010：591-600.

［11]Blandford D K， Blelloch G E， Kash I A. An experimental analysis of a compact graph representation［C］//Proc of the 6th Workshop on Algorithm Engineering and Experiments and the 1st Workshop on Analytic Algorithmics and Combinatorics.Philadelphia，PA：SIAM，2004：49-61.

［12]Bu Yingyi， Borkar V， Jia Jianfeng， et al. Pregelix： big （ger） graph analytics on a dataflow engine［J］.Proceeding of the VLDB Endowment， 2014，8（2）：161-172.

［13]Fan Wenfei， Wang Xin， Wu Yinghui. Querying big graphs within bounded resources［C］//Proc of ACM SIGMOD International Confe-rence on Management of Data.New York：ACM Press，2014：301-312.

［14]陆晔，张伟，李飞，等.一种基于主题时空价值的服务器端瓦片缓存算法［J］.浙江大学学报：理学版，2020，47（1）：12-19.（Lu Ye， Zhang Wei， Li Fei， et al. A server-side tile cache algorithm based on the space-time value of the topic［J］.Journal of Zhejiang University：Science Edition，2020，47（1）：12-19.）

［15]汤求毅，王超，杜震洪，等.基于时空老化模型的服务端瓦片缓存置换算法［J］.浙江大学学报：理学版，2022，49（2）：210-218.（Tang Qiuyi， Wang Chao， Du Zhenhong， et al. Tile cache replacement algorithm for server based on time-space aging model［J］.Journal of Zhejiang University：Science Edition，2022，49（2）：210-218.）

［16]汤求毅.顾及时空与主题特征的分布式遥感影像瓦片缓存方法［D］.杭州：浙江大学，2021.（Tang Qiuyi. A tile cache method for distributed remote sensing images considering space-time and thematic characteristics［D］.Hangzhou：Zhejiang University，2021.）

［17]Kang S J， Lee S W， Ko Y B. A recent popularity based dynamic cache management for content centric networking［C］//Proc of the 4th International Conference on Ubiquitous and Future Networks.Piscataway，NJ：IEEE Press，2012：219-224.

［18]Rossi D， Giuseppe R. Caching performance of content centric networks under multi-path routing（and more）［R］.［S.l.］：Télécom ParisTech， 2011.

［19]葛国栋，郭云飞，兰巨龙，等.CCN中基于替换率的缓存空间动态借调机制［J］.通信学报，2015，36（5）：124-133.（Ge Guodong， Guo Yunfei， Lan Julong， et al. Cache space dynamic secondment mechanism based on replacement rate in CCN［J］.Journal of Communications，2015，36（5）：124-133.）

［20]Wang Yinyin， Yang Yuwang， Han Chen， et al. LR-LRU： a PACS-oriented intelligent cache replacement policy［J］.IEEE Access，2019，7：58073-58084.

［21]Kathavate S， Rajesh L， Srinath NK. PR-LRU：partial random LRU technique for performance improvement of last level cache［J］.International Journal of Computer Aided Engineering and Technology，2019，11（1）：111-121.

［22]Jia Gangyong， Han Guangjie， Xie Hongtianchen， et al. Hybrid-LRU caching for optimizing data storage and retrieval in edge computing-based wearable sensors［J］.IEEE Internet of Things Journal，2018，6（2）：1342-1351.

［23]Guia J， Soares V G， Bernardino J. Graph databases： Neo4j analysis［J］.ICEIS，2017（1）：351-356.

［24]代繼鹏.基于复合复杂网络的网络社区热点话题的识别与分析［D］.青岛：青岛大学，2021.（Dai Jipeng. Identification and analysis of hot topics in online communities based on complex networks［D］.Qingdao：Qingdao University，2021.）

［25]端祥宇.基于图嵌入的动态社交网络社区发现方法研究［D］.徐州：中国矿业大学，2022.（Duan Xiangyu. Research on dynamic social network community discovery method based on graph embedding［D］.Xuzhou：China University of Mining and Technology，2022.）

［26]Park C S， Kaye B K. The Tweet goes on： interconnection of Twitter opinion leadership， network size， and civic engagement［J］.Computers in Human Behavior，2017，69：174-180.

［27]Fricker C， Robert P， Roberts J， et al. Impact of traffic mix on ca-ching performance in a content-centric network［C］//Proc of IEEE INFOCOM Workshops.Piscataway，NJ：IEEE Press，2012：310-315.

［1］ Cisco global cloud index： forecast and methodology，2016—2021 white paper［EB/OL］.（2018-02-01）［2018-05-08］.https：//www.cisco.com/.

收稿日期：2023-01-08；

修回日期：2023-03-06

基金项目：中央级公益科研院所基本科研业务专项资金项目（MS2023-11）

作者简介：王大伟（1989-），男（通信作者），山东潍坊人，助理研究员，博士，主要研究方向为数据库、双碳科技、信息领域的前沿跟踪及监测分析研究（wangdw1@istic.ac.cn）；郑佳（1982-），女，河北唐山人，研究员，博士，主要研究方向为科技政策与产业发展研究；杨岩（1986-），男，山西忻州人，副研究员，博士，主要研究方向为可持续发展模型、科技信息可视化研究.