使用MSS維護(hù)語(yǔ)義緩存一致性的方法*

梁茹冰劉瓊

(1.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006;2.華南農(nóng)業(yè)大學(xué)理學(xué)院，廣東廣州510642)

移動(dòng)計(jì)算使計(jì)算機(jī)和其它移動(dòng)信息智能終端設(shè)備可以在無(wú)線(xiàn)網(wǎng)絡(luò)環(huán)境下實(shí)現(xiàn)數(shù)據(jù)傳輸及資源共享，并且這種傳輸與共享可以發(fā)生在任何時(shí)間、任何位置以及任何移動(dòng)終端之間.移動(dòng)計(jì)算是當(dāng)前計(jì)算技術(shù)研究中的熱點(diǎn)之一，對(duì)移動(dòng)計(jì)算的研究是游牧計(jì)算和普適計(jì)算發(fā)展的技術(shù)支撐和重要階段.然而，移動(dòng)計(jì)算本身的特點(diǎn)讓相關(guān)研究工作充滿(mǎn)了挑戰(zhàn)，如無(wú)線(xiàn)網(wǎng)絡(luò)帶寬和電池等資源的有限性、客戶(hù)端及其設(shè)備的頻繁移動(dòng)性和頻繁斷接性等.在數(shù)據(jù)通信方面，采用“廣播”和“緩存”技術(shù)是解決這些難題的有效方法.

文獻(xiàn)［1］中提出，語(yǔ)義緩存的基本結(jié)構(gòu)由查詢(xún)語(yǔ)義描述和查詢(xún)結(jié)果兩部分組成，并研究了對(duì)單個(gè)關(guān)系表的查詢(xún)處理.與傳統(tǒng)的頁(yè)緩存和元組緩存不同，語(yǔ)義緩存能夠支持對(duì)關(guān)系型數(shù)據(jù)庫(kù)的查詢(xún)，而頁(yè)緩存與元組緩存對(duì)此支持不夠，只適用于面向?qū)ο蟮臄?shù)據(jù)庫(kù)管理系統(tǒng).文獻(xiàn)［2］中對(duì)移動(dòng)計(jì)算環(huán)境中的用戶(hù)位置、速度、狀態(tài)，以及位置比較、位置綁定、位置相關(guān)查詢(xún)、語(yǔ)義片段進(jìn)行了形式化定義，并研究了語(yǔ)義查詢(xún)的處理過(guò)程，提出了查詢(xún)裁剪的思想.文獻(xiàn)［3］中除了進(jìn)一步利用關(guān)系代數(shù)形式化相關(guān)表達(dá)外，還提出了判斷當(dāng)前查詢(xún)能否被語(yǔ)義緩存滿(mǎn)足的3個(gè)判定定理;在語(yǔ)義緩存查詢(xún)裁剪方面，針對(duì)5種相交情況給出了具體的實(shí)現(xiàn)算法.文獻(xiàn)［4-5］中對(duì)查詢(xún)?nèi)绾螐木彺鎸?dǎo)出、查詢(xún)與緩存的匹配兩方面進(jìn)行了深入的研究，給出了相應(yīng)的定義、判定定理及算法，并提出了一個(gè)語(yǔ)義緩存查詢(xún)模型.文獻(xiàn)［6］中以海量數(shù)據(jù)庫(kù)應(yīng)用為背景，將語(yǔ)義緩存技術(shù)拓展到海量數(shù)據(jù)庫(kù)的聚集查詢(xún)，研究了面向聚集查詢(xún)的語(yǔ)義緩存形式模型，構(gòu)造了海量數(shù)據(jù)庫(kù)的語(yǔ)義緩存系統(tǒng)并研究了查詢(xún)處理、緩存管理和一致性維護(hù)等關(guān)鍵技術(shù).文獻(xiàn)［7］中通過(guò)分析語(yǔ)義緩存段與更新語(yǔ)句的條件謂詞及投影屬性的關(guān)系，將更新粒度裁剪至被更新的屬性，有效地減少了數(shù)據(jù)通信開(kāi)銷(xiāo).

綜上所述，這些研究成果為進(jìn)一步研究語(yǔ)義緩存的一致性維護(hù)策略提供了理論基礎(chǔ).但它們都基于傳統(tǒng)的服務(wù)方與客戶(hù)方的兩層結(jié)構(gòu)，不利于緩存統(tǒng)一管理，一致性維護(hù)開(kāi)銷(xiāo)較大，并且沒(méi)有涉及失效報(bào)告數(shù)據(jù)結(jié)構(gòu)方面的研究.為此，文中提出了一種利用移動(dòng)支持站點(diǎn)(MSS)進(jìn)行緩存一致性維護(hù)的方法，并給出了中間層的失效報(bào)告結(jié)構(gòu)形式.

1 語(yǔ)義緩存一致性維護(hù)方法

1.1 相關(guān)定義

定義2客戶(hù)方緩存由多個(gè)兩兩互不相交的語(yǔ)義緩存項(xiàng)及其對(duì)應(yīng)的緩存塊數(shù)據(jù)構(gòu)成.

定義3對(duì)于任意Select-From-Where查詢(xún)語(yǔ)句，如果是單表查詢(xún)，Where子句是邏輯And連接的屬性與常量組成的比較表達(dá)式，且無(wú)嵌套查詢(xún)，則稱(chēng)這樣的查詢(xún)?yōu)榭删彺娌樵?xún)，表示為QC〉.其中:為查詢(xún)的投影屬性集為查詢(xún)條件謂詞，表示成合取式;QC為關(guān)系代數(shù)表示形式的查詢(xún)結(jié)果

定義4 MSS中語(yǔ)義緩存項(xiàng)為〈SCID，SR，SA，SP，SVS〉.其中:SCID為緩存項(xiàng)索引號(hào);SR為關(guān)系表;SA為投影屬性集;SP為查詢(xún)條件合取式;SVS為緩存項(xiàng)是否發(fā)生更新標(biāo)志位，SVS=0表示無(wú)更新，SVS=1表示有更新.

定義5 MSS中索引表項(xiàng)為〈HID，State，SC〉.其中:HID為移動(dòng)客戶(hù)方索引號(hào);State為該移動(dòng)終端的當(dāng)前狀態(tài)，State=0表示在線(xiàn)，State=1表示離線(xiàn)(即設(shè)備關(guān)機(jī)或已經(jīng)移動(dòng)到另一分區(qū));SC為指向MSS中保存該客戶(hù)方緩存項(xiàng)的指針.

例1“UpdateR1Set AT1=20 Where AT2＞30”表示成Update更新元組形式為U=〈R1，{AT1}，AT1=20，{AT2}，AT2＞30，UC〉.

定義7服務(wù)方數(shù)據(jù)的Delete更新可表示為D=〈DR，DP，DC〉.其中:DR∈D;DP為刪除更新條件謂詞，表示成合取式;DC為刪除元組集合.

定義8服務(wù)方數(shù)據(jù)的Insert更新可表示為I=〈IR，IC〉，其中IR∈D，IC為插入元組集合.

1.2 結(jié)構(gòu)

典型的移動(dòng)計(jì)算系統(tǒng)結(jié)構(gòu)如圖1所示，從服務(wù)器到移動(dòng)支持站點(diǎn)段是有線(xiàn)網(wǎng)絡(luò)連接，從MSS到移動(dòng)終端(MH)是無(wú)線(xiàn)網(wǎng)絡(luò)連接.傳統(tǒng)的兩層緩存結(jié)構(gòu)將緩存數(shù)據(jù)存放在客戶(hù)方，MSS只是廣播失效數(shù)據(jù)，由于無(wú)線(xiàn)網(wǎng)絡(luò)固有的局限性，各移動(dòng)客戶(hù)方的緩存信息只能保證弱一致性，且維護(hù)開(kāi)銷(xiāo)大.顯然，數(shù)據(jù)驗(yàn)證、查詢(xún)請(qǐng)求等操作都要通過(guò)MSS來(lái)完成.因此，這里的MSS有兩重角色:對(duì)于客戶(hù)端來(lái)說(shuō)，它是一個(gè)小服務(wù)器，其中的數(shù)據(jù)實(shí)時(shí)、準(zhǔn)確、個(gè)性化;對(duì)于服務(wù)器來(lái)說(shuō)，它是一個(gè)固定的、有一定處理能力的客戶(hù)端(胖客戶(hù)端)，穩(wěn)定、高效，能夠減輕服務(wù)器的負(fù)擔(dān)，防止瓶頸.因此，文中利用MSS來(lái)擴(kuò)展傳統(tǒng)的兩層緩存結(jié)構(gòu).

圖1 典型的移動(dòng)計(jì)算系統(tǒng)結(jié)構(gòu)Fig.1 Architecture of typicalmobile computing system

客戶(hù)方語(yǔ)義緩存存儲(chǔ)了以往的查詢(xún)描述及結(jié)果，MSS中通過(guò)存儲(chǔ)緩存描述為客戶(hù)方保存緩存?zhèn)浞?CB)，這樣MSS中就有多個(gè)移動(dòng)終端的緩存內(nèi)容描述，如圖2所示.雖然較以前的設(shè)計(jì)而言，文中方案所需存儲(chǔ)空間增大了，但是當(dāng)前磁盤(pán)的價(jià)格不斷下降，磁盤(pán)容量不斷提高，多數(shù)情況下系統(tǒng)都有足夠的空間用于熱點(diǎn)對(duì)象的緩存.

圖2 擴(kuò)展型語(yǔ)義緩存結(jié)構(gòu)Fig.2 Architecture of semantic cache with extended structure

例2 MSS1所管理的分區(qū)C1中有客戶(hù)方MH1和MH2，則MH1和MH2的語(yǔ)義緩存，以及MSS1為MH1和MH2分別保存的緩存描述如圖3所示.相關(guān)數(shù)據(jù)結(jié)構(gòu)說(shuō)明參見(jiàn)定義1、4和5.通過(guò)這種數(shù)據(jù)存儲(chǔ)方式，MSS中不僅可以保存客戶(hù)方訪(fǎng)問(wèn)服務(wù)器數(shù)據(jù)的“痕跡”，以MSS中相應(yīng)的語(yǔ)義緩存項(xiàng)體現(xiàn)，還可以進(jìn)一步看出當(dāng)前客戶(hù)方狀態(tài)是在線(xiàn)還是離線(xiàn)或者移動(dòng)到另一分區(qū).廣播的失效報(bào)告中只包含當(dāng)前在線(xiàn)的客戶(hù)方緩存變化情況.

圖3 MSS和客戶(hù)方的緩存組織Fig.3 Cache organizations of MSS and client

1.3 MSS中的緩存一致性及失效報(bào)告格式

在一致性維護(hù)方面，由于MSS與高速骨干網(wǎng)絡(luò)是有線(xiàn)連接，因此其緩存一致性維護(hù)較移動(dòng)終端的緩存一致性維護(hù)容易，并且能夠做到低代價(jià)、強(qiáng)一致性，保證數(shù)據(jù)實(shí)時(shí)、有效.另一方面，由于MSS中有多個(gè)客戶(hù)方的緩存項(xiàng)備份，當(dāng)有共同目標(biāo)時(shí)，緩存還可以在一定程度上共享、合并，從而可以最大程度地滿(mǎn)足客戶(hù)方的查詢(xún)請(qǐng)求，減少與服務(wù)器的交互次數(shù)，節(jié)省帶寬資源，加快查詢(xún)響應(yīng)時(shí)間.

強(qiáng)一致性要求在任意時(shí)刻MSS中的緩存項(xiàng)數(shù)據(jù)與服務(wù)器上的數(shù)據(jù)保持一致.由于可用性與訪(fǎng)問(wèn)性能的問(wèn)題，強(qiáng)一致性在移動(dòng)計(jì)算環(huán)境中不能直接在移動(dòng)節(jié)點(diǎn)上實(shí)現(xiàn).然而，MSS與服務(wù)器是始終保持連接狀態(tài)的，服務(wù)器的數(shù)據(jù)變更可以及時(shí)發(fā)送給MSS，通過(guò)更改相應(yīng)緩存項(xiàng)的SVS位標(biāo)記來(lái)表示有無(wú)插入、刪除、更新等操作，因此，MSS中的各語(yǔ)義緩存項(xiàng)在狀態(tài)上可以與服務(wù)方保持強(qiáng)一致性.

由于無(wú)線(xiàn)網(wǎng)絡(luò)非對(duì)稱(chēng)性的特點(diǎn)，從服務(wù)方到客戶(hù)方的下行通信帶寬一般遠(yuǎn)大于上行通信帶寬，而且從服務(wù)方接收數(shù)據(jù)的開(kāi)銷(xiāo)也遠(yuǎn)小于發(fā)送開(kāi)銷(xiāo).數(shù)據(jù)廣播技術(shù)就是利用了這一特點(diǎn)，將數(shù)據(jù)庫(kù)中的熱點(diǎn)數(shù)據(jù)組織起來(lái)，通過(guò)專(zhuān)門(mén)的廣播信道，經(jīng)由MSS向客戶(hù)方廣播.進(jìn)一步地，在擴(kuò)展的3層緩存結(jié)構(gòu)下，MSS中存儲(chǔ)的語(yǔ)義緩存項(xiàng)的有效狀態(tài)與服務(wù)方一致.MSS可以采取同步或異步的方式向其客戶(hù)方廣播緩存失效報(bào)告，報(bào)告的組織可以采用位序列法，并且在報(bào)告中只包含符合State=0(見(jiàn)定義5)條件的客戶(hù)方緩存項(xiàng)更新?tīng)顟B(tài)值，進(jìn)一步縮減了失效報(bào)告長(zhǎng)度.

例3 MSS1廣播的失效報(bào)告格式“MH1:101 MH2:01……”，表示客戶(hù)方MH1的第一個(gè)緩存項(xiàng)和第三個(gè)緩存項(xiàng)發(fā)生了更新操作，第二個(gè)緩存項(xiàng)沒(méi)有更新;客戶(hù)方MH2的第一個(gè)緩存項(xiàng)沒(méi)有更新，第二個(gè)緩存項(xiàng)發(fā)生了更新;依此類(lèi)推.MH1和MH2通過(guò)收聽(tīng)廣播信道上的失效報(bào)告了解自己的緩存有效情況，客戶(hù)方甚至可以斷開(kāi)網(wǎng)絡(luò)一段時(shí)間(理論上是任意長(zhǎng)時(shí)間)，當(dāng)再次連接時(shí)，只需向MSS驗(yàn)證自己的緩存即可，而無(wú)需像傳統(tǒng)算法那樣將自己的緩存全部設(shè)置為無(wú)效或刪除.

1.4 更新粒度細(xì)化

失效報(bào)告中的0或1代表整個(gè)語(yǔ)義緩存項(xiàng)的有效狀態(tài)，假設(shè)某緩存塊中只有極少元組發(fā)生變化，也會(huì)將該緩存項(xiàng)更新?tīng)顟B(tài)位置為1，不能精確到元組級(jí)，從而導(dǎo)致用戶(hù)在維護(hù)緩存時(shí)存在通信數(shù)據(jù)量大的問(wèn)題.因此，文中對(duì)更新粒度如何細(xì)化進(jìn)行了研究.

客戶(hù)方進(jìn)行一致性維護(hù)時(shí)，傳統(tǒng)的處理方法是:如果緩存項(xiàng)失效，則將該緩存塊數(shù)據(jù)設(shè)置為無(wú)效或直接刪除，或重新提交原查詢(xún)，又或采取更新事務(wù)回滾的辦法，即在緩存塊數(shù)據(jù)中執(zhí)行引起更新的Insert、Delete和Update操作(傳統(tǒng)方法存儲(chǔ)的是關(guān)系表的全屬性，而不是投影屬性).由于這些方法都直接由客戶(hù)方來(lái)完成，網(wǎng)絡(luò)通信量大，計(jì)算開(kāi)銷(xiāo)和能量消耗也很大.文獻(xiàn)［8］中統(tǒng)計(jì)數(shù)據(jù)表明，客戶(hù)方維護(hù)緩存一致性所付出的代價(jià)占總能量消耗的30%左右，緩存減少了網(wǎng)絡(luò)通信中的數(shù)據(jù)量，但如果減少的上行和下行能量消耗不足以彌補(bǔ)一致性維護(hù)的開(kāi)銷(xiāo)，緩存的存在就沒(méi)有意義.因此，文中試圖將客戶(hù)方從這項(xiàng)艱巨的任務(wù)中解放出來(lái)，讓MSS代替客戶(hù)方進(jìn)行緩存一致性維護(hù)，并通過(guò)廣播機(jī)制發(fā)布失效報(bào)告，采用位序列方法壓縮報(bào)告大小，在傳統(tǒng)廣播方法基礎(chǔ)上進(jìn)一步減少通信量.

首先，要判斷Update、Insert和Delete更新操作與哪些緩存項(xiàng)匹配，如果某緩存項(xiàng)與更新匹配了，那么該緩存項(xiàng)就被更新，SVS=1.為了便于記錄更新，文中讓MSS中的各緩存項(xiàng)都有一個(gè)更新隊(duì)列，當(dāng)緩存項(xiàng)中數(shù)據(jù)更新時(shí)，更新操作序列就被插入到隊(duì)列中;客戶(hù)方通過(guò)讀取更新隊(duì)列中的操作序列(出隊(duì)列)，并按插入順序依次在其緩存塊數(shù)據(jù)中執(zhí)行更新操作，就可以方便地將緩存更新至最新?tīng)顟B(tài).下面詳細(xì)描述如何將一個(gè)更新細(xì)化，并插入更新隊(duì)列.

(1)插入更新方式Insert

如果服務(wù)器數(shù)據(jù)發(fā)生了Insert更新〈IR，IC〉，則MSS收到該更新信息后，將〈IR，IC〉與各緩存項(xiàng)〈SR，SA，SP，SC〉進(jìn)行匹配判斷:

(2)刪除更新方式Delete

如果服務(wù)器數(shù)據(jù)發(fā)生了Delete更新〈DR，DP，DC〉，則MSS收到該更新信息后，將〈DR，DP，DC〉與各緩存項(xiàng)〈SR，SA，SP，SC〉進(jìn)行匹配判斷:

(3)更新方式Update(方法1)

如果服務(wù)器數(shù)據(jù)發(fā)生了Update更新〈UR，UP1A，UP1，UP2A，UP2，UC〉，則MSS收到該更新信息后，將〈UR，UP1A，UP1，UP2A，UP2，UC〉與各緩存項(xiàng)〈SR，SA，SP，SC〉進(jìn)行匹配判斷:

如果UP1A∧SPA≠?且UP1?SP滿(mǎn)足，則說(shuō)明執(zhí)行Update更新后，有新的數(shù)據(jù)符合條件SP待插入緩存，需要構(gòu)造補(bǔ)充查詢(xún)Q=〈SR，SA，UP1，S'C〉，查詢(xún)結(jié)果S'C與原緩存合并可達(dá)到更新的目的.因此，SVS=1，補(bǔ)充查詢(xún)操作〈SR，SA，UP1，S'C〉添加到該緩存項(xiàng)的更新隊(duì)列中.

如果UP1A∧SPA≠?且UP1?SP不滿(mǎn)足，則說(shuō)明執(zhí)行Update更新后，緩存中有不符合條件SP待刪除的元組，需要執(zhí)行刪除更新〈DR=SR，DP=UP2，DC〉來(lái)達(dá)到一致性目的.因此，SVS=1，刪除操作〈SR，UP2，DC〉添加到該緩存項(xiàng)的更新隊(duì)列中.

若UP2∧SP=?且(UP1∧SP)?SP滿(mǎn)足，說(shuō)明執(zhí)行Update更新后，有新的數(shù)據(jù)符合條件SP待插入緩存，需要構(gòu)造補(bǔ)充查詢(xún)Q=〈SR，SA，UP1∧SP，S'C〉，查詢(xún)結(jié)果與原緩存合并可達(dá)到更新目的.因此，SVS=1，補(bǔ)充查詢(xún)操作Q=〈SR，SA，UP1∧SP，S'C〉添加到該緩存項(xiàng)的更新隊(duì)列中.

若UP2∧SP≠?，則考慮下面兩種情況.

若(UP1∧SP)?SP滿(mǎn)足，則說(shuō)明執(zhí)行Update更新后，有新的數(shù)據(jù)符合條件SP待插入緩存，需要構(gòu)造補(bǔ)充查詢(xún)Q=〈SR，SA，UP1∧SP，S'C〉，查詢(xún)結(jié)果與原緩存合并可達(dá)到更新的目的.因此，SVS=1，Update更新操作〈UR，UP1A∧SA，UP1∧SP，UP2A，UP2，UC〉和補(bǔ)充查詢(xún)操作Q=〈SR，SA，UP1∧SP，S'C〉依次添加到該緩存項(xiàng)的更新隊(duì)列中.

若UP2?SP滿(mǎn)足且UP1∧SP=?，則說(shuō)明執(zhí)行Update更新后，緩存中有不符合條件SP待刪除的元組，需要執(zhí)行刪除更新〈DR=SR，DP=UP2，DC〉來(lái)達(dá)到一致性目的.因此，SVS=1，Update更新操作〈UR，UP1A∧SA，UP1，UP2A，UP2，UC〉和刪除更新操作〈SR，DP=UP2，DC〉依次添加到該緩存項(xiàng)的更新隊(duì)列中.

