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

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

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

0 引 言

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

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

國(guó)內(nèi)外學(xué)者基于瓦片訪問(wèn)模式和瓦片數(shù)據(jù)特征，對(duì)瓦片緩存置換算法開(kāi)展了大量研究。LEE等［17］提出了基于馬爾可夫鏈的瓦片緩存預(yù)取和置換算法，通過(guò)置入預(yù)取概率高的瓦片，置換出轉(zhuǎn)移概率低的瓦片。王浩等［14］提出了基于瓦片存活壽命和訪問(wèn)熱度的緩存置換算法，通過(guò)計(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)行分組，研究了基于不同用戶組訪問(wèn)密集性的瓦片緩存置換算法。劉佳星等［15］利用瓦片金字塔特性，提出了基于地理單元熱度的瓦片緩存置換算法。這些算法結(jié)合時(shí)空特性定義了各自瓦片價(jià)值模型，并根據(jù)價(jià)值大小置換瓦片，在一定程度上提高了緩存命中率［4］。但這些算法在應(yīng)用于服務(wù)端瓦片緩存時(shí)還存在以下問(wèn)題：（1）相較于傳統(tǒng)的緩存置換算法，上述算法的復(fù)雜性高、效率低，不適合大量瓦片緩存置換的應(yīng)用場(chǎng)景；（2）大多數(shù)為客戶端緩存置換算法，不適合基于網(wǎng)絡(luò)的服務(wù)端瓦片緩存置換場(chǎng)景；（3）重點(diǎn)分析了瓦片訪問(wè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)景，綜合瓦片訪問(wèn)的長(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合瓦片訪問(wèn)的時(shí)間局部性；（3）兼顧瓦片訪問(wèn)對(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)的訪問(wèn)情況，值越大，表示該頁(yè)面被訪問(wèn)時(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)的操作過(guò)程相同。

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

當(dāng)內(nèi)存不足時(shí)，老化算法會(huì)根據(jù)計(jì)數(shù)器C 的大小置換頁(yè)面［23］。C 越大，其高位為1 的概率越大，表明其被訪問(wèn)的時(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)，綜合考慮瓦片訪問(wè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）為瓦片空間訪問(wèn)熱度價(jià)值，V（size）為瓦片大小價(jià)值。V（heat）和V（size）通過(guò)影響V（age）右移的方式參與調(diào)節(jié)。

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，maxHeat 為緩存中最大的瓦片空間訪問(wèn)熱度，Me 為緩存中所有heat 的中位數(shù)。設(shè)置Me 是為了避免當(dāng)heat 與maxHeat 相差較大時(shí)，對(duì)V（age）產(chǎn)生過(guò)大的移位影響。假設(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í)鐘周期沒(méi)有被訪問(wèn)。而瓦片C 的heat 與maxHeat 相差1 000 倍，若直接用heat 計(jì)算，將得到V（heat）≈9，這對(duì)于32 位的V（age）來(lái)說(shuō)，產(chǎn)生的移位影響過(guò)大，會(huì)造成V（age）信息丟失。若取heat=Me，則得到V（heat）≈6，這既體現(xiàn)了差距，又避免了對(duì)V（age）信息產(chǎn)生移位污染?？偟膩?lái)說(shuō)，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é)過(guò)程中，大小不同的瓦片之間應(yīng)該體現(xiàn)出適當(dāng)?shù)牟罹?。定義V（size）為

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

在運(yùn)行過(guò)程中，緩存服務(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）、空間訪問(wèn)熱度值（tileSpatailHeat）和瓦片大小（size）。

1.4 SSAT 流程

SSAT 在執(zhí)行過(guò)程中需要陸續(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é)處理客戶端的瓦片訪問(wèn)請(qǐng)求、查詢瓦片緩存以及置入、換出瓦片等，步驟如下。

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

（2）執(zhí)行定時(shí)器線程周期，每經(jīng)過(guò)一個(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)行編碼，并通過(guò)編碼值查找緩存索引，若命中，則轉(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，空間訪問(wèn)熱度值增加1，同時(shí)將緩存中存在的該瓦片水平鄰域和垂直鄰域中其他瓦片的空間訪問(wèn)熱度值增加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)過(guò)程

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

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

在SSAT 中，需要設(shè)置瓦片時(shí)鐘周期T和瓦片空間訪問(wèn)熱度權(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)被訪問(wèn)的概率增加。由于R 位僅能表示某個(gè)周期內(nèi)瓦片是否被訪問(wèn)，無(wú)法表示瓦片被訪問(wèn)頻次，T增大會(huì)使各瓦片在V（age）上的差異減小，因此緩存命中率減小。當(dāng)T＞45 s 時(shí)，V（age）不再是主要影響因子，因此，緩存命中率不隨T的變化而變化。

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

圖4 瓦片時(shí)鐘周期和瓦片空間訪問(wèn)熱度權(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é)果表明，瓦片空間訪問(wèn)熱度價(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% 左右?？偟膩?lái)說(shuō)，在不同緩存空間下，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

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

圖7 4 種算法的平均訪問(wèn)時(shí)長(zhǎng)和平均訪問(wèn)時(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 帶來(lái)了更高效的瓦片服務(wù)，但同時(shí)也會(huì)提高CPU 占用率。圖8 展示了當(dāng)緩存空間為500 MB 時(shí)4 種算法的CPU 占用率及累計(jì)占用率的統(tǒng)計(jì)結(jié)果?？芍? 種算法的CPU 占用率從大到小依次為L(zhǎng)RU，SSAT，LFU 和FIFO。LRU 有良好的緩存命中率，但資源消耗過(guò)大；FIFO占用的CPU 資源最小，但緩存命中率過(guò)低；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é) 論

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

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