ITPub博客

首页 > 大数据 > Hadoop > hadoop源码分析(一) —— namenode 内部关键数据结构简介【转】

hadoop源码分析(一) —— namenode 内部关键数据结构简介【转】

Hadoop 作者:sweetvivian 时间:2011-06-02 21:48:58 0 删除 编辑

概述

本文档目的在于对namenode中各种关键的数据结构进行剖析和解释,以方便更好的对namenode的各种处理逻辑和代码结构进行理解。其中包 括对namenode中Namenode和FSNameSystem的程序代码结构,FSDirectory,BlocksMap, CorruptReplicationMap,excessReplicateMap, UnderReplicatedBlocks,PendingReplictiondBlocks等数据结构的介绍。

1.1 代码结构

1.1.1 NameNode

在HDFS中,namenode的服务提供整个HDFS文件系统的namespace管理,块管理等所有服务,metadata所有的相关服务都是由namenode进程在提供。其中包括  filename->blocksequence (namespace),以及block->machinelist的对应表。其中前者通过fsimage写入到本地文件系统中,而后者是通过每次HDFS启动时,datanode进行blockreport后在内存中重构的数据结构。绝大部分的情况下,namenode服务进程其实都是在被动的接收服务请求 -> 进行相应的操作和更新 –> 进行适当的返回。所以,在HDFS的程序代码中,NameNode类其实只是一个用来接收被动接收调用服务的包装,它实现了ClientProtocol接口,用来接收来自DFSClient的rpc请求;它实现了DatanodeProtocol接口,用来接收来自Datanode的各种服务请求;同时它还实现了NamenodeProtocol,用来提供跟SecondaryNameNode之间的rpc请求和通信。但实际上,对NameNode的rpc调用后面的处理逻辑,以及namespace的bookkeeping,blocksmap的维护,并没有在NameNode的程序结构中包含。真正进行以上数据结构维护的,是HDFS中的FSNamesystem类。对NameNode的各种请求,比如创建,修改,删除,移动,getLocations的操作,在NameNode内部都是通过FSNamesystem提供的接口对内部数据结构进行的访问。

1.1.2 FSNamesystem

在namenode server中,真正提供对各种关键数据结构的bookkeeping,维护,更新,同步,以及各种操作接口的类,实际上是FSNamesystem类。FSNamesystem类中维护了许多个关键的数据结构,这些数据结构中维护了整个HDFS中各种metadata的信息。对HDFS的各种操作,不管操作的请求是来自client,datanode还是secondarynamenode,到最后都会落到FSNamesystem的内部接口中,FSNamesystem根据各种不同的服务请求来更新,维护内部的各种数据结构,以达到HDFS实时状态的更新。同时,对HDFS的各种操作,绝大部分情况下是要涉及到这些关键数据结构的操作,以下便是FSNamesystem各种关键数据结构的详细介绍。

1.2 关键数据结构

1.2.1 FSDirectory

在namenode中,对于HDFS整个文件系统的namespace,也就是以 ”/” 为根的整个目录树的管理,就是通过FSDirectory来管理的。HDFS是会将namespace保存到namenode的本地文件系统的一个叫fsimage的文件中。从该文件中,namenode每次重启都能将整个HDFS的namespace重构。在FSDirectory中,同时也负责对fsimage相关操作。另外,对HDFS的各种操作,namenode都会记录相应的操作日志,以便周期性的将该日志于fsimage进行合并,生成新的fsimage。该日志文件也是在namenode本地文件系统中,叫editlog文件。所以FSDirectory中也负责对editlog的相关操作。

HDFS整个文件系统的namespace在namenode的内存中,是以一颗树的结构来维护的。在HDFS中,不管是目录还是文件,都被看作是INode,如果是目录,则其实际类标识为INodeDirectory,如果是文件,则其相应的类标识为INodeFile,这两个类都是INode的派生类。INodeDirectory中包含一个成员数组变量List children,如果该目录下有子目录或者文件,其子目录或文件的引用就会保存在children列表中。HDFS就是通过这种方式来维持整个文件系统的目录结构。

1.2.2 FsImage

Namenode会将HDFS的文件和目录元数据存储在一个叫fsimage的二进制文件中,每次保存fsimage之后到下次保存之间的所有hdfs操作,将会记录在editlog文件中,当editlog达到一定的大小(bytes,由fs.checkpoint.size参数定义)或从上次保存过后一定时间段过后(sec,由fs.checkpoint.period参数定义),namenode会重新将内存中对整个HDFS的目录树和文件元数据刷到fsimage文件中。Namenode就是通过这种方式来保证HDFS中元数据信息的安全性。

