What is hard about Cache Invalidation

It depends on your case.

In something like a triple store you assign compact unique identities (maybe integer) to nodes, so you have to look up

   <https://dbpedia.org/resource/Dracula>

and replace it with 77182. If you are looking these up in the database each time it is terribly slow and you get an orders-of-magnitude speedup in a bulk loading job if you keep a cache in a hashtable.

The strategy of "empty the hashtable when it gets full" gives you most of the gains of caching and is not that much worse than an optimal solution. For an online system though it would be unacceptable because the performance of the system would be disasterous because it would slow down the server, make your connection count go through the roof, make it run out of RAM and start to swap, etc.

CPU designers have a devilishly hard problem with cache coherency because they have to support every workload and today we know information leakage in the TLB and other structures is a big problem on top of simply "correctness" and "performance".