杜建海， 呂江花,*， 高世偉， 李倩倩， 李勤勇， 馬世龍

(1. 北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院, 北京 100083； 2. 北京航天控制儀器研究所, 北京 100039)

隨著信息技術(shù)的發(fā)展，設(shè)備的自動化測試也越來越完善和便捷，但隨之而來的是測試數(shù)據(jù)的爆炸式增長。特別是在復(fù)雜的安全苛刻系統(tǒng)的綜合測試過程中，如在航天器綜合測試過程中，產(chǎn)生的測試數(shù)據(jù)更是復(fù)雜和龐大。由于其數(shù)據(jù)類型的多樣性和數(shù)據(jù)的多維特征，這些測試數(shù)據(jù)需存放在多個(gè)數(shù)據(jù)表中。對于每個(gè)型號，每年的綜合測試數(shù)據(jù)總量可達(dá)到T數(shù)量級，每個(gè)數(shù)據(jù)表中有上千萬條數(shù)據(jù)。而要很好地管理和維護(hù)這些龐大復(fù)雜的測試數(shù)據(jù)，就給科研人員帶來了許多挑戰(zhàn)。對測試數(shù)據(jù)的查詢是一種最頻繁的應(yīng)用，也是最影響系統(tǒng)性能和管理人員體驗(yàn)的主要要素。為了改善系統(tǒng)性能和用戶體驗(yàn)，需要對數(shù)據(jù)查詢系統(tǒng)的性能進(jìn)行改進(jìn)。

傳統(tǒng)的B/S數(shù)據(jù)查詢系統(tǒng)采用每次查詢都去數(shù)據(jù)庫服務(wù)器中獲取數(shù)據(jù)的方式。一方面，每次查詢都要在整個(gè)數(shù)據(jù)庫中進(jìn)行檢索，查詢范圍很大，造成了較大的延遲，且每次查詢?nèi)?shù)據(jù)庫服務(wù)器獲取數(shù)據(jù)的方式勢必需要在數(shù)據(jù)庫服務(wù)器和應(yīng)用服務(wù)器間反復(fù)傳輸大量相同的數(shù)據(jù)，從而造成了不必要的網(wǎng)絡(luò)負(fù)擔(dān)。另一方面，對于正在測試中的型號，數(shù)據(jù)庫服務(wù)器還需進(jìn)行動態(tài)的海量測試數(shù)據(jù)錄入工作，而每次查詢都檢索數(shù)據(jù)庫的方式對數(shù)據(jù)庫服務(wù)器的訪問過于頻繁，嚴(yán)重影響系統(tǒng)的性能。為了保證服務(wù)器的穩(wěn)定性和數(shù)據(jù)錄入的完整性，降低數(shù)據(jù)查詢對服務(wù)器的資源占用是很重要的。

采用Web緩存解決上述問題是一個(gè)行之有效的方法，Web緩存在改善Web性能方面有很重要的作用。通過將可能再次被訪問的對象放在距離用戶更近的地方的方式，Web緩存可以很好地提高 Web 性能，如減小響應(yīng)時(shí)間、減小網(wǎng)絡(luò)帶寬的使用以及減輕原始服務(wù)器的工作負(fù)載等[1]。同時(shí)，適合特定應(yīng)用環(huán)境的高效緩存替換算法對系統(tǒng)的性能和用戶的體驗(yàn)也將產(chǎn)生極大的影響。緩存替換算法主要以最小化損耗(如總體損耗、平均延時(shí)、失誤率和字節(jié)失誤率)為標(biāo)準(zhǔn)[2]，根據(jù)文獻(xiàn)[3-4]所述，緩存替換算法中設(shè)計(jì)價(jià)值函數(shù)的主要影響因素包括：①訪問頻率:對象被引用的總次數(shù)；②最近訪問時(shí)間：對象被引用的最后一次時(shí)間；③花費(fèi)：從原始服務(wù)器獲取對象所需的資源花費(fèi)；④大?。簩ο蟮拇笮?；⑤過期時(shí)間：對象過期的時(shí)間；⑥修改時(shí)間：對象最近被修改的時(shí)間。

