4 ms·

To some commenters: the C in CAP and the C in ACID are not the same thing. If that is not clear to you, it is unlikely the database you develop will include co

To some commenters: the C in CAP and the C in ACID are not the same thing. If that is not clear to you, it is unlikely the database you develop will include correct implementations of core concepts. Knowledge is power. Peace and love to the human family. - Lil' B

mshneider718 15y ago
Good point...CAP and ACID are not overlapping concepts - in fact, you kinda have to throw out ACID rules when you create a Dynamo-inspired data store
- roder 15y ago
  Of course the opposite of ACID is BASE: http://queue.acm.org/detail.cfm?id=1394128 http://queue.acm.org/detail.cfm?id=1394128
haberman 15y ago
> To some commenters: the C in CAP and the C in ACID are not the same thing. This is an interesting point, but I wonder if they are really that different. Even NoSQL systems support atomic updates and sequential consistency at some granularity (like a single key, document, etc.) I wonder if it's really so inaccurate to think of NoSQL data stores as a set of tiny ACID databases, one for each key/document/etc.
- benblack 15y ago
  They really are that different, and I hear 10gen is hiring. Increase the peace. - Lil' B
  - haberman 15y ago
    That's deep man, but I posed an actual question. BigTable (which I use daily and have extensive experience with) offers atomic and transactional updates at the row level. It uses Paxos to guarantee that at most one process at a time owns each row and can mutate it. That process keeps a sequential log that imposes an absolute order over updates to that row. So it appears to me that despite being a NoSQL database, BigTable rows offer both ACID and the "C" of CAP. In fact, I bet it would be possible to implement a MySQL backend that uses a BigTable row as its storage. I get strlen's point that C != C (it's more analogous to A/I), but my real point is that NoSQL (at least in the case of BigTable) doesn't appear to be fundamentally different than SQL in the offered guarantees, but rather in the granularity at which those guarantees are offered. NoSQL just takes the traditional one-single-ACID-entity model (a SQL database) and breaks it apart into lots of little ACID entities called rows/keys/documents/etc. CAP of course applies to both SQL and NoSQL equally.
    - mmalone 15y ago
      BigTable enforces integrity constraints defined by a schema on a per-row basis? This is interesting news. Why hasn't Google included this information in any of the published materials describing the system? - Forever Malone
      - haberman 15y ago
        What about this story is inspiring people to write smarmy comments and sign them with silly pseudonyms? Bigtable itself doesn't provide a schema or constraints, but it provides primitives that would allow you to implement them AFAICS. That's why I mentioned the idea of implementing a MySQL backend that uses BigTable as its storage -- MySQL would contain the schema and constraint logic, BigTable would provide the sequentially-consistent data storage.
    - benblack 15y ago
      I was not aware that BigTable worked that way, but it doesn't change my original point about "C != C". That a given NoSQL system is architected for both does not imply that such a design is always desirable or representative of the NoSQL database space. It is not and it is not. Thank you for your kind and compassionate suggestions about signing comments. - Lil' B
  - haberman 15y ago
    ps. no need to sign your comments here: http://ycombinator.com/newsguidelines.html http://ycombinator.com/newsguidelines.html
strlen 15y ago
Just to expand on this, the "C" in CAP corresponds (roughly) to the "A" and "I" in ACID. Atomicity across multiple nodes requires consensus. According to FLP Impossibility Result (CAP is a very elegant and intuitive re-statement of FLP), consensus is impossible in a network that may drop or deliver packets. Serializable isolation level requires that operations are totally ordered: total ordering on multiple nodes, requires solving the "atomic multicast" problem which is a private instance of the general consensus problem. In practice, you can achieve consensus across multiple nodes with a reasonable amount of fault tolerance if you are willing to accept high (as in, hundreds of milliseconds) latency bounds. That's a loss of availability that's not acceptable to many applications. This means, that you can't build a low-latency multi-master system that achieves the "A" and "I" guarantees. Thus, distributed systems that wish to achieve a greater form of consistency typically (Megastore from Google being a notable exception, at the cost of 140ms latency) choose master slave systems (with "floating masters" for fault tolerance). In these systems availability is lost for a short period of time in case the master fails. BigTable (or HBase) is an example of this: (grand simplification follows) when a tablet master (RegionServer in HBase) for a specific token range fails, availability is lost until other nodes take over the "master-less" token range. These are not binary "on/off" switches: see Yahoo's PNUTS for a great "middle of the road" system. The paper < http://research.yahoo.com/node/2304 http://research.yahoo.com/node/2304 > has an intuitive example explaining the various consistency models. Note: in a partitioned system, the scope of consistency guarantees (that is, any consistency guarantees: eventual or not) is typically limited to (at best) a single partition of a "table group"/"entity group" (in Microsoft Azure Cloud SQL Server and Google Megastore, respectively), a single partition of a table (usual sharded MySQL setups) or just a single row in a table (BigTable) or document in a document oriented store. Atomic and isolated cross row transactions are impractical on commodity hardware (and are limited even in systems that mandate the use of infiband interconnect and high-performance SSDs). [Disclaimer: I am commiter on Project Voldemort, a Dynamo implementation; in addition to Dynamo, I also find Yahoo's PNUTS and Google's BigTable to be very interesting architectures.]
- benblack 15y ago
  Thanks for bringing some much needed science to these proceedings, my man. Too many people mistaking computer science for a therapy session where their feelings matter. Computer science has much in common with the honey badger. Think upon this and be enlightened. Yours in perpetual discovery, - Lil' B

mshneider718 15y ago

Good point...CAP and ACID are not overlapping concepts - in fact, you kinda have to throw out ACID rules when you create a Dynamo-inspired data store

roder 15y ago
Of course the opposite of ACID is BASE: http://queue.acm.org/detail.cfm?id=1394128 http://queue.acm.org/detail.cfm?id=1394128

haberman 15y ago

> To some commenters: the C in CAP and the C in ACID are not the same thing. This is an interesting point, but I wonder if they are really that different. Even NoSQL systems support atomic updates and sequential consistency at some granularity (like a single key, document, etc.) I wonder if it's really so inaccurate to think of NoSQL data stores as a set of tiny ACID databases, one for each key/document/etc.

benblack 15y ago
They really are that different, and I hear 10gen is hiring. Increase the peace. - Lil' B
- haberman 15y ago
  That's deep man, but I posed an actual question. BigTable (which I use daily and have extensive experience with) offers atomic and transactional updates at the row level. It uses Paxos to guarantee that at most one process at a time owns each row and can mutate it. That process keeps a sequential log that imposes an absolute order over updates to that row. So it appears to me that despite being a NoSQL database, BigTable rows offer both ACID and the "C" of CAP. In fact, I bet it would be possible to implement a MySQL backend that uses a BigTable row as its storage. I get strlen's point that C != C (it's more analogous to A/I), but my real point is that NoSQL (at least in the case of BigTable) doesn't appear to be fundamentally different than SQL in the offered guarantees, but rather in the granularity at which those guarantees are offered. NoSQL just takes the traditional one-single-ACID-entity model (a SQL database) and breaks it apart into lots of little ACID entities called rows/keys/documents/etc. CAP of course applies to both SQL and NoSQL equally.
  - mmalone 15y ago
    BigTable enforces integrity constraints defined by a schema on a per-row basis? This is interesting news. Why hasn't Google included this information in any of the published materials describing the system? - Forever Malone
    - haberman 15y ago
      What about this story is inspiring people to write smarmy comments and sign them with silly pseudonyms? Bigtable itself doesn't provide a schema or constraints, but it provides primitives that would allow you to implement them AFAICS. That's why I mentioned the idea of implementing a MySQL backend that uses BigTable as its storage -- MySQL would contain the schema and constraint logic, BigTable would provide the sequentially-consistent data storage.
  - benblack 15y ago
    I was not aware that BigTable worked that way, but it doesn't change my original point about "C != C". That a given NoSQL system is architected for both does not imply that such a design is always desirable or representative of the NoSQL database space. It is not and it is not. Thank you for your kind and compassionate suggestions about signing comments. - Lil' B
- haberman 15y ago
  ps. no need to sign your comments here: http://ycombinator.com/newsguidelines.html http://ycombinator.com/newsguidelines.html

strlen 15y ago

Just to expand on this, the "C" in CAP corresponds (roughly) to the "A" and "I" in ACID. Atomicity across multiple nodes requires consensus. According to FLP Impossibility Result (CAP is a very elegant and intuitive re-statement of FLP), consensus is impossible in a network that may drop or deliver packets. Serializable isolation level requires that operations are totally ordered: total ordering on multiple nodes, requires solving the "atomic multicast" problem which is a private instance of the general consensus problem. In practice, you can achieve consensus across multiple nodes with a reasonable amount of fault tolerance if you are willing to accept high (as in, hundreds of milliseconds) latency bounds. That's a loss of availability that's not acceptable to many applications. This means, that you can't build a low-latency multi-master system that achieves the "A" and "I" guarantees. Thus, distributed systems that wish to achieve a greater form of consistency typically (Megastore from Google being a notable exception, at the cost of 140ms latency) choose master slave systems (with "floating masters" for fault tolerance). In these systems availability is lost for a short period of time in case the master fails. BigTable (or HBase) is an example of this: (grand simplification follows) when a tablet master (RegionServer in HBase) for a specific token range fails, availability is lost until other nodes take over the "master-less" token range. These are not binary "on/off" switches: see Yahoo's PNUTS for a great "middle of the road" system. The paper < http://research.yahoo.com/node/2304 http://research.yahoo.com/node/2304 > has an intuitive example explaining the various consistency models. Note: in a partitioned system, the scope of consistency guarantees (that is, any consistency guarantees: eventual or not) is typically limited to (at best) a single partition of a "table group"/"entity group" (in Microsoft Azure Cloud SQL Server and Google Megastore, respectively), a single partition of a table (usual sharded MySQL setups) or just a single row in a table (BigTable) or document in a document oriented store. Atomic and isolated cross row transactions are impractical on commodity hardware (and are limited even in systems that mandate the use of infiband interconnect and high-performance SSDs). [Disclaimer: I am commiter on Project Voldemort, a Dynamo implementation; in addition to Dynamo, I also find Yahoo's PNUTS and Google's BigTable to be very interesting architectures.]

benblack 15y ago
Thanks for bringing some much needed science to these proceedings, my man. Too many people mistaking computer science for a therapy session where their feelings matter. Computer science has much in common with the honey badger. Think upon this and be enlightened. Yours in perpetual discovery, - Lil' B