5 ms·

A CAP tradeoff in the wild

35 points by r4um 3y ago

macintux 3y ago
I’m curious whether “CAP” was normalized by the submitter or HN. Should be more easily recognizable in its original form.
- dang 3y ago
  Software did it. Fixed now.
lokar 3y ago
This is not all that novel. Lots of consistent systems have caches. The standard approach is to let the client decide: do you need a 100% consistent value (very rare) or would you rather set a staleness threshold. If the cache is not sure it is within that threshold (via some feed of invalidations) the read fails and you try another cache server.
- user32489318 3y ago
  In distributed storage! 100% consistent storage (not eventual consistent storage like s3) is still important for many transactional cases.
- belter 3y ago
  Or you end up with a broken container orchestrator: https://news.ycombinator.com/item?id=38834345 https://news.ycombinator.com/item?id=38834345
koliber 3y ago
There are only two hard things in Computer Science: cache invalidation and naming things. -- Phil Karlton I wonder if naming things is also tied in some way to the CAP theorem, or some other "difficult" tradeoff or mathemtically-hard thing.
- amw-zero 3y ago
  The mathematical intuition for why naming things is hard is definitely tied to information theory and semantics (linguistics). Names communicate bits of information, and they describe a semantic concept. When a name isn't accurate, it's not communicating enough bits, OR the reader isn't familiar enough with what the bits mean - the semantics of the bits. If the name is too vague, you have to expand it to send more bits, which can be hard to perfectly capture. If the name is accurate but the reader doesn't understand (as often happens when say reading academic papers), then it's an education issue.
  - genman 3y ago
    And education can be viewed as problem of consistent shared state.
    - amw-zero 3y ago
      That’s so true.
- nonameiguess 3y ago
  Naming is hard for a huge variety of reasons and it isn't only hard in computer science. Witness the spectacle in North American pro sports from the last few years over things like an NFL franchise calling itself the "Washington Football Team" for two seasons. My company has changed its name twice in the past three years, first because the original name was the name of a single product but then we went on to make other products, then because the new name reflected a particular customer focus and that focus expanded to encompass different customers. Names are often assumed to be stable identifiers. Sometimes they are used as unique identifiers. Yet not only companies but humans and many other things can often change their names or share the same name. Consider even where names must be unique. Is DNS an example? Why? IPs have to be unique or the routing system wouldn't know where to send packets, but if wish to map human-memorable names to IP addresses, must that really be unique? Well, first it isn't. DNS is used as a load-balancing mechanism and even IP itself can be multicast. One name can map to many destinations. But the names are still assumed to be unique in the sense that repeated requests for a record within its own time to live should always return the same record. Names are assumed to belong to some entity with the authority to create, update, and delete those records. Who should that authority be? If we're talking about street names in the same zip code, presumably its a municipal government with authority over that zip code. Human names, its their parents at birth and eventually themselves when they get old enough to have own full set of legal rights. For DNS, its authoritative root servers for a top-level domain, which delegates the authority to registrars. However, things like handshake protocol also exist allowing subsets of IP users to agree upon temporary authorities without the entire web having to buy in. The same applies in private networks where any arbitrary individual or group can run their own DNS server and point whatever name they want to whatever address they want, ignoring authoritative name servers, TLDs, and roots. What should we do about domain squatting? In DNS, we charge money to claim ownership of a name. Many dependency management systems implement a namespacing system that simply piggybacks on DNS and prefixes identifiers with an organizational name that is usually a domain name. Some do nothing and the "vector" library will forever be whoever published first, even if it is an empty package, unrelated to vectors, and/or unmaintained. Should a name have a human-intellible meaning at all? "Hacker News" was chosen because it serves links to news meant to be appealing to people who consider themselves hackers. "Kubernetes" is a Greek word for the helmsman of a ship, meant to allude to a controller of a containerized shipping vessel because it is a system that controls containerized services that are remotely addressable using IP and DNS. These meanings are both ephemeral, but for how long? If Kubernetes eventually supports orchestration of non-containerized services, should the name change? If the common usage of the word "hacker" changes, should Hacker News change its name? What if it starts serving different kinds of news that isn't specifically meant to appeal to hackers? Content-addressing systems sidestep this by not bothering to make names human-intelligible, but now you need a hashing algorithm with sufficient collision resistance and you're also beholden to the assumption that a bit sequence in and of itself defines identity, that changing the metadata of a file format used to host the movie Titanic should mean it now has a new name even if the semantic content is the same. Naming is hard in part because of a conflict between the desire for an identifier that can be used for some "long" time and the fact that usage, context, and even identity itself might not actually last very long. Philosopher have tried for at least thousands of years and can't even widely agree on how to define identity at all. Does it make sense for GE to spin off its banking division and call it "Ally Bank?" That Blackwater can respond to every controversy by changing its DBA and hoping people forget who they are? Is heredity a stable enough enough identifier that anyone should feel guilty about what their ancestors did a century ago? Is race? Is nationality? What about organizational identity? Is the CIA culpable for MK Ultra if no person in the agency was part of it when that happened and all of its policies have since changed? These are all just variants of the unanswerable questions posed by the Ship of Theseus. The linguistic variant is the paradox of word meaning itself. Words and their referents change over time but at different rates. Not all users of a common language necessarily agree on all meanings at exactly the same time. Proper nouns are no different but bring in a whole slew of additional questions related to what defines a category, what defines an individual, and who even has the right to change the meaning of a word that has personal meaning to some persons. If everyone starts calling you by a different name, public records all get updated, but you didn't agree to it, did your name actually change?

35 points by r4um 3y ago

I’m curious whether “CAP” was normalized by the submitter or HN. Should be more easily recognizable in its original form.

dang 3y ago
Software did it. Fixed now.

lokar 3y ago

This is not all that novel. Lots of consistent systems have caches. The standard approach is to let the client decide: do you need a 100% consistent value (very rare) or would you rather set a staleness threshold. If the cache is not sure it is within that threshold (via some feed of invalidations) the read fails and you try another cache server.

user32489318 3y ago
In distributed storage! 100% consistent storage (not eventual consistent storage like s3) is still important for many transactional cases.
belter 3y ago
Or you end up with a broken container orchestrator: https://news.ycombinator.com/item?id=38834345 https://news.ycombinator.com/item?id=38834345

koliber 3y ago

There are only two hard things in Computer Science: cache invalidation and naming things. -- Phil Karlton I wonder if naming things is also tied in some way to the CAP theorem, or some other "difficult" tradeoff or mathemtically-hard thing.

amw-zero 3y ago
The mathematical intuition for why naming things is hard is definitely tied to information theory and semantics (linguistics). Names communicate bits of information, and they describe a semantic concept. When a name isn't accurate, it's not communicating enough bits, OR the reader isn't familiar enough with what the bits mean - the semantics of the bits. If the name is too vague, you have to expand it to send more bits, which can be hard to perfectly capture. If the name is accurate but the reader doesn't understand (as often happens when say reading academic papers), then it's an education issue.
- genman 3y ago
  And education can be viewed as problem of consistent shared state.
  - amw-zero 3y ago
    That’s so true.
nonameiguess 3y ago
Naming is hard for a huge variety of reasons and it isn't only hard in computer science. Witness the spectacle in North American pro sports from the last few years over things like an NFL franchise calling itself the "Washington Football Team" for two seasons. My company has changed its name twice in the past three years, first because the original name was the name of a single product but then we went on to make other products, then because the new name reflected a particular customer focus and that focus expanded to encompass different customers. Names are often assumed to be stable identifiers. Sometimes they are used as unique identifiers. Yet not only companies but humans and many other things can often change their names or share the same name. Consider even where names must be unique. Is DNS an example? Why? IPs have to be unique or the routing system wouldn't know where to send packets, but if wish to map human-memorable names to IP addresses, must that really be unique? Well, first it isn't. DNS is used as a load-balancing mechanism and even IP itself can be multicast. One name can map to many destinations. But the names are still assumed to be unique in the sense that repeated requests for a record within its own time to live should always return the same record. Names are assumed to belong to some entity with the authority to create, update, and delete those records. Who should that authority be? If we're talking about street names in the same zip code, presumably its a municipal government with authority over that zip code. Human names, its their parents at birth and eventually themselves when they get old enough to have own full set of legal rights. For DNS, its authoritative root servers for a top-level domain, which delegates the authority to registrars. However, things like handshake protocol also exist allowing subsets of IP users to agree upon temporary authorities without the entire web having to buy in. The same applies in private networks where any arbitrary individual or group can run their own DNS server and point whatever name they want to whatever address they want, ignoring authoritative name servers, TLDs, and roots. What should we do about domain squatting? In DNS, we charge money to claim ownership of a name. Many dependency management systems implement a namespacing system that simply piggybacks on DNS and prefixes identifiers with an organizational name that is usually a domain name. Some do nothing and the "vector" library will forever be whoever published first, even if it is an empty package, unrelated to vectors, and/or unmaintained. Should a name have a human-intellible meaning at all? "Hacker News" was chosen because it serves links to news meant to be appealing to people who consider themselves hackers. "Kubernetes" is a Greek word for the helmsman of a ship, meant to allude to a controller of a containerized shipping vessel because it is a system that controls containerized services that are remotely addressable using IP and DNS. These meanings are both ephemeral, but for how long? If Kubernetes eventually supports orchestration of non-containerized services, should the name change? If the common usage of the word "hacker" changes, should Hacker News change its name? What if it starts serving different kinds of news that isn't specifically meant to appeal to hackers? Content-addressing systems sidestep this by not bothering to make names human-intelligible, but now you need a hashing algorithm with sufficient collision resistance and you're also beholden to the assumption that a bit sequence in and of itself defines identity, that changing the metadata of a file format used to host the movie Titanic should mean it now has a new name even if the semantic content is the same. Naming is hard in part because of a conflict between the desire for an identifier that can be used for some "long" time and the fact that usage, context, and even identity itself might not actually last very long. Philosopher have tried for at least thousands of years and can't even widely agree on how to define identity at all. Does it make sense for GE to spin off its banking division and call it "Ally Bank?" That Blackwater can respond to every controversy by changing its DBA and hoping people forget who they are? Is heredity a stable enough enough identifier that anyone should feel guilty about what their ancestors did a century ago? Is race? Is nationality? What about organizational identity? Is the CIA culpable for MK Ultra if no person in the agency was part of it when that happened and all of its policies have since changed? These are all just variants of the unanswerable questions posed by the Ship of Theseus. The linguistic variant is the paradox of word meaning itself. Words and their referents change over time but at different rates. Not all users of a common language necessarily agree on all meanings at exactly the same time. Proper nouns are no different but bring in a whole slew of additional questions related to what defines a category, what defines an individual, and who even has the right to change the meaning of a word that has personal meaning to some persons. If everyone starts calling you by a different name, public records all get updated, but you didn't agree to it, did your name actually change?