面向社交網(wǎng)絡(luò)密集圖數(shù)據(jù)存儲的緩存置換算法

王大偉 鄭佳 楊巖

摘 要：為了緩解社交網(wǎng)絡(luò)熱點(diǎn)話題生成的密集圖數(shù)據(jù)導(dǎo)致存儲的頻繁讀取和緩存空間浪費(fèi)等問題，針對話題產(chǎn)生與消亡的演化更新規(guī)律，提出了基于話題熱度演化加速度的緩存置換算法（cache replacement algorithm based on topic heat evolution acceleration，THEA-CR）。該算法首先對社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行話題簇的實(shí)體劃分，識別錨定目標(biāo)。其次，計(jì)算話題熱度演化加速度，對熱點(diǎn)數(shù)據(jù)的優(yōu)先級進(jìn)行研判；最后設(shè)計(jì)雙隊(duì)列緩存置換策略，針對話題關(guān)注度和訪問頻率進(jìn)行緩存空間的置換和更新。在新浪微博數(shù)據(jù)集中與經(jīng)典的緩存置換算法進(jìn)行大量對比實(shí)驗(yàn)，驗(yàn)證了所提算法具有較好的可行性與有效性。結(jié)果表明提出的THEA-CR算法能夠在社交網(wǎng)絡(luò)密集圖數(shù)據(jù)的不同圖查詢操作中平均提升約31.4%的緩存命中率，并且縮短了約27.1%的查詢響應(yīng)時間。

關(guān)鍵詞：密集圖數(shù)據(jù)； 話題演化加速度； 緩存置換； 空間利用率

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：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 引言

近年來，圖結(jié)構(gòu)數(shù)據(jù)呈現(xiàn)爆炸式的增長，其作為計(jì)算機(jī)領(lǐng)域中的一類最為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，能夠抽象表示這些實(shí)體數(shù)據(jù)之間的關(guān)聯(lián)性，可以適用于諸如社交網(wǎng)絡(luò)［1］、知識圖譜［2］、甚至生物蛋白結(jié)構(gòu)等眾多實(shí)際應(yīng)用場景［3～6］。圖數(shù)據(jù)中復(fù)雜的拓?fù)浣Y(jié)構(gòu)在有效展示關(guān)聯(lián)關(guān)系的同時，會引起圖數(shù)據(jù)組織、管理和存儲的相關(guān)問題［7］。特別地，對于社交網(wǎng)絡(luò)圖數(shù)據(jù)，其通常出現(xiàn)由熱點(diǎn)話題引發(fā)的結(jié)構(gòu)聚簇現(xiàn)象，生成由大量重復(fù)的強(qiáng)關(guān)聯(lián)實(shí)體組成的話題簇結(jié)構(gòu)［8］，且社交互動產(chǎn)生頻繁的磁盤讀取操作更會嚴(yán)重影響圖數(shù)據(jù)模型的空間利用率以及圖計(jì)算的處理速度。因此，針對社交網(wǎng)絡(luò)圖數(shù)據(jù)的分割與存儲，面對結(jié)構(gòu)緊湊、復(fù)雜的圖數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)時，如何在保證密集圖數(shù)據(jù)局部性的前提下，減少磁盤交互并提高緩存命中率是圖數(shù)據(jù)模型亟待解決的難題。

社交網(wǎng)絡(luò)圖數(shù)據(jù)往往存在一些具有大量鄰居節(jié)點(diǎn)的聚焦節(jié)點(diǎn)［9～11］，作為熱點(diǎn)數(shù)據(jù)受到了廣泛的關(guān)注和評論，需要被頻繁讀取。因此，該類數(shù)據(jù)影響著圖數(shù)據(jù)模型在圖計(jì)算操作中迭代執(zhí)行的速度［12，13］。同時，社交網(wǎng)絡(luò)消息具有快速更新的特點(diǎn)，在一段時間內(nèi)會有新的熱點(diǎn)話題出現(xiàn)，并且用戶所關(guān)注的熱點(diǎn)會隨著時間而發(fā)生變化。通常在迭代操作的整個周期內(nèi)，第一輪迭代只有少數(shù)的節(jié)點(diǎn)參與了計(jì)算更新。在進(jìn)一步的迭代中每個節(jié)點(diǎn)的鄰居節(jié)點(diǎn)會依次加入到計(jì)算中來，因此參與計(jì)算的節(jié)點(diǎn)會逐漸增多。當(dāng)計(jì)算中的數(shù)據(jù)節(jié)點(diǎn)達(dá)到一個峰值后，參與過計(jì)算的節(jié)點(diǎn)會慢慢從內(nèi)存中被置換出去，即在整個的圖計(jì)算過程中會有一個階段的迭代輪次，只有較少一部分的節(jié)點(diǎn)參與了計(jì)算更新的操作。針對社交網(wǎng)絡(luò)熱點(diǎn)數(shù)據(jù)不斷更新演化的特性和緩存空間對數(shù)據(jù)的管理方式，需要根據(jù)社交網(wǎng)絡(luò)熱點(diǎn)話題的使用時間與熱度，對緩存空間進(jìn)行有效的分配和置換，從而避免大量沒有參與計(jì)算的節(jié)點(diǎn)數(shù)據(jù)加載導(dǎo)致的緩存污染現(xiàn)象，以及交互操作量的增加問題。本文提出針對話題關(guān)注度和訪問頻率的雙隊(duì)列緩存空間置換和更新策略，可以在緩存隊(duì)列中長時間錨定某一熱點(diǎn)話題，使其在某段時間內(nèi)被頻繁讀取時，增加其在緩存空間的命中率，同時縮短查詢響應(yīng)時間。

在存儲機(jī)制中，為了進(jìn)一步提高緩存空間的利用率和數(shù)據(jù)的讀取效率，需要對緩存空間內(nèi)的數(shù)據(jù)進(jìn)行篩選和淘汰，這有利于一段時間內(nèi)被頻繁調(diào)用的數(shù)據(jù)能夠快速地加載到緩存中，并實(shí)現(xiàn)緩存空間的實(shí)時更新置換，從而進(jìn)一步提高緩存空間的利用率和緩存空間數(shù)據(jù)查詢操作的效率。目前，常用的緩存置換算法根據(jù)空間內(nèi)數(shù)據(jù)的到達(dá)順序以及數(shù)據(jù)使用時間、訪問頻率等因素，對緩存空間的內(nèi)存進(jìn)行分配管理，如隨機(jī)算法（RND）、先進(jìn)先出置換算法（first input first output，F(xiàn)IFO）、最少使用頻率緩存置換算法（LFU）和最近最少使用緩存置換算法（LRU）等，其均具有簡單、易實(shí)現(xiàn)的特點(diǎn)，從而被廣泛應(yīng)用。然而，由于社交網(wǎng)絡(luò)消息的更新速度快，熱點(diǎn)話題的傳播范圍廣，導(dǎo)致現(xiàn)有的緩存置換算法出現(xiàn)緩存污染等問題。針對社交網(wǎng)絡(luò)數(shù)據(jù)實(shí)時發(fā)布的特征，海量用戶的傳播和共享使數(shù)據(jù)具有不斷熱度更迭的性質(zhì)。因此在不同的時間段內(nèi)，受歡迎和頻繁被讀取的話題會隨時間發(fā)生變化，即社交網(wǎng)絡(luò)內(nèi)的熱點(diǎn)話題具有一定的傳播熱度和演化規(guī)律。如何對圖數(shù)據(jù)中代表性的節(jié)點(diǎn)（熱點(diǎn)話題）進(jìn)行熱度的評估，從而提高緩存空間的有效分配，是進(jìn)一步提升社交網(wǎng)絡(luò)圖數(shù)據(jù)存儲有效性的關(guān)鍵性問題。

