paper

HyperDex: A Distributed, Searchable Key-Value Store

  • Authors:
Read the paper

📜 Abstract

Distributed key-value stores are now a standard component of high-performance web services and cloud computing applications. While key-value stores offer significant performance and scalability advantages compared to traditional databases, they achieve these properties through a restricted API that limits object retrieval—an object can only be retrieved by the (primary and only) key under which it was inserted. This paper presents HyperDex, a novel distributed key-value store that provides a unique search primitive that enables queries on secondary attributes. The key insight behind HyperDex is the concept of hyperspace hashing in which objects with multiple attributes are mapped into a multidimensional hyperspace. This mapping leads to efficient implementations not only for retrieval by primary key, but also for partially-specified secondary attribute searches and range queries. A novel chaining protocol enables the system to achieve strong consistency, maintain availability and guarantee fault tolerance. An evaluation of the full system shows that HyperDex is 12-13× faster than Cassandra and MongoDB for finding partially specified objects. Additionally, HyperDex achieves 2-4× higher throughput for get/put operations.

✨ Summary

Summary

HyperDex proposes a distributed key-value store that supports searches over secondary attributes through hyperspace hashing. Objects are mapped to multidimensional coordinates, while servers own regions of that space; this allows clients to prune the set of servers involved in partially specified and range queries. The system addresses high dimensionality through lower-dimensional subspaces and provides strong consistency and fault tolerance through value-dependent chaining, which accommodates object relocation as attribute values change.

The paper influenced subsequent systems research in several concrete ways:

  • HyperDex’s hyperspace-hashing approach is cited as the basis for later work on multidimensional distributed data processing, including BBoxDB, which contrasts HyperDex’s support for multidimensional point data with its own support for broader data-stream workloads. (link.springer.com)
  • Later research directly revisited and extended hyperspace hashing for centralized, GPU-accelerated environments, explicitly identifying HyperDex as the originating distributed design. (link.springer.com)
  • The Replex datastore used HyperDex as a comparison point and studied an alternative replication/indexing design intended to reduce the storage and write overhead associated with maintaining full copies across subspaces. (usenix.org)
  • The HyperDex implementation was released as open source and remains available as a distributed, searchable, consistent key-value store, providing an artifact for experimentation and reuse. (github.com)

These references indicate that HyperDex’s primary lasting contribution was as a design point for multidimensional search in distributed key-value stores, particularly the combination of attribute-aware placement, search-space pruning, and replication under changing object locations.