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

楊靜麗

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

?

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

楊靜麗

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

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

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

0 引言

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

1 基于語義緩存的查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

開始時，h1，h2和 MSS的緩存都是空的。

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

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

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

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

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

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

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

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

圖3 在不同的查詢請求情況下的緩存命中率

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

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

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

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

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

3 總結(jié)

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

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

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

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

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

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

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

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

[8] 卿宸,鐘勇,向柳明. 云數(shù)據(jù)庫中基于極大熵差分進(jìn)化的負(fù)載評估算法[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

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

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

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

TP393

A

2017.03.06)