大數據

HFR:在RBF上實現跨NameSpace Rename

摘要

隨著HDFS數據量越來越大,NameNode內存已不足以裝下全部元數據,這限制了HDFS的擴展。社區提出的RBF(Router Based Federation)比較高效地解決了這個問題。它將用戶視角的目錄拆分到多組互相獨立的子集群(名字空間或者NameSpace)中,這一過程被稱為掛載。Router層記錄掛載表信息,并轉發用戶請求,使得RBF看起來和普通HDFS一樣。??但RBF也有自己的問題:

  • 不支持跨NameSpace的rename。
  • NameSpace隨著使用會逐漸不均衡,社區目前還沒有用于均衡NameSpace的工具。

為了解決這兩個問題,我們設計了HFR(HDFS Federation Rename)。它支持跨NameSpace rename目錄和文件,也可以用來做NameSpace負載均衡。介紹? HFR的思想是:先把源目錄樹從源NameNode移動到目標NameNode,再將所有數據塊從源pool遷移到目標pool,最后更新Router上的掛載表,之后client就能從新的NameNode訪問到目錄了。

在元數據和文件數據都不斷變化的情況下來實現遷移非常困難,所以HFR中引入了一個額外的限制來簡化這個問題:HFR作業執行期間,所有會修改元數據和文件數據的操作都被禁止掉(禁止寫操作)。后面我們會看到,這個限制大大簡化了HFR的實現。? HFR作業被劃分為5個階段:Prepare、 SaveTree、 GraftTree、 HardLink和Finish:

  1. Prepare: 完成權限和quota檢查,并鎖定src-path,禁止寫操作。
  2. SaveTree: 向src-NameNode發送saveTree() RPC,令其將目錄樹序列化到外部存儲中。
  3. GraftTree: 向dst-NameNode發送graftTree() RPC,dst-NameNode會讀取并反序列化上一步的目錄樹,并接到自己的目錄樹上。
  4. HardLink: RBF集群的DataNode是共享的,我們可以使用硬連接來完成數據塊傳輸。本階段會先收集所有塊的位置信息,生成HardLink計劃,最后向DataNode發送RPC實現塊的hard link。
  5. Finish: 完成校驗和清理工作,并更新Router的掛載表。

為了將這5個階段整合起來,我們設計了一個狀態機模型。HFR作業是一個狀態自動機,每一個階段對應一個狀態。如果一個階段失敗了,則跳轉到錯誤處理狀態,否則跳轉到下一階段狀態。

我們引入新角色Scheduler來負責HFR作業的啟動、執行、重試和恢復。??接下來我們會分別介紹SaveTree階段(第二部分)、GraftTree階段(第三部分)、HardLink(第四部分)、Scheduler模型(第五部分)、性能(第六部分)、總結(第七部分)。我們不討論Prepare階段和Finish階段,因為這兩個階段比較簡單,也比較多變,不同的用戶可以根據自己需要實現不同的Prepare和Finish階段。SaveTree

在SaveTree階段,我們引入了saveTree() RPC,它會保存src-path目錄樹到外部存儲中,包括樹的結構、INodes、以及Blocks。saveTree() RPC還有一個特點是,它假定src-path已經被鎖住且處于不可變的狀態,因此不會做額外措施來保護目錄樹不被改變,即不會做禁寫。下面分別討論保存src-path到外部存儲的過程和saveTree()不做禁寫的原因。

saveTree()調用會產生兩個文件:TREE-FILE和TREE-META,這兩個文件被保存在外部存儲中。TREE-FILE中保存了整個目錄樹,TREE-META則保存目錄樹的各種統計信息。saveTree() RPC首先深度優先遍歷src-path,并將所有INodeDirectory和INodeFile序列化到TREE-FILE中。序列化的方式和NameNode生成Image的方式相同,這樣目錄的全部屬性(ACL、Xattr等)都會被保留。INode的寫入順序與遍歷順序相同,因此目錄樹的結構也可以被保留。遍歷的同時,saveTree() RPC會計算src-path的name消耗、space消耗和塊總數,并將它們寫入到TREE-META中(后面的GraftTree階段會解釋為什么需要生成TREE-META)。