綜上所述，大多數(shù)緩存淘汰算法和內(nèi)存分配的相關(guān)研究沒有根據(jù)數(shù)據(jù)本身的熱度和演化規(guī)律進(jìn)行分析，因此，需要對社交網(wǎng)絡(luò)圖數(shù)據(jù)的聚集性特點(diǎn)進(jìn)行熱度演化加速度的度量。根據(jù)社交網(wǎng)絡(luò)數(shù)據(jù)更新的速度，對緩存空間數(shù)據(jù)的重要性進(jìn)行評估，動態(tài)更新并置換存儲數(shù)據(jù)，研究更為有效的、具有較高緩存命中率的緩存置換算法。因此，本文提出基于話題熱度演化加速度的緩存置換算法THEA-CR，作為一種新的緩存置換策略，減輕了密集圖結(jié)構(gòu)在加載中的負(fù)擔(dān)。首先，在整個數(shù)據(jù)集內(nèi)識別THEA-CR算法在緩存空間內(nèi)需要錨定的目標(biāo)數(shù)據(jù)，并對其設(shè)置不同的優(yōu)先級，以區(qū)別并減少不常使用、非熱點(diǎn)數(shù)據(jù)對存儲空間的占用；然后，由于空間聚類實(shí)體是由一個熱點(diǎn)話題觸發(fā)的數(shù)據(jù)節(jié)點(diǎn)，其在社交網(wǎng)絡(luò)內(nèi)將保持一段時間的關(guān)注熱度，所以，提出話題熱度演化加速度的定義，進(jìn)一步對緩存空間的數(shù)據(jù)進(jìn)行重要性和優(yōu)先級的評估；最后，基于THEA-CR算法實(shí)現(xiàn)了緩存空間數(shù)據(jù)的迭代更新和有效置換，從而提升了緩存空間的命中率和圖數(shù)據(jù)模型的處理速度。

本文主要貢獻(xiàn)歸納如下：

a）通過對社交網(wǎng)絡(luò)熱點(diǎn)話題在網(wǎng)絡(luò)傳播中的特性，對話題簇進(jìn)行實(shí)體劃分，從而錨定緩存置換中的目標(biāo)實(shí)體。

b）提出話題熱度演化加速度，挖掘話題時間演化規(guī)律，對話題簇實(shí)體進(jìn)行熱度優(yōu)先級比較，實(shí)現(xiàn)話題的熱度研判。

c）設(shè)置雙隊(duì)列緩存置換策略，針對熱點(diǎn)話題的關(guān)注度和訪問頻率進(jìn)行緩存空間的置換和更新，從而將不被關(guān)注和失去熱度的數(shù)據(jù)在緩存中進(jìn)行淘汰，錨定新產(chǎn)生的熱點(diǎn)話題，極大地提高了圖數(shù)據(jù)存儲機(jī)制的空間利用率。

d）實(shí)驗(yàn)結(jié)果表明，THEA-CR算法保證了緩存空間的更新速度，從而實(shí)現(xiàn)了對緩存空間的有效利用，提高了通用圖操作中的緩存命中率，并加速了圖數(shù)據(jù)模型的處理速度。

1 相關(guān)工作

緩存置換是通過一些優(yōu)化的指令或者算法，使得計(jì)算程序或者一個持有硬件的結(jié)構(gòu)能統(tǒng)一、有秩序的管理緩存信息［14～16］。其通常根據(jù)臨時性、頻率、重用距離、分類等性質(zhì)將其分為粗粒度和細(xì)粒度兩類。典型的緩存置換算法通常被廣泛應(yīng)用于數(shù)據(jù)庫緩存、網(wǎng)絡(luò)緩存和磁盤緩存等方面?，F(xiàn)有的緩存置換算法包括RND、FIFO、LRU和LFU及其相應(yīng)的改進(jìn)算法。文獻(xiàn)［17］提出了一種基于流行度的置換策略。文獻(xiàn)［18］在此基礎(chǔ)上進(jìn)一步提出了一種RUF緩存置換策略。此外，文獻(xiàn)［19］基于緩存置換率指標(biāo)，設(shè)計(jì)了動態(tài)緩存借調(diào)方法，使處于繁忙的節(jié)點(diǎn)能夠借調(diào)空閑節(jié)點(diǎn)的緩存資源。目前，結(jié)合LRU算法與流行度因素的新置換算法，主要應(yīng)用于在內(nèi)容中心網(wǎng)絡(luò)集群節(jié)點(diǎn)間進(jìn)行緩存置換，為單機(jī)數(shù)據(jù)管理中的緩存置換算法提供了新的思路。此外，典型的LRU和LFU算法均將近期用戶頻繁關(guān)注的內(nèi)容盡可能地保留在緩存中，間接體現(xiàn)了內(nèi)存空間對用戶熱度話題偏好的管理，并隱性地增加了高熱度話題內(nèi)容在內(nèi)存中的錨定概率。社交網(wǎng)絡(luò)圖數(shù)據(jù)，由消息之間的頻繁轉(zhuǎn)發(fā)等交互操作而形成［6］。針對某一時間爆發(fā)的熱點(diǎn)話題，會出現(xiàn)相關(guān)內(nèi)容的重復(fù)討論，進(jìn)而導(dǎo)致數(shù)據(jù)在存儲過程中被頻繁讀取。由于社交網(wǎng)絡(luò)中的圖數(shù)據(jù)具有高速更新的特點(diǎn)，所以適用于社交網(wǎng)絡(luò)的置換策略應(yīng)該具備階段性置換的特點(diǎn)。針對密集圖數(shù)據(jù)面臨的困難，頻繁的磁盤交互加上極低的磁盤訪問效率，成為了圖數(shù)據(jù)系統(tǒng)性能的瓶頸。為了降低從磁盤中載入數(shù)據(jù)對系統(tǒng)性能的影響，現(xiàn)有的處理方式通常分為以下兩種：

a）采用分布式圖處理技術(shù)，將完整的圖數(shù)據(jù)一次性加載到內(nèi)存中實(shí)現(xiàn)內(nèi)存計(jì)算。為了使內(nèi)存的容量能夠達(dá)到計(jì)算需求，通常通過分布式的方式橫向擴(kuò)展內(nèi)存的總?cè)萘浚@將引起巨額的硬件成本和復(fù)雜的管理操作。這種方案側(cè)重于圖結(jié)構(gòu)數(shù)據(jù)的分區(qū)優(yōu)化、負(fù)載均衡和圖計(jì)算方法的并行化處理。

b）使用單機(jī)有限內(nèi)存處理大規(guī)模圖數(shù)據(jù)的方案，每次計(jì)算只將圖數(shù)據(jù)的小部分加載到內(nèi)存中，未使用的圖數(shù)據(jù)保存在外存內(nèi)。為了有效地將數(shù)據(jù)規(guī)模增大的弊端轉(zhuǎn)移到外存容量上，通過縱向擴(kuò)展的方式增大單個機(jī)器的內(nèi)存容量以及優(yōu)化圖分割算法的處理方式來處理大規(guī)模的圖數(shù)據(jù)。這種方案僅依賴于一臺計(jì)算機(jī)就可以完成圖計(jì)算的任務(wù)，同時避免了分布式計(jì)算的通信開銷與硬件的成本開銷，因此，更側(cè)重于圖數(shù)據(jù)訪問過程中緩存置換算法的性能與效率優(yōu)化的問題。

