易 俗 殷慧文 張一川 張 莉

1(遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院 遼寧 沈陽 110036) 2(東北大學(xué)軟件學(xué)院 遼寧 沈陽 110819)

?

分布式環(huán)境下的頻繁數(shù)據(jù)緩存策略

易 俗1殷慧文1張一川2張 莉2

1(遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院 遼寧 沈陽 110036)2(東北大學(xué)軟件學(xué)院 遼寧 沈陽 110819)

大數(shù)據(jù)環(huán)境下利用分布式緩存技術(shù)能夠提供高性能、高可用的數(shù)據(jù)查詢。針對輕量級數(shù)據(jù)庫應(yīng)用的頻繁數(shù)據(jù)緩存策略具有高效、易擴(kuò)展的優(yōu)點(diǎn)，更有利于輕型分布式數(shù)據(jù)庫應(yīng)用的查詢優(yōu)化改進(jìn)。因此，通過分析用戶行為和用戶查詢特征，研究針對近期頻繁查詢數(shù)據(jù)的數(shù)據(jù)緩存策略，能夠預(yù)測高命中率的緩存數(shù)據(jù)，提高數(shù)據(jù)查詢效率。首先分析并給出查詢頻繁度的定義，其次根據(jù)時間因素對緩存數(shù)據(jù)選取的影響細(xì)化用戶查詢操作，并通過查詢數(shù)據(jù)的查詢頻繁度應(yīng)對查詢過程中不同的緩存命中情況整合節(jié)點(diǎn)間的緩存數(shù)據(jù)。最后，實(shí)驗(yàn)證明該數(shù)據(jù)緩存策略具有較高的數(shù)據(jù)命中率，能夠提高數(shù)據(jù)查詢的效率。實(shí)現(xiàn)方面可根據(jù)實(shí)際需要采用不同的緩存屬性組合，具有良好的易擴(kuò)展性。

數(shù)據(jù)緩存策略 查詢頻繁度 集群環(huán)境 分布式系統(tǒng) 大數(shù)據(jù)

0 引 言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)呈現(xiàn)出4V(Volume、Variety、Value、Velocity)[1]特性，即數(shù)據(jù)量大、類型繁多、價值密度低且處理速度快。這些特性也對數(shù)據(jù)庫系統(tǒng)提出了高并發(fā)讀寫、海量數(shù)據(jù)的高效存儲和訪問，以及高可擴(kuò)展性和可用性的需求[2]。傳統(tǒng)的關(guān)系數(shù)據(jù)庫雖然穩(wěn)定性高且對于集中式存儲的存儲查詢效率較高；但面對大數(shù)據(jù)的這些特性，關(guān)系數(shù)據(jù)庫高一致性和查準(zhǔn)率已經(jīng)不存在優(yōu)勢，而關(guān)系數(shù)據(jù)庫的擴(kuò)展性以及對海量數(shù)據(jù)的響應(yīng)速度都遇到了障礙，不能勝任大數(shù)據(jù)的存儲管理要求，以及滿足不了高性能、高可用的分布式查詢處理要求。

非關(guān)系型數(shù)據(jù)庫——NoSQL[3-4]的數(shù)據(jù)存儲不需要固定的表結(jié)構(gòu)，也不存在連接操作，雖然不遵循傳統(tǒng)關(guān)系型數(shù)據(jù)庫的ACID特性，但是對于非結(jié)構(gòu)或者半結(jié)構(gòu)化的分布式數(shù)據(jù)存儲和管理效率較高。NoSQL對數(shù)據(jù)庫事務(wù)一致性需求低，實(shí)時讀寫快，且對復(fù)雜的查詢響應(yīng)較快。因此NoSQL更適用于大數(shù)據(jù)的存儲和處理。

NoSQL的數(shù)據(jù)分布式存儲減少了單個服務(wù)器的存儲壓力，提高了數(shù)據(jù)的故障恢復(fù)能力；但是這種分布式查詢處理的要求要比集中式查詢變得更加復(fù)雜，需要從高性能、高可用和易擴(kuò)展角度研究分布式環(huán)境下的優(yōu)化技術(shù)和策略，以提高數(shù)據(jù)查詢處理。

現(xiàn)實(shí)生活中的數(shù)據(jù)庫應(yīng)用多以選擇、投影、連接查詢?yōu)橹鳎玢y行、學(xué)校、辦公管理等業(yè)務(wù)。這些數(shù)據(jù)庫應(yīng)用不同于科學(xué)計算、數(shù)據(jù)挖掘等分析應(yīng)用，不需要協(xié)同過濾、機(jī)器學(xué)習(xí)和圖等具有復(fù)雜算法的計算過程，算法的復(fù)雜特點(diǎn)在一定程度上將直接影響分布式系統(tǒng)的優(yōu)化方法和目標(biāo)。本文從算法角度將僅針對數(shù)據(jù)屬性和元組的數(shù)據(jù)庫查詢應(yīng)用定義為輕量級應(yīng)用。對于輕量級的分布式數(shù)據(jù)庫系統(tǒng)的查詢應(yīng)用尤其需要滿足易擴(kuò)展、針對性良好等特點(diǎn)。針對頻繁數(shù)據(jù)特征優(yōu)化目標(biāo)的緩存策略研究，能夠提供較為準(zhǔn)確且快速的查詢優(yōu)化策略，是分布式數(shù)據(jù)庫系統(tǒng)領(lǐng)域的研究熱點(diǎn)。

1 相關(guān)工作

隨著硬件技術(shù)的發(fā)展，大量研究針對分布式內(nèi)存對象緩存系統(tǒng)，比如Memcached[5]、BigTable[6]、PACMan[7]和GridGrain[8]等。由于磁盤容量往往比內(nèi)存大很多,想通過內(nèi)存永久存放、讀取和處理數(shù)據(jù)是不能解決的問題。因此，通常利用緩存作為內(nèi)存。

在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)查詢效率依賴于緩存數(shù)據(jù)的設(shè)計，如何選取高命中率緩存數(shù)據(jù)，以及管理不同節(jié)點(diǎn)間的數(shù)據(jù)緩存是當(dāng)今大數(shù)據(jù)查詢的研究熱點(diǎn)。文獻(xiàn)[9-10]中提出了元數(shù)據(jù)緩存的解決方案，通過緩存底層存儲數(shù)據(jù)的元數(shù)據(jù)以實(shí)現(xiàn)查詢數(shù)據(jù)的快速定位。由于元數(shù)據(jù)緩存多建立在客戶端，進(jìn)而減輕了總控節(jié)點(diǎn)的工作負(fù)荷。在緩存命中的情況下，客戶端可跳過總控節(jié)點(diǎn)，直接與存儲節(jié)點(diǎn)建立映射，獲得更佳的查詢性能。但這種緩存方式可擴(kuò)展性不佳，對于大規(guī)模分布式系統(tǒng)，很難將底層數(shù)據(jù)全部緩存至客戶端。同時，由于元數(shù)據(jù)緩存在客戶端內(nèi)，系統(tǒng)中任何數(shù)據(jù)變動都有可能破壞客戶端內(nèi)緩存數(shù)據(jù)與底層存儲數(shù)據(jù)的一致性，導(dǎo)致客戶端“臟數(shù)據(jù)”的讀取。基于共享數(shù)據(jù)緩存的分布式緩存體系[11-12]通過數(shù)據(jù)共享的方式減少服務(wù)器間的數(shù)據(jù)交換，提高緩存數(shù)據(jù)利用率。在這種緩存體系下，集群中節(jié)點(diǎn)的緩存數(shù)據(jù)被共享至緩存池中，每個節(jié)點(diǎn)可根據(jù)查詢?nèi)蝿?wù)的不同，訪問不同節(jié)點(diǎn)內(nèi)的緩存數(shù)據(jù)，進(jìn)而起到降低節(jié)點(diǎn)間通信開銷、提高查詢效率的作用。但這種緩存方式對共享緩存池的維護(hù)有較高要求，共享池資源管理易成為系統(tǒng)性能瓶頸，增加了系統(tǒng)開發(fā)、維護(hù)開銷，緩存池內(nèi)數(shù)據(jù)更新代價也較大，不能及時對近期頻繁查詢數(shù)據(jù)進(jìn)行處理。此外，文獻(xiàn)[13]從圖論的角度探討了緩存數(shù)據(jù)部署對查詢效率的影響，地理位置相鄰的節(jié)點(diǎn)間緩存數(shù)據(jù)具有更低的數(shù)據(jù)傳輸延遲，全局查詢效率更高，但同時也承擔(dān)著更高的節(jié)點(diǎn)故障風(fēng)險。這種方法雖未解決緩存數(shù)據(jù)的選取問題，但為集群中節(jié)點(diǎn)緩存的設(shè)計提供了新的思路。

針對大數(shù)據(jù)查詢效率問題，本文提出了條件屬性查詢頻繁度的概念，并基于此對Apriori算法進(jìn)行改進(jìn)，實(shí)現(xiàn)了一種分布式環(huán)境下的數(shù)據(jù)緩存策略，以建立頻繁查詢數(shù)據(jù)的高命中緩存的方式，既解決大數(shù)據(jù)的高效查詢問題，又能夠針對輕量級查詢應(yīng)用具有易擴(kuò)展的特性，強(qiáng)調(diào)時間因素在緩存數(shù)據(jù)選取上的重要性。

2 數(shù)據(jù)緩存策略

