王大偉 鄭佳 楊巖

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

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

中圖分類號(hào)：TP391?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

緩存置換是通過(guò)一些優(yōu)化的指令或者算法，使得計(jì)算程序或者一個(gè)持有硬件的結(jié)構(gòu)能統(tǒng)一、有秩序的管理緩存信息［14～16］。其通常根據(jù)臨時(shí)性、頻率、重用距離、分類等性質(zhì)將其分為粗粒度和細(xì)粒度兩類。典型的緩存置換算法通常被廣泛應(yīng)用于數(shù)據(jù)庫(kù)緩存、網(wǎng)絡(luò)緩存和磁盤(pán)緩存等方面。現(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ì)了動(dòng)態(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)存空間對(duì)用戶熱度話題偏好的管理，并隱性地增加了高熱度話題內(nèi)容在內(nèi)存中的錨定概率。社交網(wǎng)絡(luò)圖數(shù)據(jù)，由消息之間的頻繁轉(zhuǎn)發(fā)等交互操作而形成［6］。針對(duì)某一時(shí)間爆發(fā)的熱點(diǎn)話題，會(huì)出現(xiàn)相關(guān)內(nèi)容的重復(fù)討論，進(jìn)而導(dǎo)致數(shù)據(jù)在存儲(chǔ)過(guò)程中被頻繁讀取。由于社交網(wǎng)絡(luò)中的圖數(shù)據(jù)具有高速更新的特點(diǎn)，所以適用于社交網(wǎng)絡(luò)的置換策略應(yīng)該具備階段性置換的特點(diǎn)。針對(duì)密集圖數(shù)據(jù)面臨的困難，頻繁的磁盤(pán)交互加上極低的磁盤(pán)訪問(wèn)效率，成為了圖數(shù)據(jù)系統(tǒng)性能的瓶頸。為了降低從磁盤(pán)中載入數(shù)據(jù)對(duì)系統(tǒng)性能的影響，現(xiàn)有的處理方式通常分為以下兩種：

a）采用分布式圖處理技術(shù)，將完整的圖數(shù)據(jù)一次性加載到內(nèi)存中實(shí)現(xiàn)內(nèi)存計(jì)算。為了使內(nèi)存的容量能夠達(dá)到計(jì)算需求，通常通過(guò)分布式的方式橫向擴(kuò)展內(nèi)存的總?cè)萘?，但這將引起巨額的硬件成本和復(fù)雜的管理操作。這種方案?jìng)?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)移到外存容量上，通過(guò)縱向擴(kuò)展的方式增大單個(gè)機(jī)器的內(nèi)存容量以及優(yōu)化圖分割算法的處理方式來(lái)處理大規(guī)模的圖數(shù)據(jù)。這種方案僅依賴于一臺(tái)計(jì)算機(jī)就可以完成圖計(jì)算的任務(wù)，同時(shí)避免了分布式計(jì)算的通信開(kāi)銷(xiāo)與硬件的成本開(kāi)銷(xiāo)，因此，更側(cè)重于圖數(shù)據(jù)訪問(wèn)過(guò)程中緩存置換算法的性能與效率優(yōu)化的問(wèn)題。

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

2 THEA-CR算法

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

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

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

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

設(shè)Ep表示描述熱點(diǎn)話題的節(jié)點(diǎn)，Me是Ep中包含的節(jié)點(diǎn)屬性內(nèi)容的長(zhǎng)度、Re表示Ep被轉(zhuǎn)發(fā)的數(shù)量、Ce和Le分別表示Ep獲得的評(píng)論數(shù)和點(diǎn)贊數(shù)。如果消息內(nèi)容的大小超過(guò)32 Byte，則該內(nèi)容數(shù)據(jù)無(wú)法被編碼成為屬性記錄文件的內(nèi)聯(lián)值，在標(biāo)簽屬性圖中需要調(diào)用并占用動(dòng)態(tài)存儲(chǔ)記錄的存儲(chǔ)空間［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）

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

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

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

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

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

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

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

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

