10 ms·

"There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors."

by fla 6y ago

Tade0 6y ago
Nobody ever gets this one when I say it.
pwdisswordfish2 6y ago
Can I ask a stupid question about this? I’ve always wondered what this quote really means. It seems obvious that the author deems “cache invalidation” to be badly or awkwardly named, but is that really the joke? Isn’t cache invalidation a pretty straightforward term? Maybe I don’t feel the awkwardness as much as a native English speaker? Or is it literally that cache invalidation is hard? Isn’t cache invalidation on a completely different level as naming things, both conceptually and in difficulty?
- mcherm 6y ago
  No, it is not intended to be badly or awkwardly named. It really is the case that properly invalidating caches is surprisingly hard to do and is the root cause of many, many bugs. Of course, the term is intended to be taken broadly: "cache invalidation" includes everything from CPU level cash coherence issues with multi-processors to the maintenance of ACID compliance in a database, and probably even includes cases where a mutable variable is reused incorrectly.
- Someone 6y ago
  Throwing away cached data may not be hard, but knowing (actually, ‘guessing’ often better describes it) what to throw away is. “First in, first out” may seem fine at first sight, but if your access pattern is periodic, it may mean you just threw away the data you need, and kept around data you won’t need for 11, 10, 9, 8,… months. Also, why throw away data that’s needed, statistically, once a second, and keep the data that was read in for that one of a time query? Also, quality of service might affect caching choices. If you need room on a factory floor, you don’t move the fire extinguisher to the back room, even though you know you likely will not use it. Similarly, you might want to prefer caching data of web pages more likely to be visited, or even that of customers paying more.
  - PeterisP 6y ago
    Cache invalidation is not about effectively caching immutable values (where FIFO or least recently used may be valid solutions) but about the problem of caching mutable values, the hard part is ensuring correctness without having to clear all caches everywhere whenever something changes. Properly ensuring that when a value changes (and thus any cached copies become invalid) then every place where that value might be cached properly and timely invalidates [that part] of the cache, because otherwise other parts of the system will see stale/wrong/conflicting data which generally results in 'fun'. And it appears everywhere from memory reads in a single multicore processor (where one core might change a variable that the other core has cached) to globally distributed data storage systems with eventual consistency to state shown on the user's screen as the underlying data is getting mutated by someone/something else.
- jraph 6y ago
  I don't think this quote implies that cache invalidation is badly named. It's just one hard thing to do. To me the point of this quote / the joke is the off-by-one error applying to this list itself. To me, the original quote, "There are 2 hard problems in computer science: cache invalidation and naming things" is intended to be striking by putting naming things at the same level of difficulty as cache invalidation, while naming things might seem an easy problem… at first. The point of the quote is to be a warning on the fact that while cache invalidation is notoriously hard, naming things is hard too.
  - pwdisswordfish2 6y ago
    >To me, the original quote, "There are 2 hard problems in computer science: cache invalidation and naming things" is intended to be striking by putting naming things at the same level of difficulty as cache invalidation, while naming things might seem an easy problem… Ah, that makes sense to me, thanks. I just figured the difficulty levels the other way around, so the “punchline” couldn’t work. Guess I’m glad the most complicated caches I work with are mostly “if it’s at least this old, refresh it” ;)
    - freshhawk 6y ago
      "this old" according to what clock? What if the refresh fails or times out? Do you keep the old value there until a refresh succeeds? etc, etc, etc. Even that simple example is not remotely easy if "if it's at least this old, refresh it" is an actual requirement. Thankfully most of the time it's not, and the requirement is actually "refresh it every once in a while, about this often, but none of this is particularly important so it doesn't have to always work"
- olau 6y ago
  It didn't start off as a joke: https://www.martinfowler.com/bliki/TwoHardThings.html https://www.martinfowler.com/bliki/TwoHardThings.html If you're not careful with what you cache, you end up with bugs unless you invalidate the cache carefully. And doing that carefully is in itself surprisingly difficult and error-prone, unless you come up with a comprehensive scheme, at which point you probably no longer have a what we call a cache but more like a secondary index with performance/concurrency problems on it own. It doesn't seem hard until you've been there and given up. I think the same is true for naming. If you told someone new at programming that naming is the most difficult part, they'd laugh at you and continue using quickly thought up, confusing names that cause them to introduce bugs because they misunderstand themselves.
