User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Transparent Speculation in Geo-Replicated Transactional Data Stores

Primary tabs

download
  • Open access
  • PDF
  • 869.57 K
Li, Zhongmiao [UCL] Van Roy, Peter [UCL] Romano, Paolo

Thiswork presents Speculative Transaction Replication (STR), a protocol that exploits transparent speculation techniques to enhance performance of geo-distributed, partially replicated transactional data stores. In addition, we define a new consistency model, Speculative Snapshot Isolation (SPSI), that extends the semantics of Snapshot Isolation (SI) to shelter applications from the subtle anomalies that can arise from using speculative transaction processing. SPSI extends SI in an intuitive and rigorous fashion by specifying desirable atomicity and isolation guarantees that must hold when using speculative execution. STR provides a form of speculation that is fully transparent for programmers (it does not expose the effects of misspeculations to clients). Since the speculation techniques employed by STR satisfy SPSI, they can be leveraged by application programs in a transparent way, without requiring any source-code modification to applications designed to operate using SI. STR combines two key techniques: speculative reads, which allow transactions to observe pre-committed versions, which can reduce the ‘effective duration’ of pre-commit locks and enhance throughput; Precise Clocks, a novel timestamping mechanism that uses per-item timestamps with physical clocks, which together greatly enhance the probability of successful speculation. We assess STR’s performance on up to nine geo-distributed Amazon EC2 data centers, using both synthetic benchmarks as well as realistic benchmarks (TPC-C and RUBiS). Our evaluation shows that STR achieves throughput gains up to 11× and latency reduction up to 10×, in workloads characterized by low inter-data center contention. Furthermore, thanks to a self-tuning mechanism that dynamically and transparently enables and disables speculation, STR offers robust performance even when faced with unfavourable workloads that suffer from high misspeculation rates.

