COPS
COPS stands for Clusters of Order-Preserving Servers. It is a geo-replicated key-value store designed to provide:
- Low-latency reads and writes
- Availability during wide-area network partitions
- Scalability across many servers
- Linearizability is preserved inside each datacenter
- Between datacenters: Causal+ Consistency
Each datacenter contains a complete logical replica of the data, although that data is sharded across many servers inside the datacenter. Clients communicate only with their nearby datacenter. Operations inside one datacenter are linearizable, while replication between datacenters occurs asynchronously.
The important problem is that asynchronous replication messages can arrive in a different order from the order in which they were created.
How COPS partitions data
There are two different kinds of replication in COPS:
- Across datacenters: every datacenter stores the complete logical keyspace.
- Inside a datacenter: that keyspace is partitioned among many servers.
“Complete logical replica” therefore does not mean every server stores everything. It means the servers in one datacenter collectively store everything.
Example of data partition
Assume three datacenters, each with four nodes:
US datacenter Europe datacenter Asia datacenter
US-1 US-2 US-3 US-4 EU-1 EU-2 EU-3 EU-4 AS-1 AS-2 AS-3 AS-4
All three datacenters logically contain:
photo:42
album:alice
comment:55
profile:alice
...
COPS uses consistent hashing to assign key ranges to nodes inside each datacenter. The mapping can differ between datacenters:
Key US primary Europe primary Asia primary
-------------------------------------------------------------------
photo:42 US-1 EU-3 AS-2
album:alice US-2 EU-1 AS-4
comment:55 US-4 EU-2 AS-1
Thus:
hash("photo:42") → a node responsible for its hash range
Every key has one primary node in each datacenter. The primaries responsible for the same key in different datacenters are called that key’s equivalent nodes:
Equivalent nodes for photo:42:
US-1 <------> EU-3 <------> AS-2
After US-1 accepts a new version of photo:42, it puts that version in a replication queue and asynchronously sends it to EU-3 and AS-2.
COPS example: uploading a photo
Assume there are two keys:
photo:42 = the actual image
album:alice = the list of photos in Alice's album
Alice is connected to the US datacenter.
Step 1: Alice uploads the photo
put("photo:42", imageData)
COPS assigns the write a version:
photo:42@P7
The client library records it in Alice’s context:
Alice's context = { photo:42@P7 }
The context records what Alice has previously read or written in this logical session.
Step 2: Alice adds the photo to her album
Alice then writes:
put("album:alice", ["photo:42"])
Because photo:42@P7 is in Alice’s context, COPS attaches it as a dependency of the album update:
album:alice@A9 depends on photo:42@P7
The causal graph is therefore:
photo:42@P7 ──────────> album:alice@A9
photo exists album references it
COPS internally treats this as something similar to:
put_after(
key = "album:alice",
value = ["photo:42"],
dependency = "photo:42@P7"
)
The meaning of put_after is:
Commit this version only after the specified dependency has been committed.
The local US cluster already contains the photo, so the album update can be committed immediately there.
What happens during asynchronous replication
The US datacenter asynchronously sends both writes to Europe:
photo:42@P7
album:alice@A9
Because different keys may be owned by different servers and network messages can be delayed, Europe might receive the album update first:
Arrival order in Europe:
1. album:alice@A9
2. photo:42@P7
Without causal consistency, Europe could expose the album immediately:
album:alice = ["photo:42"]
photo:42 = missing
A European user would see a reference to a photo that does not exist locally yet.
How COPS prevents this
When the album server receives album:alice@A9, it sees the attached dependency:
photo:42@P7
It sends a dependency check to the server responsible for the photo:
dep_check("photo:42", P7)
At this point, the dependency is absent, so COPS does not expose the new album version.
Europe:
photo server: photo:42@P7 not present
album server: album:alice@A9 pending, not visible
Later, the photo write arrives:
photo:42@P7 commits
The dependency check succeeds, so COPS can now commit the album update:
photo:42@P7 commits
↓
album:alice@A9 commits
The result is:
Europe:
photo:42 = imageData
album:alice = ["photo:42"]
Although the messages arrived in the wrong order, they became visible in causal order. Remote COPS servers commit incoming versions only after their dependencies have been satisfied in that same datacenter.
Key takeaway
Thus, COPS at least ensures causally related operations to be visible in the same order across all replicas.
Client context is the key machanism
For regular COPS, the client library approximately behaves like this:
context = set()
def get(key):
value, version = local_cluster.get_latest(key)
context.add((key, version))
return value
def put(key, value):
dependencies = context.copy()
version = local_cluster.put_after(
key=key,
value=value,
nearest_dependencies=dependencies
)
context.clear()
context.add((key, version))Suppose the context before a write is:
{
user:alice@U3,
album:alice@A9,
settings:alice@S4
}The next write depends on all those observed versions. After that write succeeds, it becomes the nearest representative of the earlier dependencies:
Before put:
{ U3, A9, S4 }
New write:
post:88@P15 depends on { U3, A9, S4 }
After put:
{ post:88@P15 }
Since post:88@P15 already depends on all previous context entries, later writes can depend only on post:88@P15.
What “causal+” adds: conflict resolution
Suppose two disconnected datacenters concurrently update the same key:
US: put("meeting-time", "8 PM")
Europe: put("meeting-time", "10 PM")
Neither write caused the other:
8 PM write ∥ 10 PM write
Causal consistency alone does not order concurrent operations, so replicas could theoretically retain different results. COPS uses a convergent conflict-resolution rule. Its default implementation uses version numbers based on Lamport timestamps and node identifiers to choose a deterministic last-writer-wins result. Once both replicas receive both updates, they choose the same winner.