(4)更新方式Update(方法2)

如果Update更新所影響的元組很少(如小于3個(gè))而不是整片更新，則可以考慮將Update更新拆分為一個(gè)Delete更新、一個(gè)補(bǔ)充查詢(xún)和一個(gè)Insert更新.對(duì)于Update更新〈UR，UP1A，UP1，UP2A，UP2，UC〉，如果某緩存項(xiàng)受其影響，則先執(zhí)行刪除更新操作〈DR=UR，DP=UP2，DC〉，再執(zhí)行補(bǔ)充查詢(xún)〈UR，SA，UP2，QC〉，最后將查詢(xún)結(jié)果插入該緩存塊中.

2 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證所提出的模型及方法的性能，文中設(shè)計(jì)了兩組仿真實(shí)驗(yàn).編程基于J2SE平臺(tái)，運(yùn)行環(huán)境是AMD 2500+1.40GHz處理器，內(nèi)存為512MB，操作系統(tǒng)為Windows XPProfessional.仿真實(shí)驗(yàn)參數(shù)如表1所示.

表1 仿真實(shí)驗(yàn)參數(shù)Table 1 Simulation parameters

實(shí)驗(yàn)1服務(wù)方按UpdateInterval隨機(jī)生成更新操作，更新每隔Broad Interval廣播給客戶(hù)方.模擬了20min內(nèi)的更新及廣播失效報(bào)告情況，并在不同緩存大小(2～10 kB)情況下，比較了PCID方法［9］、文中基于位序列的報(bào)告數(shù)據(jù)組織方法與傳統(tǒng)基于數(shù)據(jù)對(duì)象和時(shí)間戳的方法的失效報(bào)告長(zhǎng)度，運(yùn)行1000次后的平均實(shí)驗(yàn)結(jié)果如圖4所示.

在相同大小的客戶(hù)端緩存(4096B)下，服務(wù)方數(shù)據(jù)以一定時(shí)間間隔被更新，更新報(bào)告以無(wú)狀態(tài)同步的方式發(fā)送到客戶(hù)方.隨著仿真時(shí)間的延長(zhǎng)，由MSS廣播的失效報(bào)告累積字節(jié)數(shù)也在增加，如圖4(a)所示.文中方法的失效報(bào)告長(zhǎng)度比傳統(tǒng)方法和PCID方法均短，這是因?yàn)閭鹘y(tǒng)方法基于數(shù)據(jù)對(duì)象和時(shí)間戳來(lái)形成失效報(bào)告，PCID方法雖然基于位序列［10］，但要求包含時(shí)間戳.文中方法采用位序列方法組織失效報(bào)告，對(duì)離線(xiàn)或剛遷移到另一分區(qū)的客戶(hù)方緩存項(xiàng)進(jìn)行更新時(shí)不需要廣播，且無(wú)需包含時(shí)間戳，因此空間復(fù)雜度更低.

在相同的傳真時(shí)間(10min)下，客戶(hù)方緩存從2 kB遞增到10 kB，3種方法的失效報(bào)告長(zhǎng)度如圖4(b)所示.從圖4(b)可知:傳統(tǒng)方法中失效報(bào)告長(zhǎng)度的增加與服務(wù)方數(shù)據(jù)更新頻率和模擬時(shí)間成正比，而與實(shí)際緩存項(xiàng)數(shù)目無(wú)關(guān);文中方法和PCID方法的報(bào)告長(zhǎng)度隨著實(shí)際緩存項(xiàng)數(shù)目增加而稍有增加，但仍遠(yuǎn)遠(yuǎn)小于傳統(tǒng)方法中的報(bào)告長(zhǎng)度;由于傳統(tǒng)方法存儲(chǔ)全屬性，對(duì)于相同的緩存空間，文中方法可以存儲(chǔ)更多的語(yǔ)義緩存項(xiàng)，從而提高了緩存命中率.也就是說(shuō)，在緩存空間明顯增加，緩存項(xiàng)數(shù)目也相應(yīng)增加的情況下，文中方法的失效報(bào)告長(zhǎng)度仍然遠(yuǎn)遠(yuǎn)小于傳統(tǒng)方法，有利于節(jié)省無(wú)線(xiàn)部分的帶寬資源.

