COPS Reading Note

Title: Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
SOSP 2011, Ref: 801, UC Berkeley, Princeton University, Intel Labs, Carnegie Mellon University.

TL;DR

Problem/Goal
Provide available, low latency, partition tolerance, and high scalability for geo-distributed data stores.
Idea
Consider performance requirements first then provide the best consistency model.
Causal+ consistency
How
Async replicas data between data centers

Clients maintain dependencies info and pass to datacenter.

More detail

Causal+ consistency

Causal is used to describe one event may affect another in a distributed system.

In the physical world, we say event a may affect event b if event a happens before event b.

We need to describe this relationship in distributed systems too.

In a distributed system, there are many processes and each process is independent.

In a process, we can know events' order easily, if event a occurs before event b, then event a may affect event b and we say event a causal effects event b.

Between processes, the only way to share information is message passing.

What we can know is if a is the sending of a message by one process and b is the receipt of the same message by another process, we know a happens before b and say event a causal effects event b.

If event a causal effects event b and event b causal effects event c, we know event a causal effects event c, it is transitivity.

That means two processes can work independently if they do not send messages to each other.

For example:

process a:

create_book1
create_book2
get_books_count # return 2

process b:

create_book3
get_books_count # return 1

Each process only sees part of the whole system.

It's helpful, as in each process' perspective, it is reasonable and most of time we do not need global information.

Why causal consistency is useful

Easy to program

Even through eventual consistency can offer good performance, but it's too hard for developers to handle consitency.

Such as for a photo manager:

c1 and c2 are in different data centers:

c1 upload photo the and the reference to the list:
   put(photo)
   put(list)

c2 reads:
   get(list)
   get(photo)

For eventual consistency, all data centers can apply the two changes in any order -- update the list first or create the photo first.

When a user reads the data, he may see the new list has the photo's reference but can't read the new photo.

Causal consistency can avoid such things.

When c2 reads the list, he can read an old list that doesn't have the new photo reference, or he can read the new list and read the new photo.

That because, put(photo) causal effects put(list).

When c2 reads the list by get(list), if the list contains the new photo's reference, c2 must "know" put(list) for keeping causal consistency.

Good performance

For strong consistency, we need to maintain a global order for all events. But for causal consistency, we only maintain partial orders.

That means we can achieve much more currency if we only guarantee causal consistency.

So causal consistency can provide better performance than strong consistency.

Conflict

Let's see an example:

process a:
set(x, 1) # event1
send_msg_to_process_b # event2

process b:
set(x, 2) # event3
receive_msg_from_process_a #event4

If process a doesn't send message to process b all things work smoothly, all events can happen in any order.

But when process b received the message, he needs to determine whether x is equal to 1 or equal to 2.

That means we need some conflict-solving mechanisms.

We need consider process b receives a message from process a and we need consider process a receives a message from process b too.

For avoiding diverging forever, both process a and process b need to get the same result after executing the conflict-solving mechanism.

That is

Convergent conflict handling requires that all conflicting puts be handled in same manner at all replicas, using a handler function h.[1]

And causal consistency + convergent conflict handling is the causal+ consistency[1] in the paper.

Read-Only Transaction

We see causal consistency can avoid some kinds of abnormal situations, but it's not enough.

Let's see the paper's example: a photo list with an ACL (Access Control List).

1 c1:
2 put(ACL)
3 put(picture)
4
5 c2:
6 read(ACL)
7 get(picture)

c1 updates the ACL at line 2 which removes c2 from the access list and creates a sensitive photo into the list.

Then c2 reads the access list but he may read it from a different data center and the ACL hasn't been updated. So he can see the list of photos.

And when he reads the list of photos, the list has been updated so can see the sensitive photo.

Those things can happen because causal consistency can only guarantee orders but not consistent versions.

For avoid such things, we need read-only sort-of transactions.

How it works

Architecture

The Datacenter is GEO-distributed across countries and each Datacenter contains Clients and Data Store Cluster.

The Client is connected to the user and used for managing the client's dependencies and sending request to its local Data Store Cluster.

The client will read and write data to the local Data Store Cluster only and Data Store Cluster will replica data between each cluster asynchronously.

The client is COPS' clients, not browsers or apps, it's backend servers.

How Simple Write and Read Works

Let's see the photo manager example again:

c1 upload photo the and the reference to the list:
   put(photo)
   put(list)

The writing request will go to the client's local cluster and the propagate asynchronously to remove clusters.

Write to the local cluster
put(photo) will send request(put_after(key=photo_key, val='some-value', nearest=nil, vers=0)) to local store node, after the node committed the data, the node will send a reply to the client.

After client received the reply, then client can update the list by put_after(key='list_key', val=with_the_photo_ref, nearest=[{key=photo_key, vers=0}]).

Wrtie replication between clusters

After the Photo Node committed the data, it will send requests to remote clusters. Photo List Node will do the same thing.

The remote clusters can receive those two requests in any order.

When the remote Photo List Node received the request, it will send check_deps request to its local Photo Node first for checking dependencies,

if the Photo Node replies OK, then the Photo List Node will commit the data.

Solving Conflict

Causal+ consistency only captures part of the order, so we need mechanisms to solve conflicts.

COPS uses Lamport clock solving conflicts by default and can allow application config the conflict handler.

Lamport clock is a "logical clock", some simple implementation can be, for each process, we can maintain a counter, when one event happens, we can increase one.

clock += 1

When sending a message to another process, it needs to pass the counter or the clock to the receiver process.

And when a process received the message, it needs to advance its clock.

clock = max(message.clock + 1, current_clock).

For more detail, you can check Erlang Mnesia's implementation[2] or Lamport's paper[3].

Read-only transactions

The read-Only Transaction section has explained why we need read-only transactions, now let's see how it is implemented.

The get_trans is used for getting multiple keys in a transaction. And the client library will do this in 2 rounds.

In the first round, the client library will request the n keys concurrency.

The keys may belong to different shards, so we can't get them in one request.

And as they are sending currently, the results may belong to different "snapshots".

For example {ACL0, version=10} <- [], {Photo1, version=0} <- [{ACL1, version=11}].

For fixing that, we need to calculate all the newest versions and then get the newest versions.

Notice, that dependency is a kind of order, if a depends on b, then b can't depend on a, COPS has solved the conflict.

So in the second round, after we get the newest version, we can get the "snapshot".

Summary

I'm curious what effort we need to make when we use causal+ consistency in a real application and how chould we solv the conflict.

This consistency model is helpful and inspiring but not easy to understand, in industry, people may like strick forward solution.

References

Wyatt Lloyd. Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS, SOSP 2011
Erlang Mnesia Implementation
https://github.com/erlang/otp/blob/40922798411c2d23ee8a99456f96d6637c62b762/lib/mnesia/doc/misc/implementation.txt
L. Lamport. Time, clocks, and the ordering of events in a distributed system. 1978.

Reading Notes #8

Description

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions