1.問題陳述
當前HDFS每個塊有3個副本是出于以下幾個方面的考慮：
1）預防DataNode的故障
2）對MapReduce本地性任務提供更好的支持
3）通過在多個副本間選擇讀取的塊，避免DataNodes節(jié)點的過載
????副本是昂貴的--在HDFS中默認的3副本機制有200%的存儲空間和其它的資源（比如：網(wǎng)絡帶寬）開銷。然而漩蟆，相對于低 I/O 活動的暖數(shù)據(jù)集和冷數(shù)據(jù)集霎褐，在正常的操作期間對其額外的副本很少訪問悼做，但是其仍然消耗與第一副本相同數(shù)量的資源入偷。因此嘹屯，一個自然的改進是使用糾刪碼（Erasure Coding）替代副本機制，它使用更少的存儲空間提供相同的容錯級別低葫，一個典型的糾刪碼設置详羡，會使得存儲空間的開銷不超過50% .
????HDFS歸檔存儲（HDFS?6584）也有類似的動機，它是為具有平衡性良好的主存儲資源和歸檔存儲資源設計的嘿悬；EC還優(yōu)化了同質(zhì)存儲體系結(jié)構(gòu)实柠，此外，可以在歸檔存儲之上使用EC節(jié)省多級存儲資源善涨。
????Facebook的解決方案是在HDFS之上構(gòu)建RAID層窒盐，這樣可以使開發(fā)變得容易，但是限制了它與HDFS內(nèi)核的交互钢拧，結(jié)果蟹漓，它將奇偶校驗數(shù)據(jù)存儲為用戶可見的文件，而不是塊源内，這樣很容易導致誤操作葡粒，此外，它不是HDFS中自帶的Feature膜钓，它依賴MySql保存元數(shù)據(jù)嗽交，使用MapReduce去創(chuàng)建校驗文件，RAID節(jié)點會周期性的查詢毀壞的文件呻此，增加了NameNode的負載轮纫。
2.使用案例
2.1.使用案例：節(jié)省 sealed / warm 數(shù)據(jù)空間
????在谷歌文件系統(tǒng)（GFS）和微軟的Azure存儲系統(tǒng)（WAS），數(shù)據(jù)集最初是3份的焚鲜，在一個文件或則塊被確定為“sealed”(不在修改)后掌唾，后臺任務對它編碼，之后刪除其余的副本忿磅，在HDFS 特定架構(gòu)糯彬、特性和負載下，下面的場景需要被考慮支持：
2.1.1.傾斜數(shù)據(jù)熱度
????HDFS承載多種的工作負載：從批量的MapReduce作業(yè)到交互式的葱她、延遲敏感的Impala和HBase查詢撩扒，因此我們應該允許用戶和管理員去指定（或者說暗示）文件的熱度。熱數(shù)據(jù)即便是 sealed 的吨些，也將保留副本搓谆，這樣讀客戶端可以選擇多個副本，避免負載過高的DataNode豪墅。
2.1.2.傾斜文件大小
????原始的GFS設計中一個很重要的假設是處理大文件泉手，隨著大數(shù)據(jù)負載能力的發(fā)展，這顯得不那么重要了偶器，像HBase和MapReduce這樣的應用軟件會生成很多小的和中等的文件斩萌，有些文件只有幾個塊缝裤，更有一些比單個塊還小，HDFS-EC應該能通用的處理各種分布類型的文件大小颊郎。
2.2.使用案例：高可用性和耐久性
????在當前的副本機制下憋飞，HDFS在離線和在線的情況下都能發(fā)現(xiàn)和修復塊錯誤，EC塊應該有相同級別的保護姆吭。
2.2.1.被動恢復（在讀路徑上）
????當讀取一個副本塊榛做，并且它的主副本不可用時，第二副本被用于服務請求内狸，塊也在后臺被重新復制瘤睹，每一個EC塊只有一個副本，當那個僅有的副本在讀取的時候不可用時答倡，EC機制應該能夠在延遲不高的情況下重構(gòu)丟失的塊從而繼續(xù)提供讀請求服務，恢復延遲對于像Impala這樣的高性能的查詢引擎是很至關(guān)重要的驴党，在服務讀請求之前去重構(gòu)整個丟失的塊是不能接受的瘪撇。
2.2.2.主動恢復（在后臺）
????HDFS NameNode從周期性的塊匯報中主動發(fā)現(xiàn)丟失的塊或者壞塊，副本塊的修復方式是通過拷貝健康的副本到一個新的DataNode港庄，這使得塊又恢復到之前的數(shù)量倔既；在EC情況下，原始的塊應該主動的判斷確保他們已經(jīng)準備好I/O鹏氧，校驗塊應該被類似的對待去維持容錯的能力渤涌。
2.3.使用案例：動態(tài)數(shù)據(jù)訪問模式
????一個文件的訪問模式可以被隨時的改變，當冷數(shù)據(jù)集變成熱數(shù)據(jù)時把还，HDFS應該重建它的其它副本用于快速的I/O訪問实蓬。
2.4.使用案例：在寫路徑上節(jié)省I/O帶寬
????當直接應用到寫路徑上時，EC會通過減少客戶端到存儲服務節(jié)點總的數(shù)據(jù)寫入數(shù)量來節(jié)省網(wǎng)絡和磁盤的帶寬吊履，QFS使用這種在線的方式安皱，注意：EC會在塊重構(gòu)的情況下使用比副本機制更多的I/O帶寬。
2.5.使用案例：利用多個磁盤主軸
????網(wǎng)絡帶寬的增長速度比磁盤的快很多艇炎，數(shù)據(jù)中心的存儲正變得扁平化酌伊，當EC使用小的編解碼單元（比如：在QFS中是64K），來自客戶端的單個的讀寫請求可以跨越多個存儲服務器缀踪，因此會利用它們的磁盤主軸的總帶寬居砖。
2.6.使用案例：地理分布式災難恢復
????地理位置的副本幫助數(shù)據(jù)集在可能使整個數(shù)據(jù)中心不可用的故障中幸存下來（HDFS?5442），這種更大的容錯會導致雙倍的存儲開銷驴娃，在默認的副本因子下奏候，同一個塊需要存本儲6個副，在這種情況下使用EC會節(jié)省大量的存儲空間和WAN帶寬托慨，F(xiàn)acebook的?f4 BLOB存儲系統(tǒng)使用跨3個站點的XOR來達到這一目標鼻由。
3.目標
3.1.節(jié)省大量的存儲空間
????基于我們已經(jīng)收集的用戶請求暇榴，節(jié)省存儲空間是用戶最重要的需求，在WAS中蕉世，EC目標的存儲開銷是33%蔼紧，而采用3副本方式的開銷是200%，對大文件和單一策略編碼 sealed 的數(shù)據(jù)狠轻，達到這個級別的空間的節(jié)省是很容易的奸例，我們的設計應該能高效的處理熱數(shù)據(jù)和小文件，因此向楼，在大多數(shù)工作負載下查吊，EC仍然可以顯著的節(jié)省存儲空間。
3.2.靈活性策略
????用戶和管理員應能標記文件是熱的或者冷的湖蜕，并且這些提示應該反映在EC的操作中逻卖，這個應該與HDFS歸檔存儲工作中的存儲策略進行集成，當前的存儲策略只能為塊的副本定義所需的存儲類型昭抒，EC需要擴展存儲策略來定義和實施分配模式评也。
????此外，當存儲使用接近配額時灭返，某些EC任務應該被標記為高優(yōu)先級/緊急優(yōu)先級用于支持釋放空間盗迟。
3.3.快速恢復/轉(zhuǎn)換
????我們應該使用本地重構(gòu)編碼（LRC）或者它的等同物去減少恢復使用的網(wǎng)絡傳輸，目前最先進的編解碼技術(shù)應是可插拔的熙含，比如：Jerasure,罚缕、Intel ISA庫等。
3.4.在寫路徑上節(jié)省IO帶寬
????在I/O密集型的工作負載下怎静，EC可以通過減少寫入系統(tǒng)的數(shù)據(jù)的數(shù)量來潛在的節(jié)省帶寬邮弹。
3.5.低開銷
????EC在NameNode上會不可避免的引入開銷以追蹤校驗塊，我們應該嘗試去最小化開銷蚓聘。
3.6.透明性/兼容性
HDFS用戶應該能夠去使用糾刪碼數(shù)據(jù)上所有基礎的或者高級的特性肠鲫，包括緩存、快照或粮、加密导饲、追加、截斷等等
4.非當前目標
以下特性是低優(yōu)先級的用戶需求氯材，考慮到它們的開發(fā)消耗渣锦，它們不包含在當前階段的范圍。
4.1.Geo-distributed?EC
????當完成geo-replication (HDFS-5442) 之后氢哮，我們應該重新關(guān)注這個話題滩报。
6.技術(shù)途徑
6.1.設計決策和體系架構(gòu)
6.1.1.EC和塊布局
????當前HDFS在單個DataNode上連續(xù)的存儲每一個塊副本岛杀，另外一個廣泛使用的布局是跨多個DataNodes存儲條帶數(shù)據(jù)甚纲，其中包括QFS,Colossus, Ceph, 和Lustre。原則上胀溺，塊布局（連續(xù)的VS條帶）和冗余方式（副本 VS 糾刪碼）是2個正交維度，會導致4中可能的組合在圖1中皆看。
????本文前面已經(jīng)討論了EC的優(yōu)缺點仓坞，另一方面，條帶方式利用并行的多磁盤主軸可以很大的增強順序I/O的性能腰吟，然而數(shù)據(jù)位置將作為代價丟失无埃；在EC的背景下，條帶布局有很多重要的優(yōu)點毛雇。首先嫉称，它能在線EC，這將繞過轉(zhuǎn)換階段灵疮，直接節(jié)省了存儲空間织阅，這在高端網(wǎng)絡的集群中非常的需要；其次震捣，它自然的分發(fā)小文件到多個DataNodes蒲稳，消除了將多個文件綁定到一個編碼組的需要，這會很大的簡化文件的操作伍派，比如刪除、配額匯報和在聯(lián)邦集群中不同的Namespace之間數(shù)據(jù)遷移等剩胁。
????在權(quán)衡考慮之后诉植，當前階段的目標是支持條帶的EC (Phase 1.1)，{EC+Striping} 和{Replication+Contiguous}表單之間的轉(zhuǎn)換(Phase 1.2)昵观，它導致了以下的設計決策：
????????1）編碼可以在線完成也可以離線完成晾腔。在離線編碼中，塊最初仍然采用復制的方式啊犬，當滿足指定條件時灼擂，轉(zhuǎn)換該塊為EC塊。
????????2）編解碼過程由客戶端和DataNode共同完成觉至，客戶端為最初的在線編碼計算校驗碼數(shù)據(jù)剔应，并在讀請求期間重構(gòu)丟失的原始數(shù)據(jù)；DataNode采用主動/后臺恢復方式構(gòu)建和存儲編碼的塊语御，并提供將副本模式轉(zhuǎn)換為EC的模式峻贮。
????????3）只有finalized狀態(tài)的文件才有資格轉(zhuǎn)換，在轉(zhuǎn)換期間是不支持追加寫的应闯。
6.1.2.系統(tǒng)架構(gòu)
????圖2闡明了提議設計的總體架構(gòu)纤控，添加的組件和邏輯被標記為藍色的，ECClient指示了HDFS客戶端的擴展碉纺，它將條帶數(shù)據(jù)往返于多個DataNodes船万，ECManager被放到了NameNode中刻撒，用于管理EC塊組，它的責任包括塊組的分配耿导、替換声怔、健康檢測、和協(xié)調(diào)恢復工作碎节。
????在正常的I/O操作期間捧搞，DataNodes對于EC或者條帶是無感知的，添加的ECWorker守護線程用于監(jiān)聽來之ECManager的恢復或者轉(zhuǎn)換命令狮荔，它通過從對等的DataNodes中拉取數(shù)據(jù)胎撇、進行編解碼計算、建立恢復或轉(zhuǎn)換的塊來完成這些請求殖氏，并且可能會推送到額外的ECWorker（如果有多個塊被恢復或者轉(zhuǎn)換）晚树。在每個操作中，ECManager都會通知ECWorker要使用的塊組和編解碼約束的名稱（例如：使用Reed?Solomon編碼給原生的塊?{A, B, C} 創(chuàng)建校驗塊）雅采，為了簡化設計文檔爵憎，ECWorker主要的功能聚焦在恢復上，它在轉(zhuǎn)換中的作用將在后續(xù)的1.2階段的工程設計中進行討論婚瓜。
6.2.用戶接口
????HDFS用戶和管理員可以使用幾種樣式控制存儲給定路徑時的策略和首選項宝鼓，本節(jié)其余部分將在EC上下文中分析和比較不同的選項。
6.2.1.存儲策略
????由于對異構(gòu)和歸檔存儲的支持巴刻，HDFS中引入了存儲類型和策略愚铡，基于這個框架，新的存儲策略（例如：EC）可以被定義胡陪，在這個存儲策略下的塊是EC塊沥寥，在最初的階段，原生數(shù)據(jù)和校驗數(shù)據(jù)都被存儲在磁盤存儲類型上柠座。
????然后邑雅，存在APIs可以用于獲取和設置存儲策略，例如妈经，下面的命令告訴HDFS在目錄/ec?dir下的所有的文件的塊都使用糾刪碼存儲淮野。
????????hdfs dfsadmin -setStoragePolicy /ec-dir EC
????存儲策略被存儲在inode的header中，就像在HDFS?6584中實現(xiàn)的那樣吹泡，如圖1中展示的录煤，項目的1.1階段主要聚焦于在以{EC+Striping}的方式創(chuàng)建的文件，因此荞胡，當目錄為空時妈踊，該目錄的EC存儲策略需要被配置，一旦配置將會被修復 -- 類似加密區(qū)域泪漂。
????在1.2階段廊营，通過改變存儲策略可以完成糾刪碼和副本方式之間的轉(zhuǎn)換歪泳，通過Mover或則ECManager直接的觸發(fā)一個新的策略被執(zhí)行，詳情將在接下來的1.2階段設計中被討論露筒。
在這個框架下呐伞，用戶應該有能力為目錄配置編解碼約束，特別是慎式，接口應支持特殊的編解碼算法（例如：Reed?Solomon vs. XOR）和塊組布局（例如：3-of-6 vs.?4-of-10）伶氢。
6.2.2. DFS 命令
????和使用hdfs dfs -setrep的方式改變一個路徑的副本因子類似，新的dfs命令被添加用于直接將一組文件在副本和糾刪碼方式之間轉(zhuǎn)換瘪吏。
????●?hdfs dfs -convertToEC -path <path> <EC schema>: 轉(zhuǎn)換path下的所有的塊為EC的格式（不在EC格式癣防，并且可以被編碼）
????●?hdfs dfs -convertToRep -path <path>: 轉(zhuǎn)換path下的所有的塊到副本格式。
6.3.協(xié)議和元數(shù)據(jù)擴展
6.3.1.塊組
????所有的糾刪碼操作中心是圍繞在塊組的概念中的掌眠，它在初始編碼中形成蕾盯，在恢復和轉(zhuǎn)換中被查找，一個輕量級的類BlockGroup被創(chuàng)建用于在編碼塊組時記錄原始塊和校驗塊蓝丙。EC存儲策略级遭，和編解碼約束一樣，可以在文件的inode（header 或則擴展屬性）中找到渺尘，在條帶布局下挫鸽，HDFS客戶端需要并行的操作塊組中所有的塊，因此我們建議去擴展文件的inode用于切換連續(xù)布局和條帶布局的模式鸥跟，條帶布局的文件有一系列的BlockGroups丢郊，BlockGroup即沒有ID也沒有時間戳，在BlockGroup中的所有的塊可能會使用連續(xù)的IDs并使用相同的時間戳锌雀，詳見“減少NameNode內(nèi)存使用”小節(jié)。這就允許使用第一個Block代表整個塊組迅诬，重用存在的blockmanagement 代碼去處理塊組腋逆，只有第一個塊的ID和共享的時間戳會被存儲在BlockGroup中，為了提供清晰的概念的討論侈贷，本文檔后面的部分使用從真實的實現(xiàn)中抽象出來的BlockGroup去聲明一個邏輯的EC塊組惩歉。
6.3.2.ErasureCodec
????編解碼算法應是可插拔的，由ErasureCodec接口支持俏蛮，提供了連接到流行的庫的一組接口的實現(xiàn)撑蚌，比如英特爾的ISAL(Intelligent Storage Acceleration Library)，下面的2個關(guān)鍵的EC參數(shù)應該也被配置搏屑，糾刪碼編解碼詳細的設計可以在HDFS?7337中被找到争涌，如下：
????????M：在條帶布局組中原始塊的數(shù)量
????????K：在條帶布局組中校驗塊的數(shù)量
????接著，(M,K)-codec可以容忍K個并發(fā)的壞塊辣恋，M也是訪問原始數(shù)據(jù)和恢復不可用的塊的最小需求的塊的數(shù)量亮垫，K/M比率是相對的存儲開銷比率模软，(M,K)-codec的一個例子是(6,3)?Reed?Solomon，(6,3)?Reed?Solomon被選擇作為默認的編解碼器饮潦。
????可能需要添加其它的塊狀態(tài)燃异，例如，當連續(xù)布局的EC在2階段被啟用時继蜡，每個塊會有一個二進制的標志標識它是否是校驗塊（isParity）回俐，連續(xù)的校驗塊被創(chuàng)建、存儲和匯報與原生的方式相同稀并，他們有固定的塊IDs與相同組中的原生塊是不相關(guān)的仅颇，它們的副本（通常只有1個）被存儲在DataNodes的RBW和finalized目錄中，具體取決于階段稻轨，它們也會包括在塊匯報中灵莲，與連續(xù)奇偶校驗塊唯一的區(qū)別是缺少文件從屬關(guān)系。
6.4.?Client Extensions
6.4.1.?ECClient
????HDFS客戶端將被擴展成并行的從多個DataNodes讀寫殴俱，如圖3所示政冻，注意：當前的高層設計是基于QFS客戶端，并將在實現(xiàn)階段為HDFS定制线欲，特別是明场，當在文件中定位一個位置時，ECClient從NameNode獲取的是BlockGroup信息而不是塊的信息李丰，如下：
????????C ?--每個條帶單元的大小苦锨，通常是 64kB
????????B ?-- ??I/O緩存區(qū)的大小，通常為 1MB
????更小的條帶單元的尺寸C可以提高I/O并行度趴泌，但是增加開銷舟舒，更大的緩存大小B可以提高I/O效率，但是會延遲數(shù)據(jù)保護嗜憔。
????當在一個文件上操作時秃励，HDFS客戶端檢測它的存儲策略去決定是否去使用ECClient為I/O進行分段。
????對于EC文件吉捶，可以像使用普通文件類似的方式去使用hflush/hsync/append夺鲜，在普通文件上的hflush/hsync/append的設計查看 [HDFS?265]。
6.4.2.?EC Writer
????當向一個EC文件寫入時呐舔，客戶端會并行的向多個DataNodes寫入條帶（例如：64K）數(shù)據(jù)币励，EC策略采用(6,3)?Reed?Solomon時，客戶端數(shù)據(jù)寫入到前面的6個DataNodes珊拼，將校驗數(shù)據(jù)寫入剩下的3個DataNodes食呻，注意：DataNodes和客戶端都有緩存存在。因此，當客戶端寫一些數(shù)據(jù)到DataNode搁进，這些數(shù)據(jù)會先被拷貝到一個緩存中（例如：1MB）浪感，然后刷出去；DataNodes的寫緩存相對較小饼问，通常4KB影兽，在本文剩下的部分，我們會把緩存忽略掉莱革。
????起初峻堰，客戶端寫第一個條帶數(shù)據(jù)到第一個DataNode，寫第二個條帶數(shù)據(jù)到第二個DataNode等等盅视，一旦它有了第6個條帶數(shù)據(jù)捐名，它會計算出3個校驗數(shù)據(jù)條帶，并把它們寫入到剩下的3個DataNodes中闹击，和寫管道類似（例如：寫管道用于多個副本）镶蹋，一旦一個DataNode已經(jīng)接收到了來自客戶端的包（數(shù)據(jù)包或則校驗包），它會發(fā)送一個確認信息到客戶端赏半，客戶端會不斷的寫贺归，除了最后一個包外，其它的包客戶端都不會等待來自DataNode的確認信息断箫。
????除了最后一個條帶組拂酣，客戶端總是發(fā)送完整的條帶數(shù)據(jù)到DataNode，在文件的末尾仲义，數(shù)據(jù)長度可能不是數(shù)據(jù)條帶組的大猩舭尽（在這個例子中是 6 X 64K）的倍數(shù)，客戶端一旦收到關(guān)閉文件的請求就會計算校驗數(shù)據(jù)埃撵，當最后一個條帶組不完整時赵颅，客戶端還會在末尾寫入最后一個條帶組的長度。
????解碼所需要的條帶組的長度如下所述暂刘。
6.4.3.?在寫期間處理Datanode故障
????在寫數(shù)據(jù)的時候當一個或多個DataNode失斀让（例如：DataNode掛掉，網(wǎng)絡問題）時鸳惯，客戶端會忽略失敗的DataNodes商蕴，為塊組中剩下的所有的塊重新生成時間戳叠萍，之后往剩下的DataNodes上繼續(xù)寫數(shù)據(jù)芝发，前提是剩余的DataNodes的數(shù)量大于等于最小需求的DataNodes的數(shù)量，注意：塊組中的塊共用相同的時間戳苛谷，直到客戶端完成到塊組的寫入前辅鲸，丟失的塊不能恢復，恢復操作通常是由NameNode中EC重構(gòu)計劃調(diào)起的腹殿。如果剩余的DataNodes小于最小需求的DataNodes独悴，客戶端會拋出一個寫失敗的異常例书，EC策略采用(6,3)?Reed?Solomon時，最小需求的DataNodes是6刻炒，客戶端可以容忍3個DataNodes失敗决采。
????另外一種方式是關(guān)閉當前的BlockGroup，之后使用變長塊組長度特性繼續(xù)寫一個新的BlockGroup [HDFS?3689]坟奥。
6.4.4.?慢速寫入器树瞭，故障時更換Datanode
????對于HDFS寫管道（多副本機制），有一個特性replace?datanode?on?failure用于當DataNode寫管道失敗時爱谁，可以使用新的DataNode來替換它晒喷，該特性的設計用于支持慢寫者，因為慢寫者不是EC文件（慢寫者應該使用寫管道）的使用案例访敌，所以特性replace?datanode?on?failure不支持EC文件凉敲。
6.4.5.?讀取已關(guān)閉文件
????因為文件已經(jīng)被關(guān)閉了，它的長度是固定的寺旺，客戶端可以讀取9個DataNode中的任意6個爷抓，帶有數(shù)據(jù)塊的DataNode比帶有校驗塊的DataNode更可取，因為這樣可以減少EC塊重構(gòu)工作量迅涮。
????對于有完整數(shù)據(jù)的塊組废赞，客戶端從選擇的6個DataNodes中讀數(shù)據(jù)塊/校驗塊，如需要會重構(gòu)數(shù)據(jù)塊叮姑。
????對于部分塊組（僅對文件中最后一個塊組有效）唉地，如果沒有校驗塊被調(diào)用，并且不需要EC重構(gòu)传透，客戶端會從選中的6個DataNodes中讀數(shù)據(jù)塊/校驗塊耘沼，否則，客戶端還要從對等的DataNode上讀取最后一個條帶的長度朱盐；在重構(gòu)EC數(shù)據(jù)塊前群嗤，客戶端需要校驗來自校驗塊的最后的條帶長度、數(shù)據(jù)真實的長度和從NameNode中獲取的文件長度是否匹配兵琳。
6.4.6. 讀正在被寫入的文件
????當一個文件正在被寫時狂秘，塊組中的每一個塊的大小可能不相同，客戶端首先從帶有數(shù)據(jù)塊的DataNode獲取數(shù)據(jù)長度躯肌，從帶有校驗塊的DataNode獲取校驗長度和最后一個條帶的長度者春，它使用長度信息來決定最大有效長度，并從中選擇6個要讀取的DataNode清女，之后钱烟，客戶端可以從中讀取數(shù)據(jù)，如果需要還可以像以前一樣重構(gòu)數(shù)據(jù)，它保證新的客戶端可以像以前的客戶端讀取器一樣讀取相同的數(shù)據(jù)量拴袭。
6.4.7.?Hflush
????當hflush被調(diào)用读第，客戶端將所有存在的數(shù)據(jù)和校驗碼刷新到所有的DataNodes，之后客戶端會阻塞等待所有的DataNodes返回的最新的確認信息拥刻，一旦接收到了所有的確認信息怜瞒，它將返回成功，這個時候般哼，新的讀取器能夠讀取到hflush位置之前的所有的數(shù)據(jù)盼砍，當恢復寫操作時，并且hflush的位置不在完整的條帶組的邊界時逝她，客戶端需要重寫最后一個校驗條帶浇坐。
6.4.8.?Hsync
????hsync 和hflush類似，只是DataNode在發(fā)送確認信息之前還會發(fā)送一個本地fsync調(diào)用黔宛。
6.4.9.?Append
????追加數(shù)據(jù)到一個存在的BlockGroup近刘，需要有效的DataNode的數(shù)量大于等于最小請求的DataNode數(shù)量，它從BlockGroup中的所有塊中更新生成的時間戳開始臀晃，之后觉渴，客戶端寫數(shù)據(jù)到所有有效的DataNodes，類似于hflush徽惋，當最后一個條帶組不完整時案淋，客戶端需要去重寫最后一個校驗條帶。
????追加也可以支持使用變長塊長度特性[HDFS?3689]险绘，例如踢京，追加數(shù)據(jù)到一個新的BlockGroup，但是不能重新打開上次存在的BlockGroup宦棺。
6.4.10.?Truncate
????截斷一個EC文件瓣距，除了最后一個條帶的校驗文件可能需要去重新計算，其它的類似于截斷一個正常的文件代咸；和append類似蹈丸，它需要有效的DataNode的數(shù)量大于等于最小需求的DataNodes的數(shù)量，它更新BlockGroup中的所有塊的生成時間戳開始呐芥，對于條帶組邊界的截斷逻杖，客戶端會截斷所有的數(shù)據(jù)塊和校驗塊，之后就完成了截斷思瘟，否則荸百，客戶端讀取包含在截斷位置的所有的數(shù)據(jù)條帶，如果有些數(shù)據(jù)塊是無效的潮太，為了重構(gòu)丟失的數(shù)據(jù)條帶管搪，客戶端也需要讀取包含在截斷位置的校驗條帶；然后铡买，為截斷的數(shù)據(jù)計算新的條帶組的長度和新的校驗數(shù)據(jù)更鲁，最終，客戶端截斷DataNode上的所有的數(shù)據(jù)塊奇钞，并截斷校驗塊澡为，使用條帶組的長度重寫最后一個校驗條帶。
????如果正在進行升級或者截斷一個快照的文件景埃，為了支持回滾或者從快照中讀取數(shù)據(jù)媒至，首先需要復制最后一個塊現(xiàn)有的數(shù)據(jù)。
6.4.11.?BlockGroup?狀態(tài)
????當BlockGroup被創(chuàng)建谷徙，它處于UNDER_CONSTRUCTION狀態(tài)拒啰，一旦ECClient完成了寫入BlockGroup，它將發(fā)送所有剩余的R個數(shù)據(jù)塊寫入NameNode（某些塊可能由于失敗被排除）完慧，如果NameNode接收到的R個塊大于等于最小需求的塊數(shù)M（例如：策略(6,3)?Reed?Solomon的M是6）谋旦，BlockGroup 會被轉(zhuǎn)換為COMMITTED狀態(tài)，當NameNode從M個DataNodes接收到M個塊的信息時屈尼，BlockGroup 會被轉(zhuǎn)換為COMPLETE狀態(tài)册着，當一個塊組被恢復時，它是UNDER_RECOVERY狀態(tài)脾歧。
6.4.12. 生成時間戳
在一個塊組中的所有的數(shù)據(jù)塊和校驗塊共用相同的生成時間戳甲捏，塊組自己沒有生成時間戳，為了內(nèi)存的效率鞭执，共用的時間戳被存儲在塊組對象的實現(xiàn)中司顿。
6.4.13.?BlockGroup?恢復
????BlockGroup的恢復是一個過程，它將更新所有當前有效的塊的生成時間戳兄纺，使得有效的塊的生成時間戳變新了免猾，無效的塊的生成時間戳保留不變，這樣囤热，如果將來出現(xiàn)無效的塊猎提，它們可以被排除和刪除，這個用于故障處理旁蔼、追加和截斷锨苏。
6.4.14.?Client-Datanode?連接
????為了寫一個EC文件，客戶端會并行的寫入到9個DataNodes棺聊，它的寫入速度是現(xiàn)存的3副本寫管道的方式的9倍伞租，讀取一個EC文件會并行的從6個DataNodes讀取，它需要6倍的連接限佩，這會導致一個客戶端同時讀寫多個文件是個問題（連接數(shù)太多了）葵诈，這個問題可以通過改變DataTransferProtocol 的實現(xiàn)采用復用連接的方式來修復裸弦，以便從客戶端到DataNode的多個并發(fā)的塊的讀寫僅使用一個連接。
7.NameNode Extensions
????當前作喘，HDFS的NameNode運行了ReplicationMonitor守護進程周期的執(zhí)行塊的復制和失效任務理疙，這些任務分別是對隊列UnderReplicatedBlocks 和 InvalidateBlocks 的插入和維護的，這種機制非常適合調(diào)度后臺塊編解碼任務泞坦，包括主動塊恢復和進行副本方式和EC方式的切換窖贤。
????下面的圖4說明了 在NameNode上提議的擴展（主要在BlockManagement上）
7.1.?ECManager
????這個組件用于管理BlockGroups和相關(guān)的編解碼約束，舉個簡單的例子贰锁，當一個 {Striping+EC} 文件被創(chuàng)建并開始寫入赃梧，ECManager將用于服務來自客戶端的請求去分配新的BlockGroups并存儲它們到INodeFile下，在當前階段豌熄，初始在線編碼和從副本到EC的轉(zhuǎn)換中都會被分配BlockGroups授嘀，ECManager還為塊恢復工作中查找BlockGroup信息提供工具。
7.1.1.?EC塊重構(gòu)
????當一個塊組中的一個或多個EC塊丟失锣险，NameNode會為重構(gòu)EC塊調(diào)度塊組粤攒，對于(6,3)?Reed?Solomon策略，因為它能容忍丟失3個塊囱持，1個或者2個塊的丟失情況是處于低優(yōu)先級的夯接，丟失3個塊的情況是處于高優(yōu)先級，我們用NameNode中現(xiàn)存的副本調(diào)度框架進行EC塊重構(gòu)纷妆，如下所述：
7.1.2.UnderReplicatedBlocks
????UnderReplicatedBlocks會將新的優(yōu)先隊列（例如：QUEUE_CONVERSION）添加到5個現(xiàn)存的隊列中盔几，去維護編解碼和復制任務相對的順序，
????1）當發(fā)現(xiàn)校驗塊或者在ENCODED狀態(tài)的原生塊丟失掩幢，丟失的塊會被添加到UnderReplicatedBlocks中逊拍，它的優(yōu)先級由所在組的條件決定，例如：如果組中所有的校驗塊都丟失际邻，它們應該被添加到QUEUE_HIGHEST_PRIORITY優(yōu)先級中芯丧，可以為細粒度的區(qū)分添加新的優(yōu)先級（例如：相對于校驗塊原生塊的丟失）
????2）新的優(yōu)先級QUEUE_CONVERSION，被用于轉(zhuǎn)換副本塊到EC塊世曾，反之亦然缨恒，因為這個轉(zhuǎn)換與塊的可用性無關(guān)，在UnderReplicatedBlocks中新的優(yōu)先級應該比現(xiàn)存的更低轮听。
????3）與常規(guī)的塊復制任務相比骗露，編解碼一個塊會消耗更多的I/O帶寬和CPU周期，因此血巍，應該對塊的編解碼任務限制總的系統(tǒng)資源的消耗萧锉。
7.2.?ErasureCodecWork
????ReplicationMonitor將會被擴展以區(qū)別副本和編碼任務，如果校驗塊被創(chuàng)建述寡，或者在BlockGroup中的原始塊被修復柿隙，會催生一個ErasureCodecWork 任務去替換ReplicationWork叶洞，它會做如下的事：
????1）從ECManager中獲取所有的編解碼相關(guān)的信息，包括BlockGroup 和相關(guān)的編解碼約束禀崖，一個新的塊替換算法需要選擇目標DataNode進行編碼工作和主持恢復或轉(zhuǎn)換塊衩辟，最終的BlockGroup 應該分布在不重復的DataNodes上（在多余的副本被刪除后），理想的狀態(tài)是放在不重復的機架上帆焕，所以任何節(jié)點/機架的損壞最多會影響塊組中的一個塊，可以應用幾個有意義的優(yōu)化不恭，首先叶雹，分發(fā)編碼工作到多個DataNodes節(jié)點以減少目標節(jié)點上的CPU負載，其次换吧，將校驗塊放在組中原生塊盡可能多的副本的附近折晦，以便編碼可以部分的在本地數(shù)據(jù)上完成 ，應將這些副本作為多余副本刪除沾瓦，以維護組中條帶分布模式满着。
????2）發(fā)送編解碼命令選擇DataNode
????3）在接收到來自DataNode的確認成功的編碼的回應之后，通過添加任務到InvalidateBlocks刪除多余的副本
????4）當正在恢復丟失的原生塊時贯莺，一旦解碼塊被初始化完成风喇，選擇的DataNode應該回應ErasureCodecWork ，之后在blocksMap中的塊的存儲位置需要被更新缕探，允許客戶端在重構(gòu)時去讀取部分塊的數(shù)據(jù)魂莫。
8.?DataNode擴展
8.1.ECWorker
????這是在DataNode上的主要的糾刪碼組件，如圖5所示爹耗，當接收到來之NameNode的編解碼命令后耙考，ECWorker 解析命令并獲取組中包含原始塊的DataNodes主機的列表 -- 在修復原始塊的情況下，組中校驗塊對應的一個或多個DataNodes主機也應該包含在列表中潭兽，之后它嘗試去連接這些節(jié)點的DataXceiver 倦始，接收數(shù)據(jù)包去逐漸的重構(gòu)校驗塊（或者恢復原始塊），在校驗塊被成功的構(gòu)建（或者原始塊被修復）后山卦，ECWorker 會發(fā)送一個回應給NameNode鞋邑，此時，可以計劃刪除組中多余的塊副本账蓉。
9.優(yōu)化
9.1.?減少NameNode?內(nèi)存使用
條帶方式通過引入更多的塊增加NameNode的內(nèi)存的使用炫狱，例如，HDFS當前將一個128MB的文件存儲為帶有3個副本的塊剔猿，在blocksMap中產(chǎn)生一個條目视译，使用條帶方式和Reed?Solomon (6,3)約束，文件會使用9個塊归敬，每個塊有一個副本酷含，這個可以通過使用連續(xù)的IDs（或者其它的可預測的方式）對塊進行編號來減緩NameNode內(nèi)存壓力鄙早，下面提供了一個編號方案，如圖6所示椅亚。
????1）64位的塊ID空間被分成2部分限番，正常的塊ID空間和EC塊ID空間，最高的位表示這個塊是否是一個EC塊（因此屬于一個塊組）
????2）對于EC塊：
????????a.?最高位是1呀舔。
????????b.?使用最低4位標記一個塊在BlockGroup中的序號
????????c.?塊組中第一個塊的ID的最低4位是0
????????d.?BlockGroup不是一個ID
????3）對于正常的塊弥虐，最高位是0，使用剩余的63位生成IDs
????4）除了BlockGroup中第一個塊的ID被放入到blocksMap中外媚赖，還要保留一個blockGroupsMap 霜瘪，當DataNode匯報一個塊時，它可以很容易的推斷出它是否是一個編碼的塊惧磺，如果是的颖对，則確定它的BlockGroup。
????這次優(yōu)化再加上其它的一些正在進行的努力磨隘，應該可以幫助避免大多數(shù)生產(chǎn)集群中的內(nèi)存不足：
????1）HDFS?6658 (optimizing block replicas list)
? ????在沒有使用壓縮的情況下節(jié)省11%的內(nèi)存使用缤底。
????2）HDFS?7244 （享元模式）
????在堆外內(nèi)存的情況下，......番捂，BlockInfo對象的內(nèi)存的使用可以減少到一個非常小的常量值
????3）將blockId從long類型縮小到一個6字節(jié)的數(shù)組
????這將為每個塊節(jié)省8 - 6 = 2字節(jié)
9.2.與隨機塊ID的沖突
????因為早期的HDFS支持隨機的塊IDs个唧，為EC塊保留的塊IDs可能已經(jīng)被集群中現(xiàn)有的塊使用，在NameNode啟動期間设预，它會檢測是否有保留的EC塊IDs被非EC塊使用坑鱼，如果有，當在blockGroupsMap 中查找失敗時絮缅，NameNode將會在額外的blocksMap中查找鲁沥。
9.3.?Datanode?退役
????比起副本機制EC塊的重構(gòu)是昂貴的，因為副本可以從任意有效的擁有該副本的源DataNode上拷貝耕魄，然而画恰，如果一個EC塊是無效的，它需要從6個DataNodes讀取數(shù)據(jù)用于恢復失效的塊吸奴，因此允扇，當一個DataNode要被從集群中移除時，在DataNode退役前移除它上面的所有的EC塊是個好的主意则奥。對于重啟DataNode,為了指示該DataNode將很快就重新加入集群考润，為DataNode引入了一個新的睡眠狀態(tài)，在重啟期間读处，NameNode不會為這個DataNode上的任意EC塊調(diào)度重構(gòu)工作糊治。
9.4.?MapReduce數(shù)據(jù)本地性
????MapReduce工作在?record?的粒度忿檩，因此煌集，我們需要對齊record和條帶邊界，這種對齊可以使用隔離的MapReduce作業(yè)來完成，MapReduce任務的調(diào)度算法也應該知道條帶模式吆豹。
9.5.?Block?移動
1）一個簡單的方式是禁用對EC塊的balance操作，同時刷允，因為數(shù)據(jù)存儲策略（例如：HOT/WARM/COLD）是被用戶準確的定義的冤留，如果編碼的塊要被移動，我們應該跳過它們树灶。
2）一個更有效的方式是讓Balancer和Mover對EC組是感知的纤怒，避免上述的放置決定Appendix: 3-replication vs (6,3)-Reed-Solomon
10.附錄：3-replication vs (6,3)-Reed-Solomon
我們在這部分比較3副本方式和 (6,3)-Reed-Solomon方式
10.1. 容錯：
對于數(shù)據(jù)的訪問最小需要的塊數(shù)：
磁盤空間使用：
命名空間使用：
客戶端到DataNode的連接數(shù)：
10.2. 網(wǎng)絡流量
假設一個機架最多2個塊，
Keys: LN = local node, LR = local rack, RR = remote rack?
寫數(shù)據(jù)：
讀數(shù)據(jù)假設客戶端可以被移動到任意的DataNode破托，并且集群有足夠的大以至于2個不同的塊總是存儲在不同的機架肪跋。
?3-replication(6,3)-Reed-Solomon
對于1個塊的丟失重構(gòu)假設機架本地化是可能：
11.引用:
[Fan09] “DiskReduce: RAID for Data?Intensive Scalable Computing”, PDSW 2009 [Ford10] “Availability in Globally Distributed Storage Systems”, OSDI 2010
[Harter14] “Analysis of HDFS Under HBase: A Facebook Messages Case Study", FAST 2014 [Huang12] “Erasure Coding in Windows Azure Storage”, USENIX ATC 2012
[Khan12] “Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads”, FAST 2012
[HDFS-265]?Append/Hflush/Read Design
[HDFS-3689] Add support for variable length block
[Intel-ISA]?https://01.org/intel@?storage?acceleration?library?open?source?version [Muralidhar14] “f4: Facebook’s Warm BLOB Storage System”, OSDI 2014 [Nightingale12] “Flat Datacenter Storage”, OSDI 2012
“The Quantcast File System”, VLDB 2013
[Sathiamoorthy13] “XORing Elephants: Novel Erasure Codes for Big Data”, VLDB 2013
