A Study On Disk Data Prefetching Based On Access Pattern Mining

The performance gap between processor units and storage systems has been widening. The optimization of data accessing is crucial for file system or even for the entire computer system. Among the various approaches, prefetching is a common and important one, which is not only used within CPU internal architecture to asynchronously fetch instructions and data, but also studied and applied massively in storage system. However, most of prefetching techniques somehow make prior assumption about the workload of targeted applications, which makes these techniques limited to specific use scenarios. In this dissertation, a novel prefech approach based on data mining is proposed in an attempt to adapt applications whose workload has wider range of character. This prefetch method has no assumption about application, and is only dependent on the association rules extracted by our proposed mining algorithm.Base on the review of some representative research and the implementation of prefetching algorithm in Linux kernel, we argue the idea of prefetching at a lower layer of the system. To incorporate the pattern recognizing technology, a prediction-oriented association rule and involving constrains are proposed. We focus on the time constrains and its effect on mining and rule-matching processes. With this specific association rules, we can express the access patterns, and derive rule mining and matching algorithms.In chapter 3, we discuss the design of mining algorithms, and explain the pruning made to constrain the searching space.To meet the real-time feature that a prefetcher requires, rules have to be matched quickly. we propose two algorithms to perform this task. The first one is simple and time-consuming, while the other incorporates bloom filter and achieves good real-time character. The experimental results show that the improved rule-matching algorithm can avoid almost any invalid inquiries to rule database, and almost each inquiry the algorithm makes can find corresponding rule in the database.Finally, we implement a simulation environment which is used to evaluate the performance of the proposed prefetching method. To obtain the disk access trace of arbitrary application, an in-kernel tracer is provided, by which we record traces when running OLTPBench that simulates an OLTP server, and a compilation of Linux kernel source code. With the two traces and a public available trace, we test the proposed algorithm. The results show that it effectively reduced system’s responding time and maintains good real-time performance.