在緩存替換算法中，可以綜合考慮以上影響因素。根據(jù)分析，緩存替換算法主要有5種類型[3]：①基于LRU(Least Recently Used)的算法[5]。這類算法包括LRU、LRU-Threshold、Pitkow/Reckers strategy、SIZE[6]、LRU-Min、EXP1、Value-Aging、HLRU、PSS(Pyramidal Selection Schema)[4]、LRU-LSC、Partitioned LRU等。這類算法的優(yōu)點(diǎn)是較易實(shí)現(xiàn)，且時(shí)間復(fù)雜度低。但簡單的LRU變體沒有很好地考慮對象大小的影響，也沒有考慮訪問頻率的影響。②基于LFU(Least Frequently Used)的算法。這類算法包括LFU、DS-LFU[7]、LFU-Aging、LFU-DA(LFU with Dynamic Aging)[8]、σ-Aging、swLFU等。這類算法需要一個(gè)較為復(fù)雜的緩存管理，同時(shí)還存在緩存污染的問題?？赡芡瑫r(shí)會有多個(gè)對象有相同的頻率計(jì)數(shù)值，在這種情況下，就得需要另外的因素來確定移除哪個(gè)對象。③綜合考慮了最近訪問時(shí)間和訪問頻率兩者的影響，有些算法可能還會加入其他因素。這類算法包括[3]LRFU、SLRU、SF-LRU、Generational Replacement、LRU*、LRU-Hot、LRU-SP、CSS(Cubic Selection Scheme)、HYPER-G等。如果設(shè)計(jì)合理，這類算法就可以避免上述基于訪問頻率的算法和基于最近訪問時(shí)間的算法的缺點(diǎn)。但因?yàn)樘厥獾奶幚磉^程，大部分這類算法會引入額外的復(fù)雜度。只有LRU*和Generational Replacement算法試圖盡量簡單地將頻率和LRU結(jié)合起來，但是它們沒考慮對象大小的影響。④基于函數(shù)的緩存替換算法，這類算法可以通過選擇合適的加權(quán)參數(shù)，來優(yōu)化其性能。這類算法包括GD(Greedy Dual)-Size、GDSF[9]、GD*、Ser-ver-assisted cache replacement、TSP(Taylor Series Prediction)、Bolot/Hoschka’s strategy、MIX、M-Me-tric、HYBRID、LNC-R-W3、LRV、LUV、LR(Logistic Regression)-Model等。它們可以考慮多個(gè)影響因素來處理不同的工作負(fù)載情況。但這類算法的缺點(diǎn)是如何選擇合適的加權(quán)參數(shù)，這是一個(gè)十分困難的任務(wù)。在對函數(shù)值的計(jì)算中可能會引入新的問題。⑤使用隨機(jī)決策來尋找被替換的對象[3]。這類算法包括RAND、HARMONIC、LRU-C[10]、LRU-S、Randomized replacement with general value functions等。這類算法的優(yōu)點(diǎn)是易于實(shí)現(xiàn)，在進(jìn)行插入和刪除對象時(shí)，不需要特殊的數(shù)據(jù)結(jié)構(gòu)。不足之處在于難于進(jìn)行評估，如運(yùn)行在同一個(gè)Web請求跟蹤上的不同仿真實(shí)例的結(jié)果，可能僅存在些細(xì)微的差異。

除了上面給出的傳統(tǒng)緩存替換算法之外，近年來，有些研究者提出了一些“智能的”或者“有適應(yīng)性的”緩存替換算法。例如，文獻(xiàn)[11]提出了一種基于多Markov鏈預(yù)測模型的Web緩存替換算法PGDSF-AI，首先將Web中具有不同瀏覽特征的用戶分為多類,為每一類用戶建立類Markov鏈,進(jìn)一步建立多Markov鏈預(yù)測模型，然后利用該模型對當(dāng)前的用戶請求預(yù)測,進(jìn)而組成預(yù)測對象集，當(dāng)緩存空間不足時(shí),選取鍵值最小且不在預(yù)測對象集中的對象替換。文獻(xiàn)[12]通過語義的方式來增加命中率，利用語義分段、探查查詢、剩余查詢等來描述語義緩存，構(gòu)建了分段感知訪問的動態(tài)語義緩存模型。文獻(xiàn)[13]首先通過Web日志挖掘得到預(yù)測模型，來獲取每個(gè)Web對象將來可能被訪問的頻率，然后將此頻率加入到經(jīng)典Web緩存替換算法GDSF中。同樣，文獻(xiàn)[14]也通過Web挖掘的方式來改進(jìn)Web緩存。文獻(xiàn)[15]給出了3個(gè)基于機(jī)器學(xué)習(xí)的智能Web代理緩存替換算法：SVM-LRU、C4.5-GDS、SVM-GDSF。在常規(guī)的緩存替換算法中加入智能方式，用機(jī)器學(xué)習(xí)的智能來預(yù)測和判斷此Web對象是屬于不會被訪問的對象類還是將要被再次訪問的對象類。

上述幾種算法的共同缺點(diǎn)是：計(jì)算復(fù)雜度和時(shí)間復(fù)雜度較高，同時(shí)占用系統(tǒng)資源也多，且都需要預(yù)先進(jìn)行大數(shù)據(jù)量的訓(xùn)練，才能獲取一定的智能性或者適應(yīng)性，綜合考慮其系統(tǒng)的整體性價(jià)比不高[16]；并且主要是針對是萬維網(wǎng)中的普通用戶訪問Web網(wǎng)頁、多媒體等的情況下。上述算法都有自己的優(yōu)勢以及不足，存在所謂的“足夠好”的緩存替換算法[3,17](在基本性能指標(biāo)上可以取得比較好的結(jié)果)，但是無法給出一種在任何應(yīng)用環(huán)境中都能表現(xiàn)出較好性能的算法[18]，甚至無法給出最好的一些算法[3]。這是因?yàn)榫W(wǎng)絡(luò)環(huán)境是不確定的、動態(tài)的，不同應(yīng)用的不同 Web 訪問特性，以及工作負(fù)載變化不盡相同，且不同緩存系統(tǒng)需要考慮的設(shè)計(jì)因素及設(shè)計(jì)目標(biāo)不盡相同。因此，在設(shè)計(jì)和選擇緩存替換算法時(shí)，需針對具體應(yīng)用的工作負(fù)載變化特點(diǎn)。沒有哪一種緩存替換策略是能夠在任何網(wǎng)絡(luò)情況下都能很好地適應(yīng)的，所以如何使得置換策略能夠依據(jù)不同的訪問特性和網(wǎng)絡(luò)情況采取最適合的緩存替換算法，成為了緩存替換領(lǐng)域研究的熱點(diǎn)[17]。