SaveTree階段不做禁寫操作有兩個原因,一是要保持簡單。saveTree() RPC只是簡單地遍歷目錄樹并寫兩個文件,整個過程都是無鎖的,也沒有edit log,是非常輕量級的操作。二是保持靈活,我們可以讓SaveTree之前的階段來負責禁寫,它可以根據自身需要用任何它想使用的手段,比如簡單的取消src-path的x權限,或是復雜些的逐個子目錄取消w權限等等。這些自定義的階段都可以與SaveTree階段組合,來滿足不同需求。saveTree()的結果文件也不被限制只能用于HFR,也可以被用來其他用途,譬如DEBUG。如果用戶愿意,他們可以在沒有禁寫的目錄上調用saveTree(),這樣做雖然不會損壞NameNode,但也無法保證寫到外部存儲的目錄樹的完整性。

Figure 1: The process of saveTree.GraftTree  GraftTree階段是HFR的核心,graftTree() RPC讀取TREE-FILE和TREE-META并構造dst-path。過程如下:

  1. 讀取TREE-META文件。
  2. 合法性檢查,包括路徑名合法性、權限、quota等。
  3. 預分配INode Id和Block Id。
  4. 讀取TREE-FILE,反序列化并構造目錄樹。
  5. 將構造好的目錄樹接到NameNode根目錄樹上,將所有Id添加到對應Map。

