CN104008152B - 支持海量数据访问的分布式文件系统的架构方法 - Google Patents

Abstract

本发明公开了一种支持海量数据访问的分布式文件系统的架构方法，该方法基于分布式哈希表，通过对文件路径进行哈希映射获取存取节点。采用完全分布式的无中心化架构设计，新节点通过若干次通信即可加入集群。节点间的寻址采用Kademlia算法，对路由表进行划分并通过异或运算得到节点间的距离以实现最近邻节点的跳转。通过PaxosLease算法选取领导者来处理映射到该节点的操作，以解决一致性问题。文件的实际数据则进行固定大小的分块存储，并冗余备份在若干个节点上，提供安全性以及分布式计算的需求。架构的系统在海量文件处理时能显著地提高处理效率，在较低延迟需求的环境中也可取得较好效果。

Description

支持海量数据访问的分布式文件系统的架构方法

技术领域

本发明涉及分布式文件系统研究领域，特别涉及一种支持海量数据访问的分布式文件系统的架构方法。

背景技术

随着互联网技术的发展，“云计算”正日益受人们重视，它是分布式计算、并行计算、效用计算、网络存储、虚拟化、负载均衡等传统技术的融合而形成的一种新的面向用户的服务型产品概念。而“云存储”又是最为贴近普通网民的云服务之一。

早期的分布式文件系统，文件及其元数据信息没有做冗余备份，一旦其中某台服务器故障，则存储在该服务器上的文件就不可用。而且随着文件数量增加，系统也变得更为庞大，既难扩展也难管理。现代的分布式文件系统则更加注重元数据的分布策略，将文件元数据和数据存储分离，可以提高服务的并发性、可用性，并充分利用集群中实际数据存储机器的磁盘IO。

目前常见的分布式文件系统有GFS、HDFS、Lustre、MogileFS等，其各自适用于不同的领域。最活跃是Hadoop上的HDFS，其架构图如图8所示，其面向的是分布式计算，采用单一元数据服务器的架构，系统简单，适合较大的文件体积，通过追加方式写入的文件往往达到了成百上千GB，将文件进行分块存储。对于分布式数据处理、计算的场景来说，HDFS足够应付，并已有许多成功案例。但是其单个的主节点容易成为瓶颈，而且有单点失败的情况。MogileFS支持大量小文件的读写，可自动复制文件，但是不支持文件的随机读写，对数据库过度依赖，同样存在单点故障。Lustre采用对象存储技术，适合对大文件进行读写，其将大文件分片，通过存储节点上的RAID提供可靠性，故系统不提供多个副本的冗余备份。

发明内容

本发明的主要目的在于克服现有技术的缺点与不足，提供一种支持海量数据访问的分布式文件系统的架构方法，该系统借鉴了各种分布式文件系统的优点，其无中心化架构及冗余备份机制可向上层提供安全可靠的、高效的分布式文件存取服务以及海量的数据访问。

本发明的目的通过以下的技术方案实现：支持海量数据访问的分布式文件系统的架构方法，包括以下步骤：

(1)采用非阻塞的网络通信框架，在Linux系统中，采用epoll选择器。使系统在大量连接及高IO时仍有很高的性能；

(2)采用简单且高效的基于动态代理的远程过程调用(RPC，Remote ProcedureCall)，降低系统复杂性；

(3)与传统的C/S架构类似，客户端通过API访问文件系统，集群中的节点通过以太网实现相互通信，每个节点负责维护路由表、元数据、文件数据。客户端连接任意一个已注册服务的节点即可实现对文件的操作；

(4)文件通过一致性哈希算法映射到相应的节点上，保证文件的分布与节点数目无关，节点的加入与退出对系统的影响和数据的迁移量降到最低，分布式哈希表采用Kademila算法，能最大限度的减少查找文件中的时间消耗；

(5)对大文件分块，文件的数据以及元数据都备份在3个不同的节点上，节点宕机后能迅速切换，保证数据的安全有效；