航天器綜合測試數(shù)據(jù)的特征具有：數(shù)據(jù)量大，數(shù)據(jù)與時(shí)間相關(guān)，時(shí)間密集，數(shù)據(jù)結(jié)構(gòu)復(fù)雜。用戶對數(shù)據(jù)查詢的特征包括：所查詢的數(shù)據(jù)具有很強(qiáng)的時(shí)間局域性，即通常主要查詢某段時(shí)間內(nèi)的數(shù)據(jù)；所查詢的數(shù)據(jù)具有空間局域性，即所訪問的數(shù)據(jù)往往只是數(shù)據(jù)庫中數(shù)據(jù)很小的一部分?jǐn)?shù)據(jù)[19]。而現(xiàn)有的Web緩存替換算法不能很好地適用于如航天器這類安全苛刻系統(tǒng)的綜合測試數(shù)據(jù)查詢系統(tǒng)。對于這類系統(tǒng)，需要設(shè)計(jì)和改進(jìn)一種新的Web緩存替換算法來提高算法的緩存命中率，從而提高數(shù)據(jù)庫服務(wù)器的資源利用率，減輕網(wǎng)絡(luò)負(fù)載，提升系統(tǒng)的整體性能，改善用戶體驗(yàn)，提高用戶工作效率。

本文通過對如航天器這類安全苛刻系統(tǒng)綜合測試數(shù)據(jù)特點(diǎn)和用戶查詢特征的分析，綜合考慮實(shí)際應(yīng)用需求特點(diǎn)，在對現(xiàn)有經(jīng)典Web緩沖替換算法GDSF研究的基礎(chǔ)上，結(jié)合 Web 數(shù)據(jù)流挖掘的相關(guān)技術(shù)和滑動時(shí)間窗口的思想，基于 GDSF算法，設(shè)計(jì)面向安全苛刻系統(tǒng)測試數(shù)據(jù)查詢的緩存替換算法GDSF-STW，并對其進(jìn)行充分的實(shí)驗(yàn)分析，證明了該算法具有更好的性能，占用較少的系統(tǒng)資源，高效且運(yùn)行穩(wěn)定，具有一定的通用性。

1 問題提出

1.1 航天器綜合測試數(shù)據(jù)特點(diǎn)及其查詢特征

航天器綜合測試數(shù)據(jù)庫系統(tǒng)中保存著多種類型的測試數(shù)據(jù)，這些數(shù)據(jù)被存儲在多種類型的數(shù)據(jù)庫表中。典型的航天器綜合測試數(shù)據(jù)表結(jié)構(gòu)示例如表1所示。綜合測試數(shù)據(jù)以時(shí)間為主鍵，存儲了該時(shí)間點(diǎn)上各參數(shù)的值[20-21]。航天器綜合測試數(shù)據(jù)具有以下4個(gè)特點(diǎn)：

1) 數(shù)據(jù)量大。每小時(shí)產(chǎn)生大約20 GB的數(shù)據(jù)，一天數(shù)據(jù)量大約可達(dá)500 GB。對于單個(gè)航天器型號，一年的數(shù)據(jù)總量通常能達(dá)到T數(shù)量級。

2) 數(shù)據(jù)結(jié)構(gòu)復(fù)雜。航天器綜合測試數(shù)據(jù)的數(shù)據(jù)類型繁多，所屬分系統(tǒng)繁多且每個(gè)分系統(tǒng)又有多種參數(shù)，其數(shù)據(jù)結(jié)構(gòu)十分復(fù)雜。這些復(fù)雜的數(shù)據(jù)被存儲于多個(gè)數(shù)據(jù)庫表中。

表1 航天器綜合測試數(shù)據(jù)表結(jié)構(gòu)示例

3) 數(shù)據(jù)與時(shí)間相關(guān)。在數(shù)據(jù)庫中，業(yè)務(wù)數(shù)據(jù)以時(shí)間為主鍵；在邏輯上，數(shù)據(jù)具有時(shí)間相關(guān)性，即對數(shù)據(jù)進(jìn)行查詢分析時(shí)以時(shí)間為檢索條件，強(qiáng)調(diào)一段時(shí)間內(nèi)每個(gè)時(shí)間點(diǎn)上的數(shù)據(jù)情況以及整個(gè)時(shí)間段內(nèi)數(shù)據(jù)的變化趨勢。

4) 時(shí)間密集。每秒一條甚至多條數(shù)據(jù)，其導(dǎo)致即使查詢較短時(shí)間區(qū)間時(shí)，仍有較大的查詢結(jié)果集，如查詢1 h的數(shù)據(jù)則至少有3 600條。

從宏觀上來看，用戶對航天器綜合測試數(shù)據(jù)的查詢具有一定的特征，主要包括在以下4個(gè)方面：

1) 所查詢的數(shù)據(jù)具有很強(qiáng)的時(shí)間局域性。對于階段總結(jié)時(shí)查詢的情況，每天所查詢的數(shù)據(jù)一般局限于之前的測試階段(7～10 d)，通常會按照一定的時(shí)間順序?qū)?shù)據(jù)進(jìn)行總結(jié)分析；對于邊測試邊查詢的情況，其所查尋的數(shù)據(jù)一般局限于當(dāng)天產(chǎn)生的數(shù)據(jù)，且查詢的數(shù)據(jù)區(qū)間會隨著時(shí)間順序的推移而推移。

2) 多次訪問。為了確保測試的準(zhǔn)確性和測試的完備性，每個(gè)數(shù)據(jù)都會被多次訪問。

3) 所查詢的數(shù)據(jù)具有空間局域性。從存儲空間角度來看，雖然數(shù)據(jù)庫服務(wù)器存放當(dāng)前型號到目前為止所有的綜合測試數(shù)據(jù)，而用戶所查詢的數(shù)據(jù)局限在較短的測試時(shí)間內(nèi)，因此所訪問的數(shù)據(jù)是數(shù)據(jù)庫中存儲空間里很小的一部分，即具有空間局域性。

4) 存在一些高頻訪問對象。某些對象可能在一段時(shí)間內(nèi)被訪問的頻率要遠(yuǎn)遠(yuǎn)大于其他對象被訪問的頻率，如對于有問題的地方，會被多人反復(fù)檢查。

