FRONT互联网文件存储与共享系统.doc

FRONT互联网文件存储与共享系统刘斌 刘忠义网络实验室夏冰数据库实验室朱彬软工实验室摘要 本文受Freenet项目的启发，设计并实现了一个具备存储和共享功能的互联网分布式文件系统Files Reiable ON inTernet (FRONT)。FRONT在操作系统的文件系统之上提供了一层新的虚拟文件系统，上传到FRONT系统的文件被适当地切分并分配到网络中某些节点上。通过文件分块表或文件块复制和缓存，用户得以利用FRONT实现可用高效的文件访问。FRONT系统使用磁盘配额和固定共享空间比例的技术来配合这个虚拟文件系统，来解决P2P应用中的Free rider问题。Front使用Random Walk算法进行文件定位，并且在网路规模变化时保持系统中文件的高可用性和高性能。实验表明本文实现FRONT系统运行正确，性能有待进一步实验。关键词 分布式系统、P2P、网络存储、文件共享I. 介绍A. 工作动机今天互联网上已经有许多成熟的P2P文件共享系统，例如BT、迅雷、Maze等，它们的存在极大地丰富了普通网民可以访问的互联网资源。这些系统着重于将互联网上的文件以P2P的方式共享给更多用户。几乎在这些P2P共享协议在开始被研究和应用的同时（2001年），学术界也曾热烈地讨论过在互联网络上提供开放的存储服务的分布式文件系统，一些著名的系统包括CFS、Gnutella、FreeNet等。今天仍有一些个人和组织在这些协议的基础上开发扩展和应用。但是由于版权、用户激励、网络封禁等等原因，这些系统一直停留在研究阶段或者很小规模的应用。随着网络的普及和计算服务的无所不在，普通用户开始在一个以上的计算机上进行文件存取；并且越来越多的群体或组织的成员参与到互联网上的协作和共享。这样的需求可以使用分布式的文件存储和共享技术来满足。本文是几位研究生在学习分布式系统课程之后的一次尝试，希望开发一个具有一定可扩展性的分布式文件系统FRONT（Files Reliable ON inTernet），用户可以使用这个系统实现高效的文件存储与访问。B. 本文内容FRONT文件系统最主要受到FreeNet6项目的启发。FRONT系统无须依托任何基础设施，当文件存储或者共享的需求产生时，它即可从一台主机的规模开始扩展，在网络规模和共享空间逐渐扩大的同时，它可以持续提供高可用、高性能的文件存储与共享服务。FRONT采用用户磁盘配额的方式，让每一台主机向整个系统提供存储空间，并通过控制共享空间与用户需求空间的比例来避免free rider问题。FRONT系统对用户上传的文件进行适当地切分，使之映射为操作系统的文件系统之上的虚拟文件系统Front VFS中的文件。文件分块的设计让用户可以上传更大的文件，并且流行的文件块将被分配到更多的机器上，带来更高的访问性能。新的一层虚拟文件系统还造成了用户对磁盘空间使用的不透明性，又一次保证了客户端在使用系统的同时提供必要的服务。在文件分块后，系统中需要存储的数据包括文件的分块表和文件块两种类型。文件分块表使用“发布者用户空间”上的路径来定位，文件块使用对数据内容的哈希来定位。为了提供高可用性和高性能，FRONT在文件块的级别在系统中实现了复制和缓存。FRONT对于局域网构成的网络还做了特别的优化处理，让处在同一个以太网络内的本地用户高效地利用网络，并降低对整体网络的负担。另外，FRONT系统中节点的通讯组织方式提供了高效的文件查找功能。这些都将在下面的章节中系统介绍。下文的主要内容：第II部分描述了Front文件系统对于应用场景的假设，并分析在假设情况下的文件系需要解决的问题。第III部分是对Front文件系统的结构设计。第IV部分是本文的主要部分，介绍了开发Front文件系统的细节。第V部分讲述了Front文件系统的运行情况，分析对比了与其他文件系统的区别和特点。最后第VI部分是对本文工作的总结和展望。II. 假设和问题我们基于互联网上的存储和共享需求设计并实现了Front网络文件系统，为互联网用户提供了高效可靠的文件服务。它适用于在下文定义的一些假设情况，我们认为这些假设有较强的普遍性和适应性，满足了很多应用需求。这些假设包括以下几点：1） 互联网中存在多个节点，无论它们是否邻近。它们愿意共同组织一个文件存储和共享平台。这个平台可以选择由预先定义的用户组成，与Internet上可能存在的其他front网络没有交互。2） 每个参与的节点提供存储空间和一定的网络带宽。每个节点的空间组合起来构成全局大容量的存储共享空间。节点在自己的文件需要的容量之外还能够提供一定比例的“服务空间”，用于存储全局的其他文件，为别人提供服务。3） 文件系统的文件发布和下载对于用户来说好像本地的一样。节点上的用户不用关心文件传输的事情，包括文件内容从哪里获得、发往哪里。分布式系统数据复制和协议通讯对用户都是不可见的。4） 一些节点组成的分布式网络中。发布和下载的需求并不一定是对称的。例如在一个极端情况下，一个网络中总是由一个节点在发布（上传）文件，其他节点都是不同需要的下载者。5） 文件系统提供的语义是只读的。文件发布后即可由他人获得，但不可修改。6） 向Front网络上发布的文件可能很大，甚至大于本地节点提供的共享空间容量。但只要front网络平台上还有空间，它就应该上传成功。本文需要设计一个网络文件系统，满足以上假设的应用场景，并且保证这个分布式文件系统的高可用和高性能。需要解决的问题有下面3个方面：a) 本地文件系统首先，为了在本地保证用户提供的“共享空间”比例，Front在本地磁盘上的存取应该对用户有一定的不透明性。也即用户看不到是什么数据（在操作系统里看就是文件）占用了本地磁盘。一种可行的方案是，用户在操作系统里看到的存储文件不是发布到Front系统的文件的直接形式。发布的文件可以经过某种转化后存在磁盘上，用户不知道那个什么文件是自己需要的还是提供给他人的，因此不太愿意去冒险删掉其中的一部分。从这个角度上可以部分解决P2P系统的Free Rider问题。一种简单的磁盘存储不透明性可以用文件分块来实现。通过把文件切分成一定大小的文件块，可以自然的把系统上的众多文件数据“混淆”在一起。把文件分成块，还可以简化一个节点上传大于本地空间大小的文件的设计。另外，在分布式文件系统中，我们希望资源（包括复本）可以均匀的分布在更多的节点上，这样可以带来更高的可用性和性能。显然，当文件分成较小的块时，系统中的大文件也更加容易实现在网络中的这种分布。文件分块的一个额外开销是需要在这个网络中维护文件分块信息，并且对文件的请求被分为多个不走。另一个需要在本地处理的问题是，当资源请求超过了本地磁盘配额，如何权衡用户的需要得到满足和节点同时为网络提供存储服务的矛盾，Front系统本地需要一个安全有效的数据替换算法。b) 网络互联和文件查询网络上需要协作的Front节点需要一种办法来知道彼此的存在。节点加入和离开对网络的影响不能太大。因此当网络规模较大时，节点之间不可能两两可知的。相互可知的节点互为邻居，并且可以彼此交换信息，以增强网络连通性或者传递查询请求等。一个理想的网络连接情况是：临近（IP或者地理位置）的节点尽可能互为邻居，形成连通性较强的局部网络；距离较远的节点之间保持一定的连通，这样才能让远处的查询得到本地的信息，让整个网络的信息通畅。为了避免网络中的节点孤岛，需要一种方法显式地加入已经存在的网络。文件的查询涉及命名和查询路由。文件在系统的命名最好可阅读的，并且具有一定的区分性。后者让不同用户发布文件较难产生命名冲突。对于系统内部，对文件（可能被切分成文件块）的识别应该是唯一的，可以跟可阅读的文件名一一对应。另外，不同的用户可能发布完全一样的文件，应该被识别并且利用起来。当网络中的节点向路由器一样连接起来后，每个节点根据本地邻居信息，以一定的方式将请求和应答在分布式系统中传播，最终使请求发起者获得文件的信息。c) 数据复制和传输系统中的文件数据需要被合理地分配在分布式节点上。这一点保证系统中的文件以尽可能大的概率存在于网络中并且可达。同时对于文件的传输请求也可以向传统P2P网络中那样从多个目标节点同时开始。当文件被分块后，文件的结构信息也应该被广泛地分布于整个网络中，以使得被更多的节点可知。数据复制的触发可以放在发布时，当节点有可能探测到文件的复本可能在网络中下降时，或者很受欢迎被很多人请求时，也应该出发复制（在后一种情况中被称为缓存）。III. 系统结构设计为了解决第II部分提出来的几点问题，设计Front网络文件系统需要考虑的几个模块的交互。Front系统及节点的本地结构如图表一所示。图表 Front系统节点的本地结构系统中所共有的Front结构信息在common structures里定义。Front Virtual File System是本地与操作系统的文件系统交互的唯一模块，它通过将文件分块，并维持本地文件结构表和本地分块表，来向上层提供一层虚拟的文件系统。Networking component模块负责与其他节点的通讯和数据传输。在FrontVFS和Networking componet之上的一层是Front文件系统的对外接口FSClientNode。FSClientNode就好像一层中间件，可以向上层提供可以实现网络存储和共享的文件系统。在我们的实现中，我们设计了用户界面来调用FSClientNode，即实现了一个完整的客户端。关于每个模块的实现将在第IV部分介绍。IV. 实现FRONT互联网文件存储与共享系统的实现，分成以下5个部分来介绍。A. 命名Front文件系统的命名问题属于第V部分介绍的Front common structures部分。上文已经提到，每个文件应该拥有一个可阅读（human readable）的文件路径。这个路径在用户发布是制定。有namespace域和systempath域组成。文件系统内部使用的定位符(identifier)统一使用128位数据来表示。针对文件的定位符，根据可阅读的文件路径经过MD5计算得到。因此，请求文件的用户只要知道这个可阅读的文件路径即可发出请求。针对文件块的定位符，根据文件块数据内容经过MD5计算得到。这样当一个固定的文件被分块时，如果能够保证分块结构总是一致，那每一块计算得到的定位符也是相等的。这个特性有利于Front系统对发布相同文件的识别和利用。下文将会提到，Front VFS对于相同的文件，分块的结果是一致的。B. 本地文件系统FRONT VFSFRONT VFS是建立在操作系统文件系统之上的一层文件系统，用户与在整个系统中与FRONT VFS进行交互。对系统中存在的文件我们选择了对其进行分块。分块的好处首先在于一个节点存放不下的文件可以分开存储在多个节点上。第二，如果用户修改某个文件的一部分，重新发布时很可能有的块并没有变化，此时只需发布更改过的块即可。第三个好处在于可以均衡负载，用户可以同时从几个网络节点上下载不同的块来达到加速传输的目的。考虑下面一种情况：网络中有三个节点存储三个300M的文件，每个节点指定的共享空间为300M。那么，如果我们将三个文件都分成三个块，分布在三个节点。这样用户下载每一个文件时都可以从三个节点同时下载三个块，比文件不分块时必须从单个节点下载的情况效率要高。但是，分块同时带来了资源存在的不确定性。如果存放一个文件的某个块的节点关机，系统中又没有该块的备份，那么这个文件就无法被完整获得。分块越多分布越广越容易出现这样的问题。除了采取一定的复制策略外，我们的分块算法也保证一个文件不要分成太多的块。根据文件大小所在的不同区间，我们对文件采取不同的分块策略。分块算法如下：int chunkSize;int times = 1;int maxChunkNum = chunkNumStart;while(true)if( minChunkSize * times maxChunkSize )chunkSize = maxChunkSize;break;if( fileLength 0，则任选一个邻居把FILEQUERY发送出去。FILEQUERY的发起节点在启动RandomWalk之后，启动一个计时器，在这个时段内系统收集所有的应答(FILEREPLY)。每个应答中包含了文件的Chunk列表和本地保存的Chunk的列表。在计时器到期时，如果所有的chunk的信息都已经可用，则把结果显示到UI；否则再依次搜索每个未知未知的chunk。搜索chunk的方式也是K-RandomWalk。收到FILEQUERY丢弃FILEQUERY任选邻居转发FILEQUERY本地保存有请求的文件信息？FILEQUERY.TTL0？YNYN发送应答FILEQUERY.TTL-图表 3 FILEQUERY的路由Procedure QueryFile(fileKey)BEGIN FOR i in 0,minK,neighborCount DO BEGINNeighbor = getRandomNeighbor();Send FILEQUERY to neighborENDStart_timer(T_Query, collectQueryResult) /waits T_Query secods and then collect the resultENDProcedure recvFileQueryReply(reply)BEGINMerge reply.availiableChunks to receivedAvailiableChunks;Record chunk locations in receivedAvailiableChunks;ENDProcedure collectQueryResult()BEGINIF has full result THENDisplay result to UIELSE BEGIN Query remaining chunks like file query startTimer(T_chunk_Query, collectQueryResult) ENDEND 根据引文10的结论，在K=1664的情况下，K-RandomWalk能够得到很好的查询效率。 然而，简单的K-RandomWalk可能导致一定的低效率，原因包括： K次选择随即邻居有可能重复选择； 有可能造成环状搜索，即节点A选择了邻居B，B又选择了A（或者A选择了B，B选择了C，C又选择了A，等等）； 不同的Walker可能遍历相同的节点。其中，第一个问题很容易解决。然而，后面两个问题则不那么简单。事实上，一个有意思的研究问题是，如何使得K-Random Walk的效率最高（遍历的节点最多）？如何避免重复经过某些节点？一个简单的解决环状搜索（第二个问题）的方法是在Query消息中添加途经的节点列表，然后每个转发节点尽量选择不在途经节点列表中的邻居进行转发。然而，更进一步，如何使得不同的Walk之间的重叠尽可能的小？我们提出的解决方案是：(1) 为每个FILEQUERY添加一个序列号属性，每个FILEQUERY由唯一确定；(2) 添加主动HELLO消息，每当有FILEQUERY经过本节点时就广播主动HELLO，主动HELLO中包含近期所途经的M个Query消息的，主动HELLO的信息也添加到邻居表中；(3) 节点在进行转发决策时，就可以选择邻居列表中不曾收到过待转发请求的节点进行转发。E. 文件块的复制和传输当用户发布文件时，就需要发起文件复制。文件复制包括了复制触发点、块传输和文件的复制策略三方面。在设计这一部分时需要考虑到实现的灵活性和可扩展性。首先是复制触发点的设置。当用户发布文件时，显然需要触发文件复制。然后客户端需要主动地定时探测当前网络该文件的复制情况，当复本数长期小于额定值时，也是需要触发文件复制的。当出现替换文件块时，就需要主动地发起复制，最简单的情况就是将该块复制到某个其它的节点，但这样的复制没有全局的考虑。如果考虑了整个文件当前的复制情况的话，就可以收到更好的效果，例如可以请求发布文件的节点重新发起复制。其次，在考虑块传输时，有两种实现的方法：一种是使用多线程同步Socket的方法，一种是使用异步Socket的方法。使用异步Socket的方法虽然在效率上和多线程相近，但在代码的简洁性上显然不如多线程的方法。因此为了提高块传输的效率，以及追求代码的简洁，我们使用了多线程。每个块的传输都有一个线程对应，这样很好的减少了代码量和代码的复杂性。文件复制时存在很多的线程同时在传输，这时就需要有一个统一的线程来管理这些块传输的线程。每个文件复制的过程由一个线程控制，而每个文件块的传输也都由一个线程负责，这样的实现可以保证在用户发布文件时，不用长时间等待文件复制的完成，就可以进行下一步的操作。在实现之初，文件复制需要文件的本地分块完成之后才开始，这样就要求用户的本地空间足够大，显然这个要求过于苛刻。为了解决这个问题，我们需要在用户本地空间不够放下整个文件时，只要用户本地空间能都放下最大的文件块，用户仍然可以发布文件。在分块过程中，如果发现本地空间不足时，就需要等待当前文件块复制完成，再使用相应的替换算法替换不必要的文件块。这样的实现既提高了文件复制的效率，又无需用户长时间的等待，还能满足用户发布大文件的需求。再次，可以将文件的复制策略从文件复制中剥离出来，通过定义一个复制策略的基类，如果需要新的复制策略时，只需要继承这个基类，实现其中的方法。这样就可以在只改变少量代码的情况下就能实现扩展，定义新的文件复制策略。在实现具体的复制策略时，需要确定复制中候选节点的范围、复制节点的选择、文件块在这些节点的分配策略以及复制份数。这些方面并非各自独立的，某一方面的决策可能会影响另一方面的策略。候选节点的范围可以是在邻居节点或者整个网络。如果是邻居节点则较易实现，如果是在整个网络则需要通过邻居节点来试探整个网络，以得到潜在的候选节点，这些节点需要能够均匀的分布在网络中。在选择候选节点时，节点之间的距离（即两个节点间的最短跳数）是一个重要的参考，不同距离的节点就是有代表性的候选节点。在一个合理的网络中，各种不同距离的节点可以认为是均匀分布的，同时也考虑了网络的连通性，远端节点也覆盖到了。另外节点的IP地址也是很好的参考，通过IP地址和子网掩码可以了解节点之间的关系，相同网段的节点可以认为具有较近的地理位置，不同网段的节点也是有代表性的候选节点。复制节点选择的复杂性同候选节点的范围有关，当候选节点的范围较小时，复杂性相对会低一点。选择复制节点需要考虑节点的网络带宽、存储余额等，网络带宽较大或者存储余额较大的节点较易被选中，同时还需要考虑节点数，一种策略是一个文件复本应尽量在少量的节点上，以确保文件的可用性。除此之外，选择有代表性的节点也是很重要的，能够考虑整个网络的全局信息，选择最佳的复制节点也是需要考虑的因素。文件块的分配策略需要考虑到均衡性，尽量保证文件块均匀的放置在这些节点中，同时还需保证相同的文件块复本不应放在同一个节点上。这样的策略不仅是为了公平而均匀的使用用户共享的空间，同时也是基于多线程的考虑，均匀的分配有利于充分利用网络带宽，在尽可能短的时间内完成复制。考虑到候选节点的选择策略，距离较接近的节点和相同网段的节点倾向于拥有一个复本，当然两个复本所占用节点的交集应当尽量小，这些节点往往连通性较好，地理位置较近，这样即使网络出现了问题，在网络的某个局部仍然可以保证文件的可用性。至于复制份数，可以根据当前网络的大小和网络存储空间的大小来确定，网络的大小可以通过探测节点之间的距离和网络中的节点数来获得，网络的大小同节点之间的距离和网络中的节点数成正比，当然其中节点数的比重应该更大。节点数多、节点间距离大，那么复制份数就可以多一点。网络存储空间的大小可以通过试探各个节点的存储余额来估算。在获得相当数量的存储余额后，通过简单的求平均来得到当前网络中节点的平均存储余额，余额越多，那么复制份数就可以越多。V. 性能与相关工作由于Front文件系统和其它类似系统在应用场景的区别，难以构造同样的环境对比。并且由于时间和网络环境的限制，我们只在3个节点的网络规模上进行了测试。实验中文件发布、复制和下载功能均得到正确的结果。在本文之前的大多数P2P文件系统，例如迅雷、Bt等，都提供的是文件共享的服务。本文试图使用文件分块的技术提供具有一定扩展性的网络文件存储和共享系统。不同于使用DHT结构的一些系统，例如Chord等，Front系统的设计目标是尽可能地提供高可靠、高性能的文件服务，同时降低对网络负载的影响。Front文件系统使用文件分块实现了一层操作系统文件系统之上的文件层。磁盘上文件的不透明性一定程度上促使用户向网络提供一定比例的空间服务。Front系统使用Random Walk算法进行文件定位，一定程度上降低了网络开销，但查询的时间可能会较长。VI. 总结和展望从Front文件存储和共享系统的运行试验中我们得知，Front系统的功能可行，但是由于时间和测试的限制，系统在较大网络规模上的性能还未知。之后的一项重要工作是进行更多的测试，发现系统性能在较大规模网络上的影响因素，并设计策略进一步提高可用性和性能。其他一些已知的需要改进的地方有：1） Front文件系统是只读的。无法显式删除一个已经发布的文件，以释放全局空间。2） 文件块的复制，需要在更多的情况下触发。以避免文件内容慢慢地在网络中消失。3） 现在的文件定位算法Random Walk，还需要性能