“分布式”存儲結構存儲方法研究

方勝吉

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

關鍵詞 分布式存儲；海量數據；存儲算法

中圖分類號 TP3 文獻標識碼 A 文章編號 1674-6708（2017）198-0142-02

1 常見的分布式存儲算法

1.1 NFS網絡文件系統

早期的分布式文件系統，多數都是基于NFS的[1]。NFS的設計，主要是對硬件和操作系統提供異構支持，即容許不同操作系統的終端接入NFS系統，訪問同一個共享存儲區，進行文件的共享。它的適用范圍包括局域網和廣域網，而且NFS還形成了Internet標準-NFS協議。被大多數企業構建局域網時所采用。

從結構上看，其中要有一臺服務器和至少一臺的客戶端，服務器的功能比較復雜，主要用來存儲文件和目錄；客戶機的功能主要是對存儲在服務器上的數據進行遠程訪問。當服務器上保存的元數據非常龐大時，直接檢索效率極低，只能依賴CDN，但這并不能從本質上解決問題。所以當網絡文件系統在存儲大量的龐大數據時，緩存成為了存儲的關鍵所在，而且，其擴展性比較一般。

1.2 BigTab1e

與傳統的關系型數據庫不同，BigTab1e是非關系型的，其本質是分布式的、稀疏的、可持久化存儲的多維度排序Map。Bigtab1e是為了處理PB級別的數據而設計的。它具有廣泛的適用性，可擴展能力強，具有高性能和高可用特性。

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

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

2 分布式處理算法

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

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

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

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

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

3 結論

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

參考文獻

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

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

[3]霍樹民.基于Hadoop的海里影像數據管理關鍵技術研究[D].長沙：國防科學技術大學，2010.