Performance Modeling of Database Systems: a Survey
DOI:
https://doi.org/10.26636/jtit.2018.128918Keywords:
database systems, NoSQL data stores, performance evaluation, queueing networks, queueing Petri netsAbstract
This paper presents a systematic survey of the existing database system performance evaluation models based on the queueing theory. The continuous evolution of the methodologies developed is classified according to the mathematical modeling language used. This survey covers formal models – from queueing systems and queueing networks to queueing Petri nets. Some fundamentals of the queueing system theory are presented and queueing system models are classified according to service time distribution. The paper introduces queueing networks and considers several classification criteria applicable to such models. This survey distinguishes methodologies, which evaluate database performance at the integrated system level. Finally, queueing Petri nets are introduced, which combine modeling power of queueing networks and Petri nets. Two performance models within this formalism are investigated. We find that an insufficient amount of research effort is directed into the area of NoSQL data stores. Vast majority of models developed focus on traditional relational models. These models should be adapted to evaluate performance of non-relational data stores.
Downloads
References
[1] M. Nicola and M. Jarke, “Performance modeling of distributed and replicated databases”, IEEE Trans. on Knowl. and Data Engin., vol. 12, pp. 645–672, no. 4, 2000. DOI: https://doi.org/10.1109/69.868912
View in Google Scholar
[2] R. Osman and W. J. Knottenbelt, “Database system performance evaluation models: A survey”, Perform. Eval., vol. 69, pp. 471–493, no. 10, 2012. DOI: https://doi.org/10.1016/j.peva.2012.05.006
View in Google Scholar
[3] L. Kleinrock, Queueing Systems. Volume 1: Theory. New York: Wiley-Interscience, 1975 (ISBN: 9780471491101).
View in Google Scholar
[4] E. G. Coffmann, E. Gelenbe, and B. Plateau, “Optimization of the number of copies in a distributed data base”, IEEE Trans. on Software Engin., vol. SE-7, no. 1, pp. 78–84, 1981. DOI: https://doi.org/10.1109/TSE.1981.234510
View in Google Scholar
[5] F. Bacelli and E. Coffmann, “A database replication analysis using an M/M/m queue with service interruptions”, in Proc. of the 1982 ACM SIGMETRICS Conf. on Measur. and Model. of Comp. Syst. SIGMETRICS’82, Seattle, VA, USA, 1982, pp. 102–107. DOI: https://doi.org/10.1145/1035332.1035309
View in Google Scholar
[6] R. Nelson and R. Iyer, “Analysis of a replicated data base”, Perform. Eval., vol. 5, no. 3, pp. 133–148, 1985. DOI: https://doi.org/10.1016/0166-5316(85)90008-2
View in Google Scholar
[7] E. Arzuaga and D. S. Kaeli, “An M/G/1 queue model for multiple applications on storage area networks”, in Proc. for the 11th Worksh. on Comp. Architec. Eval. using Commercial Workloads CAECW-11, Salt Lake City, UT, USA, 2008, pp. 25–32.
View in Google Scholar
[8] M. Dellkrantz, M. Kihl, and A. Robertsson, “Performance modeling and analysis of a database server with write-heavy workload”, in Proc. 1st Eur. Conf. on Serv.-Orient. and Cloud Comput. ESOCC 2012, Bertinoro, Italy, 2012, pp. 184–191, 2012. DOI: https://doi.org/10.1007/978-3-642-33427-6_13
View in Google Scholar
[9] M. Kihl, P. Amani, A. Robertsson, G. Radu, M. Dellkrantz, and B. Aspernas, “Performance modeling of database servers in a telecommunication service management system”, in Proc. 7th Int. Conf. on Digit. Telecommun. ICDT 2012, Chamonix, France, 2012, pp. 123–129.
View in Google Scholar
[10] J. Mc Dermott and R. Mukkamala, “Performance analysis of transaction management algorithms for the SINTRA replicated architecture database systems”, in Proc. of the IFIP WG11.3 Working Conf. on Datab. Secur. VII, Lake Guntersville, Alabama, USA pp. 215–234, 1993.
View in Google Scholar
[11] B.-C. Jenq, B. C. Twichell, and T. W. Keller, “Locking performance in a shared nothing parallel database machine”, IEEE Trans. on Knowl. and Data Engin., vol. 1, no. 4, pp. 530–543, 1989. DOI: https://doi.org/10.1109/69.43427
View in Google Scholar
[12] H. Garcia-Molina, “Performance of the update algorithms for replicated data in a distributed database”, Ph.D. Thesis, Stanford University, Stanford, CA, USA, 1979.
View in Google Scholar
[13] H. Garcia-Molina and G. Wiederhold, “Read-only transactions in a distributed database”, ACM Trans. on Datab. Syst., vol. 7, no. 2, pp. 209–234, 1982. DOI: https://doi.org/10.1145/319702.319704
View in Google Scholar
[14] R. D. van der Mei, A. R. de Wilde, and S. Bhulai, “A method for approximating the variance of the sojourn times in star-shaped queueing networks”, Stochastic Models, vol. 24, no. 3, pp. 487–501, 2008. DOI: https://doi.org/10.1080/15326340802232327
View in Google Scholar
[15] D. Liang and S. Tripathi, “Performance analysis of long-lived transaction processing systems with rollbacks and aborts,” IEEE Trans. on Knowl. and Data Engin., vol. 8, no. 5, pp. 802–815, 1996. DOI: https://doi.org/10.1109/69.542031
View in Google Scholar
[16] M. J. Carey and M. Liviny, “Distributed concurrency control performance: A study of algorithms, distribution, and replication”, in Proc. of the 14th Int. Conf. on Very Large Datab. VLDB’88, Los Angeles, CA, USA, 1988, pp. 13–25.
View in Google Scholar
[17] B. Ciciani, D. M. Dias, and P. S. Yu, “Analysis of replication in distributed database systems”, IEEE Trans. on Knowl. and Data Engin., vol. 2, no. 2, pp. 247–261, 1990. DOI: https://doi.org/10.1109/69.54723
View in Google Scholar
[18] B. Ciciani, D. Dias, M., and P. S. Yu, “Analysis of concurrencycoherency control protocols for distributed transaction processing systems with regional locality”, IEEE Trans. on Knowl. and Data Engin., vol. 18, no. 10, pp. 899–914, 1992. DOI: https://doi.org/10.1109/32.163606
View in Google Scholar
[19] S. Banerjee, V. O. Li, and C. Wang, “Performance analysis of the send-on-demand: A distributed database concurrency control protocol for high-speed networks”, Comp. Commun., vol. 17, no. 3, pp. 189–204, 1994. DOI: https://doi.org/10.1016/0140-3664(94)90005-1
View in Google Scholar
[20] S. Y. Hwang, K. Lee, and Y. H. Chin, “Data replication in a distributed system: A performance study”, in Proc. 7th Int. Conf. Database and Expert Systems Applications, Zurich, Switzerland, 1996, pp. 708–717. DOI: https://doi.org/10.1007/BFb0034724
View in Google Scholar
[21] K. K. Leung, “An update algorithm for replicated signaling databases in wireless and advanced intelligent networks”, IEEE Trans. on Comp. – Special issue on mobile computing archive, vol. 46, no. 3, pp. 362–367, 1997. DOI: https://doi.org/10.1109/12.580431
View in Google Scholar
[22] E. Born, “Analytical performance modelling of lock management in distributed systems”, Distributed Systems Engineering, vol. 3, no. 1, pp. 68–76, 1996. DOI: https://doi.org/10.1088/0967-1846/3/1/008
View in Google Scholar
[23] D. A. Menasc´ e and M. N. Bennani, “Analytic performance models for single class and multiple class multithreaded software servers”, in Proc. 32nd Int. Computer Measur. Group Conf., Reno, NV, USA, 2006, pp. 475–482.
View in Google Scholar
[24] B. M. M. Gijsen, R. D. van der Mei, P. Engelberts, J. L. van den Berg, and K. M. C. van Wingerden, “Sojourn time approximations in queueing networks with feedback”, Perform. Eval., vol. 63, no. 8, pp. 743–758, 2006. DOI: https://doi.org/10.1016/j.peva.2005.08.002
View in Google Scholar
[25] A. Thomasian and K. Ryu, “A decomposition solution to the queueing network model of the centralized DBMS with static locking”, in Proc. of the Int. Conf. on Measur. and Model. of Comp. Syst. SIGMETRICS 1983, Minneapolis, MN, USA, 1983, pp. 82–92, 1983. DOI: https://doi.org/10.1145/800040.801397
View in Google Scholar
[26] R. J. T. Morris and W. S. Wong, “Performance analysis of locking and optimistic concurrency control algorithms”, Perform. Eval., vol. 5, no. 2, pp. 105–118, 1985. DOI: https://doi.org/10.1016/0166-5316(85)90043-4
View in Google Scholar
[27] P. S. Yu, S. Balsamo, and Y. Lee, “Dynamic transaction routing in distributed database systems”, IEEE Trans. on Software Engin., vol. 14, no. 9, pp. 1307–1318, 1988. DOI: https://doi.org/10.1109/32.6174
View in Google Scholar
[28] N. Tomov et al., “Analytical response time estimation in parallel relation database systems”, Parallel Computing, vol. 30, no. 2, pp. 249–283, 2004. DOI: https://doi.org/10.1016/j.parco.2003.11.003
View in Google Scholar
[29] R. Osman, I. Awan, and M. E. Woodward, “QuePED: Revisiting queueing networks for the performance evaluation of database designs”, Simulation Modelling Practice and Theory, vol. 19, no. 1, pp. 251–270, 2011. DOI: https://doi.org/10.1016/j.simpat.2010.06.010
View in Google Scholar
[30] R. Ramakrishnan and J. Gehrke, Database Management Systems. Boston: McGraw-Hill, 2002 (ISBN: 9780072465631).
View in Google Scholar
[31] F. Bause, “Queueing Petri nets – a formalism for the combined qualitative and quantitative analysis of systems”, in Proc. of 5th Int. Worksh on Petri Nets and Perf. Models, Toulouse, France, 1993.
View in Google Scholar
[32] S. Kounev, S. Spinner, and P. Meier, “Introduction to queueing Petri nets: Modeling formalism, tool support and case studies”, in Proc. of the 3rd ACM/SPEC Int. Conf. on Perform. Engin. ICPE 2012, Boston, MA, USA, 2012, pp. 9–18. DOI: https://doi.org/10.1145/2188286.2188290
View in Google Scholar
[33] R. Osman and P. Piazzolla, “Modeling replication in noSQL datastore”, in Proc. 11th Int. Conf. Quantitat. Eval. of Syst. QEST 2014, Florence, Italy, 2014, pp. 194–209. DOI: https://doi.org/10.1007/978-3-319-10696-0_16
View in Google Scholar
[34] R. Cattell, “Scalable SQL and noSQL data stores”, ACM SIGMOD Record, vol. 39, no. 4, pp. 12–27, 2010. DOI: https://doi.org/10.1145/1978915.1978919
View in Google Scholar
[35] K. Chodorov, MongoDB: The Definitive Guide, 2nd ed. Sebastopol, CA, USA: O’Reilly Media, Inc., 2013 (ISBN 9781449344795).
View in Google Scholar
[36] D. Coulden, R. Osman, and W. J. Knottenbelt, “Performance modelling of database contention using queueing Petri nets”, in Proc. of the 4th ACM/SPEC Int. Conf. on Perform. Engin. ICPE 2018, Prague, Czech Republic, 2013. DOI: https://doi.org/10.1145/2479871.2479919
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2018 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
