云端文件高效传输与存储机制的设计与实现

密级:_硕士学位论文云端文件高效传输与存储机制的设计与实现 作者姓名： 张闵 指导教师： 叶丹 研究员 软件研究所 学位类别： 工学硕士 学科专业： 计算机软件与理论 培养单位： 大学 2013年 4 月Design and Implementation of an Efficient Cloud File Transfer and Storage MechanismByLv Ying A Dissertation Submitted toUniversity of Chinese Academy of SciencesIn partial fulfillment of the requirementFor the degree ofDoctor/Master of Computer Software and TheoryInstitute of Software, Chinese Academy of SciencesApril, 2013独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明。签名：_ 日期：_关于论文使用授权的说明本人完全了解软件研究所有关保留、使用学位论文的规定，即：软件研究所有权保留送交论文的复印件，允许论文被查阅和借阅；软件研究所可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后应遵守此规定）签名： 导师签名： 日期： 中国科学院软件研究所硕士学位论文摘要云端文件高效传输与存储机制的设计与实现摘 要随着现代信息数据的爆炸式增长和云计算技术的飞速发展，云端文件存储系统得到众多企业的青睐。云端文件存储系统具备敏捷性、可扩展性、弹性和多租户等诸多特性，为企业提供文件备份、移动办公、文件共享等服务。其中文件共享服务已成为系统核心服务之一。对于云端文件存储系统而言，网络带宽资源和存储成本昂贵，海量用户的并发访问负载始终是其面临的重要问题，而这些问题在文件共享服务场景中尤为显著。为解决上述难题，论文设计与实现了一套高效的云端文件传输与存储机制，一方面基于增量传输算法优化文件传输过程，另一方面利用冗余数据删除技术优化文件存储过程，从而达到减少网络传输开销和提高存储利用率的目的。首先，论文介绍了云端文件存储系统传输与存储的相关技术，包括云存储系统和文件共享服务的研究概述、传统文件传输方法、业内通用的存储去重算法。然后分析这些传输方法和存储算法对于处理上述难题存在的局限性和不足，提出了针对云端文件的高效传输与存储机制。接下来，重点研究了文件传输与存储机制的关键技术和难点：在传输方面，针对文件高并发和网络带宽紧张的难题，设计了一种基于增量的传输机制，挖掘文件历史版本的相似性，达到减少数据传输量、缩短传输时间的目的；在存储方面，针对相同数据冗余存储导致文件存储成本提升的问题，设计了基于滑动块的存储去重机制，在文件存储之前定位文件相同数据块并进行删除，达到减少文件存储空间的目的，节约单位文件存储成本；针对云端文件传输和存储的特点，论文对传输机制的文件下载流程进行优化，有效减少服务器端压力；对存储机制的内存数据缓冲区进行优化，有效地减少存储任务的内存占用量，提高并发场景中磁盘和内存访问的限度；对系统存储分块和传输分块设定统一大小，简化分块合并分割过程。最后，论文介绍了基于增量的传输机制和基于滑动块的存储机制的具体设计与实现过程。基于上述研究成果，开发实现了云享云端文件存储与共享平台中的云端文件共享服务、文件存储服务等模块，并通过多组实验验证了论文设计的传输与存储机制的有效性和优越性。关键词： 云存储，增量传输，存储去重，并发访问，文件共享I中国科学院软件研究所硕士学位论文AbstractDesign and Implementation of an Efficient Cloud File Transfer and Storage MechanismLv Ying (Computer Software and Theory)Directed by Dan YeAbstractWith the explosive growth of modern information and the rapid development of cloud computing, more and more companies pay attentions to Cloud File Synchronization System. Cloud File Synchronization System has many features and provides file backup, work outside office, file-sharing services. Among them, file-sharing has already been one of core service. Limited network bandwidth and expensive storage cost and multiply requests from mass users are always the important problems that Cloud File Synchronization System meets. And these problems are more critical in file-sharing situation.In order to solve these problems, this paper designed and implemented a file transfer and storage mechanism. On the one side, the increment-based algorithm optimized the file transfer process. On the other side, deduplicated data technique optimized file storage process. As a result, network transfer expense decreased and storage usage increased.Firstly, this paper introduced the relative work of transfer and storage in Cloud File Synchronization System, including summary of cloud storage and file-sharing service, traditional file transfer methods, popular deduplicated data algorithm. Then analyse the drawbacks of these methods and algorithm while dealing with the problems described above. Present an efficient file transfer and storage mechanism. After that, this paper focuses on the key technique of file transfer and storage mechanism. In the aspect of file transferring, this paper designed a transfer mechanism using an increment-based transfer algorithm. In the aspect of storage, this paper designed a storage mechanism using rolling-block algorithm. According to the feature of cloud file transfer and storage, this paper optimizes the download process, improves the concurrency count by optimized memory buffer usage of storage mechanism and keeps same size of the transfer and storage blocks. Finally, this paper introduced the specific design and implement of increment-based file transfer mechanism and rolling-block-based storage mechanism.According to the Research findings, the file transfer and storage mechanism has many features such as efficient, increment-based, high concurrency and low storage occupied and so on. And it works well for Cloud File Synchronization System, especially for file-sharing service situation. This paper takes a series of experiments to verify that the file transfer and storage mechanism is superior to traditional ones.Key words： File Storage, Increment-based transfer, Storage Deduplication, Concurrency Request, File sharingV中国科学院软件研究所硕士学位论文目录目录摘 要IAbstractIII第一章 绪论11.1研究背景11.2论文主要工作31.3论文内容组织4第二章 云端文件传输与存储的相关技术52.1云端文件存储系统52.1.1云存储服务概述52.1.2文件共享服务的相关工作52.2文件传输相关技术72.2.1传统的文件传输72.2.2增量传输算法Rsync92.2.3云端文件的传输问题分析112.3文件存储的相关技术112.3.1相同数据删除技术122.3.2云端文件的存储问题分析132.4云享云端文件存储与共享平台132.4.1系统架构132.4.2文件共享服务142.4.3云享系统的文件传输与存储142.5本章小结15第三章 云端文件传输与存储机制的关键技术173.1面向云端文件传输与存储的文件分块机制173.1.1文件传输分块173.1.2文件存储分块183.1.3云享云端文件传输与存储分块的选择203.2基于增量的云端文件传输203.2.1全副本传输203.2.2基于增量的上传过程213.2.3基于增量的下载过程233.2.4基于滑动窗口的滚动校验253.3基于滑动块的云端文件存储263.3.1基于分块的相同数据删除技术分析263.3.2基于滑动块的存储机制273.3.3滚动校验的内存优化方法293.3.4优化方法空间复杂度分析303.4云享云端文件传输与存储机制313.5本章小结33第四章 云端文件传输与存储机制的设计实现354.1云享系统总体架构354.1.1云享系统架构图354.1.2应用层354.1.3服务层364.1.4存储层364.1.5服务层子模块组织364.2增量传输机制的实现384.2.1增量的数据模型384.2.2客户端模块的实现394.2.3服务器模块的实现444.3基于滑动块的存储机制的实现474.3.1存储去重的数据模型474.3.2存储去重技术的流程484.4本章小结49第五章 实验分析515.1实验环境515.2滚动校验算法实验515.3传输实验525.3.1单文件传输实验525.3.2文件并发传输实验535.4存储实验535.4.1单文件存储实验545.4.2文件并发存储实验545.5本章小结55第六章 结束语576.1论文贡献576.2进一步工作57参考文献59发表文章61致谢63中国科学院软件研究所硕士学位论文第一章 绪论第一章 绪论 本章介绍论文的研究背景、主要工作和论文组织方式。1.1 研究背景随着互联网技术的飞速发展，全球信息呈爆炸式的增长。研究表明，从2006年到2010年，全球信息总量将增长6倍以上。当今企业面临着海量信息管理困难，例如：数据存储成本高、可靠性低等难题。随着企业的年龄的增长，行业的发展，企业汇总的数据和文件正以指数级别的速度增长，这使数据管理更为复杂，系统运营成本不断上升。传统企业的存储主要靠Expand NAS（扩展网络存储技术），Tape（磁带）等方式保存企业数据。这些存储方式在存储的灵活性，存储的可扩展性以及存储资源的可视化管理等方面有很大的不足。云存储1（Cloud Storage）是云计算2范畴内的概念，具有敏捷、可扩展性、弹性和多租户的特性。云存储系统具备的强大存储能力、易用性和数据备份等特性，逐渐得到企业用户的青睐。越来越多的企业开始将存储作为单独的项目进行管理。同时，持续增长的数据存储压力带动着整个存储市场的快速发展。云存储服务提供商在数据中心提供可靠安全的海量文件存储服务。用户能够将文件保存在云端，并能够随时随地的访问云端中央服务的文件资源。云存储服务通常支持各种智能终端的访问请求，例如PC客户端，手机客户端，Web客户端等等。目前业内主流的云存储产品有DropBox，GoogleDrive，金山快盘，百度云盘等等，面向互联网用户和企业用户，都提供了文件存储、文件共享等服务。云端文件共享服务，已经被业界主流的各大云存储产品支持，并逐步成为云存储的核心服务之一。共享服务允许用户将个人存储在云端的文件资源共享给其他用户进行读写，为存储服务加入了用户交互的属性，不仅提高文件访问的灵活性，而且提升了存储资源的利用率。其特点有三：1.文件多版本；2.多用户多终端；3.高并发请求。（1）多版本，共享文件可能被其拥有者按时间顺序进行多次修改，并具有多个历史版本3。共享文件的修改内容需要通过云存储服务传输到其接收共享的用户客户端。（2）多用户多终端，一个共享文件可能被共享给多个用户，并且不同用户使用不同类型的客户端。（3）高并发请求，一次共享文件内容的修改，将引起所有参与该文件共享的用户接收新版本的共享文件，而云端海量共享文件的修改，将会引起云端服务器和各个在线客户端之间某一时刻同步数据的并发传输。云端文件共享服务经常面临相似的文件数据重复传输和存储的场景。共享文件同步和共享文件历史版本是最典型的两个场景，详见如下图表。表 1.1 相似文件数据重复传输与存储的场景及问题共享服务场景场景描述存在问题共享文件同步一个文件被共享给多个用户，并被其中一个用户的客户端修改形成新版本文件。服务器将向参与文件共享的各个客户端同步更新文件数据。当用户数量非常大的时候，服务器向每个客户端传输相同文件，传输性能将成为瓶颈。共享文件历史版本一个文件被共享给多个用户，每个用户都具有修改文件的权限，则经过多次修改后，共享文件具有多个历史版本文件。相似的历史版本全部存储到存储层中，必然导致每个版本相同数据被重复存储，占用大量空间。共享文件同步服务对文件的传输和存储性能有更高的要求。因为云端文件存储服务面对的工作环境相比普适的云存储环境更加的复杂，例如高延时低带宽的网络环境、共享环境中客户端对服务器的高并发访问等等。在高延时或者低带宽的网络环境下，文件在客户端和服务器之间传输会受到不稳定的网络环境的影响。可能会导致用户上传文件或者下载文件的等待时间过长，影响产品的用户体验。共享并发场景的复杂之处在于，一个文件可能被共享给多个用户的不同终端，文件数据的传输路径是由中央服务器与各个客户端连接而成的星形的拓扑结构。此时一次客户端文件的修改，会进一步带来所有参与共享的用户终端与云端服务器之间的文件数据同步操作。作为星形结构的中心，云端服务器非常容易成为传输性能的瓶颈，文件并发传输成本昂贵。因此，云端文件存储系统需要设计一套高效的文件传输与存储机制，来应对云端文件共享服务中面临的复杂传输环境和相同数据存储场景。在传输过程中，挖掘共享文件历史版本间的关联性，进行增量的数据传输，缩短文件在网络中传输的时间，降低文件数据对网络带宽的占用；在存储过程中，尽可能的定位出历史版本文件的相同数据块，提高物理存储的利用率。云享系统（CloudShare）是软件研究所自主研发的一套云端文件存储与共享系统。系统支持文件共享服务，支持一系列的文件共享策略，涵盖日常办公过程中各个场景。但云享系统还未对复杂的工作环境下的传输和存储做应对策略，传输和存储的效率都有进一步提升的空间。1.2 论文主要工作论文针对文件共享服务场景中的文件传输和存储性能的问题进行研究，对如何利用历史版本文件的相似性，提高文件传输和文件存储效率的问题进行深入的思考。提出一套云端文件高效传输与存储机制，解决云享系统在复杂共享场景中文件数据传输和存储效率的关键技术难点。最终实现一个高效传输和存储的云端文件共享服务。论文工作主要包括以下几个部分。1相关技术的调研分析论文对云端文件存储系统的相关技术进行调研，首先是云存储系统相关技术的概述。再进一步调研云端文件共享服务中最重要的传输与存储两方面内容的相关技术，将云端文件传输与存储场景与传统的传输与存储场景作对比，分析二者的技术需求的差异。然后指出云存储业内产品在文件传输与文件传输上遇到的挑战。最后调研云享系统面向服务的架构和目前的传输与存储机制的不足。2.文件传输与存储关键技术的研究云享系统将文件分块机制应用于传输与存储过程中。传输分块，是实现增量传输机制和断点续传功能的基础；存储分块是存储去重机制的基础，使云享系统的存储机制具备数据安全、并发操作等特性。采用相同大小的传输与存储分块能够简化流程，避免不必要的分割、合并分块的操作开销。增量传输机制采用Rsync45增量传输算法思想，并结合云存储系统基于分块的存储模型，对具有历史版本属性的文件进行增量传输，从而减少网络传输的时间，降低传输所需的网络带宽开销。论文还对增量传输的下载流程进行优化，优化后的传输机制使服务器计算压力大大降低。存储去重机制调研了业内多种成熟的相同数据删除技术，结合云存储系统服务器端高并发和文件块大小不确定的特点，采用基于滑动块的相同数据删除技术，定位出文件的相同数据实现存储去重。论文对滑动窗口滚动校验算法进行了内存使用的优化，使每次滑动窗口检测算法占用内存最小化，从而支持更大的存储线程并发量。3.传输与存储机制的设计与实现基于文件传输与存储关键技术的研究，论文结合云享云端文件存储与共享平台，设计实现了一套高效的云端文件传输与存储机制。该机制为云享系统传输层提供增量传输功能。为PC端，Mobile端，Web端等不同类型的客户端提供定制的传输与存储接口，支持增量传输和普通传输之间的机制切换，使文件传输更加高效。该机制为云享系统存储层提供基于滑动块的存储去重机制，并且支持全副本存储和存储去重机制的切换，尽可能减少服务器端的CPU计算和I/O的开销，提高存储层的利用率。4.实验验证将增量传输机制与存储去重机制集成到云享系统后，本文针对增量传输机制和存储去重机制进行了实验。对机制的核心算法滚动校验算法进行实验，验证滑动缓冲区的性能。对增量传输过程进行实验，验证增量传输机制在并发场景下的有效性和高效性。对存储去重过程进行实现，验证基于滑动块的存储机制的去重效果和并发性能。1.3 论文内容组织论文的后续章节按以下方式组织：第二章围绕云端文件传输与存储的相关技术展开，首先介绍了云存储服务系统的特点以及云端文件共享服务场景特点。然后介绍文件传输和存储的相关技术。文件传输的相关技术包括传统文件传输的工具和算法以及云端文件存储场景中系统面临的传输问题。文件存储的相关技术主要介绍业内流行四种相同数据删除技术。最后介绍，云享系统的架构和文件共享策略以及传输与存储中存在的不足。论文研究的传输与存储机制将基于云享系统展开。第三章介绍设计传输与存储机制的关键技术。首先介绍云享系统的传输与存储的文件分块机制。然后，论文研究了当前系统的传输和存储机制的不足，对基于增量的传输机制和基于滑动块的存储机制的关键技术进行了介绍。最后给出了结合云享系统的传输与存储机制的整体方案。第四章介绍云享系统传输与存储机制设计与实现。首先介绍了云享系统的总体架构，并对核心服务层模块作介绍。然后分别介绍了增量传输机制和基于滑动块的存储机制的实现。第五章介绍系统实验。实验共有三组：（1）滚动校验算法实验；（2）传输实验；（3）存储实验。通过实验，证明增量传输机制能够有效提升云享系统的文件传输效率，存储去重机制能够显著的提升存储的利用率。第六章对全文工作进行了总结，对未来工作进行了展望。67中国科学院软件研究所硕士学位论文第二章 云端文件传输与存储的相关技术第二章 云端文件传输与存储的相关技术本章首先对云端文件存储系统和共享服务做基本介绍。再介绍文件传输和文件存储的相关技术，包括增量传输算法Rsync和相同数据删除技术。在传输与存储两个方面，指出传统技术应对云端文件共享场景时的不足，引出云端文件系统遇到的挑战。最后介绍云享系统面向服务的架构、共享服务策略以及当前采用的传输与存储技术，为后续章节做知识铺垫。2.1 云端文件存储系统2.1.1 云存储服务概述云存储是一种联网的企业级的存储模型。云存储的文件数据通常保存在虚拟化的存储池之中，而存储池通常由第三方的云存储服务商维护管理。云存储服务商运营巨大的数据中心，需要存储空间的用户通过购买或者租借的方式获得存储资源。数据中心根据用户的需求将存储资源虚拟化并将其暴露成一个存储池。这样，云存储客户本身就可以用其进行文件或者数据对象的存取。值得一提的是，这些被虚拟化6的存储池在物理上可能跨越了多个服务器多个机房甚至多个城市。存储文件的安全性由云存储厂商和他们所提供的云存储应用来保证。云存储基于高度虚拟化的基础设施，并且具有和云计算相同的特性，例如敏捷性，可扩展性，多租户等，而且同样可以架设在公有云（Amazon S37）或者私有云（ViON Capacity Services）上。云存储通常物理上分布式，但是对外逻辑上表现为一个整体，或者被称为联邦存储云 89。对大规模的分布式的数据具有高容错性。对文件历史版本的创建具有高容忍度。对文件副本采用最终一致性。随着云存储技术的飞速发展，越来越多的云存储系统涌现出来。根据面向用户类型的不同，云存储可以被划分为企业云存储和个人云存储。根据用户连接云存储的方式的不同，云存储系统可以被划分为公有云存储，私有云存储10。2.1.2 文件共享服务的相关工作文件共享服务是一种借助工具或者系统的方式允许多人协同操作同一份文档或者文件，并使其达到最终的一致性的服务。通常，这类能帮助实现文件共享服务的软件允许多个用户或者用户团队通过不同的智能终端设备工作于单个文档而不受工作场合的限制。因此，当今的文件共享服务是一个允许用户随时随地接入网络来进行协同办公的服务。 传统文件共享功能传统文件共享11功能主要通过即时聊天工具文件发送，邮件服务，FTP传输等方式进行。这些文件共享方式都存在一定的不足之处，例如，它们都不是以文件为中心的共享方式，它们对文件的历史版本的缺乏较好的管理模式。即时聊天工具共享方式的优点在于及时的沟通，但是缺点也非常明显，文件与评论记录分开管理。将历时评论记录和共享文件关联困难。邮件服务能够一定程度上将共享文件和评论信息关联。但是邮件服务以邮件为中心，文件以附件的形式发送，共享的生命周期以邮件的生命周期为准，而非文件。FTP传输服务能够一定程度上做到文件为中心，但是它并不具备直接的评论和标签等功能以及历史版本的管理功能。 文件为核心的共享服务文件为中心12的共享服务，指的在在线协同工作中将文件和文件内容作为流程的核心进行信息共享协同的共享服务。相比之下，早期的商务共享工具因为将文件和对文件的评论等相关信息分开管理而一直被诟病。为了解决这个问题，业内具有创新精神的公司开始推广云端文件共享服务工具。云端文件共享服务将共享文件置于整个协同流程的核心。这意味着共享服务允许用户将文件相关信息，例如段落评论，文件标签等与文件产生粘性。 云端文件共享服务云端文件共享1314是种全新的文档共享和协作的共享服务模式。依托于云存储服务，共享文件都被上传到了云端存储服务器，经由云端服务器被其他用户访问。所有的共享操作坚持以共享文件为核心，允许用户对云端文件或者文件夹进行上传/下载，评论，标注等。在过去的数年里，各个行业的公司开始逐渐选择从传统的共享服务模式转变成云端文件共享模式，进行公司内的文件管理和共享工作。文件共享服务是一种借助工具或者系统的方式将多人协同操作同一份文档或者文件，并使其达到最终的一致性的服务。传统的文件共享方式将文件和评论、标签等信息分离，不利于共享和协作。云端文件共享服务以文件为中心，提供了一套覆盖日常工作场景的共享策略，提供文件共享和协同办公的效率，正受到越来越多企业的青睐。2.2 文件传输相关技术云端文件共享的场景涉及多客户端进行云端文件传输的问题。在云端文件共享的场景中，一个共享文件被共享给了多个企业用户。那么，这些企业用户可以通过PC，Web，Mobile等客户端查看下载查看共享文件。如果这些企业用户还具有修改共享文件的权限，则他们可以对共享文件做修改。修改后的共享文件会从执行修改的客户端上传至云端服务器，再由云端服务器传输至其他的客户端，使各个客户端的共享文件内容最终达到一致。2.2.1 传统的文件传输远程文件同步问题15是计算机领域的经典研究问题，文件同步过程指的是通过一些特定的规则，将两个或者两个以上的位置的文件进行更新的过程。文件同步按传输方向有单向同步和双向同步两种。单向同步，也称镜像同步，被更新的文件从源地址拷贝到一个或者多个目标地址，但是没有目标地址的文件会拷贝回源地址。双向同步，被更新的文件会在两个或者多个地址间互相拷贝，旨在保证两个地址之间的数据内容保持相同。单向同步的物理拓扑结构相对简单，多为线型，一个发起同步的源地址和一个接受同步的目标地址，文件单向传输。双向同步，物理拓扑结构相对复杂。多个物理地址之间同步，拓扑结构更加多样，简单的有双工的线型结构，典型的复杂结构比如环形结构，星形结构等等。针对不同的文件同步需求，业内有不少出色的文件同步工具提供了相应的同步算法。例如分布式文件系统的数据同步，版本控制软件的文件同步以及端对端文件同步软件等等，下文将介绍三类流行的文件同步系统或者工具以及其适用的同步场景。分布式文件系统16，顾名思义，在物理位置上分布式的文件系统，文件系统的存储介质可能位于不同的位置，文件系统在系统层面维护数据一致性17，但是对外表现和普通文件系统并无差异。客户端访问不会意识到文件系统分布式的存在。 主流的版本控制软件（Version Control Software），也称源控制（Source Control），旨在管理文档，项目代码，大型网站等信息集合。新旧版本的改变量通常是一些行代码的变更或者少量文本的变化。目前，功能最强大的版本管理软件正是那些被用在软件开发领域的版本管理软件，支持一个团队的成员修改同一个工程里的文件。这类软件中的佼佼者有SVN和CVS，而Git 和Bazaar 则是最近几年兴起的分布式版本控制系统。版本控制软件通常由客户端和服务器两部分组成。客户端修改内容会和服务器端的旧版本内容合并生成新版本。版本分为主干版本（Trunk）和分支版本（branch），主干和分支构成了一个逻辑上有向树的拓扑结构。在主干的上可以建立一个分支，在分支上可以合并到某个主干上。每个版本都基于上一个版本的内容，每个版本都有一个唯一的时间戳作为版本区分。当前版本与之前版本的不同之处需要通过合并操作（Merge）生成新的版本。每次从客户端上传新版本到服务器都是增量的传输。版本管理软件通常执行按行比对的增量传输算法。客户端只把两个版本间不同的文本行上传至服务器。服务器也只将当前版本的记录成一个完整的版本，之前的历史版本都只保存和目前版本的对比所得的增量18，如图2.1所示，每个数字表示一个文件版本，箭头起始方向表示历史版本的依赖关系。通过这种增量的方式进行按行比对的文件同步传输19。0 - 8 - 9 4 - 8 2 - 4 6 - 81 - 2 3 - 4 5 - 6 7 - 8图 2.1 SVN版本管理软件历史版本依赖关系业内流行的端对端的文件同步软件有两款，分别为风靡Linux平台下的Rsync20同步软件和支持跨平台同步软件Unison21。Rsync是Linux平台下的著名单向同步软件，采用传统Rsync算法，快速的将远程文件进行同步。支持端对端的单向文件或文件夹同步。命令行格式，命令简单，基于TCP/IP协议传输，支持SSH加密传输，支持压缩传输。对于文件夹，Rsync软件有压缩和递归两种方式进行传输。Rsync是很好的单向同步软件，在网络带宽有限的情况下依旧能够表现良好，因此被广泛的应用于单向数据传输或者备份场景。另一个流行的端对端软件被是Unison。Unison是一款运行于Unix和Windows上的文件同步工具，它允许两台主机上的两个文件和文件夹集合进行双向同步。它与其他同步软件的不同之处在于它兼具各家的优点，例如Unison能够跨平台的进行文件同步；Unison能够像版本控制软件那样，检测副本更新的冲突并提示；支持类似Rsync的增量传输；Unison对文件副本更新谨慎，在突然网络异常或者宕机的情况下，能够保证文件数据的正确性；Unison开源免费等等。综上所述，版本控制软件，Rsync或者Unison等等文件同步工具能够在小规模的文件同步场景下，工作良好，稳定同步。但是在云存储的场景下，尤其在典型的大规模共享同步的场景下，传统的文件同步软件有着些许不足，详见2.2节内容。2.2.2 增量传输算法Rsync在文件同步和传输领域，国内外的学者提出了很多远程数据传输的算法。这些算法，根据同步两端交换数据的轮数，可以划分为单轮同步算法和多轮同步算法。其中的单轮和多轮指的是为了比较同步两端文件数据信息而进行的数据交换的次数。最经典最重要的远程数据同步算法是Tridgell 和 MacKerras等人在1996年发表的Rsync同步算法，它是一个单轮的数据同步算法。Rsync的算法思想是最近20年文件传输和文件同步领域的重要思想之一。在其之后绝大多数的单轮和多轮远程数据同步算法2223都直接或者间接的借鉴了其算法思想。论文基于增量的传输机制和基于滑动块的存储机制都借鉴了Rsync的算法思想，并针对其进行优化，使其在云端文件环境中达到很好的效果。Rsync增量传输算法想要解决两台远程终端上两个相似文件A,B的在有限网络带宽情况下的同步传输问题。该同步问题有两个难点，1. A，B两个文件位于两台不同的终端。2. 两台终端之间的网络带宽非常有限。Rsync增量传输算法，将接收方的文件块的信息传输到发送方，发送方借助收到的文件块信息，将本地文件和远程文件作对比，定位本地文件的改变量，进而进行本地文件的增量传输。假设我们有两台终端PC_sender和PC_receiver，PC_sender上有文件file_s，PC_receiver上有文件file_r，并且file_s和file_r是相似的。“相似”指的是其中一个文件内容是另一个文件内容进行少量数据增删改操作形成的文件。现要将file_r同步成和file_s相同的文件。具体的，Rsync算法由以下五个步骤组成：步骤1.将PC_receiver上的file_r切分成一系列大小为Size且互相不重叠的文件块，最后一块文件块的大小可能略小于Size。步骤2.对每个切分后的文件块分别计算两个校验码：滚动弱校验码（RollingHash）和消息摘要强校验码（MD5）。步骤3. PC_receiver将所有分块的强弱校验码都发送到PC_sender上。步骤4. PC_sender在文件file_s上搜索所有的长度为Size的块，找出所有具有和file_r中分块相同强弱校验码的分块。由于滚动校验码增量滚动的特性，这个过程可以通过很快的一次遍历file_s来达到。步骤5. PC_sender根据步骤4遍历生成一个分块序列，分块序列由两个文件公有的分块和file_s特有的分块组成。PC_sender将分块序列发送给PC_receiver。发送遇到公有分块，则发送强弱校验码，遇到特有分块则发送整个文件块数据。步骤6.最终PC_receiver获得一份文件file_s的分块序列。文件序列在PC_receiver端与file_r重新组织，合并生成file_s。Rsync算法中的弱校验码RollingHash计算方法的灵感来源于Mark Adlers adler-32校验码：当计算出字节流 Xl Xn 的弱校验码后，只要拥有第Xn+1个字符，字节流 X2 Xn+1 的计算代价非常小，几乎是时间复杂度O(1)的时间。我们定义 s( l , k ) 是文件字节流 Xl Xk 的弱检验码，则其计算公式为sk , l=ak , l+M*b(k , l)其中，ak , l=i=klXimod M bk , l=i=kl(l-i+1)Ximod MM = 216，因此计算s( l+1 , k+1) 的校验码公式如下：ak+1, l+1=a k , l -Xk+Xl+1 mod Mbk+1, l+1=bk , l-l-k+1Xk+ak+1, l+1 mod M不难看出，s(l+1 , k+1) 的结果可以用Xk 和Xl+1的一次项以及s(l , k)的结果计算获得，一次校验码的计算过程只有少量的加法和乘法，时间开销非常小。那么，我们可以对文件流开启 l , k 大小的窗口，一次遍历整个文件流，滑动计算所有可能重复的公共文件块。虽然弱校验码的计算速度非常快，但其计算结果有一定的碰撞率。碰撞率指的是，根据弱校验码的公式两个不同的文件块有一定概率计算出相同的弱校验码。因此，仍然需要一种碰撞率更低的强校验算法来确认弱校验相同的情况下，文件块是否是公共文件块。用计算成本较低但是碰撞率高的弱校验码判断可能的公共块，再用计算成本较高但是碰撞率较低的强校验确认是否是公共块。2.2.3 云端文件的传输问题分析云端文件存储与共享同步场景，允许用户在任意连接云端的终端上创建或者下载云端文件，以便用户进行文件的共享和协作等等。我们定义一次云端文件传输周期为：服务器和客户端之间单向完成一次传输，并在目标机器上形成完整文件副本。例如，一次个人文件上传和下载的同步可以被认为是一次完整的云端文件传输。文件共享服务中的文件传输比个人文件传输场景更加复杂。一个文件可能被共享给多个用户的不同终端，文件数据的传输路径是由中央服务器与各个客户端连接而成的星形的拓扑结构。此时一次客户端文件的修改，会带来1+N次的云端文件传输。其中的1是，客户端上传新版本到服务；N次传输是服务器将新版本文件更新至所有参与共享的客户端的文件传输。我们假定发生这1+N次传输之前，所有客户端文件副本满足一致性，则N次传输的将是N次内容相同的文件数据传输。而作为星形结构的中心，云端服务器需要与N个客户端建立传输连接。当N非常大即大规模共享同步发生时，服务器非常容易成为传输性能瓶颈，文件并发传输成本昂贵。由此可见，数据在客户端与服务器之间的如何高效的传输是云端文件服务的核心问题之一。2.2节提到的Rsync，Unison软件在云端文件传输与存储的场景下，没能很好的解决服务器性能瓶颈的问题。版本控制软件SVN，在非文本文件传输的过程中，并不能提供足够小的时间复杂度，更不用说大规模并发的场景。增量传输算法Rsync也并不能完全适用于云端文件存储与传输的场景。因此，论文提出一种改良的增量传输算法，通过优化服务器端内存使用以及分摊计算压力给各个客户端的方式，尽可能减少服务器端的CPU计算和I/O的开销，使双工的传输效率和云端服务器资源的利用率都更加得高效。2.3 文件存储的相关技术研究发现，一般的应用系统存储的数据约有60%是冗余数据24，即重复存储的数据，并且冗余数据随着系统寿命的增长会越来越多。如何应用相同数据删除技术25消除存储系统中相同的物理文件或者文件块，是文件存储的热门研究问题之一。云端文件共享服务中，经常会面临共享文件历史版本存储的问题。一个文件经过多次修改后，形成文件的历史版本。历史版本如何存储，对系统的存储利用率有直接影响。运用相同数据删除技术可以有效解决文件共享服务中历史版本存储的问题。相同数据删除技术能够定位出相同的数据，达到存储去冗余的效果。2.3.1 相同数据删除技术相同数据主要包括相同的文件和相同文件块两个粒度，目前业内主流的相同数据删除技术有四种：(1)完全文件检测技术(whole file detection)；(2)基于FSP(fixed-size partition)算法的块检测技术；(3)基于CDC算法的检测技术；(4)基于滑动块的检测技术。(1)完全文件检测技术(whole file detection)。属于文件粒度的相同数据删除。通过对整个文件数据计算Hash值的方式查找相同文件。这种技术通常会预先保存一个历史文件Hash值的集合。在检测新文件是否需要存储时，该技术计算文件Hash值并进入历史Hash集合中查询。若查到相同Hash值，则认为检测到相同文件数据。目前，MD526值和SHA127是完全文件检测技术中应用最广泛且使用效果最好的Hash算法。(2)基于FSP(fixed-size partition)算法的块检测技术。该技术又称为基于固定分块的相同数据删除技术。作为(1)完全文件检测技术的延伸和补充，FSP算法提供了更细粒度的文件块级别相同数据的检测技术。同样，该技术会预存历史文件数据块的Hash集合。该技术将文件按固定大小分块，每块计算Hash值，将块的Hash值在预存集合中进行查询。如果查到相同记录，则说明文件块为相同数据，否则即是需要存储的文件块。(3)基于CDC算法的检测技术28。CDC算法从文件头开始，对固定大小的滑动窗口中的数据计算Rabin指纹。当Rabin指纹值满足用它对某个指定的整数取模为0时，就把此时的窗口末尾作为分块的边界。通过这个方式迭代将文件分割为长度大小不一的分块。对每个分块求Hash值，与预存的Hash做比对，相同则认为是相同数据块，不相同则对新文件块进行存储处理。(4)滑动块检测技术指的是，通过用固定大小的窗口。在文件流上设置固定大小的滑动窗口，滑动遍历文件，分别计算强弱校验码的方式进行数据检测。如果文件块的弱校验码与预存的弱校验相同，则进一步计算强校验码，若强校验码再相同，则认为该文件块是相同数据块，滑动窗口越过当前块继续滑动扫描。滑动块检测技术的特点是块大小固定，弱校验计算快速，有效节约计算时间。对不同数据敏感，能够检测出所有的不同数据。缺点是如果文件微少修改，会产生细粒度的文件碎片。2.3.2 云端文件的存储问题分析云端文件存储接收用户的海量上传文件，必然面临文件数据存储冗余问题。多个相互独立的用户可能上传相同或者相似的文件数据。例如，文件共享服务中，多个用户修改产生历史版本的场景就是典型的文件数据冗余存储的问题。文件存储冗余问题不解决，随着系统使用寿命的延长，底层存储中会出现越来越多的冗余数据，造成存储资源的浪费。虽然可以从硬件扩容的角度，缓解这个问题，但并不能从根本上解决这个问题。通过对上述四种相同数据删除技术的组合应用，可以有效的解决文件数据存储冗余。2.4 云享云端文件存储与共享平台云享云端文件存储与共享平台（Cl