基于多尺度復(fù)合金字塔模型的緩存策略研究

王 賀，王志寶，陳良富，趙 亮

(1.東北石油大學(xué) 計算機與信息技術(shù)學(xué)院，黑龍江 大慶 163318；2.中國科學(xué)院空天信息創(chuàng)新研究院遙感科學(xué)國家重點實驗室，北京 100000)

0 引 言

網(wǎng)絡(luò)地理信息系統(tǒng)(WebGIS)是網(wǎng)絡(luò)和地理信息系統(tǒng)的結(jié)合，以互聯(lián)網(wǎng)協(xié)議和終端為基礎(chǔ)形成的客戶端地理信息應(yīng)用系統(tǒng)，與人們的日常生活密不可分。傳統(tǒng)的WebGIS系統(tǒng)通過客戶端向服務(wù)器發(fā)送地理信息相關(guān)的請求，服務(wù)器收到后將相應(yīng)的數(shù)據(jù)返回給客戶端。該方法受網(wǎng)絡(luò)速度和服務(wù)器配置的影響，存在響應(yīng)時間長、渲染效率低的缺點。為了提高客戶端顯示效率，構(gòu)建金字塔模型是重要的解決方案，在不影響畫面視覺效果的同時，構(gòu)建不同分辨率的多級數(shù)據(jù)來提高繪制速度，節(jié)省繪制所需時間。構(gòu)建金字塔模型的關(guān)鍵環(huán)節(jié)是對空間數(shù)據(jù)進(jìn)行組織，經(jīng)過組織后的瓦片數(shù)據(jù)可以提升檢索效率。

在大數(shù)據(jù)時代，由于瓦片數(shù)據(jù)的海量特性和用戶規(guī)模的不斷增長，仍然存在網(wǎng)絡(luò)擁塞、服務(wù)器過載等問題。通過研究瓦片緩存策略，以讀取緩存數(shù)據(jù)的方式來減少對服務(wù)器的請求數(shù)量，可以在數(shù)據(jù)組織的基礎(chǔ)上減輕服務(wù)器和網(wǎng)絡(luò)傳輸?shù)膲毫?。因此，改進(jìn)現(xiàn)有的瓦片緩存策略對網(wǎng)絡(luò)地理信息系統(tǒng)具有重要意義。

在瓦片金字塔的基礎(chǔ)上，該文提出了一種多尺度復(fù)合金字塔模型。與傳統(tǒng)的瓦片金字塔模型相比，它可以統(tǒng)一組織和管理多種類型數(shù)據(jù)。并在此基礎(chǔ)上提出了一種基于多尺度復(fù)合金字塔模型的緩存置換策略(multi-scale compound pyramid cache replacement)，相較于現(xiàn)有的瓦片緩存算法，進(jìn)行了如下優(yōu)化：(1)支持加載多種類型數(shù)據(jù)；(2)考慮瓦片數(shù)據(jù)的空間特性，根據(jù)用戶操作習(xí)慣，動態(tài)計算當(dāng)前命中瓦片相鄰及相鄰層級瓦片數(shù)據(jù)的請求頻次；(3)引入瓦片保護(hù)機制。在瓦片進(jìn)入到緩存空間后，一段時間內(nèi)無法被置換。這種方式可以有效解決當(dāng)緩存空間已滿時，新進(jìn)入到緩存空間的瓦片數(shù)據(jù)由于價值最低而被置換的問題。

1 構(gòu)建多尺度復(fù)合金字塔模型

對多種類型數(shù)據(jù)進(jìn)行組織，傳統(tǒng)的做法是將多種類型數(shù)據(jù)單獨建立索引，建立不同的金字塔模型以分開管理。采用這種方式金字塔的構(gòu)建效率低、管理難度大。所以該文提出了一種能夠統(tǒng)一管理各類數(shù)據(jù)的多尺度復(fù)合金字塔模型，如圖1所示。

圖1 多尺度復(fù)合金字塔模型

多尺度復(fù)合金字塔模型從金字塔的底層到頂層，分辨率逐漸降低，包含了全球、區(qū)域、城市三個尺度數(shù)據(jù)，在不同尺度下又由多種類型數(shù)據(jù)共同組成，且多種類型數(shù)據(jù)在相同層級下表示的地理范圍一致。

在多尺度復(fù)合金字塔模型中，在每種尺度下分別定義1個層級作為實際物理儲存層級，負(fù)責(zé)儲存該尺度范圍內(nèi)的所有信息。如圖2所示，地理空間共分為

P

個等級，其中

L

級至

M

