面向社交網絡密集圖數據存儲的緩存置換算法

王大偉 鄭佳 楊巖

摘 要：為了緩解社交網絡熱點話題生成的密集圖數據導致存儲的頻繁讀取和緩存空間浪費等問題，針對話題產生與消亡的演化更新規律，提出了基于話題熱度演化加速度的緩存置換算法（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-），男，山西忻州人，副研究員，博士，主要研究方向為可持續發展模型、科技信息可視化研究.