一种网络文件系统中数据的实时去重和传输方法

摘要

本发明涉及一种网络文件系统中数据的实时去重和传输方法，属于计算机数据存储技术领域。首先在客户端和服务器端各设置文件元数据表、数据块索引表和文件组成表，客户端设置一个待发送消息队列，用于存储数据更新消息；客户端通过文件系统驱动接收和响应客户端应用程序对网络文件系统发起的操作命令，包括创建新文件、向已有文件写入数据、从已有文件读取数据和删除已有文件；在服务器端设置的网络服务接口，用于上传和下载数据块内容，接收和应答客户端消息。本发明方法，可删除重复数据，节省存储空间，避免在客户端与服务器端之间传输对方已有的数据，降低了网络带宽的开销；同时支持定长和不定长的文件分块方法，提高存储空间的利用效率。

说明书

技术领域

本发明涉及一种网络文件系统中数据的实时去重和传输方法，属于计算机数据存储技术领域。

背景技术

长期以来，如何用尽可能少的空间储存尽可能多的数据以及如何以尽可能低的网络带宽开销传输尽可能多的信息一直是网络存储领域最核心问题。减少对文件中重复数据的存储和传输是解决上述问题的关键技术所在。

数据去重技术又称为重复数据删除技术，兴起于本世纪初期，近年来得到普及。数据去重的思想并不复杂：首先发掘在不同文件、同一文件不同版本、甚至同一版本的不同位置出现的相同数据单元，然后对内容互不相同的数据单元建立索引，这样就能够对每种内容的数据单元只存储一份内容，而在数据单元出现的位置仅记录该数据单元的索引。尽管数据去重技术炙手可热，但目前主要应用于数据同步、备份或归档阶段，如Sun公司提出的网络文件系统ZFS和同步备份工具Dropbox等。

Muthitacharoen等人在2001年的第18届ACM SOSP大会论文集中发表了“A Low-Bandwidth Network File System”，其中利用上述思想减少网络带宽开销。但是，在其方法中，只有当文件被关闭以后，才对整个文件进行分块和向服务器端同步，其方法至少存在下述若干显著缺点：一、数据切块和去重不是实时进行，客户端的新数据不能被及时传输到服务器端；二、切块效率低下，即使只修改文件中极小一部分内容，也需要对整个文件都重新进行切块；三、新打开一个文件时，需要先将该文件的所有数据块拼接成一个临时文件，才能对该文件进行操作，因而需等候相当长时间。

现有的其它网络系统，如网络文件系统(NFS)和服务器消息块(SMB)等，则没有采用数据去重技术，也无法提供减少存储空间占用和网络数据传输的功能。

发明内容

本发明的目的是提出一种网络文件系统中数据的实时去重和传输方法，通过文件系统驱动截获客户端的应用程序创建文件及向文件中写入的操作命令，实时进行数据的分块和去重，并只将新产生的数据块传输到服务器端，从而在根本上实现以数据块为基本存储单元的网络文件系统及其存储和组织结构，达到节省本地存储空间和网络传输带宽的目的。

本发明提出的网络文件系统中数据的实时去重和传输方法，包括以下步骤：

(1)在网络文件系统的客户端和服务器端各设置文件元数据表、数据块索引表和文件组成表；所述的文件元数据表记录网络文件系统中每个文件的元数据，该元数据包括文件标识、文件名、文件所在文件夹的标识、文件大小、文件类型、访问权限以及文件的创建、修改和访问时间；所述的数据块索引表记录网络文件系统中文件的数据块的标识以及与标识相对应的数据块的引用次数，其中数据块的标识为该数据块内容的哈希值；所述的文件组成表记录组成网络文件系统中的文件的数据块的信息，包括文件标识、起始位置、数据块大小和数据块标识，由其中的起始位置和数据块大小决定数据区域；

在网络文件系统的客户端设置一个待发送消息队列，用于存储客户端待发送给服务器端的数据更新消息；

(2)客户端通过文件系统驱动接收和响应客户端应用程序对网络文件系统发起的操作命令，该操作命令包括创建新文件、向已有文件写入数据、从已有文件读取数据和删除已有文件；