分布式集群中的工作節(jié)點(diǎn)由于內(nèi)存資源有限，對于存儲在本地的大量數(shù)據(jù)，可能出現(xiàn)被查詢數(shù)據(jù)無法一次全部加載入內(nèi)存的情況，而多次內(nèi)存與磁盤間的數(shù)據(jù)傳輸又會增加查詢?nèi)蝿?wù)的執(zhí)行時間，降低查詢效率。對于一些輕量級數(shù)據(jù)管理業(yè)務(wù)而言，數(shù)據(jù)庫查詢請求多數(shù)為其中一些關(guān)鍵數(shù)據(jù)屬性的頻繁查詢處理。因此，在數(shù)據(jù)裝載內(nèi)存過程中，將頻繁處理的屬性數(shù)據(jù)盡量載入內(nèi)存作為數(shù)據(jù)庫查詢的主要目標(biāo)，能夠調(diào)高頻繁數(shù)據(jù)的查詢機(jī)會，從而提高數(shù)據(jù)庫查詢處理的效率。

當(dāng)前主流的NoSQL數(shù)據(jù)庫多采用LIRS算法實(shí)現(xiàn)數(shù)據(jù)緩存機(jī)制，LIRS算法使用IRR(Inter-Reference Recency)和Recency兩個參數(shù)。IRR：一個頁面最近兩次的訪問間隔；Recency：頁面上次訪問至今訪問了多少其他頁。能夠針對數(shù)據(jù)的近期更迭給出緩存策略。但是，這種與業(yè)務(wù)無關(guān)的處理方法無法對較長時間內(nèi)頻繁查詢的業(yè)務(wù)屬性數(shù)據(jù)進(jìn)行更合理的統(tǒng)計，不能采取有針對性的策略緩存查詢數(shù)據(jù)。

針對輕量級數(shù)據(jù)庫查詢系統(tǒng)的應(yīng)用環(huán)境中數(shù)據(jù)更新頻率較低，且數(shù)據(jù)具有更強(qiáng)的業(yè)務(wù)語義。因此從查詢屬性入手，深入考察查詢條件屬性對業(yè)務(wù)的關(guān)聯(lián)程度，能夠更準(zhǔn)確地發(fā)現(xiàn)較長時間內(nèi)的頻繁屬性查詢數(shù)據(jù)，進(jìn)一步提高緩存數(shù)據(jù)的命中率。

本文引入查詢屬性頻繁度的概念，使用一種改進(jìn)的Apriori算法—FD-Apriori確定頻繁數(shù)據(jù)，并根據(jù)頻繁數(shù)據(jù)處理數(shù)據(jù)緩存。該算法可根據(jù)查詢記錄日志文件分析獲得較長時間內(nèi)頻繁查詢的數(shù)據(jù)，并將具有高頻繁度的數(shù)據(jù)進(jìn)行緩存，獲得相比于LIRS算法命中率更高的緩存數(shù)據(jù)。同時，該方法易于擴(kuò)展，能夠更有效地支持輕量級數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化。

2.1 Apriori算法

Apriori算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識，基于逐層搜索迭代方法獲得不同維度的頻繁項(xiàng)集，即通過較低維頻繁項(xiàng)集獲得較高維的頻繁項(xiàng)集候選集，經(jīng)過進(jìn)一步支持度驗(yàn)證獲得較高維頻繁項(xiàng)集的方法實(shí)現(xiàn)頻繁項(xiàng)集的挖掘[14-15]。

Apriori算法包括以下兩類操作：

1) 連接步：根據(jù)已有的頻繁k項(xiàng)集集合獲得頻繁項(xiàng)集的候選集集合Ck+1。將Lk中各項(xiàng)集的項(xiàng)按字典序排序，對于Lk集合中任意兩k項(xiàng)集l1、l2，若有l(wèi)1[1]=l2[1]，l1[2]=l2[2]，l1[k-1]=l2[k-1]，l1[k]≠l2[k]，則對l1、l2做連接∞操作，獲得k+1項(xiàng)集Ck+1={l1[1]，l1[2],…,l1[k-1]，l1[k]，l2[k]}。重復(fù)上述連接操作，得到的k+1項(xiàng)集集合即為頻繁k+1項(xiàng)集的候選集集合Ck+1。

2) 剪枝步：篩選Ck+1中不滿足頻繁要求的項(xiàng)集，獲得頻繁k+1項(xiàng)集集合Lk+1。根據(jù)先驗(yàn)性質(zhì)——頻繁項(xiàng)集的所有非空子集也一定是頻繁的，檢驗(yàn)連接步操作獲得的Ck+1中各項(xiàng)集子集支持度計數(shù)是否滿足最小支持度計數(shù)min_sup，去除Ck+1中不滿足先驗(yàn)性質(zhì)的項(xiàng)集，進(jìn)而獲得頻繁k+1項(xiàng)集Lk+1。

Apriori算法在執(zhí)行過程中，通過重復(fù)迭代“連接步—剪枝步”操作進(jìn)而獲得記錄集D中所有滿足頻繁要求的n項(xiàng)集(n≥1)。

2.2 基于Apriori算法的數(shù)據(jù)緩存策略