針對第二種方法，其關(guān)鍵點(diǎn)在于如何保證用于內(nèi)存交互的子圖狀態(tài)的穩(wěn)定性。該過程包含了圖結(jié)構(gòu)數(shù)據(jù)從外存加載到內(nèi)存的操作、內(nèi)存查找匹配與排序的操作，以及計(jì)算結(jié)果寫回外存的操作。每一次的迭代過程均會包含上述操作，因此大量的I/O開銷是該方法的瓶頸。選擇合理的緩存策略，可以有效地減少磁盤讀取的頻率從而提升系統(tǒng)性能，而科學(xué)的緩存置換算法則可以影響用戶訪問的命中率。目前普遍使用的緩存置換算法主要有RND、FIFO、LFU、LRU等經(jīng)典算法，其中LRU算法是最常使用的緩存置換算法。針對大規(guī)模圖數(shù)據(jù)處理的問題，存在很多LRU算法的改進(jìn)算法。如Wang等人［20］提出了一種結(jié)合邏輯回歸的算法LR與LRU的智能緩存替換策略LR-LRU。Kathavate等人［21］提出了PR-LRU算法，通過從N個LRU的模塊中擇優(yōu)選擇獲取更好的置換結(jié)果。Jia等人［22］提出了一種新的緩存策略Hybrid-LRU，其可以使用多種LRU緩存策略來區(qū)分優(yōu)化不同的存儲介質(zhì)。然而這些緩存置換算法均沒有考慮數(shù)據(jù)被訪問的熱度因素。

2 THEA-CR算法

本章提出TEHA-CR算法，通過評估社交網(wǎng)絡(luò)中熱點(diǎn)話題的熱度演化規(guī)律，提高圖數(shù)據(jù)模型存儲空間的有效利用和管理。其主要目標(biāo)是改善單機(jī)上社交網(wǎng)絡(luò)圖數(shù)據(jù)在圖查詢中內(nèi)容的命中率，減少熱點(diǎn)話題內(nèi)容的頻繁磁盤交互，實(shí)現(xiàn)高效的緩存淘汰策略。話題簇內(nèi)的緩存是社交網(wǎng)絡(luò)圖數(shù)據(jù)交互操作的主要特征，因此，提出一種新的緩存置換策略改進(jìn)密集圖讀取的性能。具體地，提出了基于話題熱度演化加速度的緩存置換算法THEA-CR。該算法設(shè)計(jì)維持兩個隊(duì)列，分別對數(shù)據(jù)的使用頻率和熱度進(jìn)行置換管理。根據(jù)熱度演化加速度將代表性節(jié)點(diǎn)在內(nèi)存中錨定一個熱度持續(xù)的周期。通過淘汰熱度消退的數(shù)據(jù)，提高了圖數(shù)據(jù)模型的命中率。通過評估話題熱度演化規(guī)律，對緩存空間進(jìn)行了有效的更新和替換，進(jìn)一步減少了I/O操作的次數(shù)。社交網(wǎng)絡(luò)圖數(shù)據(jù)模型中基于話題熱度演化加速度的緩存置換算法框架如圖1所示。

THEA-CR算法首先將本地?cái)?shù)據(jù)建模為多個社區(qū)［23～25］，聚集屬于同一熱點(diǎn)話題的節(jié)點(diǎn)，建立較為獨(dú)立的社交網(wǎng)絡(luò)話題簇。在每個話題簇中，篩選代表性熱度節(jié)點(diǎn)作為錨定目標(biāo)。然后，定義話題熱度演化加速度，判定熱度實(shí)體優(yōu)先級。最后，通過雙隊(duì)列緩存置換策略，實(shí)現(xiàn)熱點(diǎn)話題數(shù)據(jù)的有效管理。根據(jù)節(jié)點(diǎn)所表示話題的使用時間間隔和熱度，對數(shù)據(jù)進(jìn)行兩個維度的重要性評價(jià)，通過對社交網(wǎng)絡(luò)內(nèi)話題熱度演化加速度的評估，設(shè)置節(jié)點(diǎn)優(yōu)先級，從而對緩存空間實(shí)現(xiàn)有效的利用，減輕了圖數(shù)據(jù)模型的負(fù)擔(dān)，并加速了圖數(shù)據(jù)處理的效率。

2.1 社交網(wǎng)絡(luò)話題簇實(shí)體劃分與錨定目標(biāo)識別

由于社交網(wǎng)絡(luò)用戶時刻活躍在社交平臺上，其持續(xù)發(fā)布和分享著各種新鮮的資訊，并且隨著新消息的不斷產(chǎn)生，用戶的注意力和關(guān)注偏好會發(fā)生轉(zhuǎn)移。所以，熱點(diǎn)話題通常是相對某一固定時間段而言的。針對社交網(wǎng)絡(luò)消息的轉(zhuǎn)發(fā)量、評論數(shù)量以及關(guān)注者的人數(shù)，同一數(shù)據(jù)在不同時間內(nèi)將體現(xiàn)出不同的熱度。根據(jù)熱點(diǎn)話題受關(guān)注度的差異，社交網(wǎng)絡(luò)圖數(shù)據(jù)在不同的熱點(diǎn)話題周圍呈現(xiàn)出多個密集的子圖結(jié)構(gòu)。由于話題簇內(nèi)實(shí)體密集、簇間實(shí)體稀疏的現(xiàn)象，需要將社交網(wǎng)絡(luò)圖數(shù)據(jù)劃分為多個簇結(jié)構(gòu)。下面對密集型話題簇結(jié)構(gòu)進(jìn)行分類和形式化定義。

設(shè)Ep表示描述熱點(diǎn)話題的節(jié)點(diǎn)，Me是Ep中包含的節(jié)點(diǎn)屬性內(nèi)容的長度、Re表示Ep被轉(zhuǎn)發(fā)的數(shù)量、Ce和Le分別表示Ep獲得的評論數(shù)和點(diǎn)贊數(shù)。如果消息內(nèi)容的大小超過32 Byte，則該內(nèi)容數(shù)據(jù)無法被編碼成為屬性記錄文件的內(nèi)聯(lián)值，在標(biāo)簽屬性圖中需要調(diào)用并占用動態(tài)存儲記錄的存儲空間［26］。設(shè)置社交網(wǎng)絡(luò)節(jié)點(diǎn)屬性內(nèi)容大小的閾值Γl=32 Byte，交互作用次數(shù)的閾值分別表示為Γk和γk。

a）如果Me>Γl，并且Re>Γk，Ce +Le>γk，那么Ep是超大實(shí)體節(jié)點(diǎn)，用EΘp表示；

b）如果Me>Γl，并且Re>Γk，但是Ce+Le<γk，那么Ep為社交網(wǎng)絡(luò)內(nèi)的大實(shí)體，用Eθp表示；

c）如果Me>Γl，但是Re<Γk，Ce +Le<γk，那么Ep是寬實(shí)體，用E+p表示；

d）如果Me<Γl，則Ep是短實(shí)體，用E－p表示。

概括上述四類社交網(wǎng)絡(luò)實(shí)體類型，可以將社交網(wǎng)絡(luò)密集簇中的實(shí)體表示為

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）

針對以上實(shí)體，分析如下：

