The Effect of Skewed Data Access on Buffer Hits and Data Contention an a Data Sharing Environment.

Asit Dan, Daniel M. Dias, Philip S. Yu: The Effect of Skewed Data Access on Buffer Hits and Data Contention an a Data Sharing Environment. VLDB 1990: 419-431
  author    = {Asit Dan and
               Daniel M. Dias and
               Philip S. Yu},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {The Effect of Skewed Data Access on Buffer Hits and Data Contention
               an a Data Sharing Environment},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {419-431},
  ee        = {db/conf/vldb/DanDY90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP,}


In this paper we examine the effect of skewed access on the buffer hit ratio in a multi-system data sharing environment, where each computing node has access to shared data on disks, and has a local buffer of recently accessed granules. In the literature, the effect of skewness in data access on increased data contention has been examined, since with skew most accesses go to few data items. For the same reason, skewness can also increase the buffer hit probability, alleviating the effect on data contention. We examine the resultant effect on the transaction response time, which depends not only on the various system parameters but also on the Concurrency Control (CC) protocol. Furthermore, the CC protocol can give rise to rerun transactions that have different buffer hit probabilities. In a multi-system environment, when a data block gets updated by a system, copies of that block in other system's local buffers are invalidated. We develop a comprehensive analytical buffer model that captures all these effects and integrate it with a CC model to estimate the overall transaction response time. The model is validated through simulations. We find that higher skew does not necessarily lead to worse performance, and that with skewed access optimistic CC is more robust than pessimistic CC. Examining the buffer hit probability as a function of the buffer size, we findthat the effectiveness of additional buffer allocation can be broken down intomultiple regions that depend on the degree of skewness.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X


Matthew Bellew, Meichun Hsu, Va-On Tam: Update Propagation in Distributed Memory Hierarchy. ICDE 1990: 521-528 BibTeX
Ignacio R. Casas, Kenneth C. Sevcik: A Buffer Management Model For Use In Predicting Overall Database System Performance. ICDE 1989: 463-469 BibTeX
David R. Cheriton: The V Distributed System. Commun. ACM 31(3): 314-333(1988) BibTeX
Asit Dan, Donald F. Towsley, Walter H. Kohler: Modeling the Effects of Data and Resource Contention on the Performance of Optimistic Concurrency Control Protocols. ICDE 1988: 418-425 BibTeX
Asit Dan, Daniel M. Dias, Philip S. Yu: Database Buffer Model for the Data Sharing Environment. ICDE 1990: 538-544 BibTeX
Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152 BibTeX
Daniel M. Dias, Balakrishna R. Iyer, Philip S. Yu: Tradeoffs Between Coupling Small and Large Processors for Transaction Processing. IEEE Trans. Computers 37(3): 310-320(1988) BibTeX
Nancy P. Kronenberg, Henry M. Levy, William D. Strecker: VAXclusters: A Closely-Coupled Distributed System. ACM Trans. Comput. Syst. 4(2): 130-146(1986) BibTeX
Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985) BibTeX
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) BibTeX
Qing Yang, Laxmi N. Bhuyan, Bao-Chyn Liu: Analysis and Comparison of Cache Coherence Protocols for a Packet-Switched Multiprocessor. IEEE Trans. Computers 38(8): 1143-1153(1989) BibTeX
Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36 BibTeX

Referenced by

  1. Michael J. Franklin, Michael J. Carey, Miron Livny: Transactional Client-Server Cache Consistency: Alternatives and Performance. ACM Trans. Database Syst. 22(3): 315-363(1997)
  2. Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik: Disseminating Updates on Broadcast Disks. VLDB 1996: 354-365
  3. Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik: Prefetching from Broadcast Disks. ICDE 1996: 276-285
  4. Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik: Broadcast Disks: Data Management for Asymmetric Communications Environments. SIGMOD Conference 1995: 199-210
  5. Asit Dan, Daniel M. Dias, Philip S. Yu: Buffer Analysis for a Data Sharing Environment with Skewed Data Access. IEEE Trans. Knowl. Data Eng. 6(2): 331-337(1994)
  6. Erhard Rahm: Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Database Sharing Systems. ACM Trans. Database Syst. 18(2): 333-377(1993)
  7. Michael J. Franklin, Michael J. Carey, Miron Livny: Local Disk Caching for Client-Server Database Systems. VLDB 1993: 641-655
  8. Asit Dan, Philip S. Yu, Jen-Yao Chung: Database Access Characterization for Buffer Hit Prediction. ICDE 1993: 134-143
  9. Anupam Bhide, Asit Dan, Daniel M. Dias: A Simple Analysis of the LRU Buffer Policy and Its Relationship to Buffer Warm-Up Transient. ICDE 1993: 125-133
  10. Asit Dan, Philip S. Yu: Performance Analysis of Coherency Control Policies through Lock Retention. SIGMOD Conference 1992: 114-123
  11. Philip S. Yu, Asit Dan: Effect of System Dynamics on Coupling Architectures for Transaction Processing. ICDE 1992: 458-469
  12. Michael J. Carey, Michael J. Franklin, Miron Livny, Eugene J. Shekita: Data Caching Tradeoffs in Client-Server DBMS Architectures. SIGMOD Conference 1991: 357-366
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:44 2009