Analysis of recovery in a database system using a write-ahead log protocol

TLDR

The study investigates recovery time in a database system employing a Write‑Ahead Log protocol (e.g., ARIES) under a strict LRU buffer replacement policy. The authors develop analytical equations modeling log read, data I/O, log application, and undo processing times, first assuming a read/write ratio of one and uniform access, then extending the model to variable ratios and a hot‑set access pattern. They find that with uniform access, recovery is dominated by data I/O, but under extreme hot‑set conditions this dominance can disappear, and the derived equations enable analysis across arbitrary parameter settings.

Abstract

In this paper we examine the recovery time in a database system using a Write-Ahead Log protocol, such as ARIES [9], under the assumption that the buffer replacement policy is strict LRU. In particular, analytical equations for log read time, data I/O, log application, and undo processing time are presented. Our initial model assumes a read/write ratio of one, and a uniform access pattern. This is later generalized to include different read/write ratios, as well as a "hot set" model (i.e. x% of the accesses go to y% of the data). We show that in the uniform access model, recovery is dominated by data I/O costs, but under extreme hot-set conditions, this may no longer be true. Furthermore, since we derive anaytical equations, recovery can be analyzed for any set of parameter conditions not discussed here.