一種基于主題時(shí)空價(jià)值的服務(wù)器端瓦片緩存算法

陸曄，張偉，李飛，杜震洪*，張豐，劉仁義

（1.浙江大學(xué)浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,浙江杭州310028；2.浙江大學(xué)地理信息科學(xué)研究所,浙江 杭州310027；3.山東省國土測繪院，山東 濟(jì)南250102）

瓦片服務(wù)是WebGIS中最重要的功能之一，其出現(xiàn)改變了地理信息數(shù)據(jù)的發(fā)布與獲取方式，為人們的生活體驗(yàn)和工作帶來了便利。然而，隨著GIS用戶規(guī)模和各種影像產(chǎn)品瓦片數(shù)據(jù)量的持續(xù)增長，瓦片服務(wù)器面臨服務(wù)過載和響應(yīng)延遲等問題[1]。通過在客戶端和瓦片服務(wù)器間添加瓦片緩存服務(wù)器的方法[2]，可以有效降低源瓦片服務(wù)器接受請求數(shù)目，提高瓦片的響應(yīng)速度，而瓦片緩存算法的優(yōu)劣則決定了瓦片緩存的命中率，直接影響緩存服務(wù)器的壓力分流能力和WebGIS 用戶的請求等待時(shí)間[1]。因此，瓦片服務(wù)器端緩存算法的相關(guān)研究，對于提升WebGIS服務(wù)質(zhì)量具有重要意義。

國內(nèi)外學(xué)者針對瓦片數(shù)據(jù)緩存算法做了較多研究，KANG 等[3]研究了瓦片的預(yù)取和替換方式，用預(yù)取概率高的瓦片替換轉(zhuǎn)移概率最小的。王浩等[4]研究了基于瓦片壽命和訪問熱度的緩存置換算法（TCLEPR），通過瓦片緩存存活超限壽命和瓦片訪問熱度來計(jì)算瓦片老化程度，置換出老化程度最高的瓦片的緩存。涂振發(fā)等[5]研究了最小空間數(shù)據(jù)價(jià)值緩存置換算法（GDLVF）,通過數(shù)據(jù)訪問時(shí)間、訪問頻率、數(shù)據(jù)大小和空間位置特性計(jì)算瓦片價(jià)值，置換出價(jià)值最低的瓦片的緩存。LI 等[6]研究了stat算法，用瓦片訪問次數(shù)和訪問時(shí)間間隔來累計(jì)瓦片的stat值，置換出stat值最低的瓦片的緩存。劉佳星等[1]研究了基于地理單元熱度的瓦片緩存置換算法（GUH），通過瓦片所包含的地理單元和縮放層級來計(jì)算瓦片熱度值，置換出熱度值最低的瓦片的緩存。這些文獻(xiàn)通過研究瓦片訪問的時(shí)空局部性原理，定義了各自的瓦片價(jià)值（概率、老化程度、熱度或stat值），根據(jù)價(jià)值來置換瓦片，這些方法較傳統(tǒng)緩存置換算法獲得了較好的效果，但在應(yīng)用于服務(wù)器端瓦片緩存時(shí)存在2個(gè)問題：(1)面向單一類型瓦片數(shù)據(jù)的緩存算法，沒有體現(xiàn)瓦片類型對于瓦片價(jià)值的影響，不太適合服務(wù)器端擁有大量不同類型瓦片數(shù)據(jù)的場景；(2)通過瓦片訪問頻率或地理單元熱度來反映瓦片的空間局部性，僅僅反映了瓦片的長期空間局部性，缺乏對短期空間局部性的表現(xiàn)，即沒有考慮當(dāng)前請求瓦片對下一時(shí)刻其鄰近位置瓦片被訪問造成的影響。

本文在基于價(jià)值的瓦片緩存模型的基礎(chǔ)上，提出了一種基于主題時(shí)空價(jià)值的服務(wù)器端緩存置換算法（GDTST）。相較于現(xiàn)有的瓦片緩存算法，進(jìn)行了以下優(yōu)化：(1)在考慮瓦片訪問的時(shí)間局部性和空間局部性基礎(chǔ)上，進(jìn)一步引入了瓦片主題權(quán)重，并設(shè)計(jì)了基于主題金字塔的緩存索引，使其適應(yīng)多類型瓦片的服務(wù)器端瓦片緩存；(2)優(yōu)化了空間局部性的表達(dá)方式，通過計(jì)算基于瓦片鄰接范圍的空間訪問頻次，實(shí)現(xiàn)在考慮長期空間局部性的同時(shí)兼顧短期空間局部性。

1 基于主題金字塔的瓦片緩存索引設(shè)計(jì)

瓦片數(shù)據(jù)是由影像或地圖數(shù)據(jù)按照某種瓦片數(shù)據(jù)模型切分而成的數(shù)據(jù)單元，目前常用的瓦片數(shù)據(jù)模型為金字塔模型。瓦片金字塔模型是一種多分辨率的層次模型，它先將影像或地圖數(shù)據(jù)按“行×列”的方式進(jìn)行切片，生成瓦片矩陣，再通過分級、分塊構(gòu)建多尺度瓦片矩陣集[7]。在單個(gè)瓦片金字塔中，每一張瓦片都可以通過層級、行號與列號唯一確定。然而，瓦片服務(wù)器往往提供多套瓦片數(shù)據(jù)的訪問，原有的僅依靠層級與行列號的緩存索引體系[1,4,8]已經(jīng)不再適用。因此，為了在服務(wù)器端緩存中實(shí)現(xiàn)瓦片索引唯一化，進(jìn)行以下定義：

定義1主題金字塔是由相同類型的瓦片構(gòu)成的瓦片集合，每一張瓦片可由主題、層級、列號與行號唯一確定。在實(shí)際應(yīng)用中，由于瓦片請求URL 前綴往往包含瓦片的版本號、傳感器信息、生成時(shí)間信息等，所以可以直接由URL的前綴生成主題信息。

基于主題金字塔的瓦片索引值tileId可表示為

式（1）中，t表示瓦片主題，z表示瓦片在該主題金字塔中的層級號，x表示瓦片在z層級上的列號，y表示瓦片在z層級上的行號，idFunc為索引值生成函數(shù)，tileId可唯一確定服務(wù)器端的一張瓦片。

idFunc為降維函數(shù)，即將主題、層級、行號、列號所構(gòu)成的四維數(shù)據(jù)降維成一維數(shù)據(jù)，以方便采用B樹、Hash表等方式創(chuàng)建索引。為減小編碼，加快編碼計(jì)算速度，本文采用如圖1所示的tileId 編碼結(jié)構(gòu)。

圖1 索引編碼結(jié)構(gòu)Fig.1 Index coding structure

圖1中，tileId占有128個(gè)二進(jìn)制位，前64位表示瓦片的主題信息；中間41位為瓦片空間位置信息，最后一位為1，用來快速轉(zhuǎn)換空間位置信息，即從末尾最后一位向前查找，找到第一個(gè)不為0的位置，設(shè)這一位的前一位置為pos（pos為64時(shí)表示0級瓦片），用第65位到位表示列號x，用位到pos位表示行號y,用表示層級號l，而依照地理信息公共服務(wù)平臺電子地圖數(shù)據(jù)規(guī)范，瓦片數(shù)據(jù)通常有1～20級，因此40位足以表示目前WebGIS常用瓦片范圍；最后23位為保留位，可用于拓展瓦片層級。

在實(shí)際應(yīng)用中，筆者根據(jù)瓦片請求URL 生成請求前綴preUrl、層級號l、列號x、行號y，采用MurmurHash 函數(shù)由preUrl 生成t值。同時(shí)，采用2級索引機(jī)制，即首先根據(jù)主題值t，檢索到該主題下的瓦片索引表，再根據(jù)由主題值t、層級號l、列號x和行號y生成的索引tileId 在瓦片索引表中檢索瓦片數(shù)據(jù)，為加快數(shù)據(jù)定位速度，索引項(xiàng)tileId 采用hash表存儲。