Document type Document de travail (Working Paper)
Access type Accès libre
Publication date 2018
Language Anglais
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. P. T. Wojciechowski, T. Kobus, and M. Kokocinski. State-machine and deferred-update replication: Analysis and comparison. IEEE TPDS, PP(99):1--1, 2016.
  2. G. Weikum and G. Vossen. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Elsevier, 2001.
  3. A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: fast distributed transactions for partitioned database systems. In SIGMOD '12, pages 1--12. ACM, 2012.
  4. A. Thomson and D. J. Abadi. The case for determinism in database systems. PVLDB '10, 3(1--2):70--80, 2010.
  5. 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. SOSP '95, pages 172--182, New York, NY, USA, 1995. ACM.
  6. R. S. Sutton and A. G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1st edition, 1998.
  7. Sovran Yair, Power Russell, Aguilera Marcos K., Li Jinyang, Transactional storage for geo-replicated systems, 10.1145/2043556.2043592
  8. J. Shute, R. Vingralek, B. Samwel, B. Handy, C. Whipkey, E. Rollins, M. Oancea, K. Littlefield, D. Menestrina, S. Ellner, et al. F1: A distributed sql database that scales. PVLDB '13, 6(11):1068--1079, 2013.
  9. K. Ren, A. Thomson, and D. J. Abadi. An evaluation of the advantages and disadvantages of deterministic database systems. PVLDB '14, 2014.
  10. Peluso Sebastiano, Ruivo Pedro, Romano Paolo, Quaglia Francesco, Rodrigues Luis, When Scalability Meets Consistency: Genuine Multiversion Update-Serializable Partial Data Replication, 10.1109/icdcs.2012.55
  11. Peluso Sebastiano, Romano Paolo, Quaglia Francesco, SCORe: A Scalable One-Copy Serializable Partial Replication Protocol, Lecture Notes in Computer Science (2012) ISBN:9783642351693 p.456-475, 10.1007/978-3-642-35170-9_23
  12. S. Peluso, J. Fernandes, P. Romano, F. Quaglia, and L. Rodrigues. SPECULA: Speculative replication of software transactional memory. In SRDS '12, pages 91--100, 2012.
  13. A. Pavlo, E. P. Jones, and S. Zdonik. On predictive modeling for optimizing transaction execution in parallel oltp systems. PVLDB '11, 5(2):85--96, 2011.
  14. Pang Gene, Kraska Tim, Franklin Michael J., Fekete Alan, PLANET : making progress with commit processing in unpredictable environments, 10.1145/2588555.2588558
  15. Palmieri Roberto, Quaglia Francesco, Romano Paolo, Carvalho Nuno, Evaluating database-oriented replication schemes in Software Transactional Memory systems, 10.1109/ipdpsw.2010.5470866
  16. R. Palmieri, F. Quaglia, and P. Romano. Aggro: Boosting STM replication via aggressively optimistic transaction processing. In NCA '10, pages 20--27. IEEE, 2010.
  17. J. Paiva, P. Ruivo, P. Romano, and L. Rodrigues. Autoplacer: Scalable self-tuning data placement in distributed key-value stores. ACM TAAS, 9(4):19, 2015.
  18. Z. Li, P. Van Roy, and P. Romano. Speculative transaction processing in geo-replicated data stores. Technical Report 2, INESC-ID, Feb. 2017.
  19. Lamport Leslie, The part-time parliament, 10.1145/279227.279229
  20. T. Kraska, G. Pang, M. J. Franklin, S. Madden, and A. Fekete. MDCC: Multi-data center consistency. In Eurosys '13, pages 113--126. ACM, 2013.
  21. R. Kotla, M. Balakrishnan, D. Terry, and M. K. Aguilera. Transactions with consistency choices on geo-replicated cloud storage. Technical report, September 2013.
  22. Jones Evan P.C., Abadi Daniel J., Madden Samuel, Low overhead concurrency control for partitioned main memory databases, 10.1145/1807167.1807233
  23. Jimenez-Peris R., Patino-Martinez M., Kemme B., Alonso G., Improving the scalability of fault-tolerant database clusters, 10.1109/icdcs.2002.1022297
  24. P. Heiland and D. Campbell. Building on quicksand. arXiv preprint arXiv:0909.1788, 2009.
  25. Haritsa J.R., Ramamritham K., Gupta R., The PROMPT real-time commit protocol, 10.1109/71.841752
  26. A. Gupta, F. Yang, J. Govig, A. Kirsch, K. Chan, K. Lai, S. Wu, S. G. Dhoot, A. R. Kumar, A. Agiwal, et al. Mesa: Geo-replicated, near real-time, scalable data warehousing. PVLDB '14, 7(12):1259--1270, 2014.
  27. R. Guerraoui, M. Pavlovic, and D.-A. Seredinschi. Incremental consistency guarantees for replicated objects. In OSDI '16, GA, 2016. USENIX Association.
  28. Gray Jim, Lamport Leslie, Consensus on transaction commit, 10.1145/1132863.1132867
  29. Graefe Goetz, Lillibridge Mark, Kuno Harumi, Tucek Joseph, Veitch Alistair, Controlled lock violation, 10.1145/2463676.2465325
  30. Fischer Michael J., Lynch Nancy A., Paterson Michael S., Impossibility of distributed consensus with one faulty process, 10.1145/3149.214121
  31. Elnikety S., Zwaenepoel W., Pedone F., Database Replication Using Generalized Snapshot Isolation, 10.1109/reldis.2005.14
  32. Dwork Cynthia, Lynch Nancy, Stockmeyer Larry, Consensus in the presence of partial synchrony, 10.1145/42282.42283
  33. S. Duan, V. Thummala, and S. Babu. Tuning database configuration parameters with iTuned. PVLDB '09, 2(1):1246--1257, 2009.
  34. J. Du, D. Sciascia, S. Elnikety, W. Zwaenepoel, and F. Pedone. Clock-RSM: Low-latency inter-datacenter state machine replication using loosely synchronized physical clocks. In DSN '14, pages 343--354. IEEE, 2014.
  35. J. Du, S. Elnikety, and W. Zwaenepoel. Clock-SI: Snapshot isolation for partitioned data stores using loosely synchronized clocks. In SRDS '13, pages 173--184. IEEE, 2013.
  36. Corbett James C., Hochschild Peter, Hsieh Wilson, Kanthak Sebastian, Kogan Eugene, Li Hongyi, Lloyd Alexander, Melnik Sergey, Mwaura David, Nagle David, Quinlan Sean, Dean Jeffrey, Rao Rajesh, Rolig Lindsay, Saito Yasushi, Szymaniak Michal, Taylor Christopher, Wang Ruth, Woodford Dale, Epstein Michael, Fikes Andrew, Frost Christopher, Furman J. J., Ghemawat Sanjay, Gubarev Andrey, Heiser Christopher, Spanner : Google’s Globally Distributed Database, 10.1145/2518037.2491245
  37. Chandra Tushar Deepak, Toueg Sam, Unreliable failure detectors for reliable distributed systems, 10.1145/226643.226647
  38. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in database systems. 1987.
  39. M. Basseville and I. V. Nikiforov. Detection of Abrupt Changes: Theory and Application. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.
  40. J. Baker, C. Bond, J. C. Corbett, J. Furman, A. Khorlin, J. Larson, J.-M. Leon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR '11, volume 11, pages 223--234, 2011.
  41. D. D. Akkoorath, A. Z. Tomsic, M. Bravo, Z. Li, T. Crain, A. Bieniusa, N. Preguiça, and M. Shapiro. Cure: Strong semantics meets high availability and low latency. In ICDCS '16, pages 405--414. IEEE, 2016.
Bibliographic reference Li, Zhongmiao ; Van Roy, Peter ; Romano, Paolo. Transparent Speculation in Geo-Replicated Transactional Data Stores. (2018)
Permanent URL http://hdl.handle.net/2078.1/214290