[kennu]

I always figured that the C in CAP is more about scalability. If you keep adding servers indefinitely, it becomes slower and slower to commit every transaction to every server. But if you ditch the C, you can write fully in parallel to all servers.

[cx01]

ACID transactions require consistency (C in CAP) in order to guarantee atomicity. So if you ditch C, you'll just be unable to perform transactions at all.

In general, weakening the consistency guarantees is not done to improve scalability, but rather to improve the partition tolerance. There are replication techniques (e.g. chain replication) that allow very high performance without sacrificing consistency.

[kingkilr]

The C in CAP and the C in ACID are not the same C. Consistency in the ACID sense means that all constraints are met, Consistency in the CAP sense means all servers have the same data.

[cx01]

I know. I actually explained this not too long ago here: http://news.ycombinator.com/item?id=1191003

But what I'm saying here is: You cannot have ACID transactions without the C in CAP.

[dm_mongodb]

fwiw, here is the formal version of the theorem from the gilbert/lynch proof paper:

Theorem 1. It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: * Availability, * Atomic consistency, in all fair executions (including those in which messages are lost).

[kennu]

Without knowing much about it, I can imagine that chain replication could reduce the problem of copying data to every server from O(n) to something like O(log n).

But can it also manage simultaneous writes (of possibly conflicting data) to multiple masters, to achieve write scalability? Won't it get slowed down, checking every master for conflicts before committing?

[cx01]

You do not copy data to all servers; in practice you may choose a replication degree of 3, so all data is written to 3 servers. In chain replication the first server in the chain will decide on the order of writes (i.e. he will serialize the writes), which is very fast. In a P2P system you'll need to do some kind of distributed consensus for every write, which (when conflicts happen) will be much slower than having one node serialize the writes.

Having multiple masters will most likely add overhead for conflict resolution and should be avoided, but it's really orthogonal to the whole CAP stuff. If you allow writes to multiple masters without conflict resolution at write-time, then you will need to do the conflict-resolution at read-time, which is going to be much more complicated, because your read may yield multiple versions.

[kennu]

That was pretty much my original point about giving up consistency to achieve (write) scalability. E.g. CouchDB is based on that principle: You can write to all masters in parallel and the system provides a mechanism for resolving the conflicts afterwards.

[wmf]

If you keep adding servers indefinitely, it becomes slower and slower to commit every transaction to every server.

The point of database partitioning is that a transaction that doesn't span partitions only touches a constant number of servers (usually 2 or 3).

[kennu]

I would interpret that as a compromise where C, A and P are divided into some ratio (you still don't get 100% of each). I understand Cassandra does that well if the application fits the model.