(10)申请公布号 (43)申请公布日 2014.08.27
C N 104008152
A (21)申请号 201410216506.6
(22)申请日 2014.05.21
G06F 17/30(2006.01)
(71)申请人华南理工大学
地址510640 广东省广州市天河区五山路
381号
(72)发明人董敏 金泽豪 毕盛
(74)专利代理机构广州市华学知识产权代理有
限公司 44245
代理人
蔡茂略
(54)发明名称
方法
(57)摘要
本发明公开了一种支持海量数据访问的分布
式文件系统的架构方法，该方法基于分布式哈希
采用完全分布式的无中心化架构设计，新节点通
过若干次通信即可加入集。节点间的寻址采用
Kademlia 算法，对路由表进行划分并通过异或运
算得到节点间的距离以实现最近邻节点的跳转。
通过PaxosLease 算法选取领导者来处理映射到
该节点的操作，以解决一致性问题。文件的实际数
据则进行固定大小的分块存储，并冗余备份在若
干个节点上，提供安全性以及分布式计算的需求。
架构的系统在海量文件处理时能显著地提高处理
效率，在较低延迟需求的环境中也可取得较好效
果。
(51)Int.Cl.
权利要求书2页 说明书7页 附图6页
(19)中华人民共和国国家知识产权局(12)发明专利申请权利要求书2页 说明书7页 附图6页(10)申请公布号CN 104008152 A
1.支持海量数据访问的分布式文件系统的架构方法，其特征在于，包括以下步骤：
(1)采用非阻塞的网络通信框架，在Linux系统中，采用epoll选择器；
(2)采用基于动态代理的远程过程调用；
(3)客户端通过API访问文件系统，集中的节点通过以太网实现相互通信，每个节点负责维护路由表、元数据、文件数据；客户端连接任意一个已注册服务的节点即实现对文件的操作；
(4)文件通过一致性哈希算法映射到相应的节点上，分布式哈希表采用Kademila算法；
(5)对大文件分块，文件的数据以及元数据都备份在若干个不同的节点上；
(6)对某个文件操作时采用PaxosLease算法在多个节点中选举出领导者，由领导者操作后再同步到其他备份。
2.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(1)中所述的非阻塞的网络通信框架，是基于Java的NIO库MINA，其提供支持TCP/ UDP上抽象的事件驱动的API，对数据包进行封装解包，并交给多线程控制器处理。
3.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(2)中所述的远程过程调用的传统模式为三层：
(2-1)存根/框架层：用于客户端存根/代理、服务器端框架；
(2-2)远程引用层：用于远程引用行为；
(2-3)传输层：用于连接的建立和管理，以及远程对象的跟踪；
步骤(2)中所述的动态代理模式为：运行时根据需要动态的生成代理对象，将要调用的方法名、参数通过包装后发送给服务端，服务端接收到请求后查已经注册的服务实体，调用实体的方法后对返回值和异常包装后发送给客户端。
4.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(3)中所述的元数据参考Linux文件系统索引节点和GFS的思想，包括文件的子节点信息、文件大小、权限模式、数据块信息，形成树形结构，系统中每个文件块的大小为64M，大文件被分块存储，并由文件元数据的块信息链表维护；文件操作API包括创建节点、判断是否存在、创建目录、删除、列出目录文件的操作。
5.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(4)所述Kademila算法步骤如下：
(4-1)机器特征和文件路径都通过哈希运算得到一个ID；
(4-2)ID分布在264大小的环上，为寻与当前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路由是一棵非平衡的线段二叉树，其操作分为插入、删除、查最接近某ID
值的一个。
6.根据权利要求5所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(4-1)中机器特征和文件路径都通过64位CityHash算法得到一个ID。
7.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(5)所述对大文件分块的步骤为：将大于64M的文件进行分块，默认每个分块为64M；每个分块都备份到邻近的3个节点上，文件的写入默认采用的是追加的方式，写入过程为链式的，每个节点接收到数据后向下一个节点传输，数据至少在第一个节点校验成功后认为写入成功，若有分块写入失败，则由检查数据备份的线程发起同步。
8.根据权利要求1所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，步骤(6)所述PaxosLease算法具体如下：
当一个提案者提出一个议案，要想该议案获得批准，必须获得超过半数的决议者的批准，才能同步到所
有执行议案的人手册上；其约束包括：
P1：一个决议者必须接受第一次收到的提案；
P2：一旦一个具有提案值v的提案被批准，那么之后批准的提案必须具有值v。
9.根据权利要求8所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，对上述约束条件P2进行进一步约束：
P2a：一旦一个具有提案值v的提案被批准，那么之后任何决议者再次接受的提案必须具有值v；
同时，对提议者的行为进行约束：
P2b：一旦一个具有提案值v的提案被批准，那么以后任何提案者提出的提案必须具有值v。
10.根据权利要求9所述的支持海量数据访问的分布式文件系统的架构方法，其特征在于，约束包括：
P2c：如果一个编号为n的提案具有提案值v，那么存在一个多数派，要么他们中所有人都没有接受编号小于n的任何提案，要么他们已经接受的所有编号小于n的提案中编号最大的那个提案具有提案值v。
支持海量数据访问的分布式文件系统的架构方法
技术领域
[0001] 本发明涉及分布式文件系统研究领域，特别涉及一种支持海量数据访问的分布式文件系统的架构方法。
背景技术
[0002] 随着互联网技术的发展，“云计算”正日益受人们重视，它是分布式计算、并行计算、效用计算、网络存储、虚拟化、负载均衡等传统技术的融合而形成的一种新的面向用户的服务型产品概念。而“云存储”又是最为贴近普通网民的云服务之一。
[0003] 早期的分布式文件系统，文件及其元数据信息没有做冗余备份，一旦其中某台服务器故障，则存储在该服务器上的文件就不可用。而且随着文件数量增加，系统也变得更为庞大，既难扩展也难管理。现代的分布式文件系统则更加注重元数据的分布策略，将文件元数据和数据存储分离，可以提高服务的并发性、可用性，并充分利用集中实际数据存储机器的磁盘IO。
[0004] 目前常见的分布式文件系统有GFS、HDFS、Lustre、MogileFS等，其各自适用于不同的领域。最活跃是Hadoop上的HDFS，其架构图如图8所示，其面向的是分布式计算，采用单一元数据服务器的架构，系统简单，适合较大的文件体积，通过追加方式写入的文件往往达到了成百上千GB，将文件进行
分块存储。对于分布式数据处理、计算的场景来说，HDFS 足够应付，并已有许多成功案例。但是其单个的主节点容易成为瓶颈，而且有单点失败的情况。MogileFS支持大量小文件的读写，可自动复制文件，但是不支持文件的随机读写，对数据库过度依赖，同样存在单点故障。Lustre采用对象存储技术，适合对大文件进行读写，其将大文件分片，通过存储节点上的RAID提供可靠性，故系统不提供多个副本的冗余备份。
发明内容
[0005] 本发明的主要目的在于克服现有技术的缺点与不足，提供一种支持海量数据访问的分布式文件系统的架构方法，该系统借鉴了各种分布式文件系统的优点，其无中心化架构及冗余备份机制可向上层提供安全可靠的、高效的分布式文件存取服务以及海量的数据访问。
[0006] 本发明的目的通过以下的技术方案实现：支持海量数据访问的分布式文件系统的架构方法，包括以下步骤：
[0007] (1)采用非阻塞的网络通信框架，在Linux系统中，采用epoll选择器。使系统在大量连接及高IO时仍有很高的性能；
[0008] (2)采用简单且高效的基于动态代理的远程过程调用(RPC，Remote Procedure Call)，降低系统复杂性；
[0009] (3)与传统的C/S架构类似，客户端通过API访问文件系统，集中的节点通过以太网实现相互通信，每个节点负责维护路由表、元数据、文件数据。客户端连接任意一个已注册服务的节点即可实现对文件的操作；
[0010] (4)文件通过一致性哈希算法映射到相应的节点上，保证文件的分布与节点数目无关，节点的加入与退出对系统的影响和数据的迁移量降到最低，分布式哈希表采用Kademila算法，能最大限度的减少查文件中的时间消耗；
[0011] (5)对大文件分块，文件的数据以及元数据都备份在3个不同的节点上，节点宕机后能迅速切换，保证数据的安全有效；
[0012] (6)完全分布式的结构在多个节点上都存在文件备份，对某个文件操作时需要判断真正可操作的备份。系统采用一种优秀的、可快速在多个节点中选举出领导者的算法PaxosLease，由领导者操作后再同步到其他备份。
[0013] 上述方法的步骤(1)中所述的非阻塞网络通信框架，是基于Java的NIO库MINA，其提供支持TCP/UDP上抽象的事件驱动的API。其也是优秀的过滤器链和和多线程控制器模型，对数据包快速进行封装解包，并交给多线程控制器处理，MINA在完整的RPC调用中耗时约为0.5毫秒。
[0014] 上述方法的步骤(2)中所述的远程过程调用的传统模式为三层：
[0015] (2-1)存根/框架(Stub/Skeleton)层：用于客户端存根(代理)和服务器端框架。
[0016] (2-2)远程引用(Remote Refference)层：用于远程引用行为。
[0017] (2-3)传输(Transport)层：用于连接的建立和管理，以及远程对象的跟踪。[0018] Java自带的RMI框架内部过多的异常检查，传输时附带不必要的信息，存根的生成也使得代码的管理变得复杂，见图11。而动态的代理模式(见图6)在运行时根据需要动态的生成代理对象，将要调用的方法名、参数通过包装后发送给服务端，服务端接收到请求后查已经注册的服务实体，调用实体的方法后对返回值和异常包装后发送给客户端。[0019] 上述方法的步骤(3)中所述的元数据参考Linux文件系统索引节点和GFS的思想，包括文件的子节点信息、文件大小、权限模式、数据块信息等，形成树形结构，系统中每个文件块的大小为64M，大文件被分块存储，并由文件元数据的块信息链表维护；文件操作API包括创建节点、判断是否存在、创建目录、删除、列出目录文件等与其他操作系统类似的操作。
[0020] 上述方法的步骤(4)所述Kademila协议算法过程有：
[0021] (4-1)机器特征(如IP地址)和文件路径都通过哈希运算得到一个ID，本系统采用了快速且健全的64位CityHash算法，具有均匀、碰撞率低等特点。
[0022] (4-2)ID分布在264大小的环上，为寻与当前key所映射到的ID最邻近的节点，需要计算到已知节点的距离。在Kademila算法中，两个ID间的距离通过异或运算得到：[0023] d(x,y)＝x⊕y
[0024] 可以知道，异或运算是单向性的。对于任意给定的节点x和距离D，总会存在一个确定的节点y，使得d(x,y)＝D；
[0025] (4-3)Kad路由表由称之为K桶的数据结构组成，K桶实际存放的是<K,V>对映射，每个K桶都有一个ID以及它所包含的ID值的距离范围。当插入的<K,V>对足够多时，K桶会分裂，在最终状态下一台机器的Kad路由表为64个。若某个K桶已满，则采用LRU算法替换，有利于临计节点的管理。
[0026] (4-4)Kad路由是一棵非平衡的线段二叉树，但是一个节点的Kad路由不会太大，
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议