导　　师： 冯丹

学科专业： 081201

授予学位： 博士

作　　者： ;

机构地区： 华中科技大学

摘　　要： 数据的爆炸式增长使得当前的存储系统规模越来越庞大。而云计算、云存储和大数据等新技术不断的出现,也对存储系统的容量、性能等方面提出了更高的要求。当前数据中心广泛使用异构存储设备构建大规模存储系统,以满足存储容量和性能需求的不断增加。如何构建大规模异构存储系统面临诸多问题,其中一个典型问题是由于设备负载和服务能力不匹配,使得存储系统中广泛使用的条带等并行访问技术难以充分发挥作用,导致性能降低。同时,随着云存储等技术的发展,不同应用共享异构存储系统越来越普遍,如何为这些应用提供服务质量保证或者服务公平性非常重要,而存储系统异构性更是对解决这一问题提出了更高的挑战。通过研究异构存储系统中的缓存算法,解决异构存储系统中的性能优化和服务质量保证等问题,主要内容包括以下几个方面。 针对异构存储系统的设备负载和服务能力不匹配所导致的性能降低问题,提出了一种基于负载特征识别和访问性能预测的缓存算法/(Caper/)。 Caper算法的主要思想是通过优化缓存调度来平衡I//0请求在异构存储设备上的性能差异,减少甚至消除性能最差的存储设备在异构存储系统中性能瓶颈问题。Caper算法采用缓存分区策略,为了合理设置缓存分区的大小,Caper算法用CART模型预测I//0请求在存储设备上的性能,并结合性能预测结果分析不同访问特征负载的缓存需求。此外,Caper算法还改进时钟缓存替换算法以进一步提高缓存效益。实验结果表明,和Clock算法、Forney算法以及Chakraborty算法相比,Caper算法在不同类型的负载访问下均能够获得比较明显的性能提升。 为应用提供服务质量保证一直都是共享存储系统中的重要研究内容。然而,当不同应用共享缓存时,不同I//0请求到达率的应用之间相互影响程度不一样。在传统缓存算法/(如LRU算法/)中,和I//0请求到达率较高的应用相比,I//0请求到达率较低的应用获得的缓存资源比较少,从而造成I//0请求到达率较低的应用的服务质量难以保证。针对不同I//0请求到达率的应用共享缓存时存在的上述问题,提出了一种服务质量保证的缓存算法/(Qaca/)。Qaca算法采用开始时间公平队列控制I//0请求的服务顺序,并采用基于反馈结构的缓存管理策略动态调整应用之间的缓存分配。算法周期性地跟踪应用的服务质量保证程度,计算已满足服务质量保证的应用的富余缓存,然后将这些富余缓存分配给未达到服务质量保证的应用,以保证更多应用的服务质量。在执行缓存分配时,Qaca算法根据富余缓存是否充足采用性能优先或者服务质量优先的缓存分配策略。实验结果表明,和LRU算法和Static算法相比,Qaca算法能够以较小的性能牺牲获得较大程度的服务质量保证,甚至有可能同时获得少量的性能提升。 在不同I//O请求到达率的应用共享缓存时,传统的预取算法存在较多的预取浪费和预取缓存污染,从而导致性能降低。特别是I//O请求到达率较低的应用,其预取缓存命中率的降低程度要远远高于I//O请求到达率较高的应用,从而使得性能降低呈现不公平性。针对不同应用在共享预取缓存中存在的上述问题,本文提出了一种优化性能和兼顾公平性的预取算法Fepa。为了减少因应用的I//O请求到达率差异造成的预取浪费和预取缓存污染,提出了一种基于I//O请求到达率的预取长度动态调整策略,提高缓存效益和整体性能。此外,Fepa算法分别为每个应用计算最小缓存需求,以避免一个应用发生预取缓存缺失,同时还能够让其它应用分配到更多的缓存,从而提高缓存分配公平性。并以最小缓存需求计算为基础,提出一种基于轮询方法的缓存分配策略,在公平性和整体性能之间取得较好的平衡。实验表明,和LRU算法、Linux内核自带的预取算法以及AMP预取算法相比,Fepa算法在性能和公平性方面都有较好的效果。 The scale of storage system is becoming larger with the rapidly increase of the amount of produced data. Along with the development of computer technologies, such as cloud computing, cloud storage and big data, thus putting forward higher requirement to storage systems:higher capacity, higher performance and higher reliability. As a result of increasing requirement of capacity and performance, the storage system trends more and more hetero-geneous. The traditional algorithms face several problems in the heterogeneous storage systems. One problem in heterogeneous storage system is the degradation of performance as load unbalance. The difference of capacity and performance between heterogenous stor-age devices make the parallelism technologies hardly to obtain high performance. At the same time, the number of sharing application will be significantly increased with the larger scale of storage system. It is very important to provide QoS or fairness to the application in such sharing environment. It is a serious challenge to solve the above problems as load unbalance in heterogeneous storage system. We study the cache replacement algorithms in heterogeneous storage system to address the above problems. Compared with migration and other algorithms, the cache replacement can obtain better performance with little cost. Specifically, the contributions of this dissertation are three fold. We propose an caching algorithm based on performance predication and identification of workload characteristic, named Caper. The main idea of Caper algorithm is to alleviate the load unbalance and performance bottleneck in heterogeneous storage devices by caching algorithm. The Caper algorithm partitions the cache into several partitions. In order to set appropriate partition size, we analysis the caching requirement for the partitions by the cache utility and accessing performance. The Caper algorithm build CART model to predict the performance when an I//O request access the storage device. The Caper algorithm predict the cache utility for the workload with different access pattern. Besides, the Caper algorithm extends the Clock algorithm to improve the cache utility. The experimental results show that compared with the Clock algorithm, Forney algorithm and Chakraborty algorithm, the Caper algorithm can obtain better performance under different type of workload. It is very important to provide QoS for applications in the sharing environment. How-ever, the commonly used cache replacement algorithms /(like LRU/) are inherently un-fair in cache allocation for heterogeneous applications. They implicitly give more cache to the application with high access rate, which may lead that it is hard to guarantee the QoS for the application with slow access rate. We propose a caching management algorithm to pro-vide QoS for the application with devise access rate, named Qaca. The Qaca algorithm adopts the start-time fair queuing to control the servicing order of I//O requests. At the same time, the Qaca algorithm propose a feedback-based caching allocation, which periodically monitor the QoS guarantee for each application and analysis the cache utility under curren-t workload. When performing the caching allocation, the Qaca algorithm chooses one of performance-first and QoS-first greedy allocation whether the cache is enough or not. The choosing obtain fine tradeoff between performance optimize and QoS guarantee. The ex-perimental results show that compared with the LRU algorithm and the Static algorithm, the Qaca algorithm can obtain better QoS guarantee with little performance degradation. And at some times, it can achieve slightly performance improvement. When the applications with diverse access rate share the cache, the application with slow access rate always suffer huge much prefetching wastage and prefetching pollution in the prefetching cache, which will make overall performance degradation. In concurrence paradigm, providing fairness to concurrent applications is also very important which always ignored by the traditional prefetching algorithms. For the above issues, we propose a fairness and efficiency prefetching algorithm, named Fepa. In order to avoid prefetching wastage, the Fepa algorithm proposes a rate-aware adjustment of prefetching degree. An analysis model is also proposed to compute the optimal partition size to further improve the cache utility. Based on the analysis model, the Fepa algorithm proposes a round-robin caching allocation, which get fine tradeoff between fairness and overall performance. the experimental results show that compared with the LRU algorithm, Linux Kernel prefetching algorithm and AMP prefetching algorithm, the Fepa algorithm can achieve better performance and fairness at the same time.

关 键 词： 缓存 异构存储 性能优化 共享 服务质量保证 公平性

分 类 号： [TP333]

领　　域： [自动化与计算机技术] [自动化与计算机技术]