Thespis: Causally-consistent OLTP

Camilleri, Carl; Vella, Joseph G.; Nezval, Vitezslav

doi:10.15439/2021F34

Artykuł - szczegóły

Tytuł artykułu

Thespis: Causally-consistent OLTP

Autorzy

Camilleri Carl , Vella Joseph G. , Nezval Vitezslav

Wybrane pełne teksty z tego czasopisma

http://annals-csis.org

Identyfikatory

DOI

10.15439/2021F34

Warianty tytułu

Konferencja

Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)

Języki publikacji

Abstrakty

Data Consistency defines the validity of a data set according to some set of rules, and different levels of data consistency have been proposed. Causal consistency is the strongest type of consistency possible when data is stored in multiple locations, and fault tolerance is desired. Thespis is a middleware that leverages the Actor model to implement causal consistency over a DBMS, whilst abstracting complexities for application developers behind a REST interface. ThespisTRX is an extension that provides read-only transaction capabilities, whilst ThespisDIIP is another extension that handles distributed integrity invariant preservation. Here, we analyse standard transactional workloads on the relational data model, which is richer than the key-value data model supported by the Thespis interface. We show the applicability of the Thespis approach for this data model by designing new operations for the Thespis interface, which ensure correct execution of such workloads in a convergent, causally consistent distributed environment.

Słowa kluczowe

data mining data models middleware relational databases transaction processing

wydobywanie danych modele danych oprogramowanie pośredniczące relacyjne bazy danych przetwarzanie transakcji

Wydawca

Polskie Towarzystwo Informatyczne

Czasopismo

Annals of Computer Science and Information Systems

Rocznik

2021

Tom

Vol. 25

Strony

261--269

Opis fizyczny

Bibliogr. 56 poz., tab., rys.

Twórcy

autor

Camilleri Carl

carl.camilleri.04@um.edu.mt

Computer Information Systems University of Malta, Malta

autor

Vella Joseph G.

joseph.g.vella@um.edu.mt

Computer Information Systems University of Malta, Malta

autor

Nezval Vitezslav

vitezslav.nezval@um.edu.mt

Computer Information Systems University of Malta, Malta

Bibliografia

