基于删冗的云存储文件系统客户端的实现.doc

1、目 录第1章引 言11.1 背景介绍11.2 服务器端Aegean System1第2章客户端的实现32.1 客户端文件系统的实现32.1.1 列目录请求.112.1.2 创建目录请求.272.1.3 移动文件请求.282.1.4 删除文件请求.292.1.5 重命名请求.302.1.6 文件的读写.312.2 客户端功能的实现.332.2.1 文件上传的实现.332.2.2 文件下载的实现.352.2.3 用户管理的实现.37第3章客户端删冗.393.1 基于内容分块39 3.2 分块算法TTTD算法.40 3.3 删冗的实现.42第4章客户端演示及论文总结464.1 功能演示464.2 论

2、文总结48插图索引49表格索引50参考文献51致 谢52声 明53附录A 外文资料的书面翻译54附录B 客户端与服务器端信息交互格式示例6551第1章 引 言1.1 背景介绍云存储在云计算概念上发展出来的一个新的概念，而云计算是分布式处理、并行处理和网格计算的发展，是透过网络将庞大的计算处理程序自动分拆成无数个较小的子程序，再交由多个服务器所组成的庞大系统经计算分析之后将处理结果回传给用户。通过云计算技术，网络服务提供者可以获得与“超级计算机”同样强大的网络服务在数秒之内，处理数以千万计甚至亿计的信息。概念上，云存储与云计算类似，它是指通过集群应用、网格技术或分布式文件系统等功能，将网络中大量

3、不同类型的存储设备通过应用软件集合起来协同工作，共同对外提供数据存储和业务访问功能的一个系统。本文中所用到的服务器端就是一个云存储文件系统基于广域网的分布式文件系统，而我所做的工作就是实现一个具有删冗功能的客户端，客户端的实现要以用户空间文件系统的形式实现，这里使用了开源项目Fuse，用它在ubuntu上实现一个用户空间的文件系统，具体介绍见下文客户端的实现中将有详细介绍。而客户端所对应的服务器端的实现虽然不是本文所关心的，但如果对服务器端不了解的话，客户端就没有了意义。下面我们将对Aegean System做一简单介绍。1.2 服务器端Aegean SystemAegean System是一

4、整套完整的广域网分布式存储系统，由基于key-value后端分布式存储服务(Aegean Store)、支持版本控制的文件系统表示层(Aegean FS)和各种存储应用(Aegean Sync、Aegean Share，etc)组成。系统目标是提供一个通用高可扩展的存储服务，并且具有良好可用性的文件系统语义(易于管理、迁移、开发)和高可靠的多版本支持。面向用户的应用可以方便将数据存储在Aegean System中，如同使用本地文件系统，但用户可以在互联网任意地点高效访问自己的数据，同时系统保证数据的可靠和任意时刻的数据回卷。图1即Aegean System的部署示意。而本文所做的内容属于Aeg

5、ean Sync的一部分，即对存储的应用，利用Aegean System提供的通用高可扩展的存储服务等实现一个客户端，使得用户可以进行注册、登录、登出，在互联网的任意地点高效访问自己的数据，如同访问本地的一个硬盘上的数据一样，当然，这样的实现还要借助于Fuse，这个下文将进行介绍。图1.1 Aegean System 部署示意1第2章 客户端的实现2.1 客户端文件系统的实现首先要对Fuse进行介绍，Fuse的全写是Filesystem in Userspace，即用户空间的文件系统，利用Fuse我们可以很容易地实现一个具有完善功能的用户空间文件系统，而且具有以下优点：l 简单的API库，容易

6、读懂并且便于利用；l 安装简便，不需要补丁以及编译操作系统内核；l 很好的稳定性；l 用户空间跟内核的接口非常高效；l 可以被非特权用户使用；l 运行在Linux内核上，支持版本为2.4.X和2.6.X；l 稳定性久经证明。实现一个文件系统将会因此而变得非常简单，一个hello world文件系统的创建将会不超过一百行代码，下面就是一个例子：/fuse/example$ mkdir /tmp/fuse/fuse/example$ ./hello /tmp/fuse/fuse/example$ ls -l /tmp/fusetotal 0-r-r-r- 1 root root 13 Jan 1