圖4 在不同緩存空間情況下3種方法的失效報(bào)告長(zhǎng)度比較Fig.4 Comparison of invalidation report size among three algorithms with different cache spaces

實(shí)驗(yàn)2仿真了緩存一致性維護(hù)過(guò)程，比較了文中提出的基于更新隊(duì)列與粒度細(xì)化一致性維護(hù)方法、傳統(tǒng)方法和兩層結(jié)構(gòu)粒度細(xì)化方法(簡(jiǎn)稱(chēng)兩層方法)［7］在網(wǎng)絡(luò)通信量方面的性能，運(yùn)行1000次后的平均實(shí)驗(yàn)結(jié)果如圖5、6所示.

實(shí)驗(yàn)數(shù)據(jù)表明，與傳統(tǒng)方法和兩層方法相比，文中方法可以存儲(chǔ)更多的緩存項(xiàng)，因?yàn)閭鹘y(tǒng)方法需存儲(chǔ)全屬性，兩層方法要預(yù)留空間存儲(chǔ)更新語(yǔ)句，因此，文中方法的緩存命中率更高.也就是說(shuō)，由于命中率較高，在相同的仿真時(shí)間內(nèi)，文中方法較其它兩種方法要做更多的緩存一致性維護(hù)工作，有更多待更新的元組數(shù)，如圖5所示.

圖5 3種方法的更新元組數(shù)比較Fig.5 Comparison of numbers of updated tuples among three algorithms

圖6 3種方法的網(wǎng)絡(luò)通信量比較Fig.6 Comparison of data communication traffic among three methods

最后，依次對(duì)緩存中50、100、150和200個(gè)待更新元組進(jìn)行一致性維護(hù)，分別比較3種方法所產(chǎn)生的網(wǎng)絡(luò)通信量，結(jié)果如圖6所示.由圖6中可知，文中方法和兩層方法較傳統(tǒng)方法有更低的網(wǎng)絡(luò)通信量，且增長(zhǎng)幅度也較小.這是因?yàn)閭鹘y(tǒng)方法執(zhí)行Update更新操作時(shí)，先在緩存中執(zhí)行Delete操作，再執(zhí)行Select操作以獲取更新后的元組，然后將它們插入到緩存中.因此在更新過(guò)程中，有時(shí)只需要修改個(gè)別屬性值，卻變成了對(duì)整個(gè)元組的操作，從而增加了通信量.應(yīng)用文中方法時(shí)，網(wǎng)絡(luò)通信量隨著更新元組數(shù)的增加而增加，但由于采取了粒度細(xì)化策略和更新隊(duì)列機(jī)制，只有當(dāng)產(chǎn)生補(bǔ)充查詢(xún)時(shí)才會(huì)明顯增加網(wǎng)絡(luò)通信量(實(shí)驗(yàn)中補(bǔ)充查詢(xún)值設(shè)為0.2).如果無(wú)補(bǔ)充查詢(xún)或者補(bǔ)充查詢(xún)幾率很小，則更新元組數(shù)的增加不會(huì)帶來(lái)通信量的明顯增加.

當(dāng)客戶(hù)方始終與網(wǎng)絡(luò)保持連接時(shí)，可以持續(xù)接收失效報(bào)告進(jìn)行緩存一致性維護(hù).此時(shí)，文中方法與兩層方法在網(wǎng)絡(luò)通信量開(kāi)銷(xiāo)上很接近，如圖6所示.但是，當(dāng)發(fā)生斷接操作時(shí)，傳統(tǒng)方法與兩層方法在斷接時(shí)間小于廣播時(shí)間間隔情況下，緩存恢復(fù)較易;一旦斷接時(shí)間大于廣播時(shí)間間隔，再次連接就無(wú)法根據(jù)當(dāng)前失效報(bào)告來(lái)判斷緩存的有效性，文獻(xiàn)［7］中的兩層方法沒(méi)有對(duì)此進(jìn)行研究.由于文中方法在MSS中設(shè)置更新隊(duì)列，因此即使客戶(hù)方離線(xiàn)(理論上可以斷開(kāi)任意長(zhǎng)時(shí)間)，其緩存更新序列始終有相應(yīng)的MSS為其保存在更新隊(duì)列中，當(dāng)客戶(hù)方再次連接時(shí)，只需執(zhí)行出隊(duì)列操作，并依次執(zhí)行隊(duì)列中的更新操作即可將其緩存恢復(fù)有效.

