張淼波

摘要：該文對(duì)現(xiàn)行云存儲(chǔ)數(shù)據(jù)中心或大規(guī)模數(shù)據(jù)中心的存儲(chǔ)管理儲(chǔ)系統(tǒng)，從提高數(shù)據(jù)訪問效率的角度淺析如何優(yōu)化訪問策略的問題；以現(xiàn)行云存儲(chǔ)數(shù)據(jù)中心存儲(chǔ)管理方案為基礎(chǔ)，詳細(xì)描述和分析目前較為流行的兩種數(shù)據(jù)存儲(chǔ)管理方案：數(shù)據(jù)冗余策略和糾刪碼策略的優(yōu)劣勢，提出了一種根據(jù)數(shù)據(jù)訪問“冷熱度”，建立冷熱數(shù)據(jù)統(tǒng)計(jì)模型、分析模型、冷熱數(shù)據(jù)的分離模型，建立基于冷熱數(shù)據(jù)震蕩緩沖層的冗余策略變更模型，從而達(dá)到改進(jìn)數(shù)據(jù)存儲(chǔ)管理方案的新構(gòu)想。

關(guān)鍵詞：冗余策略；副本；糾刪碼；伸展樹；數(shù)據(jù)冷熱度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）26-0005-02

云計(jì)算中心是我國十三五重點(diǎn)扶持領(lǐng)域，在整個(gè)“十二五規(guī)劃”期間，我國的云計(jì)算領(lǐng)域的產(chǎn)業(yè)鏈規(guī)模將達(dá)到7500-10000億元人民幣。云計(jì)算的崛起使得數(shù)據(jù)越來越集中，在眾多場合，云計(jì)算和大數(shù)據(jù)的概念通常緊密聯(lián)系在一起，數(shù)據(jù)越來越大，使得數(shù)據(jù)中心需要面對(duì)一個(gè)極其重要的挑戰(zhàn)：對(duì)大數(shù)據(jù)的安全、高效的管理。IDC數(shù)字宇宙研究指出，全球的數(shù)據(jù)量每兩年翻一番。2015年創(chuàng)建和復(fù)制的數(shù)據(jù)量為8.6ZB。預(yù)計(jì)到2020年將達(dá)到44ZB。這要求數(shù)據(jù)中心能夠同時(shí)滿足大數(shù)據(jù)的存儲(chǔ)規(guī)模，以及數(shù)據(jù)安全可靠性和可用性的要求。

現(xiàn)行云存儲(chǔ)系統(tǒng)中數(shù)據(jù)冗余是保證系統(tǒng)可靠性、提高數(shù)據(jù)可用性和持久性最基本的方法，目前，云存儲(chǔ)系統(tǒng)廣泛使用的冗余策略分為副本和糾刪碼[1]兩種，兩種策略的優(yōu)缺點(diǎn)都非常明顯。

1 副本和糾刪碼簡介

文本副本中的節(jié)點(diǎn)，最簡單的數(shù)據(jù)就是獲取該文件。由于副本不涉及冗余策略，通過將文件的多個(gè)副本原理，通過將文件的多個(gè)副本分布到系統(tǒng)不同節(jié)點(diǎn)，只要這些節(jié)點(diǎn)中的一個(gè)副本有效，數(shù)據(jù)的可用性越好，就能獲取該文件的編碼運(yùn)算。文件的副本越多，數(shù)據(jù)的可用性越好，可靠性越高。文件讀取和創(chuàng)建需要解碼和編碼操作，讀寫效率高。

糾刪碼是另一種重要的冗余策略，將這K塊文件編碼成N個(gè)編碼（N，K），糾刪碼將一個(gè)大小為M的原始文件分成K塊，其中每個(gè)存儲(chǔ)節(jié)點(diǎn)存儲(chǔ)一個(gè)編碼塊，每塊大小為M /K；然后塊后分發(fā)到N個(gè)節(jié)點(diǎn)中去，且N>K。（N，K）糾刪碼指的是N編碼中的任意K個(gè)編碼塊就能重構(gòu)原文件。

2 副本和糾刪碼的比較

相關(guān)文獻(xiàn)對(duì)兩種冗余策略進(jìn)行比較，得出在不同情況下，兩種策略各有各的優(yōu)勢。副本冗余方式響應(yīng)速度快，冗余方式簡單，但極大地浪費(fèi)存儲(chǔ)資源。特別是在規(guī)模龐大的云存儲(chǔ)中心，勢必會(huì)增加系統(tǒng)的投入成本，例如常見的3副本策略，使得存儲(chǔ)系統(tǒng)的存儲(chǔ)資源利用率最高也只能達(dá)到30%左右；糾刪碼方式雖然能夠節(jié)省存儲(chǔ)空間，提高存儲(chǔ)利用率，但是糾刪碼分片冗余機(jī)制也有其自身的局限性。首先，對(duì)數(shù)據(jù)分片及解碼算法的引入將增加系統(tǒng)設(shè)計(jì)的復(fù)雜度。其次，糾刪碼分片冗余機(jī)制要求用戶必須從網(wǎng)絡(luò)的多個(gè)節(jié)點(diǎn)中獲得多個(gè)分片才可以恢復(fù)原始數(shù)據(jù)，若在互聯(lián)網(wǎng)環(huán)境中，由于地理位置等因素，用戶到多個(gè)節(jié)點(diǎn)的時(shí)延各有差異，這樣獲取數(shù)據(jù)的最終時(shí)延總是取決于各節(jié)點(diǎn)中的最大者，導(dǎo)致數(shù)據(jù)下載率降低。

3 冷熱數(shù)據(jù)與冗余策略

對(duì)云存儲(chǔ)系統(tǒng)中數(shù)據(jù)訪問特性的統(tǒng)計(jì)分析發(fā)現(xiàn)，文件訪問集中在文件創(chuàng)建時(shí)的時(shí)間段，并且滿足于Zipf分布規(guī)律[2]，呈現(xiàn)出“局部性”的特點(diǎn)，即大量的訪問集中在小部分?jǐn)?shù)據(jù)之上。

3.1 冷熱數(shù)據(jù)的分級(jí)存儲(chǔ)

虛擬內(nèi)存的冷熱數(shù)據(jù)的分級(jí)最早的原型是頁面置換算法[3]，頁面置換算法最近最久未使用置換算法，頁面置換算法是一種典型的兩級(jí)存儲(chǔ)模型，包括先進(jìn)先出置換算法，最近未用置換算法。頁面置換算法的核心是選擇哪些永不使用的，這個(gè)思想在最長時(shí)間內(nèi)不在被訪問的頁面，反映了對(duì)頁面重要性的基本評(píng)價(jià)標(biāo)準(zhǔn)或者是轉(zhuǎn)換出云。 數(shù)據(jù)是否被訪問，一直延用當(dāng)前這種思想轉(zhuǎn)型為分級(jí)存儲(chǔ)算法。

3.2 冷熱數(shù)據(jù)的判定

3.2.1 固定閥值法

將數(shù)據(jù)遷移到固定閥值法，基本思想是在一段時(shí)間內(nèi)，當(dāng)數(shù)據(jù)存放在高級(jí)存儲(chǔ)設(shè)備中設(shè)定一個(gè)固定的訪問頻度閥值對(duì)數(shù)據(jù)進(jìn)行分級(jí)，否則不遷移數(shù)據(jù)；首先統(tǒng)計(jì)一段時(shí)間內(nèi)所有數(shù)據(jù)的訪問頻度，并且訪問頻度大于閥值，（速度快容量?。?，如果（速度慢容量大）數(shù)據(jù)存放在低級(jí)存儲(chǔ)設(shè)備中，并且訪問頻度小于閥值，低級(jí)存儲(chǔ)設(shè)備，將數(shù)據(jù)遷移到高級(jí)存儲(chǔ)設(shè)備，否則不遷移數(shù)據(jù)。