7、1970 hello/fuse/example$ cat /tmp/fuse/helloHello World!/fuse/example$ fusermount -u /tmp/fuse/fuse/example$Fuse的安装也非常简单，安装过程如下： ./configure make make install那么Fuse是怎么工作的呢？如下图所示：实际上我们使用一个命令比如ls时，这个命令被截获并传给了Fuse，而Fuse中有相应的函数对此进行处理，当然如何处理是需要我们来完善的，之后把结果返还给用户，我们就看到了文件目录下的文件列表。图2.1 Fuse工作原理图2实际上，本文直接使用的

8、并不是Fuse，而是Fuse-j，也就是Fuse的java包，这个包使得我们可以用java语言实现用户空间文件系统，下面我们对Fuse-j进行简单介绍。Fuse-j是Fuse的一个java语言包，也就是说Fuse-j的运行还是依附于Fuse的，只是我们可以通过java语言来编程实现，具体的细节由于不是本文的重点，所以不再详细介绍，下面对Fuse-j的安装和使用进行说明。首先我们必须安装Fuse的内核组件和库，而且通常Fuse的库被安装到目录/usr/local/lib下，而头文件被安装到/usr/local/include目录下。如果把Fuse安装到了别的目录下，我们就需要编辑build.co

9、nf和FUSE_HOME变量，使得其指向Fuse的库和头文件所安装的目录。而且我们需要JDK1.4或者更高的版本。这主要是因为它利JNI_VERSION_1_4，比如java.nio.ByteBuffer。编辑build.conf并且设置JDK_HOME变量指向JDK安装目录。然后运行“make”命令。这个命令将首先编译src目录中的java源代码成为class文件并且保存到build目录中，然后运行JNI包生成程序，产生两个文件：jni/javafs_bindings.h和jni/javafs_bindings.c。之后链接库jni/libjavafs.so将会被生成。那么Fuse-j该如何

10、使用呢？Fuse-j由两个部分组成：l JNI链接库（jni/libjavafs.so)；l 用java语言完成的API，用以实现文件系统。由于安装包中包含了一个示例文件系统，也即是ZIP文件系统，它可以把一个ZIP压缩文件mount到一个指定的挂载点，然后可以进入文件夹中查看及读取文件，如同本地的一个文件目录一样，这只需如下命令即可： cd fuse-j-build-dir ./zipfs_mount.sh some.zip /mnt/point然后还可以卸载它： fusremount -u /mnt/point下面我们总结一下如何完成我们自己的文件系统：1 完成fuse.Filesyste

11、m接口；2 调用fuse.FuseMount.mount(String args, fuse.Filesystem filesystem)，其中args是传递给Fuse库中的fuse_main函数的参数序列，其中必须包含：l 挂载点作为第一个参数；l 可选的选项作为第二以及随后的参数。文件系统就是完成fuse.Filesystem接口的一个实例；3. 可以运行命令进行试验。ls -al /mount/point上面对Fuse和Fuse-j进行的简单介绍，下面根据我们的需求来实现所需的客户端文件系统。既然是客户端，我们就要设计与服务器端的通信方式等细节，比如客户端的注册、登录等等。首先我们设计用

12、户管理部分，考虑我们要实现基于删冗的云存储文件系统客户端，那就意味着我们可以在任何一台拥有客户端的机器上登录到云存储文件系统，并且把自己的工作目录挂载到本地，那么如何实现呢？显然需要用户管理。登录服务器端需要我们输入用户名密码等信息，当然还需要注册以及登出等相关信息。所以有了表1中1、用户管理的设计，其中messageType用来标识每一种信息的类型，方便确认不同的信息进行不同的处理。用户注册需要提供用户名、用户ID、密码等信息，注册成功的话服务器端应该返回通用成功返回信息，否则返回通用错误返回信息，其中errno为错误类型编号，detail为错误的详细信息，这样的话说明我们注册失败，可能是用

13、户名重复等等错误，需要我们重新注册。而用户登录部分，除了提供用户名、密码之外还要提供一个location，这个参量表示用户的域，当然这里我们可以随便定义。用户登陆成功的话我们会收到用户成功登录的返回信息，messageType为4，内容包括session、name、quota、used等，分别表示会话、用户名、分配空间、已使用空间，收到这个信息就表示登录成功，并且session在后面的整个操作中都要使用，直到登出为止。当然如果我们没有收到成功的信息，就说明登录失败，这时会收到通用错误返回信息，根据错误信息重新登录。而登出只有在完成所有操作卸载网络文件系统之前进行用户登出。然后就是文件管理，其实

