分布式存储系统中高性能和高可靠性问题的研究

摘要

计算机技术和宽带网络技术的迅猛发展以及存储市场的巨大需求，极大地推动了分布式存储技术的进步，同时也给现有的存储系统不断地提出各种新的要求。对分布式存储系统而言，系统应该能够提供始终如一的、高质量的存储服务，尽量降低由于网络环境的动态性和不可预知性以及热点数据访问等原因对系统服务的可靠性和服务性能所造成的影响。另外，数据的重要性也决定了高可靠性是分布式存储系统的基本目标之一。在信息化程度越来越高的今天，数据丢失已经变得不可忍受，因为一些重要信息的丢失往往会给企业带来巨大的经济损失。因此，如何实现高性能、高可靠的存储服务是当今存储系统中亟待解决的关键问题。
　　 然而，纵观现有的各种分布式存储系统，发现它们在服务性能和可靠性方面仍然存在一些问题，主要表现在：1）目前大多数存储系统普遍存在主服务器性能瓶颈和单点失效问题，由此容易造成系统服务的不可靠和服务性能低下。虽然心跳机制能够在一定程度上降低单点失效发生的可能性，但在系统服务的可用性和服务性能等方面仍然存在着不足之处。2）现有的任务调度算法往往追求单一的调度目标，虽然可以使得加权总完成时间最优，但是在任务的平均周转时间方面考虑不足，并且在某些情况下可能会导致“饥饿”现象。3）现有的大多数副本管理策略主要根据节点对文件的访问频率或者系统总的请求响应时间来选择合适的副本放置节点，缺乏对单个请求的响应时间要求进行考虑，这可能会造成部分用户的请求响应时间过长。4）目前关于存储系统可靠性方面的研究主要是围绕数据冗余方法的研究而展开，而较少关注甚至忽略了存储资源分配方案对系统整体可靠性的影响。现有的存储资源分配方案虽然简单直观，但在文件大小和文件的重要性对系统整体可靠性的影响方面考虑不足。
　　 本文针对现有的存储系统在服务性能和可靠性方面所存在的一些问题，分别从系统服务模型、任务调度算法、副本分发机制以及存储资源分配方案四个方面进行了系统而深入的研究，取得了若干创新性成果。
　　 本文的主要研究工作和创新性成果体现在以下几个方面：
　　 1.针对现有存储系统在服务的可靠性和服务性能等方面存在的不足，首先引入一种动态k叉树结构，给出了动态k叉树的相关定义和算法。然后在此基础上，提出了一种基于系统负载的轮流服务模型--ASSL（Alternate Service based on System Load）。在ASSL模型中，首先采用自回归负载预测模型来预测节点的负载以及过载发生的时间，这样，可以在节点过载发生之前采取主动防范措施（选举新的服务节点），从而提高了系统服务的可用性和服务性能；其次，通过采用基于选举域划分的多机心跳机制方法，减少了节点失效的检测时间和主节点的通信量；最后，为了进一步降低选举开销，对主节点过载和失效两种情形分别采取不同的选举机制。理论分析和实验结果表明，该模型对提高系统服务的可靠性、可用性以及服务性能是有效的。
　　 2.分析了现有任务调度算法MTWCT（Minimize Total Weighted Completion Time）存在的不足，在此基础上提出了一种改进的优化任务调度算法E-TWCT（Enhanced TWCT），并给出了ρ因子的划分规则、△ρ和△t的临界值的设定方法以及E-TWCT算法的调度策略，同时进行了算法复杂度分析。实验结果表明，本文提出的算法不仅能够有效地消除“饥饿”现象，而且能够获得和MTWCT算法相同或者更优的平均周转时间，并且加权总完成时间和MTWCT算法相当。
　　 3.分析了现有副本管理策略存在的不足，根据副本分发方案所需满足的目标要求，建立了一种基于响应时间度量的动态副本分发模型，并设计了求解该模型的遗传算法。实例分析表明，本文求解的副本分发方案RPRTM（Replica Placement based on Response Time Measure）能够在满足各个节点的单个请求的响应时间要求的同时使得系统所需创建的副本数最小化，而且在最大程度上缩短了系统总的请求响应时间，提高了系统整体服务性能。
　　 4.针对现有存储资源分配方案存在的不足，提出了文件优先级比重的概念，充分考虑了文件大小和文件重要性对系统整体可靠性收益的影响。在此基础上，研究了有限资源条件下如何对多个大小不同、重要性不同的文件进行资源分配的问题。建立了一种非线性整数规划模型，求解并得出了能够使得系统整体可靠性收益达到最大的理论最优资源分配方案和可行最优资源分配方案，同时给出了相关的理论推导和证明。实验结果表明，相比现有的资源分配方案而言，本文求解的资源分配方案能够在相同存储资源条件下获得更高的系统可靠性收益。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 研究背景及意义

1.2 分布式存储系统概述

1.2.1 网络存储系统

1.2.2 集群存储系统

1.2.3 网格存储系统

1.2.4 P2P存储系统

1.3 现有分布式存储系统在服务性能和可靠性方面存在的问题

1.4 本文的主要研究内容

1.5 本文的组织结构

第二章 一种基于系统负载的轮流服务模型

2.1 引言

2.2 相关研究

2.2.1 存储系统的服务结构

2.2.2 心跳机制

2.3 动态κ叉树

2.3.1 动态κ叉树及其相关定义

2.3.2 域成员节点

2.3.3 相关算法

2.4 基于系统负载的轮流服务模型

2.4.1 自回归负载预测模型

2.4.2 基于选举域划分的多机心跳机制

2.4.3 动态域主节点的选举机制和算法

2.5 系统可靠性及服务性能分析

2.5.1 系统可靠性分析

2.5.2 系统服务性能分析

2.6 实验仿真及结果分析

2.7 本章小结

第三章 一种兼顾加权总完成时间和平均周转时间的任务调度算法

3.1 引言

3.2 相关研究

3.3 最小化加权总完成时间算法

3.3.1 算法思想

3.3.2 不足之处

3.4 E-TWCT任务调度算法

3.4.1 ρ因子的划分

3.4.2 临界值设定

3.4.3 算法思想

3.4.4 复杂度分析

3.5 实验仿真及结果分析

3.6 本章小结

第四章 一种基于响应时间度量的动态副本分发机制

4.1 引言

4.2 相关研究

4.3 基于响应时间度量的副本分发模型

4.3.1 响应时间分析

4.3.2 问题描述

4.3.3 模型建立

4.4 基于遗传算法的副本分发模型求解

4.4.1 编码

4.4.2 适应度函数

4.4.3 遗传操作

4.4.4 终止条件

4.5 实例分析

4.5.1 节点拓扑结构及相关参数

4.5.2 比较分析

4.6 本章小结

第五章 有限资源条件下最大化系统可靠性收益的资源分配方案

5.1 引言

5.2 相关研究

5.3 基于贪婪算法的资源分配方案

5.3.1 算法思想

5.3.2 不足之处

5.4 最大化系统可靠性收益的资源分配模型

5.4.1 问题描述

5.4.2 模型建立

5.4.3 模型求解

5.4.4 分析讨论

5.5 实验仿真及结果分析

5.6 关于模型的进一步讨论

5.7 本章小结

总结与展望

参考文献

攻读博士学位期间取得的研究成果

致谢