(6)完全分布式的结构在多个节点上都存在文件备份，对某个文件操作时需要判断真正可操作的备份。系统采用一种优秀的、可快速在多个节点中选举出领导者的算法PaxosLease，由领导者操作后再同步到其他备份。

上述方法的步骤(1)中所述的非阻塞网络通信框架，是基于Java的NIO库MINA，其提供支持TCP/UDP上抽象的事件驱动的API。其也是优秀的过滤器链和和多线程控制器模型，对数据包快速进行封装解包，并交给多线程控制器处理，MINA在完整的RPC调用中耗时约为0.5毫秒。

上述方法的步骤(2)中所述的远程过程调用的传统模式为三层：

(2-1)存根/框架(Stub/Skeleton)层：用于客户端存根(代理)和服务器端框架。

(2-2)远程引用(Remote Refference)层：用于远程引用行为。

(2-3)传输(Transport)层：用于连接的建立和管理，以及远程对象的跟踪。

Java自带的RMI框架内部过多的异常检查，传输时附带不必要的信息，存根的生成也使得代码的管理变得复杂，见图11。而动态的代理模式(见图6)在运行时根据需要动态的生成代理对象，将要调用的方法名、参数通过包装后发送给服务端，服务端接收到请求后查找已经注册的服务实体，调用实体的方法后对返回值和异常包装后发送给客户端。

上述方法的步骤(3)中所述的元数据参考Linux文件系统索引节点和GFS的思想，包括文件的子节点信息、文件大小、权限模式、数据块信息等，形成树形结构，系统中每个文件块的大小为64M，大文件被分块存储，并由文件元数据的块信息链表维护；文件操作API包括创建节点、判断是否存在、创建目录、删除、列出目录文件等与其他操作系统类似的操作。

上述方法的步骤(4)所述Kademila协议算法过程有：

(4-1)机器特征(如IP地址)和文件路径都通过哈希运算得到一个ID，本系统采用了快速且健全的64位CityHash算法，具有均匀、碰撞率低等特点。

(4-2)ID分布在2⁶⁴大小的环上，为寻找与当前key所映射到的ID最邻近的节点，需要计算到已知节点的距离。在Kademila算法中，两个ID间的距离通过异或运算得到：

d(x,y)＝x⊕y

可以知道，异或运算是单向性的。对于任意给定的节点x和距离D，总会存在一个确定的节点y，使得d(x,y)＝D；

(4-3)Kad路由表由称之为K桶的数据结构组成，K桶实际存放的是<K,V>对映射，每个K桶都有一个ID以及它所包含的ID值的距离范围。当插入的<K,V>对足够多时，K桶会分裂，在最终状态下一台机器的Kad路由表为64个。若某个K桶已满，则采用LRU算法替换，有利于临计节点的管理。

(4-4)Kad路由是一棵非平衡的线段二叉树，但是一个节点的Kad路由不会太大，查询的平均时间复杂度为O(logN)，其操作分为插入、删除、查找最接近某ID值的一个。

上述方法的步骤(5)所述的大文件的分块策略参考HDFS中的分块策略，将大于64M的文件进行分块，默认每个分块为64M。每个分块都备份到邻近的3个节点上，文件的写入默认采用的是追加的方式，写入过程为链式的，每个节点接收到数据后向下一个节点传输，数据至少在第一个节点校验成功后认为写入成功，若有分块写入失败，则由检查数据备份的线程发起同步。

上述方法的步骤(6)所述PaxosLease算法具体如下：

当一个提案者(Proposer)提出一个议案，要想该议案获得批准，必须获得超过半数的决议者(Acceptor)的批准，才能同步到所有执行议案的人(Learner)手册上。决议者和消息传递的服务员并不是全职工作的(对应在分布式系统中节点、网络失效)，我们认为只要超过半数(1+n/2)的决议者批准了议案，则该议案获得了通过。

其约束包括：

P1：一个决议者必须接受第一次收到的提案；

P2：一旦一个具有提案值v(提案值是每个提案必须具有的，比如现实中的税收提案，那么提案值可以是税收比率)的提案被批准，那么之后批准的提案必须具有值v。