- barkingcat 6y ago
  the joke is the off by one error. 3 instead of 2. Cache invalidation is a true challenge. Naming things is a true challenge too. Same level of complexity (if not more) as cache invalidation since it deals with psychology of the user/programmer, patterns of thinking, etc.
- loopz 6y ago
  Caching isn't just hard, it adds complexity for which the costs and flaws are often obscure, especially in separate changing components and over time. Caching facts (events) isn't caching, but a legitimate copy that is forever true. Naming things is "hard", as names tend to stick forever. Later, names may miss the moving target of recent changes. Off by 1 errors, refers to the list itself (joke). You either spend extra effort reducing their possibility upfront, or get dragged into hours/days trying to dechiper only to discover it was a off by 1 error. Programming needs to be exact, to be correct, and very few are consistently avoiding such subtle flaws in code logic. When you have to explain the joke, it's not funny anymore! :D
- detaro 6y ago
  > Or is it literally that cache invalidation is hard? Yes. It's a problem that repeats across the computing stack, can cause maddening edge-case errors, and doesn't (can't, in the general case) have a clear perfect solution.
- craigsmansion 6y ago
  > Or is it literally that cache invalidation is hard? It's literally that cache invalidation is hard. You can also think of "cache invalidation" as a substitute of concurrent programming: keeping multiple related threads of logic synchronised. >Isn’t cache invalidation on a completely different level as naming things, both conceptually and in difficulty? I'd say it's on a conceptually different level, but not less difficult, and because "naming things" is easy, it's more insidious. From my point of view "naming things" is a substitute for architecting software instead of coding your way out of dead ends whilst inventing a lot of off the cuff names in the process. (of course, in the current climate, such ad-hoc solutions are now the standard, called "design patterns", and people find names that have "Factory" in them twice a normal thing.)
  - Sesse__ 6y ago
    No, naming things is really hard. Well, giving things (functions, variables, classes, algorithms) _bad_ names is easy, giving them good names is hard. For instance, when did you last see a class called <something>Manager? Then consider the fact that “manager” means absolutely nothing.
    - uryga 6y ago
      > “manager” means absolutely nothing do you know a better name for "window manager"? i don't mean to hold that up as a paragon of great naming, just genuinely curious what you'd call it. like, i'm no fan of AbstractFactories (or classes for that matter), but i never quite got this sentiment. to me, "manager" suggests that you have a bunch of resources that should be centrally managed (created/freed, whatever), and theres's something (perhaps an object) that handles that. ofc it's really generic, and a more concrete name should be used if possible, but i wouldn't say it's meaningless
    - HelloNurse 6y ago
      Both cache invalidation and naming things are hard activities because they require precognition to be done well.
    - fegu 6y ago
- akavel 6y ago
  Additionally to what others wrote in their replies, I think in a broader sense, "cache invalidation" actually kinda means a fundamental balance you need to decide on when programming, of what data/information you store vs. what you calculate on the fly. Whenever you're storing some results of some calculation, it's de facto caching the calculation. As to naming things, I seem to feel that good naming tends to go hand in hand with good abstractions, good model of the world; this is not as easy as "copying" relations from the real world to the computer (your stereotypical "cat is-a animal" which may result in surprising problems), but finding models and ideas that are at the same time simple & elastic & robust at representing some core essential concepts of the real world. Sorry I can't give specific examples, I feel those moments are often surprisingly vague and local. Also, I may just be overinterpreting this quote...
- hathawsh 6y ago
  Both cache invalidation and naming are easy on the surface but surprisingly complicated and prone to error. Cache invalidation has a risk of both false positives (something got evicted from the cache but shouldn't have) and false negatives (something should have been evicted but was not) and the effects of errors can be invisible, annoying, or disastrous, depending on the situation. Incorrect cache invalidation usually results from incorrect dependency management. Naming is hard because names have a conflicting combination of requirements: names need to be short (they will be repeated often), expressive, accurate, unchanging, and easy to remember. It's often quite difficult to find a name for a concept that fits all those requirements. My company has spent years finding the right names for certain core concepts, but that is time well spent.
seer 6y ago
To be honest with all the tooling around programming languages nowadays I haven’t encountered a bug caused by off-by-one error in years. The other two though ... yeah still true :)
- kohtatsu 6y ago
  Really? You must have some smart tooling.
jsilence 6y ago
Actually funny. Thanks!
zeckalpha 6y ago
That looks like 10 problems to me, if you include binary encoding issues.

"There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors."

by fla 6y ago

"There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors."

Tade0 6y ago

Nobody ever gets this one when I say it.

pwdisswordfish2 6y ago

Can I ask a stupid question about this? I’ve always wondered what this quote really means. It seems obvious that the author deems “cache invalidation” to be badly or awkwardly named, but is that really the joke? Isn’t cache invalidation a pretty straightforward term? Maybe I don’t feel the awkwardness as much as a native English speaker? Or is it literally that cache invalidation is hard? Isn’t cache invalidation on a completely different level as naming things, both conceptually and in difficulty?

mcherm 6y ago
No, it is not intended to be badly or awkwardly named. It really is the case that properly invalidating caches is surprisingly hard to do and is the root cause of many, many bugs. Of course, the term is intended to be taken broadly: "cache invalidation" includes everything from CPU level cash coherence issues with multi-processors to the maintenance of ACID compliance in a database, and probably even includes cases where a mutable variable is reused incorrectly.
Someone 6y ago
Throwing away cached data may not be hard, but knowing (actually, ‘guessing’ often better describes it) what to throw away is. “First in, first out” may seem fine at first sight, but if your access pattern is periodic, it may mean you just threw away the data you need, and kept around data you won’t need for 11, 10, 9, 8,… months. Also, why throw away data that’s needed, statistically, once a second, and keep the data that was read in for that one of a time query? Also, quality of service might affect caching choices. If you need room on a factory floor, you don’t move the fire extinguisher to the back room, even though you know you likely will not use it. Similarly, you might want to prefer caching data of web pages more likely to be visited, or even that of customers paying more.
- PeterisP 6y ago
  Cache invalidation is not about effectively caching immutable values (where FIFO or least recently used may be valid solutions) but about the problem of caching mutable values, the hard part is ensuring correctness without having to clear all caches everywhere whenever something changes. Properly ensuring that when a value changes (and thus any cached copies become invalid) then every place where that value might be cached properly and timely invalidates [that part] of the cache, because otherwise other parts of the system will see stale/wrong/conflicting data which generally results in 'fun'. And it appears everywhere from memory reads in a single multicore processor (where one core might change a variable that the other core has cached) to globally distributed data storage systems with eventual consistency to state shown on the user's screen as the underlying data is getting mutated by someone/something else.
jraph 6y ago
I don't think this quote implies that cache invalidation is badly named. It's just one hard thing to do. To me the point of this quote / the joke is the off-by-one error applying to this list itself. To me, the original quote, "There are 2 hard problems in computer science: cache invalidation and naming things" is intended to be striking by putting naming things at the same level of difficulty as cache invalidation, while naming things might seem an easy problem… at first. The point of the quote is to be a warning on the fact that while cache invalidation is notoriously hard, naming things is hard too.
- pwdisswordfish2 6y ago
  >To me, the original quote, "There are 2 hard problems in computer science: cache invalidation and naming things" is intended to be striking by putting naming things at the same level of difficulty as cache invalidation, while naming things might seem an easy problem… Ah, that makes sense to me, thanks. I just figured the difficulty levels the other way around, so the “punchline” couldn’t work. Guess I’m glad the most complicated caches I work with are mostly “if it’s at least this old, refresh it” ;)
  - freshhawk 6y ago
    "this old" according to what clock? What if the refresh fails or times out? Do you keep the old value there until a refresh succeeds? etc, etc, etc. Even that simple example is not remotely easy if "if it's at least this old, refresh it" is an actual requirement. Thankfully most of the time it's not, and the requirement is actually "refresh it every once in a while, about this often, but none of this is particularly important so it doesn't have to always work"
olau 6y ago
It didn't start off as a joke: https://www.martinfowler.com/bliki/TwoHardThings.html https://www.martinfowler.com/bliki/TwoHardThings.html If you're not careful with what you cache, you end up with bugs unless you invalidate the cache carefully. And doing that carefully is in itself surprisingly difficult and error-prone, unless you come up with a comprehensive scheme, at which point you probably no longer have a what we call a cache but more like a secondary index with performance/concurrency problems on it own. It doesn't seem hard until you've been there and given up. I think the same is true for naming. If you told someone new at programming that naming is the most difficult part, they'd laugh at you and continue using quickly thought up, confusing names that cause them to introduce bugs because they misunderstand themselves.
barkingcat 6y ago
the joke is the off by one error. 3 instead of 2. Cache invalidation is a true challenge. Naming things is a true challenge too. Same level of complexity (if not more) as cache invalidation since it deals with psychology of the user/programmer, patterns of thinking, etc.
loopz 6y ago
Caching isn't just hard, it adds complexity for which the costs and flaws are often obscure, especially in separate changing components and over time. Caching facts (events) isn't caching, but a legitimate copy that is forever true. Naming things is "hard", as names tend to stick forever. Later, names may miss the moving target of recent changes. Off by 1 errors, refers to the list itself (joke). You either spend extra effort reducing their possibility upfront, or get dragged into hours/days trying to dechiper only to discover it was a off by 1 error. Programming needs to be exact, to be correct, and very few are consistently avoiding such subtle flaws in code logic. When you have to explain the joke, it's not funny anymore! :D
detaro 6y ago
> Or is it literally that cache invalidation is hard? Yes. It's a problem that repeats across the computing stack, can cause maddening edge-case errors, and doesn't (can't, in the general case) have a clear perfect solution.
craigsmansion 6y ago
> Or is it literally that cache invalidation is hard? It's literally that cache invalidation is hard. You can also think of "cache invalidation" as a substitute of concurrent programming: keeping multiple related threads of logic synchronised. >Isn’t cache invalidation on a completely different level as naming things, both conceptually and in difficulty? I'd say it's on a conceptually different level, but not less difficult, and because "naming things" is easy, it's more insidious. From my point of view "naming things" is a substitute for architecting software instead of coding your way out of dead ends whilst inventing a lot of off the cuff names in the process. (of course, in the current climate, such ad-hoc solutions are now the standard, called "design patterns", and people find names that have "Factory" in them twice a normal thing.)
- Sesse__ 6y ago
  No, naming things is really hard. Well, giving things (functions, variables, classes, algorithms) _bad_ names is easy, giving them good names is hard. For instance, when did you last see a class called <something>Manager? Then consider the fact that “manager” means absolutely nothing.
  - uryga 6y ago
    > “manager” means absolutely nothing do you know a better name for "window manager"? i don't mean to hold that up as a paragon of great naming, just genuinely curious what you'd call it. like, i'm no fan of AbstractFactories (or classes for that matter), but i never quite got this sentiment. to me, "manager" suggests that you have a bunch of resources that should be centrally managed (created/freed, whatever), and theres's something (perhaps an object) that handles that. ofc it's really generic, and a more concrete name should be used if possible, but i wouldn't say it's meaningless
  - HelloNurse 6y ago
    Both cache invalidation and naming things are hard activities because they require precognition to be done well.
  - fegu 6y ago
akavel 6y ago
Additionally to what others wrote in their replies, I think in a broader sense, "cache invalidation" actually kinda means a fundamental balance you need to decide on when programming, of what data/information you store vs. what you calculate on the fly. Whenever you're storing some results of some calculation, it's de facto caching the calculation. As to naming things, I seem to feel that good naming tends to go hand in hand with good abstractions, good model of the world; this is not as easy as "copying" relations from the real world to the computer (your stereotypical "cat is-a animal" which may result in surprising problems), but finding models and ideas that are at the same time simple & elastic & robust at representing some core essential concepts of the real world. Sorry I can't give specific examples, I feel those moments are often surprisingly vague and local. Also, I may just be overinterpreting this quote...
hathawsh 6y ago
Both cache invalidation and naming are easy on the surface but surprisingly complicated and prone to error. Cache invalidation has a risk of both false positives (something got evicted from the cache but shouldn't have) and false negatives (something should have been evicted but was not) and the effects of errors can be invisible, annoying, or disastrous, depending on the situation. Incorrect cache invalidation usually results from incorrect dependency management. Naming is hard because names have a conflicting combination of requirements: names need to be short (they will be repeated often), expressive, accurate, unchanging, and easy to remember. It's often quite difficult to find a name for a concept that fits all those requirements. My company has spent years finding the right names for certain core concepts, but that is time well spent.

seer 6y ago

To be honest with all the tooling around programming languages nowadays I haven’t encountered a bug caused by off-by-one error in years. The other two though ... yeah still true :)

kohtatsu 6y ago
Really? You must have some smart tooling.

jsilence 6y ago

Actually funny. Thanks!

zeckalpha 6y ago

That looks like 10 problems to me, if you include binary encoding issues.