在大数据时代,随着互联网应用技术的高速发展,信息被海量产生、传输、处理和存储,并成指数级增长的态势。为了满足海量数据的存储需求,分布式存储系统由于其成本低、扩展性强、访问速度高、可靠性高、支持更高的并发访问量等特点得到了广泛的研究与应用,其中,数据被分布式地存储在通过网络连接的多个服务器节点上。随着系统规模的增大和节点个数的增多,系统节点发生故障的情况大大增加。为了保证存储的数据不因为部分节点的失效而丢失,纠删码被广泛地应用于分布式存储系统中,如微软的Azure、谷歌的GFS和淘宝的TFS等。传统的纠删码(如Reed-Solomon码)能够在保证较高数据可靠性的情况下大大减少存储数据冗余,但在修复损坏节点时需要使用大量的网络带宽。为了平衡数据存储和修复带宽之间的折中关系,Dimakis等人使用信息流图对分布式存储系统建模,接着利用网络编码的方法定义了系统容量,分析刻画了节点存储与修复带宽的折中界,并根据折中界提出了最小存储再生(Minimum Storage Regenerating,MSR)码和最小带宽再生(Minimum Bandwidth Regenerating,MBR)码的构造问题。Rashmi等人使用乘积矩阵的方法给出了精确修复下的MBR和MSR码构造。此外还有大量关于再生码构造的研究工作。目前,针对同构分布式存储系统,即各节点存储的数据量相等且修复损坏节点时需要的帮助节点数和下载的数据量均相等,折中界和再生码构造的研究已经较为成熟。考虑到实际存储系统中网络拓扑结构各不相同,在这些异构分布式存储系统中,存储节点往往按集群(机架)组织配置,集群内节点通信带宽较大,而跨集群通信带宽比较受限。因此,在修复损坏节点时,从集群内节点下载较多数据,集群外节点下载较少数据更能充分利用网络带宽。这方面的研究工作主要分为含集群中继节点和不含中继节点两类,其中,中继节点用于从同集群内其它节点收集数据然后传给集群外节点。Hu等人研究了含中继节点的情况下,在节点修复时最小化跨集群带宽的问题;Prakash等人同样分析含中继节点的集群分布式存储系统,各中继节点不仅应用于节点修复,同时应用于原始数据重构。另一方面,Sohn等人则重点研究了不含中继节点的集群模型,从集群内外节点下载的数据量分别作为两个参数进行分析,其模型分析中假设在修复一个损坏节点时,要从所有其它完好节点下载数据,该假设虽然可以最大化系统容量,但却导致较高的重构读开销,即帮助节点数取到了最大值。同时,该假设不利于分析多节点同时损坏的情况。此外,在实际分布式存储系统中分散节点(以下简称“散点”)也同样普遍存在,但这方面的研究工作还不充分。基于此问题,本文首先研究了更一般参数约束下的集群模型(不含中继节点),其中,我们不需要从所有完好节点下载数据来修复损坏节点,而只要求从所有集群内节点下载数据,集群外帮助节点数则作为变量进行分析。由于我们研究了更一般化参数约束下的集群模型,故传统的同构分布式存储系统以及已有的集群模型的折中界均可以由本文模型退化得到。在此基础上我们从最小割分析入手进一步研究了集群散点分布式存储系统,这对于结合实际存储系统构造灵活的再生码,以充分利用网络带宽有重要的理论指导意义。本文的研究内容主要分为如下几个方面:首先,研究了一般参数下的集群分布式存储系统容量以及存储修复带宽折中界问题。在修复损坏节点时,不同于已有的所有完好节点均用作帮助节点的情况,我们只要求同集群内的节点均用作帮助节点,集群外帮助节点数不加限制,该假设是基于集群内通信带宽较大的实际情况,集群内节点优先参与数据传输。根据刻画出的存储修复带宽折中界,我们给出了相应的MSR码构造实例。其次,我们进一步研究了在集群分布式存储系统中加入单个散点之后,系统容量以及折中界的变化。分析了散点修复带宽和集群节点修复带宽参数的相互关系对折中界的影响,理论上证明了加入单散点后,分布式存储系统参数和容量的变化关系。特别地,我们证明了当每个集群由R个节点构成,且任意k个节点可以恢复原始文件(MDS属性)时,若R|k则增加一个散点将不会影响到原集群系统容量,其它情况则使容量降低。接下来,我们利用干扰对齐的方法给出了单散点情况下的MSR码构造实例。最后,在单散点模型研究的基础上,我们进一步研究了多散点集群分布式存储系统模型,由于散点又可以看作是只含有一个节点的特殊集群,故该模型又可称作异构集群分布式存储系统模型。我们给出了多散点情况下的系统容量以及存储修复带宽折中界,并从多个角度分析了系统参数(帮助节点数量、散点个数和修复带宽关系)对存储修复带宽折中界的影响。此外,我们同样给出了多散点模型下的MSR码构造实例。