5 ms·

I never understood about cache invalidation or naming things Both are not that difficult, honestly. Aren’t there a lot harder things out there

by EGreg 1y ago

szundi 1y ago
[dead]
gryfft 1y ago
It's a little bit tongue in cheek; no one is seriously suggesting it's harder than P=NP or the problem of consciousness. But there's something a bit "death and taxes" to the inevitability that any large enough project is going to have some corner cases involving these old chestnuts. Heck you can probably prove that any system for naming things is either inconsistent or incomplete.
- TeMPOraL 1y ago
  > no one is seriously suggesting it's harder than P=NP or the problem of consciousness. Well, I for one feel that "naming things" ultimately boils down to the latter, which may or may not be harder than the former.
Valodim 1y ago
In my experience, the larger the software you write, the truer these become. At some point all obvious names will have collisions, and getting caching right is crucial to do but difficult to achieve because it transcends the entire stack. You could group these two things into "getting the data model right" as the single hard thing, perhaps that rings more true to you :)
quuxplusone 1y ago
For "only two hard problems," read "two candidates for among the hardest problems (but we feel strongly that these are indeed good candidates)," or something along those lines, more or less. It's also possible that these used to be the only two hard problems at the time the aphorism was first recorded, but the underlying state of the world has changed since then and the aphorism, as recorded, is no longer current.
IshKebab 1y ago
Cache invalidation isn't hard in theory. It's just one of those things that is very easy to get subtly wrong and difficult to test. Think about all those times your program isn't building and `make clean` fixes it.
- throwaway150 1y ago
  > Think about all those times your program isn't building and `make clean` fixes it. I don't think that's a good example. I've worked with more than 20 different build tools by now, and I cannot recall a single instance where the problem actually came down to cache invalidation. Every time I dug into it, the real cause was something else: a mistake in the build script, an incorrectly declared dependency, or something similar. So when you say "think about all those times", not a single such time comes to my mind!
  - degamad 1y ago
    I think the idea is that if make clean allows the build to complete correctly, then the underlying issue is that the "mistake in the build script, incorrectly declared dependency, or similar" was causing the cached build results to not be invalidated when they should have.
  - IshKebab 1y ago
    > an incorrectly declared dependency That literally IS cache invalidation. Incremental build systems are caching previous artefacts. They're supposed to invalidate the artefact if a dependency changes. But you forgot to declare the dependency... so it doesn't get invalidated when it should.
gpderetta 1y ago
Namings things is of course a bit tongue in cheek. But cache invalidation is hard. For example, allegedly MESI is one of the hardest things to validate in processor design.
TOGoS 1y ago
There is a secret technique, called content-addressing[1], which elegantly solves both of them at once. A lot of people haven't caught on, and try to cache things using ambiguous names, hence the struggle to invalidate their caches when the meaning changes. [1] This can be applied even if you don't know the content yet; you just have to unambiguously name the inputs to the function that produces it. You might not know what all the inputs are, and then you have to start adding stuff like "unknown-unknown-2025-07-03T16", but it'll still basically work.
ninalanyon 1y ago
Really? Have you tried building any substantial program that makes use of caching and succeeded in invalidating the cache both correctly and efficiently? It's not all about simple things like disk access, caching is also useful in software that models complex hardware where properties depend on multitudes of interconnected calculated values that are time consuming to calculate and where you cannot predict which ones the client will ask for next.
- EGreg 1y ago
  Yes, I have. I've actually built a general-purpose cache system. Several, in fact: Here's one for PHP: https://github.com/Qbix/Platform/blob/main/platform/classes/Q/Cache.php https://github.com/Qbix/Platform/blob/main/platform/classes/... And here is for the Web: https://github.com/Qbix/Platform/blob/dc95bd85fa386e45546b0b1f9303580c3670767e/platform/plugins/Q/web/js/Q.js#L6784 https://github.com/Qbix/Platform/blob/dc95bd85fa386e45546b0b... I also discuss caching in the context of HTTP: https://community.qbix.com/t/caching-and-sessions/192 https://community.qbix.com/t/caching-and-sessions/192 WRITING ABOUT CACHING AND INVALIDATION You should especially start here: https://community.qbix.com/t/qbix-websites-loading-quickly/232 https://community.qbix.com/t/qbix-websites-loading-quickly/2... And then you can read about incremental updates: https://community.qbix.com/t/streams-plugin-messages-subscriptions-and-notifications/293 https://community.qbix.com/t/streams-plugin-messages-subscri...
  - necovek 1y ago
    Your implementations are not cache systems: they are key-value store abstractions which can be used for caching. There is a simpler one in most languages (IIRC, named "hashes" in PHP). Caching becomes hard when such a stores are used in distributed or concurrent contexts. An example: imagine Qcache being used when fetching data from an SQL database. And data in the database changes with a direct SQL query from another process. How will your key-value store know that the value in it is stale and needs refreshing?
    - EGreg 1y ago
      Yes, they are cache systems. And as you say, they can be used for caching. Caching systems know when something needs updating several ways. One is pubsub: When the information is loaded from the cache, you want to set up a realtime websocket or webhook for example, to reflect any changes since the cached info was shown. If you can manage to have a server running, you can simply receive new data (deltas) and update your cached data — in that case you can even have it ready and never stale by the time it is shown. If you can’t run a server and don’t want to reveive pushes then another approach simply involves storing the latest ordinal or state for EACH cached item locally (e-tags does this) and then before rendering (or right after you do) bulk-sending the tags and seeing what has been updated, then pulling just that. The downside is that you may have a flash of old content if you show it optimistically. If you combine the two methods, you can easily get an up-to-date syndication of a remote mutable data store. My whole framework is built around such abstractions, to take care of them for people.