14、就是文件系统的实现，首先我们考虑一个文件系统需要什么呢？起码能显示出文件目录，哪个文件夹下有哪些文件又有哪些文件夹；可以移动文件，把它从一个文件夹下移到另外一个文件夹下；可以删除文件等等。这些都是我们平常在文件系统下常用的命令，假如插到电脑上一个移动硬盘或许很容易就能这样做，因为操作系统提供的支持，但对于我们的云存储文件系统呢？显然要靠我们自己去实现这些功能。我们的目标操作系统是Linux操作系统，这里使用的是Ubuntu8.10，之所以这样是因为我们要使用一个Linux下的开源项目Fuse，前面已经介绍过，借助它我们可以不用编译内核，省去很多麻烦，而且能够实现一个稳定的用户态的文件系统。实际

15、上Fuse对基本的文件系统命令都提供的支持，也就是说我们在文件系统中使用这些命令的话Fuse都可以帮我们截获，但具体如何处理，返回什么结果是要靠我们来定义和提供的。常见的如列目录（ls、dir）、创建目录（mkdir）、移动文件（mv）、删除文件（rm）、重命名（mv，这里通过不同的参数我们用一个命令在一个函数里实现了不同的功能）。首先对于列目录，简单的看只是一个命令，实际上这个命令的实现是其它所有命令的基础，我们首先要获得服务器端我们需要的目录以及它下面的文件目录等等信息，这里我们可以首先向服务器端请求目录，然后服务器端会返回我们文件目录列表，其中包括文件目录的结构和文件以及文件夹的属性等信

16、息。之后的处理下文会介绍。对于创建目录、移动文件、删除文件、重命名等命令主要工作就是本地操作，然后要告诉服务器端相应进行了什么操作。其中对于文件目录来说如何表示是一个难题，因为一个文件目录包含文件夹的结构、文件夹的属性、文件的属性等等，是一个树结构，如何表示呢？这里我们采用面向对象的方法，定义DirEntry表示文件夹入口、FileEntry表示文件入口，这里入口的意思就是通过这个对象我们可以获得它的所以信息，比如对于根目录来说，就可以把它当作一个DirEntry，它包含什么呢？文件夹的名称String name;文件夹的逻辑属性String magic;文件夹的时间属性long timest

17、amp;文件夹的可扩展属性boolean expanded;还有最重要的是文件夹下的文件或者文件夹等目录结构List dirList;List fileList。由于DirEntry对象中包含了子文件夹对象和子文件对象的链表结构，可以很容易用一个对象表示整个目录树，当然还有一些细节难题后面我们会处理。对于文件我们定义FileEntry，包括文件名String name;文件大小long size;文件时间属性long timestamp;以及文件的版本int version。由此我们设计了文件目录的表示方法。对于文件来说，仅有文件的管理是不够的，因为我们还需要文件的修改。不同于本地文件的修改，

18、我们必须要保持客户端与服务器端的同步和一致，当然不同的情况下以哪方为准是有不同的要求的，当我们成功登陆服务器端后，首先要挂载服务器上的工作区到本地，那么我们就需要下载文件，这样就是以服务器端为准进行的同步，当然假如本地已经有文件存在的话我们就可以通过删冗使得尽可能少地通过网络传输数据。当我们对文件进行了修改之后，我们需要把自己的工作进行保存，当然就需要上传文件了，这时我们就是以客户端为准，向服务器端上传文件，由于服务器端本身就有该文件，那么我们如何才能尽可能少地进行传输呢？同样的道理，我们在本地对文件进行删冗处理，当然具体的方法跟下载是不同的，后文会详细介绍。所以我们就要设计信息交流方式使得我

19、们的想法能够实行。对于文件上传，我们可以令int messageType = 11，信息内容还要包括用户String id、会话Session session（用户登录时得到）、文件的路径String path、是否使用新的网络连接boolean newConnection，最后就是最重要的部分List chunkList（其中Chunk:byte32 key; long size;），表示本地文件的文件块列表，文件块通过基于内容分块算法得到，这里的块只包括快的key通过对块求SHA-1码并且扩展到32位、块的大小size，而文件块的内容则不需要传输，当我们收到返回信息时再进行处理。根据需要我