-1級為全球尺度；

M

級至

N

-1級為區(qū)域尺度；

N

級至

P

-1級為城市尺度。將多種類型數(shù)據(jù)根據(jù)三個尺度進(jìn)行重新組織，并分別選擇

L

級、

M

級、

N

級存儲該尺度下的元數(shù)據(jù)信息。

圖2 多尺度組織模型示意圖

多尺度復(fù)合金字塔模型本質(zhì)上是利用地理空間劃分將同一尺度下不同類型元數(shù)據(jù)存儲到統(tǒng)一的存儲單元或單元組中，根據(jù)索引實現(xiàn)以空間區(qū)域為基礎(chǔ)的文件組織管理體系。采用這種數(shù)據(jù)組織與管理技術(shù)可以將用戶訪問數(shù)據(jù)的空間區(qū)域位置與數(shù)據(jù)文件本身表達(dá)的空間區(qū)域位置建立直接關(guān)聯(lián)，提高了海量數(shù)據(jù)的尋址檢索。

2 瓦片緩存機制

傳統(tǒng)的緩存置換算法主要有：先進(jìn)先出置換算法(FIFO)、最近最少使用瓦片置換算法(LRU)、最不經(jīng)常使用置換算法(LFU)。國內(nèi)外學(xué)者針對瓦片數(shù)據(jù)緩存算法做了較多研究，Kang等對瓦片預(yù)取和替換方式進(jìn)行了研究，根據(jù)計算結(jié)果留下概率高的瓦片；在此基礎(chǔ)上，張婷婷提出了基于時空熱度的瓦片緩存置換策略，可以快速傳輸影像數(shù)據(jù)；Hsiao等將多核gpu共享緩存中的瓦片進(jìn)行分組，提出了一種基于多核位置感知的緩存置換算法(MLCR)；史孝國通過考慮瓦片的訪問頻率及瓦片數(shù)據(jù)大小計算瓦片的保留價值，對置換算法進(jìn)行了改進(jìn)；涂振發(fā)等提出了一種最小空間數(shù)據(jù)價值緩存置換算法(GDLVF),基于時間、頻率及空間位置計算瓦片價值，將價值最低的瓦片置換；劉佳星等提出了基于地理單元熱度的瓦片緩存置換算法(GUH)，通過考慮空間特性，結(jié)合貪婪算法置換出熱度值最低的瓦片；陸曄等研究了基于主題時空價值的瓦片緩存算法(GDTST)，綜合考慮了時間局部性、空間局部性以及用戶主題傾向性，置換出主題時空價值最低的瓦片。傳統(tǒng)的緩存置換算法沒有考慮到瓦片數(shù)據(jù)的空間位置特性，瓦片命中率效果較差；傳統(tǒng)的緩存置換算法只考慮了瓦片進(jìn)入緩存時間及命中次數(shù)，瓦片命中率較差。在上述研究中，依然存在如下三個問題：(1)緩存置換策略都是基于同一類型數(shù)據(jù)進(jìn)行研究，不適用于多種類型數(shù)據(jù)進(jìn)行加載；(2)部分研究人員雖然考慮了空間位置特性以及請求瓦片對下一時刻其鄰近位置瓦片被訪問造成的影響，但是在進(jìn)行研究時沒有考慮用戶的操作習(xí)慣，請求瓦片對臨近位置瓦片影響相同；(3)未設(shè)置保護(hù)機制，新進(jìn)入緩存的瓦片由于價值低可能會很快被置換出去。

因此，該文提出了一種基于多尺度復(fù)合金字塔模型的緩存置換策略MCPCR。MCPCR滿足多種類型數(shù)據(jù)在客戶端進(jìn)行緩存，并充分考慮瓦片數(shù)據(jù)的空間特性，根據(jù)用戶操作習(xí)慣，動態(tài)計算當(dāng)前命中瓦片相鄰及相鄰層級瓦片數(shù)據(jù)的請求頻次，當(dāng)瓦片數(shù)據(jù)進(jìn)入緩存時，計算當(dāng)前瓦片數(shù)據(jù)價值，當(dāng)緩存空間已滿或達(dá)到閾值時，緩存空間中價值最低的瓦片將被替換。同時引入瓦片保護(hù)機制，在瓦片進(jìn)入到緩存空間后，一段時間內(nèi)無法被置換，避免當(dāng)緩存空間已滿時，進(jìn)行置換操作時將新進(jìn)入到緩存空間的瓦片數(shù)據(jù)剔除。

2.1 瓦片緩存索引設(shè)計

