Here’s a little Thanksgiving reading for you while you’re digesting that fourth helping of pie: a paper on a new approach to geo-replicated, distributed data stores (PDF). The paper, authored by researchers from Princeton University, Intel Labs, and Carnegie Mellon University, proposes a new consistency model for wide-area storage.
The idea is to provide an infrastructure that can support major Internet services. That might entail tens of data centers, each one having a set of application servers and data stores for those systems.
As the paper notes “a distributed storage system has multiple, sometimes competing, goals: availability, low latency, and partition tolerance to provide an ‘always on’ user experience; scalability to adapt to increasing load and storage demands; and a supportciently strong consistency model to simplify programming and provide users with the system behavior that they expect.”
The system that is being proposed, is called Clusters of Order-Preserving Servers (COPS). According to the post:
Our system, COPS, is a key-value store that delivers this consistency model across the wide-area. A key contribution of COPS is its scalability, which can enforce causal dependencies between keys stored across an entire cluster, rather than a single server like previous systems. Scaling the size of each cluster brings causal consistency to a new set of applications, such as social networks like Facebook and Twitter, whose data is far too large and query rates far too high to be handled by single machine clusters.
The central approach in COPS involves explicitly tracking and enforcing causal dependencies between updates. For instance, if you upload a photo and add it to an album, the album update “depends on” the photo addition, and should only be applied after it. Writes in COPS are accepted by a local datacenter that then propagates them to other, remote, datacenters. These remote datacenters check that all dependencies are satisfied by querying other nodes in the cluster before applying writes. This approach differs from traditional causal systems that exchange update logs between replicas. In particular, the COPS approach avoids any single serialization point to collect, transmit, merge, or apply logs. Avoiding single serialization points is a major factor in enabling COPS to scale to large cluster sizes.
The paper is 16 pages, and full of detail. The High Scalability blog has an interesting summary of the paper. At first glance I’d say that we’re going to be hearing a lot more about ALPS and COPS.