1.2 航天器綜合測試數(shù)據(jù)查詢問題分析

在B/S架構(gòu)的Web應(yīng)用查詢系統(tǒng)中，數(shù)據(jù)查詢是“激勵(lì)”式的，即一次前端操作一次響應(yīng)。由于航天系統(tǒng)的保密性要求，其數(shù)據(jù)是不允許備份在前端的普通PC機(jī)上的，同時(shí)由于結(jié)果數(shù)據(jù)集較大，也使得瀏覽器緩存結(jié)果的方式不可行。因此對于每次查詢操作，必須從后臺返回查詢結(jié)果。結(jié)合前面對航天器綜合測試數(shù)據(jù)的特征及用戶查詢特征的分析，為解決多次連接數(shù)據(jù)庫重復(fù)傳輸相同數(shù)據(jù)的問題，從而減小網(wǎng)絡(luò)流量，減輕數(shù)據(jù)庫服務(wù)器的訪問負(fù)載，并保證較好的用戶查詢響應(yīng)時(shí)間，應(yīng)該采用Web服務(wù)器緩存數(shù)據(jù)的方式。對于動態(tài)生成結(jié)果的應(yīng)用環(huán)境，目前的文獻(xiàn)中給出的常用方法并不完全適用于面向?qū)崟r(shí)環(huán)境的航天器綜合測試數(shù)據(jù)查詢。本文采用的方法是：將用戶在一個(gè)工作日內(nèi)所訪問的所有數(shù)據(jù)作為一個(gè)整體，將一個(gè)工作日內(nèi)訪問的數(shù)據(jù)的時(shí)間區(qū)間記為timeInterval=[begin,end]，并將每個(gè)原始數(shù)據(jù)庫表中處于區(qū)間timeInterval內(nèi)的數(shù)據(jù)按整點(diǎn)在邏輯上劃分成不同的小數(shù)據(jù)表，以這些小數(shù)據(jù)表為單位從數(shù)據(jù)庫服務(wù)器獲取數(shù)據(jù)，并將這些小數(shù)據(jù)表作為一個(gè)對象緩存于Web應(yīng)用服務(wù)器上。因此，核心問題是以這些小數(shù)據(jù)庫表作為Web對象，設(shè)計(jì)優(yōu)秀的緩存替換算法，提高系統(tǒng)性能。

根據(jù)緩存在Web中所處位置的不同，Web緩存可分為原始服務(wù)器緩存、Web代理緩存和瀏覽器緩存[22]，如圖1所示。其中，原始服務(wù)器緩存是服務(wù)器本身的緩存，Web代理緩存位于Web代理服務(wù)器上，瀏覽器緩存在用戶端。Web代理服務(wù)器位于原始服務(wù)器和用戶機(jī)之間，接收用戶的請求并向用戶返回請求結(jié)果，Web代理緩存被廣泛應(yīng)用于Web代理服務(wù)器上，其性能的好壞直接影響到Web訪問性能。本文關(guān)注的緩存類型是Web代理緩存。對于安全苛刻系統(tǒng)這類復(fù)雜系統(tǒng)的綜合測試數(shù)據(jù)系統(tǒng)，如航天器綜合測試數(shù)據(jù)系統(tǒng)，目前的文獻(xiàn)中給出的常用方法并不完全適用于面向?qū)崟r(shí)環(huán)境的航天器綜合測試數(shù)據(jù)查詢。因此，設(shè)計(jì)一種優(yōu)秀的緩存替換算法來提高系統(tǒng)的性能具有重要意義。

2 GDSF算法

GDSF算法是目前應(yīng)用最廣泛的緩存替換算法之一，是被公認(rèn)為“足夠好”的緩存替換算法，具有較好的緩存命中率。GDSF算法綜合考慮了Web對象訪問頻率、對象的大小和獲取對象所需的代價(jià)的影響，并且通過老化因子的設(shè)置，將Web訪問的時(shí)間局域性特征對緩存替換的影響很好地融合到了算法中。但GDSF算法不能很好地適應(yīng)數(shù)據(jù)流的快速變化，因而不能取得足夠好的緩存命中率。Web應(yīng)用是典型的數(shù)據(jù)流應(yīng)用[23-24]，在Web數(shù)據(jù)流變化較快的環(huán)境中(如航天器綜合測試數(shù)據(jù)查詢應(yīng)用中)。本文在GDSF算法的基礎(chǔ)上，引入了數(shù)據(jù)流挖掘中在滑動時(shí)間窗口上挖掘頻繁模式所使用的一些方法，提出了GDSF-STW算法，改進(jìn)了GDSF算法的頻率計(jì)數(shù)方法，并引入了過期事務(wù)的概念，使得算法有一定的適應(yīng)性，實(shí)現(xiàn)較好的緩存命中率，提高緩存系統(tǒng)的性能。

GDSF算法使用以下函數(shù)計(jì)算每個(gè)Web對象的特征值：

(1)

式中：I為Web對象；V(I)為Web對象I的特征值；L為老化因子，初始值為0，當(dāng)緩存替換發(fā)生時(shí)，L被賦值為最近一次被替換出去的對象的特征值；ffreq(I)為對象I的頻率計(jì)數(shù)，即該對象在過去的所有訪問請求中被請求的次數(shù)，對象I緩存命中時(shí)，其對應(yīng)的計(jì)數(shù)加1，否則ffreq(I)=1；Size(I)為對象I的大小；Cost(I)為取回對象I所需花費(fèi)的代價(jià)。