當(dāng)用戶在客戶端請求數(shù)據(jù)時，首先要在緩存中查找是否存在相關(guān)數(shù)據(jù)，因此，為了實現(xiàn)緩存中數(shù)據(jù)的快速檢索，需要對緩存索引進(jìn)行設(shè)計，從而提高數(shù)據(jù)檢索速度，本次研究基于多尺度復(fù)合金字塔模型設(shè)計了索引機制。

服務(wù)器端為已經(jīng)組織好的多分辨率層級的復(fù)合瓦片金字塔模型。當(dāng)客戶端請求相應(yīng)數(shù)據(jù)時，當(dāng)縮放層級為Z時，獲取到當(dāng)前顯示區(qū)域中心點的地理坐標(biāo)Center(

X

,

Y

)；根據(jù)屏幕寬度

W

，屏幕高度

H

，以及瀏覽器顯示的單位像素表示的實際地理距離

D

，以屏幕左下角為原點，計算屏幕左下角(

X

,

Y

)及屏幕右上角(

X

,

Y

)地理坐標(biāo):

根據(jù)請求數(shù)據(jù)類型以及在該層級下地理范圍對該類型瓦片數(shù)據(jù)行列號進(jìn)行轉(zhuǎn)換，并向復(fù)合金字塔模型中請求相應(yīng)數(shù)據(jù)，將查詢到的數(shù)據(jù)向客戶端進(jìn)行傳遞。

瓦片金字塔模型中瓦片的生成都是先將柵格數(shù)據(jù)或矢量數(shù)據(jù)進(jìn)行切片，生成瓦片矩陣后再通過分級分塊的方式構(gòu)建多尺度瓦片矩陣集，每張瓦片通過層級與行列號唯一確定。本次研究是對多尺度復(fù)合金字塔模型進(jìn)行研究，具有多種類型瓦片數(shù)據(jù)，因此做出如下定義:

定義1：多尺度復(fù)合金字塔模型包含多種類型數(shù)據(jù)瓦片金字塔模型，每一張瓦片都可以通過數(shù)據(jù)類型、層級及行列號唯一確定。TileID代表多尺度復(fù)合金字塔模型的瓦片索引值，可以表示為:

TileID=(Type,Layer,Row,Column)

其中，Type表示瓦片數(shù)據(jù)類型，Layer表示該類型瓦片數(shù)據(jù)所在層級號，Row表示瓦片在該級下的行號，Column表示瓦片在該級下的列號。為了加快數(shù)據(jù)定位速度，索引項TileID采用哈希存儲。基于多尺度復(fù)合金字塔的瓦片索引結(jié)構(gòu)為:

Index=(TileID,Value,Size,Frequency,

LastTime,TimeInterval)

其中，Value表示當(dāng)前瓦片的價值，Size表示瓦片所占空間的大小，F(xiàn)requency表示該瓦片的請求頻次，LastTime表示瓦片上一次被請求時間，TimeInterval表示瓦片最近兩次被請求的時間間隔。

2.2 MCPCR策略

MCPCR策略，當(dāng)緩存空間已滿或達(dá)到閾值時，置換出過了保護(hù)期限且價值最低的瓦片數(shù)據(jù)。其中瓦片價值為:

其中，F(xiàn)requency(a)表示基于用戶操作習(xí)慣的空間訪問頻次，TimeInterval(a)表示當(dāng)前瓦片的歷史平均訪問間隔，Type(a)表示數(shù)據(jù)類型權(quán)重。

用戶在客戶端最常用的操作是平移操作和縮放操作。圖3所示為瓦片相鄰范圍示意圖。

圖3 瓦片相鄰范圍示意圖

當(dāng)用戶操作為平移操作時，可以從上、下、左、右、左上、左下、右上、右下八個方向請求瓦片數(shù)據(jù)；當(dāng)用戶進(jìn)行縮放操作時，有放大操作和縮小操作兩種情況。放大操作是指向服務(wù)器請求當(dāng)前位置高層級數(shù)據(jù)；縮小操作是指向服務(wù)器請求當(dāng)前位置低層級數(shù)據(jù)。也就是說，在某個時間用戶訪問了瓦片數(shù)據(jù)，附近的瓦片和相鄰級別的瓦片數(shù)據(jù)在下一次再次被訪問的概率更高。故定義瓦片的請求頻次Frequency為：

定義2：設(shè)Frequency為瓦片請求頻次。根據(jù)用戶操作歷史庫，分別記錄用戶操作up、down、left、right、upperLeft、lowerLeft、upperRight、lowerRight、upLayer、nextLayer及操作總次數(shù)

