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.

REFERENCES

• 1: Belady, L. A., "A Study of Replacement Algorithms for a Virtual Storage Computer", IBM Systems Journal, Vol.5, No.2, 1966, pp. 78-101.
• 2: Richard W. Carr , John L. Hennessy, WSCLOCK—a simple and effective algorithm for virtual memory management, Proceedings of the eighth ACM symposium on Operating systems principles, p.87-95, December 14-16, 1981, Pacific Grove, California, United States
• 3: Ignacio R. Casas , Kenneth C. Sevcik, A Buffer Management Model For Use In Predicting Overall Database System Performance, Proceedings of the Fifth International Conference on Data Engineering, p.463-469, February 06-10, 1989
• 4: Chou, H. T., and D. J. Dewitt, "An Evaluation of Buffer Management Strategies for Relational Database Systems", 11th International Conference on Very Large Databases, Stockholm, Sweden, 1985, pp. 127-141.
• 5: Corbato, F. J., "A Paging Experiment with the Multics System", MIT Pro3ect MAC Report MAC-M-384, May 1968.
• 6: Asit Dan , Don Towsley, An approximate analysis of the LRU and FIFO buffer replacement schemes, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.143-152, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 7: Asit Dan , Daniel M. Dias , Philip S. Yu, The effect of skewed data access on buffer hits and data contention in a data sharing environment, Proceedings of the sixteenth international conference on Very large databases, p.418-431, September 1990, Brisbane, Australia
• 8: Asit Dan , Daniel M. Dias , Philip S. Yu, Analytical modelling of a hierarchical buffer for a data sharing environment, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.156-167, May 21-24, 1991, San Diego, California, United States
• 9: Dan, A., and P. S. Yu, "Performance Comparisons of Buffer Coherency Policies," 11th International Con- }erence on Distributed Computing Systems, Arlington, TX, May 1991.
• 10: Dan, A., P. S. Yu and J. Y. Chung, "Characterization of Database Access Skew of a Transaction Processing Environment", IBM Research Report RC 17436, Yorktown Heights, NY, Sept. 1991.
• 11: Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
• 12: J. P. Kearns , S. DeFazio, Diversity in database reference behavior, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.11-19, May 1989
• 13: King, W. F., "Analysis of Paging Algorithms", Proc. IFIP Congress, Ljublanjana, Yugoslavia, Aug. 1971, pp. 485-490.
• 14: Nicola, V. F., A. Dan, and D. M. Dins, "Analysis of the Generahzed Clock Buffer Replacement Scheme for Database Transaction Processing", IBM Research Report RC 17225, Yorktown Heights, NY, Sept. 1991.
• 15: Reiter, A., "A Study of Buffer Management Pohcies for Data Management Systems", Technical Summary Report 1619, Mathematics Research Center, Univ. of Wisconsin, Madison, March 1976.
• 16: Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986 [doi>10.1145/7239.7336]
• 17: Alan Jay Smith, Sequentiality and prefetching in database systems, ACM Transactions on Database Systems (TODS), v.3 n.3, p.223-247, Sept. 1978 [doi>10.1145/320263.320276]
• 18: "TPC Benchmark A Standard Specification", Transaction Processing Council, 1989.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Performance, Verification