Figure 2: The process of GraftTree.  在graftTree()中涉及到很多NameNode元數據操作,因此必須獲取寫鎖。但整個RPC過程又有很多IO操作,所以不能像其他RPC那樣簡單地在RPC開始時獲取寫鎖并在RPC結束的時候釋放掉。這里我們使用了一個比較巧妙的辦法避免拿著寫鎖做IO,實際上只需要在第2步獲取讀鎖,在第3和5步獲取寫鎖就夠了,其余步驟都是無鎖的。因為在第3和5步要獲取寫鎖,而在第4步不需要任何鎖,所以中間會有一個放棄鎖再恢復鎖的過程。為此我們引入了一個計數器,在第4步開始的時候,開始一邊釋放鎖一邊計數,直到所有鎖都被釋放掉,然后執行第4步,執行完成后再根據計數器恢復被釋放掉的鎖。下面解釋一下鎖設計的正確性:

  • 第1步只是讀取TREE-META文件,包含IO操作且不需要讀寫NameNode自身元數據,自然應該是無鎖的。
  • 第2步需要做合法性檢查,涉及到讀取NameNode元數據,和所有其他讀操作一樣,這一步是要拿讀鎖的。
  • 第3步預分配Id,這一步會修改NameNode元數據,因此必須拿寫鎖。
  • 第4步構造目錄樹,構造過程需要讀取TREE-FILE文件,并給新建INode和Block分Id,因為所有Id都在第三步分配好了,所以這一步雖然有IO但不需要拿任何鎖。
  • 第5步將目錄樹接到NameNode上,還要添加Id到Map,這都會改變NameNode元數據,必須拿寫鎖。

  現在我們可以解釋為什么SaveTree階段還會保存一個TREE-META文件了。在第二步quota檢查時我們需要知道目錄樹的name和space大小,在第三步Id預分配時我們需要知道INode總數和Block總數,有了TREE-META我們就不必讀取整個TREE-FILE來自己計算了,只要在第一步讀取TREE-META即可。  現在我們討論至關重要的錯誤處理部分。在這里我們的思路是”不要undo”,即GraftTree階段的5個步驟不論哪一個出錯了,都不要做回滾。這是因為回滾操作非常復雜,每一步都可能失敗,回滾本身也可能失敗。這里我們同樣使用了一個比較巧妙的辦法,通過引入兩階段edit log解決了這個問題,完全避免了回滾操作,這兩個edit log是:

  • Pre-allocation edit log,在第3步預分配Id成功時,記錄分配了哪些Id。
  • Graft-done edit log,在第5步整個RPC成功時,記錄graftTree()參數列表和id映射表。

  我們將NameNode重放edit log后的狀態叫做重放狀態,將NameNode記錄完edit log那一刻的狀態叫做標準狀態,只要重放狀態與標準狀態一致,那么無論發生failover、重啟、或是standby節點追日志,NameNode狀態都是正確的。下面簡單證明一下為什么兩階段edit log可以保證重放狀態與標準狀態一致。我們用e表示NameNode原有的edit log,用S表示標準狀態,用R表示重放狀態。NameNode當前每條edit log(不包含Pre-allocation和Graft-done)都滿足重放狀態等于標準狀態:對于任意一個ei和初始狀態S,我們都有Si=Ri,其中Si表示S狀態保存ei之后的標準狀態,Ri表示S狀態重放ei之后的重放狀態。將上一步稍微推廣一下,對于一個序列{e1,…,ei,…,en}和初始狀態S,數學歸納法易證對于任意i屬于[1,n],Si=Ri。  從兩階段edit log過程我們知道,其實edit log序列只有三種情況(ep表示Pre-allocation edit log,eg表示Graft-done edit log):無ep無eg、有ep無eg和有ep有eg。接下來我們逐個討論3種情況下標準狀態與重放狀態一致性:

  • 無ep無eg(步驟1,2,3其中一個失敗),edit log序列={e1,…,en},屬于原始的NameNode edit log序列,顯然成立。
  • 有ep無eg(步驟4或5失敗),edit log序列={e1,…,ei,ep,…,en}。考慮對于任意起始狀態S,當從Si->Sp時,NameNode會從可用Id集合中去除預分配Id并將去掉的Id記錄到ep,當重放ep時NameNode會將ep記錄的Id從可用Id集合中去除掉。對于Si->Sp和Si->Rp兩個過程來說,起始可用Id集合相同又去除了相同的Id,因此Sp=Rp,進而對任意x,都有Sx=Rx。
  • 有ep有eg(全部步驟成功),edit log序列={e1,…,ei,ep,…,ej,eg,…,en}。在Sj->Sp時,NameNode完成了步驟4和5,并記錄graftTree()參數和預分配Id到eg。步驟4和5可以看作有兩個輸入的函數:f(狀態Sj、預分配Id)。當重放ep時NameNode也重做步驟4、5,其中步驟4使用的Id記錄在eg中,與Sj->Sp時使用的Id完全相同。可見Sj->Sp和Sj-Rp時兩者輸入均相同,因此Sg=Rg。結合上一步證明可知對e1~eg均有Si=Ri,進而對任意x有Sx=Rx。

  在graftTree() RPC過程中,NameNode的狀態改變涉及到Id生成器、根目錄樹和Id映射表三部分。其中”Id被添加到Id映射表”和”dst-path目錄樹被添加到根目錄樹”同時發生,所以可以用根目錄樹的添加來表示Id映射表添加。下圖展示了三種情況下NameNode狀態與對應的edit log狀態:

Figure 3: The NameNode states and the edit log.? 下面討論一些實踐中的細節。首先討論步驟4,我們知道步驟4是無鎖的,這意味著它不可以改變NameNode的元數據。步驟4構造的dst-path目錄樹不能被接到根目錄樹上,而是作為整個RPC過程的一個局部變量保存在內存中。一旦RPC失敗,這棵樹就會被自動回收掉,不需要額外的清理工作。

下面來看一下graftTree() RPC的最后一步,我們先將所有Id添加到block-map和inode-map,然后將dst-path目錄樹接到根目錄樹上,最后寫下edit log。