當(dāng)需要緩存替換時(shí)，具有最小特征值的對象將會被替換出去。從式(1)可以明顯看出，GDSF算法綜合考慮了對象訪問頻率ffreq(I)、對象大小Size(I)和獲取對象所需的代價(jià)Cost(I)的影響。此外，還考慮了對象訪問的時(shí)間局域性特征。每次緩存命中時(shí)，都會更新對象的特征值V，在發(fā)生緩存替換時(shí)，將老化因子L的值更新為被逐出對象中最大的特征值V，由此可見，老化因子L的值將是逐步遞增的，這就使得最近命中的對象要比那些長時(shí)間沒有訪問到的對象，在特征值的老化因子部分要大，這就將對象訪問的時(shí)間局域性的影響融合到了算法中。但并沒有考慮用戶更關(guān)心的是最近的事務(wù)，而那些很久的事務(wù)對用戶現(xiàn)在所查詢的事務(wù)影響很小了，而對那些較遠(yuǎn)的歷史事務(wù)進(jìn)行處理所需要的資源開銷卻是巨大的。所以，某一時(shí)間段內(nèi)的事務(wù)數(shù)據(jù)可能更重要。而應(yīng)用滑動時(shí)間窗口模型就能夠應(yīng)對數(shù)據(jù)過期的問題。下面給出本文提出的GDSF-STW算法。

3 GDSF-STW算法

3.1 相關(guān)概念

設(shè)C={I1,I2,…,In,…,Im}為數(shù)據(jù)項(xiàng)的集合。

定義1事務(wù)Tj={Ix,Iy,…,Iz}為C的一個(gè)子集，即Tj?C，每個(gè)事務(wù)有一個(gè)標(biāo)識符，稱為TID。事務(wù)中的數(shù)據(jù)項(xiàng)是無序的，可以任何順序排列。

定義2數(shù)據(jù)流DS={T1,T2,…,Tj,…,Tm}由按時(shí)間順序連續(xù)排列的事務(wù)組成，事務(wù)的數(shù)量可能是無限的，且其事務(wù)按時(shí)間到達(dá)的先后順序分配TID，每個(gè)事務(wù)的TID是唯一的。

定義3滑動時(shí)間窗口SW[25-26]是數(shù)據(jù)流DS中最近N(N≥0)個(gè)事務(wù)的序列，事務(wù)在滑動時(shí)間窗口中的先后順序與其在數(shù)據(jù)流DS中的先后順序是一致的。根據(jù)N是可變的還是固定的，可將滑動時(shí)間窗口分為可變長度滑動時(shí)間窗口和固定長度滑動時(shí)間窗口。常用的可變長度滑動時(shí)間窗口主要是基于時(shí)間的滑動時(shí)間窗口，即窗口中保存最近時(shí)間范圍(如1 h)內(nèi)的事務(wù)?？蓪瑒訒r(shí)間窗口進(jìn)行的操作應(yīng)該包括從滑動時(shí)間窗口中刪除最舊的事務(wù)以及向滑動時(shí)間窗口中添加新的事務(wù)，但對于固定長度滑動時(shí)間窗口，當(dāng)窗口中的事務(wù)數(shù)量達(dá)到N之后刪除和插入操作必須是成對進(jìn)行的，可變長度滑動時(shí)間窗口[27]則沒有這方面的限制。

本文對Web點(diǎn)擊流進(jìn)行分析，用戶一次Web點(diǎn)擊所請求的對象的集合用一個(gè)事務(wù)來表示，而集合中的每個(gè)數(shù)據(jù)項(xiàng)用一個(gè)Web對象來表示。所有事務(wù)按請求到達(dá)的先后順序所組成的數(shù)據(jù)流就稱為Web點(diǎn)擊流。

3.2 算法描述

GDSF-STW算法的特征值函數(shù)可以表述為

V(In,Tj)=

(2)

式中：V(In,Tj)為事務(wù)Tj到達(dá)時(shí)對象In的特征值；fd(In,Tj)為事務(wù)Tj到達(dá)時(shí)對象In的衰減支持?jǐn)?shù)；Toldest≤Tj≤Tlast和TjTlast表示滑動時(shí)間窗口，從而引入了過期事務(wù)對算法的影響。

(3)

其中:

Web對象訪問具有時(shí)間局域性，即被訪問的對象距現(xiàn)在越近，將來被訪問的可能性越越大。也就是說，Web點(diǎn)擊流總會隨著時(shí)間的推移發(fā)生變化，最近產(chǎn)生的事務(wù)所蘊(yùn)含的知識通常比歷史事務(wù)中所蘊(yùn)含的知識更有價(jià)值[28]。因此，可采用文獻(xiàn)[29-30]中提出的時(shí)間衰減模型支持?jǐn)?shù)計(jì)算方法來逐步減輕歷史事務(wù)的影響。記數(shù)據(jù)項(xiàng)在單位時(shí)間內(nèi)的衰減比率為衰減因子f(0

3.3 算法流程

在介紹算法流程之前，先給出算法中用到的數(shù)據(jù)結(jié)構(gòu)。

1) 滑動時(shí)間窗口?；跁r(shí)間的滑動時(shí)間窗口用于保存最近可變時(shí)間段time內(nèi)到達(dá)的事務(wù)隊(duì)列?；瑒訒r(shí)間窗口的成員用一個(gè)數(shù)據(jù)結(jié)構(gòu)SwItem來表示，字段包括提交時(shí)間subTime和事務(wù)TID。當(dāng)一個(gè)新的事務(wù)Tj到達(dá)時(shí)，則需要更新滑動時(shí)間窗口，將該事務(wù)的提交時(shí)間及該事務(wù)的TID封裝到SwItem對象，并將其插入隊(duì)列尾部。然后從隊(duì)首開始檢查，刪除所有已經(jīng)過期的事務(wù)。用oldestTid和newestTid分別表示滑動時(shí)間窗口隊(duì)首事務(wù)和隊(duì)尾事務(wù)TID(newestTid減去oldestTid等于滑動時(shí)間窗口的長度time)。

