Recent years have seen an explosion of Internet-scale applications, ranging from web search to social networks. These applications are typically implemented with many machines running in multiple data centers. In order to coordinate their operations, these machines access some shared storage. In this context, a prominent storage model is the key-value store (KVS) or key-value database. A KVS offers functions for storing and retrieving objects (called values) associated with unique keys. KVSs have become widely used as shared storage solutions for Internet-scale distributed applications. A KVS offers a range of simple functions for manipulation of unstructured data objects, each one identified by a unique key. While different services and systems offer various extensions to the KVS interface, the common denominator of existing KVS services implements an associative array: A client may store a value by associating the value with a key, retrieve a value associated with a key, list the keys that are currently associated, and remove a value associated with a key.