基于時(shí)空老化模型的服務(wù)端瓦片緩存置換算法

湯求毅，王超，杜震洪*，張豐，劉仁義

（1.浙江大學(xué)浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310028； 2.浙江大學(xué)地理信息科學(xué)研究所，浙江杭州 310027）

0 引 言

近年來，隨著遙感影像數(shù)據(jù)量的快速增長(zhǎng)，網(wǎng)絡(luò)地理信息服務(wù)（network geographic information service，NGIS）逐漸向云服務(wù)發(fā)展［1-3］，進(jìn)一步促使NGIS 提供高效實(shí)時(shí)的遙感影像預(yù)覽、可視化及漫游服務(wù)。由于遙感影像單幅數(shù)據(jù)量過大，不適合在網(wǎng)絡(luò)中頻繁傳輸，在實(shí)際應(yīng)用中往往用瓦片實(shí)現(xiàn)可視化［4］，因此，高效、實(shí)時(shí)的瓦片服務(wù)是支撐高性能NGIS 的基礎(chǔ)技術(shù)之一。然而，數(shù)據(jù)量和用戶量的激增，導(dǎo)致瓦片服務(wù)器服務(wù)過載，造成瓦片服務(wù)的延遲與低效［4-5］。瓦片緩存可以減少對(duì)瓦片服務(wù)器直接訪問的頻率，減輕瓦片服務(wù)器的壓力。目前，瓦片緩存架構(gòu)主要分為客戶端緩存和服務(wù)端緩存2 種，由于前者在云環(huán)境下存在應(yīng)用局限性［6］，Google Earth 建議使用服務(wù)端緩存解決瓦片服務(wù)延遲的問題［7］。良好的緩存置換算法可以有效提高緩存命中率［5，8］，進(jìn)一步減輕瓦片服務(wù)器壓力，因此，設(shè)計(jì)高命中率的瓦片緩存置換算法成為當(dāng)前研究的熱點(diǎn)和難點(diǎn)［9］。

瓦片緩存置換算法的設(shè)計(jì)需要考慮瓦片訪問模式和瓦片數(shù)據(jù)特征［10］。瓦片數(shù)據(jù)在訪問模式上存在短期流行度和長(zhǎng)期流行度［7，11-12］，能反映瓦片的訪問趨勢(shì)。短期流行度可通過瓦片訪問的時(shí)間局部性和空間局部性進(jìn)行表達(dá)［13］。時(shí)間局部性是指近期被訪問過的瓦片被再次訪問的概率更高，空間局部性是指與當(dāng)前被訪問瓦片相鄰的瓦片被訪問的概率更高，時(shí)間局部性和空間局部性相互關(guān)聯(lián)、相互影響，對(duì)外統(tǒng)一表現(xiàn)為時(shí)間局部性［7，11］。長(zhǎng)期流行度可通過瓦片訪問熱度，即瓦片的累計(jì)訪問頻次表達(dá)［4，14-15］，熱度值高的瓦片被再次訪問的概率更高［4］。瓦片數(shù)據(jù)特征包含瓦片大小特征、瓦片主題特征等，瓦片大小特征是指不同的瓦片存在大小差異。由于緩存過程中大文件越多，緩存命中率越低［16］，因此瓦片大小特征也是不可忽略的因素。

國(guó)內(nèi)外學(xué)者基于瓦片訪問模式和瓦片數(shù)據(jù)特征，對(duì)瓦片緩存置換算法開展了大量研究。LEE等［17］提出了基于馬爾可夫鏈的瓦片緩存預(yù)取和置換算法，通過置入預(yù)取概率高的瓦片，置換出轉(zhuǎn)移概率低的瓦片。王浩等［14］提出了基于瓦片存活壽命和訪問熱度的緩存置換算法，通過計(jì)算瓦片平均存活時(shí)間得到瓦片年齡，并置換出年齡最高的瓦片緩存。涂振發(fā)等［18］提出了基于瓦片數(shù)據(jù)價(jià)值的緩存置換算法，綜合考慮時(shí)間價(jià)值、空間價(jià)值和數(shù)據(jù)大小價(jià)值對(duì)瓦片數(shù)據(jù)價(jià)值進(jìn)行定義，并置換出價(jià)值最小的瓦片緩存。ULUAT 等［19］基于模糊邏輯的推理引擎，提出了一種基于優(yōu)先級(jí)的瓦片預(yù)測(cè)方法。LI等［20］對(duì)用戶進(jìn)行分組，研究了基于不同用戶組訪問密集性的瓦片緩存置換算法。劉佳星等［15］利用瓦片金字塔特性，提出了基于地理單元熱度的瓦片緩存置換算法。這些算法結(jié)合時(shí)空特性定義了各自瓦片價(jià)值模型，并根據(jù)價(jià)值大小置換瓦片，在一定程度上提高了緩存命中率［4］。但這些算法在應(yīng)用于服務(wù)端瓦片緩存時(shí)還存在以下問題：（1）相較于傳統(tǒng)的緩存置換算法，上述算法的復(fù)雜性高、效率低，不適合大量瓦片緩存置換的應(yīng)用場(chǎng)景；（2）大多數(shù)為客戶端緩存置換算法，不適合基于網(wǎng)絡(luò)的服務(wù)端瓦片緩存置換場(chǎng)景；（3）重點(diǎn)分析了瓦片訪問對(duì)水平相鄰?fù)咂挠绊懀纯紤]對(duì)其上下層瓦片的影響；（4）未考慮瓦片大小差異對(duì)緩存命中率的影響。

老化算法原本用于頁(yè)面緩存置換，同時(shí)具備最近最少使用（least recently used，LRU）和最不經(jīng)常使用（least frequently used，LFU）2 種算法的優(yōu)點(diǎn)，在短期流行度擬合和運(yùn)行性能方面具備優(yōu)勢(shì)，且具擴(kuò)展性和移植性［21-22］。本文將老化算法引入服務(wù)端瓦片緩存置換場(chǎng)景，綜合瓦片訪問的長(zhǎng)短期流行度和瓦片大小特征對(duì)老化算法進(jìn)行改造，提出時(shí)空老化模型，并設(shè)計(jì)了基于時(shí)空老化模型的服務(wù)端瓦片緩存置換算法（server-side cache replacement algorithm based on spatiotemporal aging model for tiles，SSAT），具有以下優(yōu)勢(shì)：（1）運(yùn)行效率高，適用于大量瓦片緩存置換場(chǎng)景；（2）可更好地?cái)M合瓦片訪問的時(shí)間局部性；（3）兼顧瓦片訪問對(duì)水平和垂直2 個(gè)空間維度的影響，更全面地體現(xiàn)其空間局部性；（4）顧及瓦片大小特征，進(jìn)一步提高瓦片緩存命中率。

1 基于時(shí)空老化模型的服務(wù)端瓦片緩存置換算法

1.1 老化算法

老化算法是一種操作系統(tǒng)頁(yè)面緩存置換算法［22］，其數(shù)據(jù)結(jié)構(gòu)和工作流程如圖1 所示。R 位用于標(biāo)記頁(yè)面在時(shí)鐘周期內(nèi)的引用情況，若頁(yè)面被引用，則將R 位設(shè)置為1，若頁(yè)面進(jìn)入新的時(shí)鐘周期，則將R 位設(shè)置為0。計(jì)數(shù)器C 用于記錄頁(yè)面在各時(shí)鐘周期內(nèi)的訪問情況，值越大，表示該頁(yè)面被訪問時(shí)間間隔越短［23］。計(jì)數(shù)器的長(zhǎng)度一般取決于處理器的位數(shù)，老化表是所有計(jì)數(shù)器的集合。

假設(shè)緩存中有頁(yè)面P1、P2和P3。在初始時(shí)刻，3個(gè)頁(yè)面的R 位和計(jì)數(shù)器C 均為0。假設(shè)在時(shí)鐘周期T1內(nèi)，只有P1和P3被引用，則需將R1和R3設(shè)置為1。當(dāng)時(shí)鐘從T1進(jìn)入T2時(shí)，先如圖1 中黃色箭頭所示，將所有計(jì)數(shù)器C1、C2、C3右移一位，接著如圖1 中綠色箭頭所示，將R1、R2、R3分別設(shè)置為計(jì)數(shù)器的最高位，最后將R1、R2、R3重新設(shè)置為0。算法在時(shí)鐘周期T3、T4、T5內(nèi)的操作過程相同。

圖1 老化算法工作流程Fig.1 Aging algorithm workflow

當(dāng)內(nèi)存不足時(shí)，老化算法會(huì)根據(jù)計(jì)數(shù)器C 的大小置換頁(yè)面［23］。C 越大，其高位為1 的概率越大，表明其被訪問的時(shí)間間隔越短。假設(shè)在T5內(nèi)需要進(jìn)行緩存置換，算法會(huì)根據(jù)計(jì)數(shù)器C1、C2、C3的大小，找出最小值C2，并置換出其對(duì)應(yīng)頁(yè)面的P2緩存。老化算法的優(yōu)點(diǎn)是，最新引用的頁(yè)面比頻繁引用的頁(yè)面具有更高的優(yōu)先級(jí)［24］。

頁(yè)面緩存置換算法只需要考慮時(shí)間局部性［22］，而瓦片數(shù)據(jù)有空間局部性和大小差異，因此在應(yīng)用時(shí)需要對(duì)老化算法進(jìn)行擴(kuò)展。

1.2 時(shí)空老化模型

時(shí)空老化模型以老化算法的計(jì)數(shù)器周期性移位為基準(zhǔn)，綜合考慮瓦片訪問長(zhǎng)短期流行度和瓦片大小，并將其作為比重進(jìn)行調(diào)節(jié)，得到瓦片時(shí)空老化程度，記為V（ssat）。當(dāng)緩存空間不足時(shí)，SSAT 會(huì)置換出V（ssat）最低的瓦片緩存。時(shí)空老化模型的表達(dá)式為

V（ssat）=V（age）?（V（heat）+V（size）），（1）其中，?為右移運(yùn)算符，V（age）為瓦片時(shí)間老化程度，V（heat）為瓦片空間訪問熱度價(jià)值，V（size）為瓦片大小價(jià)值。V（heat）和V（size）通過影響V（age）右移的方式參與調(diào)節(jié)。

1.2.1 瓦片時(shí)間老化程度

老化算法在原理上利用了時(shí)間局部性［24］，因此直接用老化表計(jì)數(shù)器值表示瓦片訪問的短期流行度，定義如下：

定義1 瓦片老化表。每張瓦片各自對(duì)應(yīng)一個(gè)32 位的計(jì)數(shù)器，瓦片老化表是計(jì)數(shù)器的集合。

定義2 瓦片老化時(shí)鐘周期。與老化算法的時(shí)鐘周期相對(duì)應(yīng)，記為T。每經(jīng)過時(shí)間T，瓦片老化表中每個(gè)計(jì)數(shù)器的值右移一位。

定義3 瓦片時(shí)間老化程度。可用計(jì)數(shù)器的值表示，值越小，表示瓦片時(shí)間老化程度越高。

1.2.2 瓦片空間訪問熱度價(jià)值

空間位置相鄰的瓦片，在訪問時(shí)間上也傾向于相鄰?fù)咂Ｕ_定義單張瓦片影響的鄰域空間范圍，是提高瓦片緩存命中率的關(guān)鍵。因此，定義如下：

定義4 瓦片水平鄰域。以被訪問的瓦片為中心，在同層中與該瓦片直接相鄰的8 張瓦片。

定義5 瓦片垂直鄰域。在下一層級(jí)中，由被訪問的瓦片分裂得到的4 張瓦片。

定義6 瓦片空間訪問熱度權(quán)重。由于瓦片訪問存在空間局部性，瓦片空間訪問熱度權(quán)重表示被訪問瓦片對(duì)其水平鄰域和垂直鄰域的影響程度，記為vol。

定義7 瓦片空間訪問熱度。可用瓦片的累計(jì)被訪問頻次表示，記為heat。當(dāng)瓦片被訪問命中后，每增加1 heat，其水平鄰域和垂直鄰域中的瓦片heat增加vol，計(jì)算過程如圖2 所示。

