On the Support of Versioning in Distributed Key-Value Stores
Pascal Felber, Marcelo Pasin, Etienne Rivière, Valerio Schiavoni, Pierre Sutra, Fábio Coehlo, Rui Oliveira, Miguel Matos & Ricardo Vilaça
| Résumé |
The ability to access and query data stored in multiple versions is
an important asset for many applications, such as Web graph
analysis, collaborative editing platforms, data forensics, or
correlation mining. The storage and retrieval of versioned data
requires a specific API and support from the storage layer. The
choice of the data structures used to maintain versioned data has a
fundamental impact on the performance of insertions and queries. The
appropriate data structure also depends on the nature of the
versioned data and the nature of the access patterns. In this paper
we study the design and implementation space for providing
versioning support on top of a distributed key-value store (KVS).
We define an API for versioned data access supporting multiple
writers and show that a plain KVS does not offer the necessary
synchronization power for implementing this API. We leverage the
support for listeners at the KVS level and propose a general
construction for implementing arbitrary types of data structures
for storing and querying versioned data. We explore the design
space of versioned data storage ranging from a flat data structure
to a distributed sharded index. The resulting system, ALEPH, is
implemented on top of an industrial-grade open-source KVS,
Infinispan. Our evaluation, based on real-world Wikipedia access
logs, studies the performance of each versioning mechanisms in
terms of load balancing, latency and storage overhead in the
context of different access scenarios. |
| Mots-clés |
|
| Citation | P. Felber, et al., "On the Support of Versioning in Distributed Key-Value Stores," in SRDS'14: The 33rd IEEE International Symposium on Reliable Distributed Systems, Nara, Japan, 2014, p. 95-104. |
| Type | Actes de congrès (Anglais) |
| Nom de la conférence | SRDS'14: The 33rd IEEE International Symposium on Reliable Distributed Systems (Nara, Japan) |
| Date de la conférence | 6-10-2014 |
| Editeur commercial | IEEE |
| Pages | 95-104 |
| URL | http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumbe... |
| Liée au projet | LEADS: Large-Scale Elastic Architecture for Data as a Ser... |