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

@inproceedings{DBLP:conf/vldb/DanDY90,
  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, http://dblp.uni-trier.de}
}

Abstract

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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

References

[BELL90]: Matthew Bellew, Meichun Hsu, Va-On Tam: Update Propagation in Distributed Memory Hierarchy. ICDE 1990: 521-528
[CASA89]: Ignacio R. Casas, Kenneth C. Sevcik: A Buffer Management Model For Use In Predicting Overall Database System Performance. ICDE 1989: 463-469
[CHER88]: David R. Cheriton: The V Distributed System. Commun. ACM 31(3): 314-333(1988)
[DAN88]: 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
[DAN89]: ...
[DAN90a]: Asit Dan, Daniel M. Dias, Philip S. Yu: Database Buffer Model for the Data Sharing Environment. ICDE 1990: 538-544
[DAN90b]: Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152
[DIAS88]: 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)
[DUBO82]: ...
[KRON86]: Nancy P. Kronenberg, Henry M. Levy, William D. Strecker: VAXclusters: A Closely-Coupled Distributed System. ACM Trans. Comput. Syst. 4(2): 130-146(1986)
[GREE87]: ...
[STRI82]: ...
[TAY85]: Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985)
[TENG84]: James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984)
[YANG89]: 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)
[YU87]: ...
[YU90a]: ...
[YU90b]: Philip S. Yu, Daniel M. Dias: Concurrency Control Using Locking with Deferred Blocking. ICDE 1990: 30-36
[YU90c]: ...