KFS文件系统的MetaServer元数据管理采用的是B+树方式，下面将结合其源码，对KFS MetaServer中元数据的组织形式及有关实现细节进行分析。
1. 相关源码文件
KFS MetaServer元数据管理的代码所在目录为kfs-[version]/src/cc/meta，其中，相关的源码文件有：
（1）meta/base.h：KFS元数据metadata中各节点的基础类，包括的类：类Key、类MetaNode，它们分别代表B+树种存储的数据、所有B+树节点的公共基础信息。
（2）meta/meta.h和meta/meta.cc：封装了metadata的基本数据定义，包括：类Meta、类MetaDentry、类MetaFattr和类MetaChunkInfo，它们分别代表文件系统中的目录项、文件或目录的属性项、对于一个文件偏移（file offset）的Chunk信息。
（3）meta/kfstree.h和meta/kfstree.cc：封装了对B+树中内部节点Node的各种操作及Tree的基本操作（与文件系统无关，B+树底层的实现），如插入节点、删除节点等。
（4）meta/kfsops.cc：封装了使用B+树存储KFS文件系统，实现的相关基本操作，如创建文件、删除文件、创建目录、删除目录等（作为Tree的实现）。
（5）meta/request.h和meta/request.cc：封装了对ChunkServer或KfsClient发出的meta data请求的处理，通过Tree metatree执行相应的操作，实现对KFS文件系统各种基本操作的调用。
2. 为什么选用B+树
KFS的文件系统采用的是B+树，那么为什么选用B+树而不是B-树呢？这里做一个简单的分析：
2.1 B-树
B-树的定义：
B-树是一种平衡多路查找树，一棵m阶的B-树，或者是一颗空树，或者是满足下列特征的m叉树：
（1）树中每个节点至多有m棵字数；
（2）若根节点不是叶子结点，则至少有2棵子树；
（3）除根之外的所有非终端结点，则至少有[m/2]棵子树；
（4）所有的非终端结点中包含下列信息数据：(n, p0, k1, p1, k2, p2, ..., kn, pn)，
其中：ki为关键字，且ki （5）所有叶子结点均在同一层。 B-树的检索： 从根结点开始，对结点内的有序关键字序列进行二分查找，如果命中，则直接结束查找过程；否则，进入查询关键字所属范围的儿子结点进行查找。重复以上过程，直到所对应的儿子指针为空，或已经是叶子结点。 B-树的特性： （1）关键字集合分布在整颗树中； （2）任何一个关键字出现且只出现在一个结点中； （3）搜索有可能在非叶子结点结束； （4）其搜索性能等价于在关键字全集内做一次二分查找； （5）自动层次控制。 2.2 B+树 B+树的定义： B+树也是一种平衡多路查找树，它是应文件系统所需而出的一种B-树的变型树。一颗B+树满足以下条件： （1）每个非终端结点至多有m颗子树； （2）除根结点外，其他每个非终端结点至少有[(m+1)/2]颗子树； （3）根结点至少有2颗子树； （4）有n棵子树的结点中含有n个关键字； （5）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接； （6）所有的非终端结点可以看成是索引部分，仅包含其各个子结点中的最大关键字及指向子结点的指针。 通常来说，B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。 B+树的检索： B+树的检索方式分为两种： （1）一种是从指向关键字最小的叶子结点的头指针开始，进行顺序查找； （2）一种是从指向根结点的头指针开始，进行随机查找：与B-树基本相同，等价于在关键字全集做一次二分查找，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中）。 B+树的特性： （1）所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的； （2）检索时只有在叶子结点命中，不可能在非叶子结点命中； （3）非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层； （4）更适合文件索引系统。 2.3 B+树与B-树的比较 通过对B-树和B+树的定义及特性的了解，对两者进行比较： （1）占用空间大小方面： B-树的非叶子节点中含有大量的关键字信息，占用的空间相对比较大； B+树中只有叶子节点中才有关键字信息，非叶子节点并没有指向关键字具体信息的指针，占用的空间相对比较小。 （2）检索路径长短方面： 由于B+树的所有关键字都分布在叶子节点上，其他非叶子节点都是索引部分，因此树阶数（即树高）要比B-大，检索时要经过的路径就多，运算时间相对长一些； 由于B-树的关键字分布到各个节点上，相对于B+树中完全分布到叶子节点上来说，分散分布的阶数自然要小，因此B-树的树阶数要比B+小，查找要经过的路径相对比较少，运算时间相对短一些。 对于文件系统的设计来说，最关键的瓶颈在于磁盘IO操作，如果占用的磁盘空间少的话，IO操作耗时自然就少。而真正检索内存中的数据结构（如B+树、B-树）的过程中，运算时间相对于磁盘IO操作来说要小的多，即内存的检索时间不是主要的瓶颈之处。 因此，虽然对于同阶的B-树和B+树，B+树的树高和平均检索长度均大于B-树 ，但实际上，检索过程中，最耗时的操作是磁盘IO操作，而B-树占用的空间相对较大，IO操作时劣势明显。由于B+树的非叶子结点无记录信息，只有索引，同样大小磁盘空间就可以存放更多的索引信息，检索访盘次数反而少，速度也就比B-树快。 2.4 选择B+树 B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引，原因在于： （1）磁盘读写代价低：即使B-树的运算时间相对于B+树来说较短，但由于磁盘IO操作方面的劣势，导致其总体上效率不如B+树。 （2）查询效率更稳定：B+树中任何关键字的查找都必须经历从根结点到叶子结点，因此所有关键字查询的路径长度相同，每一个数据的查询效率相当。 3. 元数据组织结构 在KFS文件系统MetaServer元数据的实现中，有图示几种类型的B+树节点： （1）MetaNode: 所有叶节点和内部节点的公共基础类，其中记录了不同树节点的类型信息。 （2）Node：表示内部节点，其中记录了树种内部节点的各种操作。 （3）Meta: 表示叶节点，而具体来说，不同的叶节点有： MetaDentry: 文件目录项（Directory entry），实现从文件名到文件id的映射。 MetaFattr: 文件或目录属性，相当于KFS中的一个inode节点。 MetaChunkInfo: 对于一个文件偏移（file offset）的Chunk信息。 3.1 MetaNode 成员变量： MetaType type; //节点类型值int flagbits; //标志位 构造函数： MetaNode(MetaType t) //初始化type=t, flagbits=0MetaNode(MetaType t, int f) //初始化type=t, flagbits=f 3.2 Node 成员变量： int count; //孩子节点个数Key childKey[NKEY]; //孩子的keyMetaNode *childNode[NKEY]; //孩子节点Node *next; //下一个相邻节点 构造函数： Node(int f) //初始化MetaNode中的节点类型type=KFS_INTERNAL，flagbits=f 3.3 Meta 成员变量： fid_t fid; //文件fid 构造函数： Meta(MetaType t, fid_t id) //初始化MetaNode中的节点类型信息type=t，及自身的fid=id 3.4 MetaDentry 成员变量： fid_t dir; //父目录的fidstring name; //目录项的名称fid_t fid; //目录项的文件id 构造函数： MetaDentry(fid_t parent, string fname, fid_t myID) 举例说明：通过Dentry结构实现/root/1.txt的查找过程： (1) 获取”/”的fid=2 dir=2, name=“/”, fid=2 (2) 获取”root”的fid=8 dir=2, name=“root”, fid=8 dir=2, name=“usr”, fid=6 (3) 获取”1.txt”的fid=12 dir=8, name=”1.txt”, fid=12 dir=8, name=”2.txt”, fid=13 dir=8, name=”3.txt”, fid=14 由以上查找过程可知，/root/1.txt的fid为12。 3.5 MetaFattr 成员变量： FileType type; //类型（文件或目录）int16_t numReplicas; //一个文件要求的备份数struct timeval mtime; //修改时间struct timeval ctime; //属性变更时间struct timeval crtime; //创建时间longlong chunkcount; //chunk数目off_t filesize; //文件大小 构造函数： MetaFattr(FileType t, fid_t id, int16_t n)MetaFattr(FileType t, fid_t id, struct timeval mt, struct timeval ct, struct timeval crt, longlong c, int16_t n) 3.6 MetaChunkInfo 成员变量： chunkOff_t offset; //chunk在文件中的偏移chunkId_t chunkId; //chunk的标识符idseq_t chunkVersion; //chunk的版本号 分布式文件系统KFS源码阅读与分析（二）：MetaServer元数据持久化 KFS文件系统的MetaServer元数据的持久化采用的是checkpoint + log方式，下面将结合其源码，对KFS MetaServer中元数据的持久化机制及其实现细节进行分析。 1. 相关源码文件 KFS MetaServer元数据持久化所涉及的代码所在目录为kfs-[version]/src/cc/meta，其中，KFS元数据持久化的相关源码如下： （1）meta/statup.cc: 负责KFS的启动，在启动过程中处理checkpoint和log。 （2）meta/checkpoint.cc: 负责metadata的checkpointing操作。 （3）meta/restore.cc: 从已保存的checkpoint重新构建metatree（以B+树的方式组织）。 （4）meta/logger.cc: 为metadata的更新做日志记录操作。 （5）meta/replay.cc: 在checkpoint恢复之后，重做log日志文件中的所有操作。 （6）meta/kfstree.h: 构建一个新的metatree，即初始化根目录为”/”。 2. checkpoint和log机制 Log（日志）通常是系统或者软件对已完成的某种处理操作的记录，以便将来用作系统恢复，一般来说是文本格式。Checkpoint（检查点）机制是将内存中被修改的数据块与磁盘上的数据文件进行同步的一种数据持久化方式。 在KFS的元数据持久化中，之所有采用checkpoint + log的方式，本人觉得主要出于以下考虑： （1）通过记录必要的Checkpoint（检查点），保证将文件系统元数据按照序列化的要求，永久持久化存储到磁盘上，从而保证内存和硬盘上的数据的同步与一致；当下次系统恢复时，直接按照反序列化的要求进行还原，快速重新构建KFS的元数据metatree树。 （2）通过checkpoint（检查点）和log（日志）相结合，缩短KFS系统的启动恢复时间。在系统恢复时，首先将系统恢复到最近一次的checkpoint状态（即重新构建B+树），然后，只需将最近一次checkpoint之后的log中的操作进行redo即可，而不是所有log中的所有操作进行redo，从而有效缩短系统恢复时间。 3. 元数据的持久化 在KFS中，log操作是由logger.cc自动完成的，默认为每隔10分钟做一次log（写切换）；checkpoint操作是由checkpoint.cc实现，但是是通过logcompactor_main.cc的离线操作手动完成的，其main函数的工作过程如下： 加载log和checkpoint文件的目录； 恢复最近一次的checkpoint文件； 重做最近一次checkpoint之后的所有logs； 将metatree中所有叶节点写入新的checkpoint文件中。 4. 元数据加载过程 KFS文件系统停止时，MetaServer的元数据被持久化存储到物理磁盘上（checkpoint文件和log文件）；当KFS下次启动时，这些持久化后的数据会被KFS MetaServer启动程序所加载，相关方法的调用关系如图中所示： 其中， （1）KFS启动后，将日志目录logdir和checkpoint目录cpdir等信息，传给KFS::kfs_startup()函数，该函数中首先会调用KFS::logger_setup_paths()设置KFS的日志目录； （2）然后，KFS::kfs_startup()函数会继续调用KFS::checkpointer_setup_paths()设置KFS的checkpoint目录； （3）接下来，KFS::kfs_startup()函数会继续调用KFS::setup_initial_tree()函数，初始化MetaServer的B+树metatree，分为以下两种情况： （4.1）如果存在最近的checkpoint文件，则调用Restorer::rebuild()函数，根据加载checkpoint文件，初始化后构建metatree树； （4.2）否则，则调用KFS::metatree.new_tree()函数，初始化一个新的metatree树,只包含根目录”/”，并设置与其相关联的"."和".."链接项； （5）完成之后，回到KFS::kfs_startup()函数中，调用Replay::playAllLogs()函数，重做最近一次checkpointing之后的所有日志中的操作； （6）在KFS::kfs_startup()函数中，调用KFS::logger_init()函数，启动记录日志，设置日志轮转的间隔时间； （7）在KFS::kfs_startup()函数中，调用KFS::checkpointer_init()函数，初始化checkpoint。 至此，完成了KFS文件系统中持久化后的元数据的恢复过程。 分布式文件系统KFS的MetaServer和Client采用服务器/客户端模型，MetaServer和Client之间的通讯是通过RPC机制来实现的。这里介绍下KFS中MetaServer端的RPC实现机制。 1. RPC相关类 下图所示为MetaServer端的RPC相关实现类： 1、NetDispatch （1）启动MetaServer端的epoll主循环； （2）通过调用gNetDispatch.Start(gClientPort, gChunkServerPort)，在指定的端口监听来自Client和ChunkServer的RPC请求： 启动ClientManager的接收者acceptor； 启动ChunkServerFactory的接收者acceptor。 2、NetManager （1）通过epoll机制，维护一组NetConnection对象；当NetConnection状态发生变化时，调用其中的KfsCallbackObj的回调函数； （2）同时实现了一个定时器机制。 3、NetConnection （1）将KfsCallbackObj和TcpSocket关联起来，代表来自客户端的一个连接； （2）当TCP连接的状态发生变化时，KfsCallbackObj的回调函数将会被调用执行。 4、Acceptor （1）从Client/ChunkServer接收新的连接，然后创建一个新的NetConnection与这个新连接关联起来。NetConnection中含有相关的ClientSM/ChunkServer KfsCallbackObj，而ClientSM/ChunkServer KfsCallbackObj通过IAcceptorOwner的CreateKfsCallbackObj()方法被创建； （2）继承于KfsCallbackObj，回调函数是Acceptor::RecvConnection： 一个Acceptor含有一个相关的NetConnection； 一个Acceptor含有一个成员变量mAcceptorOwner指向ClientManager或ChunkServerFactory。 5、IAcceptorOwner （1）维护一个Acceptor，并提供CreateKfsCallbackObj()接口创建KfsCallbackObj。 6、ClientManager （1）继承于IAcceptorOwner； （2）含有一个Acceptor，用于接收新的连接； （3）含有CreateKfsCallbackObj()方法，用于返回一个ClientSM KfsCallbackObj与Client的连接请求关联起来。 7、ChunkServerFactory （1）继承于IAcceptorOwner； （2）含有一个Acceptor，用于接收新的连接； （3）含有CreateKfsCallbackObj()方法，用于返回一个ChunkServer KfsCallbackObj与ChunkServer的连接请求关联起来。 8、ClientSM （1）继承于KfsCallbackObj，回调函数是HandleRequest()； （2）用于与一个Client连接建立关系，处理Client发起的请求。 9、ChunkServer （1）继承于KfsCallbackObj，回调函数是HandleHello()； （2）用于与一个ChunkServer连接建立关系，处理ChunkServer发起的hello消息。 10、KfsCallbackObj （1）调用SetHandler()设置回调函数，当外部事件发生时，调用HandleEvent()进行回调处理。 2. 请求处理过程 下图所示为MetaServer端的RPC请求处理过程的时序图： KFS启动时，将RPC的各种请求操作映射到不同的处理函数上：kfs_startup (startup.cc) > initialize_request_handlers (request.cc) > setup_handlers (request.cc)。 更进一步来分析一下，以KfsClient与MetaServer之间的RPC为例，KfsClient与MetaServer建立RPC连接后，ClientSM作为KfsClient与MetaServer之间RPC请求的代理，ClientSM负责接收并转发来自KfsClient的各种不同Request信息，处理后负责向KfsClient写Response信息，RPC请求的处理过程如下图所示（以MetaLookup为例，图中详细展示了相关的类及方法的调用关系）： 分布式文件系统KFS源码阅读与分析（四）：RPC实现机制（KfsClient端） 上一篇博客介绍了KFS中RPC实现机制MetaServer端的实现，下面接着介绍一下KfsClient端的实现框架。 KfsClient是为应用程序暴露的接口类，它是在应用程序代码和KFS Servers（MetaServer和Chunkserver）之间起着桥梁的作用，对于一个MetaServer，只能有一个KfsClient。KfsClientFactory单态工厂类负责为不同的MetaServer创建KfsClient。 KfsClientImpl是KfsClient的实现类，负责实际地与MetaServer的RPC请求的交互，如目录操作（cd、mkdir、rmdir、readdir等），文件操作（create、remove、rename等）。 FileTableEntry缓存已打开的文件/目录的句柄，包括当前的文件偏移（FilePosition对象），文件属性信息、chunk属性的集合（ChunkAttr对象）、chunk的缓存（ChunkBuffer对象），打开模式等。 FilePosition记录文件指针的位置，包括两个方面：文件的offset偏移被转换为一个chunk号及在chunk内的偏移量。为了提高性能，客户端对读写进行了缓存，存储的是当前chunk中的数据，这是通过PendingChunkRead来实现的，而缓存的是对应的FileTableEntry中的ChunkBuffer。 ChunkAttr包含chunk server的位置，chunk id，大小，版本号等基本属性信息。 ChunkBuffer是为了加速小的读写操作而设置的buffer，从当前chunk缓存一块数据。 PendingChunkRead用于chunk的预读操作：向chunk server发起读请求；从chunk server接收数据；通过重置与chunk server的连接，取消读请求。 下图概括地展示了这些类之间的关系： （1）KfsClient中包含了一个代理类KfsClientImpl； （2）KfsClientImpl中维护了一个FileTableEntry的集合，记录所有已打开的文件/目录的句柄； （3）FileTableEntry中通过ChunkAttr缓存chunk属性信息（如chunk位置），通过FilePosition缓存当前chunk信息，通过ChunkBuffer对当前chunk进行buffer操作； （4）ChunkAttr记录chunk server位置和chunk id等属性信息； （5）FilePosition通过PendingChunkRead进行预读操作。