移動(dòng)云數(shù)據(jù)庫(kù)的協(xié)作式語(yǔ)義緩存設(shè)計(jì)

楊靜麗

(南京工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院， 南京 210023)

?

移動(dòng)云數(shù)據(jù)庫(kù)的協(xié)作式語(yǔ)義緩存設(shè)計(jì)

楊靜麗

(南京工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院， 南京 210023)

移動(dòng)設(shè)備的數(shù)據(jù)訪問量在不斷增加，而且數(shù)據(jù)也越來(lái)越復(fù)雜，但是由于移動(dòng)設(shè)備本身的約束，增加了用戶的訪問時(shí)間。為了解決這個(gè)問題，一方面引入了各個(gè)用戶之間的協(xié)作式緩存，另一方面使用云資源。在這里，提供一個(gè)移動(dòng)云數(shù)據(jù)庫(kù)架構(gòu)模型和協(xié)作式語(yǔ)義緩存算法，使用戶可以根據(jù)自己對(duì)訪問時(shí)間的需求，來(lái)決定采取什么樣的方式來(lái)訪問數(shù)據(jù)。

協(xié)作式語(yǔ)義緩存； 移動(dòng)； 云； 數(shù)據(jù)庫(kù)； 能量消耗

0 引言

移動(dòng)計(jì)算的應(yīng)用在日常生活中慢慢的普及化了[1-4]，在任何時(shí)候、任何地點(diǎn)都能接入信息網(wǎng)獲取所需的信息將成為人們的普遍需求。移動(dòng)數(shù)據(jù)庫(kù)的發(fā)展對(duì)移動(dòng)計(jì)算的廣泛應(yīng)用起著重要的推動(dòng)作用。但由于移動(dòng)設(shè)備本身的一些約束，例如存儲(chǔ)有限、能量消耗、計(jì)算能力，網(wǎng)絡(luò)連接情況等，增加了用戶的訪問時(shí)間。為了解決這個(gè)問題，一方面引入了各個(gè)用戶之間的協(xié)作式語(yǔ)義緩存[5-6]，另一方面使用云資源[7-8]。緩存系統(tǒng)能夠存儲(chǔ)以前處理的數(shù)據(jù)，使用語(yǔ)義緩存可以大大減少在云和移動(dòng)設(shè)備之間的數(shù)據(jù)傳送，同時(shí)能進(jìn)一步提高云服務(wù)查詢的性能。

1 基于語(yǔ)義緩存的查詢

語(yǔ)義緩存主要包括三個(gè)關(guān)鍵概念[9][10]。首先，包括對(duì)被包含在每一個(gè)緩存入口的數(shù)據(jù)的語(yǔ)義描述，例如，查詢關(guān)系、投影屬性、查詢謂詞。可以使用語(yǔ)義描述來(lái)表示包含在緩存入口的相應(yīng)的數(shù)據(jù)項(xiàng)，同時(shí)能迅速地知道緩存入口是否能解答當(dāng)前的輸入查詢。其次，使用值函數(shù)來(lái)實(shí)現(xiàn)緩存數(shù)據(jù)替換。通過值函數(shù)來(lái)選擇并替換舊的緩存入口。最后，在緩存內(nèi)部，每一個(gè)緩存入口被稱作一個(gè)語(yǔ)義區(qū)域并被認(rèn)為是一個(gè)替換單元，它存儲(chǔ)了有關(guān)一個(gè)查詢結(jié)果的所有信息，包括投影屬性列表，查詢謂詞列表，這個(gè)區(qū)域的元組的數(shù)目，一個(gè)元組的最大可能大小，結(jié)果元組以及用來(lái)處理數(shù)據(jù)替換的另外數(shù)據(jù)。當(dāng)處理查詢時(shí)，語(yǔ)義緩存管理分析查詢內(nèi)容，同時(shí)建立兩個(gè)子查詢：試探查詢和剩余查詢。試探查詢直接在緩存中得到數(shù)據(jù)，剩余查詢從數(shù)據(jù)庫(kù)服務(wù)器或者使用云服務(wù)得到缺少的數(shù)據(jù)。在使用云服務(wù)時(shí)，除了要考慮移動(dòng)設(shè)備上的查詢優(yōu)化，還必須要考慮在云上的優(yōu)化。不同的云供應(yīng)商為他們提供的每個(gè)云服務(wù)提出了他們的定價(jià)模型。