20、们要得到服务器需要哪些数据块、以及服务器如何接收这些块等信息，于是可以这样设计上传返回信息，令int messageType = 12，而List chunkList表示需要上传的文件块，也就是说我们需要用数据通道进行数据传输，这时boolean newConnection应该为true，对应应该告诉我们String host和int port使得我们创建新的socket连接，将服务器端需要的文件块的内容传输过去。文件下载的话就更复杂一点，首先我们要以服务器端的文件为准，但我们并不想直接把服务器端的文件直接下载下来，虽然这样也是可行的而且对我们来说处理会简单得多，但那样无疑会牺牲大量的网络流量

21、和传输时间，而且容易导致数据传输错误。我们的做法是首先发送一个请求给服务器端，告诉它我们要下载哪个文件，即请求信息要包括文件的路径，但chunk列表为空。之后服务器要把该文件的chunk列表返回，当然包括所有的块，此时我们掌握的资源包括服务器端的文件的chunk列表和本地文件的chunk列表，而我们的目的是使本地获得服务器端的文件，这样的话就要对两个列表进行匹配，当然是以服务器端为准，假如是服务器端和客户端都有的文件块或者服务器端没有而客户端有的文件块则不需要处理，我们关注的只有那些服务器端有但客户端没有的块，这些块就是我们删冗后得到的块，然后我们再次发送下载请求，不同的是这次我们的chunk

22、列表包含了那些删冗后的块，另外我们还要告诉服务器端我们新建的连接的主机和端口号，接着我们就进行数据传输，当收到所有的块之后，我们就可以在本地根据服务器端的chunk列表获得该文件的所有块的列表，进而可以很容易地合成本地的文件。文件下载就这样完成了，于是有了表1中的设计。当然，对于文件上传和下载我们都需要进行数据传输，数据传输需要开新的端口，而且不再是用xml来传递信息，我们需要定义新的协议内容，也就是数据的传输协议。首先我们进行登记，内容还是我们之前登录时获得的session，获得成功返回后我们进行数据的传输，每个数据块的传输遵守这样的格式：首先我们发送一个四位的整型表示整段数据的长度，包括数

23、据类型Type，文件块byte32 key，之后是文件块数据byteother data。成功的话会收到成功返回，失败的话会收到失败返回。当然，接收时是相反的过程。根据以上分析，所需实现的功能及要求如下：表1 系统接口0、通用成功返回：int messageType = 0;错误返回：int messageType = 1;int errno;String detail;1、用户管理用户注册请求:int messageType = 2;String id;String name;String password;用户登录请求：int messageType = 3;String id;Strin

24、g password;String location;用户登录返回：int messageType = 4;Session session;String name;long quota;long used;Session:byte16 session;用户登出请求：int messageType = 5;String id;Session session;2、文件管理列目录请求：int messageType = 6;String id;Session session;String path;列目录返回：int messageType = 7;DirEntry root;DirEntry:St

25、ring name;String magic;long timestamp;boolean expanded;List dirList;List fileList;FileEntry:String name;long size;long timestamp;int version; 创建目录请求：int messageType = 8;String id;Session session;String parentDir;String dirName;移动文件请求：int messageType = 9;String id;Session session;String srcPath;Strin

26、g dstPath;/语义改变，要移动到的目标目录，不能用作rename删除文件请求：int messageType = 10;String id;Session session;String path;新增：rename接口:int messageType = 15;String id;Session session;String srcPath;String dstPath;/新文件名，复用move，只修改messageType3、文件修改文件上传请求：int messageType = 11;String id;Session session;String path;int versio

27、n;boolean newConnection;List chunkList;Chunk:byte32 key;long size;文件上传返回：int messageType = 12;List chunkList;boolean newConnection;String host;int port;/建立新的tcp连接，用于传送数据，数据格式见4，首先发送session，收到确认（不含key），/再发送数据块，然后等待成功返回，接着再传数据块。文件下载请求：int messageType = 13;String id;Session session;String path;int vers

