Document Open Access Logo

Non-Uniform Replication

Authors Gonçalo Cabrita, Nuno Preguiça

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2017.24.pdf
  • Filesize: 0.65 MB
  • 19 pages

Document Identifiers

Subject Classification

Keywords
  • Non-uniform Replication
  • Partial Replication
  • Replicated Data Types
  • Eventual Consistency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Replication is a key technique in the design of efficient and reliable distributed systems. As information grows, it becomes difficult or even impossible to store all information at every replica. A common approach to deal with this problem is to rely on partial replication, where each replica maintains only a part of the total system information. As a consequence, a remote replica might need to be contacted for computing the reply to some given query, which leads to high latency costs particularly in geo-replicated settings. In this work, we introduce the concept of non- uniform replication, where each replica stores only part of the information, but where all replicas store enough information to answer every query. We apply this concept to eventual consistency and conflict-free replicated data types. We show that this model can address useful problems and present two data types that solve such problems. Our evaluation shows that non-uniform replication is more efficient than traditional replication, using less storage space and network bandwidth.

Cite As Get BibTex

Gonçalo Cabrita and Nuno Preguiça. Non-Uniform Replication. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.24

Author Details

Gonçalo Cabrita
Nuno Preguiça

References

  1. Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. Delta state replicated data types. J. Parallel Distrib. Comput., 111:162-173, 2018. URL: http://dx.doi.org/10.1016/j.jpdc.2017.08.003.
  2. Sérgio Almeida, João Leitão, and Luís E. T. Rodrigues. Chainreaction: a causal+ consistent datastore based on chain replication. In Zdenek Hanzálek, Hermann Härtig, Miguel Castro, and M. Frans Kaashoek, editors, Eighth Eurosys Conference 2013, EuroSys '13, Prague, Czech Republic, April 14-17, 2013, pages 85-98. ACM, 2013. URL: http://dx.doi.org/10.1145/2465351.2465361.
  3. Gustavo Alonso. Partial database replication and group communication primitives. In Proc. European Research Seminar on Advances in Distributed Systems, 1997. Google Scholar
  4. Daniel Barbará-Millá and Hector Garcia-Molina. The Demarcation Protocol: A Technique for Maintaining Constraints in Distributed Database Systems. The VLDB Journal, 3(3):325-353, jul 1994. URL: http://dx.doi.org/10.1007/BF01232643.
  5. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s Globally-distributed Database. In Proc. 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, 2012. Google Scholar
  6. Tyler Crain and Marc Shapiro. Designing a causally consistent protocol for geo-distributed partial replication. In Carlos Baquero and Marco Serafini, editors, Proceedings of the First Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC@EuroSys 2015, Bordeaux, France, April 21, 2015, pages 6:1-6:4. ACM, 2015. URL: http://dx.doi.org/10.1145/2745947.2745953.
  7. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: amazon’s highly available key-value store. In Thomas C. Bressoud and M. Frans Kaashoek, editors, Proceedings of the 21st ACM Symposium on Operating Systems Principles 2007, SOSP 2007, Stevenson, Washington, USA, October 14-17, 2007, pages 205-220. ACM, 2007. URL: http://dx.doi.org/10.1145/1294261.1294281.
  8. Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, and Douglas B. Terry. Epidemic algorithms for replicated database maintenance. In Fred B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages 1-12. ACM, 1987. URL: http://dx.doi.org/10.1145/41840.41841.
  9. Patrick Th. Eugster, Rachid Guerraoui, Anne-Marie Kermarrec, and Laurent Massoulié. Epidemic information dissemination in distributed systems. IEEE Computer, 37(5):60-67, 2004. URL: http://dx.doi.org/10.1109/MC.2004.1297243.
  10. Konstantinos Kloudas, Margarida Mamede, Nuno Preguiça, and Rodrigo Rodrigues. Pixida: Optimizing Data Parallel Jobs in Wide-area Data Analytics. Proc. VLDB Endow., 9(2):72-83, 2015. URL: http://dx.doi.org/10.14778/2850578.2850582.
  11. Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. Operating Systems Review, 44(2):35-40, 2010. URL: http://dx.doi.org/10.1145/1773912.1773922.
  12. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, 1978. URL: http://dx.doi.org/10.1145/359545.359563.
  13. Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133-169, 1998. URL: http://dx.doi.org/10.1145/279227.279229.
  14. Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguiça, and Rodrigo Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 265-278, 2012. Google Scholar
  15. Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In Ted Wobber and Peter Druschel, editors, Proceedings of the 23rd ACM Symposium on Operating Systems Principles 2011, SOSP 2011, Cascais, Portugal, October 23-26, 2011, pages 401-416. ACM, 2011. URL: http://dx.doi.org/10.1145/2043556.2043593.
  16. Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Stronger Semantics for Low-latency Geo-replicated Storage. In Proc. 10th USENIX Conference on Networked Systems Design and Implementation, nsdi'13, 2013. Google Scholar
  17. Hatem Mahmoud, Faisal Nawab, Alexander Pucher, Divyakant Agrawal, and Amr El Abbadi. Low-latency Multi-datacenter Databases Using Replicated Commit. Proc. VLDB Endow., 6(9), jul 2013. URL: http://dx.doi.org/10.14778/2536360.2536366.
  18. Henrique Moniz, João Leitão, Ricardo J. Dias, Johannes Gehrke, Nuno M. Preguiça, and Rodrigo Rodrigues. Blotter: Low latency transactions for geo-replicated storage. In Rick Barrett, Rick Cummings, Eugene Agichtein, and Evgeniy Gabrilovich, editors, Proceedings of the 26th International Conference on World Wide Web, WWW 2017, Perth, Australia, April 3-7, 2017, pages 263-272. ACM, 2017. URL: http://dx.doi.org/10.1145/3038912.3052603.
  19. David Navalho, Sérgio Duarte, and Nuno M. Preguiça. A study of crdts that do computations. In Carlos Baquero and Marco Serafini, editors, Proceedings of the First Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC@EuroSys 2015, Bordeaux, France, April 21, 2015, pages 1:1-1:4. ACM, 2015. URL: http://dx.doi.org/10.1145/2745947.2745948.
  20. Patrick E. O'Neil. The escrow transactional method. ACM Trans. Database Syst., 11(4):405-430, 1986. URL: http://dx.doi.org/10.1145/7239.7265.
  21. Yasushi Saito and Marc Shapiro. Optimistic replication. ACM Comput. Surv., 37(1):42-81, 2005. URL: http://dx.doi.org/10.1145/1057977.1057980.
  22. Nicolas Schiper, Pierre Sutra, and Fernando Pedone. P-store: Genuine partial replication in wide area networks. In 29th IEEE Symposium on Reliable Distributed Systems (SRDS 2010), New Delhi, Punjab, India, October 31 - November 3, 2010, pages 214-224. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/SRDS.2010.32.
  23. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free Replicated Data Types. In Proc. 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS'11, 2011. Google Scholar
  24. Yair Sovran, Russell Power, Marcos K. Aguilera, and Jinyang Li. Transactional storage for geo-replicated systems. In Ted Wobber and Peter Druschel, editors, Proceedings of the 23rd ACM Symposium on Operating Systems Principles 2011, SOSP 2011, Cascais, Portugal, October 23-26, 2011, pages 385-400. ACM, 2011. URL: http://dx.doi.org/10.1145/2043556.2043592.
  25. Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, and Hussam Abu-Libdeh. Consistency-based service level agreements for cloud storage. In Michael Kaminsky and Mike Dahlin, editors, ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP '13, Farmington, PA, USA, November 3-6, 2013, pages 309-324. ACM, 2013. URL: http://dx.doi.org/10.1145/2517349.2522731.
  26. Albert van der Linde, João Leitão, and Nuno M. Preguiça. Δ-crdts: making Δ-crdts delta-based. In Peter Alvaro and Alysson Bessani, editors, Proceedings of the 2nd Workshop on the Principles and Practice of Consistency for Distributed Data, PaPoC@EuroSys 2016, London, United Kingdom, April 18, 2016, pages 12:1-12:4. ACM, 2016. URL: http://dx.doi.org/10.1145/2911151.2911163.
  27. Werner Vogels. Eventually consistent. Commun. ACM, 52(1):40-44, 2009. URL: http://dx.doi.org/10.1145/1435417.1435432.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact