一种支持并发访问流的文件预取算法

设计并实现了一种按需预取算法,采用更为宽松的顺序性判决条件,并以页面和页面缓存的状态作为可靠的决策依据.它可以发现淹没在随机读中的顺序访问并进行有效的预读,支持对单个文件实例的并发访问而产生的交织访问模式.实验结果表明:相对于原Linux预读算法,该算法在随机干扰下的顺序读性能可提高29%;交织读的性能是传统算法的4~27倍;同时,应用程序可见延迟改善可达35倍.该算法已被Linux 2.6.24内核采用.     

Linux预取算法分析与研究

LinuX作为一个多任务、分时、通用的开源操作系统,越来越广泛地应用于各种商业和企业的服务器。为了提高系统的性能,LinuX采用预取技术将应用程序所需的数据提前加载到缓存中,减少应用程序的I／O等待时间。然而由于服务器系统负载的多样化,导致了预取算法遇到越来越多的挑战。该文主要从分析Linux-2．6．29张涛rc2内核源代码人手,对Linux预取算法的体系结构与内部机制进行了深入分析与研究,并提出了一些改进预取算法的方法．对于进一步提高Linux系统服务器的性能以及LinuX的推广与使用具有重要的意义。     

网格虚拟组织副本协作预取机制

副本复制是数据网格中提高数据访问效率的有效方法,如何提高副本复制的效率是一个关键性问题.现有的复制策略大多基于文件访问历史选择高价值副本进行复制,但其针对的都是节点已经访问过的文件.通过对虚拟组织文件访问特性进行深入分析,引入隐性高价值文件概念,提出虚拟组织副本协作预取机制(cooperative replica prefetching mechanism,简称CoRPM),使得本地节点通过与虚拟组织中其他节点进行协作来获取隐性高价值文件副本.该机制首先给出了副本协作预取架构,各个虚拟组织节点上的文件预取模块以协作的方式为虚拟组织内节点提供文件预取服务;然后,在副本协作预取架构的基础上设计了副本协作预取流程,其核心算法包括以作业类型为中心的本地文件预取算法和预取文件选择算法.模拟实验结果表明,CoRPM与已有的基于文件访问历史的副本复制策略相结合,可以更加有效地降低数据访问延迟.     

DiskSeen预取算法的分析及优化研究

计算机存储层次结构是一种典型的金字塔形结构,以平衡计算机对存储系统的两方面需求,即高速处理数据和大的存储容量。然而随着信息技术的飞速发展,计算机处理器和磁盘之间的速度鸿沟持续扩大,因而磁盘访问便成为一个 影响 计算机系统性能的瓶颈问题。近几十年来,如何减小磁盘访问延迟对整个计算机系统性能的影响,一直是存储领域的热点研究问题。预取技术,通过提前预测I/O请求并将数据读入缓存中,以对上层应用程序隐藏I/O延迟,是缓解这一瓶颈问题的重要技术手段。DiskSeen是一种块级预取算法,通过分析磁盘块的位置和访问时间的联系来提高磁盘访问的顺序性和总体的预取性能。针对DiskSeen算法,文中主要做了以下几方面工作:首先,分析DiskSeen算法的不足之处,据此提出动态控制预取粒度和二次匹配激活历史预取方法,以优化效率;然后,实现了DiskSeen算法及改进后的算法;最后,在模拟仿真实验环境下对算法进行了性能对比测试。实验结果显示,DiskSeen算法能够明显提高缓存命中率并减少平均响应时间,而优化后的DiskSeen算法则可以进一步提升上述两方面的系统性能。     

Web预取技术综述

Web预取是减少用户访问延时、提高网络服务质量的关键技术之一,近年来已成为国内外的研究热点.通过利用WWW访问的空间局部性,Web预取使缓存机制从时间局部性向空间局部性扩展.归纳了Web预取技术的分类,概括和比较了不同类别的优势和局限性,给出了预取模型的基本框架及每部分的主要功能,并对各种评价标准进行了详细介绍.同时,深入分析和探讨了现有的几种典型预取算法,系统地比较了这些算法的优缺点.最后从在线性、协作预取、动态流行度、划分用户会话和基于语义与基于路径相结合等方面指出了Web预取技术的研究方向.     