3.2.2 高低水位法

設(shè)定存儲(chǔ)設(shè)備總?cè)萘扛叩退环ǖ幕舅枷胧遣捎米罡甙俜直群妥畹桶俜直龋瑢?shù)據(jù)向低級(jí)存儲(chǔ)設(shè)備遷移，遷移數(shù)據(jù)的選擇根據(jù)是從上一次遷移開始將這兩個(gè)百分比稱之為存儲(chǔ)高水位和低水位。當(dāng)高級(jí)存儲(chǔ)設(shè)備中的數(shù)據(jù)最達(dá)到高水位時(shí)，直到數(shù)據(jù)量達(dá)到低水位時(shí)停止。由低到高依次遷移到低級(jí)存儲(chǔ)設(shè)備。由于數(shù)據(jù)量快速增長，當(dāng)前的訪問頻度統(tǒng)計(jì)值，高低水位法強(qiáng)調(diào)解決，導(dǎo)致高級(jí)存儲(chǔ)設(shè)備容量不足問題的算法。

分級(jí)存儲(chǔ)系統(tǒng)中，根據(jù)數(shù)據(jù)的不同重要性、數(shù)據(jù)的訪問頻率、存儲(chǔ)成本等因素，分別存儲(chǔ)在相應(yīng)的設(shè)備上，由信息生命周期理論可知，數(shù)據(jù)信息在不同地域、不同時(shí)間、不同應(yīng)用環(huán)境中其價(jià)值也不相同，因此，不同情況下同一類數(shù)據(jù)要在存儲(chǔ)系統(tǒng)的不同等級(jí)存儲(chǔ)設(shè)備之間流動(dòng)；典型的數(shù)據(jù)遷移算法主要有三種[4]：基于存儲(chǔ)空間的高低水位法，基于數(shù)據(jù)訪問頻率的Cache替換法和信息生命周期管理（ILM）中的價(jià)值評(píng)估法。

3.3 針對(duì)云存儲(chǔ)系統(tǒng)中數(shù)據(jù)的“局部性”特征，我們可以進(jìn)一步探求冷熱數(shù)據(jù)的分離機(jī)制，建立更科學(xué)、合理的存儲(chǔ)策略

3.3.1 建立熱度統(tǒng)計(jì)和分析模型

在存儲(chǔ)系統(tǒng)中，熱點(diǎn)數(shù)據(jù)被分為兩在類：永久性熱（Permanent Hotspor）和階段性熱（Stage Hotspot）。其中階段性熱點(diǎn)還可以繼續(xù)分成兩小類：周期性熱點(diǎn)（Cyclical Hotspot）和突發(fā)性熱點(diǎn)（Sudden Hotspot）。如果某個(gè)數(shù)據(jù)一直都被頻繁地訪問，則稱為“永久性熱點(diǎn)”，如圖1（a）所示。周期性熱點(diǎn)是一個(gè)數(shù)據(jù)對(duì)像周期性地被頻繁訪問，如圖1（b）所示。如果一個(gè)數(shù)據(jù)對(duì)象從默默無聞突然變成數(shù)據(jù)訪問的焦點(diǎn)，則將其稱為“突發(fā)性熱點(diǎn)” 如圖1（c）所示。

熱度統(tǒng)計(jì)和分析模型需要根據(jù)數(shù)據(jù)的訪問頻率、數(shù)據(jù)大小、創(chuàng)建時(shí)間、熱點(diǎn)訪問、重要性等參考信息進(jìn)行設(shè)計(jì)，對(duì)于熱點(diǎn)數(shù)據(jù)需要建立一套識(shí)別和評(píng)價(jià)方法，在構(gòu)建分析模型時(shí)應(yīng)區(qū)分永久性熱點(diǎn)、周期性熱點(diǎn)和突發(fā)性熱點(diǎn)等問題

3.3.2 建立基于伸展樹的冷熱數(shù)據(jù)分離模型