a）超大實(shí)體EΘp屬性信息的內(nèi)容量和社交網(wǎng)絡(luò)消息交互的數(shù)量（包括轉(zhuǎn)發(fā)、點(diǎn)贊和評論）均超過了給定的閾值，大量數(shù)據(jù)無法編碼為內(nèi)聯(lián)值，并且這些數(shù)據(jù)會經(jīng)常被刷新到內(nèi)存中。因此，該類數(shù)據(jù)很容易增加I/O操作的負(fù)擔(dān)，從而降低數(shù)據(jù)庫的吞吐量。

b）大實(shí)體Eθp屬性信息的內(nèi)容量和轉(zhuǎn)發(fā)數(shù)均超過了預(yù)設(shè)的閾值，而點(diǎn)贊和評論的數(shù)量沒有超過閾值。其不能被編碼為內(nèi)聯(lián)值，但是這些數(shù)據(jù)無須在內(nèi)存中被頻繁刷新。因此，該數(shù)據(jù)對圖數(shù)據(jù)處理中的吞吐量影響較小。

c）寬實(shí)體E+p文本容量超過了給定的閾值，但交互次數(shù)較少，未超過閾值，表明該類數(shù)據(jù)在社交網(wǎng)絡(luò)中不屬于熱數(shù)據(jù)，因此對存儲模型影響不大。

d）短實(shí)體E－p分散在簇結(jié)構(gòu)的最外層結(jié)構(gòu)，可以在存儲時內(nèi)聯(lián)編碼到存儲記錄中，不會額外占用存儲空間。

根據(jù)社交網(wǎng)絡(luò)話題簇實(shí)體的劃分，對社交網(wǎng)絡(luò)圖數(shù)據(jù)中的熱點(diǎn)話題查詢概率進(jìn)行規(guī)范化定義。

定義1 熱點(diǎn)話題查詢概率。根據(jù)對話題簇實(shí)體的分析，假設(shè)將社交網(wǎng)絡(luò)圖數(shù)據(jù)內(nèi)屬性信息的熱度均勻地劃分為四種不同的實(shí)體類別，則社交網(wǎng)絡(luò)用戶對第k類內(nèi)容的請求概率表示為qk，如式（2）所示。

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

其中：設(shè)置K=4，參數(shù)α代表節(jié)點(diǎn)內(nèi)容屬性熱度分布的集中性程度。α取值越大，節(jié)點(diǎn)所代表話題在社交網(wǎng)絡(luò)中的熱度越集中于k取值較小時的內(nèi)容。根據(jù)有關(guān)機(jī)構(gòu)關(guān)于消息流行度分布和網(wǎng)絡(luò)流量的分析工作［27，28］中得出的結(jié)論，本文設(shè)置α為0.8。此外，c值計(jì)算如式（3）所示。

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

針對話題簇子圖劃分以及熱點(diǎn)話題的查詢概率，分析對存儲空間造成一定影響的實(shí)體數(shù)據(jù)，并對其在圖模型存儲中進(jìn)行熱度的評估。隨機(jī)給定一個節(jié)點(diǎn)作為起始節(jié)點(diǎn)，搜索與之直接相連的所有節(jié)點(diǎn)，并計(jì)算相鄰節(jié)點(diǎn)的度。選擇具有最大度的節(jié)點(diǎn)作為root，并開始執(zhí)行廣度優(yōu)先遍歷。在下一輪遍歷中，如果root仍然是最大度的節(jié)點(diǎn)，則將r放入根節(jié)點(diǎn)的堆棧Sr中。此外，將root放入節(jié)點(diǎn)隊(duì)列Ln（以度進(jìn)行排序），同時作為隊(duì)列的頭節(jié)點(diǎn)。對于Sr中的每個root，其子節(jié)點(diǎn)根據(jù)標(biāo)簽和度迭代遍歷并存儲到一個新的關(guān)于r的隊(duì)列Ln中。當(dāng)存在節(jié)點(diǎn)的度高于Sr的當(dāng)前頭節(jié)點(diǎn)時，檢查該節(jié)點(diǎn)的內(nèi)容與頭節(jié)點(diǎn)內(nèi)容的相似性。若兩個節(jié)點(diǎn)屬于同一熱點(diǎn)話題，將度數(shù)較大的節(jié)點(diǎn)作為Sr中新的頭節(jié)點(diǎn)，并刪除另一節(jié)點(diǎn)；否則，將節(jié)點(diǎn)作為一個新的熱點(diǎn)話題直接放入Sr中作為頭節(jié)點(diǎn)。最后，算法在遍歷所有節(jié)點(diǎn)后終止，得到一個根堆棧Sr和一個或多個節(jié)點(diǎn)隊(duì)列Ln，其中多個節(jié)點(diǎn)隊(duì)列是以Sr棧中的根節(jié)點(diǎn)作為隊(duì)列頭節(jié)點(diǎn)生成的。Ln包含具有多層次的結(jié)構(gòu)樹，每棵樹均屬于相同的熱點(diǎn)話題，由其根節(jié)點(diǎn)決定。確定根堆棧中的節(jié)點(diǎn)是否滿足話題簇實(shí)體的條件，如果滿足，根節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)隊(duì)列將被識別為話題簇，否則將其刪除。識別過程如算法1所示。

算法1 錨定目標(biāo)識別算法identifyTC（G，v0）

輸入： 圖G，開始節(jié)點(diǎn)v0。

輸出： 話題簇根隊(duì)列Sr，節(jié)點(diǎn)隊(duì)列集合{Ln}。

1. while 圖G中的節(jié)點(diǎn)沒有全部被訪問 then

2.? LN←查找節(jié)點(diǎn)v0的所有未被方位的一階鄰居；

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

3.? if root不在以Sr.top節(jié)點(diǎn)為隊(duì)首的隊(duì)列Ln中 then

4.?? ?if root與Sr的頭節(jié)點(diǎn)具有很高的相似度 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.??? ?創(chuàng)建一個以當(dāng)前root為隊(duì)首的節(jié)點(diǎn)隊(duì)列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中的節(jié)點(diǎn)不是話題簇實(shí)體then

17. ?刪除以該節(jié)點(diǎn)生成的節(jié)點(diǎn)隊(duì)列Ln；

18. 返回Sr，{Ln}。

在算法1中，identifyTC（G，v0）是一個遞歸算法，其時間復(fù)雜度在圖的鄰接表上為O（|V|+|E|）。identifyTC內(nèi)包含兩個核心操作，即節(jié)點(diǎn)隊(duì)列的遍歷（第13行）和插入排序（第16行）。前一個操作可以在O（|V|）時間內(nèi)執(zhí)行，而后一個操作需要時間O（|V（Ln）|2），其中Ln表示一個節(jié)點(diǎn)鄰居的集合。因此，整個算法的時間復(fù)雜度為O（（|V|+|E|）×（|V|+|V（Ln）|2））。identifyTC的迭代次數(shù)與Ln的大小成反比，即整個算法的迭代次數(shù)越多，每個節(jié)點(diǎn)的鄰居就越少。因此在最壞情況下的迭代運(yùn)算中，identifyTC（G，v0）算法時間復(fù)雜度約為O（|V|2+|V|×|E|）。根據(jù)篩選出的話題簇Sr，進(jìn)一步定義和識別內(nèi)存置換策略中處理的錨定目標(biāo)。

