bitfinex

              大数据

              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}??悸嵌杂谌我馄鹗甲刺琒,当从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完全相同??杉鸖j->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 每周精要将以邮件的形式发放至您的邮箱


              微信扫一扫

              微信扫一扫

              百度|中国纪委国家监委网站|北京纪检监察网|bitfinex注册 | bitfinex平台 | www.baidu.com-百度百科|

              健康遊戲忠告:抵制不良遊戲拒絕盜版遊戲注意自我保護謹防受騙上當適度遊戲益腦沉迷遊戲傷身合理安排時間享受健康生活

              備案號:皖B2-2334451本站www.837996.com所有