分布式存储中更新带宽的研究

作     者：李政睿 

作者单位：中国科学技术大学 

学位级别：硕士

导师姓名：林宪正

授予年度：2021年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：分布式存储系统 纠删码 不规则阵列码 更新带宽 冗余 更新复杂度 修复带宽 

摘      要：在本论文中,我们研究基于纠删码的分布式存储系统中的更新过程。具体来说,我们考虑的更新过程是,当一个节点更新时,该节点需要经由网络传输一定的数据给其他节点来维持数据一致性,而其他节点在收到这些数据之后再经由某些计算来更新其中需要相应被更新的数据。在前期的调研中,我们发现以往的研究结果忽视了这一过程的传输效率,也就是此过程占用网络带宽的大小。因此,我们提出一个新的衡量标准:更新带宽,其被定义为分布式存储系统中一个节点的所有数据单元更新时,为了保证分布式存储系统中数据的一致性,平均需要传输给其他节点的数据量,也就是平均需要占用的网络带宽。另外,为了保证在满足更新带宽较小的同时不会影响分布式存储系统在其他方面的需求,诸如存储效率、修复效率、更新过程中的读写效率,我们还研究了更新带宽与现有三个分布式存储系统的重要指标——冗余、更新复杂度和修复带宽之间的关系。总结来说,本文包含以下贡献。1.对于最一般的阵列码——不规则阵列码,我们在保证一定的节点修复能力的前提下（以下提到不规则阵列码都指一定的节点修复能力的不规则阵列码）,建立了不规则阵列码最小更新带宽的完整数学表达,并且给出了能达到最小更新带宽的不规则阵列码相应参数的具体刻画。2.基于最小更新带宽的结果,我们定义一类拥有最小更新带宽的不规则阵列码,称作最小更新带宽（MUB）码。进一步,我们推导了任意MUB码所需要的最小冗余,也就是不规则阵列码在达到最小更新带宽的前提下,所需要的最小冗余。为了与不规则阵列码所需要的最小冗余相区别,我们将MUB码所能达到的最小冗余称为极小冗余。3.为了进一步刻画更新带宽和冗余的关系,我们分析了 MUB码的极小冗余和不规则阵列码的最小冗余,发现这两个参数只在某些特殊情况下才相等。由此,我们进一步定义一类特殊的MUB码为同时拥有最小更新带宽和最小冗余的不规则阵列码,称作最小冗余最小更新带宽（MR-MUB）码,还讨论了哪些特殊的不规则阵列码才有可能成为一个MR-MUB码。4.我们分别构造了 MR-MUB码和拥有极小冗余的MUB码来说明我们得出的有关更新带宽和冗余的下界都是准确且可达的。5.为了刻画更新带宽与更新复杂度的关系,我们推导了 MR-MUB码所能达到的更新复杂度的下界,并且这一下界是严格大于不规则阵列码的最小更新复杂度的。这说明最小冗余,最小更新带宽和最小更新复杂度三者是无法同时达到的。6.为了刻画更新带宽与修复带宽的关系,我们构造了一类（n=k+2,k）最大距离可分离（MDS）阵列码,并证明了这是一类MR-MUB码且拥有最优修复带宽。这说明在n-k=2这一特殊的条件下,不规则阵列码的最小冗余,最小更新带宽和最优修复带宽三者可以同时达到。