圖2 瓦片水平鄰域和瓦片垂直鄰域Fig.2 Tile horizontal neighborhood and vertical neighborhood

定義8 瓦片空間訪問熱度價(jià)值。由瓦片空間訪問熱度進(jìn)行歸一化處理得到。在調(diào)節(jié)V（age）的過程中，heat 不同的瓦片之間應(yīng)體現(xiàn)出適當(dāng)?shù)牟罹啵虼耍xV（heat）：

其中，maxHeat 為緩存中最大的瓦片空間訪問熱度，Me 為緩存中所有heat 的中位數(shù)。設(shè)置Me 是為了避免當(dāng)heat 與maxHeat 相差較大時(shí)，對(duì)V（age）產(chǎn)生過大的移位影響。假設(shè)緩存中有3 張瓦片A，B和C，其heat 分別為1 000，500 和10，緩存中maxHeat 為10 000，Me 為100。 此時(shí)瓦片A 的V（heat）≈3，瓦片B 的V（heat）≈4，在時(shí)空老化模型中，瓦片A 將影響V（age）右移3 位，瓦片B 將影響V（age）右移4 位，即heat 值相差2 倍的瓦片，相當(dāng)于一個(gè)瓦片時(shí)鐘周期沒有被訪問。而瓦片C 的heat 與maxHeat 相差1 000 倍，若直接用heat 計(jì)算，將得到V（heat）≈9，這對(duì)于32 位的V（age）來說，產(chǎn)生的移位影響過大，會(huì)造成V（age）信息丟失。若取heat=Me，則得到V（heat）≈6，這既體現(xiàn)了差距，又避免了對(duì)V（age）信息產(chǎn)生移位污染。總的來說，V（heat）的計(jì)算方式可以滿足應(yīng)用需求。

1.2.3 瓦片大小價(jià)值

遙感影像金字塔瓦片的大小可能相差近百倍，如果小瓦片擁有更高的優(yōu)先級(jí)，則會(huì)提高瓦片緩存命中率［22］。將不同大小的瓦片所對(duì)應(yīng)的優(yōu)先級(jí)稱為瓦片大小價(jià)值，記為V（size）。與V（heat）的作用類似，V（size）也是以移位的形式對(duì)老化表計(jì)數(shù)器進(jìn)行調(diào)節(jié)。在調(diào)節(jié)過程中，大小不同的瓦片之間應(yīng)該體現(xiàn)出適當(dāng)?shù)牟罹唷６xV（size）為

1.3 基于老化算法的服務(wù)端瓦片緩存索引

在運(yùn)行過程中，緩存服務(wù)器可逐漸保存大量瓦片。當(dāng)客戶端的請(qǐng)求到達(dá)緩存服務(wù)器時(shí)，需要高效的索引機(jī)制，檢索其是否存在目標(biāo)瓦片。根據(jù)瓦片服務(wù)的統(tǒng)一資源定位符（uniform resource locator，URL）規(guī)則，參照老化算法原理設(shè)計(jì)了一種以瓦片為粒度的緩存索引方法，如圖3 所示。

圖3 服務(wù)端瓦片緩存索引結(jié)構(gòu)Fig.3 Server-side tile cache index structure

該索引方法基于鍵值對(duì)的哈希索引結(jié)構(gòu)，對(duì)URL 中的level、row 和col 進(jìn)行CityHash64 編碼，將得到的64 位散列值作為哈希鍵（HashKey），對(duì)應(yīng)的哈希值（HashValue）包括瓦片信息（tileNode）、R 位（referenceBit）、計(jì)數(shù)器（counter）、空間訪問熱度值（tileSpatailHeat）和瓦片大小（size）。

1.4 SSAT 流程

SSAT 在執(zhí)行過程中需要陸續(xù)啟動(dòng)一個(gè)程序主線程和2 個(gè)工作線程。程序主線程隨緩存服務(wù)器的啟動(dòng)而啟動(dòng)，負(fù)責(zé)初始化算法運(yùn)行環(huán)境。工作線程包括定時(shí)器線程和瓦片請(qǐng)求響應(yīng)線程，定時(shí)器線程主要負(fù)責(zé)瓦片老化表周期性移位；瓦片請(qǐng)求響應(yīng)線程主要負(fù)責(zé)處理客戶端的瓦片訪問請(qǐng)求、查詢瓦片緩存以及置入、換出瓦片等，步驟如下。

