Performance analysis of recovery techniques

Reviewer: Jane B. Grimson

Database recovery is an area which has been largely neglected by researchers, yet there is unanimous agreement that recovery is a vital component of every DBMS. A number of recovery algorithms have been put forward. While there have been many attempts to compare the performance of, for example, concurrency control algorithms, there has been no parallel development for recovery. This is all the more surprising, as the author points out, given that experience has shown that the recovery component has a strong impact on overall system performance. Predicting the performance of recovery algorithms is a difficult task because it is almost impossible to analyze the recovery component in isolation from other components of the system. This paper develops a fairly simplistic model of DB recovery, with a view to identifying the influence of the most significant parameters on performance. The author classifies recovery algorithms according to a number of different characteristics. These include the timing of the propagation of updates to the database; for examples, algorithms using update-in-place entail immediate propagation, whereas under shadow-page algorithms, propagation only takes place when the next checkpoint is taken. Recovery algorithms are also classified according to whether or not pages can be written to disk prior to end-of-transaction. Similarly, algorithms will vary according to whether or not propagation of all pages involved in a transaction is tied to end-of-transaction. Finally, the taxonomy of recovery algorithms distinguishes between different checkpoint schemes by the events triggering the checkpoint generation, e.g., at end-of-transaction. Clearly, logging activity is an integral part of the recovery technique since it is the log information which provides the input to the recovery component. Having produced a classification scheme for recovery and logging techniques, the author identifies the principal performance measures for these techniques. These include overhead during normal DB processing, speed of recovery after failure, degree of reliability achieved by the algorithm, space requirements of the log file, and the software complexity of the logging and recovery components. The author points out that these measures are difficult to quantify and rank. For the purposes of his model, he takes a much more simplistic view, identifying the number of I/O operations caused by the logging and recovery activities. The main aim is to determine the maximum transaction rate beyond which the system becomes I/O bound due to recovery-related activity. A number of different models of various recovery and logging techniques, according to the classification scheme developed in the paper, are given and evaluated. From this a number of broad conclusions are drawn. Of particular interest is that for applications with a high degree of communality (i.e., there is a high probability of finding a page referenced by a transaction in the buffer); techniques which do not tie update propagation to end-of-transaction are superior. Also, where the meantime between failure is orders of magnitude greater than the time for restart (the normal situation), techniques without checkpoints can be ruled out. The results also show that page logging is more costly than entry logging (cf., the role of lock granularity in concurrency control). This is an interesting paper which addresses a difficult subject. The model is undoubtedly somewhat oversimplified, although the results obtained analytically and empirically, through a very small study, do support intuitive notions about the performance of recovery algorithms. It is to be hoped that this paper will stimulate research in the vital area of recovery in DBMS.