Adding a cache to improve Availability and Partition tolerance while pretending that your (now) distributed system is also Consistent is not "hard", it's imposs

Adding a cache to improve Availability and Partition tolerance while pretending that your (now) distributed system is also Consistent is not "hard", it's impossible. Sorry, CAP applies to caches too. You inflict this hard problem on yourself when you try to throw away the time context of the data. Just... don't do that. Contextualize data with a commit log sequence id and all of these problems vanish. If the cache has data valid up to sequence id XYZ, include that context in the response -- that's all a cache can say anyways: client: hey can I have /foo/bar cache: sure, /foo/bar was 'abc' as of #XYZ (or) client: hey can I have /foo/bar as of at least #XYZ+7 cache: sure let me look that up... And thus the cache invalidation problem is reduced to the naming problem, and you have at least one fewer off-by-one errors. Change my mind. :)