Name
Title | ||
|---|---|---|
Analysis of the generalized clock buffer replacement scheme for database transaction processing |
Abstract | ||
|---|---|---|
The CLOCK algorithm is a popular buffer replacement algorithm because of its simplicity and its ability to approximate the performance of the Least Recently Used (LRU) replacement policy. The Generalized Clock (GCLOCK) buffer replacement policy uses a circular buffer and a weight associated with each page brought in buffer to decide on which page to replace. We develop an approximate analysis for the GCLOCK policy under the Independent Reference Model (IRM) that applies to many database transaction processing workloads. We validate the analysis for various workloads with data access skew. Comparison with simulations shows that in all cases examined the error is extremely small (less than 1%). To show the usefulness of the model we apply it to a Transaction Processing Council benchmark A (TPC-A) like workload. If knowledge of the different data partitions in this workload is assumed, the analysis shows that, with appropriate choice of weights, the performance of the GCLOCK algorithm can be better than the LRU policy. Performance very close to that for optimal (static) buffer allocation can be achieved by assigning sufficiently high weights, and can be implemented with a reasonably low overhead. Finally, we outline how the model can be extended to capture the effect of page invalidation in a multinode system. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1145/133057.133084 | SIGMETRICS |
Keywords | Field | DocType |
gclock algorithm,lru policy,gclock policy,popular buffer replacement algorithm,generalized clock buffer replacement,circular buffer,buffer allocation,database transaction processing,replacement policy,buffer replacement policy,approximate analysis,clock algorithm,reference model,data access,least recently used,transaction processing | Transaction processing,Workload,Computer science,Circular buffer,Parallel computing,Cache algorithms,Real-time computing,Write buffer,Skew,Data access,Adaptive replacement cache | Conference |
Volume | Issue | ISSN |
20 | 1 | 0163-5999 |
ISBN | Citations | PageRank |
0-89791-507-0 | 37 | 11.36 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor F. Nicola | 1 | 468 | 84.45 |
| Asit Dan | 2 | 2027 | 412.72 |
| D. M. Dias | 3 | 1585 | 586.25 |