方勝吉

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

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

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

1 常見的分布式存儲算法

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

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

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

1.2 BigTab1e

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

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

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

2 分布式處理算法

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

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

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

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