本文提出了基于條件屬性查詢頻繁度的數(shù)據(jù)緩存策略。首先，該策略的核心為條件屬性查詢頻繁度概念的提出及計算方法；其次，在此基礎(chǔ)上通過改進(jìn)現(xiàn)有Apriori算法，提出FD-Apriori算法以獲取具有較高查詢頻繁度的條件屬性組；最后，針對計算得到的條件屬性數(shù)據(jù)集，給出緩存情況的分類，以及緩存更新步驟。具體情況如下。

首先，在數(shù)據(jù)查詢過程中，查詢屬性分為結(jié)果屬性與條件屬性。而近期查詢頻率較高的條件屬性又可分為兩種：始終保持高查詢頻率的條件屬性，以及在近期短時間內(nèi)被大量檢索的條件屬性。對此，本文針對條件屬性定義查詢頻繁度FD的概念，用于區(qū)分頻繁查詢屬性、解釋屬性的頻繁性。

定義1條件屬性的查詢頻繁度:條件屬性的頻繁性度量，用于區(qū)分不同條件屬性間查詢熱度的高低。通過設(shè)置查詢計數(shù)上限以及加權(quán)函數(shù)的方式強(qiáng)調(diào)近期查詢對屬性頻繁性的影響。

對于查詢條件屬性a，a的查詢頻繁度FD計算過程為：

① 根據(jù)查詢?nèi)罩精@得屬性a第t天被查詢次數(shù)。其中t表示日志記錄時間距離有效記錄起始時間的天數(shù)，t越大，表示日志記錄時間距離當(dāng)前時間越近。

② 對Count(t)進(jìn)行規(guī)范化處理。設(shè)置近期記錄比例qrec區(qū)分近期記錄與歷史記錄。對于第t天查詢?nèi)罩綝t，當(dāng)t≥qrec×T時，Dt所包含記錄屬于近期記錄；當(dāng)tMaxhis。對于總記錄天數(shù)，用T表示。Countstd(t)取值情況如式(1)所示：

(1)

③ 根據(jù)加權(quán)函數(shù)W(t)，對Countstd進(jìn)行加權(quán)操作。加權(quán)函數(shù)W(t)應(yīng)滿足以下條件：

W(t)應(yīng)為增函數(shù)，以突出近期記錄的重要性，獲得近期短時間內(nèi)被大量檢索的頻繁屬性。

不同時間t應(yīng)對應(yīng)不同權(quán)值，以區(qū)分處于不同查詢層次的屬性。

④ 計算屬性a的頻繁度如式(2)所示:

FD=∑W(t)×Countstd

(2)

其次，在FD(條件屬性頻繁度)概念的支持下，本文以頻繁度替換傳統(tǒng)Apriori算法中的支持度，從而獲得一種能夠準(zhǔn)確篩選出頻繁查詢條件屬性的改進(jìn)Apriori算法—FD-Apriori。

FD-Apriori的偽碼，如算法1所示。

FD-Apriori算法使用一種逐層搜索的迭代方法，利用“K-1項(xiàng)集”用于搜索“K項(xiàng)集”。首先，找出根據(jù)條件查詢頻繁度的頻繁“1項(xiàng)集”集合，該集合記作A1，如偽碼中第1)步至第4)步。A1用于找頻繁“2項(xiàng)集”的集合A2，而A2用于找A3。通過迭代的方式找到“K項(xiàng)集”。每個Ak都需要對整個日志數(shù)據(jù)庫進(jìn)行一次掃描。

算法的核心思想是偽碼中的第7)步(連接步)和第11)步(剪枝步)。其中，連接步是自連接，原則是保證前k-2項(xiàng)相同，并按照字典順序連接；在剪枝步中保證任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。即某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從Ck中刪除。

該算法簡單直觀的描述就是為了根據(jù)定義的FD(條件屬性查詢頻繁度)發(fā)現(xiàn)頻繁項(xiàng)集。過程為掃描、計數(shù)、比較、產(chǎn)生頻繁項(xiàng)集、連接、剪枝、產(chǎn)生候選項(xiàng)集的重復(fù)迭代處理，直到不能發(fā)現(xiàn)更大的頻集。

算法1FD-Apriori算法

輸入：查詢?nèi)罩綝(D=∑Di,Di表示第i天查詢?nèi)罩? ，最小頻繁度minfd

輸出：A-D中各長度的頻繁查詢條件屬性組集

方法：

1) k=1

2) A1=φ

3) if(a.fd in D≥minfd){

4) add a into A1

//檢索查詢?nèi)罩?，獲得長度為1的頻繁查詢條件屬性組集

5) }

6) while(true){

7) Ck+2=Ak∞Ak+1

//連接步操作，獲得K+1長度的頻繁查詢條件屬性組候

//選集

8) Ak+2=φ

9) for(ak+1: Ak+1){

10) if(ak+1.fd in D ≥minfd)

11) add ak+1into Ak+1

//剪枝步操作，去除候選集中非頻繁的屬性組

12) }

13) }

14) if(ak+1≠φ)

