5 ms·

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 g

by cx01 17y ago

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 17y ago
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 17y ago
  I know. I actually explained this not too long ago here: http://news.ycombinator.com/item?id=1191003 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 17y ago
  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 17y ago
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 17y ago
  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 17y ago
    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.

by cx01 17y ago

kingkilr 17y ago

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 17y ago
I know. I actually explained this not too long ago here: http://news.ycombinator.com/item?id=1191003 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 17y ago
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 17y ago

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 17y ago
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 17y ago
  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.