基于主題金字塔的瓦片索引的結(jié)構(gòu)如圖2所示，第1級主題索引表themeIndex 實(shí)現(xiàn)主題值t與主題索引節(jié)點(diǎn)themeIndexNode的映射，themeIndexNode內(nèi)容包括：請求前綴preUrl、緩存中該主題瓦片數(shù)目themeCount和第2級瓦片索引表tileIndex；第2級瓦片索引表tileIndex 實(shí)現(xiàn)瓦片索引值tileId與瓦片索引節(jié)點(diǎn)tileIndexNode的映射，tileIndexNode內(nèi)容包括：上一次訪問時(shí)間lastAccessTime、瓦片歷史平均訪問間隔avgAccessTime、基于鄰接范圍的空間訪問頻次freqSpatial、數(shù)據(jù)大小size、緩存數(shù)據(jù)價(jià)值gdtst和瓦片數(shù)據(jù)指針data。

圖2 2級瓦片索引結(jié)構(gòu)Fig.2 Two-level tile index structure

2 基于主題時(shí)空價(jià)值的瓦片緩存置換算法

瓦片緩存服務(wù)器的空間大小是有限的，當(dāng)緩存空間已滿或達(dá)到某一閾值而無法容納新的瓦片數(shù)據(jù)時(shí)，為了使緩存系統(tǒng)繼續(xù)工作，就需要使用緩存置換算法將緩存中已有的瓦片替換出去。傳統(tǒng)的緩存置換算法主要有：最近最少使用瓦片置換算法（LRU）、最不經(jīng)常使用置換算法（LFU）、先進(jìn)先出置換算法（FIFO）等，但這些算法忽視了瓦片數(shù)據(jù)的空間位置特性，不具備良好的瓦片命中率[9]；面向瓦片的緩存算法主要有TCLERPR、GDLVF、Stat、GUH 等[1,4-6]，這些算法均定義了自己的瓦片緩存價(jià)值，每次置換出價(jià)值最小的瓦片，較傳統(tǒng)緩存算法效果好，但在面對服務(wù)器端的多套瓦片數(shù)據(jù)時(shí)無法進(jìn)行很好的區(qū)分，并且對瓦片空間局部性利用欠充分。為此，提出了一種基于主題時(shí)空價(jià)值的瓦片緩存置換算法（GDTST算法），當(dāng)緩存空間已滿或達(dá)到閾值時(shí)，剔除gdtst值最小的瓦片，實(shí)現(xiàn)瓦片置換，gdtst值計(jì)算式為

式(2)中，lowest表示當(dāng)前緩存中瓦片價(jià)值的最低值，freqSpatial(i)表示當(dāng)前瓦片基于鄰接范圍的空間訪問頻次，avgAcessTime(i)表示當(dāng)前瓦片的歷史平均訪問間隔，weightTheme(i)表示瓦片主題權(quán)重。對于剛進(jìn)入緩存的瓦片，gdtst值置為lowest。

2.1 基于鄰接范圍的空間訪問頻次

瓦片的空間局部性指在空間上距離相鄰的瓦片總是傾向于在被訪問的時(shí)間上也相鄰，即地形漫游時(shí)，瓦片在某時(shí)刻被訪問，則下一時(shí)刻該瓦片附近的瓦片有更高的概率再次被訪問[8]。TCLERPR 等算法認(rèn)為，瓦片訪問的空間局部性體現(xiàn)在瓦片的長期流行度上，即用瓦片的累計(jì)訪問次數(shù)來反映瓦片訪問請求的空間分布特性。這種方式體現(xiàn)了瓦片訪問空間局部性的長期趨勢，可以很好地表現(xiàn)某一時(shí)間段內(nèi)哪些區(qū)域的瓦片最有可能被訪問，但是對于瓦片訪問的短期局部性，即當(dāng)某一瓦片被訪問后，其鄰近瓦片將在下一時(shí)刻被訪問的概率升高這一特性沒有很好體現(xiàn)。因此，本文提出基于鄰接范圍的空間訪問頻次，并做以下定義：

定義2瓦片鄰接范圍是指當(dāng)某一瓦片被請求后，在主題金字塔的當(dāng)前縮放層級上，該瓦片可以影響以當(dāng)前請求瓦片為中心的正方形范圍內(nèi)瓦片被訪問的概率，這一范圍稱為瓦片鄰接范圍。

設(shè)瓦片鄰接范圍大小為adjacent，則adjacent表示以當(dāng)前請求瓦片為中心，鄰接范圍內(nèi)瓦片數(shù)據(jù)集中的瓦片個(gè)數(shù)，adjacent可取1，9，25，…，(2n+1)2。如圖3所示，當(dāng)adjacent 取9時(shí)，瓦片（x，y）被請求后，陰影部分則為其鄰接范圍。

圖3 瓦片鄰接范圍Fig.3 Adjacency range of a tile

定義3瓦片鄰接影響度為某一瓦片被請求后，對其鄰接范圍內(nèi)其他瓦片的影響程度。設(shè)瓦片鄰接影響度為aw，aw的取值范圍為[0,1]，值越大，瓦片的訪問對其空間鄰近瓦片的影響越大，aw=0,即不會影響對鄰近瓦片的訪問。

定義4基于鄰接范圍的空間訪問頻次。設(shè)freqSpatial為瓦片基于鄰接范圍的空間訪問頻次，當(dāng)該瓦片被命中時(shí)，其freqSpatial=freqSpatial+1，緩存中該瓦片鄰接范圍內(nèi)其余瓦片的freqSpatial=freqSpatial+aw；未被命中時(shí)，將該瓦片鄰接范圍內(nèi)所有瓦片寫入緩存，該瓦片的freqSpatial值為1，鄰接范圍內(nèi)其余瓦片的freqSpatial值為aw。

freqSpatial 實(shí)質(zhì)是瓦片的累計(jì)訪問頻次和其鄰接范圍影響權(quán)重的累加，反映了瓦片訪問的長期局部性；而每一次瓦片freqSpatial的更新則是瓦片訪問短期局部性的體現(xiàn)，反映下一時(shí)刻鄰接范圍內(nèi)的瓦片被訪問的概率將升高。為減少緩存對瓦片服務(wù)器的請求次數(shù)，本文在瓦片服務(wù)器上實(shí)現(xiàn)瓦片批量獲取接口，即通過單次請求，獲取瓦片鄰接范圍內(nèi)所有瓦片；同時(shí)，當(dāng)瓦片被命中時(shí)，僅更新緩存中鄰接范圍內(nèi)已有瓦片的訪問頻次，不請求缺失的鄰接范圍瓦片。

2.2 瓦片歷史平均訪問間隔

瓦片的時(shí)間局部性是指如果某個(gè)瓦片對象剛剛被客戶端請求過，那么在今后的一段時(shí)間內(nèi)，該瓦片對象被再次訪問的概率較高，并且隨著訪問時(shí)間間隔的縮短，被再次訪問的概率會隨之增大[10]。本文采用瓦片歷史平均訪問間隔來體現(xiàn)瓦片訪問的時(shí)間局部性，即采用遞進(jìn)的方式來計(jì)算瓦片的平均訪問間隔，從而實(shí)現(xiàn)既考慮瓦片的當(dāng)前訪問時(shí)間間隔，又兼顧歷史訪問時(shí)間間隔[11]。

定義5瓦片歷史平均訪問間隔。設(shè)avgAccessTime表示瓦片的歷史平均訪問時(shí)間間隔，lastAccessTime為瓦片上次被訪問的時(shí)間，hw為歷史瓦片訪問權(quán)重，currentTime表示當(dāng)前時(shí)間，當(dāng)瓦片被再次訪問時(shí)，avgAccessTime 按下式更新：

式(3)中，瓦片剛進(jìn)入緩存時(shí)設(shè)置avgAcessTime為0，hw的取值范圍為[0,1)，hw值越大瓦片的歷史訪問時(shí)間間隔對下一次訪問影響越大，hw 取0時(shí)，則退化為LRU算法中的時(shí)間間隔，僅反映短期內(nèi)該瓦片被訪問的概率。

2.3 瓦片主題權(quán)重

服務(wù)器端瓦片對象除了具有時(shí)空局部性外，由于其具有不同的主題，用戶訪問時(shí)往往還有主題傾向性，即對相同價(jià)值的瓦片，用戶傾向主題的瓦片數(shù)據(jù)被再次訪問的概率要大于非傾向主題的瓦片數(shù)據(jù)，前者的實(shí)際數(shù)據(jù)價(jià)值大于后者[12]；同時(shí)，對于不同主題的瓦片金字塔，其瓦片大小差異較大。在計(jì)算面向服務(wù)器端的瓦片緩存價(jià)值時(shí)，還需考慮主題與數(shù)據(jù)大小相關(guān)因素，因此，本文定義了服務(wù)器端的瓦片主題權(quán)重。

定義6瓦片主題權(quán)重。設(shè)weightTheme為瓦片主題權(quán)重，themeCount為該主題金字塔緩存中的瓦片數(shù)目，totalThemeCount為緩存中的所有瓦片數(shù)目，size為瓦片大小，則

weightTheme 實(shí)質(zhì)上通過緩存中不同瓦片主題所占比例來反映用戶的主題傾向性，即認(rèn)為緩存中某一主題瓦片數(shù)據(jù)所占比例較大，則下一時(shí)刻該主題的瓦片較其他主題的瓦片被訪問的概率要大。同時(shí)為了提高瓦片對象的命中率，該權(quán)重與數(shù)據(jù)大小成反比，認(rèn)為數(shù)據(jù)較小的瓦片權(quán)重更大，即應(yīng)優(yōu)先置換單個(gè)數(shù)據(jù)較大的瓦片而不是多個(gè)數(shù)據(jù)較小的瓦片。

2.4 基于主題時(shí)空價(jià)值緩存算法的流程

結(jié)合基于主題金字塔的瓦片緩存索引，GDTST算法的具體過程描述如下：

(1)當(dāng)有新的請求到達(dá)緩存時(shí)，根據(jù)請求的URL信息生成瓦片的主題信息t、層級號l、列號x、行號y；

(2)根據(jù)t查找主題索引表themeIndex，如果未命中轉(zhuǎn)(3)，命中轉(zhuǎn)(4)；

(3)創(chuàng)建并初始化主題索引節(jié)點(diǎn)themeNode，加入一級索引表themeIndex，轉(zhuǎn)(6)；

(4)獲取主題索引節(jié)點(diǎn)themeNode，根據(jù)瓦片t、l、x、y生成瓦片索引tileId，根據(jù)tileId查找themeNode的瓦片索引表tileIndex，如果命中轉(zhuǎn)(5)，未命中轉(zhuǎn)(6)；

(5)獲取該瓦片索引節(jié)點(diǎn)，返回被請求瓦片數(shù)據(jù)，更新該節(jié)點(diǎn)的lastAccessTime、avgAccessTime、freqSpatial和gdtst；更新該瓦片鄰接范圍內(nèi)其余瓦片索引節(jié)點(diǎn)的freqSpatial和gdtst，若鄰接瓦片不在緩存中，則跳過，轉(zhuǎn)(10)；

(6)根據(jù)t、l、x、y構(gòu)造瓦片及其鄰接范圍內(nèi)其余瓦片的URL，從源瓦片服務(wù)器獲取瓦片鄰接范圍內(nèi)所有瓦片，同時(shí)，返回被請求瓦片；

(7)判斷緩存空間是否足以容納鄰接范圍內(nèi)所有瓦片，若不足轉(zhuǎn)(8)，若足夠轉(zhuǎn)(9)；

(8)移除緩存中主題時(shí)空價(jià)值最低的瓦片，并移除相應(yīng)索引項(xiàng)，直到緩存空間充足；

(9)對于每一張瓦片，生成其tileId，當(dāng)tileId 在索引中時(shí)，僅更新其瓦片索引節(jié)點(diǎn)的freqSpatial和gdtst；當(dāng)tileId 不在索引中時(shí)，創(chuàng)建并初始化瓦片索引節(jié)點(diǎn)，加入到二級索引表tileIndex中，并將瓦片數(shù)據(jù)加入緩存。

(10)結(jié)束。

在實(shí)際應(yīng)用中，步驟(5)和(6)中的返回瓦片數(shù)據(jù)操作和其余緩存更新操作異步進(jìn)行，因此鄰接范圍內(nèi)瓦片的更新不會影響瓦片數(shù)據(jù)的返回延時(shí)。同時(shí)，對于步驟(6)請求的鄰接范圍瓦片操作，當(dāng)瓦片服務(wù)器實(shí)現(xiàn)批量獲取接口時(shí)，僅需請求1次便可獲取鄰接范圍內(nèi)瓦片，對源瓦片服務(wù)器不會產(chǎn)生額外的負(fù)載。

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

3.1 實(shí)驗(yàn)內(nèi)容與環(huán)境

采用日志驅(qū)動(dòng)模式，考察GDTST算法對多主題瓦片數(shù)據(jù)的請求命中率、字節(jié)命中率和延遲節(jié)省率三方面的性能。首先，采集在不設(shè)置緩存情況下的源瓦片服務(wù)器日志記錄；接著，按請求時(shí)間順序提取日志中瓦片請求的URL 信息，生成測試文件；然后，測試客戶端程序，按照測試文件模擬用戶訪問，向緩存服務(wù)程序請求瓦片；最后，在不同相對緩存大小下，計(jì)算采用LRU、LFU、FIFO與GDTST 緩存算法時(shí)緩存服務(wù)程序的3項(xiàng)指標(biāo)值。其中，相對緩存為實(shí)際緩存空間相對所設(shè)定最大緩存容量（2GB）的百分比。

實(shí)驗(yàn)采集的日志記錄為近海碳通量信息可視化系統(tǒng)[13]瓦片服務(wù)器2018年10月23日的被訪問記錄，共141 236 條日志，涉及241種瓦片產(chǎn)品數(shù)據(jù)。其中，最大的瓦片為134.7 kB，最小的瓦片為668 B。硬件環(huán)境為2臺相同的小型服務(wù)器，其中一臺服務(wù)器部署測試客戶端程序，另一臺服務(wù)器部署緩存服務(wù)程序和瓦片服務(wù)程序，2臺服務(wù)器通過千兆交換機(jī)相連。服務(wù)器配置：Windows 7，64位操作系統(tǒng)，Intel(R)Core(TM)i7-4790 CPU @3.60 GHz，8 核CPU，8 GB內(nèi)存。

3.2 GDTST算法的參數(shù)選擇

在GDTST算法中，需要設(shè)置歷史瓦片訪問權(quán)重hw、瓦片鄰接影響度aw和瓦片鄰接范圍adjacent。其中，瓦片鄰接范圍的選取主要依據(jù)緩存空間的大小，在最大緩存容量2 GB的條件下，本文設(shè)置adjacent=9，并進(jìn)一步進(jìn)行hw和aw的選取。

圖4 hw 參數(shù)選取比較Fig.4 The comparison of hw parameter selection

圖5 aw 參數(shù)選取比較Fig.5 The comparison of aw parameter selection

圖4為瓦片鄰接影響度aw 設(shè)置為0時(shí)，采用不同歷史瓦片訪問權(quán)重hw的GDTST算法請求命中率結(jié)果。由圖4可知，當(dāng)相對緩存大于25%時(shí)，GDTST算法對于瓦片歷史訪問權(quán)重參數(shù)不敏感；而當(dāng)相對緩存小于25%時(shí)，可以發(fā)現(xiàn)當(dāng)歷史瓦片訪問權(quán)重取0.6 或0.8時(shí)，較取其他值時(shí)獲得了更高的瓦片請求命中率。

圖5為歷史瓦片訪問權(quán)重hw 設(shè)置為0時(shí)，采用不同瓦片鄰接影響度aw的GDTST算法請求命中率結(jié)果。由圖5可知，瓦片鄰接影響度參數(shù)大于0時(shí)的請求命中率明顯大于瓦片鄰接影響度等于0時(shí)。同時(shí)，當(dāng)相對緩存大于50%時(shí)，請求命中率對于瓦片鄰接影響度大于0的不敏感；而當(dāng)相對緩存小于50%時(shí)，瓦片鄰接影響度參數(shù)取1時(shí)，可以獲得更高的請求命中率。

為了獲得更高的緩存命中率，在緩存算法對比實(shí)驗(yàn)中，GDTST算法的參數(shù)分別取hw=0.6，aw=1，adjacent=9。

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