T

。當(dāng)瓦片被命中時，此瓦片F(xiàn)requency = Frequency+1，緩存中相鄰?fù)咂瑪?shù)據(jù)及相鄰層級瓦片數(shù)據(jù)Frequency = Frequency +

t

,其中

t

為用戶分別在10個方向上的操作占總操作次數(shù)

T

的比例。

Frequency本質(zhì)上是瓦片的累計訪問頻率及其相鄰范圍影響權(quán)值的總和。當(dāng)瓦片被請求時，其相鄰?fù)咂跋噜弻蛹壨咂乱淮伪徽埱蟮母怕试黾樱⒏鶕?jù)用戶操作習(xí)慣將不同方向上的瓦片賦予不同的權(quán)重。

通過計算瓦片歷史平均間隔實現(xiàn)對瓦片數(shù)據(jù)命中在時間維度上產(chǎn)生的影響，同時考慮當(dāng)前訪問時間間隔以及歷史訪問時間間隔。故定義歷史平均訪問間隔TimeInterval:

定義3:設(shè)TimeInterval為歷史平均訪問間隔，CurrentTime表示當(dāng)前瓦片訪問時間，LastTime表示瓦片上一次訪問時間，TimeInterval表示瓦片最近兩次被獲取的時間間隔，

H

為歷史訪問權(quán)重，

C

為當(dāng)前訪問權(quán)重。TimeInterval公式為:TimeInterval=[TimeInterval×

H

+(CurrentTime-LastTime)×

C

]其中，

H

與

C

的和為1，當(dāng)

H

的越大時，認(rèn)為歷史訪問間隔對瓦片請求的影響越大。

由于數(shù)據(jù)類型多樣，針對緩存置換策略的制定需要考慮到數(shù)據(jù)類型權(quán)重，同時考慮到瓦片單個數(shù)據(jù)大小，對數(shù)據(jù)類型權(quán)重進(jìn)行定義:

其中，Type(i)表示訪問的某一類型數(shù)據(jù)總和，Type(s)表示訪問瓦片全部類型的總數(shù)量，并考慮瓦片大小對于緩存置換的影響，單個瓦片數(shù)據(jù)量越大，影響度越低，當(dāng)緩存空間已滿時，優(yōu)先置換出數(shù)據(jù)較大的瓦片。

為了避免在緩存空間已滿，新進(jìn)入的瓦片由于價值最低，下一次置換操作時被移除，引入瓦片保護(hù)機制，也就是說，瓦片數(shù)據(jù)在剛剛進(jìn)入緩存空間的一段時間內(nèi)不能被替換。故定義瓦片保護(hù)時間ProtectTime:

定義4：設(shè)瓦片保護(hù)時間為ProtectTime，瓦片數(shù)據(jù)進(jìn)入到緩存空間后初始化ProtectTime，進(jìn)入保護(hù)期，并隨著時間的增加不斷減小，當(dāng)ProtectTime為0時，保護(hù)期結(jié)束，瓦片保護(hù)時間為ProtectTime=ProtextTime -Time。

其中，Time為當(dāng)前時間與瓦片進(jìn)入到緩存空間的時間差。

2.3 MCPCR算法流程

(1)新的瓦片數(shù)據(jù)進(jìn)入緩存空間時，需要初始化瓦片信息，包括瓦片類型Type，層級Layer，行列號Row、Column，價值Value以及保護(hù)時間ProtectTime；

(2)判斷緩存空間能否容納新瓦片，當(dāng)緩存空間充足時，將瓦片存儲在緩存空間中并執(zhí)行步驟(3)；當(dāng)緩存空間不足時，則執(zhí)行步驟(5)；

(3)將瓦片數(shù)據(jù)發(fā)送至客戶端，同時得到該瓦片相鄰?fù)咂瑪?shù)據(jù)信息及相鄰層級瓦片數(shù)據(jù)信息，將已經(jīng)在緩存空間中的瓦片數(shù)據(jù)執(zhí)行步驟(4),否則一次性從服務(wù)器中獲取所有瓦片；

(4)更新緩存中瓦片價值Value；

(5)判斷ProtectTime是否為0，若已經(jīng)為0，說明已經(jīng)過期，同時不再更新；若不為0，則繼續(xù)更新；

(6)計算緩存空間中保護(hù)機制過期且價值最低的瓦片，按順序進(jìn)行移除直至緩存空間充足；

(7)MCP算法結(jié)束。

3 實驗與分析

3.1 實驗環(huán)境