批准一个提案值v意味着多个决议者接受了该值，因此，可以对P2进行加强：

P2a：一旦一个具有提案值v的提案被批准，那么之后任何决议者再次接受的提案必须具有值v。

由于通信是异步的，约束条件P2a和约束条件P1会发生冲突。如果一个提案值v被批准后，一个提案者和一个决议者从休眠中苏醒，前者提出一个具有新的提案值的提案。根据约束条件P1，后者应当接受，根据约束条件P2a，则不应当接受，这中场景下约束条件P2a和P1有矛盾。于是需要对提议者的行为进行约束：

P2b：一旦一个具有提案值v的提案被批准，那么以后任何提案者提出的提案必须具有值v。

约束条件P2b蕴涵了约束条件P2a，是一个更强的约束，但是难以实现，可以找到一个蕴涵约束条件P2b的约束P2c：

P2c：如果一个编号为n的提案具有提案值v，那么存在一个多数派，要么他们中所有人都没有接受编号小于n的任何提案，要么他们已经接受的所有编号小于n的提案中编号最大的那个提案具有提案值v。

本发明与现有技术相比，具有如下优点和有益效果：

(1)本发明借鉴了各种分布式文件系统的优点，如HDFS的文件分块，在此基础上提出基于哈希映射的分布式文件系统，使每个节点既作为数据访问节点，也作为元数据存储节点，克服传统的单点失败情形，既能提供服务，也能作为路由查询、跳转的中继节点，克服了元数据由单一节点维护的压力，无单点故障的问题，极大提高了系统的稳定性。

(2)本发明是完全分布式架构，每个节点都是廉价PC，充分挖掘其运算与IO能力，节点的退出对数据的迁移和系统的影响降到最低，节点的加入也非常灵活，具有很高的扩展性。

(3)本发明方法中一次文件操作的查找过程采用Kademila算法，所需要的时间是对数级的复杂度，能最大限度的减少查找过程中的时间消耗。对具体的3个副本中的操作通过PaxosLease选举领导者，可靠性强。两个阶段所有操作具有非常低的时间延迟。

附图说明

图1为本实施例两层系统架构示意图。

图2为本实施例RPC通信模型。

图3为本实施例文件数据写入中的传输通道示意图。

图4为本实施例Kademlia算法一次插入K桶的演示图。

图5为本实施例Kademlia算法中一次查找ID的示意图。

图6为动态代理示意图。

图7为本实施例PaxosLease算法一次竞争的过程示意图。

图8为现有技术中Hadoop文件系统HDFS架构图。

图9为MINA网络框架结构图。

图10为RPC结构框架图。

图11为Java自身的RPC框架(RMI)调用示意图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

实施例1

本实施例所述支持海量数据访问的分布式文件系统所采用的硬件网络结构如图1所示，为两层系统架构，具体包括客户端和若干个服务器，每个服务器均包括名称节点(NameNode)和数据节点(DataNode)，与传统的C/S架构类似，客户端通过API访问文件系统，集群中的节点通过以太网实现相互通信，每个节点负责维护路由表，元数据，文件数据。客户端可实现以下操作：A、连接到任意节点；B、连接到具体服务器。客户端通过连接任意一个已注册服务的节点即可实现对文件的操作。

本实施例所述的架构方法基于分布式哈希表，通过对文件路径进行哈希映射获取存取节点。此系统采用完全分布式的无中心化架构设计，新节点通过若干次通信即可加入集群。节点间的寻址算法采用了Kademlia算法，对路由表进行划分并通过异或运算得到节点间的距离以实现最近邻节点的跳转。通过PaxosLease算法选取领导者来处理映射到该节点的操作，以解决一致性问题。文件的元数据通过对文件绝对路径的哈希映射到所对应的节点，并存储在该节点上。元数据对象直接保存在内存中以提供访问服务，同时在硬盘上保存一份镜像以作故障恢复使用。文件的实际数据则进行固定大小的分块存储，并冗余备份在若干个节点上，提供安全性以及分布式计算的需求。该系统在海量文件处理时能显著地提高处理效率，在较低延迟需求的环境中也可取得较好效果。下面结合附图对具体的方法步骤进行描述。

一、本实施例采用基于Java的NIO库MINA，在Linux系统中，采用epoll选择器。MINA的网络框架图如图9所示。

二、采用简单且高效的基于动态代理的远程过程调用(RPC，RemoteProcedureCall)，降低系统复杂性，RPC通信模型如图2所示。

所述的RPC传统模式为三层，如图10所示，包括：存根/框架(Stub/Skeleton)层：用于客户端存根(代理)和服务器端框架；远程引用(Remote Refference)层：用于远程引用行为；传输(Transport)层：用于连接的建立和管理，以及远程对象的跟踪。

三、与传统的C/S架构类似，客户端通过API访问文件系统，集群中的节点通过以太网实现相互通信，每个节点负责维护路由表、元数据、文件数据。客户端连接任意一个已注册服务的节点即可实现对文件的操作。

所述的元数据参考Linux文件系统索引节点和GFS的思想，包括文件的子节点信息、文件大小、权限模式、数据块信息等，形成树形结构，系统中每个文件块的大小为64M，大文件被分块存储，并由文件元数据的块信息链表维护；文件操作API包括创建节点、判断是否存在、创建目录、删除、列出目录文件等与其他操作系统类似的操作。例如在本实施例中建立的两个元数据INode和BlockInfo的数据结构分别为以下的结构，INode包括了fsVersion、path、type、mode、createTime、modifyTime、children、size、blockInfos等信息；BlockInfo包括了path、blocklength、offset、seqNum、replica等信息。

四、文件通过一致性哈希算法映射到相应的节点上，其中分布式哈希表采用Kademila算法，最大限度的减少查找文件中的时间消耗。

所述Kademila协议算法过程有：

(4-1)机器特征(如IP地址)和文件路径都通过哈希运算得到一个ID，本系统采用了快速且健全的64位CityHash算法，具有均匀、碰撞率低等特点。

(4-2)ID分布在2⁶⁴大小的环上，为寻找与当前key所映射到的ID最邻近的节点，需要计算到已知节点的距离。在Kademila算法中，两个ID间的距离通过异或运算得到：

d(x,y)＝x⊕y

可以知道，异或运算是单向性的。对于任意给定的节点x和距离D，总会存在一个确定的节点y，使得d(x,y)＝D；

(4-3)Kad路由表由称之为K桶的数据结构组成，K桶实际存放的是<K,V>对映射，每个K桶都有一个ID以及它所包含的ID值的距离范围。当插入的<K,V>对足够多时，K桶会分裂，在最终状态下一台机器的Kad路由表为64个。若某个K桶已满，则采用LRU算法替换，有利于临计节点的管理。

(4-4)Kad路由是一棵非平衡的线段二叉树，但是一个节点的Kad路由不会太大，查询的平均时间复杂度为O(logN)，其操作分为插入、删除、查找最接近某ID值的一个。

结合附图4、5具体给出Kademila算法一次查找过程如下：

(1)K桶的分裂

每台机器都有一个Kad路由表，K桶实际存放的是<K,V>对映射。每个K桶都有一个ID以及它所包含的ID值的距离范围。当插入的<K,V>对足够多时，K桶会分裂。见图4。

(2)查找ID

设定：

节点ID	路由信息
		0	0,1,11,15
1	1,2,10,15
		2	2,3,11,13
3	3,4,12,14
		4	4,5,12,13
5	5,6,13,15

6	6,7,12,14
		7	7,8,10,12
8	8,9,11,13
		9	3,9,10,15
10	0,6,10,11
		11	0,7,11,12
12	0,9,12,13
		13	1,8,13,14
14	2,7,14,15
		15	0,9,12,15

在本实施例中，需要从节点0出发，查找节点13，如上表所示，结合图5，查找过程如下：

a)在节点0，通过findNear(寻找邻近点)操作找到0、11、15这三个节点可能知道节点13。其中0已访问过，不再访问。