I never understood about cache invalidation or naming things Both are not that difficult, honestly. Aren’t there a lot harder things out there

by EGreg 1y ago

I never understood about cache invalidation or naming things Both are not that difficult, honestly. Aren’t there a lot harder things out there

szundi 1y ago

[dead]

gryfft 1y ago

It's a little bit tongue in cheek; no one is seriously suggesting it's harder than P=NP or the problem of consciousness. But there's something a bit "death and taxes" to the inevitability that any large enough project is going to have some corner cases involving these old chestnuts. Heck you can probably prove that any system for naming things is either inconsistent or incomplete.

TeMPOraL 1y ago
> no one is seriously suggesting it's harder than P=NP or the problem of consciousness. Well, I for one feel that "naming things" ultimately boils down to the latter, which may or may not be harder than the former.

Valodim 1y ago

In my experience, the larger the software you write, the truer these become. At some point all obvious names will have collisions, and getting caching right is crucial to do but difficult to achieve because it transcends the entire stack. You could group these two things into "getting the data model right" as the single hard thing, perhaps that rings more true to you :)

quuxplusone 1y ago

For "only two hard problems," read "two candidates for among the hardest problems (but we feel strongly that these are indeed good candidates)," or something along those lines, more or less. It's also possible that these used to be the only two hard problems at the time the aphorism was first recorded, but the underlying state of the world has changed since then and the aphorism, as recorded, is no longer current.

IshKebab 1y ago

Cache invalidation isn't hard in theory. It's just one of those things that is very easy to get subtly wrong and difficult to test. Think about all those times your program isn't building and `make clean` fixes it.

throwaway150 1y ago
> Think about all those times your program isn't building and `make clean` fixes it. I don't think that's a good example. I've worked with more than 20 different build tools by now, and I cannot recall a single instance where the problem actually came down to cache invalidation. Every time I dug into it, the real cause was something else: a mistake in the build script, an incorrectly declared dependency, or something similar. So when you say "think about all those times", not a single such time comes to my mind!
- degamad 1y ago
  I think the idea is that if make clean allows the build to complete correctly, then the underlying issue is that the "mistake in the build script, incorrectly declared dependency, or similar" was causing the cached build results to not be invalidated when they should have.
- IshKebab 1y ago
  > an incorrectly declared dependency That literally IS cache invalidation. Incremental build systems are caching previous artefacts. They're supposed to invalidate the artefact if a dependency changes. But you forgot to declare the dependency... so it doesn't get invalidated when it should.

gpderetta 1y ago

Namings things is of course a bit tongue in cheek. But cache invalidation is hard. For example, allegedly MESI is one of the hardest things to validate in processor design.

TOGoS 1y ago

There is a secret technique, called content-addressing[1], which elegantly solves both of them at once. A lot of people haven't caught on, and try to cache things using ambiguous names, hence the struggle to invalidate their caches when the meaning changes. [1] This can be applied even if you don't know the content yet; you just have to unambiguously name the inputs to the function that produces it. You might not know what all the inputs are, and then you have to start adding stuff like "unknown-unknown-2025-07-03T16", but it'll still basically work.

ninalanyon 1y ago

Really? Have you tried building any substantial program that makes use of caching and succeeded in invalidating the cache both correctly and efficiently? It's not all about simple things like disk access, caching is also useful in software that models complex hardware where properties depend on multitudes of interconnected calculated values that are time consuming to calculate and where you cannot predict which ones the client will ask for next.

EGreg 1y ago
Yes, I have. I've actually built a general-purpose cache system. Several, in fact: Here's one for PHP: https://github.com/Qbix/Platform/blob/main/platform/classes/Q/Cache.php https://github.com/Qbix/Platform/blob/main/platform/classes/... And here is for the Web: https://github.com/Qbix/Platform/blob/dc95bd85fa386e45546b0b1f9303580c3670767e/platform/plugins/Q/web/js/Q.js#L6784 https://github.com/Qbix/Platform/blob/dc95bd85fa386e45546b0b... I also discuss caching in the context of HTTP: https://community.qbix.com/t/caching-and-sessions/192 https://community.qbix.com/t/caching-and-sessions/192 WRITING ABOUT CACHING AND INVALIDATION You should especially start here: https://community.qbix.com/t/qbix-websites-loading-quickly/232 https://community.qbix.com/t/qbix-websites-loading-quickly/2... And then you can read about incremental updates: https://community.qbix.com/t/streams-plugin-messages-subscriptions-and-notifications/293 https://community.qbix.com/t/streams-plugin-messages-subscri...
- necovek 1y ago
  Your implementations are not cache systems: they are key-value store abstractions which can be used for caching. There is a simpler one in most languages (IIRC, named "hashes" in PHP). Caching becomes hard when such a stores are used in distributed or concurrent contexts. An example: imagine Qcache being used when fetching data from an SQL database. And data in the database changes with a direct SQL query from another process. How will your key-value store know that the value in it is stale and needs refreshing?
  - EGreg 1y ago
    Yes, they are cache systems. And as you say, they can be used for caching. Caching systems know when something needs updating several ways. One is pubsub: When the information is loaded from the cache, you want to set up a realtime websocket or webhook for example, to reflect any changes since the cached info was shown. If you can manage to have a server running, you can simply receive new data (deltas) and update your cached data — in that case you can even have it ready and never stale by the time it is shown. If you can’t run a server and don’t want to reveive pushes then another approach simply involves storing the latest ordinal or state for EACH cached item locally (e-tags does this) and then before rendering (or right after you do) bulk-sending the tags and seeing what has been updated, then pulling just that. The downside is that you may have a flash of old content if you show it optimistically. If you combine the two methods, you can easily get an up-to-date syndication of a remote mutable data store. My whole framework is built around such abstractions, to take care of them for people.