方勝吉

摘 要 本文主要是對(duì)分布式存儲(chǔ)的存儲(chǔ)算法及分布式處理的核心算法的研究，分布式存儲(chǔ)究其本質(zhì)而言，主要就是通過(guò)分布式文件系統(tǒng)，把數(shù)量十分巨大的數(shù)據(jù)，存儲(chǔ)到零散的、不同的物理設(shè)備上的過(guò)程，而在這一過(guò)程當(dāng)中，采用不同的存儲(chǔ)方法和存儲(chǔ)結(jié)構(gòu)所得到的存儲(chǔ)效率是完全不同的，因此，對(duì)存儲(chǔ)方法的研究對(duì)海量存儲(chǔ)結(jié)構(gòu)的構(gòu)建有著十分重要的意義。

關(guān)鍵詞 分布式存儲(chǔ)；海量數(shù)據(jù)；存儲(chǔ)算法

中圖分類(lèi)號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2017）198-0142-02

1 常見(jiàn)的分布式存儲(chǔ)算法

1.1 NFS網(wǎng)絡(luò)文件系統(tǒng)

早期的分布式文件系統(tǒng)，多數(shù)都是基于NFS的[1]。NFS的設(shè)計(jì)，主要是對(duì)硬件和操作系統(tǒng)提供異構(gòu)支持，即容許不同操作系統(tǒng)的終端接入NFS系統(tǒng)，訪問(wèn)同一個(gè)共享存儲(chǔ)區(qū)，進(jìn)行文件的共享。它的適用范圍包括局域網(wǎng)和廣域網(wǎng)，而且NFS還形成了Internet標(biāo)準(zhǔn)-NFS協(xié)議。被大多數(shù)企業(yè)構(gòu)建局域網(wǎng)時(shí)所采用。

從結(jié)構(gòu)上看，其中要有一臺(tái)服務(wù)器和至少一臺(tái)的客戶端，服務(wù)器的功能比較復(fù)雜，主要用來(lái)存儲(chǔ)文件和目錄；客戶機(jī)的功能主要是對(duì)存儲(chǔ)在服務(wù)器上的數(shù)據(jù)進(jìn)行遠(yuǎn)程訪問(wèn)。當(dāng)服務(wù)器上保存的元數(shù)據(jù)非常龐大時(shí)，直接檢索效率極低，只能依賴CDN，但這并不能從本質(zhì)上解決問(wèn)題。所以當(dāng)網(wǎng)絡(luò)文件系統(tǒng)在存儲(chǔ)大量的龐大數(shù)據(jù)時(shí)，緩存成為了存儲(chǔ)的關(guān)鍵所在，而且，其擴(kuò)展性比較一般。

1.2 BigTab1e

與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)不同，BigTab1e是非關(guān)系型的，其本質(zhì)是分布式的、稀疏的、可持久化存儲(chǔ)的多維度排序Map。Bigtab1e是為了處理PB級(jí)別的數(shù)據(jù)而設(shè)計(jì)的。它具有廣泛的適用性，可擴(kuò)展能力強(qiáng)，具有高性能和高可用特性。

從實(shí)現(xiàn)策略的層面來(lái)講，BitTab1e與數(shù)據(jù)庫(kù)更加接近，但對(duì)于數(shù)據(jù)庫(kù)的一些高級(jí)操作它是不支持的，比如SQL中的關(guān)聯(lián)操作。但它對(duì)大數(shù)據(jù)的處理是很擅長(zhǎng)的，而且容錯(cuò)性和管理性也極為強(qiáng)大，它可以用多級(jí)映射的方式來(lái)解決數(shù)據(jù)操作問(wèn)題。

它以一種開(kāi)放模式提供給客戶簡(jiǎn)單的數(shù)據(jù)模型，對(duì)數(shù)據(jù)分布策略的設(shè)計(jì)以及對(duì)數(shù)據(jù)結(jié)構(gòu)的構(gòu)建都相當(dāng)?shù)淖杂?。BigTab1e對(duì)功能的要求也很簡(jiǎn)單，就是能夠存儲(chǔ)數(shù)據(jù)，并完善相應(yīng)的技術(shù)，保證數(shù)據(jù)安全就可以了，至于更加復(fù)雜的工作，比如確保數(shù)據(jù)正確，則交由上層應(yīng)用系統(tǒng)來(lái)完成。它也采用Master/Slave的架構(gòu)，一臺(tái)Master服務(wù)器，管理多個(gè)Tab1et的機(jī)器。在Master上主要完成的工作就是把Ta1bets分配給相應(yīng)的服務(wù)器，同時(shí)還要對(duì)Tab1et服務(wù)器的數(shù)量進(jìn)行動(dòng)態(tài)的查詢，控制其數(shù)量在一個(gè)閾值范圍內(nèi)，還要有一項(xiàng)重要的工作就是要平衡服務(wù)器的負(fù)載，并對(duì)分布式文件系統(tǒng)上的垃圾文件進(jìn)行處理。之外，還需要對(duì)數(shù)據(jù)模式相關(guān)的操作，進(jìn)行修改和處理。每個(gè)Tab1et server基本都會(huì)管理著數(shù)十至數(shù)千個(gè)數(shù)量不等的客戶端，負(fù)責(zé)對(duì)其中的讀和寫(xiě)操作進(jìn)行處理，如果數(shù)據(jù)量太大時(shí)，對(duì)要把它分割成小塊?？蛻舳俗x數(shù)據(jù)，將跳過(guò)Master，直通Tab1et Server。因此，在實(shí)際應(yīng)用中，Master服務(wù)器的負(fù)載并不重。最初的一個(gè)表單會(huì)伴隨著其中數(shù)據(jù)的不斷積增而被分割成不同的小塊Tab1et，但是Tab1et的大小又不能沒(méi)有限制，一般情況下，都在100～200MB左右。

