本发明公开了一种基于HDFS分布式文件系统的数据冗余及文件操作方法。它包括：文件写入、读取、追加及删除，其中：文件写入包括：客户请求、分配主结点、文件分段、生成和存储基本块、生成和存储编码块及主结点汇报；文件读取包括：客户请求、选择主结点、发送信息数据、根据信息数据恢复原文件及主结点汇报；文件追加包括：客户请求、查询文件信息并分配主节点、对追加文件分段、生成和存储基本块、生成和存储编码块及追加汇报。文件删除包括：客户请求、删除文件的文件名处理、删除隐藏文件、删除孤立Block元数据和删除任意Block块。本发明具有读写性能和效率高，节约存储资源、存储可靠的优点，可用于分布式文件系统在大规模客户访问下的存储和管理。
1.基于HDFS分布式文件系统的数据冗余方法，包括如下步骤：（1）将文件数据进行分段，每个文件段的基本长度为64MB，如果不足64MB的文件段数据结尾用0填补；
（2）将分好的文件段分为等长的基本块，并且将这些基本块存储在同一Datanode结点的Block块中，同时对存储在Block块中的数据生成校验和，存入文件元数据表中；
（3）对基本块数据进行编码，得到编码块，将这些编码块、对应的编码系数和Block标志发送到系统的不同于基本块所存储的Datanode结点的Datanode结点；
（4）收到编码块的Datanode结点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、编码系数写入附加文件中，完成数据冗余；
步骤（3）所述的对基本块数据进行编码，采用随机线性网络编码方法，具体步骤如下：a)将基本块数据按照文件的分块顺序组合在一起，表示为[X1X2…Xi…Xn]，1≤i≤n，n表示文件总的分块数，Xi表示文件基本块数据；
b)在伽罗华域GF(2 )上随机选择一组系数序列gj=(gj,1,gj,2,…gj,n)，用这组序列与数据块进行如下运算，得到信息向量：其中，1≤i≤n，j是任意正整数，Xi表示文件基本块数据，gj,i表示系数序列gj的任意一个元素；
c)根据信息向量公式对基本块数据[X1X2…Xi…Xn]进行m次运算，完成整个编码，即Y1=g1,1X1+g1,2X2+…+g1,nXnY2=g2,1X1+g2,2X2+…+g2,nXn. . . .
Ym=gm,1X1+gm,2X2+…+gm,nXn其中，m是该文件段的编码块个数，m大于n，(Y1,Y2,…Ym)是编码块(g1,g2,…gm)是对应编码块的编码系数。
2.根据权利要求1所述的数据冗余方法，其中步骤（2）所述的生成校验和，采用CRC-32循环校验方法，每个基本块和编码块的校验和都是32比特。
3.基于HDFS分布式文件系统的文件操作方法，包括：（A）文件写入步骤：
A2)Namenode在文件命名空间里查询是否存在相同的文件请求名，如果存在，则要求客户端更改文件名，如果不存在，则为该客户指定一个主结点，并且将其它结点作为该客户端的次结点；
A3)客户端将数据发送给主结点，主结点对接收到的数据进行冗余:首先，由主结点将数据划分成文件段，每个文件段的基本长度为64MB，如果不足64MB的文件段数据结尾用0填补；
其次，将分好的文件段分为等长的基本块，并且将这些基本块存储在同一Datanode结点的Block块中，同时对存储在Block块中的数据生成校验和，存入文件元数据表中；
再次，对基本块数据进行编码，得到编码块，将这些编码块对应的编码系数和Block标志发送到各个次结点；
最后，由收到编码块的次结点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、编码系数写入附加文件中，完成数据冗余；
A4)数据冗余结束后，主结点向客户端和Namenode结点报告写入文件完成；
B1)客户端联系Namenode结点，发送文件读取请求；
B2)Namenode结点在文件命名空间中查询请求的文件是否存在，若不存在回复“文件不存在”，否则查询主结点和次结点的位置、各基本块和编码块的标志信息，发送给客户端；
B3)客户端向主结点发送基本块、编码块及次结点的信息，收到信息后，主结点查找基本块并验证完整性，若数据完整则发送给客户端，读取结束，否则，联系载有相关编码块的次结点；
B4)收到请求的次结点将编码块和编码系数发送给主结点，主结点用收到的编码块和编码系数恢复原始数据并发送给客户端，读取结束:a)主结点收到数据包集合(g1,Y1)，(g2,Y2)，…(gi,Yi)，…(gm,Ym)，其中，gj=(gj,1,gj,2,…gj,n)；
其中，Yj表示收到的编码块，gj,i表示gj的任意元素，Xi是所要求解的未知数，由方程表示式可知该方程有m个等式和n个未知数，如果m≥n时，求解Xi，恢复出原始数据，发送给客户端；如果m
C1)客户端联系Namenode结点，发送文件追加请求；
C2)Namenode结点检测文件名是否有需要追加的文件，如果有，则委托主结点将追加信息放在原来最后一个基本块后，并且删除填充的0，如果不存在该文件，则向客户端返回“该文件不存在，无法追加”的信息；
D1)客户端联系Namenode结点，发送文件删除请求；
D2)Namenode结点立刻把删除操作以日志的方式记录下来，将文件名改为一个包含删除时间戳的、隐藏的名字，并进行如下操作：对文件系统命名空间做常规扫描时，删除三天前的隐藏文件；
对Block命名空间做常规扫描时，找到不被任何文件包含的Block，同时删除它的元数据；
在与Datanode结点交互时，Datanode结点向Namenode结点报告自己拥有的Block信息，Namenode结点向Datanode结点回复已经不存在的那些Block元数据信息，由Datanode结点对这些不存在元数据Block进行任意删除。
基于HDFS分布式文件系统的数据冗余及文件操作方法
技术领域
[0001] 本发明属于数字信息存储技术领域，特别涉及基于Hadoop Distributed File Syetem(HDFS)分布式文件系统的数据冗余和文件操作方法，可用于文件系统的存储和管理。
背景技术
[0002] 随着信息技术的发展，存储数据在爆炸式的增长，本地的存储很难满足不断增长的海量存储的需要，加上个人移动计算和企业级的大规模计算对底层存储系统提出更高的要求，人们越来越多的使用分布式文件系统，因为它能给人们带来更高的存储能力、可靠性、安全性和移动性。
[0003] 目前，分布式文件系统有Sun公司开发的NFS分布式文件系统，它是第一个基于IP协议分布式文件系统，微软研究院的Farsite系统，加州大学圣地亚哥分校的TotalRecall系统，亚马逊公司的Dynamo系统，以及Google公司为其商业应用开发的GFS和Apache基金会开发的HDFS。
[0004] HDFS是GFS的开源实现，有着大量的参考文档和实验方式，HDFS采用master/slave架构，如图1所示。HDFS集群是由一个Namenode结点和多个Datanode结点组成。Namenode结点是一个中心服务器，相当于GFS中Master结点。其负责管理文件系统的名字空间以及客户端对文件的访问，比如打开、关闭、重命名文件或目录操作等。Datanode结点当于GFS中Chunk Server结点，负责管理它所在结点上块数据的存储。即在Namenode结点的统一调度下进行数据块的创建、删除和复制。
[0005] 为了保证数据的可用性，现实中的分布式存储系统都对数据采取冗余技术。冗余技术包括两大类：完整副本冗余和编码冗余。HDFS的数据冗余机制采取复制机制，默认情况下系统分布式存储三份副本，分散存储在系统Datanode结点，这样虽然能够保证数据恢复的完整性，但造成了系统资源的巨大浪费。HDFS文件操作包括文件写入、文件读取、文件追加和文件删除，由于采用三个副本的数据冗余方案，带来文件读取和文件写入效率和性能上的损失。
发明内容
[0006] 本发明的目的在于克服上述已有技术的不足，提出了一种基于HDFS分布式文件系统的数据冗余方法和文件操作方法，有效地在数据可靠性和读写性能间取得了平衡，在相同的冗余度下提高了文件的读取和文件写入的性能和效率，缩减了系统硬盘的存储空间。
[0007] 为实现上述目的，本发明基于HDFS分布式文件系统的数据冗余方法，包括如下步骤：
[0008] (1)将文件数据进行分段，每个文件段的基本长度为64MB，如果不足64MB的文件段数据结尾用0填补；
[0009] (2)将分好的文件段分为等长的基本块，并且将这些基本块存储在同一Datanode结点的Block块中，同时对存储在Block块中的数据生成校验和，存入文件元数据表中；
[0010] (3)对基本块数据进行编码，得到编码块，将这些编码块、对应的编码系数和Block标志发送到系统的不同于基本块的Datanode结点；
[0011] (4)收到编码块的节点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、编码系数写入附加文件中，完成数据冗余。
[0012] 为实现上述目的，本发明基于HDFS分布式文件系统的文件操作方法，包括：
[0013] (A)文件写入步骤：
[0014] A1)客户端向Namenode结点发出文件写请求；
[0015] A2)Namenode结点在文件命名空间里查询是否存在相同的文件请求名，如果存在，则要求客户端更改文件名，如果不存在，则为该客户指定一个主结点，并且将其它结点作为该客户端的次结点；
[0016] A3)客户端将数据发送给主结点，主结点对接收到的数据进行冗余：
[0017] 首先，由主结点将数据划分成文件段，每个文件段的基本长度为64MB，如果不足64MB的文件段数据结尾用0填补；
[0018] 其次，将分好的文件段分为等长的基本块，并且将这些基本块存储在同一Datanode结点的Block块中，同时对存储在Block块中的数据生成校验和，存入文件元数据表中；
[0019] 再次，对基本块数据进行编码，得到编码块，将这些编码块对应的编码向量和Block标志发送到各个次结点；
[0020] 最后，由收到编码块的次节点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、编码向量写入附加文件中，完成数据冗余；
[0021] A4)数据冗余结束后，主结点向客户端报告写入文件完成；
[0022] (B)文件读取步骤：
[0023] B1)客户端联系Namenode结点，发送文件读取请求；
[0024] B2)Namenode结点在文件命名空间中查询请求的文件是否存在，若不存在回复“文件不存在”，否则查询主结点和次结点的位置、各基本块和编码块的标志信息，发送给客户端；
[0025] B3)客户端向主节点发送基本块、编码块及次结点的信息，收到信息后，主结点查找基本块并验证完整性，若数据完整则发送给客户端，读取结束，否则，联系载有相关编码块的次结点；
[0026] B4)收到请求的次结点将编码块和编码系数向量发送给主结点，主结点用收到的编码块和编码系数恢复原始数据并发送给客户端，读取结束；
[0027] (C)文件追加步骤：
[0028] C1)客户端联系Namenode结点，发送文件追加请求；
[0029] C2)Namenode结点检测文件名是否有追加文件，如果有，则委托主结点将追加信息放在原来最后一个基本块后，并且删除填充的0，如果不存在该文件，则向客户端返回“该文件不存在，无法追加”的信息；
[0030] (D)文件删除步骤：
[0031] D1)客户端联系Namenode结点，发送文件删除请求；
[0032] D2)Namenode结点立刻把删除操作以日志的方式记录下来，将文件名改为一个包含删除时间戳的、隐藏的名字，并进行如下操作：
[0033] 对文件系统命名空间做常规扫描时，删除三天前的隐藏文件；
[0034] 对Block命名空间做常规扫描时，找到不被任何文件包含的Block，同时删除它的元数据；
[0035] 在与Datanode结点交互时，Datanode结点向Namenode结点报告自己拥有的Block信息，Namenode结点向Datanode结点回复已经不存在的那些Block元数据信息，由Datanode结点对这些不存在元数据Block进行任意删除。
[0036] 本发明与现有技术相比具有以下优点：
[0037] 第一，由于本发明的数据冗余机制的复制部分采用只存储文件的一个基本块，克服了现有HDFS分布式文件系统存储三个副本，存储空间较大的缺点，可在占用存储空间更小的情况下达到与现有HDFS系统相同的数据可靠性，这在存储海量数据时有利于节省宝贵的硬盘资源。
[0038] 第二，由于本发明的数据冗余机制编码部分采用在伽罗华域GF(216)上随机线性网络编码的编码方式以及编码块随机放置的方法，克服了现有HDFS分布式文件系统数据失效率较高、可靠性差的缺点，在相同的宕机率下，本发明的数据失效率明显降低，而且在保证宕机率小于0.15的情况下数据失效的可能性无限接近于0，这有助于在大规模客户端读取的情况下存储系统提供近乎百分百可靠的服务，在商业环境下具有非常现实的意义。
[0039] 第三，由于本发明在文件读取操作上采用先读取基本块，若基本块读取失败，再读取编码块的方法，克服了现有HDFS系统文件读取操作花费时间较长的缺点，读取相同大小的文件，本发明花费的时间更短，因此，效率更高，提高了分布式文件管理系统的整体性能。
附图说明
[0040] 图1为现有HDFS系统框架图；
[0041] 图2为本发明数据冗余流程图；
[0042] 图3为本发明数据冗余过程中对文件进行分段、分块、编码的子流程图；
[0043] 图4为本发明数据冗余过程中对基本块、编码块存储的元数据表结构图；
[0044] 图5为本发明文件操作总框图；
[0045] 图6为本发明的文件写入操作的流程图；
[0046] 图7为本发明的文件读取操作的流程图；
[0047] 图8为本发明的文件追加操作的流程图；
[0048] 图9为本发明的文件删除操作的流程图。
具体实施方式
[0049] 下面结合附图对发明做进一步的详细描述。
[0050] 参照图2，本发明的数据冗余具体步骤如下：
[0051] 步骤1：对文件进行分段，文件段的大小以基本分块数为单位，默认每个文件段由16个基本块组成，每个基本块的大小为4MB，因此，每个文件段数据长度为64MB，如果不足
64MB的文件段数据结尾用0填补。对于文件段非定长的情况，如图3，文件长度为74MB，只能分成两个文件段，文件段1分成16个4MB的基本块，文件段2分成3个4MB的基本块，前两个基本块中的文件来自于文件中，后一个基本块只有2MB的数据来自原始文件，后面的数据用0填充。
[0052] 步骤2：对文件段生成基本块，并且存储基本块数据。
[0053] 2a)将分好的文件段分为等长的基本块，每个基本块的大小为4MB，Namenode结点将这些基本块存储在同一Datanode结点的Block块中，每个Block块的大小也为4MB，以避免系统内部碎块的出现；
[0054] 2b)Namenode结点给每个Datanode结点的Block块分配一个不变的，全球唯一的64位Block标识符，同时对存储在Block块中的数据生成校验和，存入文件元数据表中，文件元数据表的格式如图4所示，第一行包括文件的分段数N，第二行包括：段数编号、校验和、实际数据长度、基本块Block标志和编码块Block标志。校验和是用来验证数据读取的完整性，由于部分基本块可能被0填充，需要知道实际数据长度，基本块Block标志引导读写基本块，编码块Block标志引导读写编码块信息；
[0055] 2c)Datanode结点把Block块以linux形式保存在本地硬盘上。
[0056] 步骤3：对基本块数据采用随机线性网络编码方法进行编码，得到编码块。
[0057] 3a)将数据块按照文件的分块顺序组合在一起，表示为[X1X2L XiL Xn]，1≤i≤n，n表示文件总的分块数，Xi表示文件基本数据块；
[0058] 3b)在伽罗华域GF(216)上随机选择一组系数序列gj＝(gj，1，gj，2，L gj，n)，用这组序列与数据块进行如下运算，得到信息向量：
[0059]
[0060] 其中，1≤i≤n，j是任意正整数，Xi表示文件基本数据块，gj，i表示系数序列gj的任意一个元素；
[0061] 3c)根据信息向量公式对数据块[X1X2L XiL Xn]进行m次运算，完成整个编码，即：
[0062] Y1＝g1，1X1+g1，2X2+L+g1，nXn
[0063] Y2＝g2，1X1+g2，2X2+L+g2，nXn
[0064]
[0065] Ym＝gm，1X1+gm，2X2+L+gm，nXn
[0066] 其中，m是该文件段的编码块个数，m大于n，(Y1，Y2，L Ym)是编码块，(g1，g2，L gm)是对应编码块的编码系数。将这些编码块、对应的编码系数和Block标志发送到系统的不同于基本块的Datanode结点。
[0067] 步骤4：收到编码块的Datanode结点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、基本块个数以附加文件的形式永久保存在Datanode结点，完成数据冗余。
[0068] 参照图5，对本发明的文件操作做进一步描述：
[0069] 文件操作包括文件写入、文件读取、文件追加和文件删除四个部分，各部分相互独立，分别描述如下：
[0070] 参照图6，本发明对文件进行如下写入操作：
[0071] 与传统的HDFS文件系统的写入操作相比，本发明在复制的同时还伴随着编码过程，因此，必须首先选择一个性能良好的主机结点，委托它进行数据的编码工作，文件写入操作的具体步骤如下：
[0072] 步骤一：客户端向Namenode结点发出文件写请求，包含请求的文件名和文件的大小；
[0073] 步骤二：Namenode结点在文件命名空间里查询是否存在相同的文件请求名，如果[0074] 存在相同的文件，则向用户端回复“存在同名文件”，要求客户端更改文件名，如果不存在相同的文件，则为该客户端指定一个主结点，分配Block标志，并且将其它结点作为该客户端的次结点，并将这些信息发送给客户端；
[0075] 步骤三：客户端将数据发送给主结点，如果在设定的时间间隔内，主结点没有回复任何收到连接的信息，表明主结点正处于繁忙或者无连接状态，这时，客户端向Namenode申请重新选定主结点，写入结束。如果客户端在设定的时间内，成功收到主结点回复的正常连接信息，表明主结点已经成功接收到了客户端发出的数据信息。主结点对接收到的数据进行冗余：
[0076] 3a)由主结点将数据划分成文件段，每个文件段的基本长度为64MB，如果不足64MB的文件段数据结尾用0填补；
[0077] 3b)将分好的文件段分为等长的基本块，并且将这些基本块存储在同一Datanode结点的Block块中，同时对存储在Block块中的数据生成校验和，存入文件元数据表中；
[0078] 3c)对基本块数据进行编码，得到编码块，将这些编码块对应的编码向量和Block标志发送到各个次结点；
[0079] 3d).由收到编码块的次节点将编码块保存在本地Block块上，并对这些编码块生成校验和，将Block标志、校验和、编码向量写入附加文件中，完成数据冗余；
[0080] 步骤四：数据冗余结束后，主结点向客户端报告写入文件完成，并且将每个文件段的校验和发送给Namenode结点，向Namenode结点报告写入完成。
[0081] 参照图7，本发明对文件进行如下读取操作：
[0082] 为了优化读取性能，将优先读取完整的副本，即各个文件段的基本块。只有当基本块读取失败后，才搜集比基本分块数多的编码块解码得到原始数据。解码操作委托给主节点进行，因为计算量比较大，需要主节点的性能满足一定的要求，否则更换主节点。客户端既可能是读取整个文件，也可能是读取某一部分，所以发出文件读取请求时需要指定文件名和起始位置，读取文件的步骤如下：
[0083] 步骤1：客户端联系Namenode结点，发送文件读取请求，包含请求的文件名和起始长度；
[0084] 步骤2：Namenode结点在文件命名空间中查询请求的文件是否存在，若不存在请求文件名，则回复“文件不存在”，读取结束，否则根据客户端的请求文件名在元数据表中查询主结点和次结点的位置、各基本块和编码块的Block标志信息及文件段校验和，将这些信息发送给客户端；
[0085] 步骤3：客户端连接主结点，如果在设定的时间间隔内，主结点没有回复任何收到连接的信息，表明主结点正处于繁忙或者无连接状态，这时，客户端向Namenode结点申请重新选定主结点，读取结束；如果客户端在设定的时间内，成功收到主结点回复的正常连接信息，表明主结点已经成功接收到了客户端发出的连接请求信息，此时，客户端向主节点发送基本块Block标志、编码块Block标志及次结点信息，主节点收到信息后，查找附加文件，并根据附加文件中存储的基本分块数和收到的基本块Block标志验证收到基本块的完整性，若数据完整则将基本块数据发送给客户端，读取结束，否则，联系载有相关编码块的次结点；
[0086] 步骤4：收到请求的次结点将编码块和编码系数发送给主结点，主结点用收到的编码块和编码系数恢复原始数据，其步骤如下：
[0087] 4a)主结点收到数据包集合(g1，Y1)，(g2，Y2)， 其中，gj＝(gj，1，gj，2，L gj，n)；
[0088] 4b)解线性方程组
[0089]
[0090] 其中，Yj表示收到的编码向量，gj，i表示gj的任意元素，Xi是所要求解的未知数，由方程表示式可知该方程有m个等式和n个未知数，如果m≥n时，求解Xi，恢复出原始数据，发送给客户端；如果m＜n时，无法求解Xi，读取结束。
[0091] 参照图8，本发明对文件进行追加操作，步骤如下：
[0092] 步骤A：客户端联系Namenode结点，发送文件追加请求，包含请求追加的文件名和文件的大小。
[0093] 步骤B：Namenode结点在文件命名空间里查询是否存在需要追加的文件名，如果不
[0094] 存在需要追加的文件名，则向用户端回复“该文件不存在，无法追加”的信息；如果存在需要追加的文件名，则为该客户指定一个主结点，并根据客户端的请求追加文件名在元数据表中查询各基本块Block标志、编码块Block标志及文件段校验和，将这些信息发送给客户端。
[0095] 步骤C：客户端连接主结点，如果在设定的时间间隔内，主结点没有回复任何收到连接的信息，表明主结点正处于繁忙或者无连接状态，这时，客户端向Namenode结点申请重新选定主结点，追加结束。如果客户端在设定的时间内，成功收到主结点回复的正常连接信息，表明主结点已经成功接收到了客户端发出的连接请求信息。此时，客户端向主节点发送追加文件的各基本块和编码块的Block标志信息，文件段校验和以及需要追加的文件内容。
[0096] 步骤D：主结点对收到的追加文件内容进行数据冗余，将追加的内容放在原来最后一个基本块后，删除填充的0，重新选择编码系数，生成编码块，更新文件的基本块和编码块的Block标志信息以及文件段校验和，将这些信息返回给Namenode结点，并向客户端返回追加文件成功。
[0097] 参照图9，对本发明的文件读删除进行作述：
[0098] 文件删除是将文件的元数据从NameNode结点删除，并在DataNode结点上删除各个基本块和编码块及相关附加数据，因为文件是分布式存储的，在删除的时候可能还有多个客户端读取，所以Namenode结点必须对文件系统命名空间、Block命名空间做定时扫描，对Datanode结点做定时交互，具体步骤如下：
[0099] 步骤a：客户端联系Namenode结点，向Namenode结点发送请求删除的文件名。
[0100] 步骤b：Namenode结点立刻把删除操作以日志的方式记录下来，在文件命名空间里查询该文件，如果查询该文件不存在，向客户端返回“文件不存在，无法删除”的信息，删除结束，否则，将该文件名隐藏，称为隐藏文件，并且在文件名中记录此刻时间，将此刻时间作为该文件的删除时间，再做如下操作：
[0101] 对文件系统命名空间做常规扫描，删除三天前的隐藏文件；
[0102] 对Block命名空间做常规扫描，找到不被任何文件包含的Block，同时删除它的元数据；
[0103] 在与Datanode结点交互时，Datanode结点向Namenode结点报告自己拥有的Block信息，Namenode结点向Datanode结点回复已经不存在的那些Block元数据信息，由Datanode结点对这些不存在元数据Block进行任意删除，文件删除结束。
