RECODE: Reconfigurable, consistent and decentralized data services

Key-based routing schemes, where a message is forwarded towards a server responsible for a partition in a large name space, does not provide strong delivery guarantees when the network is reconfigured with servers joining and leaving. This best-effort behavior is sufficient for eventually consistent data services such as key-value stores, content distribution networks or publish/subscribe systems. However, such schemes are not able to provide stronger consistency guarantees as required by, for example, metadata services and databases. We present RECODE, a framework for reconfigurable, consistent and decentralized data services. RECODE simplifies the implementation of strongly consistent data services, and continues to provide strong guarantees even during reconfiguration. More specifically, we introduce the routecast primitive which delivers messages for a key in the same total order, independent of the servers responsible for the key.We demonstrate the expressiveness and practical usability of RECODE by presenting three applications: a map of atomic registers, a set of distributed counters, and a lease management system. We evaluate the performance and elasticity of RECODE executing in a cluster.