Replex: A scalable, highly available multi-index data store

Amy Tai, Michael Wei, Michael J. Freedman, Ittai Abraham, Dahlia Malkhi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


The need for scalable, high-performance datastores has led to the development of NoSQL databases, which achieve scalability by partitioning data over a single key. However, programmers often need to query data with other keys, which data stores provide by either querying every partition, eliminating the benefits of partitioning, or replicating additional indexes, wasting the benefits of data replication. In this paper, we show there is no need to compromise scalability for functionality. We present Replex, a datastore that enables efficient querying on multiple keys by rethinking data placement during replication. Traditionally, a data store is first globally partitioned, then each partition is replicated identically to multiple nodes. Instead, Replex relies on a novel replication unit, termed replex, which partitions a full copy of the data based on its unique key. Replexes eliminate any additional overhead to maintaining indices, at the cost of increasing recovery complexity. To address this issue, we also introduce hybrid replexes, which enable a rich design space for trading off steady-state performance with faster recovery. We build, parameterize, and evaluate Replex on multiple dimensions and find that Replex surpasses the steady-state and failure recovery performance of Hyper- Dex, a state-of-the-art multi-key data store.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 USENIX Annual Technical Conference, USENIX ATC 2016
PublisherUSENIX Association
Number of pages14
ISBN (Electronic)9781931971300
StatePublished - 2016
Event2016 USENIX Annual Technical Conference, USENIX ATC 2016 - Denver, United States
Duration: Jun 22 2016Jun 24 2016

Publication series

NameProceedings of the 2016 USENIX Annual Technical Conference, USENIX ATC 2016


Conference2016 USENIX Annual Technical Conference, USENIX ATC 2016
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Replex: A scalable, highly available multi-index data store'. Together they form a unique fingerprint.

Cite this