Fsimage是一个二进制文件,当中记录了HDFS中所有文件和目录的元数据信息,在version为-18的hadoop的HDFS image版中,该文件的中保存文件和目录的格式如下:

当namenode重启加载fsimage时,就是按照如下格式协议从文件流中加载元数据信息。从fsimag的存储格式可以看出,fsimage保存有如下信息:

1.         首先是一个image head,其中包含:

a)         imgVersion(int):当前image的版本信息

b)        namespaceID(int):用来确保别的HDFS instance中的datanode不会误连上当前NN。

c)         numFiles(long):整个文件系统中包含有多少文件和目录

d)        genStamp(long):生成该image时的时间戳信息。

2.         接下来便是对每个文件或目录的源数据信息,如果是目录,则包含以下信息:

a)         path(String):该目录的路径,如”/user/build/build-index”

b)        replications(short):副本数(目录虽然没有副本,但这里记录的目录副本数也为3)

c)         mtime(long):该目录的修改时间的时间戳信息

d)        atime(long):该目录的访问时间的时间戳信息

e)         blocksize(long):目录的blocksize都为0

f)         numBlocks(int):实际有多少个文件块,目录的该值都为-1,表示该item为目录

g)        nsQuota(long):namespace Quota值,若没加Quota限制则为-1

h)        dsQuota(long):disk Quota值,若没加限制则也为-1

i)          username(String):该目录的所属用户名

j)          group(String):该目录的所属组

k)        permission(short):该目录的permission信息,如644等,有一个short来记录。

3.         若从fsimage中读到的item是一个文件,则还会额外包含如下信息:

a)         blockid(long):属于该文件的block的blockid,

b)        numBytes(long):该block的大小

c)         genStamp(long):该block的时间戳

当该文件对应的numBlocks数不为1,而是大于1时,表示该文件对应有多个block信息,此时紧接在该fsimage之后的就会有多个blockid,numBytes和genStamp信息。

因此,在namenode启动时,就需要对fsimage按照如下格式进行顺序的加载,以将fsimage中记录的HDFS元数据信息加载到内存中。

1.2.3 BlocksMap

从以上fsimage中加载如namenode内存中的信息中可以很明显的看出,在fsimage中,并没有记录每一个block对应到哪几个datanodes的对应表信息,而只是存储了所有的关于namespace的相关信息。而真正每个block对应到datanodes列表的信息在hadoop中并没有进行持久化存储,而是在所有datanode启动时,每个datanode对本地磁盘进行扫描,将本datanode上保存的block信息汇报给namenode,namenode在接收到每个datanode的块信息汇报后,将接收到的块信息,以及其所在的datanode信息等保存在内存中。HDFS就是通过这种块信息汇报的方式来完成 block -> datanodes list的对应表构建。Datanode向namenode汇报块信息的过程叫做blockReport,而namenode将block -> datanodes list的对应表信息保存在一个叫BlocksMap的数据结构中。

BlocksMap的内部数据结构如下:

如上图显示,BlocksMap实际上就是一个Block对象对BlockInfo对象的一个Map表,其中Block对象中只记录了blockid,block大小以及时间戳信息,这些信息在fsimage中都有记录。而BlockInfo是从Block对象继承而来,因此除了Block对象中保存的信息外,还包括代表该block所属的HDFS文件的INodeFile对象引用以及该block所属datanodes列表的信息(即上图中的DN1,DN2,DN3,该数据结构会在下文详述)。

因此在namenode启动并加载fsimage完成之后,实际上BlocksMap中的key,也就是Block对象都已经加载到BlocksMap中,每个key对应的value(BlockInfo)中,除了表示其所属的datanodes列表的数组为空外,其他信息也都已经成功加载。所以可以说:fsimage加载完毕后,BlocksMap中仅缺少每个块对应到其所属的datanodes list的对应关系信息。所缺这些信息,就是通过上文提到的从各datanode接收blockReport来构建。当所有的datanode汇报给namenode的blockReport处理完毕后,BlocksMap整个结构也就构建完成。

1.2.4 BlockInfo中datanode列表数据结构