1. E. A. Brewer, “Towards robust distributed systems,” in Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, ser. PODC ’00, vol. 7, 2000. http://dx.doi.org/10.1145/343477.343502. ISBN 1581131836
2. S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,” ACM SIGACT News, vol. 33, no. 2, pp. 51–59, 2002. http://dx.doi.org/10.1145/564585.564601
3. M. P. Herlihy and J. M. Wing, “Linearizability: A correctness condition for concurrent objects,” ACM Transactions on Programming Languages and Systems, vol. 12, no. 3, pp. 463–492, July 1990. http://dx.doi.org/10.1145/78969.78972
4. W. Vogels, “Eventually consistent,” Communications of the ACM, vol. 52, no. 1, pp. 40–44, January 2009. http://dx.doi.org/10.1145/1435417.1435432
5. L. Lamport, “The part-time parliament,” ACM Transactions on Computer Systems, vol. 16, no. 2, pp. 133–169, May 1998. doi: 10.1145/279227.279229
6. M. M. Elbushra and J. Lindström, “Eventual consistent databases: State of the art,” Open Journal of Databases (OJDB), vol. 1, no. 1, pp. 26–41, January 2014.
7. M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. W. Hutto, “Causal memory: Definitions, implementation, and programming,” Distributed Computing, vol. 9, no. 1, pp. 37–49, 1995. http://dx.doi.org/10.1007/bf01784241
8. P. Mahajan, L. Alvisi, and M. Dahlin, “Consistency, availability, and convergence,” University of Texas at Austin Tech Report, vol. 11, 2011.
9. P. Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica, “Bolt-on causal consistency,” in Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 2013. doi: 10.1145/2463676.2465279 pp. 761–772.
10. K. Spirovska, D. Didona, and W. Zwaenepoel, “Optimistic causal consistency for geo-replicated key-value stores,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 3, pp. 527–542, March 2021. http://dx.doi.org/10.1109/tpds.2020.3026778
11. S. Braun, A. Bieniusa, and F. Elberzhager, “Advanced domain-driven design for consistency in distributed data-intensive systems,” in Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data. ACM, April 2021. http://dx.doi.org/10.1145/3447865.3457969 pp. 1–12.
12. L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, vol. 21, no. 7, pp. 558–565, 1978. http://dx.doi.org/10.1145/359545.359563
13. J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild et al., “Spanner: Google’s globally distributed database,” ACM Transactions on Computer Systems (TOCS), vol. 31, no. 3, p. 8, August 2013. http://dx.doi.org/10.1145/2491245
14. D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser, “Managing update conflicts in Bayou, a weakly connected replicated storage system,” ACM SIGOPS Operating Systems Review, vol. 29, no. 5, pp. 172–182, December 1995. http://dx.doi.org/10.1145/224057.224070
15. A. Lakshman and P. Malik, “Cassandra: a decentralized structured storage system,” ACM SIGOPS Operating Systems Review, vol. 44, no. 2, pp. 35–40, April 2010. http://dx.doi.org/10.1145/1773912.1773922
16. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen, “Don’t settle for eventual: scalable causal consistency for wide-area storage with cops,” in Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, ser. SOSP ’11. Association for Computing Machinery (ACM), 2011. http://dx.doi.org/10.1145/2043556.2043593. ISBN 9781450309776 pp. 401–416.
17. J. Du, C. Iorgulescu, A. Roy, and W. Zwaenepoel, “Gentlerain: Cheap and scalable causal consistency with physical clocks,” in Proceedings of the ACM Symposium on Cloud Computing. ACM, November 2014. http://dx.doi.org/10.1145/2670979.2670983 pp. 1–13.
18. K. Spirovska, D. Didona, and W. Zwaenepoel, “Wren: Nonblocking reads in a partitioned transactional causally consistent data store,” in 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, June 2018. http://dx.doi.org/10.1109/dsn.2018.00014 pp. 1–12.
19. S. S. Kulkarni, M. Demirbas, D. Madappa, B. Avva, and M. Leone, “Logical physical clocks,” in Lecture Notes in Computer Science, M. K. Aguilera, L. Querzoni, and M. Shapiro, Eds. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-14472-6_2 pp. 17–32.
20. S. Elnaffar, P. Martin, and R. Horman, “Automatically classifying database workloads,” in Proceedings of the eleventh international conference on Information and knowledge management - CIKM '02. ACM Press, 2002. http://dx.doi.org/10.1145/584792.584898 pp. 622–624.
21. L. Li, G. Wu, G. Wang, and Y. Yuan, “Accelerating hybrid transactional/analytical processing using consistent dual-snapshot,” in International Conference on Database Systems for Advanced Applications. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-18576-3_4 pp. 52–69.
22. M. Bach and A. Werner, “Hybrid column/row-oriented DBMS,” in Advances in Intelligent Systems and Computing. Springer International Publishing, September 2015, pp. 697–707. http://dx.doi.org/10.1007/978-3-319-23437-3_60
23. N. Poggi, D. Carrera, R. Gavalda, E. Ayguadé, and J. Torres, “A methodology for the evaluation of high response time on e-commerce users and sales,” Information Systems Frontiers, vol. 16, no. 5, pp. 867–885, October 2014. http://dx.doi.org/10.1007/s10796-012-9387-4
24. F. Raab, “TPC-C - the standard benchmark for online transaction processing (OLTP),” in The Benchmark Handbook for Database and Transaction Systems (2nd Edition), 1993.
25. P. Tözün, I. Pandis, C. Kaynak, D. Jevdjic, and A. Ailamaki, “From A to E: analyzing TPC’s OLTP benchmarks: the obsolete, the ubiquitous, the unexplored,” in Proceedings of the 16th International Conference on Extending Database Technology - EDBT '13, 2013. http://dx.doi.org/10.1145/2452376.2452380 pp. 17–28.
26. S. T. Leutenegger and D. Dias, “A modeling study of the TPC-c benchmark,” ACM SIGMOD Record, vol. 22, no. 2, pp. 22–31, June 1993. http://dx.doi.org/10.1145/170036.170042
27. T. P. P. C. TPC, “Tpc benchmark e,” 2010.
28. S. Chen, A. Ailamaki, M. Athanassoulis, P. B. Gibbons, R. Johnson, I. Pandis, and R. Stoica, “TPC-E vs. TPC-C: Characterizing the new TPC-E benchmark via an I/O comparison study,” ACM SIGMOD Record, vol. 39, no. 3, pp. 5–10, February 2011. http://dx.doi.org/10.1145/1942776.1942778
29. M. J. Cahill, U. Röhm, and A. D. Fekete, “Serializable isolation for snapshot databases,” ACM Transactions on Database Systems, vol. 34, no. 4, pp. 1–42, December 2009. http://dx.doi.org/10.1145/1620585.1620587
30. C. Camilleri, J. G. Vella, and V. Nezval, “Thespis: Actor-Based Causal Consistency,” in Database and Expert Systems Applications (DEXA), 2017. 28th International Workshop on Big Data Management in Cloud Systems. IEEE, August 2017. http://dx.doi.org/10.1109/dexa.2017.25 pp. 42–46.
31. C. Hewitt, P. Bishop, and R. Steiger, “A universal modular actor formalism for artificial intelligence,” in Proceedings of the 3rd international joint conference on Artificial intelligence. Morgan Kaufmann Publishers Inc., 1973, pp. 235–245.
32. G. Agha, Actors: A Model of Concurrent Computation in Distributed Systems. The MIT Press, 1986. http://dx.doi.org/10.7551/mitpress/1086.001.0001
33. G. Young, “CQRS documents by Greg Young,” 2010. [Online]. Available: https://github.com/keyvanakbary/cqrs-documents
34. B. Meyer, Eiffel: The Language. Prentice-Hall, Inc., December 1992. ISBN 0-13-247925-7. http://dx.doi.org/10.1016/0950-5849(92)90131-8
35. M. Fowler, “Event sourcing,” December 2005. [Online]. Available: https://martinfowler.com/eaaDev/EventSourcing.html
36. D. Abadi, “Consistency tradeoffs in modern distributed database system design: CAP is only part of the story,” Computer, vol. 45, no. 2, pp. 37–42, February 2012. http://dx.doi.org/10.1109/mc.2012.33
37. C. Camilleri, J. G. Vella, and V. Nezval, “ThespisTRX: Causally-consistent read transactions,” International Journal of Information Technology and Web Engineering (IJITWE), vol. 15, no. 1, pp. 1–16, January 2020. http://dx.doi.org/10.4018/ijitwe.2020010101
38. V. Balegas, S. Duarte, C. Ferreira, R. Rodrigues, and N. Preguiça, “IPA: Invariant-preserving applications for weakly-consistent replicated databases,” Proceedings of the VLDB Endowment, vol. 12, no. 4, pp. 404–418, December 2018. http://dx.doi.org/10.14778/3297753.3297760
39. C. Camilleri, J. G. Vella, and V. Nezval, “ThespisDIIP: Distributed integrity invariant preservation,” in International Conference on Database and Expert Systems Applications. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-99133-7_2 pp. 21–37.
40. D. Barbará-Millá and H. Garcia-Molina, “The demarcation protocol: A technique for maintaining constraints in distributed database systems,” The VLDB Journal - The International Journal on Very Large Data Bases, vol. 3, no. 3, pp. 325–353, July 1994. http://dx.doi.org/10.1007/bf01232643
41. N. Krishnakumar and A. J. Bernstein, “High throughput escrow algorithms for replicated databases,” ser. VLDB ’92. Morgan Kaufmann Publishers Inc., 1992. ISBN 1558601511 pp. 175–186.
42. P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica, “Feral concurrency control: An empirical investigation of modern application integrity,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, May 2015. http://dx.doi.org/10.1145/2723372.2737784 pp. 1327–1342.
43. P. Bailis, A. Fekete, M. J. Franklin, and A. Ghodsi, “Coordination avoidance in database systems,” Proceedings of the VLDB Endowment, vol. 8, no. 3, pp. 185–196, 2014. http://dx.doi.org/10.14778/2735508.2735509
44. N. Soparkar and A. Silberschatz, “Data-valued partitioning and virtual messages,” in Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '90. ACM Press, 1990. http://dx.doi.org/10.1145/298514.298587 pp. 357–367.
45. B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, “Benchmarking cloud serving systems with ycsb,” in Proceedings of the 1st ACM symposium on Cloud computing - SoCC '10. ACM Press, 2010. http://dx.doi.org/10.1145/1807128.1807152 pp. 143–154.
46. K. Rahmani, K. Nagar, B. Delaware, and S. Jagannathan, “CLOTHO: directed test generation for weakly consistent database systems,” Proceedings of the ACM on Programming Languages, vol. 3, no. OOPSLA, pp. 1–28, October 2019. http://dx.doi.org/10.1145/3360543
47. A. Chikhaoui, K. Boukhalfa, and J. Boukhobza, “A cost model for hybrid storage systems in a cloud federations,” in Proceedings of the 2018 Federated Conference on Computer Science and Information Systems (FedCSIS), ser. Annals of Computer Science and Information Systems, M. Ganzha, L. Maciaszek, and M. Paprzycki, Eds., vol. 15. IEEE, September 2018. http://dx.doi.org/10.15439/2018F237 pp. 1025–1034.
48. V. Balegas, S. Duarte, C. Ferreira, R. Rodrigues, N. Preguiça, M. Najafzadeh, and M. Shapiro, “Putting consistency back into eventual consistency,” in Proceedings of the Tenth European Conference on Computer Systems, April 2015. http://dx.doi.org/10.1145/2741948.2741972 pp. 1–16.
49. M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski, “A comprehensive study of convergent and commutative replicated data types,” Ph.D. dissertation, Inria–Centre Paris-Rocquencourt; INRIA, 2011. [Online]. Available: https://hal.inria.fr/inria-00555588
50. P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica, “Highly available transactions: Virtues and limitations,” Proceedings of the VLDB Endowment, vol. 7, no. 3, pp. 181–192, November 2013. http://dx.doi.org/10.14778/2732232.2732237
51. C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues, “Making geo-replicated systems fast as possible, consistent when necessary,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI’12), 2012. ISBN 9781931971966 pp. 265–278.
52. A. Bouajjani, C. Enea, M. Mukund, G. Shenoy, and S. Suresh, “Formalizing and checking multilevel consistency,” in International Conference on Verification, Model Checking, and Abstract Interpretation. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-39322-9_18 pp. 379–400.
53. R. Elmasri and S. B. Navathe, Fundamentals of Database Systems, 7th ed. Pearson, June 2015. ISBN 0133970779
54. M. Milano and A. C. Myers, “Mixt: A language for mixing consistency in geodistributed transactions,” in Proceedings of the 39th ACM SIG-PLAN Conference on Programming Language Design and Implementation, vol. 53, no. 4. ACM, June 2018. http://dx.doi.org/10.1145/3192366.3192375 pp. 226–241.
55. B. Holt, J. Bornholt, I. Zhang, D. Ports, M. Oskin, and L. Ceze, “Disciplined inconsistency with consistency types,” in Proceedings of the Seventh ACM Symposium on Cloud Computing, October 2016. http://dx.doi.org/10.1145/2987550.2987559 pp. 279–293.
56. M. Köhler, N. Eskandani, P. Weisenburger, A. Margara, and G. Salvaneschi, “Rethinking safe consistency in distributed object-oriented programming,” Proceedings of the ACM on Programming Languages, vol. 4, no. OOPSLA, pp. 1–30, November 2020. http://dx.doi.org/10.1145/3428256

Uwagi

Track 2: Computer Science and Systems

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-19f02c6a-b53d-479e-bd35-6e5a4174cfb9