HDFS 副本放置策略的研究和優化
云存儲作為云計算的延伸和發展，在實際生產環境中越來越受到關注。其中 Hadoop 分布式文件系統 (HDFS) 就被廣泛地應用于各種場景中。而如果能優化其使用的一些策略，則能大大提高生產效率。本文就是通過對 HDFS 默認的基于機架敏感的副本放置策略進行研究和優化，提出更具高效的基于用戶信息和負載的副本放置策略 (UILBPS，Placement Strategy based on User Information and Load Balance)，充分考慮了節點負載情況和用戶歷史訪問的地域特征，提高了系統的性能并均衡了系統負載，降低了用戶的訪問延遲，提高了數據的可用性。
云計算
云計算(cloud computing)是基于互聯網的相關服務的增加、使用和交付模式，通常涉及通過互聯網來提供動態易擴展且經常是虛擬化的資源。云是網絡、互聯網的一種比喻說法。過去在圖中往往用云來表示電信網，后來也用來表示互聯網和底層基礎設施的抽象。因此，云計算甚至可以讓你體驗每秒 10 萬億次的運算能力，擁有這么強大的計算能力可以模擬核爆炸、預測氣候變化和市場發展趨勢。用戶通過電腦、筆記本、手機等方式接入數據中心，按自己的需求進行運算。
按照美國國家標準與技術研究院(NIST)定義：云計算是一種按使用量付費的模式，這種模式提供可用的、便捷的、按需的網絡訪問，進入可配置的計算資源共享池(資源包括網絡、服務器、存儲、應用軟件、服務)，這些資源能夠被快速提供，只需投入很少的管理工作，或與服務供應商進行很少的交互。
云計算是分布式計算(Distributed Computing)、并行計算(Parallel Computing)、效用計算(Utility Computing)、網絡存儲(Network Storage Technologies)、虛擬化(Virtualization)、負載均衡(Load Balance)、熱備份冗余(High Available)等傳統計算機和網絡技術發展融合的產物。
云計算可以認為包括以下幾個層次的服務：基礎設施即服務(IaaS)，平臺即服務(PaaS)和軟件即服務(SaaS)。
云存儲
云存儲是在云計算概念上延伸和發展出來的一個新的概念，是指通過集群應用、網格技術或分布式文件系統等功能，將網絡中大量各種不同類型的存儲設備通過應用軟件集合起來協同工作，共同對外提供數據存儲和業務訪問功能的一個系統。當云計算系統運算和處理的核心是大量數據的存儲和管理時，云計算系統中就需要配置大量的存儲設備，那么云計算系統就轉變成為一個云存儲系統，所以云存儲是一個以數據存儲和管理為核心的云計算系統。簡單來說，云存儲就是將儲存資源放到云上供人存取的一種新興方案。使用者可以在任何時間、任何地方，通過任何可連網的裝置連接到云上方便地存取數據。
云存儲系統的結構模型由 4 層組成。
存儲層
存儲層是云存儲最基礎的部分。存儲設備可以是 FC 光纖通道存儲設備，可以是 NAS 和 iSCSI 等 IP 存儲設備，也可以是 SCSI 或 SAS 等 DAS 存儲設備。云存儲中的存儲設備往往數量龐大且分布在多種不同地域，彼此之間通過廣域網、互聯網或者 FC 光纖通道網絡連接在一起。
存儲設備之上是一個統一存儲設備管理系統，可以實現存儲設備的邏輯虛擬化管理、多鏈路冗余管理，以及硬件設備的狀態監控和故障維護。
基礎管理
基礎管理層是云存儲最核心的部分，也是云存儲中最難以實現的部分。基礎管理層通過集群、分布式文件系統和網格計算等技術，實現云存儲中多個存儲設備之間的協同工作，使多個的存儲設備可以對外提供同一種服務，并提供更大更強更好的數據訪問性能。
應用接口
應用接口層是云存儲最靈活多變的部分。不同的云存儲運營單位可以根據實際業務類型，開發不同的應用服務接口，提供不同的應用服務。比如視頻監控應用平臺、IPTV 和視頻點播應用平臺、網絡硬盤引用平臺，遠程數據備份應用平臺等。
訪問層
任何一個授權用戶都可以通過標準的公用應用接口來登錄云存儲系統，享受云存儲服務。云存儲運營單位不同，云存儲提供的訪問類型和訪問手段也不同。
HDFS
Hadoop 分布式文件系統 (HDFS) 被設計成適合運行在通用硬件 (commodity hardware) 上的分布式文件系統。它和現有的分布式文件系統有很多共同點。但同時，它和其他的分布式文件系統的區別也是很明顯的。HDFS 是一個高度容錯性的系統，適合部署在廉價的機器上。HDFS 能提供高吞吐量的數據訪問，非常適合大規模數據集上的應用。HDFS 放寬了一部分可移植操作系統接口 (POSIX) 約束，來實現流式讀取文件系統數據的目的。HDFS 在最開始是作為 Apache Nutch 搜索引擎項目的基礎架構而開發的。HDFS 是 Apache Hadoop Core 項目的一部分。
以下是本文對 HDFS 及其副本放置策略的具體介紹說明。
副本技術
副本技術即分布式數據復制技術，是分布式計算的一個重要組成部分。該技術允許數據在多個服務器端共享，一個本地服務器可以存取不同物理地點的遠程服務器上的數據，也可以使所有的服務器均持有數據的拷貝。
通過副本技術可以有以下優點：
- 提高系統可靠性：系統不可避免的會產生故障和錯誤，擁有多個副本的文件系統不會導致無法訪問的情況，從而提高了系統的可用性。另外，系統可以通過其他完好的副本對發生錯誤的副本進行修復，從而提高了系統的容錯性。
- 負載均衡：副本可以對系統的負載量進行擴展。多個副本存放在不同的服務器上，可有效的分擔工作量，從而將較大的工作量有效的分布在不同的站點上。
- 提高訪問效率：將副本創建在訪問頻度較大的區域，即副本在訪問節點的附近，相應減小了其通信開銷，從而提高了整體的訪問效率。
#p#
HDFS 架構
圖 1. HDFS 架構圖
HDFS 是一個主從結構，一個 HDFS 集群有一個名字節點，它是一個管理文件命名空間和調節客戶端訪問文件的主服務器，當然還有一些數據節點，通常是一個節點一個機器，它來管理對應節點的存儲。HDFS 對外開放文件命名空間并允許用戶數據以文件形式存儲。
內部機制是將一個文件分割成一個或多個塊，這些塊被存儲在一組數據節點中。名字節點用來操作文件命名空間的文件或目錄操作，如打開、關閉、重命名等等。它同時確定塊與數據節點的映射。數據節點來負責來自文件系統客戶的讀寫請求。數據節點同時還要執行塊的創建、刪除、和來自名字節點的塊復制指令。
集群中只有一個名字節點極大地簡單化了系統的體系結構。名字節點是仲裁者和所有 HDFS 元數據的倉庫，用戶的實際數據不經過名字節點。
數據復制
HDFS 設計成能可靠地在集群中大量機器之間存儲大量的文件，它以塊序列的形式存儲文件。文件中除了***一個塊，其他塊都有相同的大小。屬于文件的塊為了故障容錯而被復制。塊的大小和復制數是以文件為單位進行配置的，應用可以在文件創建時或者之后修改復制因子。HDFS 中的文件是一次寫的，并且任何時候都只有一個寫操作。
名字節點負責處理與所有的塊復制相關的決策。它周期性地接受集群中數據節點的心跳和塊報告。一個心跳的到達表示這個數據節點是正常的。一個塊報告包括該數據節點上所有塊的列表。
副本放置策略
塊副本存放位置的選擇嚴重影響 HDFS 的可靠性和性能。HDFS 采用機架敏感(rack awareness)的副本存放策略來提高數據的可靠性、可用性和網絡帶寬的利用率。
圖 2. 副本放置策略圖
HDFS 運行在跨越大量機架的集群之上。兩個不同機架上的節點是通過交換機實現通信的，在大多數情況下，相同機架上機器間的網絡帶寬優于在不同機架上的機器。
在開始的時候，每一個數據節點自檢它所屬的機架 id，然后在向名字節點注冊的時候告知它的機架 id。HDFS 提供接口以便很容易地掛載檢測機架標示的模塊。一個簡單但不是***的方式就是將副本放置在不同的機架上，這就防止了機架故障時數據的丟失，并且在讀數據的時候可以充分利用不同機架的帶寬。這個方式均勻地將復制分散在集群中，這就簡單地實現了組建故障時的負載均衡。然而這種方式增加了寫的成本，因為寫的時候需要跨越多個機架傳輸文件塊。
一般情況下復制因子(文件的副本數)為 3，HDFS 的副本放置策略是：將***個副本放在本地節點，將第二個副本放到本地機架上的另外一個節點，而將第三個副本放到不同機架上的節點。這種方式減少了機架間的寫流量，從而提高了寫的性能。機架故障的幾率遠小于節點故障。這種方式并不影響數據可靠性和可用性的限制，并且它確實減少了讀操作的網絡聚合帶寬，因為文件塊僅存在兩個不同的機架，而不是三個。文件的副本不是均勻地分布在機架當中，1/3 副本在同一個節點上，1/3 副本在同一個機架上，另外 1/3 副本均勻地分布在其他機架上。這種方式提高了寫的性能，并且不影響數據的可靠性和讀性能
圖 3. 副本放置策略源碼分析圖
#p#
HDFS 副本放置策略缺陷
HDFS 的默認副本放置策略是一個隨機選擇策略，副本放置的最終狀態很難被控制。其具體表現如下：
- 其是利用將副本放置在不同的機架上來達到高可靠性和數據塊的均勻分布存儲的，但如果數據中心只有一個機架，那么該副本放置策略就退化為一個隨機選擇策略，數據塊的均勻分布和可靠性就很難被保證。
- 其并沒有考慮到節點負載的情況，即使有一個節點的負載遠高于其他節點，按照默認的副本放置策略，這個節點還是有可能被持續的寫入數據。
- 其主要是對前三個副本的放置位置做出了考慮，如果需要放置更多的副本，則后面的副本放置會采用隨機選擇的策略。
當然在 HDFS 系統中也有個叫均衡器(Balancer)的守護進程。它會將數據塊從負載較高的節點移動到負載較低的節點上，從而達到數據塊重新分配的目的，最終使得整個集群分布均衡。雖然均衡器能在一定程度上解決問題，但是它也是存在缺陷的：
- 它對于集群數據塊均衡的調節具有滯后性。
- 均衡器的調節和數據塊的移動都需要一定資源的消耗。
因此，解決問題的關鍵是應該放在最初副本的放置上而不是事后去補救。這也就需要對 HDFS 的副本放置策略做出適當的優化。
HDFS 副本放置策略優化
根據上述所說的缺陷，本文提出了基于用戶信息和負載的副本放置策略 UILBPS(Placement Strategy based on User Information and Load Balance)。
基于 HDFS 的特性，在副本創建副本后的操作主要以讀取為主，即將負載均衡副本可用性和訪問速率作為副本放置策略的優化目標。其中，副本訪問速率性能受到副本節點負載的影響，尤其是 I/O 負載會成為訪問的瓶頸;副本所在節點的狀態也會對副本訪問產生一定的影響，并影響到之后的負載均衡上。另外，同一用戶所創建的副本，其副本訪問在地域上有一定的相似性。因此，UILBPS 將通過副本訪問特征的提取和節點負載的計算，解決副本初始創建階段的副本數量和副本放置位置的確定問題。
副本訪問特征提取
對用戶副本放置特征的提取主要借助用戶的歷史信息。對于一個有歷史信息的用戶來說，其創建的副本已有一定的訪問記錄。
我們定義副本訪問位置向量 cn_P 和訪問位置范圍 cn_cov 來提取副本訪問的特征。其中 cn_P 表示該副本被訪問的具體位置，cn_cov 表示訪問同一副本的客戶端(Client)的主要分布范圍。
對于有 k 條副本訪問位置記錄的數據塊 i，其 cn_cov 為其大于 q 條記錄所對應的最小位置范圍(q=0.8k)，若沒有這樣的范圍則 cn_cov 為全集。
提取過程如下：
- Client 隨機抽取用戶已創建的 n 個數據塊組成抽樣樣本集合。
- Client 向名字節點發送獲取集合 N 的副本個數信息和 cn_P 請求，獲得樣本副本個數集合和 cn_P 集合。
- Client 計算樣本集合中 n 個數據塊的副本平均值下界作為該次副本創建數量 rep_num。默認副本下界為 2，即至少有 2 個副本。
- Client 根據樣本的 cn_P 計算 cn_cov，并組成包含了 n 個副本位置范圍的集合 F={f1，f2，f3，……，fn}。
- Client 根據集合 F 來確定副本位置選擇集合 F'(F 子元素的并集)。
- Client 將 rep_num 和 F'發送給名字節點。
如下表所示，根據訪問節點的記錄，可以得出其訪問位置范圍為向量(0，86，0574)。
表 1. 訪問節點抽樣的樣本集合
節點負載
名字節點在獲得副本創建個數和副本位置選擇集合后，對處于副本位置選擇集合中的節點根據其負載情況，選擇 req_num 個負載低的節點進行副本放置。
其中節點負載越大表示磁盤越繁忙，已使用空間越多;越小表示磁盤空閑，已使用的空間越小。因此，通過考慮節點的負載情況，一方面可以避免因磁盤繁忙而導致數據塊寫操作的阻塞，從而導致系統性能的下降;一方面可以盡可能的使副本分布均衡，降低后續副本調整操作的壓力，節約系統資源。
因此以磁盤 I/O 負載和磁盤空間負載作為整個節點負載的主要影響因素。公式如下：
清單 1. 節點負載計算公式
LOAD=W1*IO + W2*SPACE
其中 W1 和 W2 是磁盤 I/O 負載和磁盤空間負載的權重值。
放置算法
圖 4. 副本創建流程圖
#p#
副本放置策略比較分析和思考
本節通過模擬數據，進行 HDFS 默認算法與 UILBPS 算法進行比較分析。初始化模擬系統中有 3 個大洲，5 個國家，10 個地區，10 個數據中心，20 個機架，200 個節點，20 個 Client，250 個數據及其 2~5 個副本。其中節點和 Client 隨機分布在各個不同的機架上，每個數據對象的副本也隨機分布在不同的節點上，且被 Client 訪問 10~20 次。不過同一 Client 的訪問節點有一定的相似性，保證訪問節點分布在一定的范圍。系統默認磁盤負載的權重值為 0.5。
下圖都是該模擬系統在重新創建 M 個數據對象后的比較：
圖 5. 負載分析圖
由上圖可見，在創建的數據對象 M 相同的情況下，UILBPS 的負載是明顯低于 HDFS 默認算法下的負載的，這正是因為考慮到了負載均衡的原因，盡可能的選擇那些負載較低的節點進行副本的放置的結果。
圖 6. 訪問速率分析圖
由上圖可見，在創建的數據對象 M 相同的情況下，UILBPS 的平均訪問距離是略小于 HDFS 默認算法下的負載的，這正是因為考慮到了用戶訪問特性的原因，使其 Client 能盡可能的訪問與其較近的節點，從而節約了網絡帶寬，減少了因網絡故障帶來的風險，加快了節點訪問的速率。
HDFS 的機架敏感放置策略對其副本放置的位置是隨機的，而 UILBPS 則是基于用戶歷史信息和負載的，充分考慮了節點負載情況和用戶歷史訪問的地域特征，從某種程度來說對機架敏感放置策略進行了優化，提高了系統的性能并均衡了系統負載，降低了用戶的訪問延遲，提高了數據的可用性。
因為 HDFS 系統將由數百或數千個存儲著文件數據片斷的服務器組成。實際上它里面有非常巨大的組成部分，每一個組成部分都很可能出現故障，這就意味著 HDFS 里的總是有一些部件是失效的，即硬件故障是常態，而不是異常。那么如何自動快速的恢復是 HDFS 一個很重要的目標。而對副本放置策略的優化則減少了系統負載，加快了副本的訪問速率，從而能將失效的部件盡快的恢復過來或者起到與原失效部件一樣的作用。
HDFS 有著高容錯性的特點，并且設計了用來部署在低廉的硬件上的特性。同時，用戶歷史信息和負載狀況都是通過名字節點來進行管理和計算。因此，優化中附加的信息并不會很大程度上占用 HDFS 所需要的磁盤空間，也不會產生因磁盤空間的減少而帶來的系統性能下降問題。
對于因數據節點失效，副本損壞，數據節點磁盤損壞或者文件的復制因子增大等原因而導致的后續副本的調整來說，較好的副本位置更有利于副本的創建、刪除和遷移，即更有利于后續的副本調整，保證了分布式系統的一致性、可用性、分區容錯性。
結束語
本文主要對 HDFS 中副本放置策略進行了研究分析，并根據其算法上的實現提出了疑問，然后提出了基于用戶歷史信息和負載的放置策略對其原本的策略做出了一定的優化。事實上，本文提出的優化算法也并不是說一定是***算法。哥倫比亞大學提出了一種自穩定的、全分布的、異步可升級的副本放置算法。加州大學伯克利分校開發設計了一個動態、高效及可升級的內容分發網絡 SCAN(sealableContentAccessNetwork)，使用了沿路緩存的算法進行副本放置。德克薩斯大學提出了一種協作的緩存放置算法等等。每種算法都有其優劣性，至于哪種算法***，則需要通過生產環境來驗證了。同時，整個 HDFS 系統乃至說 Hadoop 還是有很多值得研究、思考、優化和完善的地方。
原文鏈接：http://www.ibm.com/developerworks/cn/data/library/bd-1505-hdfs-uilbps-optimize/index.html