伸展樹（splay tree）是一種能夠根據(jù)訪問請求變化動(dòng)態(tài)調(diào)整其自身結(jié)構(gòu)的二叉搜索樹（BST）。采用伸展樹（splay tree）方式對(duì)元數(shù)據(jù)進(jìn)行有效的索引組織，伸展樹是能夠根據(jù)訪問請求變化動(dòng)態(tài)調(diào)整其自身結(jié)構(gòu)的二叉搜索樹。對(duì)于提升熱點(diǎn)數(shù)據(jù)節(jié)點(diǎn)的訪問性能，伸展樹是一種很理想的數(shù)據(jù)結(jié)構(gòu)。最近最多被訪問的節(jié)點(diǎn)一直位于根節(jié)點(diǎn)的附近，從而將縮短再次被訪問時(shí)的搜索路徑長度。通過伸展樹的這一特性，可以使用伸展樹實(shí)現(xiàn)冷熱數(shù)據(jù)的分離。

3.3.3 建立基于冷熱數(shù)據(jù)震蕩緩沖層的冗余策略變更模型

在對(duì)索引緩存進(jìn)行自適應(yīng)調(diào)整實(shí)現(xiàn)冷熱數(shù)據(jù)的調(diào)整之后，需要對(duì)元數(shù)據(jù)索引指向的數(shù)據(jù)進(jìn)行冗余策略變更操作，采用某種冷熱度數(shù)判定方法（固定閥值法或高低水位法），當(dāng)系統(tǒng)出現(xiàn)突發(fā)性熱點(diǎn)事件時(shí)，在臨界點(diǎn)將產(chǎn)生冷熱震蕩的數(shù)據(jù)，其冗余方式的變更將出現(xiàn)“搖擺”現(xiàn)象，頻繁的冗余策略變更會(huì)極大的消耗系統(tǒng)資源。

此時(shí)我們應(yīng)當(dāng)考慮通過設(shè)置冷熱震蕩緩沖層，采用延遲變更冗余策略的方式來防止該現(xiàn)象的產(chǎn)生，在基于冷熱數(shù)據(jù)震蕩緩沖層的模型中有兩個(gè)關(guān)鍵問題也需要解決，一個(gè)是冷數(shù)據(jù)、熱數(shù)據(jù)以及緩沖帶數(shù)據(jù)的比例，另一個(gè)是冗余策略變更時(shí)間點(diǎn)的選擇。

4 結(jié)束語

大量研究已對(duì)副本和糾刪碼冗余策略在分布式系統(tǒng)中的應(yīng)用做了對(duì)比分析，指出了副本和糾刪碼在存儲(chǔ)系統(tǒng)可靠性和可用性方面的特點(diǎn)。本文采用原型系統(tǒng)Swift所提供的副本和糾刪碼兩種冗余策略方式，因此只需對(duì)數(shù)據(jù)的訪問熱度進(jìn)行統(tǒng)計(jì)分析，建立冷熱數(shù)據(jù)分離模型和冗余策略模型，如若采取理論與實(shí)驗(yàn)相結(jié)合的方法，即可驗(yàn)證理論的可行性，從而實(shí)現(xiàn)對(duì)云存儲(chǔ)數(shù)據(jù)中心存儲(chǔ)系統(tǒng)管理的優(yōu)化。

參考文獻(xiàn)：

[1] AJoseph.O.Sullivan.and L.Xu. coding for High-Density Storage System.Technical report.Network and Information System lab.Washington University Saint Louis.Feb，2004.

[3] 昌帥，高光明，徐凱，等.海量信息分級(jí)存儲(chǔ)數(shù)據(jù)遷移策略研究[J].計(jì)算機(jī)工程與科學(xué)，2009，31（A01）：163-167

[4] 王艷云，邊根慶，王瑞龍.數(shù)據(jù)遷移算法研究[J].電腦知識(shí)與技術(shù)（學(xué)術(shù)交流），2012，8（5）：2968-2970.

[通聯(lián)編輯：光文玲]