2) 對象信息Hash表fdHash。用來保存Web對象的衰減支持?jǐn)?shù)及相關(guān)的其他信息，以鍵值對的形式表示。以Web對象名稱為主鍵，值是一個(gè)稱為Item_Node的數(shù)據(jù)結(jié)構(gòu)，即。Item_Node包含5個(gè)數(shù)據(jù)域：tid(最近的包含Item_Name對象的事務(wù)TID)、fd(In,Tj)(衰減支持?jǐn)?shù))、size(In)(對象大小)、V(In,Tj)(對象特征值)、Cost(In)(從原始服務(wù)器獲取對象的花費(fèi))。記錄tid是為了判斷過期事務(wù)和計(jì)算對象的衰減支持?jǐn)?shù)。

當(dāng)一個(gè)新的事務(wù)Tj到達(dá)時(shí)，對于該事務(wù)中的每一個(gè)對象In，GDFS-STW算法流程描述如下：

步驟1若對象In緩存命中，即In已存在于緩存中，則更新對象In的衰減支持?jǐn)?shù)fd(In,Tj)=fd(In,Tj)fj-tid+1(f值為1時(shí)表示不衰減)。更新對象In最近被包含的TID：tid=j。使用式(2)更新對象In的特征值V(In,Tj)。Used值保證不變。算法對該對象的處理結(jié)束。

若對象In不存在于緩存中，則對象In的衰減支持?jǐn)?shù)fd(In,Tj)=1；對象In最近被包含的TID：tid=j；使用式(2)計(jì)算對象In的特征值V(In,Tj)；將對象In的相關(guān)信息保存至對象信息Hash表fdHash中；Used=Used+Size(In)。

步驟2若Used≤TotalSize，表示緩存中有足夠的空間保存對象In，此時(shí)直接將對象In存入緩存中，算法對該對象的處理結(jié)束。

若Used>TotalSize，表示緩存空間不夠，此時(shí)需進(jìn)行緩存替換。從對象信息Hash表fdHash中逐個(gè)找出過期對象(對于fdHash中的一個(gè)Item_Node，若Item_Node.tid

步驟3若Used≤TotalSize，說明移除過期對象Ie后，有足夠大的緩存空間存儲對象In。將對象In放入緩存中，算法對該對象的處理結(jié)束。

若Used>TotalSize，說明移除所有的過期對象后，仍沒有足夠的緩存空間存儲對象In。此時(shí)，遍歷對象信息Hash表fdHash，選擇最小的k(k≥1)個(gè)特征值(特征值相同時(shí)優(yōu)先選擇最近包含tid最小的對象)，找到其對應(yīng)的對象I1，I2，…，Ik，它們滿足如下3個(gè)條件：

V(I1,Tj)≤V(I2,Tj)≤…≤V(Ik,Tj)

(4)

(5)

(6)

步驟4老化因子L被賦值為V(I1,Tj)，V(I2,Tj)，…,V(Ik,Tj)中的最大值V(Ik,Tj)，即

(7)

步驟5從緩存中移除對象I1，I2，…，Ik，并按式(8)更新Used的值：

(8)

從對象信息Hash表fdHash中，清除對象I1,I2,…,Ik的相關(guān)信息。

將對象In存入緩存中，算法對該對象的處理結(jié)束。如此循環(huán)，直至對事務(wù)Tj中所有的對象處理完畢后，返回事務(wù)請求的對象集合，算法結(jié)束。

GDSF-STW算法的流程如圖2所示。

GDSF-STW算法使用了數(shù)據(jù)流挖掘中滑動時(shí)間窗口模型的相關(guān)概念。滑動時(shí)間窗口模型的最初靈感來源是：由于內(nèi)存大小有限，保存數(shù)據(jù)流中的所有事務(wù)是不可行的，且對所有歷史事務(wù)進(jìn)行處理的時(shí)間開銷也是不可接受的，而用戶更關(guān)心最近的事務(wù)。應(yīng)用滑動時(shí)間窗口模型能夠應(yīng)對數(shù)據(jù)過期的問題。

4 實(shí)驗(yàn)設(shè)計(jì)及分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

本文中，算法實(shí)驗(yàn)運(yùn)行在DELL臺式機(jī)上，CPU型號為Intel酷睿四核i5，型號7500，CPU頻率為3.4 GHz，4 GB物理內(nèi)存，500 G SATA3硬盤，硬盤轉(zhuǎn)速為7 200 r/min。操作系統(tǒng)為Microsoft Windows 7，實(shí)驗(yàn)中的算法均采用Java語言實(shí)現(xiàn)。

4.1.2 實(shí)驗(yàn)數(shù)據(jù)

本文采用軌跡驅(qū)動[1,31]的方法來對GDSF-STW算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)來源于航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的服務(wù)器所記錄的查詢?nèi)罩拘畔ⅰＳ捎谠嫉牟樵內(nèi)罩拘畔⒅杏行┬畔⒉荒軌驅(qū)ν夤?，且有很多冗余信息需要去除。本文中使用?jīng)過處理的Web查詢?nèi)罩疚募?，文件命名?guī)范為：WebLog_+日志編號，每個(gè)日志文件中存放21條查詢記錄，記錄格式如表2所示。航天器綜合測試數(shù)據(jù)有很多數(shù)據(jù)類型(即數(shù)據(jù)流)，數(shù)據(jù)量巨大，為了方便實(shí)驗(yàn)操作，選取其中一部分具有代表性的數(shù)據(jù)流數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。上述日志文件中，每條記錄代表一次查詢，被看作是一個(gè)事務(wù)，一個(gè)事務(wù)通常需要訪問多個(gè)Web對象。為了方便緩存替換算法處理，將上述日志文件進(jìn)行解析得到事務(wù)文件，每個(gè)日志文件對應(yīng)解析為一個(gè)事務(wù)文件，事務(wù)文件命名格式為：TransactionFlow+對應(yīng)日志文件的編號，每條日志記錄解析為一條事務(wù)記錄，事務(wù)記錄的格式如表3所示。實(shí)驗(yàn)中使用2017-03-10—2017-03-24共15天的日志數(shù)據(jù)，由于日志數(shù)據(jù)統(tǒng)計(jì)信息表占用篇幅過大，此處省略。

