RW-Through: A Data Replication Protocol Suitable for GeoDistributed and Read-Intensive Workloads
In large-scale modern applications, users consume much more datathan they create. To guarantee that data storage systems appropriately han-dle read-intensive workloads, application designers have been adopting datareplication and caching techniques. These techniques face many challenges re-garding data consistency, specially in faulty network conditions such as wide-area networks. In this work we use recent distributed consistency frameworksto identify the consistency models of the main solutions for read-intensive work-loads used today in the industry. Additionally, we present RW-Through, a newdata replication protocol suited for large-scale read-intensive workloads. Ournew protocol provides stronger consistency guarantees than current solutionsand is designed to tolerate unreliable network conditions, making it suitable forgeo-distributed deployments.
Bailis, P. and Ghodsi, A. (2013). Eventual consistency today: Limitations, extensions, and beyond. Queue, 11(3):20:20-20:32.
Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Com-mun. ACM, 13(7):422-426.
Brewer, E. A. (2000). Towards robust distributed systems. In Proceedings of the Nine-teenth Annual ACM Symposium on Principles of Distributed Computing, PODC '00.
Bruner, J. (2013). Tweets loud and quiet.
Burckhardt, S. (2014). Principles of Eventual Consistency, volume 1. now publishers.
Cecchet, E., Candea, G., and Ailamaki, A. (2008). Middleware-based database replica-tion: The gaps between theory and practice. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD '08.
Fan, B., Andersen, D. G., Kaminsky, M., and Mitzenmacher, M. D. (2014). Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT '14.
Gilbert, S. and Lynch, N. (2002). Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51-59.
Gray, J., Helland, P., O'Neil, P., and Shasha, D. (1996). The dangers of replication and a solution. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, SIGMOD '96, pages 173-182, New York, NY, USA. ACM.
Herlihy, M. P. and Wing, J. M. (1990). Linearizability: A correctness condition for con-current objects. ACM Trans. Program. Lang. Syst., 12(3):463-492.
Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565.
Nishtala, R., Fugal, H., Grimm, S., Kwiatkowski, M., Lee, H., Li, H. C., McElroy, R., Paleczny, M., Peek, D., Saab, P., Stafford, D., Tung, T., and Venkataramani, V. (2013). Scaling memcache at facebook. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13).
Pacitti, E. p., Minet, P., and Simon, E. Fast Algorithms for Maintaining Replica Consis-tency in Lazy Master Replicated Databases. Technical report.
Schwarz, R. and Mattern, F. (1994). Detecting causal relationships in distributed compu-tations: In search of the holy grail. Distributed Computing, 7(3):149-174.
Viotti, P. and Vukolić, M. (2016). Consistency in non-transactional distributed storage systems. ACM Comput. Surv., 49(1):19:1-19:34.