Cristina Basescu
ABSTRACT
A key-value store (KVS) offers functions for storing and retrieving values associated with unique keys. KVSs have become widely used as shared storage solutions for Internet-scale distributed applications.
We present a fault-tolerant wait-free efficient algorithm that emulates a multi-reader multi-writer register from a set of KVS replicas in an asynchronous environment. Our implementation serves an unbounded number of clients that use the storage. It tolerates crashes of a minority of the KVSs and crashes of any number of clients. We provide two variants of our algorithm: one implementing an atomic register and one implementing a regular register; the latter does not require read operations to store data at the underlying KVSs. We note that applying state-of-the-art reliable storage solutions to this scenario is either impossible or prohibitively inefficient.
- Amazon S3 availability event: July 20, 2008. http://status.aws.amazon.com/s3-20080720.html.Google Scholar
- Amazon Simple Storage Service. http://aws.amazon.com/s3/.Google Scholar
- Gmail back soon for everyone. http://gmailblog.blogspot.com/2011/02/gmail-back-soon-for-everyone.html.Google Scholar
- Project Voldemort: A distributed database. http://project-voldemort.com/.Google Scholar
- Windows Azure Storage. http://www.microsoft.com/windowsazure/storage/.Google Scholar
- I. Abraham, G. Chockler, I. Keidar, and D. Malkhi. Byzantine disk Paxos: Optimal resilience with Byzantine shared memory. Distributed Computing, 18(5):387--408, 2006.Google ScholarDigital Library
- H. Attiya, A. Bar-Noy, and D. Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124--142, 1995. Google ScholarDigital Library
- C. Basescu, C. Cachin, I. Eyal, R. Haas, and M. Vukolić. Robust data sharing with key-value stores. Research Report RZ 3802, IBM Research, 2011.Google Scholar
- C. Cachin, R. Guerraoui, and L. Rodrigues. Introduction to Reliable and Secure Distributed Programming (Second Edition). Springer, 2011. Google ScholarDigital Library
- G. Chockler and D. Malkhi. Active disk Paxos with infinitely many processes. Distributed Computing, 18:73--84, 2005. 10.1007/s00446-005-0123-x. Google ScholarDigital Library
- R. Fan and N. A. Lynch. Efficient replication of large data objects. In Distributed Computing (DISC), pages 75--91, 2003.Google ScholarCross Ref
- E. Gafni and L. Lamport. Disk Paxos. Distributed Computing, 16(1):1--20, 2003. Google ScholarDigital Library
- D. K. Gifford. Weighted voting for replicated data. In Symposium on Operating System Principles (SOSP), pages 150--162, 1979. Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12:463--492, July 1990. Google ScholarDigital Library
- A. Lakshman and P. Malik. Cassandra: A decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44:35--40, 2010. Google ScholarDigital Library
- L. Lamport. On interprocess communication. Distributed Computing, 1(2):77--101, 1986.Google ScholarCross Ref
- C. Shao, E. Pierce, and J. L. Welch. Multi-writer consistency conditions for shared memory objects. In Distributed Computing (DISC), pages 106--120, 2003.Google ScholarCross Ref
Index Terms
- Robust data sharing with key-value stores
Recommendations
Robust data sharing with key-value stores
DSN '12: Proceedings of the 2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)A key-value store (KVS) offers functions for storing and retrieving values associated with unique keys. KVSs have become the most popular way to access Internet-scale “cloud” storage systems. We present an efficient wait-free algorithm that emulates ...
Building Efficient Key-Value Stores via a Lightweight Compaction Tree
Special Issue on MSST 2017 and Regular PapersLog-Structure Merge tree (LSM-tree) has been one of the mainstream indexes in key-value systems supporting a variety of write-intensive Internet applications in today’s data centers. However, the performance of LSM-tree is seriously hampered by ...
An IO Optimized Data Access Method in Distributed Key-Value Storage System
GREENCOM-ITHINGS-CPSCOM '13: Proceedings of the 2013 IEEE International Conference on Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and Social ComputingDistributed KEY-VALUE storage system is a new storage framework for cloud computing. It can enable an application to dynamically adapt to growing workloads by increasing the number of servers. However, current distributed KEY-VALUE storage systems are ...
Comments