Autoplacer: scalable self-tuning data placement in distributed key-value stores

This paper addresses the problem of autonomic data placement in replicated key-value stores. The goal is to automatically optimize replica placement in a way that leverages locality patterns in data accesses, such that inter-node communication is minimized. To do this ef-ficiently is extremely challenging, as one needs not only to find lightweight and scalable ways to identify the right data placement, but also to preserve fast data lookup. The paper introduces new techniques that address each of the challenges above. The first challenge is addressed by optimizing, in a decentralized way, the placement of the objects generating most remote operations for each node. The second challenge is addressed by combining the usage of consistent hashing with a novel data struc-ture, which provides efficient probabilistic data place-ment. These techniques have been integrated in Infinis-pan, a popular open-source key-value store. The perfor-mance results show that the throughput of the optimized system can be 6 times better than a baseline system em-ploying the widely used static placement based on con-sistent hashing.