2.1 内存Tree设计

本章节主要介绍Namenode及其与元数据管理的相关内容。首先介绍Namenode服务的主要作用和启动流程，接着介绍元数据的组成部分——FsImage和Edit Log，然后对元数据在Namenode内存中维护的各个部分及其组成部分进行详细的介绍。

2.1.1 Namenode介绍

HDFS的主要功能是对文件进行存储：一方面数据被保存在某些位置，另一方面在需要的时候数据应该能够被灵活地访问。为了实现这两个方面的需求，HDFS做了很多巧妙的设计。先来说说数据保存。

HDFS中一个完整的文件由两部分组成（见图2-1）：一部分是meta，它由一些被称为Namenode的服务节点管理；另一部分是Block数据块，它由一些被称为DataNode的服务节点管理（关于DataNode会在第3章详细介绍）。

meta可以理解为文件的索引（Index），Block数据块可以理解为真实保存的数据。

Namenode在HDFS中被称为Master节点，主要包括如下功能。

• 管理元（meta）数据。一个集群保存的所有的文件都会在Namenode中保存一份meta视图，以便于对文件的整体管理。

• 处理客户端请求。Client在访问数据时，必须经过Namenode。Client的大多数访问都和数据相关，而元数据都由Namenode管理，因此Client第一步就要和Namenode交互。

2.1.2 Namenode启动

要想启动一个Namenode服务，首先要获取一个已编译完成的包，这里有两种获取方法。

一是从开源网站下载源码，自行编译。编译的方法见https://github.com/apache/hadoop/blob/trunk/BUILDING.txt。

二是从官方网站下载可部署的包下载地址为https://hadoop.apache.org/releases.html。

在${hadoop_home}目录中的启动命令如下：

这条命令本质上是启动一个Namenode服务，将集群已存在的meta数据载入Namenode内存。入口为org.apache.hadoop.hdfs.server.namenode.NameNode#main（）。

1.Namenode启动主流程

Namenode启动过程主要完成了3件事情。

（1）加载预先生成的持久化文件FsImage

FsImage是一种持久化到磁盘上的文件，里面包含了集群大部分的meta数据，持久化的目的主要是为了防止meta数据丢失，也就是在HDFS不可用的情况下还能够保证绝大多数的数据是正常的。这个工作在Namenode服务中有专门的线程去做。FsImage文件最终会被保存在${dfs.namenode.name.dir}/current目录中。

具体实现类为org.apache.hadoop.hdfs.server.namenode.ha.StandbyCheckpointer。

负责做具体工作的异步处理代码如下：

FsImage包含了所有在持久化之前Namenode管理的meta信息，加载这些数据时会按照数据类型逐条、串行处理每一条数据。具体类型如下所示。

• NS_INFO：描述当前namespace中的标识信息。

• STRING_TABLE：描述当前namespace中String Table信息。

• INODE：描述当前namespace中的文件数据。

• INODE_REFERENCE：描述当前namespace中的inode reference信息。

• SNAPSHOT：描述当前namespace中的snapshot信息。

• INODE_DIR：描述当前namespace中的目录数据。

• FILES_UNDERCONSTRUCTION：描述当前namespace中的正在生成文件的信息。

• SNAPSHOT_DIFF：描述当前namespace中存在差异的snapshot信息。

• SECRET_MANAGER：描述当前namespace中和Delegation Token相关的secret信息。

• CACHE_MANAGER：描述当前namespace中的cache信息。

还有一类EXTENDED_ACL用的比较少。以上提到的namespace可以理解为集群的意思。

加载FsImage的主逻辑在FSNamesystem#loadFromDisk（），处理流如下所示。

在loadInternal（）中逐条处理FsImage中的内容，下面是对这个过程的解析：

这里loadxxxx（）分别逐条处理各自类型的数据，然后填充到Namenode内存中的主体结构FSDirectory中。

（2）加载没有完成处理的Edit Log

这一步是紧接第（1）步完成的。

FsImage保存了集群大部分的meta，而且FsImage定期被持久化，对于一个处理在线业务的分布式系统，这样是为了保证存储数据不丢失。还有另外一部分meta被单独持久化，这就是Edit Log。不难理解，Edit Log肯定和事务相关。

几乎每种分布式存储都会涉及数据写入，这个过程中通常都会产生一个事务（Transaction），主要目的是记录本次操作针对哪些数据做了哪种类型的数据更新，然后集群会根据事务类型对数据本身执行操作。注意每种产品针对事务的定义可能有所不同。

HDFS同样存在类似的机制，将Client每一次针对HDFS集群的更新操作都记录为一条事务。每条事务都会被记录并持久化到Edit Log文件中。关于事务会在第6章有更加详细的介绍。

处理Edit Log同样发生在FsImage#recoverTransitionRead（），处理流如下所示。

处理Edit Log数据时，当存在多个需要被处理的log文件时，会逐个处理每个文件，并逐条解析文件中的Transaction数据，之后更新到Namenode内存结构FSDirectory中。加载Edit Log流程如图2-2所示。

有时候将这个过程称为回放（Reply）Edit。

（3）等待Slave节点注册和汇报其所包含的Block数据

第（1）步和第（2）步完成后，意味着meta数据已经初步加载到Namenode，但是还缺少一个对meta的校验过程。校验过程实际就是和真实的数据块（Block）对比，检查meta描述的信息和对应的Block是否一致。

Block数据存在于DataNode节点上，那校验过程如何进行呢？首先是Namenode管理DataNode注册，然后是DataNode全量上报Block。

2.管理DataNode注册

Namenode作为Master节点，除了负责管理数据外，还负责管理资源。这里所说的资源其实就是指对DataNode的管理。DataNode启动后会定期向Namenode发送心跳，以此向Namenode证明自己还处于存活状态。此时Namenode会处理心跳信息，如发现此前没有保存DataNode的信息，这时会通知DataNode做一次注册。注册的目的是为了检测该DataNode是否是“意外节点”（所谓“意外节点”，就是指该DataNode是不是被配置在Namenode的管控之下），再之后的每次心跳就会被正常处理。因此在DataNode注册这件事情上，Namenode是主动管理方，DataNode是被动执行方。

DataNode向Namenode注册如图2-3所示。

DataNode向Namenode注册时，会携带如下信息，Namenode收到后会进行比较。

• SoftwareVersion：当前DataNode服务版本号。

• StorageInfo：DataNode包含的所属集群相关信息，如namespace id、cluster id和layoutVersion。

• DataNodeID：DataNode节点自身信息，如hostname、uuid和port。

DataNode通过RPC向Namenode注册，入口是org.apache.hadoop.hdfs.server.namenode.NameNode RpcServer#registerDatanode（）。

这个工作实际是在FSNamesystem#registerDatanode（）中完成的。

3.DataNode全量上报Block

DataNode向Namenode汇报Block的主要目的有两个：一是Namenode维护集群数据，二是和meta校验。

在Namenode启动过程中，校验meta是一个非常重要的步骤。DataNode向Namenode完成注册后，会强制向Namenode汇报一次全量的Block数据。这里全量的意思是DataNode本地存储的所有Block。

由于一个DataNode上存储的Block可能会很多，并且在实际生产环境下会配置多个磁盘存储，因此这里涉及如何向Namenode汇报Block。通过RPC一次性将所有数据发给Namenode非常占用带宽，而且Namenode处理单个DataNode数据会占用较长时间。因此，针对Block全量上报，有个配置${dfs.blockreport.split.threshold}。它的默认值是100w，即当DataNode存储的Block总量小于100w时，通过一个RPC一次性将数据发给Namenode处理；当Block总量高于100w时，会按照磁盘分批次处理。在实际生产环境下，可根据实际情况适当调小阈值。