定義2 錨定目標(biāo)。針對社交網(wǎng)絡(luò)話題簇實(shí)體的前兩種類型實(shí)體，其在標(biāo)簽屬性圖模型的存儲中會導(dǎo)致建模的大量節(jié)點(diǎn)中存在重復(fù)性的冗余數(shù)據(jù)，這些數(shù)據(jù)降低了存儲空間利用率，影響了圖計(jì)算的處理效率。因此，將EΘp和Eθp定義為THEA-CR算法的錨定目標(biāo)，是緩存置換優(yōu)化的對象。該實(shí)體表示為EΘp∪Eθp={Me>Γl & Re>Γk}?；诮y(tǒng)計(jì)分析，將Γk設(shè)置為數(shù)據(jù)集中每個事件內(nèi)消息轉(zhuǎn)發(fā)時間的平均值。

2.2 話題熱度演化加速度

本節(jié)分析從磁盤加載到內(nèi)存中的所有節(jié)點(diǎn)、聯(lián)系等數(shù)據(jù)的受歡迎程度。社交網(wǎng)絡(luò)內(nèi)的熱點(diǎn)數(shù)據(jù)是由被轉(zhuǎn)發(fā)、評論和點(diǎn)贊的數(shù)量決定的。選擇代表話題的熱度持續(xù)時間較長的節(jié)點(diǎn)，并將其錨定在內(nèi)存中，可以減少緩存的頻繁刷新，從而能夠提高命中率。THEA-CR算法考慮話題熱度，對錨定目標(biāo)進(jìn)行實(shí)時更新。首先，評估置換數(shù)據(jù)的優(yōu)先級。設(shè)置錨定目標(biāo)的優(yōu)先級最高，向下依次降低。根據(jù)社交網(wǎng)絡(luò)話題簇結(jié)構(gòu)的類型，定義每個元素的優(yōu)先級如式（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）

其中：ρ表示實(shí)體的屬性;EN表示除話題簇實(shí)體以外的普通節(jié)點(diǎn)。優(yōu)先級對比決定了緩存中動態(tài)置換演化的規(guī)律，將每個數(shù)據(jù)結(jié)構(gòu)的優(yōu)先級關(guān)系進(jìn)行形式化，如式（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）

根據(jù)相關(guān)統(tǒng)計(jì)，社交網(wǎng)絡(luò)上熱點(diǎn)話題的傳播時間通常為一周左右。因此，THEA-CR算法將話題熱度的持續(xù)時間設(shè)置為一周，表示為T。熱點(diǎn)話題的熱度維持時間服從正態(tài)分布或偏態(tài)分布。無論服從正態(tài)分布還是偏態(tài)分布，在其生命周期T內(nèi)均不是常數(shù)。為了測量熱度變化狀態(tài)，定義話題熱度演化加速度，計(jì)算如式（6）所示。

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

其中：ID=Re+（Ce+Le）;t1和t2是周期中的任意兩個時間點(diǎn)，t2>t1;IDt1和IDt2分別代表熱點(diǎn)話題在t1和t2時間點(diǎn)下的熱度，它們受節(jié)點(diǎn)轉(zhuǎn)發(fā)次數(shù)、評論數(shù)和點(diǎn)贊數(shù)的影響。

針對某一熱點(diǎn)話題，話題熱度演化加速度處于該話題在社交網(wǎng)絡(luò)上持續(xù)時間的半個周期時，共存在以下三種情況：

a）αT/2=0時，表示熱點(diǎn)話題服從正態(tài)分布；

b）αT/2>0時，表明熱點(diǎn)話題服從負(fù)偏態(tài)分布；

c）αT/2<0時，表示熱點(diǎn)話題服從正偏態(tài)分布。

根據(jù)以上三種情況，對話題簇實(shí)體數(shù)據(jù)進(jìn)行熱度更新計(jì)算。

2.3 雙隊(duì)列緩存置換策略

THEA-CR算法維護(hù)兩個隊(duì)列，即LRU和THEA-CR隊(duì)列。它們分別從使用時間間隔、話題熱度兩個維度實(shí)現(xiàn)代表性數(shù)據(jù)在內(nèi)存中的不斷更新置換。在數(shù)據(jù)查詢操作中，將同時對LRU和THEA隊(duì)列進(jìn)行查詢匹配，任何一個隊(duì)列的命中均會終止查詢操作，直接輸出數(shù)據(jù)。當(dāng)兩個隊(duì)列均不包含查詢數(shù)據(jù)時，將會從外存中加載數(shù)據(jù)插入到LRU隊(duì)列，此時會對加載數(shù)據(jù)進(jìn)行優(yōu)先級判斷，將優(yōu)先級大于等于4的數(shù)據(jù)轉(zhuǎn)儲到THEA隊(duì)列中。加載的數(shù)據(jù)需要優(yōu)先級達(dá)到5或4時才會轉(zhuǎn)儲到THEA隊(duì)列中，因此THEA隊(duì)列的更新置換頻率會明顯地低于LRU隊(duì)列。圍繞數(shù)據(jù)的局部性查詢時，熱點(diǎn)數(shù)據(jù)會被頻繁的讀取到，將其置換到THEA隊(duì)列中可以在緩存中錨定較長的時間，降低了磁盤的反復(fù)讀取，提升了命中率。THEA-CR算法的雙隊(duì)列查詢示意圖如圖2所示。

隨著緩存空間內(nèi)數(shù)據(jù)加載量的增加，LRU和THEA隊(duì)列加載滿之后，兩個隊(duì)列需要進(jìn)行并行化的排序淘汰。LRU隊(duì)列使用時間間隔進(jìn)行排序，隊(duì)列滿后優(yōu)先淘汰最近最少被使用的數(shù)據(jù)。THEA隊(duì)列使用話題熱度演化加速度進(jìn)行排序，當(dāng)在滿隊(duì)列的狀態(tài)下插入新數(shù)據(jù)時，計(jì)算隊(duì)尾數(shù)據(jù)的加速度，若此時αφ變?yōu)樨?fù)值，便將該數(shù)據(jù)從隊(duì)列中淘汰。關(guān)于話題加速度計(jì)算的方法，已在本文第2.2節(jié)中詳細(xì)闡述。雙隊(duì)列緩存置換策略的工作流程如下：

給定社交網(wǎng)絡(luò)圖數(shù)據(jù)，針對話題簇實(shí)體提取緩存置換算法的錨定目標(biāo)，調(diào)用identifyTC算法生成包含錨定目標(biāo)的序列Sr，并對相應(yīng)的實(shí)體進(jìn)行優(yōu)先級標(biāo)記。根據(jù)式（6）計(jì)算話題熱度演化加速度。最后，在雙隊(duì)列緩存置換的過程中，根據(jù)話題關(guān)注度和訪問頻率分別進(jìn)行數(shù)據(jù)的錨定和置換，雙隊(duì)列緩存置換策略的整個過程包含數(shù)據(jù)從外存加載到內(nèi)存、查找匹配與排序、緩存數(shù)據(jù)淘汰置換以及數(shù)據(jù)寫回操作。流程如圖3所示。

具體地，雙隊(duì)列緩存置換策略維持兩個隊(duì)列，分別是基于使用時間間隔的LRU隊(duì)列和使用熱度演化加速度的THEA隊(duì)列。當(dāng)有數(shù)據(jù)查詢操作時，兩個隊(duì)列同時進(jìn)行查找匹配，以獲取命中的數(shù)據(jù)。當(dāng)查詢的數(shù)據(jù)在兩個隊(duì)列中均不存在時，需要從磁盤中加載數(shù)據(jù)到LRU隊(duì)列中，并同時進(jìn)行優(yōu)先級的判斷。若加載數(shù)據(jù)的優(yōu)先級小于4時，數(shù)據(jù)將存儲在LRU隊(duì)列中，根據(jù)其使用時間的間隔進(jìn)行隊(duì)列排序。當(dāng)加載數(shù)據(jù)的優(yōu)先級為5或4時，則直接將其存儲到THEA隊(duì)列中。緩存隊(duì)列THEA在每次數(shù)據(jù)插入的過程中，根據(jù)熱度演化加速度的變化在話題生命周期內(nèi)排序。當(dāng)LRU隊(duì)列已滿時，將LRU隊(duì)尾的最近最少使用的數(shù)據(jù)淘汰掉。當(dāng)THEA隊(duì)列已滿時，將THEA隊(duì)尾熱度演化加速度最小的數(shù)據(jù)淘汰。下面對雙隊(duì)列緩存置換策略進(jìn)行概括，偽代碼如算法2所示。

