Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

Thespis: Causally-consistent OLTP

, ,

DOI: http://dx.doi.org/10.15439/2021F34

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 261–269 ()

Full text

Abstract. Data Consistency defines the validity of a data set according to some set of rules. Causal consistency is the strongest level achievable over a distributed data set with high availability. Thespis is a middleware that leverages the Actor model to implement causal consistency, whilst abstracting complexities for 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.  By analysing standard transactional workloads, we show the applicability of the Thespis approach, and present the design of operations necessary to run transactional workloads in a distributed environment.

References

  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