3 結(jié)語(yǔ)

緩存和數(shù)據(jù)廣播技術(shù)是移動(dòng)計(jì)算中有效利用帶寬資源和節(jié)省能量的重要方法.針對(duì)傳統(tǒng)語(yǔ)義緩存方法沒(méi)有有效利用移動(dòng)支持站點(diǎn)以及一致性維護(hù)通信開(kāi)銷(xiāo)大的問(wèn)題，文中提出利用移動(dòng)支持站點(diǎn)進(jìn)行數(shù)據(jù)廣播的方法，基于客戶(hù)方訪(fǎng)問(wèn)服務(wù)器的數(shù)據(jù)“痕跡”和當(dāng)前活動(dòng)狀態(tài)信息，采用位序列法組織失效報(bào)告，從而有效地減少了廣播失效報(bào)告長(zhǎng)度.在一致性維護(hù)方面，歸納整理了粒度細(xì)化和屬性裁剪的邏輯方法，提出將原更新操作轉(zhuǎn)化為等價(jià)更新序列并插入更新隊(duì)列中的思想，從而簡(jiǎn)化了客戶(hù)方的緩存維護(hù)過(guò)程，減少了網(wǎng)絡(luò)通信量，并能夠適應(yīng)客戶(hù)方頻繁斷接情況下的一致性維護(hù).仿真實(shí)驗(yàn)結(jié)果表明，文中方法是有效的，在縮減失效報(bào)告長(zhǎng)度和網(wǎng)絡(luò)通信量方面都較傳統(tǒng)方法等有明顯的改善.

［1］Dar S，F(xiàn)ranklin M，Jonsson B，etal.Semantic data caching and replacement［C］∥Proceedings of the 22nd VLDB Conference.Mumbai:Morgan Kaufmann Pub Inc，1996:330-341.

［2］Ren Qun，Dunham M H.Using semantic caching to manage location dependent data inmobile computing［C］∥Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.New York:ACM，2000:210-221.

［3］Ren Qun，Dunham M H，Kumar V.Semantic caching and query processing［J］.IEEE Transactions on Knowledge and Data Engineering，2003，15(1):192-210.

［4］吳婷婷，周興銘.基于語(yǔ)義緩存的移動(dòng)查詢(xún)導(dǎo)出［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25(10):1104-1110.Wu Ting-ting，Zhou Xing-ming.Extracting query results from semantic cache［J］.Chinese Journal of Computers，2002，25(10):1104-1110.

［5］吳婷婷，蘇武運(yùn)，周興銘，等.移動(dòng)查詢(xún)緩存處理的研究［J］.計(jì)算機(jī)研究與發(fā)展，2004，41(1):187-193.Wu Ting-ting，Su Wu-yun，Zhou Xing-ming，et al.Mobile query through semantic cache［J］.Journal of Computer Research and Development，2004，41(1):187-193.

［6］蔡建宇，吳泉源，賈焰，等.面向聚集查詢(xún)的語(yǔ)義緩存技術(shù)［J］.軟件學(xué)報(bào)，2007，18(2):361-371.Cai Jian-yu，Wu Quan-yuan，Jia Yan，et al.Semantic cache technology for aggregate queries［J］.Journal of Software，2007，18(2):361-371.

［7］李東，袁應(yīng)化，葉友，等.基于屬性更新的語(yǔ)義緩存一致性維護(hù)自算法［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2009，37(5):139-144.Li Dong，Yuan Ying-hua，Ye You，et al.Algorithm of semantic caching coherency maintenance based on attribute update［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(5):139-144.

［8］Yeung M K H，Kwok Y-K.On energy efficient wireless data access:caching or not?［C］∥Proceedings of International Conference on Mobile Ad-hoc and Sensor Networks.Berlin/Heidelberg:Springer-Verlag，2005:528-537.

［9］Chung Y D.A cache invalidation scheme for continuous partialmatch queries in mobile computing environments［J］.Distributed and Parallel Databases，2008，23(3):207-234.

［10］Jing J，Elmagarmid A，Helal A，et al.Bit-sequences:an adaptive cache invalidation method in mobile client/server environments［J］.Mobile Networks and Applications，1997，2(2):115-127.