3 ms·

> "netsplits" exist in every distributed system, be it a chat app or a database, it's just the CAP theorem Well let's not get carried away. Network partitions

by throwaway20371 5y ago

> "netsplits" exist in every distributed system, be it a chat app or a database, it's just the CAP theorem Well let's not get carried away. Network partitions happen everywhere, but everything is not about the CAP theorem. CAP theorem is a very specific model that a lot of apps (even ACID databases) don't conform with. Comparing IRC to CAP theorem is like comparing it to ACID and saying, "IRC decided to sacrifice transaction integrity". IRC didn't explicitly sacrifice the C in CAP, they designed a simple server protocol. They could have added a bunch of weirdness to hide splits from users, but it would have been unnecessarily complicated and not contributed significantly to the user experience.

H8crilA 5y ago
I'm sorry but I don't think you realise how simple and fundamental the CAP theorem is. It's almost a tautology. And yes it applies fully. The most basic case is if there's absolutely no method of exchanging information from point A to point B. Then agents at A and B will not be able to communicate. That's it. Any system built to facilitate information exhange will either have to deliver incomplete information (C) or will have to refuse to operate (A). Now then, as I said, nowadays it's extremely unlikely that there's truly no connection between any two major Internet hubs (though it can happen, hello BGP). It still happens in specific systems that do not work on any method of information transfer but rather on specific methods of information transfer. The IRC example requires specific servers to be up, not just a functioning IP routing between the end clients. If some server is not up then (at least temporarily) from IRC's point of view there's no way to deliver information from A to B. The Google auth outage example requires (among most likely many other things) disk space availability on specific servers for information exchange to happen.
- throwaway20371 5y ago
  > The most basic case is if there's absolutely no method of exchanging information from point A to point B. Then agents at A and B will not be able to communicate. That's it. That's not it. The most basic case is if there's no linearizeability between A and B. A and B can continue communicating but fail the C in CAP if linearizeability fails. Hence we shouldn't compare everything to CAP.
- TheDong 5y ago
  > I don't think you realise how simple and fundamental the CAP theorem is May I recommend reading "A Critique of the CAP Theorum - Martin Kleppmann", available as a PDF here https://arxiv.org/abs/1509.05393 https://arxiv.org/abs/1509.05393 As that paper points out, your definition of CAP theorem is simplified and incomplete to the point of being wrong, as many are. As it also point out, CAP theorem doesn't really account for eventual consistency well. I would argue that a chat protocol is a good place to perform eventual consistency, and those tradeoffs work well. During network partitions, have both sides of the partition continue to accept messages. Have the client mark messages with random unique IDs, and have each server mark messages with a server timestamp. The well-defined merge operation is now to sort by server-time and dedupe by message ID, such that if a message is sent to two servers it only displays once. This doesn't work for IRC traditionally, since messages do not have unique IDs, and so no merge operation can deduplicate them, and servers do not store messages during netsplits (or at any time really), so they cannot be re-sent. However, a similar system exists for other chat systems. matrix is a federated system of multiple servers, and when partitions occur, each server will still accept new messages, and later those messages will be made available to other servers and merged in at the appropriate time. I think that CAP theorem's results are less interesting if you consider application-level resolutions to network issues (i.e. eventual consistency), and as I believe the paper also implies trotting it out constantly when talking about practical systems gets old fast.
  - H8crilA 5y ago
    If you can always merge reordered edits/messages then CAP does not apply because you don't need C (as defined in CAP), you may instead talk about partitions/connectivity issues as if they were some anomalous sources of large latencies in the system. You have your own, different definition of C. There are some very very large scale systems out there that work under the assumption that any edits can arrive reordered, and it's OK for the observable properties of the system. Here's what's "inconsistent" in an eventually consistent chat app: your typed responses might have been different had you seen in time what the other party has to say. To some degree the "computation" happens in your head. A "fully consistent" / "fully synchronous" chat app would sometimes refuse to send a message because the other party might have said something in the meantime. Like you'd expect from a fully-synchronous bank account balance handling system that wants to keep >= 0 balance at all times, rejecting overdraft transactions. (And I agree that this is completely acceptable behavior for a chat app; we as people are built to tolerate this kind of a problem in async person to person communication; just pointing out what does C in CAP exactly mean; the "fully synchronous" chat app would be just an occasional pain in the ass with little benefit)

H8crilA 5y ago

I'm sorry but I don't think you realise how simple and fundamental the CAP theorem is. It's almost a tautology. And yes it applies fully. The most basic case is if there's absolutely no method of exchanging information from point A to point B. Then agents at A and B will not be able to communicate. That's it. Any system built to facilitate information exhange will either have to deliver incomplete information (C) or will have to refuse to operate (A). Now then, as I said, nowadays it's extremely unlikely that there's truly no connection between any two major Internet hubs (though it can happen, hello BGP). It still happens in specific systems that do not work on any method of information transfer but rather on specific methods of information transfer. The IRC example requires specific servers to be up, not just a functioning IP routing between the end clients. If some server is not up then (at least temporarily) from IRC's point of view there's no way to deliver information from A to B. The Google auth outage example requires (among most likely many other things) disk space availability on specific servers for information exchange to happen.

throwaway20371 5y ago
> The most basic case is if there's absolutely no method of exchanging information from point A to point B. Then agents at A and B will not be able to communicate. That's it. That's not it. The most basic case is if there's no linearizeability between A and B. A and B can continue communicating but fail the C in CAP if linearizeability fails. Hence we shouldn't compare everything to CAP.
TheDong 5y ago
> I don't think you realise how simple and fundamental the CAP theorem is May I recommend reading "A Critique of the CAP Theorum - Martin Kleppmann", available as a PDF here https://arxiv.org/abs/1509.05393 https://arxiv.org/abs/1509.05393 As that paper points out, your definition of CAP theorem is simplified and incomplete to the point of being wrong, as many are. As it also point out, CAP theorem doesn't really account for eventual consistency well. I would argue that a chat protocol is a good place to perform eventual consistency, and those tradeoffs work well. During network partitions, have both sides of the partition continue to accept messages. Have the client mark messages with random unique IDs, and have each server mark messages with a server timestamp. The well-defined merge operation is now to sort by server-time and dedupe by message ID, such that if a message is sent to two servers it only displays once. This doesn't work for IRC traditionally, since messages do not have unique IDs, and so no merge operation can deduplicate them, and servers do not store messages during netsplits (or at any time really), so they cannot be re-sent. However, a similar system exists for other chat systems. matrix is a federated system of multiple servers, and when partitions occur, each server will still accept new messages, and later those messages will be made available to other servers and merged in at the appropriate time. I think that CAP theorem's results are less interesting if you consider application-level resolutions to network issues (i.e. eventual consistency), and as I believe the paper also implies trotting it out constantly when talking about practical systems gets old fast.
- H8crilA 5y ago
  If you can always merge reordered edits/messages then CAP does not apply because you don't need C (as defined in CAP), you may instead talk about partitions/connectivity issues as if they were some anomalous sources of large latencies in the system. You have your own, different definition of C. There are some very very large scale systems out there that work under the assumption that any edits can arrive reordered, and it's OK for the observable properties of the system. Here's what's "inconsistent" in an eventually consistent chat app: your typed responses might have been different had you seen in time what the other party has to say. To some degree the "computation" happens in your head. A "fully consistent" / "fully synchronous" chat app would sometimes refuse to send a message because the other party might have said something in the meantime. Like you'd expect from a fully-synchronous bank account balance handling system that wants to keep >= 0 balance at all times, rejecting overdraft transactions. (And I agree that this is completely acceptable behavior for a chat app; we as people are built to tolerate this kind of a problem in async person to person communication; just pointing out what does C in CAP exactly mean; the "fully synchronous" chat app would be just an occasional pain in the ass with little benefit)