Time-shift replacement algorithm for main memory performance optimization

Page replacement algorithms of main memory in modern operating systems are crucial in system performance. When memory is full, a page replacement algorithm exploits temporal locality and frequency of page references to evict the page that is least likely to be accessed in the near future. Subsequently, loading the majority of data directly from memory improves performance by reducing I/O waits of accessing slow storage. Research of replacement algorithms that maximizes hit ratio while incurring as less overhead as possible has been constantly studied. In this paper, we propose a time-shift least recently used (TSLRU) algorithm that converts frequency information of page references into temporal locality. Frequent accesses of a page are thus recognized and accumulated in terms of time. Moreover, pages being loaded into memory for the first time are not necessarily the most recently used pages. As a result, one-pass pages are evicted sooner in our algorithm than in traditional LRU algorithm. Our performance evaluations show that the TSLRU outperforms conventional page replacement algorithms on both artificial and real application traces. For example, hit ratio of TSLRU advances ARC by \(4.17\%\) and LRU by \(5.91\%\) on normal distributed workloads. Moreover, TSLRU outperforms ARC by over \(2\%\) on half of the application traces tested.     

一种基于闪存的缓冲区管理算法

在大多数以磁盘为存储系统的操作系统中,缓冲区管理算法只考虑到了数据访问的命中率。然而,闪存的写操作代价远远大于读操作代价。为了提高闪存性能,本文提出的O CFLRU（Optimal CFLRU）算法对于CFLRU（Clean First LRU）算法做了优化。该算法用一种页 块混合的数据结构来分别管理缓冲区中的干净页面和脏的数据页面聚簇。当缓冲区空间不够时,优先置换干净页面,再置换出脏的数据页聚簇,从而减少了写回的次数和随机写带来的擦除次数,提高了闪存的性能。     

一种对LRFU置换策略的自适应改进

数据库缓冲区页面置换算法对磁盘数据库的性能有着重要的影响,页面置换算法主要有基于访问时间的置换策略、基于访问次数的置换策略、两者结合的置换策略等。LRFU算法是一系列结合LRU和LFU置换策略的置换算法,很好地实现了两种置换策略的结合,但却没有给出一种在不同的应用场景中进行动态调整的机制。提出了一种对LRFU算法进行动态调整的方法,模拟测试发现改进的LRFU算法都不同程度地提高了缓冲区命中率。     

Window‐LRFU: a cache replacement policy subsumes the LRU and window‐LFU policies

Replacement algorithms have been widely used as key technologies for cache management in areas such as file systems or database management. A replacement algorithm determines which page to be evicted when the cache is full and a new page is referenced. Because replacement policies considering only recency or frequency such as LRU (Least Recently Used) and LFU (Least Frequently Used) do not perform well, replacement polices that take both recency and frequency into account have been intensively studied. As a classical replacement policy, LRFU (Least Recently/Frequently Used) policy subsumes the LRU and LFU policy. However, because LFU is not able to adapt to the change of page accessing pattern and it is hard to select a suitable λ for each certain trace, LRFU cannot always guarantee a good performance. In this paper, we propose a Window‐LRFU policy, to subsume the LRU and Window‐LFU policies. Experimental results show that the Window‐LRFU policy outperforms LRFU and has at least competitive performance than other classical algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Adaptive spatial information-theoretic clustering for image segmentation