(2-1)当客户端的文件系统驱动接收到创建新文件的操作命令时，在客户端的上述文件元数据表中记录被创建文件的元数据，并将该元数据封装成一个文件元数据更新消息，再将该消息添加到客户端的上述待发送消息队列的队尾；

(2-2)当客户端的文件系统驱动接收到向已有文件写入数据的操作命令时，进行以下操作：

(2-2-1)根据操作命令中被写文件的文件标识、写入位置和写入数据大小，从客户端的上述文件组成表中检索属于该被写文件的两个数据块标识，且与该两个数据块标识相对应的两个数据块为与被写入数据区域相互重叠的首、尾两个数据块；

(2-2-2)根据检索到的数据块标识，从客户端存储的文件中读取与该数据块标识相对应的数据块内容；

(2-2-3)将读出的数据块内容中与被写入数据区域相不重叠的数据拼接到被写入数据的两侧，得到拼接后的数据及数据区域；

(2-2-4)从客户端的上述文件组成表中检索与属于该被写文件、且起始位置位于上述步骤(2-2-3)数据区域之内的数据块相对应的数据块标识；

(2-2-5)将与从客户端的上述数据块索引表中检索到的数据块标识相对应的数据块的引用次数减1，当引用次数成为0时，从客户端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块引用次数，并从客户端的存储设备上删除该数据块内容；

(2-2-6)将上述步骤(2-2-3)拼接后的数据切分成一组新数据块；

(2-2-7)从客户端的上述数据块索引表中分别搜索与上述一组新数据块相对应的每个数据块标识：若该新数据块标识已存在，则在客户端的数据块索引表中将与该新数据块标识相对应的数据块的引用次数加1，若该数据块标识为新标识，则在客户端的数据块索引表中添加该新数据块的标识，并将与该新数据块标识相对应的数据块的引用次数设置为1；在客户端存储该新数据块的内容；在客户端的上述文件组成表中记录被写文件的标识、写入位置、该新数据块的大小以及该新数据块的标识；

(2-2-8)在客户端将上述被写文件的文件标识、每个新数据块的起始位置、每个新数据块大小和每个新数据块标识封装成一个文件组成更新消息，并将该更新消息添加到客户端的上述待发送消息队列的队尾；

(2-2-9)更新客户端的上述文件元数据表中被写文件的元数据，并将该更新后的元数据封装成文件元数据更新消息，并将该更新消息添加到客户端的上述待发送消息队列的队尾；

(2-3)当客户端的文件系统驱动接收到从已有文件读取数据的操作命令时，进行以下操作：

(2-3-1)根据操作命令，在客户端的内存中分配与待读取数据的大小相等的内存空间，并将该内存空间初始化为空白；

(2-3-2)根据操作命令中的被读文件的文件标识和读取位置，从客户端的上述文件组成表中检索属于该被读文件的数据块标识，且与该数据块标识相对应的数据块是起始位置处于读取位置之前的最后一个数据块，若该数据块标识存在，且该数据块区域与待读取数据区域存在重叠，则从客户端读取该数据块内容，并将该读取的内容与待读取数据区域的重叠部分写入上述步骤(2-3-1)的内存空间的头部；

(2-3-3)根据该操作命令，从客户端的上述文件组成表中检索属于该被读文件的数据块标识，且与该数据块标识相对应的数据块的起始位置处于待读取数据区域内，遍历检索到的所有数据块标识，对每个数据块标识进行以下操作：

(2-3-3-1)判断客户端是否存有与该数据块标识相对应的数据块内容，若该内容存在，则读取该数据块内容，若该内容不存在，则从网络文件系统的服务器端下载该数据块内容，并在客户端存储该数据块内容；

(2-3-3-2)将上述数据块内容中与待读取数据区域的重叠部分写入上述步骤(2-3-1)的内存空间中；

(2-3-4)更新客户端的上述文件元数据表中被读文件的元数据，将该元数据封装成一个文件元数据更新消息，并将该消息添加到客户端的上述待发送消息队列的队尾；

(2-3-5)将上述步骤(2-3-1)的内存空间中的数据通过客户端的文件系统驱动返回给客户端的应用程序；

