posts - 15, comments - 10, trackbacks - 0, articles - 0

KFS代码分析1(meta内存结构)

Posted on 2013-10-23 01:36 whspecial 阅读(1204) 评论(0)  编辑 收藏 引用 所属分类: KFS分析

此处的KFS是指Kosmos distributed file system,代码位于http://sourceforge.net/projects/kosmosfs/,之后会写几篇相关的文章,以供后来者参考。

KFS里Meta的内存结构主要是一棵B+树,保存在内存里,具体分析如下:

B-树,B+树的定义

关于这些树的定义,最好还是参考算法导论等经典书,网路上的信息有些不是很准确,为了方便大家还是贴一个链接:

http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

KFS为何选用B+树而非B树?

这是我个人的理解:

虽然B树可以在非叶子节点命中,会缩短一些平均查找长度,但是B+树在这种应用一个优势就是每个节点都有指向next节点的指针,对于范围查询或者遍历操作很适合。对于文件系统的一个ls某个子目录的需求,用B+树可以较高效的解决。

KFSB+树的类图


MetaNode
base class for both internal and leaf nodes

Metabase class for data objects (leaf nodes)

Nodean internal node in the KFS search tree

MetaChunkInfochunk information for a given file offset

MetaDentry Directory entry, mapping a file name to a file id

MetaFattrFile or directory attributes

各节点的介绍

1Meta类是子节点的父类,其最主要的成员变量是fid

有三个叶子节点:MetaChunkInfoMetaDentryMetaFattr

2MetaDentry实现从文件名到fid的映射,对于每个文件(目录)都拥有1MetaDentry

成员变量包括:

dir:文件父目录的fid

namedentry的名称,实际就是文件名

3MetaFattr实现从fid到文件属性的映射,对于每个文件(目录)都拥有一个MetaFattr

成员变量包括:

Type:文件还是目录

numReplicas:文件有几份副本

mtime:修改时间

ctime:属性修改时间

crtime:文件创建时间

chunkcount:连续的chunk数目

filesize:文件大小

nextChunkOffset:最后一个chunk在文件的所处的offset

mode_t mode:文件属性(rwx位)

key:由KFS_FATTRfid来构成,可以通过fid直接找到保存文件属性的节点。

4MetaChunkInfo标志某个文件对应的chunk信息,如果一个文件包含多个chunk,那么需要有多个MetaChunkInfo

成员变量包括:

offsetchunk在文件中的偏移量,因为一个文件可能由多个chunk组成

chunkIdchunkid

chunkVersionchunkversion

5Node实现的是B+树的内部节点,这种节点仅仅作为索引用途,存储实际元数据信息的节点位于最底部的叶子节点。

成员变量包括:

NKEY = 32:每个节点最多拥有的关键字数目,实际上也就是最多拥有的子节点数目,如果多余这个值节点进行分裂

NSPLIT = NKEY / 2:分裂之后每个节点的关键字数目

NFEWEST = NKEY - NSPLIT:每个节点最少拥有的关键字数目,如果少于这个值两个节点进行合并

count:节点实际拥有的关键字数目

Key childKey[NKEY]:节点存储的关键字列表

MetaNode *childNode[NKEY]:节点指向子节点的指针列表

Node *next:指向下一个同级节点的指针

实际上每个内部节点的阶数为32,可以有32个子节点,而每个叶子节点只保存一个key值。

三类子节点在B+树中如何分布?

可以想象,必定是将同一类的节点聚集在一起。因此对于排序函数就是先比较节点类型,然后再对节点内部的成员变量进行比较。MetaDentry是根据dir(父目录的id),MetaFattr是根据fidMetaChunkInfo是根据idchunkId来排序。

一个不太相关的思考

看上面的三类子节点,我们可以发现chunk的位置信息并没有保存在B+树里,它是单独保存在一个Map数据结构里的,也不会在meta server里进行持久化,而是每次chunk启动时向meta server来报告。之所以不做持久化,可以这样来理解:

只有Chunk服务器才能最终确定一个Chunk是否在它的硬盘上。Chunk服务器的错误可能会导致Chunk自动消失(比如,硬盘损坏了或者无法访问了),亦或者操作人员可能会重命名一个Chunk服务器,还是由chunk server来报告比较靠谱。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理