15) k++

16) else

17) break

//當(dāng)不存在更大長度的頻繁查詢條件屬性組集時，結(jié)束

//循環(huán)

18) return A=∪kAk

在NoSQL數(shù)據(jù)庫中，數(shù)據(jù)存儲方式多樣，如以鍵值對方式存儲數(shù)據(jù)的Cassandra、以列族存儲的HBase等。接下來僅以數(shù)據(jù)塊的概念泛指NoSQL型數(shù)據(jù)庫中數(shù)據(jù)存儲的最小單元進(jìn)行討論。

在集群存儲節(jié)點(diǎn)上，第一次運(yùn)行FD-Apriori算法獲得在當(dāng)前存儲節(jié)點(diǎn)中頻繁被檢索的數(shù)據(jù)塊，第二次在頻繁數(shù)據(jù)塊上運(yùn)行該算法，獲得在數(shù)據(jù)查詢中查詢頻率較高的條件屬性組集合。在FD-Apriori算法返回的屬性組集合中包含不同長度的條件屬性集，根據(jù)系統(tǒng)實(shí)際需要將不同長度的滿足頻繁定義的條件屬性組對應(yīng)數(shù)據(jù)緩存至內(nèi)存中，并針對查詢較頻繁的結(jié)果屬性建立B+樹索引以處理緩存中屬性部分命中的情況。當(dāng)用戶進(jìn)行查詢操作時，若查詢的數(shù)據(jù)塊在內(nèi)存中，分布式系統(tǒng)不再從磁盤中讀取查詢數(shù)據(jù)，而是直接在內(nèi)存中進(jìn)行查詢并返回查詢結(jié)果，可在一定程度上減少內(nèi)存與磁盤間的數(shù)據(jù)交換次數(shù)，節(jié)省查詢開銷。

在應(yīng)用緩存策略的節(jié)點(diǎn)上，對于一次實(shí)際數(shù)據(jù)查詢，如圖1所示的3種不同命中情況。

圖1 查詢屬性不同命中情況處理流程

(1) 未命中:查詢中的條件屬性不在內(nèi)存緩存中。此時需要重新從磁盤中加載數(shù)據(jù)塊數(shù)據(jù)進(jìn)行查詢操作，查詢速度較慢。

(2) 部分命中:查詢中的條件屬性僅有一部分在內(nèi)存緩存中。由于查詢結(jié)果屬性個數(shù)較少且固定，可通過建立索引的方式提高查詢效率。此時可根據(jù)內(nèi)存中已有的屬性數(shù)據(jù)對數(shù)據(jù)庫中的記錄進(jìn)行篩選，減少需進(jìn)一步在數(shù)據(jù)庫中檢索的數(shù)據(jù)量。同時，提供相應(yīng)結(jié)果屬性的索引值，加速數(shù)據(jù)的檢索。這種情況下雖仍需從磁盤中讀取數(shù)據(jù)，但因索引的建立以及查詢規(guī)模較小，查詢速度相比于未命中情況仍比較理想。

(3) 完全命中:查詢中的條件屬性全部在內(nèi)存緩存中。這是最理想的情況，可直接返回查詢結(jié)果。

對于同樣的查詢集，上述3種命中情況的出現(xiàn)取決于內(nèi)存中的屬性緩存方式。當(dāng)以屬性組的形式緩存數(shù)據(jù)時，屬性組的長度越大，查詢完全命中的可能性也就越大；但同時，部分命中情況下被篩選掉的無關(guān)數(shù)據(jù)量可能會相應(yīng)減少。通常情況下，較長屬性組適合查詢環(huán)境中存在某一類極高頻查詢的情況，中等長度屬性組則更適合存在多類頻率較高且接近的查詢的查詢環(huán)境。本文將在實(shí)驗(yàn)?zāi)M章節(jié)測試不同長度屬性組對查詢結(jié)果的影響。

由于本文采取的是一種靜態(tài)的數(shù)據(jù)緩存策略，緩存數(shù)據(jù)具有固定的生命周期，相比于LIRS類數(shù)據(jù)緩存算法，需定期更新內(nèi)存中的緩存數(shù)據(jù)。由于在計算條件屬性的查詢頻繁度過程中，以天為單位進(jìn)行查詢次數(shù)計數(shù)，故應(yīng)以天為更新頻率進(jìn)行緩存數(shù)據(jù)的更新。緩存更新操作應(yīng)在一天中節(jié)點(diǎn)訪問負(fù)荷最小的時間段進(jìn)行。緩存更新共分為6步:

(1) 禁用內(nèi)存緩存數(shù)據(jù)，出現(xiàn)數(shù)據(jù)查詢請求時直接檢索存儲底層的數(shù)據(jù)塊，此時緩存屬性命中率為0。

(2) 根據(jù)近T天查詢?nèi)罩具\(yùn)行FD-Apriori算法，獲得頻繁查詢數(shù)據(jù)塊與頻繁查詢屬性組集。

