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

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

(1.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318；2.中國科學(xué)院空天信息創(chuàng)新研究院遙感科學(xué)國家重點(diǎn)實(shí)驗(yàn)室，北京 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)時(shí)間長、渲染效率低的缺點(diǎn)。為了提高客戶端顯示效率，構(gòu)建金字塔模型是重要的解決方案，在不影響畫面視覺效果的同時(shí)，構(gòu)建不同分辨率的多級數(shù)據(jù)來提高繪制速度，節(jié)省繪制所需時(shí)間。構(gòu)建金字塔模型的關(guān)鍵環(huán)節(jié)是對空間數(shù)據(jù)進(jìn)行組織，經(jīng)過組織后的瓦片數(shù)據(jù)可以提升檢索效率。

在大數(shù)據(jù)時(shí)代，由于瓦片數(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)計(jì)算當(dāng)前命中瓦片相鄰及相鄰層級瓦片數(shù)據(jù)的請求頻次；(3)引入瓦片保護(hù)機(jī)制。在瓦片進(jìn)入到緩存空間后，一段時(shí)間內(nèi)無法被置換。這種方式可以有效解決當(dāng)緩存空間已滿時(shí)，新進(jìn)入到緩存空間的瓦片數(shù)據(jù)由于價(jià)值最低而被置換的問題。

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

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

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

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

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

P

個(gè)等級，其中

L

級至

M

-1級為全球尺度；

M

級至

N

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

N

級至

P

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

L

級、

M

級、

N

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

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

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

2 瓦片緩存機(jī)制

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

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

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

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

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

X

,

Y

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

W

，屏幕高度

H

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

D

，以屏幕左下角為原點(diǎn)，計(jì)算屏幕左下角(

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ù)定位速度，索引項(xiàng)TileID采用哈希存儲?；诙喑叨葟?fù)合金字塔的瓦片索引結(jié)構(gòu)為:

Index=(TileID,Value,Size,Frequency,

LastTime,TimeInterval)

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

2.2 MCPCR策略

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

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

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

圖3 瓦片相鄰范圍示意圖

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

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

T

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

t

,其中

t

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

T

的比例。

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

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

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

H

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

C

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

H

+(CurrentTime-LastTime)×

C

]其中，

H

與

C

的和為1，當(dāng)

H

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

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

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

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

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

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

2.3 MCPCR算法流程

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

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

H

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

C

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

3.2 實(shí)驗(yàn)結(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時(shí)，利用FIFO、LRU、LFU、MCPCR四種緩存置換策略進(jìn)行模擬調(diào)度。比較相應(yīng)的字節(jié)命中率及瓦片命中率，圖4中(a)、(b)、(c)、(d)分別代表數(shù)據(jù)集a、b、c、d字節(jié)命中率點(diǎn)線圖，圖5中(a)、(b)、(c)、(d)分別代表數(shù)據(jù)集a、b、c、d瓦片命中率點(diǎn)線圖。

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

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

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

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

4 結(jié)束語

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