4 ms·

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

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.
    - necovek 1y ago
      We can agree to disagree on this being a "caching system" and it "knowing when something needs updating" (from the API, I am guessing it's a "set" method). Phrases like "simply" and "never stale" are doing a lot of heavy lifting. Yet you haven't answered a very simple question I posted above: how would Q_Cache structure handle a direct SQL write query from another process on the database it is being used as a cache for? SQL databases don't run websockets to external servers, nor do they fire webhooks. If you are running a server which you are hitting with every update instead of doing direct SQL on the DB, there's always a small amount of time where a cache user can see stale data before this server manages to trigger the update of the cache.
      - EGreg 1y ago
        Simple. Use the principles I said above, for distributed and asynchronous systems. The SQL server should have a way to do pubsub. It can then notify your PHP webhook via HTTP, or run a script on the command line, when a row changes. It should have an interface to subscribe to these changes. If your SQL data store lacks the ability to notify others that a row changed, then there’s your main problem. Add that functionality. Make a TRIGGER in SQL for instance and use an extension. If MySQL really lacks this ability then just put node.js middleware in front of it that will do this for you. And make sure that all mysql transactions from all clients go through that middleware. Now your combined MySQL+Node server is adequate to help clients avoid stale data. As I already said, if you for some reason refuse to handle push updates, then you have to store the latest row state (etags) in your PHP cache (apcu). And then when you access a bunch of cached items on a request, at the end collect all their ids and etags and simply bulk query node.js for any cached items that changed. You can use bloom filters or merkle trees or prolly trees to optimize the query. Joel Gustafson had a great article on this and now uses it in gossiplog: https://joelgustafson.com/posts/2023-05-04/merklizing-the-key-value-store-for-fun-and-profit https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
logical42 1y ago
I agree with you, but you are omitting a key aspect of the problem which makes this hard. If you have a single server serving from a local sqlite database, caching and invalidating the cache is trivially easy. It becomes way more difficult when you have N servers all of which could potentially serve the same data. Local caches could then, yes easily become stale, and even if you have a propagation mechanism, you couldn't guarantee against network failures or latency issues. But suppose you have an HA redis instance that you store your cached data in. Even with a write-through cache, you basically need to implement a 2-phase commit to ensure consistency.
- EGreg 1y ago
  See the thread below. Caches only become stale if you refuse to implement any sort of push architecture. And even then, frequent batch-polling with etags will quickly resolve it. (eg right after you used N entries, poll to see which of the N have changed). Bloom filters, Prolly trees etc can speed the batch polling up. But push architecture obviates the need for it prevents caches from being stale, it’s called eventual consistency. (Well, of course unless there is a network partition and you can’t communicate with the machine holding the actual source of truth then yeah, your local cache will be stale. And to catch up on missed updates you will need to request all updates since a certain marker you saved. If the upstream had a ton of updates since your marker and can’t send the entire history since your marker then you might have to purge your cache for that specific table / collection, yeah.).
  - logical42 1y ago
    I would love it if I could over-withdraw money from my bank account by having someone on the other side of the country take out money from my account at an ATM at the exact time as me, due to the fact that the bank's storage system was eventually consistent, but that's not the case.
    - EGreg 1y ago
      Now you're just conflating things. Pretty sure that when it comes to write transactions, such as bank transactions, you want them to be executed on a source of truth with enforces consistency, not eventual consistency. Any client software should not be trusted -- especially one written by a silly programmer who uses a cache as the source of truth.

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.
  - necovek 1y ago
    We can agree to disagree on this being a "caching system" and it "knowing when something needs updating" (from the API, I am guessing it's a "set" method). Phrases like "simply" and "never stale" are doing a lot of heavy lifting. Yet you haven't answered a very simple question I posted above: how would Q_Cache structure handle a direct SQL write query from another process on the database it is being used as a cache for? SQL databases don't run websockets to external servers, nor do they fire webhooks. If you are running a server which you are hitting with every update instead of doing direct SQL on the DB, there's always a small amount of time where a cache user can see stale data before this server manages to trigger the update of the cache.
    - EGreg 1y ago
      Simple. Use the principles I said above, for distributed and asynchronous systems. The SQL server should have a way to do pubsub. It can then notify your PHP webhook via HTTP, or run a script on the command line, when a row changes. It should have an interface to subscribe to these changes. If your SQL data store lacks the ability to notify others that a row changed, then there’s your main problem. Add that functionality. Make a TRIGGER in SQL for instance and use an extension. If MySQL really lacks this ability then just put node.js middleware in front of it that will do this for you. And make sure that all mysql transactions from all clients go through that middleware. Now your combined MySQL+Node server is adequate to help clients avoid stale data. As I already said, if you for some reason refuse to handle push updates, then you have to store the latest row state (etags) in your PHP cache (apcu). And then when you access a bunch of cached items on a request, at the end collect all their ids and etags and simply bulk query node.js for any cached items that changed. You can use bloom filters or merkle trees or prolly trees to optimize the query. Joel Gustafson had a great article on this and now uses it in gossiplog: https://joelgustafson.com/posts/2023-05-04/merklizing-the-key-value-store-for-fun-and-profit https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...

logical42 1y ago

I agree with you, but you are omitting a key aspect of the problem which makes this hard. If you have a single server serving from a local sqlite database, caching and invalidating the cache is trivially easy. It becomes way more difficult when you have N servers all of which could potentially serve the same data. Local caches could then, yes easily become stale, and even if you have a propagation mechanism, you couldn't guarantee against network failures or latency issues. But suppose you have an HA redis instance that you store your cached data in. Even with a write-through cache, you basically need to implement a 2-phase commit to ensure consistency.

EGreg 1y ago
See the thread below. Caches only become stale if you refuse to implement any sort of push architecture. And even then, frequent batch-polling with etags will quickly resolve it. (eg right after you used N entries, poll to see which of the N have changed). Bloom filters, Prolly trees etc can speed the batch polling up. But push architecture obviates the need for it prevents caches from being stale, it’s called eventual consistency. (Well, of course unless there is a network partition and you can’t communicate with the machine holding the actual source of truth then yeah, your local cache will be stale. And to catch up on missed updates you will need to request all updates since a certain marker you saved. If the upstream had a ton of updates since your marker and can’t send the entire history since your marker then you might have to purge your cache for that specific table / collection, yeah.).
- logical42 1y ago
  I would love it if I could over-withdraw money from my bank account by having someone on the other side of the country take out money from my account at an ATM at the exact time as me, due to the fact that the bank's storage system was eventually consistent, but that's not the case.
  - EGreg 1y ago
    Now you're just conflating things. Pretty sure that when it comes to write transactions, such as bank transactions, you want them to be executed on a source of truth with enforces consistency, not eventual consistency. Any client software should not be trusted -- especially one written by a silly programmer who uses a cache as the source of truth.