云查詢處理和RDBMS系統(tǒng)中的查詢處理的主要區(qū)別是：由于在云中無(wú)數(shù)的配置和查詢路線，所以在云上處理一個(gè)查詢的可能路線也是無(wú)數(shù)的。在云上的查詢優(yōu)化除了要考慮時(shí)間還要考慮花費(fèi)，這就形成了一個(gè)二維優(yōu)化問題。為了解決這個(gè)問題，首先使用預(yù)算約束來(lái)最小化處理時(shí)間，使用時(shí)間約束最小化成本。使用貪婪算法分配每一個(gè)具體操作，并多次執(zhí)行該算法，產(chǎn)生多個(gè)時(shí)間表。按照約束，找出最優(yōu)時(shí)間表。使用語(yǔ)義緩存，在查詢裁剪算法過程中，可能會(huì)發(fā)生這4種情況:緩存準(zhǔn)確命中、緩存未命中、緩存擴(kuò)展命中、緩存部分命中。

緩存擴(kuò)展命中又包括3種類型：

(1) 輸入查詢的結(jié)果被包含在一個(gè)緩存區(qū)域中，例如，輸入查詢?chǔ)襧ava=60，而緩存區(qū)域中存放的是σjava>50σjava<70；

(2) 輸入查詢的結(jié)果需要從緩存中幾個(gè)緩存區(qū)域中檢索得到，例如，輸入查詢?chǔ)襧ava≥0，而一個(gè)緩存中存放的是σjava=60，另一個(gè)緩存中存放的是σjava>60；

(3) 輸入查詢和語(yǔ)義區(qū)域的查詢是等價(jià)的，例如，輸入查詢?chǔ)襧ava=60，語(yǔ)義區(qū)域的查詢?chǔ)襧ava>59 andσjava<61。那么，如果我們獲得了語(yǔ)義區(qū)域的查詢結(jié)果，也就得到了輸入查詢的查詢結(jié)果。

緩存部分命中指的是，使用試探查詢，一部分查詢結(jié)果可以從緩存中得到，另一部分查詢結(jié)果使用剩余查詢，從數(shù)據(jù)庫(kù)服務(wù)器中得到。在緩存中只能得到部分查詢結(jié)果，所有對(duì)應(yīng)于剩余查詢的元組，會(huì)在數(shù)據(jù)庫(kù)服務(wù)器中下載。

2 使用協(xié)作式語(yǔ)義緩存

2.1 協(xié)作式緩存的架構(gòu)

Padmanabhan and Sripanidkulchai[11][12]提出了一種稱為協(xié)作式對(duì)等網(wǎng)絡(luò)架構(gòu)。本文采用分布式協(xié)作式網(wǎng)絡(luò)，每一個(gè)客戶使用一個(gè)分布式哈希表來(lái)緩存自己的查詢基本信息和以往的查詢結(jié)果。在移動(dòng)網(wǎng)絡(luò)中，客戶會(huì)經(jīng)常從一個(gè)地方移動(dòng)到另一個(gè)地方，所以會(huì)受到電池能量和資源的限制。為了節(jié)約能量，我們不能在一些移動(dòng)客戶之間來(lái)選擇緩存管理器，也不能讓每一個(gè)客戶都變成一個(gè)分布式主機(jī)[13]，這樣當(dāng)為其他客戶服務(wù)時(shí)，會(huì)有一個(gè)復(fù)雜的搜索過程。在這里，我們提供一個(gè)新的協(xié)作式語(yǔ)義緩存的方法，緩存架構(gòu)，如圖1所示。

圖1 移動(dòng)云數(shù)據(jù)庫(kù)架構(gòu)

h是移動(dòng)主機(jī)，MSS是移動(dòng)支持站，它提供到主機(jī)h的無(wú)線連接。MSS有無(wú)線通訊接口，通過它，主機(jī)h就可以連接到有線主干網(wǎng)絡(luò)。MSS在移動(dòng)客戶端和服務(wù)器之間起到了網(wǎng)關(guān)的作用。F表示對(duì)應(yīng)的移動(dòng)主機(jī)的緩存?zhèn)浞荩鱾€(gè)客戶之間以協(xié)作的方式，共享他們的緩存。

2.2 云服務(wù)移動(dòng)計(jì)算環(huán)境下的協(xié)作式語(yǔ)義緩存

在移動(dòng)云數(shù)據(jù)庫(kù)架構(gòu)中，MSS不是一個(gè)移動(dòng)客戶端，而是作為一個(gè)緩存管理器。MSS主要包含3個(gè)獨(dú)立部分：緩存內(nèi)容管理器、緩存替換管理器、緩存解析管理器。緩存內(nèi)容管理器用于管理緩存內(nèi)的結(jié)果，經(jīng)常用于插入，刪除和查找。緩存替換管理器使用一些相關(guān)的項(xiàng)來(lái)處理緩存數(shù)據(jù)替換。緩存解析管理器用來(lái)恢復(fù)緩存中的數(shù)據(jù)同時(shí)調(diào)用一些外部工具來(lái)加載丟失的數(shù)據(jù)項(xiàng)。還使用3種其他類型的管理器，包括：移動(dòng)估計(jì)計(jì)算管理器、云估計(jì)計(jì)算管理、優(yōu)化管理器，主要用來(lái)處理每一次評(píng)估的計(jì)算以及制定更好的解決方案。當(dāng)在移動(dòng)設(shè)備上執(zhí)行一個(gè)查詢時(shí)，移動(dòng)估計(jì)計(jì)算管理器計(jì)算執(zhí)行時(shí)間和能量消耗。云估計(jì)計(jì)算管理器用來(lái)在云上處理一個(gè)查詢時(shí)的計(jì)算時(shí)間，移動(dòng)能量消耗以及必要的成本。當(dāng)考慮到用戶的一些約束時(shí)，比如，剩余電池情況，最大查詢響應(yīng)時(shí)間以及支付給云供應(yīng)商的費(fèi)用等等，優(yōu)化管理器負(fù)責(zé)在移動(dòng)查詢處理估計(jì)和云查詢處理估計(jì)之間進(jìn)行選擇。

舉例：假設(shè)h1和h2是兩個(gè)移動(dòng)客戶。

開始時(shí)，h1，h2和 MSS的緩存都是空的。

第一步：h1在時(shí)刻T1發(fā)送查詢請(qǐng)求Q1(select num, name from student where math<80 and 50

第二步：客戶端h2在時(shí)刻T2發(fā)送查詢請(qǐng)求Q2(select num, name from student where math<80 and 60

第三步：h1在時(shí)刻T3發(fā)送查詢請(qǐng)求Q3(select num , name from student where math<90 and 65

2.3 協(xié)作式語(yǔ)義緩存算法

上面的例子是一個(gè)典型的無(wú)線數(shù)據(jù)訪問情況，說明了怎樣使用協(xié)作式語(yǔ)義緩存來(lái)滿足客戶端的查詢。算法主要包含下面幾步：查詢緩存分析、估計(jì)計(jì)算、決策過程、查詢計(jì)算。首先，查詢緩存調(diào)用內(nèi)容管理器返回三種結(jié)果：緩存命中或未命中的類型、試探查詢、剩余查詢。其次，根據(jù)查詢分析結(jié)果進(jìn)行估計(jì)計(jì)算。在查詢命中的情況下，查詢直接在移動(dòng)設(shè)備上執(zhí)行，并得到結(jié)果，因此，可以忽略在移動(dòng)設(shè)備上的查詢處理成本。在查詢部分命中的情況下，要估計(jì)在移動(dòng)設(shè)備上的試探查詢處理時(shí)間和在云上處理剩余查詢的成本。另外，還要計(jì)算在云上處理整個(gè)輸入查詢的估計(jì)成本，在這里我們使用acquiredEstimation函數(shù)[14][15]來(lái)得到。函數(shù)在云估計(jì)緩存或者移動(dòng)估計(jì)緩存中查找那些估計(jì)值。估計(jì)緩存調(diào)用替換管理器將新的估計(jì)插入到緩存中保存起來(lái)。在擴(kuò)展命中的情況下，在移動(dòng)設(shè)備上處理查詢要花費(fèi)一定的成本。所以，在這種情況下，執(zhí)行之前來(lái)計(jì)算估計(jì)值是非常重要的。同時(shí)，依據(jù)在云上執(zhí)行查詢的預(yù)估成本來(lái)決定是應(yīng)當(dāng)在移動(dòng)設(shè)備上查詢還是在云上查詢。最后，在查詢未命中時(shí)，算法計(jì)算在云上處理查詢的成本，以滿足用戶的一些需求。一旦計(jì)算好了估計(jì)值，就可以決定應(yīng)該在哪處理查詢并建立查詢計(jì)劃。如果在執(zhí)行時(shí)間、能量消耗以及花費(fèi)上，都能滿足用戶需求，那么查詢緩存就會(huì)調(diào)用解析管理器來(lái)處理已經(jīng)產(chǎn)生的查詢計(jì)劃并返回查詢結(jié)果。同時(shí)，要更新估計(jì)緩存中的執(zhí)行時(shí)間，能量消耗，花費(fèi)等值，再使用查詢緩存的替換管理器替換查詢緩存中的數(shù)據(jù)。如果有些部分需要從查詢緩存中移除，那么與其對(duì)應(yīng)的移動(dòng)估計(jì)緩存中的內(nèi)容也應(yīng)該移除。如果這個(gè)部分被一個(gè)只需要很少花費(fèi)就能獲得查詢結(jié)果的替換了，那么這個(gè)估計(jì)也就不正確了。最后，所有的替換完成以后，用戶得到查詢結(jié)果。

算法定義的類和acquiredEstimation函數(shù)的實(shí)現(xiàn)以及整個(gè)算法的流程圖，如圖2所示。

圖2 協(xié)作式語(yǔ)義緩存算法流程圖

類的定義：查詢Query、查詢緩存QueryCache、移動(dòng)估計(jì)緩存MobileEstimationCache、云估計(jì)緩存CloundEstimationCache、移動(dòng)估計(jì)計(jì)算管理器、云估計(jì)計(jì)算管理器、優(yōu)化管理器。

acquiredEstimation函數(shù)：

輸入：Query query, EstimationCache estimationCache,

EstimationComputationManager estimationCo-

mpManager

輸出：Estimation estiResult

1. estiLookup=estiCache.lookup(query)

2. if estiLookup=CACHE_HIT then

3. estiResult=estiCache.process()

4.else 5.estiResult=estimationCompManager.compute(que

ry)

6.estiCache.replace(query,estiResult)

7.end if

8.return estiResult

3 仿真實(shí)驗(yàn)

使用Java進(jìn)行模擬實(shí)驗(yàn)，首先建立一個(gè)模擬實(shí)驗(yàn)環(huán)境：一個(gè)數(shù)據(jù)庫(kù)服務(wù)器，一臺(tái)模擬MSS的計(jì)算機(jī)，多個(gè)移動(dòng)客戶端，1.728 GHz CPU，2 GB of RAM，2300 mAh的電池容量，使用阿里私有云服務(wù)。實(shí)驗(yàn)中使用Hadoop框架以及數(shù)據(jù)倉(cāng)庫(kù)Hive。通過運(yùn)行在tomcat服務(wù)器上的RESTful Web服務(wù)來(lái)訪問云架構(gòu)基礎(chǔ)設(shè)施。Web服務(wù)使用云來(lái)評(píng)估查詢的成本，同時(shí)使用HiveQL在云上處理查詢，HiveQL使用MySQL數(shù)據(jù)庫(kù)存儲(chǔ)數(shù)據(jù)。為了研究本算法的性能，在下面3種情況下完成實(shí)驗(yàn)：(1)不使用緩存(2)使用語(yǔ)義緩存(3)使用協(xié)作式語(yǔ)義緩存。在每一種情況下，記錄算法的平均查詢時(shí)間、查詢成本、能量消耗以及緩存命中率。對(duì)于每一種情況，模擬執(zhí)行100次迭代，并記錄平均結(jié)果，如圖3所示。

圖3 在不同的查詢請(qǐng)求情況下的緩存命中率

從圖3可以看出隨著請(qǐng)求數(shù)量的增加，在使用語(yǔ)義緩存和協(xié)作式語(yǔ)義緩存兩種情況下，緩存命中率都在不斷地提高。在沒有使用緩存的情況下，命中率均為零。使用協(xié)作式語(yǔ)義緩存不僅可以利用移動(dòng)主機(jī)的本地緩存，還可以使用備份存儲(chǔ)在MSS中的其他移動(dòng)主機(jī)的緩存，所以緩存命中率迅速提高，如圖4所示。

圖4 在不同緩存擴(kuò)展命中率的情況下進(jìn)行100

從圖4可以看出，使用語(yǔ)義緩存和使用協(xié)作式語(yǔ)義緩存在處理時(shí)間，能量消耗，費(fèi)用等方面是相似的，這也說明了，估計(jì)緩存阻止了由于估計(jì)計(jì)算所引起的一些開銷。當(dāng)使用協(xié)作式語(yǔ)義緩存時(shí)，由于使用了云服務(wù)，查詢處理時(shí)間明顯減少，如圖5所示。

圖5 在不同緩存擴(kuò)展命中率的情況下進(jìn)行100次查詢的費(fèi)用

但是從圖5可以看出，由于使用云服務(wù)，產(chǎn)生了一些費(fèi)用。當(dāng)用戶在費(fèi)用上有一定限制時(shí)，本文算法可以阻止一些對(duì)于個(gè)別用戶來(lái)講花費(fèi)費(fèi)用比較高的查詢，因此，與不考慮任何用戶約束的語(yǔ)義緩存相比，使用本文算法減少了不滿足用戶約束的查詢的數(shù)量，保證用戶和云服務(wù)之間能互相協(xié)作的工作。當(dāng)緩存部分命中時(shí)，本算法和語(yǔ)義緩存算法的處理查詢時(shí)間是類似的，因而在緩存部分命中的情況下，查詢效率沒有提高。

3 總結(jié)

本文一方面引入了各個(gè)用戶之間相互合作的緩存，另一方面給出了一個(gè)應(yīng)用于移動(dòng)云數(shù)據(jù)庫(kù)的協(xié)作式語(yǔ)義緩存的算法。算法能夠預(yù)先估計(jì)在移動(dòng)設(shè)備上處理查詢和在云上處理查詢所花費(fèi)的時(shí)間，消耗的能量以及使用云服務(wù)所花費(fèi)的費(fèi)用，所以算法能夠根據(jù)用戶的要求來(lái)執(zhí)行查詢，用戶和數(shù)據(jù)庫(kù)系統(tǒng)之間能夠相互協(xié)作地工作。從仿真實(shí)驗(yàn)結(jié)果可以看出，由于算法能夠在移動(dòng)云環(huán)境下運(yùn)行，減少了查詢處理時(shí)間。

[1] 徐小龍，劉笑笑. 面向移動(dòng)計(jì)算環(huán)境的混合式數(shù)據(jù)同步機(jī)制[J].通信學(xué)報(bào)，2016，37(8):1-12.

[2] 薛彥俊. 移動(dòng)圖書館APP 應(yīng)用的探討[J].網(wǎng)絡(luò)與信息工程,2016,55-56.

[3] 胡金萍.新時(shí)期云數(shù)據(jù)庫(kù)研究[J].網(wǎng)絡(luò)技術(shù)，2016,43-45.

[4] 劉琰,郭斌,吳文樂等.移動(dòng)群智感知多任務(wù)參與者優(yōu)選方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2016,39(3):1-16.

[5] 龔玉利,冷文浩. 移動(dòng)計(jì)算中語(yǔ)義緩存的改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用與軟件，2014,31(2):37-40.

[6] 梁茹冰,劉瓊.移動(dòng)環(huán)境中語(yǔ)義緩存一致性維護(hù)的Agent 方法[J].北京郵電大學(xué)學(xué)報(bào)，2014,37(3):67-72.

[7] 林子雨,賴永炫,林琛,謝怡,鄒權(quán).數(shù)據(jù)庫(kù)研究[J].軟件學(xué)報(bào)，2012，23(5):1148-1166.

[8] 卿宸,鐘勇,向柳明. 云數(shù)據(jù)庫(kù)中基于極大熵差分進(jìn)化的負(fù)載評(píng)估算法[J].計(jì)算機(jī)應(yīng)用，2014，34(S2):123-125.

[9] Dar, S., Franklin, M.J., Jonsson, B.T., Srivastava. Semantic data caching and replacement:Very Large Data Bases VLDB[J]. 1996: 330-341.

[10] Ren, Q., Dunham, M.H., Kumar, V. Semantic caching and query processing[J]. IEEE Trans. Knowl. Data Eng.2003,15(1): 192-210.

[11] Padmanabhan V N, Sripanidkulchai K. The case for cooperative networking[C]∥Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS’02), Mar 7-8, 2002. Berlin,Germany: Springer-Verlag, 2002: 178-190.

[12] Liang Ru-bing, Liu Qiong. Answering queries using cooperative semantic cache in mobile computing environments[J]. The Journal of China Universities of Posts and Telecommunications, 2012, 19(3): 54-59.

[13] Bruno, N., Jain, S., Zhou, J.Continuous cloud-scale query optimization and processing[C]∥Proceedings of the VLDB Endowment, 2013, 6(11): 961-972.

[14] Mikael Perrin, Jonathan Mullen, Florian Helff, LeGruenwald, and Laurent d’Orazio. Time-, Energy-, and Monetary Cost-Aware Cache Design for a Mobile-Cloud Database System[C]∥Biomedical Data Management and Graph Online Querying. VLDB. 2015,71-85.

[15] Li D W, Huang W J, Hu J H, et al. A distributed redundant real-time data storage mechanism[J]. Journal of Shanghai Jiaotong University,2014, 48(7): 948- 952.

Cooperative Semantic Cache Design for Mobile-Cloud Database Systems

Yang Jingli

(School of Computer and Software, Nanjing Institute of Industry Technology, Nanjing 210023, China)

Growing demand for mobile access to data is only outpaced by the growth of large and complex data, accentuating the constrained nature of mobile devices. On the one hand, we introduce the cooperative semantic cache among different users, on the other hand, we use cloud resources to solve this problem. We present a mobile cloud database architecture model and a cooperative semantic cache algorithm by which the users can decide the manner to use to access data according to their demand of accessing time.

Cooperative semantic cache; Mobile; Cloud; Energy consumption

國(guó)家自然科學(xué)基金(61671253),南京工業(yè)職業(yè)技術(shù)學(xué)院2015年院級(jí)科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目(TK15-04-01)

楊靜麗(1971-),女, 遼寧綏中人,教授，碩士,研究方向：軟件技術(shù),云計(jì)算等。

1007-757X(2017)07-0007-04

TP393

A

2017.03.06)