DataNode存储的Block数量低于${dfs.blockreport.split.threshold}。

DataNode一次性汇报所有Block如图2-4所示。

DataNode存储的Block数量高于${dfs.blockreport.split.threshold}。

DataNode分磁盘汇报Block如图2-5所示。

Namenode启动后，即可具备接收Client请求的条件。此后一旦有新的数据流入，Namenode会不断填充meta, DataNode上的Block也会不断变化。

作为Master角色，Namenode需要完成很多瞬时状态、持久状态及两种状态切换的操作。例如，Client向Namenode发送一个文件创建的请求，这个过程会比较快速完成；已经创建的文件在一段时间内不会得到任何操作，对应的meta信息会在Namenode保持比较长的时间；Namenode中有一个容器会完成所有瞬时状态和持久状态的簿记工作——FSNamesystem。

FSNamesystem的主要功能如下。

• 盛放BlockManager、DatanodeManager、DelegationTokens和LeaseManager等服务。

• 进入Namenode的RPC请求会被委托至FSNamesystem处理。

• Block上报后被委托进入FSNamesystem中的BlockManager服务。

• 涉及文件信息相关的操作，会被委托进入FSNamesystem中的FSDirectory服务，如权限create。

• 协调Edit Log的记录。

这里的BlockManager主要负责管理各个DataNode上的Block信息，LeaseManager主要负责Client写数据时需要的Lease。以上每一部分在Namenode服务中都极其重要。

2.1.3 meta视图

2.1.2节讲到HDFS中的元（meta）数据都由Namenode管理。本节会进一步介绍meta主要由哪些部分组成。

meta数据是关于文件或目录的描述信息，如文件路径、名称、文件类型等，这些信息被称为元（meta）数据。对文件来说，包括文件的Block、各Block所在DataNode，以及它们的修改时间、访问时间等；对目录来说，包括修改时间和访问权限控制信息，如权限、所属组等。

HDFS中的meta数据采用内存和持久化的方式维护，并随着请求生成。Namenode维护meta数据的流程如图2-6所示。

Namenode以树形结构维护在内存中的meta，被称为内存Tree。每次有新的请求时，都会实时更新内存Tree，同时在Edit Log中产生一条Transaction记录。此外，内存Tree会定期被持久化。

1.内存Tree

内存Tree主要针对存储在HDFS中的数据，其目的主要有两个：一是维护集群中存储的数据的变化状态；二是提供快速检索数据。

存储在HDFS中的文件都是以多副本的形式存放，也就是将一个文件的数据复制多份分别保存在不同的DataNode节点上，这样在出现机器故障时，也有可访问的数据。数据存放在各个数据节点上，必然有不同的状态变化，主要的变化有：

• 数据处于正常的状态，包括数据正在更新或写入、Block校验完整等。

• 数据副本丢失，比如3个副本数据中有1个副本数据因所在节点故障不可用。

• 数据副本剩余，比如由于副本数据丢失而重复复制了数据。

所有的数据都需要Namenode和DataNode紧密协作，DataNode需要经常告知Namenode保存在自身的Block数据的状态变化。DataNode向Namenode反馈自身数据状态，如图2-7所示。

Namenode得到数据状态的过程中，最重要的是从DataNode处获取，DataNode采用定期汇报的形式。此外，Client与Namenode交互时，也会将已完成写入或更新的数据量告知Namenode，进一步加强对数据的校验。

当Client需要访问数据时，需要优先和Namenode交互的一个原因就是Namenode已实时掌握了集群存储的数据，并对这些数据做了有规则的排列，方便快速定位。

2.FsImage

保存在Namenode节点中的完整数据存在于内存中，一旦发生故障，如操作系统宕机、停电，数据会马上消失。也就是由于数据的瞬时性，数据无法长久保存。为了弥补这个不足，Namenode内存中的meta数据会被定期持久化在本地，这种文件被称为FsImage。这样Namenode在重启服务时，加载此前已持久化的FsImage，可以快速回到之前的状态，meta和各种数据状态都将得以重现。