(3) 對頻繁查詢數(shù)據(jù)塊加鎖，限制數(shù)據(jù)塊內(nèi)數(shù)據(jù)的修改操作，保證緩存更新期間緩存數(shù)據(jù)與底層數(shù)據(jù)的一致性。

(4) 對比待緩存頻繁查詢數(shù)據(jù)與內(nèi)存中已有緩存數(shù)據(jù)，保留相同的緩存數(shù)據(jù)，對于不同的緩存數(shù)據(jù)，清除舊頻繁數(shù)據(jù)，加載新頻繁數(shù)據(jù)。

(5) 將頻繁查詢數(shù)據(jù)塊解鎖，恢復(fù)數(shù)據(jù)塊內(nèi)數(shù)據(jù)的修改權(quán)限。

(6) 更新緩存數(shù)據(jù)索引結(jié)構(gòu)，啟用內(nèi)存緩存數(shù)據(jù)。

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

3.1 緩存策略在HBase上的實(shí)現(xiàn)

基于FD-Apriori算法的頻繁數(shù)據(jù)緩存策略具有易擴(kuò)展性，能夠面向輕量級數(shù)據(jù)庫應(yīng)用給出快速解決方案。本文將針對HBase數(shù)據(jù)設(shè)計并實(shí)現(xiàn)上述數(shù)據(jù)緩存策略的應(yīng)用范例。HBase是一個面向列的NoSQL數(shù)據(jù)庫，其作為Hadoop 項(xiàng)目的一部分，運(yùn)行于HDFS文件系統(tǒng)之上[16-17]。

在數(shù)據(jù)讀取方面，HBase采取按列存儲策略，相比于按行存儲策略，減少了數(shù)據(jù)讀取過程中冗余數(shù)據(jù)的讀取，提高了數(shù)據(jù)讀取效率，使數(shù)據(jù)檢索更加迅速有效。在存儲方面，HBase將規(guī)模較大的數(shù)據(jù)表分割成若干區(qū)域(region)，每個區(qū)域順序存儲數(shù)據(jù)表中一定數(shù)量的記錄，將多個相關(guān)區(qū)域合并操作，即可獲得完整的表信息。HBase數(shù)據(jù)表分割過程，如圖2所示，其中Table表示現(xiàn)有數(shù)據(jù)表，Region表示分割過程產(chǎn)生的數(shù)據(jù)區(qū)域。

圖2 HBase分割數(shù)據(jù)表過程

HBase中的區(qū)域?qū)?yīng)上文提到的數(shù)據(jù)塊概念?；诒疚牡臄?shù)據(jù)緩存策略，根據(jù)數(shù)據(jù)查詢情況篩選出查詢頻繁的數(shù)據(jù)表區(qū)域，將頻繁度最高的若干區(qū)域中的頻繁屬性數(shù)據(jù)緩存至內(nèi)存緩沖區(qū)中。當(dāng)該區(qū)域中的數(shù)據(jù)被訪問時，根據(jù)查詢屬性與內(nèi)存中緩存屬性的命中情況，進(jìn)行不同的數(shù)據(jù)查詢操作。在HBase環(huán)境下，改進(jìn)后的數(shù)據(jù)查詢過程，如圖3所示。

圖3 HBase環(huán)境下改進(jìn)的數(shù)據(jù)查詢過程

由于HBase采取按列存儲策略存儲表數(shù)據(jù)，對于內(nèi)存中的頻繁屬性數(shù)據(jù)，可使用列組的形式進(jìn)行緩存。在列組結(jié)構(gòu)中，數(shù)據(jù)以按行存儲的形式進(jìn)行組織，雖然在緩存建立、更新過程中會帶來額外的壓力。但列組結(jié)構(gòu)能夠加快內(nèi)存中屬性間的匹配速度，減少部分命中情況下記錄篩選的時間開銷，提高查詢效率。

3.2 實(shí)驗(yàn)設(shè)計

為驗(yàn)證基于FD-Apriori算法的頻繁數(shù)據(jù)緩存策略在數(shù)據(jù)庫查詢效率方面表現(xiàn)，本文采用Hadoop-HBase搭建分布式實(shí)驗(yàn)環(huán)境，進(jìn)而考察算法的優(yōu)化效果。

在實(shí)驗(yàn)數(shù)據(jù)選擇方面，針對本文研究背景提出的輕量級分布式數(shù)據(jù)庫查詢應(yīng)用，查詢業(yè)務(wù)采用以銀行個人儲蓄存取、查詢業(yè)務(wù)數(shù)據(jù)，以及小額貸款查詢、處理業(yè)務(wù)數(shù)據(jù)。由于銀行真實(shí)數(shù)據(jù)的獲取涉及到一定的隱私保護(hù)問題，因此本文根據(jù)少部分基礎(chǔ)業(yè)務(wù)數(shù)據(jù)，按照屬性約束隨機(jī)生成大量數(shù)據(jù)，以此作為真實(shí)場景模擬查詢數(shù)據(jù)以及相應(yīng)的用戶查詢行為。

