Why is Cache Invalidation considered difficult?

Technology CommunityCategory: CachingWhy is Cache Invalidation considered difficult?
VietMX Staff asked 3 years ago

The non-determinism is why cache invalidation are unique and intractably hard problem in computer science.

  • Computers can perfectly solve deterministic problems. But they can’t predict when to invalidate a cache because, ultimately, we, the humans who design and build computational processes, shall agree on when a cache needs to be invalidated. The hard and unsolvable problem becomes: how up-to-date do you really need data to be and when to change (or remove) it?
  • Another problem a cache is (often by nature) much smaller compared to the overall amount of data that needs to be stored and if you just keep adding and adding elements to your cache, it becomes a full copy of your data. Respectively, you run out of memory quickly.

Basically it’s difficult to achieve a desirable balance between stale objects stinking up your cache, and frequent unnecessary refreshes of unchanged objects considering limitation of the cache size.