第1章绪论
1.1研究意义
随着计算技术的快速发展、网络带宽的增长及智能设备的普及，信息处理与网络服务已经深入到人们生活的方方面面。尤其近几年P2P、社交网络、多媒体共享等网络技术与移动互联网的发展，给人们提供便利的同时，也带来了全球信息资源的爆炸性增长。图灵奖获得者Jim Gray曾在1998年的获奖演说中，对未来数据量急剧增长的规律做过这样的预言:未来每18个月产生的数据量等于有史以来的数据量之和加州大学圣地亚哥分校的一群科学家曾计算出2008年全球互联网服务器上存储的信息的总容量为9.57ZB，相对于我们常用的GB和TBZB这个数据容量单位显然已经超过了普通人的理解。1ZB=1024EB，而1 EB=1024PB 1 PB=1024TB , 1 TB=1024GB换而言之每ZB大约为1万亿GB，而9.57ZB则大约为10万亿GB。数据海量化成为了一种趋势。
随着人类活动空间的不断拓展，实验手段的不断丰富，测量仪器的不断进步，在很多领域产生了海量数据，如天文观测、高能物理、能源研究、基因分析等。比如，欧洲粒子物理研究中心(CERN)在通过大型强子对撞机(LHC)进行实验研究时，为了捕捉实验中每个质子或中子的活动，系统需要拍摄数百万张的电子照片，并将它们存储下来。目前的数据量大约是每秒1 OOMB到1 GB，每年大约需要存储25PB(25,OOOTB)的数据。著名搜索引擎网址Google所索引的网页数量已经超过了81亿张，图片也超过10亿张。
在互联网时代来临之前，信息孤岛是我们社会的主要形态，信息过剩的问题只存在于大企业当中。但当网络打通了这样的阻隔，将信息孤岛连通之后，全社会的数据量立即呈现出了爆炸性增长，管理和存储这些数据成了鱼待解决的问题。对于海量存储来说，传统的解决方案大多采用网络存储。网络存储需要性能强劲的专用服务器和专用磁盘阵列进行数据存储，它虽然拥有很高的可靠性，但是其成本太高。同时，传统的网络存储系统采用集中的存储服务器存放所有数据，存储服务器成为系统性能的瓶颈，也是可靠性和安全性的焦点，不能满足大规模存储应用的需求。
近几年，随着便携式互联网设备与移动互联网的快速发展、人们对存储的需求日益增长。分布式存储做为海量存储的主要解决方案正悄然兴起，它将数据分散存储在多台独立的设备上。以网络技术为基础，将服务器系统的数据处理和数据存储分离，实现对数据的海量存储。分布式网络存储采用可扩展的系统结构，利用多台存储服务器分担存储负荷，利用位置服务器定位存储消息，不仅提高了系统的可靠性、可用性和存储效率，而且易于扩展。同时，分布式存储网络提供地理位置上分散的存储节点，以及对其的共享存储访问，降低了数据访问的时延。
Ahlswede等人于2000年提出了网络编码的概念，指出对组播网络中的某些节点附加额外的编码操作能使信源与组播成员间达到最大流最小割的组播速率。网络编码一经提出便引起了国际学术界的广泛关注，其理论和应用已成为通信领域研究的新热点。近些年的一些研究表明，将分布式存储技术和网络编码技术的结合起来，可以明显的减少节点修复时的带宽消耗。这些研究还处于刚刚发展的阶段，大多仍停留在理论层面上，如何将现有的理论不断拓展，如何将己有理论技术转化为实际上可行的技术，都是值得进一步研究的课题。当前带宽资源的宝贵，更加凸显出其实用价值。因此，对其进行深入的理论与实际应用的研究，都有十分重要的意义。
1.2国内外研究现状
分布式存储系统通常需要保证两个最基本的性能:数据的耐久性和可用性。数据的耐久性是指在系统中存储的数据不会因为永久的节点故障而导致丢失，诸如磁盘故障等等;而可用性意味着系统将能够及时取回数据对象。两者的区别是:一个能被可持久存储的数据(耐久性)可能当前并不可用(可用性)。分布式存储系统主要依赖数据冗余技术来保证这两个性能。
当前，常用的两种数据冗余策略为“复制(Replication)”和“纠删码(Erasure Codes) 2002年，Weatherspooon和Kubiatowiez定量地比较了分别基于纠删码和复制的两种存储系统，分析得出了，在同样的数据冗余度下，相比于复制而言，纠删码有更小的存储消耗。
然而，分布式存储系统的单个节点的可用性不高，在系统中会不断的有节点因为磁盘损坏、自然灾害等因素而失效，还要保证数据的耐久性。因此，在节点失效后，一定要加入新节点来代替失效的节点，来维持整个系统的数据可靠性。由于分布式存储系统存储的都是海量数据，这无疑就为分布式存储系统的设计带来了极大的挑战!由此，出现了一个新的垂待解决的问题:如何有效地重建丢失节点的数据，即如何尽可能少地消耗系统资源来重建丢失节点的数据?为了解决此问题，人们将网络编码引入到了分布式存储系统中。下面介绍一下相关的研究现状。
2005年，Szymon等在文献中首次将网络编码的思想引入到分布式存储系统中，并定量的比较了基于复制、纠删码与网络编码的分布式存储系统的性能，得出在相同的数据冗余度下，相对其它两种方案，网络编码的存储消耗更小。
2007年，Dimakis等人在分布式存储系统引入网络编码，将其中的节点修复问题抽象成了通信网络中常见的单源多播问题，利用网络信息流图对其分析，引入了修复带宽的概念，即新加入节点需要从系统中下载多少数据来产生冗余块，作者在理论上提出了两种基于网络编码的编码方式OMMDS编码以及再生码.
第1章 绪论............ 9-13
1.1 研究意义............ 9-10
1.2 国内外研究............ 10-12
1.3 本文的主要研究内容............ 12-13
第2章 相关理论基础............ 13-19
2.1 经典的网络流............ 13-15
2.2 网络编码概述............ 15-17
2.3 纠删码概述............ 17-19
第3章 节点修复问题............ 19-23
3.1 问题描述............ 19-20
3.2 不同的修复............ 20-21
3.3 相关工作............ 21-23
第4章 对称的多节点............ 23-28
4.1 模型描述............ 24-25
4.2 网络信息............ 25-27
4.3 本章小结............ 27-28
第5章 修复带宽的理论............ 28-47
5.1 模型1：t=1的............ 31-37
5.2 模型2：t=r的............ 37-42
5.3 模型3：一般............ 42-46
5.4 本章小结............ 46-47
结论
近些年，IT行业的飞速发展与互联网的广泛应用，带来了全球信息资源的爆炸性增长，各种应用对存储系统提出了越来越高的要求。分布式存储系统，因其廉价性及高扩展性等优点，而倍受人们关注，理所应当地成为了海量数据存储的首要选择。然而，由于分布式存储系统中各个存储节点的可用性不高，为保证数据可靠性，系统会频繁的进行节点修复。因此，如何有效地进行节点修复就成为了巫待解决的问题。
本文主要研究了分布式存储系统中多节点协作修复问题，其具体的研究内容和贡献如下:
·现有的工作对单节点修复问题的理论研究比较完善，专门针对多节点协作修复问题的理论研究较少，然而在实际的分布式存储系统中多节点同时修复的问题非常常见。然而，现有多节点协作修复的模型，条件要求比较严苛，要求新节点两两之前都可以进行数据交互，此外其对应的新节点之间数据传输量和从旧节点与新节点间的数据传输量不同，这会令实际分布式存储系统的设计变得复杂。在研究现有的分布式存储系统中节点修复模型的基础上，提出了一个对称的多节点协作修复模型SMCR。