Brief Announcement: Demand-Aware Consistent Hashing with Bounded Loads & Greedy Routing

Workloads of networked and distributed systems are often far from random, but exhibit certain structure: they are skewed and bursty. Networked systems which can adapt to and exploit such spatial and temporal structure, in a demand-aware manner, bear the potential to be more efficient than their demand-oblivious alternatives. This paper studies demand-awareness in the context of consistent hashing, a fundamental component in many modern distributed systems. We present a novel demand-aware consistent hashing method to improve access time and storage utilization in distributed hash tables. In particular, the resulting system supports local (greedy) routing, ensures bounded server loads, and applies to various network topologies. We formally prove that our algorithms achieve a constant approximation ratio in the offline scenario.