（1）啟動(dòng)瓦片緩存服務(wù)器主程序，建立緩存索引和瓦片老化表，設(shè)置瓦片老化時(shí)鐘周期T，創(chuàng)建定時(shí)器線程，監(jiān)聽用戶請(qǐng)求；

（2）執(zhí)行定時(shí)器線程周期，每經(jīng)過一個(gè)T，先將所有計(jì)數(shù)器的值右移一位，再將瓦片的R 位置于計(jì)數(shù)器的最高位，最后將所有的R 位清零；

（3）當(dāng)收到瓦片請(qǐng)求時(shí)，瓦片請(qǐng)求響應(yīng)線程啟動(dòng)，對(duì)URL 的level、row、col 進(jìn)行編碼，并通過編碼值查找緩存索引，若命中，則轉(zhuǎn)至步驟（6），否則，轉(zhuǎn)至步驟（4）；

（4）根據(jù)level、row、col 信息，從磁盤上讀取目標(biāo)瓦片，同時(shí)返回請(qǐng)求；

（5）判斷緩存剩余空間是否充足，若充足，則將命中的瓦片直接放入緩存，創(chuàng)建索引，然后轉(zhuǎn)至步驟（6）；否則，轉(zhuǎn)至步驟（7）；

（6）將命中瓦片的R 位設(shè)置為1，空間訪問熱度值增加1，同時(shí)將緩存中存在的該瓦片水平鄰域和垂直鄰域中其他瓦片的空間訪問熱度值增加vol；

（7）當(dāng)緩存空間不足時(shí)，先按照時(shí)空老化模型計(jì)算每個(gè)瓦片的V（ssat），再置換V（ssat）最小的瓦片，刪除緩存索引，直至空間充足。

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)過程

實(shí)驗(yàn)數(shù)據(jù)為谷歌地圖瓦片，整套瓦片共21 層（最高為0 層，最低為20 層），共6 077 501 張、6.84 GB，其中最大的瓦片為1 492 KB，最小的瓦片為6 KB。實(shí)驗(yàn)使用了3 臺(tái)配置為Windows Server 2012 操作系統(tǒng)，Intel（R）Core（TM）i7-8750H CPU @2.2 GHz，512 GB SSD 和8 GB RAM 的服務(wù)器。

實(shí)驗(yàn)過程遵循控制變量法，（1）設(shè)置最大可用緩存空間為500 MB，并以50 MB 為間隔設(shè)置10 個(gè)不同的緩存空間；（2）不使用緩存直接訪問瓦片服務(wù)，生成152 841 條瓦片請(qǐng)求日志，提取日志中的瓦片層級(jí)、行列號(hào)和請(qǐng)求時(shí)間，生成瓦片訪問次序列表；（3）按照列表順序，依次訪問瓦片緩存服務(wù)，統(tǒng)計(jì)總訪問次數(shù)、請(qǐng)求命中次數(shù)、訪問時(shí)長(zhǎng)等信息。

2.2 實(shí)驗(yàn)結(jié)果與分析

在SSAT 中，需要設(shè)置瓦片時(shí)鐘周期T和瓦片空間訪問熱度權(quán)重vol。本文在緩存空間為500 MB的條件下進(jìn)行實(shí)驗(yàn)，分別記錄了T和vol 對(duì)緩存命中率的影響，結(jié)果如圖4 所示。由圖4（a）可知，SSAT的緩存命中率隨T的增大呈現(xiàn)先減小后保持不變的特征，其主要原因是，T增大，表示老化表周期性移位的時(shí)間間隔增大，進(jìn)而造成瓦片在單個(gè)時(shí)鐘周期內(nèi)被訪問的概率增加。由于R 位僅能表示某個(gè)周期內(nèi)瓦片是否被訪問，無法表示瓦片被訪問頻次，T增大會(huì)使各瓦片在V（age）上的差異減小，因此緩存命中率減小。當(dāng)T＞45 s 時(shí)，V（age）不再是主要影響因子，因此，緩存命中率不隨T的變化而變化。

由圖4（b）可知，SSAT 的緩存命中率隨vol 的增大呈現(xiàn)先增大后減小的特征，其主要原因是，瓦片訪問會(huì)使目標(biāo)瓦片空間訪問熱度增加，當(dāng)vol＜0.3 時(shí)，瓦片訪問命中對(duì)周圍瓦片的影響較小，V（heat）不會(huì)對(duì)V（age）產(chǎn)生有效的移位影響，因此緩存命中率較低且變化不明顯；隨著vol 的增大，瓦片訪問命中對(duì)周圍瓦片的影響增大，V（heat）對(duì)V（age）產(chǎn)生有效的移位影響，因此緩存命中率不斷增大；當(dāng)vol＞1時(shí)，訪問命中使周圍瓦片獲得的熱度大于被命中瓦片自身獲得的熱度，V（heat）對(duì)V（age）產(chǎn)生的移位影響過大，因此緩存命中率不斷減小。

圖4 瓦片時(shí)鐘周期和瓦片空間訪問熱度權(quán)重值對(duì)SSAT 緩存命中率的影響Fig.4 Impact of T and vol on cache hit ratio of SSAT

綜合實(shí)驗(yàn)結(jié)果，當(dāng)T=10 s，vol=1 時(shí)，請(qǐng)求命中率和字節(jié)命中率最高，因此，選擇該組合值作為SSAT 算法的實(shí)驗(yàn)參數(shù)。

圖5 展示了在同時(shí)設(shè)置V（heat）和V（size）、僅設(shè)置V（heat）、僅設(shè)置V（size）3 個(gè)條件下，SSAT 的請(qǐng)求命中率和字節(jié)命中率隨緩存空間的變化。可知，隨著緩存空間的增大，SSAT 在3 種條件下的請(qǐng)求命中率和字節(jié)命中率均不斷增大，且增長(zhǎng)趨勢(shì)大致相同。在不同的緩存空間中，同時(shí)設(shè)置V（heat）和V（size）的SSAT 所得請(qǐng)求命中率和字節(jié)命中率最大；僅設(shè)置V（heat）的SSAT 所得請(qǐng)求命中率和字節(jié)命中率下降約22%；僅設(shè)置V（size）的SSAT所得請(qǐng)求命中率和字節(jié)命中率下降約43%。結(jié)果表明，瓦片空間訪問熱度價(jià)值和瓦片大小價(jià)值能有效提高SSAT 的緩存命中率。

圖5 在3 種條件下SSAT 的請(qǐng)求命中率和字節(jié)命中率隨緩存空間的變化Fig.5 Changes of request hit ratio and byte hit ratio of SAAT with cache space under three conditions

圖6（a）和（b）分別為SSAT、LRU、LFU、先進(jìn)先出（first in first out，F(xiàn)IFO）4 種算法的請(qǐng)求命中率和字節(jié)命中率隨緩存空間的變化。可知，當(dāng)緩存空間為100 MB 時(shí)，4 種算法均表現(xiàn)出小于7%的請(qǐng)求命中率和小于10% 的字節(jié)命中率。當(dāng)緩存空間為500 MB 時(shí)，4 種算法的緩存命中率顯著提高，其中請(qǐng)求命中率分別為73%，65%，55%和44%，字節(jié)命中率分別為76%，66%，56%和47%。圖6（c）和（d）分別為4 種算法在不同緩存空間下的請(qǐng)求命中增長(zhǎng)率和字節(jié)命中增長(zhǎng)率。當(dāng)緩存空間小于100 MB時(shí)，4 種算法的請(qǐng)求命中增長(zhǎng)率和字節(jié)命中增長(zhǎng)率均較低，其中SSAT 每MB 的請(qǐng)求命中增長(zhǎng)率和字節(jié)命中增長(zhǎng)率分別為0.06%和0.07%。在緩存空間為100～300 MB 時(shí)，4 種算法每MB 的請(qǐng)求命中率和字節(jié)命中率迅速增加，命中增長(zhǎng)率均大于0.15%，其中SSAT 的請(qǐng)求命中增長(zhǎng)率和字節(jié)命中增長(zhǎng)率每MB 分別達(dá)0.24%和0.23%。當(dāng)緩存空間為300～500 MB 時(shí)，緩存空間對(duì)命中增長(zhǎng)率的影響降低，因此4 種算法每MB 的命中增長(zhǎng)率再次趨于平緩，平均降至0.05% 左右。總的來說，在不同緩存空間下，SSAT 的緩存命中率及命中增長(zhǎng)率均最高，且隨緩存空間的增大緩存命中率優(yōu)勢(shì)更加顯著。