圖6 請求命中率比較Fig.6 The comparison of the request hit ratio

圖7 字節(jié)命中率比較Fig.7 The comparison of the byte hit ratio

圖6和圖7分別為FIFO、LFU、LRU和GDTST4種緩存算法的請求命中率和字節(jié)命中率的實(shí)驗(yàn)結(jié)果。由實(shí)驗(yàn)結(jié)果可知，4種緩存算法中，2種緩存命中率會隨緩存的增大而增大；當(dāng)相對緩存較小時(shí)，4種緩存算法命中率均隨緩存容量的增加明顯變化；當(dāng)相對緩存容量較大時(shí)，4種緩存算法隨緩存容量增加變化較為平緩，F(xiàn)IFO、LFU、LRU 瓦片請求命中率最終趨近于重復(fù)請求在所有請求中所占的比例，而GDTST算法，由于每次未命中會提前緩存鄰近范圍瓦片，故其命中率的趨近值更大。而在相對緩存大小相同的情況下，GDTST算法的命中率均高于其他3種算法，這是由于GDTST算法綜合考慮了瓦片訪問的時(shí)空局部性，特別是短期空間局部性，同時(shí)也利用了用戶對于瓦片訪問的主題傾向性，因而在多主題瓦片的訪問情景下可以獲得更好的命中效果。

由于僅在被請求瓦片缺失時(shí)才會訪問源瓦片服務(wù)器，且本文在瓦片服務(wù)器端實(shí)現(xiàn)了瓦片批量獲取接口，當(dāng)鄰接范圍瓦片更新時(shí)，GDTST算法不會導(dǎo)致額外的瓦片請求，因此，其瓦片請求命中率與源瓦片服務(wù)器的接收請求率相關(guān)，即瓦片請求命中率越高，源瓦片服務(wù)器接收請求率越低。

圖8 延遲節(jié)省率比較Fig.8 The comparison of latency reduction ratio

圖8為FIFO、LFU、LRU和GDTST4種緩存算法延遲節(jié)省率的實(shí)驗(yàn)結(jié)果，由實(shí)驗(yàn)結(jié)果可知，在相對緩存容量小于80%時(shí)，GDTST算法的延遲節(jié)省率與FIFO 相當(dāng)，但小于LRU和LFU，這是由于GDTST算法的實(shí)現(xiàn)基于優(yōu)先隊(duì)列，其寫入與調(diào)整操作都是O(log(n))的時(shí)間復(fù)雜度，而LRU、LFU和FIFO的寫入與調(diào)整則實(shí)現(xiàn)了O(1)的時(shí)間復(fù)雜度，同時(shí)，在相對緩存較小時(shí)，緩存置換操作又較為頻繁，因此，當(dāng)相對緩存容量較小時(shí)，其延遲節(jié)省率略低于LRU和LFU，當(dāng)緩存容量在10%～80%時(shí)，差值小于3%；而當(dāng)緩存容量大于80%時(shí)，GDTST算法由于其較高的緩存命中率，瓦片命中節(jié)省的時(shí)間彌補(bǔ)了算法的復(fù)雜度，因此，其延遲節(jié)省率高于其他3種算法。

4 結(jié) 論

設(shè)計(jì)了面向多主題瓦片數(shù)據(jù)的服務(wù)器端緩存索引，綜合考慮瓦片請求的時(shí)間局部性、空間局部性和用戶主題傾向性，提出了GDTST算法。實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)FIFO、LRU、LFU算法，當(dāng)面對源瓦片服務(wù)器中多主題瓦片數(shù)據(jù)時(shí)，在不同的相對緩存下，GDTST 均能取得較高的瓦片請求命中率和字節(jié)命中率，同時(shí)，在相對緩存較大的情況下?lián)碛懈叩难舆t節(jié)省率，因此，GDTST算法可以有效減輕源瓦片服務(wù)器負(fù)載、縮短用戶等待時(shí)間。但是，GDTST算法緩存更新操作時(shí)間復(fù)雜度較高，下一步工作將優(yōu)化緩存數(shù)據(jù)結(jié)構(gòu)，在相對緩存較小時(shí)提高緩存算法延遲節(jié)省率。