實(shí)驗(yàn)構(gòu)建了8節(jié)點(diǎn)的小型Hadoop集群環(huán)境，CPU為i7處理器，內(nèi)存為16 GB。模擬數(shù)據(jù)方面在40 MB基礎(chǔ)業(yè)務(wù)數(shù)據(jù)的基礎(chǔ)上，通過屬性規(guī)則約束隨機(jī)生成數(shù)據(jù)量為100 GB的模擬數(shù)據(jù)，令T=7，將模擬數(shù)據(jù)分成7等份，以模擬不同時間的查詢?nèi)罩?。在?yīng)用本文緩存策略前，一條正常SQL Select語句的查詢時間平均約為1 500 ms。

通過統(tǒng)計用戶查詢中各屬性的查詢情況，可以獲得不同長度的滿足頻繁定義的條件屬性組合。在此基礎(chǔ)上，分別考察(1)利用LIRS算法的緩存策略的平均查詢時間。以及在緩存相同個數(shù)屬性的前提下，考察(2)基于FD-Apriori算法的頻繁數(shù)據(jù)單一屬性緩存平均查詢時間。(3)基于FD-Apriori算法的頻繁數(shù)據(jù)兩屬性組緩存平均查詢時間。(4)基于FD-Apriori算法的頻繁數(shù)據(jù)三屬性組緩存平均查詢時間，從而對比檢驗(yàn)頻繁數(shù)據(jù)緩存的執(zhí)行情況以及多組屬性緩存策略的變化。除此之外，還將設(shè)計實(shí)驗(yàn)從頻繁數(shù)據(jù)的命中率角度檢驗(yàn)FD-Apriori算法不同屬性組的結(jié)果。

3.3 實(shí)驗(yàn)分析結(jié)果

在不同算法以及不同緩存屬性組方式下，平均查詢效率如圖4所示，查詢命中情況，如圖5所示。

圖4 不同緩存方式查詢效率比較

圖5 不同緩存方式屬性命中情況比較

由圖4可知，本文的數(shù)據(jù)緩存策略在頻繁區(qū)域中能夠明顯提高數(shù)據(jù)查詢效率，而對于其他區(qū)域中的數(shù)據(jù)查詢，由于未做任何處理，故不會影響其上的查詢操作。在圖4中可以發(fā)現(xiàn)，LIRS算法緩存策略執(zhí)行效率低于FD-Apriori算法，當(dāng)單一屬性時效率差異并不明顯，而當(dāng)頻繁屬性組增多的時候，F(xiàn)D-Apriori算法的頻繁數(shù)據(jù)特征將使得目標(biāo)效率變化較大。從執(zhí)行效率角度緩存兩、三屬性組相比單一屬性具有更高的查詢效率。這是由于在實(shí)際查詢過程中，單一屬性的條件查詢頻率較低，緩存完全命中率不理想，相比于多屬性查詢，單一屬性緩存不能很好地去除不相關(guān)記錄，篩選出的記錄規(guī)模較大，為之后在數(shù)據(jù)庫中的索引檢驗(yàn)工作帶來了巨大的時間開銷。

同時，由圖5可以發(fā)現(xiàn)，LIRS算法由于完全沒有考慮到頻繁屬性因素，因此對于命中對比情況的比較較為平均，基本上不能夠支持以數(shù)據(jù)頻繁度為目標(biāo)的數(shù)據(jù)緩存策略。在FD-Apriori算法的支持下，隨著頻繁屬性的數(shù)量增多，命中情況有所提高。

此外，盡管兩屬性組緩存相比三屬性組緩存完全命中率相差較多，但其部分命中率高達(dá)63.93%。對于屬性組中屬性個數(shù)處于中間規(guī)模的緩存。盡管犧牲了一部分緩存完全命中率，但該類緩存能夠更出色地完成中間記錄的精簡工作，縮減內(nèi)存中因部分屬性命中而產(chǎn)生的中間結(jié)果集，并根據(jù)結(jié)果屬性索引快速定位數(shù)據(jù)，進(jìn)而減輕數(shù)據(jù)庫的檢索壓力，取得了更高的查詢效率。圖4中兩屬性組緩存平均查詢效率略高于三屬性組緩存正屬于這種情況。

4 結(jié) 語

本文提出了數(shù)據(jù)查詢過程中查詢頻繁度的概念以及基于Apriori算法的頻繁數(shù)據(jù)緩存策略。實(shí)驗(yàn)表明，本文的數(shù)據(jù)緩存策略能夠明顯提高頻繁區(qū)域中數(shù)據(jù)的查詢效率，而緩存數(shù)據(jù)中的屬性個數(shù)以及屬性分組情況則需要根據(jù)實(shí)際需求做出不同的調(diào)整。在進(jìn)一步的工作中，本研究將對內(nèi)存緩存中的存儲過程進(jìn)行優(yōu)化，減少稀疏數(shù)據(jù)結(jié)構(gòu)對有限空間的浪費(fèi)。

[1] Labrinidis A,Jagadish H V.Challenges and opportunities with big data[C]//Proceedings of the VLDB 2012.Istanbul,Turkey,2012:2032-2033.

[2] Bizer C,Boncz P,Brodie M L,et al.The meaningful use of big data:four perspectives-four challenges[J].Acm Sigmod Record,2011,40(4):56-60.

[3] Han J,Haihong E,Le G,et al.Survey on NoSQL database[C]//International Conference on Pervasive Computing and Applications.IEEE,2011:363-366.

[4] 申德榮,于戈,王習(xí)特,等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J].軟件學(xué)報,2013,24(8):1786-1803.

[5] Memcached Team.Memcached:A distributed memory object caching system[OL].[2015].http://memcached. org/.

[6] Chang F,Dean J,Ghemawat S,et al.Bigtable:a distributed storage system for structured data[J].Acm Transactions on Computer Systems,2008,26(2):205-218.

[7] Ananthanarayanan G,Ghodsi A,Wang A,et al.PACMan:coordinated memory caching for parallel jobs[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2012:20-20.

[8] GridGain Team.Gridgain:In-memory computing platform[OL].[2015].http://gridgain.com/.

[9] 許祥,羅宇.一種SAN環(huán)境下集群文件系統(tǒng)的元數(shù)據(jù)緩存研究[J].計算機(jī)研究與發(fā)展,2012,49(S1):240-244.

[10] 周功業(yè),吳偉杰,陳進(jìn)才.一種基于對象存儲系統(tǒng)的元數(shù)據(jù)緩存實(shí)現(xiàn)方法[J].計算機(jī)科學(xué),2007,34(10):146-148.

[11] 秦秀磊,張文博,魏峻,等.云計算環(huán)境下分布式緩存技術(shù)的現(xiàn)狀與挑戰(zhàn)[J].軟件學(xué)報,2013,24(1):50-66.

[12] 劉祖云,胡進(jìn)德.分布式共享存儲研究[J].成都大學(xué)學(xué)報(自然科學(xué)版),2008,27(1):45-47.

[13] 李文中,陳道蓄,陸桑璐.分布式緩存系統(tǒng)中一種優(yōu)化緩存部署的圖算法[J].軟件學(xué)報,2010,21(7):1524-1535.

[14] Agrawal R,Imielinski T,Swami A N.Mining Association Rules Between Sets of Items in Large Databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data,1993:207-216.

[15] Agrawal R,Srikant R.Fast alg orithms for mining asso-ciation rules[C]//Proceedings of the 20th VLDB Conference Santiago,Chile,1994:487-499.

[16] HBase:bigtablelike structured storage for hadoop hdfs[EB/OL].2010.http://Hadoop.apache.org/hbase/.

[17] Fan Chang,Jeffrey Dean,Sanjay Chemawat,et al.Bigtable:a distributed storage system for structured data[C]//Proceedings of 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI’06),Seattle,WA,USA:USENIX Association,2006:205-218.

FREQUENTDATACACHINGSTRATEGIESINDISTRIBUTEDENVIRONMENT

Yi Su1Yin Huiwen1Zhang Yichuan2Zhang Li2
1(InnovationandEntrepreneurshipCollege,LiaoningUniversity,Shenyang110036,Liaoning,China)2(CollegeofSoftware,NortheasternUniversity,Shenyang110819,Liaoning,China)

Using distributed caching technology can provide high performance and high availability data query in large data environment. The frequent data caching strategies for lightweight applications have the advantages of high efficiency and easy extension. Especially, it is beneficial to improve the query optimization for lightweight distributed database system. Therefore, this research studies the data caching strategies for the recent frequent query data by analyzing the characteristics of user behavior and user query. It can predict the high hit rate of the cache data and improve the efficiency of data query. Firstly, the definition of the frequency of the query was analyzed and given. Secondly, we refined the operation of the user's query according to the influence of the time factor for the cache data. And we dealt with the different cache hits in query process through the data query frequency. Then, we integrated the cached data between nodes. Finally, the experimental results showed that the data caching strategy has a high data hit rate. It also can improve the efficiency of data query. According to the actual needs, the implementation can use different combination of cache attributes, and possesses a good scalability.

Data caching strategy Query frequency Cluster environment Distributed system Big data

2016-11-23。國家自然科學(xué)基金項(xiàng)目(61202088)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(51704003)；遼寧省檔案局科技項(xiàng)目(L-2017-X-24)；遼寧省高校健康管理協(xié)同創(chuàng)新中心資助項(xiàng)目。易俗，實(shí)驗(yàn)師，主研領(lǐng)域：云計算，分布式計算。殷慧文，講師。張一川，講師。張莉，講師。

TP3

A

10.3969/j.issn.1000-386x.2017.08.003