3 ms·

More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/

by uvdn7 4y ago

yencabulator 4y ago
From the article: - client starts a transaction - client runs any mutations as needed - client collects user_ids whose cache entries need to be invalidated - client invalidates cache - client commits the transaction You can now have caches fetching & storing the "old" state between the last two steps. This fails to invalidate cache in all scenarios.
- gigatexal 4y ago
  So they didn't solve one of the fundamentally difficult things related to computing. I knew it was probably good to be dubious of such claims.
  - uvdn7 4y ago
    I will not say cache invalidation is easy; and I am not trying to minimize anyone’s struggles. But cache invalidation is _not_ like FLP impossibility or CAP. Too many systems reason caching (inherently a distributed system) in an ad-hoc way that leads to failures and this belief that cache invalidation is uniquely hard (https://twitter.com/marcjbrooker/status/1534944338341310470?s=21&t=pXvsxVPPUZryP1VpWdgpmQ https://twitter.com/marcjbrooker/status/1534944338341310470?...). https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem
- uvdn7 4y ago
  Good catch! I shouldn't have omitted the details here. Roughly there are two ways to solve the race you mentioned here. You can use a versioning scheme supported by the database to do compare-and-swap – i.e. sending invalidate along with a hybrid-logical-clock. HLC is nice in this case as it handles DB transaction rollback gracefully, if the database supports it. Or we can always do the invalidation asynchronously (by recording the invalidation keys transactionally and have a tailer that sends out the invalidation). I will make an edit to the blog to make it more clear. Let me know if that makes sense! I mean this – cache invalidate/fill race specifically – is very much a solved problem from a protocol perspective, as long as our definition of the problem is the same – do not leave stale data in cache indefinitely. That is not to say it is easy; I am not trying to minimize anyone's struggles. https://research.facebook.com/publications/scaling-memcache-at-facebook/ https://research.facebook.com/publications/scaling-memcache-... might be of interest. A lot of the challenges in cache are in making the tradeoffs between consistency and coordination overhead based on the workload and the requirement, _and actually_ making caches consistent in production. As explained in the post, there are practical challenges that are very unique to cache and cache invalidation.

More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/

by uvdn7 4y ago

More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/

yencabulator 4y ago

From the article: - client starts a transaction - client runs any mutations as needed - client collects user_ids whose cache entries need to be invalidated - client invalidates cache - client commits the transaction You can now have caches fetching & storing the "old" state between the last two steps. This fails to invalidate cache in all scenarios.

gigatexal 4y ago
So they didn't solve one of the fundamentally difficult things related to computing. I knew it was probably good to be dubious of such claims.
- uvdn7 4y ago
  I will not say cache invalidation is easy; and I am not trying to minimize anyone’s struggles. But cache invalidation is _not_ like FLP impossibility or CAP. Too many systems reason caching (inherently a distributed system) in an ad-hoc way that leads to failures and this belief that cache invalidation is uniquely hard (https://twitter.com/marcjbrooker/status/1534944338341310470?s=21&t=pXvsxVPPUZryP1VpWdgpmQ https://twitter.com/marcjbrooker/status/1534944338341310470?...). https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem
uvdn7 4y ago
Good catch! I shouldn't have omitted the details here. Roughly there are two ways to solve the race you mentioned here. You can use a versioning scheme supported by the database to do compare-and-swap – i.e. sending invalidate along with a hybrid-logical-clock. HLC is nice in this case as it handles DB transaction rollback gracefully, if the database supports it. Or we can always do the invalidation asynchronously (by recording the invalidation keys transactionally and have a tailer that sends out the invalidation). I will make an edit to the blog to make it more clear. Let me know if that makes sense! I mean this – cache invalidate/fill race specifically – is very much a solved problem from a protocol perspective, as long as our definition of the problem is the same – do not leave stale data in cache indefinitely. That is not to say it is easy; I am not trying to minimize anyone's struggles. https://research.facebook.com/publications/scaling-memcache-at-facebook/ https://research.facebook.com/publications/scaling-memcache-... might be of interest. A lot of the challenges in cache are in making the tradeoffs between consistency and coordination overhead based on the workload and the requirement, _and actually_ making caches consistent in production. As explained in the post, there are practical challenges that are very unique to cache and cache invalidation.