Performance Modeling of Database Systems: a Survey

• Autorzy: Krajewska A.

Identyfikatory

DOI

10.26636/jtit.2018.128918

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

database systems; NoSQL data stores; performance evaluation; queueing networks; queueing Petri nets

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2018
• Tom: nr 4
• Strony: 37--45
• Opis fizyczny: Bibliogr. 36 poz., rys.

Twórcy

autor

Krajewska A.

• Research and Academic Computer Network (NASK), Kolska 12, 01-045 Warsaw, Poland

Bibliografia

• [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: 10.1109/69.868912).
• [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: 10.1016/j.peva.2012.05.006).
• [3] L. Kleinrock, Queueing Systems. Volume 1: Theory. New York: Wiley-Interscience, 1975 (ISBN: 9780471491101).
• [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: 10.1109/TSE.1981.234510).
• [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: 10.1145/1035332.1035309).
• [6] R. Nelson and R. Iyer, “Analysis of a replicated data base”, Perform. Eval., vol. 5, no. 3, pp. 133–148, 1985 (doi: 10.1016/0166-5316(85)90008-2).
• [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.
• [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: 10.1007/978-3-642-33427-6 13).
• [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.
• [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.
• [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: 10.1109/69.43427).
• [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 [Online]. Available: http://www.dtic.mil/dtic/tr/fulltext/u2/a075268.pdf
• [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: 10.1145/319702.319704).
• [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: 10.1080/15326340802232327).
• [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: 10.1109/69.542031).
• [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.
• [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: 10.1109/69.54723).
• [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: 10.1109/32.163606).
• [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: 10.1016/0140-3664(94)90005-1).
• [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: 10.1007/BFb0034724).
• [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: 10.1109/12.580431).
• [22] E. Born, “Analytical performance modelling of lock management in distributed systems”, Distributed Systems Engineering, vol. 3, no. 1, pp. 68–76, 1996 (doi: 10.1088/0967-1846/3/1/008).
• [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.
• [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: 10.1016/j.peva.2005.08.002).
• [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: 10.1145/800040.801397).
• [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: 10.1016/0166-5316(85)90043-4).
• [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: 10.1109/32.6174).
• [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: 10.1016/j.parco.2003.11.003).
• [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: 10.1016/j.simpat.2010.06.010).
• [30] R. Ramakrishnan and J. Gehrke, Database Management Systems. Boston: McGraw-Hill, 2002 (ISBN: 9780072465631).
• [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 (doi: 10.1109/PNPM.1993.393439).
• [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: 10.1145/2188286.2188290).
• [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: 10.1007/978-3-319-10696-0 16).
• [34] R. Cattell, “Scalable SQL and noSQL data stores”, ACM SIGMOD Record, vol. 39, no. 4, pp. 12–27, 2010 (doi: 10.1145/1978915.1978919).
• [35] K. Chodorov, MongoDB: The Definitive Guide, 2nd ed. Sebastopol, CA, USA: O’Reilly Media, Inc., 2013 (ISBN 9781449344795).
• [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: 10.1145/2479871.2479919).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).