這三個操作必須同時完成或同時不做,只有部分完成則NameNode要殺死自己。最后看一下BLOCK-MAP文件,在GraftTree階段,我們會寫一個新文件BLOCK-MAP。它映射了源NameNode的Id到目標NameNode的Id,包括INodeId、BlockId和GenerationStamp。這個文件是在第4步構造目錄樹時,一邊深度遍歷一邊寫成的,我們在下一步做HardLink的時候會用上它。

另外在我們的實踐中,Graft-done edit log并沒有記錄所有預分配的Id,重放這條edit log時我們是通過讀BLOCK-MAP來獲取預分配信息的。HardLink
? HardLink階段負責將所有副本hard link到新block pool。

一個塊可以被pool id、block id和gs(generation stamp)唯一確定,進而一個塊的hard link可以看作是一個6元組(src-pool, src-id, src-gs, dst-pool, dst-id, dst-gs)。我們給DataNode添加了一個新RPC接口,批量接收hard link 6元組,完成hard link并IBR(增量塊上報,與之相對的是全量塊上報)給NameNode。所有成功hard link的塊都會返回給Client。??HardLink過程分為兩個步驟:

  1. 收集塊位置信息,并生成hard link計劃。
  2. 執行hard link并處理hard link失敗的情況。

Figure 4: The process of HardLink.??在第1步我們用多線程的方式收集塊位置信息。首先我們定義一個pendingQueue用來保存未被處理的路徑,之后我們啟動多線程來消費這個隊列。

當一個線程拿到一個路徑的時候,它首先判斷路徑類別,如果是目錄就將它的所有子路徑加入到隊列中,如果是文件就收集它的塊位置信息,并添加到hard link map。這個map的key是DataNode,value是這個DataNode上一系列要做hard link的塊。

Figure 5: The thread model of collecting locations.??第2步我們使用一個線程池來做hard link,每一個線程負責一個DataNode,分批地將block發給對應DataNode,并收集hard link結果。如果一個塊成功hard link的次數滿足了最小復制因子,就認為這個塊hard link完成。

否則我們需要去目標NameNode檢查它的副本數,這是因為NameNode也會做復制,如果塊的副本數已經滿足了最小復制因子,就不需要再hard link了。如果檢查完NameNode塊副本數仍舊沒有達到最小復制因子,就對這些未達標塊重試整個流程。

Figure 6: The thread model of hardlink.Scheduler模型? Scheduler模型包括一個作業模型和一個調度器。一個作業是一個狀態自動機,可以用如下圖來表示。一個作業(Job)包括有限個任務(Task),任務間的有向邊表示任務執行流程。

標記為Start的任務是作業的初始任務,標記為None的灰色任務是一個特殊任務,表示作業的結束。Job Context保存了作業的上下文信息,當作業被執行時Job Context會被逐個傳遞給每個任務,每個任務都可以根據需要來修改它。每一次任務結束時Job Context都會被序列化并保存到外部存儲中,用于恢復失敗的作業。

Figure 7: The job model.? Scheduler管理了所有作業的生命周期,下圖表示了Scheduler的線程模型。每一個作業都有四種狀態:Running、Pending、Delay、Recovering。當一個作業被提交給Scheduler后,它就被加入到pendingQueue中,處于pending狀態。Worker線程不斷地從pendingQueue中獲取作業并執行,這時作業就進入running狀態。

當作業執行時,它可以通過設置delay time并拋出TaskRetryException的方式來觸發重試。Worker捕捉到這個重試異常,就會給它加入到delayQueue中。當delay time時間到,作業會被Rooster線程取出并加回到pendingQueue,作業再次進入pending狀態。

如果作業執行過程中有未知異常發生,作業就會被加入到recoverQueue中。Recover線程負責從recoverQueue中獲取作業,并根據job context來恢復它。當Scheduler啟動的時候,它會自動掃描外部存儲來查找所有未完成作業,并將它們加入到recoverQueue中。