3.Edit Log

虽然FsImage持久化保存了HDFS以往（FsImage持久化之前）的大多数meta和各种数据状态。但是HDFS是一个高可用的系统，一个Namenode服务停止之后会有其他Namenode顶替工作，继续接受Client的请求。这个过程必然会有新的Transaction进入。对于新部分meta会被记录到Edit Log，这样meta不会丢失。Namenode服务启动时，也会加载解析这部分数据，填充到内存，保障了meta的完整性。

Namenode启动时构建meta的流程如图2-8所示。

2.1.4 FsDirectory和INodeMap

meta在Namenode内存中的存储结构是怎样的？这个问题极其重要。因为除了要维护已存储的数据信息外，还要在Client请求时，能够快速定位到请求所需的数据的位置信息。

HDFS采用两种内存结构来实现对meta进行维护。FsDirectory维护集群所有已存储的数据对应的元数据；INodeMap用来快速定位数据所在的存储信息及位置，用于数据索引。

（1）FsDirectory

HDFS中的数据以目录和文件两种方式存在，彼此间构成一种多层级或多元树状结构。例如，系统中维护了如下数据内容。

这是一个最高6级文件结构的视图，其中的“/d=*”“/h*”“/m*”均代表目录，“*.orc”代表目录下的文件。每个文件和目录后面对应的是其所属权限（Permission）、用户和组（User/Group）。

这些数据在内存中的存放形式如图2-9所示。

通过hdfs命令也可以看出数据在HDFS中的meta是Tree：

结果显示如下：

其中，“ls”代表列出/test目录下的所有数据；“drwxr-x-”代表权限；“zhujianghua zhujianghua”代表所属用户和组。

HDFS中内存Tree上的每个节点都称为INode。只是每个节点的类型有所不同。到目前为止，所包含的INode类型如下。

• INodeDirectory：目录节点，代表一个文件目录，一个目录可以有多个子目录或文件。

• INodeFile：文件节点，代表一个文件，文件通常位于某条路径的叶子节点。

• INodeReference：文件引用节点，通常是维持INode之间的关系。

• INodeSymlink：文件符号链接节点，类似Linux系统中的软连接概念。

各类型之间的继承关系如图2-10所示。

（2）INode

INode是基础实现类，内部保存了HDFS文件和目录共有的基本属性，包括当前节点的parent节点、名称、权限和限流（Quota）等。主体字段在INodeWithAdditionalFields中定义。

• id:INode的id。

• name：文件/目录的名称。

• permission：文件/目录权限。

• modificationTime：修改时间。

• accessTime：访问时间。

• parent：父INode。

（3）INodeDirectory

代表目录。一个目录下可以创建多个文件或多个目录，以数组方式存放。一个目录下可以创建的子INode数量受制于Quota限制。默认情况下，可以创建1048576个。

值得注意的是，在HDFS中，即使没有创建任何文件，也有一个默认的“根”目录——Root目录。

（4）INodeFile

代表文件。一个文件由多个Block组成，Block是真正保存物理数据的，分散存在于各个DataNode上。文件节点通常存在于内存Tree的叶子节点中。

（5）INodeReference

代表文件或目录之间的引用。当创建快照、重命名文件、移动文件时，被处理的文件或目录一时无法被清理，这时该文件就会存在多条访问路径。为了正确地访问，就定义了INodeReference，只是为了维持INode之间的引用关系。

（6）INodeSymlink

代表对文件和目录的软引用。类似Linux中的软引用。当前在HDFS中，硬链接并没有被实现。

（7）HDFS Permission

HDFS中的文件和目录权限和Linux或UNIX文件系统中的有点类似，拥有很多POSIX的影子。但HDFS与Linux或其他采用POSIX模型的操作系统之间也存在一些差异。在Linux中，每个文件和目录都有一个用户和组，HDFS本身并无用户和组的概念，它只是从底层操作系统实体导出用户和组。

