Skip to main content

Replex: A Scalable, Highly Available Multi-Index Data Store

Author(s): Tai, Amy; Wei, Michael; Freedman, Michael J; Abraham, Ittai; Malkhi, Dahlia

To refer to this page use:
Abstract: 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.
Publication Date: 2016
Citation: Tai, Amy, Michael Wei, Michael J. Freedman, Ittai Abraham, and Dahlia Malkhi. "Replex: A scalable, highly available multi-index data store." In USENIX Annual Technical Conference (2016): pp. 337-350.
Pages: 337 - 350
Type of Material: Conference Article
Journal/Proceeding Title: USENIX Annual Technical Conference
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.