實驗通過Fiddler采集客戶端獲取瓦片日志數(shù)據(jù)，根據(jù)獲取到的瓦片數(shù)據(jù)計算用戶操作，模擬用戶瓦片數(shù)據(jù)操作記錄，共計1 267 154條記錄。其中最大的瓦片大小為48.4 KB，最小的瓦片大小為232 B。實驗環(huán)境為Intel(R) Core i5-8300H @ 2.30 GHz，4核CPU，12 GB內(nèi)存。根據(jù)用戶請求記錄，獲得瓦片的類型、層級、行列號、大小及時間等數(shù)據(jù)，模擬用戶在客戶端的行為。

在MCPCR算法中，需要設(shè)置歷史訪問權(quán)重

H

以及當(dāng)前訪問權(quán)重

C

，通過實驗測試，當(dāng)歷史訪問權(quán)重設(shè)置為0.7，當(dāng)前訪問權(quán)重設(shè)置為0.3時，實驗效果較好。實驗共由兩個部分組成，首先分別選取三種數(shù)據(jù)類型單獨進(jìn)行實驗，第二部分同時選取三種類型數(shù)據(jù)進(jìn)行實驗，統(tǒng)計緩存空間中的字節(jié)命中率及瓦片命中率，并與傳統(tǒng)緩存策略FIFO、LRU、LFU進(jìn)行對比。

3.2 實驗結(jié)果與分析

將用戶請求的日志結(jié)果分別設(shè)為數(shù)據(jù)集a、b、c、d，其中數(shù)據(jù)集a、b、c僅包含單一類型數(shù)據(jù)，數(shù)據(jù)集d包含a、b、c數(shù)據(jù)中三種類型數(shù)據(jù)。在設(shè)置客戶端緩存大小為20 M、40 M、60 M、80 M、100 M時，利用FIFO、LRU、LFU、MCPCR四種緩存置換策略進(jìn)行模擬調(diào)度。比較相應(yīng)的字節(jié)命中率及瓦片命中率，圖4中(a)、(b)、(c)、(d)分別代表數(shù)據(jù)集a、b、c、d字節(jié)命中率點線圖，圖5中(a)、(b)、(c)、(d)分別代表數(shù)據(jù)集a、b、c、d瓦片命中率點線圖。

(a)數(shù)據(jù)集a字節(jié)命中率

(a)數(shù)據(jù)集a瓦片命中率

(d)數(shù)據(jù)集d瓦片命中率

通過實驗可知，在三種不同的數(shù)據(jù)集下，四種緩存置換策略的命中率都會隨著緩存空間大小的增加而逐漸增加，曲線最終趨近于平緩。由四種緩存置換策略進(jìn)行對比可知，在對單一類型數(shù)據(jù)加載時，F(xiàn)IFO緩存置換策略命中率最低，LRU緩存策略淘汰最后被訪問時間最久的數(shù)據(jù)，要優(yōu)于FIFO，LFU緩存置換策略能夠避免LRU周期性或者偶發(fā)性的操作導(dǎo)致緩存命中率下降的問題，整體優(yōu)于LRU，MCPCR由于在考慮時間和空間因素的基礎(chǔ)上，引入用戶操作習(xí)慣因素及保護(hù)機制，在不同緩存空間大小下的命中率要優(yōu)于其他三個緩存置換策略。在對不同類型數(shù)據(jù)進(jìn)行加載時，傳統(tǒng)緩存置換策略命中率下降明顯，MCPCR依舊能夠保持良好的緩存命中率，通過實驗證明，MCPCR策略能夠有效支持多種類型數(shù)據(jù)同時進(jìn)行緩存，并能夠有效提升緩存命中效率。

4 結(jié)束語

該文提出了一種多尺度復(fù)合金字塔數(shù)據(jù)組織模型，能夠有效地組織和管理不同類型的瓦片數(shù)據(jù)。基于該模型，設(shè)計了瓦片緩存索引?？紤]到用戶的操作習(xí)慣、歷史訪問對瓦片價值的影響并引入瓦片保護(hù)機制，提出了一種基于多尺度復(fù)合金字塔模型的緩存替換策略MCPCR。實驗結(jié)果表明，對同一種瓦片數(shù)據(jù)類型進(jìn)行加載時，MCPCR在不同大小的緩存空間中命中率均優(yōu)于其他幾種算法，在對多種類型瓦片數(shù)據(jù)進(jìn)行加載時，MCPCR仍然能夠保持良好的命中率?？梢杂行еС植煌愋屯咂瑪?shù)據(jù)加載，從而提高用戶的響應(yīng)速度。