28、ion;boolean newConnection;List chunkList;文件下载返回：int messageType = 14;List ChunkList;boolean newConnection;String host;int port;down过程：1发送DownloadRequeuest,其中chunkList为空2返回DownloadReply，其中ChunkList为文件所有块的key3再次发送DownloadRequest，其中ChunkList不为空，是删冗后需要下载的新块4、数据登记session：byte type = 0;byte16 session;数据块：

29、byte type = 1;byte32 keybyteother data数据返回：byte type 2;byte32 key/等级session返回时没有这部分byte state = 0 成功 1 失败/每个信息传递都有一个int头，代表整个数据的长度根据以上要求可知，我们在文件系统中，至少要实现ls、dir、mkdir、rm、mv、touch等文件管理命令。而根据Fuse的API可得如下实现：2.1.2 列目录请求列目录的实现，命令为ls或者dir，我们首先需要获得服务器端的文件目录，也就是说连接服务器后便要向服务器发送命令请求文件目录，然后获得文件目录列表，当然我们的通信都是固定格

30、式xml文档，解析获得的xml信息，之后我们在本地创建一个文件目录树，所有的维护都将在树中进行。对于文件目录来说如何表示是一个难题，因为一个文件目录包含文件夹的结构、文件夹的属性、文件的属性等等，是一个树结构，如何表示呢？这里我们采用面向对象的方法，定义DirEntry表示文件夹入口、FileEntry表示文件入口，这里入口的意思就是通过这个对象我们可以获得它的所以信息，比如对于根目录来说，就可以把它当作一个DirEntry，它包含什么呢？文件夹的名称String name;文件夹逻辑属性String magic;文件夹的时间属性long timestamp;文件夹的可扩展属性boolean

31、expanded;还有最重要的是文件夹下的文件或者文件夹等目录结构List dirList;List fileList。由于DirEntry对象中包含了子文件夹对象和子文件对象的链表结构，可以很容易用一个对象表示整个目录树，当然还有一些细节难题后面我们会处理。对于文件我们定义FileEntry，包括文件名String name;文件大小long size;文件时间属性long timestamp;以及文件的版本int version。由此我们设计了文件目录的表示方法。表2就是我们获取文件目录的主要代码，我们根据代码来对我们的实现进行说明，1-7行主要就是定义列目录请求，路径为/，表示获取工作区

32、的根目录，也就是说我们要把整个工作区的文件结构全部获取，为什么呢？我们要在本地把整个文件文件目录保存起来，首先要做的就是如何获取文件目录，我们在8-10行中通过将获取文件目录请求发送给服务器端来获取文件目录。具体如何获得呢？11行，br.readInt()获得信息的头部，这个头部指的是xml信息的长度，所以我们可以定义字节数组sb1，其长度即为br.readInt()，之后我们就在12行读入一个长度为br.readInt()的字节序列到数组sb1，13行将该数组转换成UTF-8格式的字符串，方便下面进行xml解析。15行通过xml工厂的解析我们获得了整个文件目录的DirEntry，具体如何解析

33、下文详述，然后我们根据获得的文件目录创建文件目录树，17-27行即为创建目录树的过程。首先我们定义一个根结点，这个根结点并不是DirEntry的表示的根结点，为什么呢？一方面后面递归操作创建目录树，这样写比较方便；另一方面根结点表示默认目录，这样使得DirEntry的根结点成为空结点的子结点。目录树的定义见下文。表2 获取文件目录1. String listRequest = 2. + 63. + 4. + id5. + /6. + session7. + ;8. dout.writeInt(listRequest.length();9. dout.write(listRequest.getB

34、ytes();10. dout.flush();11. byte sb1 = new bytebr.readInt();12. br.readFully(sb1);13. String listReply = new String(sb1, UTF-8);14. ParseFactory parser = new ParseFactory();15. DirEntry dir = parser.parseFromXML(new InputSource(new StringReader(16. listReply);17. String path = dir.name;18. tree = ne

35、w Tree();19. DirEntry rootEntry = new DirEntry();20. rootEntry.dirList = null;21. rootEntry.expanded = true;22. rootEntry.fileList = null;23. rootEntry.magic = ;24. rootEntry.name = ;25. rootEntry.timestamp = dir.getTimestamp();26. tree.addNode(rootEntry.name, rootEntry);27. parser.buildTree(tree, d

36、ir, path);有上文可知文件目录树所起的作用有多么重要，我们所有的操作都体现在对目录树的操作上，而且本地所有的查询也是依据文件目录树，比如我们对某个文件进行操作，我们如何获得这个文件的信息？甚至于我们如何找到这个文件？目录树。只有通过目录树才能完成这些操作，那么我们如何来设计这个目录树呢?想像一下我们的文件系统，我们要进行哪些操作？这些操作会如何影响目录树，而文件目录树又将如何影响我们的内容？我们需要实现ls、dir这样的命令，也就说对于某个文件夹，我们使用这两个命令中的一个的话，我们就可以获得该文件夹下所有文件和文件夹的名称列表，那么我们的文件目录树是否需要能通过某个结点获得它的所有子

37、结点？这需要在树中或者结点的定义中加以实现，这里我们把它们在结点的实现中进行处理，见表10，后面将进行详解。对于创建目录命令mkdir我们的文件目录树又要做什么呢？显然我们创建一个新目录的话，就要增加一个树的结点，那么我们就要定义addNode函数；对于移动或者重命名文件（这里我们用mv命令），我们不仅需要增加新的文件结点，还要删除旧的文件结点，那么delNode函数就必需要被定义；当然对于删除文件命令rm来说更是如此。另外任何对结点的操作，不管是增结点也好还是删除结点也好，如何判断结点是否存在并且找到这个结点呢？查询结点的函数必须要被定义。根据以上分析，对文件目录树的定义，至少要可以增加结点

38、（addNode），删除结点（delNode）和查询结点（lookupNode），它们实际上对应着文件系统的各种操作，比如增加结点会在创建目录和文件时用到，而删除节点则会在删除文件时被调用，而查询结点则更常用，很多时候都会用到，具体实现如下：表3中2-7行我们定义并且设置了根结点，其实根结点的定义对文件系统内部的文件操作并没有什么大的影响，为什么这么说呢？我们所说的路径基本都是相对而言的，我们根据相对的路径就能完成各种操作，可以这么说，只要不超出某个文件夹的范围，这个文件夹叫什么名字对我们来说都是可以忽略的。8-30行是对addNode函数的定义，上文我们已经分析过这个函数的重要性，它的作用顾

39、名思义就是添加结点的，参数一个是路径，一个是结点对象本身，可以是DirEntry或者是FileEntry，既然是增加结点，那么增加到哪里？如果不知道它是哪个结点的子结点的话肯定是没办法的，那我们如何得知它是哪个结点的子结点呢？路径path通过10行用/进行划分成为几个字符串之后，就顺序表示一系列的父子结点关系，根据命令行下的规矩，空格和.表示同一个结点，而“.”则是上一级结点，11-18行对这两种情况进行了处理，19-30行直到找到父结点之后增加一个子节点为止。31-34行实现了函数delNode，首先调用了查询结点函数找到之后把该结点从父节点的子节点中删除，有意思的是，虽说这里是要删除自己，

40、怎么办呢？就把自己从父亲的儿子序列里删了，让父亲找不到就行了。下面介绍的是最重要也是最常用的一个函数，Node lookupNode（ptah）只需知道结点的路径就可以返回该结点，这是如何实现的呢？35到53行就是它的实现，看了之后感觉跟addNode的实现几乎一样，其实我们查询结点跟添加结点本身就差不多，实际上我们添加结点是一直找到要添加结点的父节点，然后创建新结点，而查询的话就是省去了添加结点，因为找到的话就返回找不到的话就是不存在而不是添加一个新的。根据以上分析，文件目录树的定义如下：表3 文件目录树的定义1. public class Tree 2. Node rootNode;3.

41、public Tree() 4. rootNode = new Node();5. rootNode.setName($ROOT);6. rootNode.setParent(rootNode);7. 8. public void addNode(String path, Object value) 9. Node node = rootNode;10. String pathParts = path.split(/);11. for (int i = 0; i pathParts.length; i+) 12. String pathPart = pathPartsi;13. if (pathPart.equals() | pathPart.equals(.) 14. / the same node15. else if (pathPart.equals(.) 16. / parent node17. node = node.getParent();18. else 19. Node childNode = node.get