表2 日志記錄格式

表3 事務(wù)記錄格式

4.1.3 性能指標(biāo)

常用的衡量緩存性能的指標(biāo)[13,17,32]主要包括命中率 HR(Hit Ratio)、字節(jié)命中率BHR(Byte Hit Ratio)和延遲節(jié)省率 DSR(Delay Saving Radio)。本文使用最常用的命中率HR作為衡量緩存替換算法的性能指標(biāo)。請求的Web對象總數(shù)目用N表示，σi表示第i個(gè)對象是否在緩存中命中，若命中則σi=1，否則σi=0。

命中率HR定義為：在緩存中命中的對象數(shù)與總請求對象數(shù)的百分比，計(jì)算公式為

4.2 實(shí)驗(yàn)分析

從3.2節(jié)的算法描述中可知，GDSF算法與GDSF-STW算法所使用的參數(shù)中，老化因子L、對象的頻率計(jì)數(shù)ffreq(In)、對象的衰減支持?jǐn)?shù)fd(In,Tj)及對象大小Size(In)的定義都很明確，而取回對象所需花費(fèi)代價(jià)Cost(In)的度量比較復(fù)雜，花費(fèi)可以使用從原始服務(wù)器獲取對象的時(shí)間延遲、取回對象需要的經(jīng)濟(jì)花費(fèi)(如一些付費(fèi)的對象和付費(fèi)鏈路)、需要經(jīng)歷的跳數(shù)(hops)等，也可以綜合考慮多種花費(fèi)信息，實(shí)際應(yīng)用中往往是根據(jù)緩存系統(tǒng)的目標(biāo)來定義Cost(In)的值，根據(jù)文獻(xiàn)[33]，如果要使命中率最大化，則定義Cost(In)=1。在航天器綜合測試數(shù)據(jù)查詢中，由于原始數(shù)據(jù)存放于同一臺服務(wù)器，Web服務(wù)器與數(shù)據(jù)服務(wù)器同處于內(nèi)網(wǎng)環(huán)境，因此從原始服務(wù)器取回不同對象的時(shí)間花費(fèi)相差不大，且無需考慮收費(fèi)情況，為了取得較高的命中率，Cost(In)的值被定義為1。下面通過實(shí)驗(yàn)分析衰減因子f及滑動時(shí)間窗口大小STW_SIZE對GDSF-STW算法性能的影響。

4.2.1 命中率與衰減因子的關(guān)系

在考慮衰減因子f對算法性能的影響時(shí)，應(yīng)先屏蔽滑動時(shí)間窗口大小STW_SIZE的影響。根據(jù)航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的實(shí)際查詢特征，用戶每天查詢的時(shí)間通常在8：00—20:30之間，當(dāng)STW_SIZE被設(shè)置為780 min，一天之內(nèi)就不存在過期事務(wù)，即滑動時(shí)間窗口不會發(fā)揮作用。因此本節(jié)實(shí)驗(yàn)中，STW_SIZE被設(shè)置為780 min。文獻(xiàn)[17]顯示，在緩存相對容量達(dá)到20%時(shí)，緩存替換算法可以取得較好的命中率，因此，本節(jié)實(shí)驗(yàn)中，設(shè)置緩存容量TotalSize的相對大小為20%。GDSF-STW算法針對2017-03-10—2017-03-19每天的日志數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，在衰減因子分別設(shè)置為0.94、0.95、0.96、0.97、0.98、0.99、0.991、0.992、0.993、0.994、0.995、0.996、0.997、0.998、0.999、1時(shí)，緩存的命中率HR值如圖3所示?？梢郧逦乜闯雒新孰S衰減因子的變化趨勢。衰減因子取值在0.996～0.997范圍內(nèi)時(shí)，可以取得最好的命中率。衰減因子取值在0.94～0.996時(shí)，命中率隨著衰減因子的增加而遞增。衰減因子取值在0.997～1時(shí)，命中率隨著衰減因子的增加而遞減，平均命中率也呈現(xiàn)相同的規(guī)律。衰減因子對算法命中率的影響比較明顯的主要原因是：航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的用戶所查詢的數(shù)據(jù)具有很強(qiáng)的時(shí)間局域性，而衰減因子可以加速將歷史較久數(shù)據(jù)的特征值減小，從而更好地適應(yīng)航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的用戶查詢特征。

4.2.2 命中率與滑動時(shí)間窗口大小的關(guān)系

