Ecole d'ingénieur et centre de recherche en Sciences du numérique

Robust data sharing with key-value stores

Basescu, Cristina; Cachin, Christian; Eyal, Ittay; Haas, Robert; Sorniotti, Alessandro; Vukolic, Marko; Zachevsky, Ido

DSN 2012, 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, 25-28 June, 2012, Boston, MA, USA

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 Internetscale “cloud” storage systems. We present an efficient wait-free algorithm that emulates multi-reader multi-writer storage from a set of potentially faulty KVS replicas in an asynchronous environment. Our implementation serves an unbounded number of clients that use the storage concurrently. It tolerates crashes of a minority of the KVSs and crashes of any number of clients. Our algorithm minimizes the space overhead at the KVSs and comes in two variants providing regular and atomic semantics, respectively. Compared with prior solutions, it is inherently scalable and allows clients to write concurrently. Because of the limited interface of a KVS, textbook-style solutions for reliable storage either do not work or incur a prohibitively large storage overhead. Our algorithm maintains two copies of the stored value per KVS in the common case, and we show that this is indeed necessary. If there are concurrent write operations, the maximum space complexity of the algorithm grows in proportion to the point contention. A series of simulations explore the behavior of the algorithm, and benchmarks obtained with KVS cloud-storage providers demonstrate its practicality.

Document Doi Bibtex

Titre:Robust data sharing with key-value stores
Département:Sécurité numérique
Eurecom ref:3696
Copyright: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+3696, doi = {}, year = {2012}, title = {{R}obust data sharing with key-value stores}, author = {{B}asescu, {C}ristina and {C}achin, {C}hristian and {E}yal, {I}ttay and {H}aas, {R}obert and {S}orniotti, {A}lessandro and {V}ukolic, {M}arko and {Z}achevsky, {I}do}, booktitle = {{DSN} 2012, 42nd {A}nnual {IEEE}/{IFIP} {I}nternational {C}onference on {D}ependable {S}ystems and {N}etworks, 25-28 {J}une, 2012, {B}oston, {MA}, {USA} }, address = {{B}oston, {\'{E}}{TATS}-{UNIS}}, month = {06}, url = {} }
Voir aussi: