一種基于主題時空價值的服務器端瓦片緩存算法

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

（1.浙江大學浙江省資源與環境信息系統重點實驗室,浙江杭州310028；2.浙江大學地理信息科學研究所,浙江 杭州310027；3.山東省國土測繪院，山東 濟南250102）

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

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

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

1 基于主題金字塔的瓦片緩存索引設計

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

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

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

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

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

圖1 索引編碼結構Fig.1 Index coding structure

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

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

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

圖2 2級瓦片索引結構Fig.2 Two-level tile index structure

2 基于主題時空價值的瓦片緩存置換算法

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

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

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

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

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

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

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

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

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

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

2.2 瓦片歷史平均訪問間隔

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

定義5瓦片歷史平均訪問間隔。設avgAccessTime表示瓦片的歷史平均訪問時間間隔，lastAccessTime為瓦片上次被訪問的時間，hw為歷史瓦片訪問權重，currentTime表示當前時間，當瓦片被再次訪問時，avgAccessTime 按下式更新：

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

2.3 瓦片主題權重

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

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

weightTheme 實質上通過緩存中不同瓦片主題所占比例來反映用戶的主題傾向性，即認為緩存中某一主題瓦片數據所占比例較大，則下一時刻該主題的瓦片較其他主題的瓦片被訪問的概率要大。同時為了提高瓦片對象的命中率，該權重與數據大小成反比，認為數據較小的瓦片權重更大，即應優先置換單個數據較大的瓦片而不是多個數據較小的瓦片。

2.4 基于主題時空價值緩存算法的流程

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

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

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

(3)創建并初始化主題索引節點themeNode，加入一級索引表themeIndex，轉(6)；

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

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

(6)根據t、l、x、y構造瓦片及其鄰接范圍內其余瓦片的URL，從源瓦片服務器獲取瓦片鄰接范圍內所有瓦片，同時，返回被請求瓦片；

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

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

(9)對于每一張瓦片，生成其tileId，當tileId 在索引中時，僅更新其瓦片索引節點的freqSpatial和gdtst；當tileId 不在索引中時，創建并初始化瓦片索引節點，加入到二級索引表tileIndex中，并將瓦片數據加入緩存。

(10)結束。

在實際應用中，步驟(5)和(6)中的返回瓦片數據操作和其余緩存更新操作異步進行，因此鄰接范圍內瓦片的更新不會影響瓦片數據的返回延時。同時，對于步驟(6)請求的鄰接范圍瓦片操作，當瓦片服務器實現批量獲取接口時，僅需請求1次便可獲取鄰接范圍內瓦片，對源瓦片服務器不會產生額外的負載。

3 實驗與分析

3.1 實驗內容與環境

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

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

3.2 GDTST算法的參數選擇

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

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

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

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

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

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

3.3 實驗結果與分析

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

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

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

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

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

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

4 結 論

設計了面向多主題瓦片數據的服務器端緩存索引，綜合考慮瓦片請求的時間局部性、空間局部性和用戶主題傾向性，提出了GDTST算法。實驗結果表明，相較于傳統FIFO、LRU、LFU算法，當面對源瓦片服務器中多主題瓦片數據時，在不同的相對緩存下，GDTST 均能取得較高的瓦片請求命中率和字節命中率，同時，在相對緩存較大的情況下擁有更高的延遲節省率，因此，GDTST算法可以有效減輕源瓦片服務器負載、縮短用戶等待時間。但是，GDTST算法緩存更新操作時間復雜度較高，下一步工作將優化緩存數據結構，在相對緩存較小時提高緩存算法延遲節省率。