b)从节点11获取到0、11、12；从节点15获取到0、12、15。其中0、11、15这三个节点已经访问过，不再访问。剩余节点12作下一次跳转。

c)从节点12中获得了命中节点13，并获得了节点13的IP值。

由此可见，在Kad网络中进行ID查找所需的RPC请求次数不超过logN次，并且随着运行时间的增加，Kad的路由信息会更加丰富，邻近节点会更加清楚彼此的情况，而热门的远端节点也能得以信任并保存。在理想情况下，通过1到2次通信就能完成节点查找，这是其他DHT技术所不具备的优势。

五、对大文件分块，文件的数据以及元数据都备份在3个不同的节点上，节点宕机后能迅速切换，保证数据的安全有效。

所述大文件分块的策略参考HDFS中的分块策略，将大于64M的文件进行分块，默认每个分块为64M。每个分块都备份到邻近的3个节点上，如图3所示，文件的写入默认采用的是追加的方式，写入过程为链式的，每个节点接收到数据后向下一个节点传输，数据至少在第一个节点校验成功后认为写入成功，若有分块写入失败，则由检查数据备份的线程发起同步。

六、系统采用一种优秀的、可快速在多个节点中选举出领导者的算法PaxosLease，由领导者操作后再同步到其他备份。算法步骤如下：

当一个提案者(Proposer)提出一个议案，要想该议案获得批准，必须获得超过半数的决议者(Acceptor)的批准，才能同步到所有执行议案的人(Learner)手册上。决议者和消息传递的服务员并不是全职工作的(对应在分布式系统中节点、网络失效)，我们认为只要超过半数(1+n/2)的决议者批准了议案，则该议案获得了通过。

下面结合附图7具体给出PaxosLease算法过程如下：

1)提案者希望获得一个T(T<M)秒的lease。首先它需要准备一个提案编号[request.ballotNumber]，并发送到决议者的多数牌上。

2)决议者在接收到一个请求的时候，判断请求的提案编号[request.ballotNumber]是否大于本机状态中承诺的最大提案编号[state.highestPromised]。如果小于，决议者可以忽略请求或发送回一个拒绝响应。如果是等于或大于，决议者构造一个Prepare Response，其中包含了目前的已批准的决议[state.acceptedProposal]，它为空或目前的leader。另外，决议者将本地的最高承诺编号设置为请求所带来的提案编号，并将最高承诺编号连同目前已接受的决议发回给提案者。

3)提案者检验从决议者发回的prepare response，如果决议者的多数派回复的已接受提案为空，表示它们可以接受一个新提案，提案者把自己当作lease的拥有者，也就是leader，并开启一个倒计时T，lease将在时间T之后失效。提案者将倒计时T、决议编号以及提案值组成propose request发送到所有决议者。

4)决议者在收到propose request后，检查编号[request.ballotNumber]是否大于本机状态所承诺的最大编号。如果小于，则忽略或回发一个拒绝响应。如果等于或大于，决议者接受提案：设置最大提案编号、启动倒计时T以及设置lease拥有者(leader)。然后，构造propose response并回发，其中包含了决议编号。在倒计时超时之后，本地状态的lease拥有者设置为空。除非系统重启，否则决议者不会重设他们的最高承诺编号。

5)提案者检验所回收的propose response，如果决议者的多数派回复接受提案，则提案者拥有lease直到在第3步设置的倒计时超时。提案者接收到多数派的回复时，将自己的状态转成“拥有lease”。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

Claims (8)

1.支持海量数据访问的分布式文件系统的架构方法，其特征在于，包括以下步骤：

(1)采用非阻塞的网络通信框架，在Linux系统中，采用epoll选择器；

(2)采用基于动态代理的远程过程调用；所述的远程过程调用的传统模式为三层：

(2-1)存根/框架层：用于客户端存根/代理、服务器端框架；

(2-2)远程引用层：用于远程引用行为；

(2-3)传输层：用于连接的建立和管理，以及远程对象的跟踪；

步骤(2)中所述的动态代理模式为：运行时根据需要动态的生成代理对象，将要调用的方法名、参数通过包装后发送给服务端，服务端接收到请求后查找已经注册的服务实体，调用实体的方法后对返回值和异常包装后发送给客户端；