Figure 8: The job scheduler model性能測試環境  測試集群包含2個NameSpace和14個DataNode。服務器配置如下:

  • Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz, 12 cores.
  • 128GB RAM, 4T x 12 HDD
  • Linux 2.6.32, JDK 8

測試方法

  • 數據集”set x-y”表示一個深度為x的目錄樹,樹的每個非葉子節點都有y個孩子節點,樹的每個葉子節點都是一個文件。
  • 文件副本數是3,每個文件只包含一個塊。Linux中對256MB文件和1KB文件做HardLink速度是一樣的,因此這里做了個優化,使用1KB塊文件代表 256MB塊。下表中File Size是按照每個文件256MB計算的總文件大小。

測試結果Table 1: The performance results.

Data setsDirectoriesFilesBlocksTime costs/msFile Size
set 7-71960811764911764918,00128.72TB
set 7-83744926214426214430,89064TB
set 8-959787147829694782969577,3601.14PB

線上環境??線上環境與測試環境有很大不同,主要是為了保證安全,線上環境我們做了更煩瑣的校驗,這對HFR速度影響很大,會使其耗時更久。線上的校驗需要給NameNode發送大量rpc,每個rpc的耗時也隨NameNode當時的ops有波動,所以會有大小差不多的目錄耗時卻不同的情況。?

下表展示了部分線上環境遷移案例:Table 2: The online cluster performance.

PathFiles+DirectoriesBlocksTime costs
/user/h_data_platform/platform/isource1900000+25239101166s
/user/h_data_platform/platform/b2cdc1600000+2461348875s
/user/h_data_platform/platform/fintech1400000+1830326697s

總結? HFR實現了跨NameSpace的rename。它的速度很快,可以在秒級完成TB數據的rename。HDFS RPC的默認超時是60秒,所以小目錄上的HFR不會引起用戶端RPC超時。HFR在處理跨NameSpace均衡的時候也非常靈活高效,我們經常遇到這樣的問題:有的用戶希望遷移整體盡量快,為此可以接受一段時間的服務不可用;有的則不能接受,他們希望大路徑被拆成很多小路徑一點一點遷移過去,整體時間可以較長,但每一部分的遷移時間要非常短。

Scheduler模型是靈活可插拔的,允許我們組合出不同的HFR作業類型來滿足不同需求。HFR的缺點是作業執行期間會禁寫,無法在所有情況下都對用戶透明。? 截止到文章撰寫時(2020年1月中旬),HFR在小米最大離線生產集群已經工作了2個多月。我們用它來拯救不堪重負的NameNode,超過3100萬文件被移動到了空閑的NameSpace,為壓力最大的NameNode釋放了10GB內存。? 后續我們對HFR的計劃是:

  • 將HFR整合到Router服務中,允許小目錄跨NameSpace rename。
  • HFR支持Hadoop3.1 EC(Erasure Code)編碼文件。
  • 通過自動分析用量和接入歷史,結合管理員設定的閾值,實現更智能的負載均衡。

??小米HDFS團隊有很棒的開源氛圍,一直非常積極地參與開源社區,貢獻了大量Patch。我們也在努力將HFR貢獻給社區,

相關Jira:https://issues.apache.org/jira/browse/HDFS-15087。

小米云平臺部,主要分享云存儲、云計算、系統、網絡、運維、私有云、安全、數據庫、內核等內容,歡迎感興趣的朋友們關注!

Nginx 為什么這么快?

上一篇

一份Gartner報告,揭露WAN Edge供應商現狀

下一篇

你也可能喜歡

HFR:在RBF上實現跨NameSpace Rename

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
双色球常规走势图 淮安七星麻将免费下载 什么平台有麻将好友房 体育比赛比分直播 股票涨跌的原理知乎 篮球比分直播90 重庆幸运农场快乐十 小鸡飞蛋吉林麻将软件 500比分完场版 古墓丽影 福彩欢乐生肖 皇冠网即时指数 北单