湯求毅,王超,杜震洪*,張豐,劉仁義
(1.浙江大學(xué)浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,浙江 杭州 310028; 2.浙江大學(xué)地理信息科學(xué)研究所,浙江杭州 310027)
近年來,隨著遙感影像數(shù)據(jù)量的快速增長,網(wǎng)絡(luò)地理信息服務(wù)(network geographic information service,NGIS)逐漸向云服務(wù)發(fā)展[1-3],進(jìn)一步促使NGIS 提供高效實(shí)時的遙感影像預(yù)覽、可視化及漫游服務(wù)。由于遙感影像單幅數(shù)據(jù)量過大,不適合在網(wǎng)絡(luò)中頻繁傳輸,在實(shí)際應(yīng)用中往往用瓦片實(shí)現(xiàn)可視化[4],因此,高效、實(shí)時的瓦片服務(wù)是支撐高性能NGIS 的基礎(chǔ)技術(shù)之一。然而,數(shù)據(jù)量和用戶量的激增,導(dǎo)致瓦片服務(wù)器服務(wù)過載,造成瓦片服務(wù)的延遲與低效[4-5]。瓦片緩存可以減少對瓦片服務(wù)器直接訪問的頻率,減輕瓦片服務(wù)器的壓力。目前,瓦片緩存架構(gòu)主要分為客戶端緩存和服務(wù)端緩存2 種,由于前者在云環(huán)境下存在應(yīng)用局限性[6],Google Earth 建議使用服務(wù)端緩存解決瓦片服務(wù)延遲的問題[7]。良好的緩存置換算法可以有效提高緩存命中率[5,8],進(jìn)一步減輕瓦片服務(wù)器壓力,因此,設(shè)計高命中率的瓦片緩存置換算法成為當(dāng)前研究的熱點(diǎn)和難點(diǎn)[9]。
瓦片緩存置換算法的設(shè)計需要考慮瓦片訪問模式和瓦片數(shù)據(jù)特征[10]。瓦片數(shù)據(jù)在訪問模式上存在短期流行度和長期流行度[7,11-12],能反映瓦片的訪問趨勢。短期流行度可通過瓦片訪問的時間局部性和空間局部性進(jìn)行表達(dá)[13]。時間局部性是指近期被訪問過的瓦片被再次訪問的概率更高,空間局部性是指與當(dāng)前被訪問瓦片相鄰的瓦片被訪問的概率更高,時間局部性和空間局部性相互關(guān)聯(lián)、相互影響,對外統(tǒng)一表現(xiàn)為時間局部性[7,11]。長期流行度可通過瓦片訪問熱度,即瓦片的累計訪問頻次表達(dá)[4,14-15],熱度值高的瓦片被再次訪問的概率更高[4]。瓦片數(shù)據(jù)特征包含瓦片大小特征、瓦片主題特征等,瓦片大小特征是指不同的瓦片存在大小差異。由于緩存過程中大文件越多,緩存命中率越低[16],因此瓦片大小特征也是不可忽略的因素。
國內(nèi)外學(xué)者基于瓦片訪問模式和瓦片數(shù)據(jù)特征,對瓦片緩存置換算法開展了大量研究。LEE等[17]提出了基于馬爾可夫鏈的瓦片緩存預(yù)取和置換算法,通過置入預(yù)取概率高的瓦片,置換出轉(zhuǎn)移概率低的瓦片。王浩等[14]提出了基于瓦片存活壽命和訪問熱度的緩存置換算法,通過計算瓦片平均存活時間得到瓦片年齡,并置換出年齡最高的瓦片緩存。涂振發(fā)等[18]提出了基于瓦片數(shù)據(jù)價值的緩存置換算法,綜合考慮時間價值、空間價值和數(shù)據(jù)大小價值對瓦片數(shù)據(jù)價值進(jìn)行定義,并置換出價值最小的瓦片緩存。ULUAT 等[19]基于模糊邏輯的推理引擎,提出了一種基于優(yōu)先級的瓦片預(yù)測方法。LI等[20]對用戶進(jìn)行分組,研究了基于不同用戶組訪問密集性的瓦片緩存置換算法。劉佳星等[15]利用瓦片金字塔特性,提出了基于地理單元熱度的瓦片緩存置換算法。這些算法結(jié)合時空特性定義了各自瓦片價值模型,并根據(jù)價值大小置換瓦片,在一定程度上提高了緩存命中率[4]。但這些算法在應(yīng)用于服務(wù)端瓦片緩存時還存在以下問題:(1)相較于傳統(tǒng)的緩存置換算法,上述算法的復(fù)雜性高、效率低,不適合大量瓦片緩存置換的應(yīng)用場景;(2)大多數(shù)為客戶端緩存置換算法,不適合基于網(wǎng)絡(luò)的服務(wù)端瓦片緩存置換場景;(3)重點(diǎn)分析了瓦片訪問對水平相鄰?fù)咂挠绊?,未考慮對其上下層瓦片的影響;(4)未考慮瓦片大小差異對緩存命中率的影響。
老化算法原本用于頁面緩存置換,同時具備最近最少使用(least recently used,LRU)和最不經(jīng)常使用(least frequently used,LFU)2 種算法的優(yōu)點(diǎn),在短期流行度擬合和運(yùn)行性能方面具備優(yōu)勢,且具擴(kuò)展性和移植性[21-22]。本文將老化算法引入服務(wù)端瓦片緩存置換場景,綜合瓦片訪問的長短期流行度和瓦片大小特征對老化算法進(jìn)行改造,提出時空老化模型,并設(shè)計了基于時空老化模型的服務(wù)端瓦片緩存置換算法(server-side cache replacement algorithm based on spatiotemporal aging model for tiles,SSAT),具有以下優(yōu)勢:(1)運(yùn)行效率高,適用于大量瓦片緩存置換場景;(2)可更好地擬合瓦片訪問的時間局部性;(3)兼顧瓦片訪問對水平和垂直2 個空間維度的影響,更全面地體現(xiàn)其空間局部性;(4)顧及瓦片大小特征,進(jìn)一步提高瓦片緩存命中率。
老化算法是一種操作系統(tǒng)頁面緩存置換算法[22],其數(shù)據(jù)結(jié)構(gòu)和工作流程如圖1 所示。R 位用于標(biāo)記頁面在時鐘周期內(nèi)的引用情況,若頁面被引用,則將R 位設(shè)置為1,若頁面進(jìn)入新的時鐘周期,則將R 位設(shè)置為0。計數(shù)器C 用于記錄頁面在各時鐘周期內(nèi)的訪問情況,值越大,表示該頁面被訪問時間間隔越短[23]。計數(shù)器的長度一般取決于處理器的位數(shù),老化表是所有計數(shù)器的集合。
假設(shè)緩存中有頁面P1、P2和P3。在初始時刻,3個頁面的R 位和計數(shù)器C 均為0。假設(shè)在時鐘周期T1內(nèi),只有P1和P3被引用,則需將R1和R3設(shè)置為1。當(dāng)時鐘從T1進(jìn)入T2時,先如圖1 中黃色箭頭所示,將所有計數(shù)器C1、C2、C3右移一位,接著如圖1 中綠色箭頭所示,將R1、R2、R3分別設(shè)置為計數(shù)器的最高位,最后將R1、R2、R3重新設(shè)置為0。算法在時鐘周期T3、T4、T5內(nèi)的操作過程相同。
圖1 老化算法工作流程Fig.1 Aging algorithm workflow
當(dāng)內(nèi)存不足時,老化算法會根據(jù)計數(shù)器C 的大小置換頁面[23]。C 越大,其高位為1 的概率越大,表明其被訪問的時間間隔越短。假設(shè)在T5內(nèi)需要進(jìn)行緩存置換,算法會根據(jù)計數(shù)器C1、C2、C3的大小,找出最小值C2,并置換出其對應(yīng)頁面的P2緩存。老化算法的優(yōu)點(diǎn)是,最新引用的頁面比頻繁引用的頁面具有更高的優(yōu)先級[24]。
頁面緩存置換算法只需要考慮時間局部性[22],而瓦片數(shù)據(jù)有空間局部性和大小差異,因此在應(yīng)用時需要對老化算法進(jìn)行擴(kuò)展。
時空老化模型以老化算法的計數(shù)器周期性移位為基準(zhǔn),綜合考慮瓦片訪問長短期流行度和瓦片大小,并將其作為比重進(jìn)行調(diào)節(jié),得到瓦片時空老化程度,記為V(ssat)。當(dāng)緩存空間不足時,SSAT 會置換出V(ssat)最低的瓦片緩存。時空老化模型的表達(dá)式為
V(ssat)=V(age)?(V(heat)+V(size)),(1)其中,?為右移運(yùn)算符,V(age)為瓦片時間老化程度,V(heat)為瓦片空間訪問熱度價值,V(size)為瓦片大小價值。V(heat)和V(size)通過影響V(age)右移的方式參與調(diào)節(jié)。
1.2.1 瓦片時間老化程度
老化算法在原理上利用了時間局部性[24],因此直接用老化表計數(shù)器值表示瓦片訪問的短期流行度,定義如下:
定義1 瓦片老化表。每張瓦片各自對應(yīng)一個32 位的計數(shù)器,瓦片老化表是計數(shù)器的集合。
定義2 瓦片老化時鐘周期。與老化算法的時鐘周期相對應(yīng),記為T。每經(jīng)過時間T,瓦片老化表中每個計數(shù)器的值右移一位。
定義3 瓦片時間老化程度。可用計數(shù)器的值表示,值越小,表示瓦片時間老化程度越高。
1.2.2 瓦片空間訪問熱度價值
空間位置相鄰的瓦片,在訪問時間上也傾向于相鄰?fù)咂U_定義單張瓦片影響的鄰域空間范圍,是提高瓦片緩存命中率的關(guān)鍵。因此,定義如下:
定義4 瓦片水平鄰域。以被訪問的瓦片為中心,在同層中與該瓦片直接相鄰的8 張瓦片。
定義5 瓦片垂直鄰域。在下一層級中,由被訪問的瓦片分裂得到的4 張瓦片。
定義6 瓦片空間訪問熱度權(quán)重。由于瓦片訪問存在空間局部性,瓦片空間訪問熱度權(quán)重表示被訪問瓦片對其水平鄰域和垂直鄰域的影響程度,記為vol。
定義7 瓦片空間訪問熱度??捎猛咂睦塾嫳辉L問頻次表示,記為heat。當(dāng)瓦片被訪問命中后,每增加1 heat,其水平鄰域和垂直鄰域中的瓦片heat增加vol,計算過程如圖2 所示。
圖2 瓦片水平鄰域和瓦片垂直鄰域Fig.2 Tile horizontal neighborhood and vertical neighborhood
定義8 瓦片空間訪問熱度價值。由瓦片空間訪問熱度進(jìn)行歸一化處理得到。在調(diào)節(jié)V(age)的過程中,heat 不同的瓦片之間應(yīng)體現(xiàn)出適當(dāng)?shù)牟罹?,因此,定義V(heat):
其中,maxHeat 為緩存中最大的瓦片空間訪問熱度,Me 為緩存中所有heat 的中位數(shù)。設(shè)置Me 是為了避免當(dāng)heat 與maxHeat 相差較大時,對V(age)產(chǎn)生過大的移位影響。假設(shè)緩存中有3 張瓦片A,B和C,其heat 分別為1 000,500 和10,緩存中maxHeat 為10 000,Me 為100。 此時瓦片A 的V(heat)≈3,瓦片B 的V(heat)≈4,在時空老化模型中,瓦片A 將影響V(age)右移3 位,瓦片B 將影響V(age)右移4 位,即heat 值相差2 倍的瓦片,相當(dāng)于一個瓦片時鐘周期沒有被訪問。而瓦片C 的heat 與maxHeat 相差1 000 倍,若直接用heat 計算,將得到V(heat)≈9,這對于32 位的V(age)來說,產(chǎn)生的移位影響過大,會造成V(age)信息丟失。若取heat=Me,則得到V(heat)≈6,這既體現(xiàn)了差距,又避免了對V(age)信息產(chǎn)生移位污染??偟膩碚f,V(heat)的計算方式可以滿足應(yīng)用需求。
1.2.3 瓦片大小價值
遙感影像金字塔瓦片的大小可能相差近百倍,如果小瓦片擁有更高的優(yōu)先級,則會提高瓦片緩存命中率[22]。將不同大小的瓦片所對應(yīng)的優(yōu)先級稱為瓦片大小價值,記為V(size)。與V(heat)的作用類似,V(size)也是以移位的形式對老化表計數(shù)器進(jìn)行調(diào)節(jié)。在調(diào)節(jié)過程中,大小不同的瓦片之間應(yīng)該體現(xiàn)出適當(dāng)?shù)牟罹?。定義V(size)為
在運(yùn)行過程中,緩存服務(wù)器可逐漸保存大量瓦片。當(dāng)客戶端的請求到達(dá)緩存服務(wù)器時,需要高效的索引機(jī)制,檢索其是否存在目標(biāo)瓦片。根據(jù)瓦片服務(wù)的統(tǒng)一資源定位符(uniform resource locator,URL)規(guī)則,參照老化算法原理設(shè)計了一種以瓦片為粒度的緩存索引方法,如圖3 所示。
圖3 服務(wù)端瓦片緩存索引結(jié)構(gòu)Fig.3 Server-side tile cache index structure
該索引方法基于鍵值對的哈希索引結(jié)構(gòu),對URL 中的level、row 和col 進(jìn)行CityHash64 編碼,將得到的64 位散列值作為哈希鍵(HashKey),對應(yīng)的哈希值(HashValue)包括瓦片信息(tileNode)、R 位(referenceBit)、計數(shù)器(counter)、空間訪問熱度值(tileSpatailHeat)和瓦片大?。╯ize)。
SSAT 在執(zhí)行過程中需要陸續(xù)啟動一個程序主線程和2 個工作線程。程序主線程隨緩存服務(wù)器的啟動而啟動,負(fù)責(zé)初始化算法運(yùn)行環(huán)境。工作線程包括定時器線程和瓦片請求響應(yīng)線程,定時器線程主要負(fù)責(zé)瓦片老化表周期性移位;瓦片請求響應(yīng)線程主要負(fù)責(zé)處理客戶端的瓦片訪問請求、查詢瓦片緩存以及置入、換出瓦片等,步驟如下。
(1)啟動瓦片緩存服務(wù)器主程序,建立緩存索引和瓦片老化表,設(shè)置瓦片老化時鐘周期T,創(chuàng)建定時器線程,監(jiān)聽用戶請求;
(2)執(zhí)行定時器線程周期,每經(jīng)過一個T,先將所有計數(shù)器的值右移一位,再將瓦片的R 位置于計數(shù)器的最高位,最后將所有的R 位清零;
(3)當(dāng)收到瓦片請求時,瓦片請求響應(yīng)線程啟動,對URL 的level、row、col 進(jìn)行編碼,并通過編碼值查找緩存索引,若命中,則轉(zhuǎn)至步驟(6),否則,轉(zhuǎn)至步驟(4);
(4)根據(jù)level、row、col 信息,從磁盤上讀取目標(biāo)瓦片,同時返回請求;
(5)判斷緩存剩余空間是否充足,若充足,則將命中的瓦片直接放入緩存,創(chuàng)建索引,然后轉(zhuǎn)至步驟(6);否則,轉(zhuǎn)至步驟(7);
(6)將命中瓦片的R 位設(shè)置為1,空間訪問熱度值增加1,同時將緩存中存在的該瓦片水平鄰域和垂直鄰域中其他瓦片的空間訪問熱度值增加vol;
(7)當(dāng)緩存空間不足時,先按照時空老化模型計算每個瓦片的V(ssat),再置換V(ssat)最小的瓦片,刪除緩存索引,直至空間充足。
實(shí)驗(yàn)數(shù)據(jù)為谷歌地圖瓦片,整套瓦片共21 層(最高為0 層,最低為20 層),共6 077 501 張、6.84 GB,其中最大的瓦片為1 492 KB,最小的瓦片為6 KB。實(shí)驗(yàn)使用了3 臺配置為Windows Server 2012 操作系統(tǒng),Intel(R)Core(TM)i7-8750H CPU @2.2 GHz,512 GB SSD 和8 GB RAM 的服務(wù)器。
實(shí)驗(yàn)過程遵循控制變量法,(1)設(shè)置最大可用緩存空間為500 MB,并以50 MB 為間隔設(shè)置10 個不同的緩存空間;(2)不使用緩存直接訪問瓦片服務(wù),生成152 841 條瓦片請求日志,提取日志中的瓦片層級、行列號和請求時間,生成瓦片訪問次序列表;(3)按照列表順序,依次訪問瓦片緩存服務(wù),統(tǒng)計總訪問次數(shù)、請求命中次數(shù)、訪問時長等信息。
在SSAT 中,需要設(shè)置瓦片時鐘周期T和瓦片空間訪問熱度權(quán)重vol。本文在緩存空間為500 MB的條件下進(jìn)行實(shí)驗(yàn),分別記錄了T和vol 對緩存命中率的影響,結(jié)果如圖4 所示。由圖4(a)可知,SSAT的緩存命中率隨T的增大呈現(xiàn)先減小后保持不變的特征,其主要原因是,T增大,表示老化表周期性移位的時間間隔增大,進(jìn)而造成瓦片在單個時鐘周期內(nèi)被訪問的概率增加。由于R 位僅能表示某個周期內(nèi)瓦片是否被訪問,無法表示瓦片被訪問頻次,T增大會使各瓦片在V(age)上的差異減小,因此緩存命中率減小。當(dāng)T>45 s 時,V(age)不再是主要影響因子,因此,緩存命中率不隨T的變化而變化。
由圖4(b)可知,SSAT 的緩存命中率隨vol 的增大呈現(xiàn)先增大后減小的特征,其主要原因是,瓦片訪問會使目標(biāo)瓦片空間訪問熱度增加,當(dāng)vol<0.3 時,瓦片訪問命中對周圍瓦片的影響較小,V(heat)不會對V(age)產(chǎn)生有效的移位影響,因此緩存命中率較低且變化不明顯;隨著vol 的增大,瓦片訪問命中對周圍瓦片的影響增大,V(heat)對V(age)產(chǎn)生有效的移位影響,因此緩存命中率不斷增大;當(dāng)vol>1時,訪問命中使周圍瓦片獲得的熱度大于被命中瓦片自身獲得的熱度,V(heat)對V(age)產(chǎn)生的移位影響過大,因此緩存命中率不斷減小。
圖4 瓦片時鐘周期和瓦片空間訪問熱度權(quán)重值對SSAT 緩存命中率的影響Fig.4 Impact of T and vol on cache hit ratio of SSAT
綜合實(shí)驗(yàn)結(jié)果,當(dāng)T=10 s,vol=1 時,請求命中率和字節(jié)命中率最高,因此,選擇該組合值作為SSAT 算法的實(shí)驗(yàn)參數(shù)。
圖5 展示了在同時設(shè)置V(heat)和V(size)、僅設(shè)置V(heat)、僅設(shè)置V(size)3 個條件下,SSAT 的請求命中率和字節(jié)命中率隨緩存空間的變化??芍S著緩存空間的增大,SSAT 在3 種條件下的請求命中率和字節(jié)命中率均不斷增大,且增長趨勢大致相同。在不同的緩存空間中,同時設(shè)置V(heat)和V(size)的SSAT 所得請求命中率和字節(jié)命中率最大;僅設(shè)置V(heat)的SSAT 所得請求命中率和字節(jié)命中率下降約22%;僅設(shè)置V(size)的SSAT所得請求命中率和字節(jié)命中率下降約43%。結(jié)果表明,瓦片空間訪問熱度價值和瓦片大小價值能有效提高SSAT 的緩存命中率。
圖5 在3 種條件下SSAT 的請求命中率和字節(jié)命中率隨緩存空間的變化Fig.5 Changes of request hit ratio and byte hit ratio of SAAT with cache space under three conditions
圖6(a)和(b)分別為SSAT、LRU、LFU、先進(jìn)先出(first in first out,F(xiàn)IFO)4 種算法的請求命中率和字節(jié)命中率隨緩存空間的變化??芍?,當(dāng)緩存空間為100 MB 時,4 種算法均表現(xiàn)出小于7%的請求命中率和小于10% 的字節(jié)命中率。當(dāng)緩存空間為500 MB 時,4 種算法的緩存命中率顯著提高,其中請求命中率分別為73%,65%,55%和44%,字節(jié)命中率分別為76%,66%,56%和47%。圖6(c)和(d)分別為4 種算法在不同緩存空間下的請求命中增長率和字節(jié)命中增長率。當(dāng)緩存空間小于100 MB時,4 種算法的請求命中增長率和字節(jié)命中增長率均較低,其中SSAT 每MB 的請求命中增長率和字節(jié)命中增長率分別為0.06%和0.07%。在緩存空間為100~300 MB 時,4 種算法每MB 的請求命中率和字節(jié)命中率迅速增加,命中增長率均大于0.15%,其中SSAT 的請求命中增長率和字節(jié)命中增長率每MB 分別達(dá)0.24%和0.23%。當(dāng)緩存空間為300~500 MB 時,緩存空間對命中增長率的影響降低,因此4 種算法每MB 的命中增長率再次趨于平緩,平均降至0.05% 左右。總的來說,在不同緩存空間下,SSAT 的緩存命中率及命中增長率均最高,且隨緩存空間的增大緩存命中率優(yōu)勢更加顯著。
圖6 4 種算法的緩存命中率及命中增長率隨緩存空間的變化Fig.6 Changes of tile request hit ratio,tile byte hit ratio and their growth of four algorithms with cache space
瓦片平均訪問時長和平均訪問時長節(jié)省率可以直觀地體現(xiàn)瓦片服務(wù)的性能。平均訪問時長越短,平均訪問時長節(jié)省率越高,則訪問延遲率越低。圖7 為4 種算法在不同緩存空間下的瓦片平均訪問時長及其節(jié)省率,可知,4 種算法的平均訪問時長隨緩存空間的增大而減小,平均訪問時長節(jié)省率隨緩存空間的增大而增大。當(dāng)緩存空間大于300 MB 時,緩存置換算法可有效縮短瓦片請求的平均訪問時長,降低延遲率,且SSAT 的延遲率最低。
圖7 4 種算法的平均訪問時長和平均訪問時長節(jié)省率隨緩存空間的變化Fig.7 Change of average visit time and save ratio of average visit time of four algorithms with cache space
瓦片緩存置換算法為NGIS 帶來了更高效的瓦片服務(wù),但同時也會提高CPU 占用率。圖8 展示了當(dāng)緩存空間為500 MB 時4 種算法的CPU 占用率及累計占用率的統(tǒng)計結(jié)果??芍?,4 種算法的CPU 占用率從大到小依次為LRU,SSAT,LFU 和FIFO。LRU 有良好的緩存命中率,但資源消耗過大;FIFO占用的CPU 資源最小,但緩存命中率過低;LFU 和SSAT 的資源消耗適中,但LFU 的緩存命中率遠(yuǎn)低于SSAT;SSAT 能兼顧性能和資源消耗,是一種良好的服務(wù)端瓦片緩存置換算法。
圖8 4 種算法的CPU 占用率和累計占用率Fig.8 CPU usage ratio and sum usage ratio of four algorithms
綜合分析了瓦片訪問的時空局部性、長短期流行度和瓦片大小特征,將老化算法引入NGIS,提出了基于時空老化模型的服務(wù)端瓦片緩存置換算法(SSAT),并進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明,相較于傳統(tǒng)算法,SSAT 能顯著提高瓦片請求命中率和字節(jié)命中率,縮短平均訪問時長,且能兼顧對計算機(jī)資源的消耗,是一種較有效的瓦片緩存置換算法。
SSAT 仍有待優(yōu)化。首先,本實(shí)驗(yàn)是在單機(jī)上進(jìn)行的,如何將SSAT 擴(kuò)展為分布式緩存置換算法,令其在多節(jié)點(diǎn)、多副本的場景下保持良好性能,進(jìn)一步提高遙感影像的共享能力是未來重點(diǎn)關(guān)注的研究方向。此外,除瓦片大小特征外,瓦片數(shù)據(jù)特征還包括瓦片類型特征和瓦片格式特征等多種信息,未來將從多個維度分析瓦片數(shù)據(jù)特征對緩存命中率的影響,為高性能地理信息服務(wù)提供更全面的理論支撐。