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

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

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

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

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

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

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

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

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

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

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

idFunc為降維函數(shù)，即將主題、層級(jí)、行號(hào)、列號(hào)所構(gòu)成的四維數(shù)據(jù)降維成一維數(shù)據(jù)，以方便采用B樹(shù)、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，用來(lái)快速轉(zhuǎn)換空間位置信息，即從末尾最后一位向前查找，找到第一個(gè)不為0的位置，設(shè)這一位的前一位置為pos（pos為64時(shí)表示0級(jí)瓦片），用第65位到位表示列號(hào)x，用位到pos位表示行號(hào)y,用表示層級(jí)號(hào)l，而依照地理信息公共服務(wù)平臺(tái)電子地圖數(shù)據(jù)規(guī)范，瓦片數(shù)據(jù)通常有1～20級(jí)，因此40位足以表示目前WebGIS常用瓦片范圍；最后23位為保留位，可用于拓展瓦片層級(jí)。

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

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

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

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

瓦片緩存服務(wù)器的空間大小是有限的，當(dāng)緩存空間已滿或達(dá)到某一閾值而無(wú)法容納新的瓦片數(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)緩存算法效果好，但在面對(duì)服務(wù)器端的多套瓦片數(shù)據(jù)時(shí)無(wú)法進(jìn)行很好的區(qū)分，并且對(duì)瓦片空間局部性利用欠充分。為此，提出了一種基于主題時(shí)空價(jià)值的瓦片緩存置換算法（GDTST算法），當(dāng)緩存空間已滿或達(dá)到閾值時(shí)，剔除gdtst值最小的瓦片，實(shí)現(xiàn)瓦片置換，gdtst值計(jì)算式為

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

2.1 基于鄰接范圍的空間訪問(wèn)頻次

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

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

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

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

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

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

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

2.2 瓦片歷史平均訪問(wèn)間隔

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

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

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

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

服務(wù)器端瓦片對(duì)象除了具有時(shí)空局部性外，由于其具有不同的主題，用戶訪問(wèn)時(shí)往往還有主題傾向性，即對(duì)相同價(jià)值的瓦片，用戶傾向主題的瓦片數(shù)據(jù)被再次訪問(wèn)的概率要大于非傾向主題的瓦片數(shù)據(jù)，前者的實(shí)際數(shù)據(jù)價(jià)值大于后者[12]；同時(shí)，對(duì)于不同主題的瓦片金字塔，其瓦片大小差異較大。在計(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ì)上通過(guò)緩存中不同瓦片主題所占比例來(lái)反映用戶的主題傾向性，即認(rèn)為緩存中某一主題瓦片數(shù)據(jù)所占比例較大，則下一時(shí)刻該主題的瓦片較其他主題的瓦片被訪問(wèn)的概率要大。同時(shí)為了提高瓦片對(duì)象的命中率，該權(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算法的具體過(guò)程描述如下：

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

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

(3)創(chuàng)建并初始化主題索引節(jié)點(diǎn)themeNode，加入一級(jí)索引表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)，返回被請(qǐng)求瓦片數(shù)據(jù)，更新該節(jié)點(diǎn)的lastAccessTime、avgAccessTime、freqSpatial和gdtst；更新該瓦片鄰接范圍內(nèi)其余瓦片索引節(jié)點(diǎn)的freqSpatial和gdtst，若鄰接瓦片不在緩存中，則跳過(guò)，轉(zhuǎn)(10)；

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

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

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

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

(10)結(jié)束。

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

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

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

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

實(shí)驗(yàn)采集的日志記錄為近海碳通量信息可視化系統(tǒng)[13]瓦片服務(wù)器2018年10月23日的被訪問(wèn)記錄，共141 236 條日志，涉及241種瓦片產(chǎn)品數(shù)據(jù)。其中，最大的瓦片為134.7 kB，最小的瓦片為668 B。硬件環(huán)境為2臺(tái)相同的小型服務(wù)器，其中一臺(tái)服務(wù)器部署測(cè)試客戶端程序，另一臺(tái)服務(wù)器部署緩存服務(wù)程序和瓦片服務(wù)程序，2臺(tái)服務(wù)器通過(guò)千兆交換機(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è)置歷史瓦片訪問(wèn)權(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í)，采用不同歷史瓦片訪問(wèn)權(quán)重hw的GDTST算法請(qǐng)求命中率結(jié)果。由圖4可知，當(dāng)相對(duì)緩存大于25%時(shí)，GDTST算法對(duì)于瓦片歷史訪問(wèn)權(quán)重參數(shù)不敏感；而當(dāng)相對(duì)緩存小于25%時(shí)，可以發(fā)現(xiàn)當(dāng)歷史瓦片訪問(wèn)權(quán)重取0.6 或0.8時(shí)，較取其他值時(shí)獲得了更高的瓦片請(qǐng)求命中率。

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

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

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

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

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

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

圖8為FIFO、LFU、LRU和GDTST4種緩存算法延遲節(jié)省率的實(shí)驗(yàn)結(jié)果，由實(shí)驗(yàn)結(jié)果可知，在相對(duì)緩存容量小于80%時(shí)，GDTST算法的延遲節(jié)省率與FIFO 相當(dāng)，但小于LRU和LFU，這是由于GDTST算法的實(shí)現(xiàn)基于優(yōu)先隊(duì)列，其寫(xiě)入與調(diào)整操作都是O(log(n))的時(shí)間復(fù)雜度，而LRU、LFU和FIFO的寫(xiě)入與調(diào)整則實(shí)現(xiàn)了O(1)的時(shí)間復(fù)雜度，同時(shí)，在相對(duì)緩存較小時(shí)，緩存置換操作又較為頻繁，因此，當(dāng)相對(duì)緩存容量較小時(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ù)器端緩存索引，綜合考慮瓦片請(qǐng)求的時(shí)間局部性、空間局部性和用戶主題傾向性，提出了GDTST算法。實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)FIFO、LRU、LFU算法，當(dāng)面對(duì)源瓦片服務(wù)器中多主題瓦片數(shù)據(jù)時(shí)，在不同的相對(duì)緩存下，GDTST 均能取得較高的瓦片請(qǐng)求命中率和字節(jié)命中率，同時(shí)，在相對(duì)緩存較大的情況下?lián)碛懈叩难舆t節(jié)省率，因此，GDTST算法可以有效減輕源瓦片服務(wù)器負(fù)載、縮短用戶等待時(shí)間。但是，GDTST算法緩存更新操作時(shí)間復(fù)雜度較高，下一步工作將優(yōu)化緩存數(shù)據(jù)結(jié)構(gòu)，在相對(duì)緩存較小時(shí)提高緩存算法延遲節(jié)省率。