（计算机系统结构专业论文）寄生存储系统设计与性能分析.pdf

ii 华 中 科 技 大 学 硕 士 学 位 论 文 摘 要* 近年来因特网在全球范围内飞速发展，其上遍布着大量的通讯和计算资源，从 而产生一个科学问题： 可否利用因特网复杂环境下的闲散资源 (含计算资源与通讯资 源， 特别是通讯资源) 进行动态数据存储？因特网在数据包收发过程中具有短暂的数 据存储能力。由于网络上数据包的传输时间非零，这样便导致数据包在传输的过程 中能够保持一定的在线时间，从而形成事实上的数据存储。这种数据存储行为可自 然地用于构建一种极其独特的网络存储新模式 寄生存储。 按照这种思想，可基于因特网现有的标准协议，如 icmp、smtp 等构建一种全 新的网络存储模型。该模型利用网络标准协议的通讯机制，在网络通讯过程中充分 挖掘网络通讯资源潜在的数据存储能力。通过分析协议自身特点，探索适用于寄生 存储的网络协议及各协议所适用的存储环境。 基于 icmp 协议构建寄生存储模型，给出模型的详细设计，并深入分析该模型 下的存储容量、i/o 速度、生命周期等相关性能。理论分析表明，寄生存储的存储容 量主要受通讯链路延时以及宿主数量的影响； i/o 速度主要受网络带宽的影响；文 件的生命周期依赖于文件的冗余数量和网络丢包率。测试结果表明：这种存储方法 适用于在广域网上进行免费、大容量及短期的数据存储；远程寄生宿主并无意识到 用户的数据存储行为；不同于计算机病毒,该存储行为对寄生宿主无害；对网络性能 的影响可以忽略不计。 关键词：网络存储，寄生存储，互联网应用，网络协议，计算机通讯 本文的研究工作受到国家“973”计划项目(2004cb318201), 以及国家自然科学基金 (60773189) 的资助 iii 华 中 科 技 大 学 硕 士 学 位 论 文 abstract* with the rapid development of internet, mass of communication and computing resources spread all over it. this brings a question: can the idle resources over the network be used to implement dynamic data storage? the internet has a momentary storage capacity in the process of sending data packages to remote systems and receiving the echoed ones. as the time of the data package traveling on network is nonzero, this causes the traveling data to be sustained online in a certain period of time and achieves an actual data storage, which can be taken as an extremely unusual network storage mode, parasitic storage, naturally. inspired by this thought, an extremely unusual storage model based on existing internet protocols, such as icmp, smtp and etc, can be achieved. it uses the communicating mechanism of standard protocol to exploit the storage potential of network communications. by analyzing the protocol s own characteristics, the protocols and environments suitable for parasitic storage are explored in detail. an icmp- based parasitic storage model is established. the detailed design of model is given out and typical performances, such as storage capacity, i/o speed, and life- cycle are analyzed. the analysis results show that: the capacity is influenced by communication channel delay and the number of hosts; i/o speed is affected by bandwidth of the initiator; and the life- cycle is determined by the number of redundant and packets loss rate of network. furthermore, the entire internet storage capacity is estimated. the results of experiments indicates that the storage method is applicable for free of cost, large space and short term data storage over wide area network without being sensed by remote hosts (i.e.parasitifers), and also it does no harm to the hosts and the influence on network can be ignored. keywords: network storage, parasitic storage, internet applications, network protocols, computer communications supported by the national grand fundamental research 973 program of china (grant no. 2004cb318201), and the national natural science foundation of china（grant no. 60773189） 华 中 科 技 大 学 硕 士 学 位 论 文 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本 论 文 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论 图灵奖获得者 jim gray提出了一个新的经验定律1：网络环境下每 18 个月新产 生的数据量等于有史以来数据量之和。信息资源的爆炸性增长，对存储系统在存储 容量、数据可用性以及 i/o 性能等方面提出了越来越高的要求。 1.1 课题背景 本课题来源于国家“973”计划课题网络存储动态规划及基于存储对象的分布 体系结构(2004cb318201),旨在探索一种网络存储的新模式。 为了适应信息存储的需求，存储系统得到了长足的发展，从传统的直接存储系 统 (direct access storage, das)、存储局域网 (storage area network, san) 和附网存 储 (network attached storage, nas)， 发 展 到 新 一 代 的 基 于 对 象 存 储 技 术 (object- based storage, obs)以及 p2p 存储技术(peer- to- peer storage)。 1.1.1 直接连接存储 直接连接存储 (das) 是一种典型的服务器存储系统。在服务器/客户端模式下， das 将具有块接口的数据存储设备 (如硬盘、磁盘阵列等) 通过外设通道 (如 scsi 等) 直接连接到总线，挂接在文件服务器上，由服务器集中调度和管理。服务器通过 i/o 通道服务来直接访问 das 中的数据。当用户通过网络访问文件服务器上的数据 资源时，被访问的数据必须在存储设备和文件服务器之间进行多次的存储转发，在 发送给用户。das 存储管理相对比较简单，从而使得 das 设备的价格比较低廉。 在 das 方式中，存储系统附属于服务器。由于受服务器总线技术的限制，das 方式系统的可扩展性差。当客户连接数增多时，服务器将成为整个系统的性能瓶颈。 卡耐基- 梅隆大学 (carnegie mellon university, cmu)的研究表明，这种瓶颈会导致系 统的资源利用率降到 3%2。das 方式主要有以下缺点。 （1） 受限于服务器 i/o 总线。虽然计算机技术的发展使主机总线带宽大为增加， 但是仍赶不上现代存储应用对带宽的要求； 2 华 中 科 技 大 学 硕 士 学 位 论 文 （2）服务器的内存容量限制。由于主机的内存容量有限，当有连续的大量数据 访问请求时，主机的内存容量将很快达到饱和，而影响了处理剩下的数据传输请求； （3）可扩展性有限。如对于 16 位的 scsi 总线，最多只能接 16 个设备。 1.1.2 存储局域网 以服务器为中心的das 访问模式越来越难以满足现代存储应用大容量、 高可靠、 高可用、高性能、动态可扩展、易维护和开放性等众多方面的需求。解决这一问题 的关键是将访问模式从以服务器为中心转化为以数据和网络为中心，实现扩展容量、 增加性能和延伸距离，尤其是实现多个主机数据的共享，这推动了存储与计算的分 离，即网络存储的发展。 为了解决 das 的可扩展性，引入了 san 技术。存储局域网3- 6 (san)源于 scsi 技术，它通过专用高速网将一个或多个网络存储设备 (如：磁盘阵列 raid) 和服务 器连接起来，具有良好的可扩展性，客户端和存储设备可直接加入到网络中。san 以网络数据存储为中心，采用可伸缩的网络拓扑结构，通过具有高速传输速率的光 线通道的直接连接方式，提供 san 内部任意节点之间的多路可选择的数据交换，并 且将数据存储管理集中在相应独立的存储区域网内，实现最大限度的数据共享和数 据优化管理，以及系统的无缝扩充。客户机可以直接访问存储设备，避开了传统文 件服务器的存储转发所带来的延迟，使之具有高吞吐量。 不过，san 主要用于存储量大的工作环境， san 的适用性和通用性较差，在 系统的安装和升级方面效率不高，由于 san 使用专用网络 (一般为光纤网络)，相应 的设备价格昂贵，总体实现费用较高，局限于大中型应用。且随着存储设备和客户 机数目的剧增，元数据服务器工作负载过重，将成为系统瓶颈。 1.1.3 附网存储 附网存储7,8 (nas) ，采用文件接口，通过网络接口直接把存储设备接入网络， 拥有唯一的 ip 地址，提供预先已配置的存储空间、集成的文件服务系统和存储管理 软件，以优化的文件系统，如网络文件系统 (network file system, nfs)、公共因特 网文件系统 (common internet file system, cifs) 等提供网络文件访问。 nas 以数据 3 华 中 科 技 大 学 硕 士 学 位 论 文 为中心，将存储设备与服务器分离，服务器将不适用的大部分计算功能去掉，仅保 留用于存储服务的功能，有着很高的 i/o 性能。 然而，nas 系统也有其潜在的局限性。nas 从根本上没有改变客户端/服务器模 式， i/o 路径在本质上仍然采用传统服务器- 存储设备的 i/o 方式， 当服务请求剧增时， 服务器将成为瓶颈。其次是缺乏灵活性。它是一种专用存储设备，不能通过公用的、 流行的软硬件升级或改变产品的功能。此外，nas 备份与恢复的实现相当困难，一 般只能采取一些补救措施。 1.1.4 对象存储 随着存储技术和理论研究的发展，存储设备逐渐智能化，能够自主管理，并了 解自身所服务的存储应用，这样就需要具有自我表述能力的接口，由此出现了基于 对象存储9,10,11。obs 采用对象接口，与固定大小的块不一样，它为可变长的，可包 含多种数据类型，如文件、数据库记录、图像以及多媒体视频音频等，可以动态的 扩大和缩小。对象除了数据外还具有属性，它反映了对象的行为和特性，如建立时 间、访问时间、读/写速度等。对象由对象 id 号标识，保存在基于对象存储设备 (object- based storage device, osd)中，通过利用对象属性，对数据进行组织和优化， 对资源进行合理分配，使 osd 成为智能型存储设备。obs 的最直接效果是将数据的 空间管理从存储应用中剥离, 存储设备具有自管理特性， 能够根据数据属性组织数据 存储来提高系统性能。 目前，面向对象的存储仍然处在标准制定之中，还没有得到广泛的接受。要实 现对象存储，需要操作系统支持对象，需要存储设备具有自配置、自保护、自优化、 自恢复和自管理等特性。 1.1.5 p2p存储 p2p 计算 (peer- to- peer computing) 是一种基于 internet 的计算模式， 其目标就是 充分利用 internet环境中各种可能的终端计算设备进行大规模协作计算和资源共享。 当前，p2p 计算模式已经涉及到诸多应用领域，如分布式计算、分布式存储共享、即 时通讯等。2002 年，oceanstore12- 14第一次提出了 p2p 存储系统的构想，并对其中 4 华 中 科 技 大 学 硕 士 学 位 论 文 的一些主要问题提出了解决方案。p2p 存储的目标是基于很多小型的、不可靠的、可 用性低的分布式节点，建立大型、可靠可用的存储网络。p2p 存储具有可扩展性好、 系统容量大、成本低等有点，然而 p2p 存储也有其缺陷。 （1）服务器节点可能成为瓶颈。定位集中式和混合式 p2p 系统中，需要服务器 集中管理各节点状况，当节点数目剧增，频繁退出、进入系统时，有可能导致服务 器成为系统瓶颈，影响系统性能； （2）用户的隐私问题。用户使用 p2p 方式进行存储或是搜索数据时，很容易被 服务器探测到数据内容，用户隐私的保密程度不够； （3）程序加载强制性。每个加入系统的节点都需要加载 p2p 程序，而这对于大 部分用户来说并不是乐意接受的。 1.1.6 寄生存储 以上各种存储系统各有优点，但都有其使用的局限性，网络的飞速发展难免引 起数据存储量的急剧增加及存储设备的投入，这样便需要新的存储方式以缓解日益 增加的存储压力。 寄生存储 (parasitic storage) 利用网络通用协议，将数据封装成数据包寄生在网 络链路或是网络节点 (parasitic host, 宿主) 中，其网络拓扑结构类似于 p2p 存储系 统，无需每个结点加载额外程序，网络节点具有不可知性，其具有以下优势。 （1）可扩展性。随着下一代互联网的产生和发展，ip 地址空间的扩充，系统所 使用的存储节点只是网络中全部节点的一个子集，系统本身并不对节点个数进行限 制，系统可容纳的节点数已不在成为系统瓶颈，理论上其扩展性可认为是无限的。 （2）隐私性。随着互联网的普及，收集隐私信息正在变得越来越容易。隐私的 保护作为网络安全的重要方面越来越被人们所关注。寄生存储中，由于信息被划分 成足够小的数据块，即使被恶意截获也难以推断出完整文件的信息，大大提高了信 息的隐私性。这对于敏感数据的存储是非常重要的。 （3）低影响性。寄生存储绝非病毒或木马，它只是充分挖掘网络潜在资源并合 理利用以达到数据存储的目的。宿主的不可知性并不意味着寄生存储在宿主不可知 的情况下对其造成损害而是为了寄生存储使用的便携性及广泛性。 5 华 中 科 技 大 学 硕 士 学 位 论 文 寄生存储的这些特点充分表明其具有重要的研究价值和较为广阔的应用前景。 1.2 国内外发展概况 寄生存储的提出源于寄生计算。2001 年， albert l szl barab si 等人于 2001 年在nature上提出了寄生计算 (parasitic computing) 15的概念，描述的是一种利 用现有通用网络协议自带的计算能力进行一些 np 复杂问题求解的方法。在此基础 上，圣玛丽亚大学 (saint mary s university) 的计算机学者通过因特网基础设施，研 制出了一种虚拟计算机。他们将每个要处理的问题分成若干个微小的部分，由分布 在北美、欧洲和亚洲的服务器进行计算求值，然后利用每个服务器的结果获得解决 办法。这就类似于分布式计算利用多台因特网上的计算机进行大量的复杂计算，所 不同的是分布式计算要求各节点都加载特定程序且将节点主要资源用于计算，而寄 生计算无需节点感知，它通过巧妙地设计网络数据包，利用网络通用协议中自带的 计算能力达到计算目的。网络中参与计算的节点只是根据协议规范对数据包进行处 理，因此对网络节点性能的影响甚微。 2002 年在拉斯维加斯举行的全球最大黑客大会 defcon 会议上， saqib a khan 提出将大规模网络作为存储介质构造瞬间存储系统的设想。 2003 年，受寄生计算思 想的启发， michal zalewski和wojciech purczynski在一篇题为 “juggling with packets: parasitic data storage”16的文章中提出了寄生存储的概念并对其性能做了初步分 析。文章介绍了当前网络协议的潜在存储能力并将协议按照寄生存储适用环境做了 分类。2004 年在“ the international conference on internet computing” 国际会议上， joseph gill 等人提出了实用的寄生存储的模型， 并且给出了实现寄生存储模型的具体 方案17。2007 年，kurt rosenfeld 等人提出了基于寄生存储的系统框架, 分析了系统 的存储容量并给出了寄生存储的防范措施18。 然而，由于寄生存储环境的复杂性和寄生存储系统实现的困难性，关于寄生存 储的研究至今仍然没有明显的突破。由于寄生存储独特的优势，例如无需额外的硬 件扩展就可实现海量存储，网络节点的非感知性，数据保密性强以及对网络和宿主 的影响可忽略不计等等，其在网络存储、敏感信息存储等领域有广泛的应用前景和 6 华 中 科 技 大 学 硕 士 学 位 论 文 较高的研究价值。 1.3 课题研究目的与意义 课题研究目的是分析寄生存储系统实现难点并给出实现方案，提高寄生存储系 统的可靠性，对寄生存储系统性能给出具体描述。寄生存储系统通过挖掘现有网络 通讯中潜在的存储能力实现大容量、高性能的网络存储，其优势在于无需额外添加 存储设备，无需存储节点授权，且对存储节点及网络环境的影响较小。随着下一代 互联网的普及，网络节点的扩张，网络协议自身的发展，寄生存储的性能也将大大 提高。本课题的研究意义在于提出一种全新的存储模式，寄生存储的实现能够缓解 日益增长的存储压力，可应用在网络海量数据存储、军方敏感数据存储、用户隐私 数据存储等诸多方面。 1.4 本文组织结构 本文的组织结构如下： 第一章介绍了课题背景，国内外研究概况，课题研究的主要内容。 第二章介绍了寄生存储的基本原理、工作机制。并从三个平衡的角度对寄生存 储模型实现的难点做了深入分析：数据生命周期和读速度的平衡；数据可靠性和保 密性之间的平衡；存储容量和对网络影响之间的平衡。 第三章从准备数据、选择宿主、存储数据三方面详细描述了寄生存储系统的工 作流程；从地址空间、文件组织、容错机制以及并行传输机制等方面阐述了寄生存 储系统设计；针对用户的三种典型文件操作：加入文件、读取文件、移除和删除文 件，给出了相应算法。 第四章分析了寄生存储文件组织。重点讨论了冗余设置方案以提高数据可靠性， 提出了一种寄生存储系统适用的数据冗余副本管理机制：基于出错率的自适应动态 副本管理机制 efsrm。详细讨论了数据分发、错误检测、数据维护以及数据包发送 速率控制等相关问题。 第五章主要分析了寄生存储系统的性能。首先从理论上推导了寄生存储的存储 7 华 中 科 技 大 学 硕 士 学 位 论 文 容量、i/o 速度以及文件存储时间等性能的分析模型。通过对实际网络进行测试，结 合性能分析模型给出了寄生存储系统在实际网络环境中的性能指标，最后估算了整 个因特网的理论存储容量。 第六章概括了本文的研究成果和创新点，说明了研究尚存在的问题和未来研究 方向。 8 华 中 科 技 大 学 硕 士 学 位 论 文 2 寄生存储的基本原理 本章主要介绍寄生存储的基本原理，工作机制，并从三种平衡的角度分析了寄 生存储的实现难点及相应方案。 2.1 寄生存储的提出 寄生存储的提出源于寄生计算。寄生计算最早由 albert l szl barab si 等人于 2001 年提出，它利用现有网络通讯协议自身的计算能力，将复杂问题分散到网络各 节点进行计算，最后将各节点计算结果进行汇总以获得复杂问题的求解。以下举例 说明如何利用寄生计算解决 np 完全问题： 在网络上发送消息是个很复杂的过程，需要多层网络协议相互协调才能够实现。 例如，当用户请求浏览网页时，用户通过浏览器输入 url地址，后台程序通过 tcp 端口连接目的网站，然后在其上层利用 http 协议展现网页内容。而 tcp 协议处理 数据的能力建立在 ip 协议服务的基础上，在 ip 层信息将被划分成多个数据包，单独 发送到目的地，最后在目的地重构成原始信息。当目标服务器将原始请求访问信息 重构并进行相关处理之后，它通过同一 tcp 连接返回用户浏览器响应信息。响应信 息也将经过多个连续步骤后重新组合，从 ip 层到 tcp 层，最后到达 http 层，将目 的服务器的响应信息反映到浏览器中。可以看到，一个简单的网络交互过程中包含 了大量的复杂操作，而这些操作的正确无误需要相应的计算功能予以保障。 数据包的传输过程中，二进制位信息可能丢失从而导致数据包不再完整，因此 tcp 协议提供了数据包校验和功能以校验数据的完整性。而通过巧妙设计 tcp 报文 内容，可利用此功能进行特定计算。例如 n- sat 问题，根据穷解法构造 2n个数据包， 结合校验和算法及 sat 问题表达式设计校验和字段之后，通过http 协议发送到网 络中至少 2n 个 web 服务器。通过 tcp 协议中校验和计算之后，其中满足 sat 问 题解的数据包会被 web服务器认为是有意义的完整的网页请求命令， 发起端能够获 得一定的响应信息(空白网页或其他)；不满足 sat 问题解的数据包则被认为不再完 9 华 中 科 技 大 学 硕 士 学 位 论 文 整，从而被直接丢失，这样发起端不会收到任何响应信息。根据 web 服务器不同的 响应，发起端浏览器所显示的内容各有差别，就可判断相应的表达式是否 sat 问题 的正解。具体实现方式可查阅文献15。 既然网络具有潜在的计算能力，那么是否也具有潜在的存储能力。可否利用因 特网复杂环境下的闲散资源 (含计算资源与通讯资源， 特别是通讯资源) 进行动态数 据存储，这种存储方式不同于传统数据存储，不能事先规划好远程存储服务节点并 安装存储服务软件。基于对这个问题的考虑，以及受因特网上进行“寄生计算”思 想的启发， “寄生存储”概念应运而生。自寄生存储概念提出以来，引起了学术界极 大的兴趣，然而时至今日并未有实质性的研究进展。 2.2 寄生存储的基本原理 存储的目的是为了不受时间和空间的限制进行信息交换，从这点上来说，数据 的延时存在也就意味着存储。冯 .诺依曼 (von neumann) 在描述第一台电子数字计算 机 edvac (electronic discrete variable automatic computer) 时指出19：存储模块本 质上是让数据延时存在。 在计算机网络中，消息到达远程系统，返回响应所需要的时间是非零的，所以 通过重复发送一段数据并在其应答返回后立即发送出去，就可以使数据延时存在于 网络中，从而达到存储的目的。寄生存储的原理可以用抛球杂技表演来类比。在抛 球杂技表演中，演员可以同时拥有多个球，但在表演过程中，他手中最多只能同时 握住两个球，其余的球总是被抛向空中，这些球在经历一段时间的自由落体运动后 将重新返回到演员手中，而这时，演员就必须将手中的某个球抛出以保证新到来的 球能够被接收。考虑杂技表演中球周而复始的在空中进行自由落体的过程，我们可 以建立一种循环传输和接收数据的机制，让数据包在返回源站点前在网络中传播一 段时间，往返于一定数量的远程计算机之间，就可保证它们一直在网络上，需要的 时候获取，由此构建高容量、可变媒介的存储系统。其模型可基于现有网络协议， 如 icmp20、smtp21等，利用协议中应答请求机制，将网络中传输的数据包作为信 息的载体以达到寄生存储的目的。 10 华 中 科 技 大 学 硕 士 学 位 论 文 在我们常用的 icmp 协议中，协议规范的数据包中有类型字段。通过将该字段 值设为 0，就可以让数据包成为请求回送数据。当某个宿主节点收到请求回送数据包 时，它将按照协议规范将数据包内容不变的返回给发起端。这个过程就像我们日常 问好一样。由于因特网通讯存在的延时，被发送的数据包自网络中延迟存在了一小 段时间。假设建立一种循环机制以保证发起端在每次收到回复后立即将数据包重新 发送出去，那么数据包将会在宿主和发起端之间的这条链路上循环往返。也就是说， 实现了数据包在网络链路中的在线存储。除此之外，寄生存储还可利用其他协议进 行数据存储，且不同的协议所带来的存储特性也各不相同。 2.3 寄生存储的实现难点 寄生存储模型实现的难点主要涉及数据生命周期和读速度之间的平衡、数据可 靠性和保密性之间的平衡以及存储容量和对网络影响之间的平衡。以下分别描述这 三种平衡问题。 2.3.1 数据生命周期和读速度之间的平衡 为了延长数据包的生命周期，寄生存储模型需要有一定机制保证存储发起端在 收到回复的数据包后尽可能快的将数据包重新发送到远端宿主。要延长数据的生命 周期也就是要让数据包在网络中传输的距离的更长，在网络联络中存在的时间更久。 可以将数据包的 ttl 字段设置得尽可能大以保证数据包能够走得更远，从而有效延 长了数据包的生命周期，但另一方面却延长了读数据包的时间。因为数据包传输的 距离远意味着它每次回到发起端所间隔的时间也就越长，而受到 icmp 协议的限制， 并没有有效的方法能够主动接受数据包，因此模型的读数据速度取决于数据包传输 的距离以及通讯链路所造成的延时。当用户需要数据时，在发起端发出读数据请求， 而发起端只能在数据包经过一次漫长的网络穿行回到源点才能够将数据重新封装给 用户。因此，需要选择一些较近的宿主以保证数据包能够在可接受的时间段内获取， 而这种做法又与延长数据包生命周期的初衷相违背。解决方法是生命周期与数据读 速度之间的平衡。设置数据冗余机制，将数据包发送到一组合适的宿主，这些宿主 11 华 中 科 技 大 学 硕 士 学 位 论 文 在延时时间上不尽相同。这样做有两个好处：延长了数据包生命周期 (取决于宿主的 最大延时)；减少了数据的读速度 (取决于宿主的最小延时)。 2.3.2 数据可靠性和保密性之间的平衡 数据可靠性是存储系统的最要参数指标之一。网络并不能够提供足够的可靠 性因为网络自身所处动态环境中，其状况受太多因素影响，而这些影响又都是我 们控制范围之外的。因此，信息的冗余设置对寄生存储的可靠性来说是非常有必 要的。 此外，在数据保密性上，寄生存储非常适合存储敏感数据。现有的存储系统的 保密性主要依靠数据加密技术。而这些加密技术在某些情况下是能够被破解的，而 寄生存储由于数据包是动态分配到事先不可知的宿主的，因此大大降低了这种可能 性。有时候，用户希望信息只是存储很短暂的一段时间便删掉，但是大多数操作系 统在删除文件的时候只是简单的释放文件所占用的硬盘空间而没有彻底清除数据内 容。即使数据经过加密或是压缩了，也可以通过简单的几个命令就恢复。对于想进 行数据恢复的用户来说，这些的确是不错的功能，但是对于保密性很高的敏感数据 来说，这是无法接受的。虽然寄生存储先天具有很高的数据保密性，但是理论上仍 然需要考虑数据包在网络传输中的保密性以防止数据包被中途截获从而透露用户信 息。 在实际系统中，数据封装成 icmp 数据包的时候加入了必要的信息字段，从而 保证数据包被复制并发送到不同的宿主并记录相关信息。数据和宿主之间有 1- 1 和 1- n 两种映射关系： 1- 1在这种关系中，数据包只会发送到唯一宿主。考虑到数据的生命周期，寄 生存储需要提供循环发送冗余数据包到相应宿主的机制。 1- n有时候，为了提高存储的可靠性，需要将相同的数据包发送到不同的宿主。 发送到一组宿主的数据包能够从不同的宿主返回， 因此相对于 1- 1 映射方式来说其可 靠性大大提高，但是由于网络中充斥着大量的冗余数据包使得数据包被捕获的可能 性增大，从而降低了数据的保密性。因此此处的参数“n”可作为调节寄生存储可靠 性与保密性的因子。 12 华 中 科 技 大 学 硕 士 学 位 论 文 2.3.3 存储容量和对网络影响之间的平衡 寄生存储的环境是网络，因此存储容量与对网络的影响之间的矛盾是显而易见 的。然而这个矛盾更倾向于道德问题，就像当前流行的众多 p2p 程序。我们有责任 在享受别人提供服务时候自己也为他人服务。无止境的大范围发送数据包以增大寄 生存储的容量必然会导致网络一定程度的拥塞甚至瘫痪（主要体现在寄生存储发起 者所在的局域网） 。当然在技术层面也应该有相应的防范措施。如现有的众多 ftp 服 务器为了防止过量下载都设置了可允许下载的最大速度及客户链接数。对应到寄生 存储可以将数据的冗余量、数据的发送间隔以及宿主的数量等主要影响网络环境的 参数控制在可接受范围。 2.4 本章小结 本章首先介绍了寄生计算的基本原理，之后引入寄生存储概念，并详细介绍了 其基本原理。然后将寄生存储的实现难点归结为以下三方面并给出相应解决方案： （1）数据生命周期和读速度的平衡； （2）数据可靠性和保密性之间的平衡； （3）存储容量和对网络影响之间的平衡。 13 华 中 科 技 大 学 硕 士 学 位 论 文 3 寄生存储系统设计 本章分析寄生存储的工作流程，系统设计方案，以及用户典型操作，并从软件 设计的角度给出形式化描述。 3.1 寄生存储工作流程 寄生存储可利用现有的多种网络协议进行数据存储。在测试中，我们利用 icmp 协议实现了简单的寄生存储模型并在 cernet (china education and research network) 不同的网络内部进行了大量数据测试。寄生存储的工作主要流程如图 3.1 所示。 文件分割 设置数据包标识位 选择宿主 发送数据包 是 否 否是 准备数据 存储数据 选择宿主 开始 退出 接受到数据包 宿主可用 图 3.1 寄生存储工作流程 以下从准备数据、选择宿主以及存储数据三阶段分别介绍寄生存储工作流程。 3.1.1 准备数据 准备数据主要包括数据分块，以及数据标识位的设置。 14 华 中 科 技 大 学 硕 士 学 位 论 文 数据分块，是指将一个文件分为多个数据块，以方便传送。这样做不仅是因为 寄生存储的数据发送受到网络协议自身携带数据能力的限制，更是为了提高同一文 件的并发存储和访问速率。数据块的大小主要参考网络协议规范。在实验中使用 icmp 协议时，其理论上最大可存储 64k 字节的数据，但是实际情况下，其能携带 的数据远小于这个值。 数据标识位的设置，除了需要按照网络协议标识设置以外，还需要根据寄生存 储需要设置一定标志位，当客户端接收到数据包时能够辨认其所属文件及对应的应 用程序。图 3.2 反映了利用 icmp 协议时数据包标识符的数据结构 (未包含 icmp 本 身标志位)。 user linksfileidlevelchecksumttlredundancy user1linkuser2linkuser3link. . . 图 3.2 数据包标志位数据结构 图 3.2 中，各字段所代表的意义如下： （1）user links，用于链接该文件所属用户，当有多个用户存储该文件时，通过 链表将所有用户链接； （2）fileid，用于标志该数据包所属文件； （3）level，用于标志该数据包重要级别； （4）ttl (time to live)，根据 level字段值设置，level字段值越大的数据包， 相应的 ttl 值也越大； （5）checksum，数据包完整性的重要标志。通过计算 （6）redundancy，数据包的冗余程度。用于表示该数据包需要冗余发送的次数。 重要的数据包其 level值越高，相应的 redundancy值也应当越大。 实际情况中，不同的用户存储相同文件的可能性较小，因此图 3.2 中 userlinks 通常只指向一个节点。数据包准备好之后就可按照相应的网络协议将其发送出去了。 15 华 中 科 技 大 学 硕 士 学 位 论 文 3.1.2 选择宿主 寄生存储利用因特网上的标准协议存储信息。最简单的形式，系统包含一个客 户端节点，一个宿主节点，及链接两者的通信链路。由于因特网不能承诺可靠性服 务，数据包有可能丢失，宿主也有可能退出系统，因此单个客户端需要对应多个宿 主以使系统具有一定的容错能力。当多个客户端共同进行寄生存储时，其网络拓扑结 构更为复杂，客户端之间可以共用宿主，而客户端之间相互独立，这也意味着客户端 a 有可能成为客户端 b 的宿主而被用于实现寄生存储。 其网络拓扑结构如图 3.3 所示。 图 3.3 寄生存储网络拓扑结构 考虑到网络拓扑结构的复杂性22，为了进行寄生存储，首先需要搜索当前网络 中可供使用的宿主。寄生存储模型需要专门的宿主管理模块以动态跟踪并管理可用 宿主列表。宿主管理模块首先发送内容较少的回复请求报文到选中 ip 段中的所有结 点，其过程类似于对该段网络进行“ping”命令广播。各结点的恢复请求响应时间作 为各结点宿主性能的主要参考因素之一。但是参考的标准存在一定的矛盾：如果响 应时间太长，宿主寻找起来不太容易。如果响应时间太短，那么数据的生命周期太 短，实用价值不大。因此当网络结点的响应时间在合适的范围内 (例如毫秒级) 时， 就可以将其作为潜在宿主添加到宿主列表当中。对于大规模的 ip 段，例如教育网， 甚至超大规模的如因特网，在首次运行寄生存储系统时需要花费较长的时间以初始 化宿主列表。当然宿主的选择上还需要考虑其他因素，如链路带宽、链路丢包率等 等。可以看到这些因素都是动态变化的，因此宿主列表需要定期维护更新，以适应 16 华 中 科 技 大 学 硕 士 学 位 论 文 当前网络状况。 3.1.3 存储数据 寄生存储的创新性主要体现在存储数据的机制上。寄生存储的存储媒介与传统 存储不同，网络链路以及网络结点中的缓存是主要存储媒介，因此延长数据存储周 期的有效措施是将数据尽可能长时间的保留在链路或宿主中。寄生存储通过循环发 送接受数据包到一组网络结点。因此需要建立用于数据通讯的多线程以及消息队 列。数据包依据其大小、重要性、冗余程度等属性以及当前网络状况决定发送到唯 一或是多个宿主，之后数据包将在数据链路及网络结点中寄居一段时间，在这段时 间中，它就像存储在本地硬盘中一样。由于整个过程是以网络标准协议为基础且利 用的是网络的潜在资源，因此无需获得宿主的授权而且对宿主造成的影响较小，图 3.4 为利用 http 进行寄生存储的简单示意图，图中“hello, world!”即为存储的数 据。数据包在网络中滞留一段时间之后，存储发起端将接收到来自宿主的数据包回 执， 虽然由于 http 协议不能够直接收到所存储的信息， 但这并不影响数据的提取， 系统可以根据需要决定是否将数据再次发送到网络中进行存储或是直接丢掉。当属 于某个文件的所有数据包均接受到后， 系统便依据数据包的序列号将他们重新组织 成完整的文件。 发起端宿主 http trace “hello world!” http ok “hello world!” 数据 存储时间 time(seconds) 数据 数据 发送数据 接收数据 图 3.4 利用 http 进行寄生存储 17 华 中 科 技 大 学 硕 士 学 位 论 文 数据包的发送过程中有许多其他因素需要考虑。为了避免数据包在网络中的丢 失或者出错，需要提供数据备份及还原机制，以便数据包丢失的时候能够使用备份 数据或是还原数据。例如重要性较高的数据包，其冗余程度也较高且会被发送到多 个网络结点，通常情况下都能够成功接收到。在试验中，我们采用了奇偶校验的方 式以避免数据出错。在数据包层次和文件层次都需要设置奇偶校验，两者作用的对 象不一样。数据包的奇偶校验主要针对单个数据包文件的出错与否，而文件的奇偶 校验则考虑的是将数据包重新整合成用户文件时是否出错。只有保证两者的校验均 正确无误才能够确保用户接受的文件的正确性以及完整性。 另一个需要考虑的问题是数据的保密性。尽管寄生存储的模式决定了数据包被 分发到不同的宿主中，即使单个或少量数据包被恶意截获也难以推断整个文件的内 容，从而大大提高了用户文件的保密性，但是理论上仍然存在某些具有重要信息的 数据包截获的可能性。在这种情况下，传统的加密技术仍然适用于寄生存储的存储 保密性。在我们的模型中，提供了删除制定文件的功能以避免网络中充斥着可能影 响网络性能的无用数据包，其原理很简单，当发起端接收到来自网络中与需要删除 文件相关的数据包时，不予重新发送而是直接将回复报文删除或是不做任何处理即 可。此时。相关文件在经过一定时间后将彻底从网络即寄生存储的存储媒介中清除 掉。 3.2 寄生存储系统设计 以下从地址空间、文件组织、文件容错机制以及并行传输机制四个方面对寄生 存储系统的设计进行描述。 3.2.1 地址空间 寄生存储中的节点和文件在加入系统时，都会被分配成一个标识 (id)。fileid 和 nodeid 一起，形成了寄生存储的二维地址空间：节点地址空间和文件地址空间。 在寄生存储中，节点拥有全局唯一的标识符“nodeid” 。nodeid 是一个 128bit 的二进制整数，由 sha- 1 (secure hash)23散列算法根据节点机器的硬件信息生成， 18 华 中 科 技 大 学 硕 士 学 位 论 文 它唯一制定了节点在宿主地址空间中的位置。sha- 1 算法不可逆、防冲突，并具有 良好的雪崩效应和良好的随机性，这保证了 nodeid 与节点地理位置、网络连接之间 的无关性，使得 nodeid 相邻的节点不会聚集在一个狭小的地域范围内，共用一条网 络通路的可能性很小，有效地均衡了寄生存储所带来的网络链路负载。 寄生存储中的所有文件对象都拥有一个文件标识符 “fileid” 。 fileid 是一个 160bit 的二进制整数，由 sha- 1 散列算法在文件加入系统时根据文件内容进行单向散列计 算后生成，故一个文件的 fileid 也是文件内容的信息摘要。两个不同内容的文件具 有相同 fileid的概率为 160 1/2，产生冲突的可能性几乎为 0。除此之外，选择 sha- 1 算法的优点还体现在根据文件内容生成 fileid 的方式使得文件内容与文件标识符之 间形成了一个映射，同时也将文件属性 (文件属主、文件名等) 和文件标识符在逻辑 上分离开来。使用文件内容相关的 fileid 的主要目的是为了发现系统中由不同用户 共享出来的内容相同的文件，减少这类可重复利用文件对系统存储空间的无谓消耗。 且由于寄生存储不提供文件修改操作，因此文件内容无法改变，从而 fileid 一旦建 立即将保持不变。 3.2.2 文件组织 将文件作为存储的最小单位，虽然实现方便，但并不适用于寄生存储。因为网 络协议自身携带数据的能力是有限的，且将文件分片并将各片分散存储可以在一定 程度上增加文件对节点失效的容错能力。这样做需要为每个文件维护多个分片的元 数据。 我们将系统存储的数据分为实体文件和元数据。用户文件不论叫什么名字， 有何属性，始终是以实体数据文件的形式存放在系统的节点中。客户端不仅要记 录该文件的 fileid，还要记录与该 fileid 相关的用户、文件名等。文件分片后各片 需要记录其所属 fileid、 所对应的宿主及其他副本的位置等信息，形成了实体文件 的元数据。 不用用户可能将同一个文件存放到系统中，由于 fileid 是文件内容的数字摘要， 这些文件将有相同的 fileid，文件的元数据必须要能区分具有相同内容的不同用户的 19 华 中 科 技 大 学 硕 士 学 位 论 文