The incorporation of spatial context into clustering algorithms for image segmentation has recently received a significant amount of attention. Many modified clustering algorithms have been proposed and proven to be effective for image segmentation. In this paper, we propose a different framework for incorporating spatial information with the aim of achieving robust and accurate segmentation in case of mixed noise without using experimentally set parameters based on the original robust information clustering (RIC) algorithm, called adaptive spatial information-theoretic clustering (ASIC) algorithm. The proposed objective function has a new dissimilarity measure, and the weighting factor for neighborhood effect is fully adaptive to the image content. It enhances the smoothness towards piecewise-homogeneous segmentation and reduces the edge blurring effect. Furthermore, a unique characteristic of the new information segmentation algorithm is that it has the capabilities to eliminate outliers at different stages of the ASIC algorithm. These result in improved segmentation result by identifying and relabeling the outliers in a relatively stronger noisy environment. Comprehensive experiments and a new information-theoretic proof are carried out to illustrate that our new algorithm can consistently improve the segmentation result while effectively handles the edge blurring effect. The experimental results with both synthetic and real images demonstrate that the proposed method is effective and robust to mixed noise and the algorithm outperforms other popular spatial clustering variants.     

Clustering data streams using grid-based synopsis

Continually advancing technology has made it feasible to capture data online for onward transmission as a steady flow of newly generated data points, termed as data stream. Continuity and unboundedness of data streams make storage of data and multiple scans of data an impractical proposition for the purpose of knowledge discovery. Need to learn structures from data in streaming environment has been a driving force for making clustering a popular technique for knowledge discovery from data streams. Continuous nature of streaming data makes it infeasible to look for point membership among the clusters discovered so far, necessitating employment of a synopsis structure to consolidate incoming data points. This synopsis is exploited for building clustering scheme to meet subsequent user demands. The proposed Exclusive and Complete Clustering (ExCC) algorithm captures non-overlapping clusters in data streams with mixed attributes, such that each point either belongs to some cluster or is an outlier/noise. The algorithm is robust, adaptive to changes in data distribution and detects succinct outliers on-the-fly. It deploys a fixed granularity grid structure as synopsis and performs clustering by coalescing dense regions in grid. Speed-based pruning is applied to synopsis prior to clustering to ensure currency of discovered clusters. Extensive experimentation demonstrates that the algorithm is robust, identifies succinct outliers on-the-fly and is adaptive to change in the data distribution. ExCC algorithm is further evaluated for performance and compared with other contemporary algorithms.     

一种闪存敏感的多级缓存管理方法

基于闪存的固态硬盘(solid state driver,简称SSD)已经广泛应用于各种移动设备、PC机和服务器.与磁盘相比,尽管SSD具有数据存取速度高、抗震、低功耗等优良特性,但SSD自身也存在读写不对称、价格昂贵等不利因素,这使得SSD 短期内不会完全取代磁盘.将SSD和磁盘组合构建混合系统,可以发挥不同的硬件特性,提升系统性能.基于 MLC 型 SSD 和 SLC 型 SSD 之间的特性差异,提出了一种闪存敏感的多级缓存管理策略——FAMC.FAMC将SSD用在内存和磁盘之间作扩展缓存,针对数据库系统、文件管理中数据访问的特点,有选择地将内存牺牲页缓存到不同类型的SSD.FAMC同时考虑写请求模式和负载类型对系统性能的影响,设计实现对SSD友好的数据管理策略.此外,FAMC基于不同的数据置换代价提出了适用于SSD的缓冲区管理算法.基于多级缓存存储系统对FAMC的性能进行了评测,实验结果表明,FAMC可以大幅度降低系统响应时间,减少磁盘I/O.     

基于ARC的闪存数据库缓冲区算法

闪存是一种纯电子设备,具备体积小、数据读取速度快、能耗低、抗震性强等优点,被用来部分替代机械硬盘从而提升存储系统的性能.但是,现有的缓冲区置换算法都是针对机械硬盘的物理特性进行设计和优化,因此有必要针对闪存的物理特性重新设计缓冲区置换算法.提出一种新的面向闪存数据库的缓冲区替换算法CF-ARC.算法设计了一种新的页替换机制,即在替换干净页或者脏页的时候考虑其访问频度的大小,优先将访问频度少的干净页替换出缓冲区,使得热页继续留在缓冲区提高命中率,从而获得更好的性能,通过对实验结果的对比分析发现CF-ARC在多数情况下具有比其它置换算法更高的性能.     

并行文件系统Lustre细粒度I/O性能优化

并行文件系统Lustre粗粒度I/O性能良好,细粒度I/O性能相对粗粒度I/O比较低下,因此优化细粒度I/O性能成为提高系统整体I/O性能的关键问题。在研究和分析了Lustre的I/O访问模式、细粒度I/O服务流程和页面替换算法等方面后,提出了细粒度优先（Fine Grained First,FGF）LRU算法。在OST端及Client端的页高速缓存中最大程度地保留细粒度I/O的页面,降低细粒度I/O引起的页面下沉速度,延长细粒度I/O页面在主存中的时间,进而减少对磁盘的访问次数,降低磁盘访问开销。通过对实验数据的对比和分析,验证了FGF-LRU算法的有效性。在不影响粗粒度I/O性能的情况下,提高了细粒度I/O性能,最终实现提高系统整体I/O性能。     

Tight bounds for prefetching and buffer management algorithms forparallel I/O systems

The I/O performance of applications in multiple-disk systems can be improved by overlapping disk accesses. This requires the use of appropriate prefetching and buffer management algorithms that ensure the most useful blocks are accessed and retained in the buffer. In this paper, we answer several fundamental questions on prefetching and buffer management for distributed-buffer parallel I/O systems. First, we derive and prove the optimality of an algorithm, P-min, that minimizes the number of parallel I/Os. Second, we analyze P-con, an algorithm that always matches its replacement decisions with those of the well-known demand-paged MIN algorithm. We show that P-con can become fully sequential in the worst case. Third, we investigate the behavior of on-line algorithms for multiple-disk prefetching and buffer management. We define and analyze P-Iru, a parallel version of the traditional LRU buffer management algorithm. Unexpectedly, we find that the competitive ratio of P-Iru is independent of the number of disks. Finally, we present the practical performance of these algorithms on randomly generated reference strings. These results confirm the conclusions derived from the analysis on worst case inputs     

The design and evaluation of a buffer algorithm for database machines

This paper reports on the design, development and evaluation of a buffer algorithm named RESBAL, which exploits parallelism in order to provide high query execution performance in relational database systems. The algorithm aims to provide both predictive and efficient data buffering by exploiting the use of advance knowledge of query reference behaviour. Designed to offer a high level of flexibility, RESBAL employs a multiple buffering strategy both on page fetch level and page replacement level in order to improve buffer performance. The evaluation of RESBAL has been carried out in a parallel database system environment based on a transputer architecture. The results of this performance assessment allow comparison to be made between different buffer algorithms, and demonstrate the feasibility and effectiveness of the RESBAL algorithm. © 1998 John Wiley & Sons, Ltd.     

A survey on enhanced subspace clustering

Subspace clustering finds sets of objects that are homogeneous in subspaces of high-dimensional datasets, and has been successfully applied in many domains. In recent years, a new breed of subspace clustering algorithms, which we denote as enhanced subspace clustering algorithms, have been proposed to (1) handle the increasing abundance and complexity of data and to (2) improve the clustering results. In this survey, we present these enhanced approaches to subspace clustering by discussing the problems they are solving, their cluster definitions and algorithms. Besides enhanced subspace clustering, we also present the basic subspace clustering and the related works in high-dimensional clustering.     

Ubase数据库系统缓冲管理器的实现

缓冲区技术是减少系统对外存访问的重要方法之一。文章分析了Ubase数据库系统缓冲管理器的基本功能,对常用页面替换算法的性能进行了比较,最终选择Love/Hate算法代替LRU算法实现了Ubase数据库系统的缓冲管理,降低了系统的开销,提高了Ubase数据库系统的性能。     

An optimal hierarchical clustering algorithm for gene expression data

Microarrays are used for measuring expression levels of thousands of genes simultaneously. Clustering algorithms are used on gene expression data to find co-regulated genes. An often used clustering strategy is the Pearson correlation coefficient based hierarchical clustering algorithm presented in [Proc. Nat. Acad. Sci. 95 (25) (1998) 14863-14868], which takes O(N³) time. We note that this run time can be reduced to O(N²) by applying known hierarchical clustering algorithms [Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 619-628] to this problem. In this paper, we present an algorithm which runs in O(NlogN) time using a geometrical reduction and show that it is optimal.     

Managing Multiuser Database Buffers Using Data Mining Techniques

In this paper, we propose a data-mining-based approach to public buffer management for a multiuser database system, where database buffers are organized into two areas – public and private. While the private buffer areas contain pages to be updated by particular users, the public buffer area contains pages shared among different users. Unlike traditional buffer management strategies where limited knowledge of user access patterns is used, the proposed approach discovers knowledge from page access sequences of user transactions and uses it to guide public buffer placement and replacement. A prefetch strategy is exploited based on the discovered page access knowledge. In practice, to make such a data-mining-based buffer management approach tractable, we present a soft variation to approximate our absolute best buffer replacement solution. The knowledge to be discovered and the discovery methods are discussed in the paper. The effectiveness of the proposed approach was investigated through a simulation study. The results indicate that with the help of the discovered knowledge, the public buffer hit ratio can be improved significantly, while the added computational complexity, compared to the achievement in buffer hit ratio, is less. In some situations, the time cost of the data-mining-based buffer management policy is even lower than that of the simplest buffer management policy.     

基于探测的自适应页面置换算法研究

页面置换算法是虚拟存储管理的重要组成部分,页面置换算法的优劣将直接影响系统的整体性能。本文在分析传统页面置换算法存在不足的基础上,介绍一种能够弥补传统页面置换算法存在不足的基于探测的自适应页面置换算法,同时分忻了该算法的性能,并且指出了进一步的研究方向。     

基于最大频繁项集的搜索引擎查询结果聚类算法

现有的搜索引擎查询结果聚类算法大多针对用户查询生成的网页摘要进行聚类,由于网页摘要篇幅较短,质量良莠不齐,聚类效果难以有较大的提高(比如后缀树算法,Lingo算法);而传统的基于全文的聚类算法运算复杂度较高,且难以生成高质量的类别标签,无法满足在线聚类的需求(比如KMeans算法)。该文提出一种基于全文最大频繁项集的网页在线聚类算法MFIC (Maximal Frequent Itemset Clustering)。算法首先基于全文挖掘最大频繁项集,然后依据网页集合之间最大频繁项集的共享关系进行聚类,最后依据类别包含的频繁项生成类别标签。实验结果表明MFIC算法降低了基于网页全文聚类的时间,聚类精度提高15%左右,且能生成可读性较好的类别标签。     

基于闪存的混合存储系统缓冲区管理算法

由于基于闪存的混合存储系统充分利用了闪存的高速随机读和磁盘的快速顺序写的特性,近年来已经成为了数据库管理系统的二级存储层的高效存储模式,但其I/O访问开销是一个继续提高存储性能的瓶颈.为了降低混合存储系统的I/O访问开销,提出了一种自适应缓冲区管理算法DLSB.该算法根据数据页的逻辑代价和物理代价进行自适应的数据域选择;并在选择的数据域中,比较闪存队列和磁盘队列容量的实际值与理想值来确定数据页的置换,达到了提高I/O访问效率的目的.实验结果表明,该算法有效且可行,显著降低了混合存储系统的I/O访问开销.     

DBMS缓冲区管理器设计的关键技术*

OSCAR对象-关系数据库管理系统的缓冲区管理器负责在必要时将页面从磁盘取到主存的软件层。由于主存不可能容纳磁盘上所有的页面,缓冲区管理器需要考虑到页面替换和回写。主要介绍在设计OSCAR缓冲区管理器中使用的关键技术,包括异步I/O、页面读写校验、页面替换策略及动态调整缓冲区物理内存技术。