Posted by on | Featured

摘要

随着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 sets Directories Files Blocks Time costs/ms File Size
set 7-7 19608 117649 117649 18,001 28.72TB
set 7-8 37449 262144 262144 30,890 64TB
set 8-9 597871 4782969 4782969 577,360 1.14PB

线上环境  线上环境与测试环境有很大不同，主要是为了保证安全，线上环境我们做了更烦琐的校验，这对HFR速度影响很大，会使其耗时更久。线上的校验需要给NameNode发送大量rpc，每个rpc的耗时也随NameNode当时的ops有波动，所以会有大小差不多的目录耗时却不同的情况。 

下表展示了部分线上环境迁移案例：Table 2: The online cluster performance.

Path Files+Directories Blocks Time costs
/user/h_data_platform/platform/isource 1900000+ 2523910 1166s
/user/h_data_platform/platform/b2cdc 1600000+ 2461348 875s
/user/h_data_platform/platform/fintech 1400000+ 1830326 697s

总结  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。

Tags: ,
Comments are closed.