与Linux文件系统一样，可以为文件或目录的所有者、组成员分配单独的文件权限，可以像Linux中一样使用r（读取文件或列出目录内容）、w（创建或删除文件/目录）和x（访问目录或子目录）权限。也可以使用八进制（如755, 644）来设置文件的模式。值得注意的是，在Linux中，x代表可以执行文件的权限，但是在HDFS中并没有这样的概念。

（8）路径

要使用内存Tree中的某个INode节点时，就要涉及如何表示从Root到目标INode的问题。

例如，想要找的上面的“1.orc”：

/test/d=1/h1=1/1.orc

这是文件1.orc的完整路径和位置。在HDFS中，使用INodesInPath来表示某个INode的具体路径。

INodesInPath定义主要字段的命令如下：

HDFS中表示路径的方法如图2-11所示。

（9）INodeMap

维护所有INode Id和INode之间的映射关系。通过INode Id可以快速查找INode。

说起查询，肯定需要考虑到查找效率问题（当然是越快越好）。在作者经历过的实际线上集群下，单Namespace的元数据超过10亿，可想而知，在这么大量的数据下，遍历速度不高势必会影响业务的访问速度。

在HDFS中，使用了一种非常巧妙的方式维护各个INode间的映射——LightWeightGSet。

（10）LightWeightGSet

这是一种低内存占用的，使用数组存储元素和链表解决冲突的存储结构，如图2-12所示。

这里的每个element都是一个INode。

hash_mask跟LightWeightGSet初始定义长度有关。因为需要经常更新该结构，在LightWeightGSet初始化时，会默认使用堆内存的1%大小。hash_mask=初始长度-1。

INode插入流程如下：

1）确定INode所在数组位置。位置由“INode的hashCode & hash_mask”确定。

2）插入INode。根据确定的位置，排查对应的位置是否有空位，如果没有空位，使用Link的方式挂接即可。

INode查找流程和插入流程差别不大，也是先确定INode的所在位置，然后遍历并对比Link过的INode即可。

2.1.5 文件维护

一款文件系统，其主体有用的数据存储在各个文件中。前面讲到HDFS中的文件是由Block组成的，且一个文件通常有多份副本（默认3副本），这些副本数据分散保存在多个DataNode节点。那这些文件对应的Meta是如何维护的？这是本节所要介绍的重点。

以上文中的目录“/test/d=1/h1=1”为例，该目录存在3个文件，即/test/d=1/h1=1/0.orc，/test/d=1/h1=1/1.orc和/test/d=1/h1=1/2.orc。

每个文件都不大（不超过128MB），都有3个副本。实际的存储位置如图2-13所示。

在正常情况下，“0.orc”“1.orc”“2.orc”会各有3个副本文件，每个副本文件也是由相同数量的Block组成。这些副本通常不会存在于同一个DataNode节点，这样做的目的是防止一个节点在不可用的情况下，仍然可以保障有访问的数据存在。

当然，每个文件由多少Block组成，以及存在于哪些DataNode，也属于meta的一部分，所以维护文件的meta的本质就是维护Block的信息。那这部分数据在内存中是如何维护的？在HDFS中，是由BlockManager来单独管理这部分内容的。BlockManager包含的功能比较强大，除了维护整个集群的Blocks信息，还负责维护Block的相关状态，如节点退役时Block的管理、副本缺失或冗余时Block的管理等。这部分在后面章节中会有介绍。

介绍到这里，想必大家已经比较清楚了。HDFS中主要存储的实体是目录和文件，以文件树状结构存储，每个目录或文件均构成一个树的节点，每个目录都有一定的存储容量限制；文件是数据存储的最主要载体，并且位于树状结构的最末端，文件通常有多个副本数据分散放置于各个数据节点（DataNode）上。

现在已经基本了解了HDFS中“集群-目录-文件-文件块（Block）”之间的关系，如图2-14所示。