其中：設(shè)置K=4，參數(shù)α代表節(jié)點(diǎn)內(nèi)容屬性熱度分布的集中性程度。α取值越大，節(jié)點(diǎn)所代表話題在社交網(wǎng)絡(luò)中的熱度越集中于k取值較小時(shí)的內(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）

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

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

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

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

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

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

2.2 話題熱度演化加速度

本節(jié)分析從磁盤(pán)加載到內(nèi)存中的所有節(jié)點(diǎn)、聯(lián)系等數(shù)據(jù)的受歡迎程度。社交網(wǎng)絡(luò)內(nèi)的熱點(diǎn)數(shù)據(jù)是由被轉(zhuǎn)發(fā)、評(píng)論和點(diǎn)贊的數(shù)量決定的。選擇代表話題的熱度持續(xù)時(shí)間較長(zhǎng)的節(jié)點(diǎn)，并將其錨定在內(nèi)存中，可以減少緩存的頻繁刷新，從而能夠提高命中率。THEA-CR算法考慮話題熱度，對(duì)錨定目標(biāo)進(jìn)行實(shí)時(shí)更新。首先，評(píng)估置換數(shù)據(jù)的優(yōu)先級(jí)。設(shè)置錨定目標(biāo)的優(yōu)先級(jí)最高，向下依次降低。根據(jù)社交網(wǎng)絡(luò)話題簇結(jié)構(gòu)的類型，定義每個(gè)元素的優(yōu)先級(jí)如式（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)先級(jí)對(duì)比決定了緩存中動(dòng)態(tài)置換演化的規(guī)律，將每個(gè)數(shù)據(jù)結(jié)構(gòu)的優(yōu)先級(jí)關(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)話題的傳播時(shí)間通常為一周左右。因此，THEA-CR算法將話題熱度的持續(xù)時(shí)間設(shè)置為一周，表示為T(mén)。熱點(diǎn)話題的熱度維持時(shí)間服從正態(tài)分布或偏態(tài)分布。無(wú)論服從正態(tài)分布還是偏態(tài)分布，在其生命周期T內(nèi)均不是常數(shù)。為了測(cè)量熱度變化狀態(tài)，定義話題熱度演化加速度，計(jì)算如式（6）所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 從磁盤(pán)中加載數(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的使用時(shí)間；

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

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

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

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

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

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)平臺(tái)上，其CPU為3.40 GHz 8-core i7-6700，內(nèi)存為16 GB，并配備ext4文件系統(tǒng)的7200轉(zhuǎn)1 TB容量的西部數(shù)字機(jī)械硬盤(pán)（HDD）。由于HDD只有一個(gè)線程，且僅受I/O的約束，所以在HDD上進(jìn)行了串行實(shí)驗(yàn)，為算法提供了公平有效的實(shí)驗(yàn)平臺(tái)。

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

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

3.2 對(duì)比算法及評(píng)價(jià)指標(biāo)

）對(duì)比算法

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

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

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

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

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

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

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

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

H=∑ni=1βin（7）

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

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

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

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

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

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

3.4.1 緩存命中率對(duì)比與分析

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

[1]侯艷輝，孟帆，王家坤，等.考慮群組結(jié)構(gòu)的在線社交網(wǎng)絡(luò)競(jìng)爭(zhēng)性輿情信息傳播模型研究［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]鄭鑫.面向分布式圖存儲(chǔ)的圖遍歷框架的設(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]陸曄，張偉，李飛，等.一種基于主題時(shí)空價(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]湯求毅，王超，杜震洪，等.基于時(shí)空老化模型的服務(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]湯求毅.顧及時(shí)空與主題特征的分布式遙感影像瓦片緩存方法［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]葛國(guó)棟，郭云飛，蘭巨龍，等.CCN中基于替換率的緩存空間動(dòng)態(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)話題的識(shí)別與分析［D］.青島：青島大學(xué)，2021.（Dai Jipeng. Identification and analysis of hot topics in online communities based on complex networks［D］.Qingdao：Qingdao University，2021.）

［25]端祥宇.基于圖嵌入的動(dòng)態(tài)社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究［D］.徐州：中國(guó)礦業(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)目：中央級(jí)公益科研院所基本科研業(yè)務(wù)專項(xiàng)資金項(xiàng)目（MS2023-11）

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