(2-4)当客户端的文件系统驱动接收到删除已有文件的操作命令时，进行以下操作：

(2-4-1)从客户端的上述文件组成表中检索属于被删除文件的数据块标识；

(2-4-2)在客户端的上述数据块索引表中将与检索到的每个数据块标识相对应的数据块的引用次数减1，当引用次数变为0时，从客户端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块引用次数，从客户端删除该数据块内容；

(2-4-3)从客户端的上述文件组成表中删除被删除文件的所有记录；

(2-4-4)从客户端的上述文件元数据表中删除被删除文件的元数据；

(2-4-5)在客户端将被删除文件的文件标识封装成一个文件删除消息，并将该消息添加到客户端的上述待发送消息队列的队尾；

(3)在网络文件系统的服务器端设置的网络服务接口，用于上传和下载数据块内容，以及用于接收和应答客户端消息，具体过程如下：

(3-1)当网络文件系统服务器端接收到来自网络文件系统客户端待发送消息队列中的文件元数据更新消息时，进行以下操作：

(3-1-1)从接收到的文件元数据更新消息中解析出文件的标识及该文件的元数据；

(3-1-2)判断服务器端的上述文件元数据表中是否存在该文件标识，若已存在，则将与该文件标识相对应的元数据更新为上述步骤(3-1-1)中的元数据；若该文件标识为新标识，则在服务器端的上述文件元数据表中添加该文件标识及上述步骤(3-1-1)中的元数据；

(3-2)当服务器端接收到客户端待发送消息队列中的文件组成更新消息时，进行以下操作：

(3-2-1)从接收到的文件组成更新消息中解析出文件的标识以及每个数据块的起始位置、数据块大小和数据块的标识；

(3-2-2)在服务器端的上述文件组成表中检索属于该文件的数据块标识，且与该数据块标识相对应的数据块的起始位置处于新生成数据块区域之内；

(3-2-3)在服务器端的上述数据块索引表中分别将与检索到的每个数据块标识相对应的数据块的引用次数减1，若引用次数变为0，则从服务器端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块的引用次数，从服务器端上删除该数据块内容；

(3-2-4)在服务器端的上述数据块索引表中检索上述步骤(3-2-1)的数据块标识，若该数据块标识已存在，则将与该数据块标识相对应的数据块的引用次数加1，若该数据块标识为新标识，则通知客户端上传与该数据块标识相对应的数据块内容，接收客户端上传的数据块的内容，在服务器端存储该数据块的内容，在服务器端的数据块索引表中添加该数据块的标识，并将与该数据块标识相对应的数据块的引用次数设置为1；

(3-3)当服务器端接收到客户端待发送消息队列中的文件删除消息时，进行以下操作：

(3-3-1)从接收到的文件组成更新消息中解析出被删除文件的标识；

(3-3-2)在服务器端的上述文件组成表中检索属于被删除文件的所有数据块标识；

(3-3-3)在服务器端的上述数据块索引表中将与检索到的每个数据块标识相对应的数据块的引用次数减1，若引用次数变为0，则从服务器端的数据块索引表中删除与该数据块标识相对应的数据块的引用次数，从服务器端删除该数据块内容；

(3-3-4)从服务器端的文件组成表中删除属于该被删除文件的数据块记录；

(3-3-5)从服务器端的文件元数据表中删除该被删除文件的元数据。

本发明提出的网络文件系统中数据的实时去重和传输方法，其优点是：

1、利用本发明的方法，可以删除网络文件系统中的重复数据，因此节省了客户端和服务器端的存储空间。

2、利用本发明的方法对网络文件系统中的数据进行实时去重和传输，保证了客户端产生的新数据能够被及时的传输和存储到服务器端，提高了网络文件系统中数据存储的可靠性。

3、利用本发明的方法进行网络文件的读取、写入的同时，对被修改的文件数据进行切块与拼接操作，无须处理未被修改的数据，因此极大提高了文件处理的效率。

4、本发明方法同时支持定长和不定长的文件分块方法，能够显著改善重复数据的去除效果，提高网络文件系统中客户端和服务器端的存储空间的利用效率。