无线Web访问的缓存和预取机制

缓存和预取在提高无线环境下的Web访问性能方面发挥着重要作用。文章研究针对无线局域网的Web缓存和预取机制,分别基于数据挖掘和信息论提出了采用序列挖掘和延迟更新的预测算法,设计了上下文感知的预取算法和获益驱动的缓存替换机制,上述算法已在Web缓存系统OnceEasyCache中实现。性能评估实验结果表明,上述算法的集成能有效地提高缓存命中率和延迟节省率。     

Linux文件服务器单线程和多线程架构的性能研究

主要研究在Linux操作系统下,一个文件服务器分别采用单线程的架构和多线程的架构,在不同类型的10负载情况下的性能。以NFS服务器为参考进行性能的测试,并对测试结果进行探讨,深入研究了Linux内核的预取机制和磁盘10调度机制对磁盘10性能的影响,分析单线程的架构方式和多线程的架构方式在各种情况下产生性能差异的原因,最后总结出单线程和多线程的架构方式分别适用的场景。     

虚拟机环境下软件按需部署中的预取机制

针对大规模虚拟机环境下软件的按需部署,提出了一种基于预取的按需软件部署优化机制,能够降低用户端虚拟机的启动延迟以及为用户提供更好的虚拟机本地运行性能.基于用户使用软件的行为特点以及虚拟磁盘映像的细粒度分割,预取机制在后台对服务器端存储的虚拟磁盘映像进行预取,通过一种基于访问频率和优先级的预取目标识别算法AFPTR(access frequency and priority-based prefetch target recognition)和一种预取量动态调节机制,将预取集中在用户使用的少数小尺寸的虚拟磁盘映像上,并在预取过程中对预取量进行动态自适应地调节,以提高虚拟磁盘访问的本地命中率,进而提高用户端虚拟机的运行性能.基于QEMU虚拟机和Linux平台,实现了基于预取的按需软件部署原型系统.实验结果表明,预取机制能够有效地降低虚拟机的启动延迟,并能提高虚拟机的本地运行性能,支持虚拟机环境下按需、快速的软件部署.     

基于数据挖掘的文件元数据预取探究

在文件存储系统中,文件系统整体性能的提升对于保证文件的安全性和可靠性具有重要意义,而在此过程中,元数据访问性能与文件系统性能有密切关系,要想进一步满足大规模文件存储系统需要,就必须建立相应的文件元数据预取模型。本文通过对基于数据挖掘的文件元数据预取进行分析,以期满足文件数据的大量存取访问需求。     

文件Cache自适应策略研究

Linux系统在被不同大小的数据块访问时,系统读写性能有差异。在少数特定访问数据块大小的应用中,Linux系统读写性能较差。文件Cache算法的性能是导致该问题的原因之一。在分析访问数据块大小对文件Cache算法性能的影响的基础上,提出了一种文件Cache自适应策略。该策略考虑了预取算法对于页面置换算法的影响,增强了页面置换算法对访问数据块大小变化的适应性,达到了提高Linux系统读写性能的目标。Linux系统读写性能测试实验表明,该策略可以使Linux系统在被不同大小的数据块访问时保持稳定且更优的读写性能。     

RLCP:异构的协同预取存储设计方案

根据存储系统各级缓存的不同特点,提出了一种基于网络的异构协同预取方案RLCP(RA and Linux collaborate prefetching),它通过在存储客户端和存储服务器端使用不同的预取算法和替换算法,构建一个异构的两级存储系统,并利用合适的协同预取策略,动态调整预取算法的积极性,提高了存储系统的性能,同时也为云存储提供了一种优秀的解决方案.     

Practical prefetching techniques for multiprocessor file systems

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have thepotential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments withpractical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of those policies across a range of architectural parameters.     

Strip-oriented asynchronous prefetching for parallel disk systems