(3)客户端通过API访问文件系统，集群中的节点通过以太网实现相互通信，每个节点负责维护路由表、元数据、文件数据；客户端连接任意一个已注册服务的节点即实现对文件的操作；

(4)文件通过一致性哈希算法映射到相应的节点上，分布式哈希表采用Kademila算法；节点间的寻址算法采用了Kademlia算法，对路由表进行划分并通过异或运算得到节点间的距离以实现最近邻节点的跳转；

(5)对大文件分块，文件的数据以及元数据都备份在若干个不同的节点上；所述对大文件分块的步骤为：将大于64M的文件进行分块，默认每个分块为64M；每个分块都备份到邻近的3个节点上，文件的写入默认采用的是追加的方式，写入过程为链式的，每个节点接收到数据后向下一个节点传输，数据至少在第一个节点校验成功后认为写入成功，若有分块写入失败，则由检查数据备份的线程发起同步；

(6)完全分布式的结构在多个节点上都存在文件备份，对某个文件操作时采用PaxosLease算法在多个节点中选举出领导者，由领导者操作后再同步到其他备份。

2.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(1)中所述的非阻塞的网络通信框架，是基于Java的NIO库MINA，其提供支持TCP/UDP上抽象的事件驱动的API，对数据包进行封装解包，并交给多线程控制器处理。

3.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(3)中所述的元数据参考Linux文件系统索引节点和GFS的思想，包括文件的子节点信息、文件大小、权限模式、数据块信息，形成树形结构，系统中每个文件块的大小为64M，大文件被分块存储，并由文件元数据的块信息链表维护；文件操作API包括创建节点、判断是否存在、创建目录、删除、列出目录文件的操作。

4.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(4)所述Kademila算法步骤如下：

(4-1)机器特征和文件路径都通过哈希运算得到一个ID；

(4-2)ID分布在2⁶⁴大小的环上，为寻找与当前key所映射到的ID最邻近的节点，需要计算到已知节点的距离，在Kademila算法中，两个ID间的距离通过异或运算得到：

<mrow> <mi>d</mi> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>)</mo> </mrow> <mo>=</mo> <mi>x</mi> <mo>&amp;CirclePlus;</mo> <mi>y</mi> <mo>;</mo> </mrow>

异或运算是单向性的，对于任意给定的节点x和距离D，总会存在一个确定的节点y，使得d(x,y)＝D；

(4-3)Kad路由表由称之为K桶的数据结构组成，K桶实际存放的是<K,V>对映射，每个K桶都有一个ID以及它所包含的ID值的距离范围，当插入的<K,V>对足够多时，K桶会分裂，在最终状态下一台机器的Kad路由表为64个；若某个K桶已满，则采用LRU算法替换；

(4-4)Kad路由是一棵非平衡的线段二叉树，其操作分为插入、删除、查找最接近某ID值的一个。

5.根据权利要求4所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(4-1)中机器特征和文件路径都通过64位CityHash算法得到一个ID。

6.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(6)所述PaxosLease算法具体如下：

当一个提案者提出一个议案，要想该议案获得批准，必须获得超过半数的决议者的批准，才能同步到所有执行议案的人手册上；其约束包括：

P1：一个决议者必须接受第一次收到的提案；

P2：一旦一个具有提案值v的提案被批准，那么之后批准的提案必须具有值v。

7.根据权利要求6所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，对上述约束条件P2进行进一步约束：

P2a：一旦一个具有提案值v的提案被批准，那么之后任何决议者再次接受的提案必须具有值v；

同时，对提议者的行为进行约束：

P2b：一旦一个具有提案值v的提案被批准，那么以后任何提案者提出的提案必须具有值v。

8.根据权利要求7所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，约束包括：

P2c：如果一个编号为n的提案具有提案值v，那么存在一个多数派，要么他们中所有人都没有接受编号小于n的任何提案，要么他们已经接受的所有编号小于n的提案中编号最大的那个提案具有提案值v。