算法2 雙隊(duì)列緩存置換策略流程

輸入：LRU和THEA隊(duì)列。

輸出：重排序后的LRU和THEA隊(duì)列。

1. 通過使用時間間隔、優(yōu)先級和熱度加速度，決定數(shù)據(jù)錨定在緩存中的時間長度;

2. Lookup（）：

3. for each i in G do

4.? ?在LRU和THEA隊(duì)列中分別進(jìn)行i的匹配；

5.? ?if 存在數(shù)據(jù)i then

6.?? ?return 命中的數(shù)據(jù)i；

7.? ?else 從磁盤中加載數(shù)據(jù)i；

8.?? 調(diào)用函數(shù)InsertData（）。

9. InsertData（）：

10. for each i in G do

11.? ?if P（i）==5 then

12.?? ?將i放入隊(duì)列THEA中；

13.?? ?使用式（6）計(jì)算所有數(shù)據(jù)的加速度αφ；

14.?? ?更新THEA隊(duì)列；

15.?? ?if THEA隊(duì)列滿載 then

16.??? ?delete Min（αφ）;

17.?? else

18.??? ?將i放入LRU隊(duì)列；

19.??? ?標(biāo)記i的使用時間；

20.??? ?更新LRU隊(duì)列;

21.?? ?if LRU隊(duì)列存儲已滿 then

22.??? ?刪除最近最少使用的數(shù)據(jù)。

雙隊(duì)列緩存置換策略是在經(jīng)典算法LRU的啟發(fā)下提出的。LRU算法在一個隊(duì)列中基于訪問歷史列表置換數(shù)據(jù)，復(fù)雜度為O（1）。LRU-K在LRU的基礎(chǔ)上，維護(hù)多個隊(duì)列從而提高了命中率，并解決了緩存污染的問題，其中K為大于2的任意整數(shù)。LRU-K的系列算法中，LRU-2是使用率最高且效率最高的算法，其需要維持的兩個隊(duì)列分別是FIFO和LRU隊(duì)列。LRU-K根據(jù)數(shù)據(jù)被訪問的頻率K將訪問歷史隊(duì)列中的數(shù)據(jù)置換到緩存隊(duì)列中。然而，THEA-CR算法通過判斷數(shù)據(jù)的優(yōu)先級、使用時間間隔和熱度維持了一個LRU隊(duì)列和一個THEA隊(duì)列，并且在隊(duì)列中不記錄數(shù)據(jù)的訪問次數(shù)，減少了開銷。因此復(fù)雜度大小為LRU-K>THEA-CR>LRU。在雙隊(duì)列緩存置換策略中，將某個數(shù)據(jù)塊從LRU隊(duì)列首部移動到尾部的平均時間為t1，從THEA隊(duì)列首部移動到尾部的平均時間為t2，因此THEA-CR緩存置換算法的時間復(fù)雜度為O（t1+t2）。

3 實(shí)驗(yàn)與評估

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

1）實(shí)驗(yàn)環(huán)境

本節(jié)設(shè)置的所有實(shí)驗(yàn)均運(yùn)行在內(nèi)核為Kernel-4.4.110的64位CentOS 7操作系統(tǒng)平臺上，其CPU為3.40 GHz 8-core i7-6700，內(nèi)存為16 GB，并配備ext4文件系統(tǒng)的7200轉(zhuǎn)1 TB容量的西部數(shù)字機(jī)械硬盤（HDD）。由于HDD只有一個線程，且僅受I/O的約束，所以在HDD上進(jìn)行了串行實(shí)驗(yàn)，為算法提供了公平有效的實(shí)驗(yàn)平臺。

2）數(shù)據(jù)集

采用來自數(shù)據(jù)堂（http：//www.datatang.com/data/46758）的新浪微博數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其下載的數(shù)據(jù)格式為json.bz。該數(shù)據(jù)集包含來自社交網(wǎng)絡(luò)的13個熱點(diǎn)話題，共84 168條微博信息、63 641條用戶信息和27 759條轉(zhuǎn)發(fā)關(guān)系信息。首先，在不影響消息語義的前提下進(jìn)行數(shù)據(jù)的預(yù)處理，刪除部分標(biāo)點(diǎn)及特殊符號，并根據(jù)微博ID爬取每條消息的點(diǎn)贊數(shù)、評論數(shù)和轉(zhuǎn)發(fā)數(shù)量的字段信息；然后，處理微博的內(nèi)容信息和轉(zhuǎn)發(fā)關(guān)系信息，通過社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)關(guān)系創(chuàng)建消息節(jié)點(diǎn)之間的連接邊。

3.2 對比算法及評價(jià)指標(biāo)

）對比算法

為了驗(yàn)證THEA-CR算法的性能，選擇四種經(jīng)典的緩存置換算法進(jìn)行對比分析，其中包括RND、FIFO、LFU和LRU算法。所有對比算法的核心思想介紹如下。

a）RND算法。其核心原則是不利用主存儲器中頁面調(diào)度情況的歷史信息，也不反映程序的局部性，僅通過隨機(jī)數(shù)生成器來確定緩存中被替換的數(shù)據(jù)，算法簡單但具有一定的隨機(jī)性。

b）FIFO算法。其根據(jù)數(shù)據(jù)進(jìn)入緩存的先后順序，先淘汰和置換掉最早進(jìn)入隊(duì)列的數(shù)據(jù)，即當(dāng)緩存空間存儲已滿時，對最先進(jìn)入緩存的數(shù)據(jù)進(jìn)行優(yōu)先淘汰，并置換新的數(shù)據(jù)。

c）LFU算法。該算法基于數(shù)據(jù)被訪問的次數(shù)實(shí)現(xiàn)緩存空間的更新置換，即當(dāng)緩存空間存儲數(shù)據(jù)已滿時，對緩存隊(duì)列中最少被訪問到的數(shù)據(jù)進(jìn)行優(yōu)先淘汰和置換。

d）LRU算法。該緩存置換算法基于數(shù)據(jù)被訪問的時間間隔對數(shù)據(jù)進(jìn)行淘汰置換，即當(dāng)緩存隊(duì)列已滿時，對緩存隊(duì)列中最長時間未被訪問到的數(shù)據(jù)進(jìn)行優(yōu)先淘汰。

2）評價(jià)指標(biāo)

數(shù)據(jù)緩存的目標(biāo)是通過合理存放預(yù)取數(shù)據(jù)，使得未來用戶能夠高效地獲取所需數(shù)據(jù)。在對緩存算法的研究過程中，選擇最常用的兩個評價(jià)指標(biāo)，分別為命中率和查詢響應(yīng)時間。

命中率是指數(shù)據(jù)庫緩存系統(tǒng)在運(yùn)行時，總的用戶請求數(shù)和緩存命中數(shù)目的比值。緩存命中率越高表示緩存置換算法的性能越好。假設(shè)用戶發(fā)出數(shù)據(jù)庫訪問數(shù)目為n，βi代表用戶的請求被命中或者沒有命中的值，如果訪問數(shù)據(jù)被命中，則βi=1，否則βi=0。計(jì)算如式（7）所示。

