Lynx: a learning linux prefetching mechanism for SSD performance model
Authors:
- 18 August 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Traditional Linux prefetching algorithms were based on spatial locality of I/O workloads and performance model of hard disk drives. From the applicative point of view, current data-intensive applications I/O workloads are turning towards more random patterns while from the storage device perspective, flash based storage devices present a different performance model than HDDs. In this work, we present a new prefetching mechanism named Lynx. Lynx aims to adapt and/or complement the Linux read-ahead prefetching system for both SSD performance model and new applications needs. Lynx uses a simple machine learning system based on Markov chains. The learning phase detects I/O workload patterns and computes the transition probabilities between file pages. The prediction phase prefetchs predicted file pages with the resulting Markov statemachine. We have implemented our solution and integrated it into the Linux kernel. We experimented our solution using the TPCH benchmark. The results show that Lynx divides the number of page cache misses (major page faults) by 2 on average and thus reduces TPC-H queries execution time by 50% as compared to traditional Linux read-ahead.Keywords
This publication has 9 references indexed in Scilit:
- Visualizing Block IO WorkloadsACM Transactions on Storage, 2015
- Flashing in the Cloud2013
- Flashy prefetching for high-performance flash drives2012
- Sequential Prefetch Cache Sizing for Maximal Hit Rate2010
- On the design of a new Linux readahead frameworkACM SIGOPS Operating Systems Review, 2008
- STEP: Sequentiality and Thrashing Detection Based Prefetching to Improve Performance of Networked Storage Servers2007
- Implementation of informed prefetching and caching in Linux2002
- Prefetching using Markov predictorsACM SIGARCH Computer Architecture News, 1997
- Implementation and performance of integrated application-controlled file caching, prefetching, and disk schedulingACM Transactions on Computer Systems, 1996