5、与已有技术相比，本发明方法对新打开的文件可立即实现随机读、写操作，无须等候拼接临时文件，因此缩短了打开文件的时间。

6、本发明方法避免了在客户端与服务器端之间传输对方已有的数据，降低了网络带宽的开销。

7、与已有网络文件系统相比，本发明方法尤其适用于具有客户端移动存储设备容量小、客户端与服务器端之间经过广域网而导致带宽受限的特点的云存储环境。

附图说明

图1是本发明方法中向已有文件写入数据的过程示意图。

图2是本发明方法中计算待读取数据区域及计算向内存空间的起始写入位置示意图。

图3是本发明方法中从已有文件读取数据的过程示意图。

具体实施方式

下面结合附图，详细介绍本发明提出的网络文件系统中数据的实时去重和传输方法：

(1)在网络文件系统的客户端和服务器端各设置文件元数据表、数据块索引表和文件组成表；所述的文件元数据表记录网络文件系统中每个文件的元数据，该元数据包括文件标识、文件名、文件所在文件夹的标识、文件大小、文件类型、访问权限以及文件的创建、修改和访问时间；所述的数据块索引表记录网络文件系统中文件的数据块的标识以及与标识相对应的数据块的引用次数，其中数据块的标识为该数据块内容的哈希值；所述的文件组成表记录组成网络文件系统中的文件的数据块的信息，包括文件标识、起始位置、数据块大小和数据块标识，由其中的起始位置和数据块大小决定数据区域。

在网络文件系统的客户端设置一个待发送消息队列，用于存储客户端待发送给服务器端的数据更新消息。

(2)客户端通过文件系统驱动接收和响应客户端应用程序对网络文件系统发起的操作命令，该操作命令包括创建新文件、向已有文件写入数据、从已有文件读取数据和删除已有文件：

(2-1)当客户端的文件系统驱动接收到创建新文件的操作命令时，在客户端的上述文件元数据表中记录被创建文件的元数据，并将该元数据封装成一个文件元数据更新消息，再将该消息添加到客户端的上述待发送消息队列的队尾。

(2-2)当客户端的文件系统驱动接收到向已有文件写入数据的操作命令时，进行以下操作。

(2-2-1)根据操作命令中被写文件的文件标识、写入位置和写入数据大小，从客户端的上述文件组成表中检索属于该被写文件的两个数据块标识，且与该两个数据块标识相对应的两个数据块为与被写入数据区域相互重叠的首、尾两个数据块，具体过程可参见图1。从图1中，可以看出，网络文件系统中存在文件标识分别为1和2的两个文件，文件标识为1的文件由5个数据块组成，该5个数据块对应的数据块标识分别为A、B、C、D、E，文件标识为2的文件由3个数据块组成，该3个数据块对应的数据块标识分贝为A、D、F，客户端的文件组成表中记录了文件的组成信息。上述两个文件存在重复数据，导致该两个文件都含有数据块标识分别为A和D的两个数据块，由于这两个数据块的内容只被存储一次，因此实现了数据去重的目的。如图1所示，操作命令中被写文件的文件标识为1，根据该文件标识，同时根据操作命令中的写入位置和写入数据大小可计算出被写入数据区域，在客户端的文件组成表中检索属于该被写文件的两个数据块标识，且与该两个数据块标识相对应的两个数据块为与被写入数据区域相互重叠的首、尾两个数据块，就会得到数据块标识B和数据块标识D。

(2-2-2)根据检索到的数据块标识，从客户端存储的文件中读取与该数据块标识相对应的数据块内容；对应图1，就是读出数据块标识分别为B和D的两个数据块的内容。

(2-2-3)将读出的数据块内容中与被写入数据区域相不重叠的数据拼接到被写入数据的两侧，得到拼接后的数据及拼接后的数据区域；拼接过程、拼接后的数据及拼接后的数据区域，如图1所示。

(2-2-4)从客户端的上述文件组成表中检索与属于该被写文件、且起始位置位于上述步骤(2-2-3)拼接后的数据区域之内的数据块相对应的数据块标识；在如图1所示例中，该检索将得到的3个数据块标识，分别为B、C和D。

(2-2-5)将与从客户端的上述数据块索引表中检索到的数据块标识相对应的数据块的引用次数减1，当引用次数成为0时，从客户端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块引用次数，并从客户端的存储设备上删除该数据块内容。

(2-2-6)将上述步骤(2-2-3)拼接后的数据切分成一组新数据块；数据切分的方法可以使用基于用户或系统设定的数据块大小的定长切分和基于内容指纹的不定长切分，本发明的一个实施例中，使用了Muthitacharoen等人在一种低带宽网络文件系统一文中提出的基于Rabin指纹的可变长切分方法；如图1所示，拼接后的数据被切分成两个新的数据块，根据数据块内容的哈希值，该两个数据块的数据块标识分别为G和H。

(2-2-7)从客户端的上述数据块索引表中分别搜索与上述一组新数据块相对应的每个数据块标识：若该新数据块标识已存在，则在客户端的数据块索引表中将与该新数据块标识相对应的数据块的引用次数加1，若该数据块标识为新标识，则在客户端的数据块索引表中添加该新数据块的标识，并将与该新数据块标识相对应的数据块的引用次数设置为1；在客户端存储该新数据块的内容；在客户端的上述文件组成表中记录被写文件的标识、写入位置、该新数据块的大小以及该新数据块的标识。

(2-2-8)在客户端将上述被写文件的文件标识、每个新数据块的起始位置、每个新数据块大小和每个新数据块标识封装成一个文件组成更新消息，并将该更新消息添加到客户端的上述待发送消息队列的队尾。

(2-2-9)更新客户端的上述文件元数据表中被写文件的元数据，并将该更新后的元数据封装成文件元数据更新消息，并将该更新消息添加到客户端的上述待发送消息队列的队尾。

(2-3)当客户端的文件系统驱动接收到从已有文件读取数据的操作命令时，进行以下操作。

(2-3-1)根据操作命令中的被读文件标识、读取位置和待读取数据大小，计算出待读取数据区域，并在客户端的内存中分配与待读取数据的大小相等的内存空间，并将该内存空间初始化为空白；如图2所示。

(2-3-2)根据操作命令中的被读文件的文件标识和读取位置，从客户端的上述文件组成表中检索属于该被读文件的数据块标识，且与该数据块标识相对应的数据块是起始位置处于读取位置之前的最后一个数据块，若该数据块标识存在，且与该数据块标识相对应的数据块区域与待读取数据区域存在重叠，则从客户端读取该数据块内容，并将该读取的内容与待读取数据区域的重叠部分写入上述步骤(2-3-1)的内存空间的头部；具体过程可参见图3。从图3中，可以看出，网络文件系统中存在文件标识分别为1和2的两个文件，文件标识为1的文件由5个数据块组成，该5个数据块对应的数据块标识分别为A、B、C、D、E，文件标识为2的文件由3个数据块组成，该3个数据块对应的数据块标识分贝为A、D、F，客户端的文件组成表中记录了文件的组成信息。在图3中，操作命令中被读文件的文件标识为1，根据该文件标识，同时根据操作命令中的读取位置，从客户端的文件组成表中检索属于该被读文件的数据块标识，且与该数据块标识相对应的数据块是起始位置处于读取位置之前的最后一个数据块，就会得到数据块标识B，而且与数据块标识B相对应的数据块区域与与待读取数据区域存在重叠，因此，就要从客户端读取与B相对应的数据块的内容，并将该读取的内容与待读取数据区域的重叠部分写入图3中所示的内存空间的头部。

(2-3-3)根据该操作命令，从客户端的上述文件组成表中检索属于该被读文件的数据块标识，且与该数据块标识相对应的数据块的起始位置处于待读取数据区域内；在图2和图3所示例中，将会检索得到数据块标识C和D；遍历检索到的所有数据块标识，对每个数据块标识进行以下操作。

(2-3-3-1)判断客户端是否存有与该数据块标识相对应的数据块内容，若该内容存在，则读取该数据块内容，若该内容不存在，则从网络文件系统的服务器端下载该数据块内容，并在客户端存储该数据块内容。