圖6 4 種算法的緩存命中率及命中增長(zhǎng)率隨緩存空間的變化Fig.6 Changes of tile request hit ratio，tile byte hit ratio and their growth of four algorithms with cache space

瓦片平均訪問時(shí)長(zhǎng)和平均訪問時(shí)長(zhǎng)節(jié)省率可以直觀地體現(xiàn)瓦片服務(wù)的性能。平均訪問時(shí)長(zhǎng)越短，平均訪問時(shí)長(zhǎng)節(jié)省率越高，則訪問延遲率越低。圖7 為4 種算法在不同緩存空間下的瓦片平均訪問時(shí)長(zhǎng)及其節(jié)省率，可知，4 種算法的平均訪問時(shí)長(zhǎng)隨緩存空間的增大而減小，平均訪問時(shí)長(zhǎng)節(jié)省率隨緩存空間的增大而增大。當(dāng)緩存空間大于300 MB 時(shí)，緩存置換算法可有效縮短瓦片請(qǐng)求的平均訪問時(shí)長(zhǎng)，降低延遲率，且SSAT 的延遲率最低。

圖7 4 種算法的平均訪問時(shí)長(zhǎng)和平均訪問時(shí)長(zhǎng)節(jié)省率隨緩存空間的變化Fig.7 Change of average visit time and save ratio of average visit time of four algorithms with cache space

瓦片緩存置換算法為NGIS 帶來了更高效的瓦片服務(wù)，但同時(shí)也會(huì)提高CPU 占用率。圖8 展示了當(dāng)緩存空間為500 MB 時(shí)4 種算法的CPU 占用率及累計(jì)占用率的統(tǒng)計(jì)結(jié)果。可知，4 種算法的CPU 占用率從大到小依次為L(zhǎng)RU，SSAT，LFU 和FIFO。LRU 有良好的緩存命中率，但資源消耗過大；FIFO占用的CPU 資源最小，但緩存命中率過低；LFU 和SSAT 的資源消耗適中，但LFU 的緩存命中率遠(yuǎn)低于SSAT；SSAT 能兼顧性能和資源消耗，是一種良好的服務(wù)端瓦片緩存置換算法。

圖8 4 種算法的CPU 占用率和累計(jì)占用率Fig.8 CPU usage ratio and sum usage ratio of four algorithms

3 結(jié) 論

綜合分析了瓦片訪問的時(shí)空局部性、長(zhǎng)短期流行度和瓦片大小特征，將老化算法引入NGIS，提出了基于時(shí)空老化模型的服務(wù)端瓦片緩存置換算法（SSAT），并進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明，相較于傳統(tǒng)算法，SSAT 能顯著提高瓦片請(qǐng)求命中率和字節(jié)命中率，縮短平均訪問時(shí)長(zhǎng)，且能兼顧對(duì)計(jì)算機(jī)資源的消耗，是一種較有效的瓦片緩存置換算法。

SSAT 仍有待優(yōu)化。首先，本實(shí)驗(yàn)是在單機(jī)上進(jìn)行的，如何將SSAT 擴(kuò)展為分布式緩存置換算法，令其在多節(jié)點(diǎn)、多副本的場(chǎng)景下保持良好性能，進(jìn)一步提高遙感影像的共享能力是未來重點(diǎn)關(guān)注的研究方向。此外，除瓦片大小特征外，瓦片數(shù)據(jù)特征還包括瓦片類型特征和瓦片格式特征等多種信息，未來將從多個(gè)維度分析瓦片數(shù)據(jù)特征對(duì)緩存命中率的影響，為高性能地理信息服務(wù)提供更全面的理論支撐。