2 分布式處理算法

Google公司的MapReduc分布處理算法，是當(dāng)今世界上最主流的分布式處理算法，MapReduce的根本的設(shè)計(jì)理念是大變小[3]；也就是說(shuō)將一個(gè)巨大的任務(wù)塊，按照一定的規(guī)則進(jìn)行分解，使其成為若干小任務(wù)塊，然后對(duì)其分別進(jìn)行并行處理，之后再把想要的最后的結(jié)果合并起來(lái)。MapReduce的數(shù)據(jù)處理格式采用結(jié)構(gòu)。用戶通過(guò)Map函數(shù)處理原始數(shù)據(jù)，通過(guò)Combine得出中間結(jié)果，用Reduce將所有具有相同中間Key值的中間結(jié)果Value值合并在一起得到最終結(jié)果。MapReduce可以運(yùn)行在低端的廉價(jià)PC機(jī)構(gòu)成的集群上，但是MapReduce能夠利用集群的整體性能完成超級(jí)計(jì)算，在性價(jià)比上還高于超級(jí)計(jì)算機(jī)。

Map Reduce 的操作流程如下[2]：

1）Map過(guò)程：MapReduce主要是為了實(shí)現(xiàn)并行處理，在任務(wù)開(kāi)始時(shí)，首先是將輸入文件分割成M個(gè)片段，片段的數(shù)量M根據(jù)Map的多少而定，在分割的過(guò)程中，不用考慮文件的類(lèi)型，分割的方法也可以自己定義。分割后，會(huì)形成M個(gè)片段，這M個(gè)片段會(huì)被分配到對(duì)應(yīng)的Task Tracker任務(wù)。由工作Tracker進(jìn)行統(tǒng)一的處理，通過(guò)心跳信號(hào)獲取每個(gè)TaskTr acker任務(wù)的狀態(tài)，從而取得每個(gè)片段處理的狀態(tài)。當(dāng)一個(gè)“分解（Map）”任務(wù)啟動(dòng)后，會(huì)創(chuàng)建一個(gè)新的“寫(xiě)對(duì)象（Writer）”，對(duì)應(yīng)到相應(yīng)的“規(guī)約（Reduce）”任務(wù)。 在指定的InputFormat里面會(huì)為Writer對(duì)象提供一個(gè)RecordReader用來(lái)讀取它的文件分割體； 同時(shí)，對(duì)輸入文件的分析、鍵值對(duì)的生成以及文件分割體邊緣的處理也都有InputFormat類(lèi)來(lái)完成。RecordReader讀取鍵值對(duì)后，傳遞給Mapper，它是由用戶自己完成的配置，在這種情況下，用戶對(duì)鍵值對(duì)的操作沒(méi)有任何的約束，接下來(lái)，通過(guò)OutputCollector.collect方法，就可以對(duì)用戶收集其自定義的鍵值對(duì)。結(jié)果的輸出，需要用兩個(gè)類(lèi)，即一個(gè)Key類(lèi)，另外一個(gè)是Value類(lèi)。鍵值對(duì)被收集后，我們要用到另外的一個(gè)類(lèi)—Partitioner，通過(guò)它給鍵值對(duì)指定一種區(qū)分方式，之后才能寫(xiě)入文件。為了使后續(xù)的規(guī)約任務(wù)能夠負(fù)載均衡，我們還要配置一個(gè)有效的哈希函數(shù)。每個(gè)輸出文件以及從Map任務(wù)中產(chǎn)生的鍵值，都會(huì)被送到其對(duì)應(yīng)的Reduce里，在指定的Reduce任務(wù)中會(huì)對(duì)指定Key的所有鍵值進(jìn)行處理。

2）Combine過(guò)程：通常，Map后的中間結(jié)果將會(huì)被送入內(nèi)存，在這里，為了提高Reduce的效率，我們?cè)O(shè)置了一個(gè)Combiner類(lèi)，Combiner會(huì)收集Map的中間結(jié)果并形成1ist列表，每一類(lèi)Key值對(duì)應(yīng)一個(gè)1ist列表，當(dāng)列表中的鍵值對(duì)達(dá)到一定數(shù)量后，相同Key值的Value就會(huì)被送入合成器Reduce方法中。

3）Reduce過(guò)程：當(dāng)Reduce獲取了間接數(shù)據(jù)結(jié)果后，就要對(duì)其按照關(guān)鍵字（即Key值）進(jìn)行排序，把同一關(guān)鍵字的值的數(shù)據(jù)排列在同一處。在Reduce過(guò)程中不同的關(guān)鍵值會(huì)映射到同一Reduce，所以對(duì)關(guān)鍵字的排序是必要的。Reduce對(duì)排序后的中間數(shù)據(jù)進(jìn)行遍歷，取得每個(gè)唯一Key值， 然后將這個(gè)Key值和它相關(guān)的Value值形成集合，最后按照用戶給定的操作輸出。

3 結(jié)論

本文主要介紹了如NFS、BigTable等常見(jiàn)的分布式存儲(chǔ)算法，又以MapReduce為例，表述了分布式存儲(chǔ)的核心處理算法。通過(guò)對(duì)分布式存儲(chǔ)及處理算法的分析，為設(shè)計(jì)海量數(shù)據(jù)存儲(chǔ)模型提供參考依據(jù)。

參考文獻(xiàn)

[1]王鵬，孟丹，詹劍鋒，等。數(shù)據(jù)密集型計(jì)算編程模式研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2010，47（11）：1993-2002.

[2]李波.基于Hadoop的海量圖像數(shù)據(jù)管理[D].上海：華東師范大學(xué)，2011.

[3]霍樹(shù)民.基于Hadoop的海里影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2010.