H=∑ni=1βin（7）

查詢響應(yīng)時間是間接反映緩存置換算法對緩存空間數(shù)據(jù)錨定與淘汰策略有效性的指標(biāo)。本文采用查詢執(zhí)行時間與最短路徑距離來評估算法的性能，其中查找最短路徑長度越短，說明查找響應(yīng)時間越小。

3.3 THEA隊(duì)列大小對緩存性能的影響

針對THEA-CR算法涉及到的兩個隊(duì)列，本節(jié)驗(yàn)證兩個隊(duì)列大小對THEA-CR算法緩存性能的影響。由于兩個隊(duì)列共同占用緩存空間，所以兩個隊(duì)列長度的比例對于提高緩存置換的效率和有效性起到了決定性的作用。在實(shí)驗(yàn)中，不考慮緩存中其他配置對緩存的占用，設(shè)單機(jī)緩存的大小為l，根據(jù)系統(tǒng)內(nèi)核以及部分應(yīng)用守護(hù)進(jìn)程的占用，初始化的系統(tǒng)內(nèi)存會占用3 GB左右，實(shí)驗(yàn)中設(shè)置l=12 GB。隊(duì)列LRU的長度大小為l1、隊(duì)列THEA的長度為l2，則l=l1+l2。當(dāng)隊(duì)列LRU較小時，緩存可以很快的進(jìn)行響應(yīng)，但是在大量的隨機(jī)查詢中，其平均命中率會下降；相反地，當(dāng)隊(duì)列LRU較大時，一段時間過后緩存的命中率能夠達(dá)到一個相對較高的水平。為了驗(yàn)證最優(yōu)隊(duì)列的比值，圖4展示了當(dāng)緩存為空時，兩個隊(duì)列陸續(xù)加載數(shù)據(jù)時緩存置換的變換情況。其中，命中率越高，越有利于社交網(wǎng)絡(luò)中熱點(diǎn)話題動態(tài)變化的查詢。

從圖4的實(shí)驗(yàn)結(jié)果中可以看出，THEA-CR算法維護(hù)的兩個緩存隊(duì)列的長度比值并沒有一個固定的最優(yōu)值。若一段時間內(nèi)查詢的數(shù)據(jù)都屬于某一熱點(diǎn)話題的局部查詢操作時，隊(duì)列THEA越小越有利于提高緩存的命中率；相反地，若一段時間內(nèi)查詢的數(shù)據(jù)屬于多個熱點(diǎn)話題的查詢時，隊(duì)列THEA與LRU的比值在上限為2的范圍內(nèi)越大越好。所以，在聚簇型密集的社交網(wǎng)絡(luò)中，采用隊(duì)列LRU與THEA較小的比值設(shè)置緩存策略，往往能夠達(dá)到效果更好的緩存命中率。此外，緩存置換算法會隨著緩存內(nèi)加載的節(jié)點(diǎn)數(shù)量的增多而有效提高命中率，但是當(dāng)加載節(jié)點(diǎn)數(shù)量達(dá)到一定的范圍后，命中率將不再明顯提升，這也證明了緩存命中率不僅受到緩存內(nèi)加載的節(jié)點(diǎn)數(shù)量的影響，同時還與緩存內(nèi)隊(duì)列長度的比值密切相關(guān)。

3.4 THEA-CR算法與對比算法緩存置換性能的比較

為了驗(yàn)證THEA-CR算法在緩存置換中的有效性，本節(jié)基于社交網(wǎng)絡(luò)聚簇密集型數(shù)據(jù)對THEA-CR算法與四種常用的緩存置換算法的緩存效果進(jìn)行比較。選擇三種圖查詢操作進(jìn)行比較，分別為鄰居查找（FindNeighbours）、相鄰節(jié)點(diǎn)查詢（FindAdjacentNodes）和最短路徑查詢（FindShortestPath）。

3.4.1 緩存命中率對比與分析

以下三組實(shí)驗(yàn)分別記錄了緩存算法從開始啟動的狀態(tài)下，緩存命中率隨時間的變化情況。表1展示了五組緩存置換算法在遍歷鄰居FindNeighbours操作中的命中率對比，表2展示了在查找相鄰節(jié)點(diǎn)FindAdjacentNodes過程中命中率的對比，表3為緩存置換算法在查找最短路徑FindShortestPath過程中命中率的對比。其中數(shù)據(jù)量加載比例表示隨著時間變化的數(shù)據(jù)量百分比。各算法命中率為在不同容量的節(jié)點(diǎn)集合塊中的平均值。

在FindNeighbours操作中數(shù)據(jù)庫需要通過寬度優(yōu)先遍歷，查找每個節(jié)點(diǎn)的一階鄰居，該過程中查找效率和緩存命中率很大程度上依賴于圖數(shù)據(jù)的局部性。如表1所示，在數(shù)據(jù)加載比例較小的情況下，RND與FIFO算法的緩存置換效果與LFU和LRU算法沒有明顯區(qū)別，甚至在置換效率上優(yōu)于LFU和LRU置換算法。然而，隨著節(jié)點(diǎn)數(shù)據(jù)量的增加，LFU和LRU算法的命中率顯著提升。但是在數(shù)據(jù)量較小時，命中率與RND和FIFO算法并沒有明顯的差距。隨著數(shù)據(jù)量的增大，LFU和LRU算法的優(yōu)勢才逐漸體現(xiàn)出來。THEA-CR緩存置換算法是專門針對社交網(wǎng)絡(luò)中的聚集型密集數(shù)據(jù)設(shè)計(jì)的，在圍繞一個熱點(diǎn)話題進(jìn)行加載的過程中，充分考慮了數(shù)據(jù)項(xiàng)的使用頻率和熱度演化的因素，并通過兩個隊(duì)列進(jìn)行維護(hù)。在查找鄰居的操作中體現(xiàn)出了較高的命中率，充分證明了THEA-CR緩存置換算法在社交網(wǎng)絡(luò)熱點(diǎn)話題壓縮存儲的基礎(chǔ)上，能夠?qū)彺婵臻g進(jìn)行有效的置換和更新。

在FindAdjacentNodes操作中，數(shù)據(jù)庫需要遍歷每一條邊，每條邊的開始節(jié)點(diǎn)與終止節(jié)點(diǎn)為相鄰的節(jié)點(diǎn)。如表2所示，RND、FIFO、LFU和LRU在節(jié)點(diǎn)數(shù)量較小時的命中率沒有明顯的區(qū)別。隨著數(shù)據(jù)量的不斷增大，LFU和LRU算法的命中率開始顯著提升，但是在數(shù)據(jù)量增大到一定程度時，上升的趨勢逐漸開始緩慢。而THEA-CR算法在查找相鄰節(jié)點(diǎn)的過程中，由于可以將熱點(diǎn)話題數(shù)據(jù)錨定在第二個隊(duì)列中，在查找相鄰節(jié)點(diǎn)時，有效地較少了緩存的置換頻率，所以始終保持了較高的命中率，使其顯著優(yōu)于其他緩存置換算法。該結(jié)果驗(yàn)證了THEA-CR算法在社交網(wǎng)絡(luò)聚集型數(shù)據(jù)中緩存置換的有效性。

