On the road to recovery
Authors:
Open Access
- 18 April 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGOPS Operating Systems Review
- Vol. 40 (4) , 235-248
Abstract
Restoring data operations after a disaster is a daunting task: how should recovery be performed to minimize data loss and application downtime? Administrators are under considerable pressure to recover quickly, so they lack time to make good scheduling decisions. They schedule recovery based on rules of thumb, or on pre-determined orders that might not be best for the failure occurrence. With multiple workloads and recovery techniques, the number of possibilities is large, so the decision process is not trivial.This paper makes several contributions to the area of data recovery scheduling. First, we formalize the description of potential recovery processes by defining recovery graphs. Recovery graphs explicitly capture alternative approaches for recovering workloads, including their recovery tasks, operational states, timing information and precedence relationships. Second, we formulate the data recovery scheduling problem as an optimization problem, where the goal is to find the schedule that minimizes the financial penalties due to downtime, data loss and vulnerability to subsequent failures. Third, we present several methods for finding optimal or near-optimal solutions, including priority-based, randomized and genetic algorithm-guided ad hoc heuristics. We quantitatively evaluate these methods using realistic storage system designs and workloads, and compare the quality of the algorithms' solutions to optimal solutions provided by a math programming formulation and to the solutions from a simple heuristic that emulates the choices made by human administrators. We find that our heuristics' solutions improve on the administrator heuristic's solutions, often approaching or achieving optimality.Keywords
This publication has 15 references indexed in Scilit:
- Challenges in managing dependable data systemsACM SIGMETRICS Performance Evaluation Review, 2006
- Going with the FlowQueue, 2006
- Value-maximizing deadline scheduling and its application to animation rendering2005
- A self‐adapting genetic algorithm for project scheduling under resource constraintsNaval Research Logistics (NRL), 2002
- Survivable information storage systemsComputer, 2000
- Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis1999
- Resource-constrained project scheduling: Notation, classification, models, and methodsEuropean Journal of Operational Research, 1999
- A genetic algorithm for multiprocessor schedulingIEEE Transactions on Parallel and Distributed Systems, 1994
- Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relationsIEEE Transactions on Software Engineering, 1993
- Scheduling Tasks with Resource Requirements in Hard Real-Time SystemsIEEE Transactions on Software Engineering, 1987