(2-3-3-2)将上述数据块内容中与待读取数据区域的重叠部分写入上述步骤(2-3-1)的内存空间中；在该内存空间的中的起始写入位置等于该数据块的起始位置减去读取位置等到的差，以图2中将数据块标识为C的数据块内容写入该内存空间为例，由于读取位置为r，与C相对应的数据块的起始位置为b，因此，与C相对应的数据块内容将以b-r为起始写入位置被写入该内存空间中。

(2-3-4)更新客户端的上述文件元数据表中被读文件的元数据，将该元数据封装成一个文件元数据更新消息，并将该消息添加到客户端的上述待发送消息队列的队尾。

(2-3-5)将上述步骤(2-3-1)的内存空间中的数据通过客户端的文件系统驱动返回给客户端的应用程序。

(2-4)当客户端的文件系统驱动接收到删除已有文件的操作命令时，进行以下操作。

(2-4-1)从客户端的上述文件组成表中检索属于被删除文件的数据块标识。

(2-4-2)在客户端的上述数据块索引表中将与检索到的每个数据块标识相对应的数据块的引用次数减1，当引用次数变为0时，从客户端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块引用次数，从客户端删除该数据块内容。

(2-4-3)从客户端的上述文件组成表中删除被删除文件的所有记录。

(2-4-4)从客户端的上述文件元数据表中删除被删除文件的元数据。

(2-4-5)在客户端将被删除文件的文件标识封装成一个文件删除消息，并将该消息添加到客户端的上述待发送消息队列的队尾。

(3)在网络文件系统的服务器端设置的网络服务接口，用于上传和下载数据块内容，以及用于接收和应答客户端消息，具体过程如下：

(3-1)当网络文件系统服务器端接收到来自网络文件系统客户端待发送消息队列中的文件元数据更新消息时，进行以下操作。

(3-1-1)从接收到的文件元数据更新消息中解析出文件的标识及该文件的元数据；

(3-1-2)判断服务器端的上述文件元数据表中是否存在该文件标识，若已存在，则将与该文件标识相对应的元数据更新为上述步骤(3-1-1)中的元数据；若该文件标识为新标识，则在服务器端的上述文件元数据表中添加该文件标识及上述步骤(3-1-1)中的元数据。

(3-2)当服务器端接收到客户端待发送消息队列中的文件组成更新消息时，进行以下操作。

(3-2-1)从接收到的文件组成更新消息中解析出文件的标识以及每个数据块的起始位置、数据块大小和数据块的标识。

(3-2-2)在服务器端的上述文件组成表中检索属于该文件的数据块标识，且与该数据块标识相对应的数据块的起始位置处于新生成数据块区域之内。

(3-2-3)在服务器端的上述数据块索引表中分别将与检索到的每个数据块标识相对应的数据块的引用次数减1，若引用次数变为0，则从服务器端的数据块索引表中删除该数据块标识及与该数据块标识相对应的数据块的引用次数，从服务器端上删除该数据块内容。

(3-2-4)在服务器端的上述数据块索引表中检索上述步骤(3-2-1)的数据块标识，若该数据块标识已存在，则将与该数据块标识相对应的数据块的引用次数加1，若该数据块标识为新标识，则通知客户端上传与该数据块标识相对应的数据块内容，接收客户端上传的数据块的内容，在服务器端存储该数据块的内容，在服务器端的数据块索引表中添加该数据块的标识，并将与该数据块标识相对应的数据块的引用次数设置为1；由于避免了传输与服务器端已有的数据块标识相对应的数据块的内容，因此能够有效节省网络传输带宽。

(3-3)当服务器端接收到客户端待发送消息队列中的文件删除消息时，进行以下操作：

(3-3-1)从接收到的文件组成更新消息中解析出被删除文件的标识。

(3-3-2)在服务器端的上述文件组成表中检索属于被删除文件的所有数据块标识。

(3-3-3)在服务器端的上述数据块索引表中将与检索到的每个数据块标识相对应的数据块的引用次数减1，若引用次数变为0，则从服务器端的数据块索引表中删除与该数据块标识相对应的数据块的引用次数，从服务器端删除该数据块内容。

(3-3-4)从服务器端的文件组成表中删除属于该被删除文件的数据块记录。

(3-3-5)从服务器端的文件元数据表中删除该被删除文件的元数据。