通過4.2.1節(jié)的實(shí)驗(yàn)分析可知，衰減因子取值在0.996～0.997范圍內(nèi)時(shí)，GDSF-STW算法可以取得最好的命中率，本節(jié)實(shí)驗(yàn)中，取f=0.996。緩存容量TotalSize仍取總訪問量的20%。本實(shí)驗(yàn)使用2017-03-10—2017-03-19共10天的日志數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。根據(jù)4.2.1節(jié)所述系統(tǒng)的查詢特點(diǎn)，當(dāng)STW_SIZE大于或等于780 min，系統(tǒng)不存在過期事務(wù)，因此，本實(shí)驗(yàn)取STW_SIZE分別為780、720、660、600、540、480、420、360、300、240、180、120、60、30、20、10、9、8、7、6、5、4、3、2 min。圖4為命中率與滑動時(shí)間窗口大小的關(guān)系曲線。可以明顯看出，滑動時(shí)間窗口大小在600 min遞減至8 min的過程中，GDSF-STW算法都能取得較好的命中率，且性能指標(biāo)保持穩(wěn)定。當(dāng)滑動時(shí)間窗口大于600 min，命中率下降，說明通過添加滑動時(shí)間窗口來判斷過期事務(wù)，在一定程度上可以提高算法的性能指標(biāo)。當(dāng)滑動時(shí)間窗口小于2 min時(shí)，命中率變得極不穩(wěn)定，迅速下降。這是因?yàn)闀r(shí)間過短，許多與用戶正在查詢的事務(wù)有關(guān)的其他事務(wù)也被過早地扔出去了；而當(dāng)滑動時(shí)間窗口大小達(dá)到8 min時(shí)，GDSF-STW算法就能取得較好的命中率，且性能指標(biāo)保持穩(wěn)定。這說明航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的用戶查詢某相關(guān)事務(wù)的時(shí)間一般會維持在2 min以上、8 min以下，且經(jīng)常在某一小段時(shí)間內(nèi)存在一些高頻訪問對象?；瑒訒r(shí)間窗口在600 min遞減至8 min的過程中，命中率指標(biāo)保持穩(wěn)定狀態(tài)，這是因?yàn)橐淮问聞?wù)查詢中通常涉及到很多的對象，因此較短時(shí)間范圍內(nèi)的事務(wù)中便包含了大多數(shù)的對象，這樣就使得較短時(shí)間范圍內(nèi)有較多對象為非過期對象。而在較小的滑動時(shí)間窗口情況下，算法所需的存儲空間和需要被存儲事務(wù)數(shù)量都較少，從而可以降低算法的空間復(fù)雜度，因此在保證算法性能基本不變的前提下，應(yīng)盡量選擇較小的時(shí)間窗口。從圖4可以看出，滑動時(shí)間窗口大小為10 min時(shí)，此時(shí)間點(diǎn)的前后算法性能均很穩(wěn)定，因此對于航天器綜合測試數(shù)據(jù)查詢系統(tǒng)中的特征，滑動時(shí)間窗口大小可選擇為10 min。

4.2.3 命中率與緩存容量的關(guān)系

根據(jù)4.2.1節(jié)和4.2.2節(jié)對GDSF-STW算法不同參數(shù)的實(shí)驗(yàn)分析，本節(jié)實(shí)驗(yàn)中，設(shè)置滑動時(shí)間窗口大小為10 min，衰減因子f=0.996，分別對緩存容量1%、2%、3%、4%、5%、10%、15%、20%、25%、30%進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)使用的日志數(shù)據(jù)為2017-03-20—2017-03-24共5天的日志記錄。由圖5看出，命中率隨著緩存容量的增加快速增加，當(dāng)緩存相對容量達(dá)到30%時(shí)，命中率可超過0.7。

4.2.4 與其他算法對比

本節(jié)實(shí)驗(yàn)中，設(shè)置GDSF-STW算法中的滑動時(shí)間窗口大小為10 min，衰減因子f=0.996。實(shí)驗(yàn)中使用的日志數(shù)據(jù)為2017-03-20—2017-03-24共5天的日志記錄。分別對GDSF-STW、GDSF、LFU、LFU-DA、LRU設(shè)置緩存容量為1%、2%、3%、4%、5%、10%、15%、20%、25%、30%進(jìn)行實(shí)驗(yàn)。圖6為各算法命中率隨緩存容量變化的曲線。因?yàn)獒槍教炱骶C合測試數(shù)據(jù)查詢系統(tǒng)的用戶查詢特征引入了衰減因子和滑動時(shí)間窗口機(jī)制，所以從圖中可以看出，GDSF-STW算法的命中率優(yōu)于其他算法。

5 結(jié) 論

本文針對航天器綜合測試數(shù)據(jù)查詢系統(tǒng)中數(shù)據(jù)的特征，分析了用戶的查詢特征，在充分調(diào)研了國內(nèi)外緩存技術(shù)研究進(jìn)展的前提下，結(jié)合Web數(shù)據(jù)流挖掘的相關(guān)技術(shù)，設(shè)計(jì)了一個(gè)面向航天器綜合測試數(shù)據(jù)查詢系統(tǒng)的緩存替換算法——GDSF-STW。

1) 給出了算法實(shí)現(xiàn)的具體流程，并使用實(shí)際運(yùn)行環(huán)境中的查詢?nèi)罩居涗洈?shù)據(jù)，進(jìn)行了軌跡驅(qū)動的仿真實(shí)驗(yàn)。

2) 進(jìn)行了充分的實(shí)驗(yàn)分析，并與現(xiàn)有的典型緩存替換算法進(jìn)行實(shí)驗(yàn)對比，證明了本文算法具有更好的性能。

進(jìn)一步的主要工作有：①采用DEA(Data Envelopment Analysis)方法對算法的有效性進(jìn)行系統(tǒng)性評估研究；②收集除航天器綜合測試數(shù)據(jù)外的其他領(lǐng)域數(shù)據(jù)，如股票交易、視頻網(wǎng)站、新聞網(wǎng)站等一些數(shù)據(jù)量大、變化快且大眾用戶更關(guān)心的最新數(shù)據(jù)變化情況的應(yīng)用，探討本文提出的GDSF-STW算法在這些領(lǐng)域數(shù)據(jù)的應(yīng)用和擴(kuò)展。