在FindShortestPath操作中，需要遍歷兩個節(jié)點(diǎn)形成的路徑間的所有節(jié)點(diǎn)。在該過程中，很多節(jié)點(diǎn)需要被多次遍歷。如表3所示，RND和FIFO算法完全沒有考慮數(shù)據(jù)的特性，僅針對隨機(jī)性和隊(duì)列的性質(zhì)作出簡單的數(shù)據(jù)加載和數(shù)據(jù)剔除的工作，整體的命中率并不高。LFU和LRU算法考慮了數(shù)據(jù)項(xiàng)的頻率因素和時間因素，整體的命中率相比RND和FIFO算法得到了有效的提升。與此同時，THEA-CR緩存置換算法通過隊(duì)列THEA錨定熱度生命周期內(nèi)的數(shù)據(jù)，而隊(duì)列LRU維護(hù)了該數(shù)據(jù)局部內(nèi)的相鄰數(shù)據(jù)，有利于節(jié)點(diǎn)的遍歷，因此使其命中率整體上受數(shù)據(jù)量的影響較小，能夠一直保持相對較高的命中率，優(yōu)于所有對比算法。該實(shí)驗(yàn)結(jié)果表明，在FindShortestPath查詢下，由于節(jié)點(diǎn)需要被多次遍歷，THEA-CR算法設(shè)計(jì)的雙隊(duì)列緩存置換策略能夠有效地將需要被頻繁操作的數(shù)據(jù)根據(jù)熱度進(jìn)行錨定，相較于基準(zhǔn)算法能夠取得較高的緩存命中率。

3.4.2 查詢響應(yīng)時間對比與分析

采用FindShortestPath操作找出給定起始節(jié)點(diǎn)與隨機(jī)選擇的100個節(jié)點(diǎn)之間的最短路徑。隨機(jī)選定起始節(jié)點(diǎn)id=1 926 965，該節(jié)點(diǎn)與隨機(jī)100個節(jié)點(diǎn)之間的最短路徑長度主要為10個不同的值，分別為{2、3、4、5、6、7、8、9、10、11}。隨機(jī)100個節(jié)點(diǎn)與給定節(jié)點(diǎn)之間的最短路徑分布如圖5所示。從統(tǒng)計(jì)結(jié)果中可以發(fā)現(xiàn)，THEA-CR算法下100個節(jié)點(diǎn)中的大多數(shù)節(jié)點(diǎn)與起始節(jié)點(diǎn)之間的距離為3，說明THEA-CR算法在查詢過程中的遍歷路徑較短，具有較短的相應(yīng)查詢響應(yīng)時間。

為了證明本文算法引入話題熱度演化加速度的有效性，本節(jié)實(shí)驗(yàn)選取目前被廣泛采用的LRU算法進(jìn)行查詢響應(yīng)時間的對比，三種常見圖查詢的總執(zhí)行時間如表4所示。在三次查詢操作中，THEA-CR的查詢具有較小的時間消耗。這是因?yàn)門HEA-CR在LRU的基礎(chǔ)上，專門針對話題熱度演化加速度設(shè)計(jì)了一個緩存隊(duì)列，其可以在話題熱度期間錨定其數(shù)據(jù)，節(jié)省往返查找的時間。在熱度管理中，有效地對緩存空間進(jìn)行更新和置換，從而加速了圖查詢操作的速度。因此，與LRU算法相比，從查詢工作負(fù)載的結(jié)果中可以發(fā)現(xiàn)，本文算法THEA-CR能夠顯著提高查詢效率。

4 結(jié)束語

基于社交網(wǎng)絡(luò)熱點(diǎn)話題的受歡迎程度與熱度演化規(guī)律，對社交網(wǎng)絡(luò)話題簇實(shí)體的存儲在緩存空間內(nèi)進(jìn)行了有效的熱度對比與置換。首先，對社交網(wǎng)絡(luò)話題簇實(shí)體進(jìn)行劃分;然后通過對緩存錨定目標(biāo)進(jìn)行識別，發(fā)現(xiàn)具有壓縮和緩存置換價(jià)值的數(shù)據(jù)，對其進(jìn)行熱度與優(yōu)先級的判斷;最后，定義話題熱度演化加速度，根據(jù)社交網(wǎng)絡(luò)內(nèi)話題的不斷更新和熱度演化，對緩存空間內(nèi)的數(shù)據(jù)進(jìn)行評估，進(jìn)而動態(tài)分配緩存空間。實(shí)驗(yàn)結(jié)果驗(yàn)證了THEA-CR算法能夠動態(tài)地錨定內(nèi)存中的數(shù)據(jù)，有效地對存儲空間進(jìn)行更新。數(shù)據(jù)表明，THEA-CR算法提高了緩存空間的利用率和圖數(shù)據(jù)的處理速度。

由于社交網(wǎng)絡(luò)圖數(shù)據(jù)的增量和數(shù)據(jù)形式的多樣性，本文算法仍具有一定的局限性。在未來的工作中，筆者將考慮社交網(wǎng)絡(luò)數(shù)據(jù)的圖像等多模態(tài)形式以及存儲機(jī)制的改進(jìn)應(yīng)用。

參考文獻(xiàn)：

[1]侯艷輝，孟帆，王家坤，等.考慮群組結(jié)構(gòu)的在線社交網(wǎng)絡(luò)競爭性輿情信息傳播模型研究［J］.計(jì)算機(jī)應(yīng)用研究，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]鄭鑫.面向分布式圖存儲的圖遍歷框架的設(shè)計(jì)與實(shí)現(xiàn)［D］.成都：電子科技大學(xué)，2022.（Zheng Xin. Design and implementation of graph traversal framework for distributed graph storage［D］.Chengdu：University of Electronic Science and Technology，2022.）

［8]李茜.基于話題生命周期的社交網(wǎng)絡(luò)熱點(diǎn)信息傳播機(jī)制研究［D］.北京：北京郵電大學(xué)，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]陸曄，張偉，李飛，等.一種基于主題時空價(jià)值的服務(wù)器端瓦片緩存算法［J］.浙江大學(xué)學(xué)報(bào)：理學(xué)版，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]湯求毅，王超，杜震洪，等.基于時空老化模型的服務(wù)端瓦片緩存置換算法［J］.浙江大學(xué)學(xué)報(bào)：理學(xué)版，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］.杭州：浙江大學(xué)，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中基于替換率的緩存空間動態(tài)借調(diào)機(jī)制［J］.通信學(xué)報(bào)，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]代繼鵬.基于復(fù)合復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)社區(qū)熱點(diǎn)話題的識別與分析［D］.青島：青島大學(xué)，2021.（Dai Jipeng. Identification and analysis of hot topics in online communities based on complex networks［D］.Qingdao：Qingdao University，2021.）

［25]端祥宇.基于圖嵌入的動態(tài)社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究［D］.徐州：中國礦業(yè)大學(xué)，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

基金項(xiàng)目：中央級公益科研院所基本科研業(yè)務(wù)專項(xiàng)資金項(xiàng)目（MS2023-11）

作者簡介：王大偉（1989-），男（通信作者），山東濰坊人，助理研究員，博士，主要研究方向?yàn)閿?shù)據(jù)庫、雙碳科技、信息領(lǐng)域的前沿跟蹤及監(jiān)測分析研究（wangdw1@istic.ac.cn）；鄭佳（1982-），女，河北唐山人，研究員，博士，主要研究方向?yàn)榭萍颊吲c產(chǎn)業(yè)發(fā)展研究；楊巖（1986-），男，山西忻州人，副研究員，博士，主要研究方向?yàn)榭沙掷m(xù)發(fā)展模型、科技信息可視化研究.