Replex: A Scalable, Highly Available Multi-Index Store

Abstract

We present Replex, a datastore that enables efficient querying on multiple keys by rethinking how data is placed 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 data based on the replex's key. Replexes eliminate any additional overhead to maintaining indices, while unfortunately increasing the cost of 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.