Sequential prefetching schemes are widely employed in storage servers to mask disk latency and improve system throughput. However, existing schemes cannot benefit parallel disk systems as expected due to the fact that they ignore the distinct internal characteristics of the parallel disk system, in particular, data striping. Moreover, their aggressive prefetching pattern suffers from premature evictions and prolonged request latencies. In this paper, we propose a strip-oriented asynchronous prefetching (SoAP) technique, which is dedicated to the parallel disk system. It settles the above-mentioned problems by providing multiple novel features, e.g., enhanced prediction accuracy, adaptive prefetching strength, physical data layout awareness, and timely prefetching. To validate SoAP, we implement a prototype by modifying the software redundant arrays of inexpensive disks (RAID) under Linux. Experimental results demonstrate that SoAP can consistently offer improved average response time and throughput to the parallel disk system under non-random workloads compared with STEP, SP, ASP, and Linux-like SEQPs.     

帮助线程预取质量的实时在线评价方法

针对传统静态枚举设置帮助线程控制参数值的繁杂耗时问题,提出了一种帮助线程预取质量的实时在线评价方法。首先,明确了帮助线程的预取服务质量（QoS）的目标;其次,分析了帮助线程预取性能评价的动态指标,对帮助线程预取QoS进行了建模分析;最后,提出一个帮助线程预取的动态自适应调节算法,算法根据程序的阶段行为变化和动态预取获益变化等信息来判断参数值的适用度以及是否需要进行反馈优化,从而实现对预取控制的自适应调节。实验结果表明,应用自适应预取评价算法之后,Mst热点模块的性能提升加速比为1.496,所提出的自适应预取评价方法能够根据程序的动态阶段行为对帮助线程控制参数值作出自适应控制和调节。     

A clustering-based prefetching scheme on a Web cache environment

Web prefetching is an attractive solution to reduce the network resources consumed by Web services as well as the access latencies perceived by Web users. Unlike Web caching, which exploits the temporal locality, Web prefetching utilizes the spatial locality of Web objects. Specifically, Web prefetching fetches objects that are likely to be accessed in the near future and stores them in advance. In this context, a sophisticated combination of these two techniques may cause significant improvements on the performance of the Web infrastructure. Considering that there have been several caching policies proposed in the past, the challenge is to extend them by using data mining techniques. In this paper, we present a clustering-based prefetching scheme where a graph-based clustering algorithm identifies clusters of “correlated” Web pages based on the users’ access patterns. This scheme can be integrated easily into a Web proxy server, improving its performance. Through a simulation environment, using a real data set, we show that the proposed integrated framework is robust and effective in improving the performance of the Web caching environment.     

User behavior modeling and content based speculative web page prefetching

This paper provides a transparent and speculative algorithm for content based web page prefetching. The algorithm relies on a profile based on the Internet browsing habits of the user. It aims at reducing the perceived latency when the user requests a document by clicking on a hyperlink. The proposed user profile relies on the frequency of occurrence for selected elements forming the web pages visited by the user. These frequencies are employed in a mechanism for the prediction of the user’s future actions. For the anticipation of an adjacent action, the anchored text around each of the outbound links is used and weights are assigned to these links. Some of the linked documents are then prefetched and stored in a local cache according to the assigned weights. The proposed algorithm was tested against three different prefetching algorithms and yield improved cache–hit rates given a moderate bandwidth overhead. Furthermore, the precision of accurately inferring the user’s preference is evaluated through the recall–precision curves. Statistical evaluation testifies that the achieved recall–precision performance improvement is significant.     

Automatic ARIMA time series modeling for adaptive I/O prefetching

Inadequate I/O performance remains a major challenge in using high-end computing systems effectively. To address this problem, we present TsModeler, an automatic time series modeling and prediction framework for adaptive I/O prefetching that uses ARIMA time series models to predict the temporal patterns of I/O requests. These online pattern analysis techniques and cutoff indicators for autocorrelation patterns enable multistep online predictions suitable for multiblock prefetching. This work also combines time series predictions with spatial Markov model predictions to determine when, what, and how many blocks to prefetch. Experimental results show reductions in execution time compared to the standard Linux file system across various hardware configurations.