在BlockInfo中,将该block所属的datanodes列表保存在一个Object[]数组中,但该数组不仅仅保存了datanodes列表,还包含了额外的信息。实际上该数组保存了如下信息:

上图表示一个block包含有三个副本,分别放置在DN1,DN2和DN3三个datanode上,每个datanode对应一个三元组,该三元组中的第二个元素,即上图中prev block所指的是该block在该datanode上的前一个BlockInfo引用。第三个元素,也就是上图中next Block所指的是该block在该datanode上的下一个BlockInfo引用。每个block有多少个副本,其对应的BlockInfo对象中就会有多少个这种三元组。

Namenode采用这种结构来保存block->datanode list的目的在于节约namenode内存。由于namenode将block->datanodes的对应关系保存在了内存当中,随着HDFS中文件数的增加,block数也会相应的增加,namenode为了保存block->datanodes的信息已经耗费了相当多的内存,如果还像这种方式一样的保存datanode->block list的对应表,势必耗费更多的内存,而且在实际应用中,要查一个datanode上保存的block list的应用实际上非常的少,大部分情况下是要根据block来查datanode列表,所以namenode中通过上图的方式来保存block->datanode list的对应关系,当需要查询datanode->block list的对应关系时,只需要沿着该数据结构中next Block的指向关系,就能得出结果,而又无需保存datanode->block list在内存中。

1.2.5 CorruptReplicationMap

如上所述,namenode中是通过block->datanode list的方式来维护一个block的副本是保存在哪几个datanodes上的对应关系的。保存在datanodes上的block,常常会因为各种各样的原因(磁盘损坏,校验错误等)出错,这种情况下,namenode中会将这些datanode上的block标记为Corrupt状态,并记录该block在哪几台datanode上保存的副本是corrupt的。这些信息,就是保存在CorruptReplicationMap中。CorruptReplicationMap内部其实就是一个Block-> Collection的TreeMap,namenode中通过该数据结构来记录哪些block的哪(几)个副本为corrupt状态,并会在随后的将这些记录的block放入到一个recentInvalidateSets(Map>)中。

在datanode的每次heartbeat过来namenode的时候,namenode就有机会查询该recentInvalidateSets,看是否在该汇报的datanode上有被标记为invalidate的block,如果有,就在heartbeat中返回给该datanode一个cmd,告诉该datanode将该有问题的block进行删除。

1.2.6 UnderReplicatedBlocks

HDFS中的block,通常会对应多个副本,假设某block的副本数是3,那么并不一定在任何时候,该block的可用副本数都能保持为3。原因是集群中随时都有可能会有硬盘损坏,datanode下线等原因。发生这种情况时,某些block的对应的副本就会下降。HDFS将副本数没有达到其期望值的block引用保存在UnderReplicatedBlocks数据结构中。UnderReplicatedBlocks其实是一个list列表,其结构为:ArrayList>。List中的每一个item其实都是一个TreeSet,set中是一系列的block引用。UnderReplicatedBlocks将该list中的block按照优先级来分类。优先级由该block当前副本数和缺少的副本数来决定,也就是说,缺少的副本数越多,标识该block的副本被拷贝到其他datanode上的请求就越紧急,其优先级也就越高。因此,优先级为0的blocks,就保存在优先级为0的TreeSet中,以此类推。

1.2.7 PendingReplicationBlocks

当namenode发现某些block的可用副本数低于其期望副本数时,在一定时期内就会对该block进行副本拷贝的操作,以将其可用副本数提高到期望副本数(通常为3)。而正在进行副本拷贝的block,namenode会将其引用保存在PendingReplicationBlocks中,当该block从一台src datanode拷贝到target datanode的副本拷贝操作时,就会将该block的引用保存在PendingReplicationBlocks中。

在block做副本拷贝时,有些能够很正常的拷贝成功,但是有些拷贝操作因为各种各样的原因,会发生失败,或者超时,默认的超时时间是5分钟。当发生超时时,namenode会将这些block重新添加到neededReplicationBlocks中,以便接下来重新对其进行副本拷贝操作。PendingReplicationBlocks中还有一个后台线程,就是这个线程在不停的检查正在做副本拷贝的block是否有超时的现象。


转载自:淘宝数据平台与产品官方博客  http://www.tbdata.org/archives/1120

<!-- 正文结束 -->

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/11165147/viewspace-1120398/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
下一篇: 没有了~
请登录后发表评论 登录
全部评论