How does LRU cache works
Real fully associative instruction and/or data caches are rare, sometimes hidden as loop buffer, combining write buffers...

What is common is having 2 to 16 ways set-associative caches.
Up to 4 ways, true LRU is possible, beyond that, pseudo-LRU is usually used.

There is little benefit to go beyond 4-8 ways for a L1/L2 CPU cache. More ways may be needed in L2-L3 caches shared between several CPUs.

For 4 ways true LRU, there are 24 possible combinations : 1-2-3-4, 1-2-4-3, 1-3-2-4... etc. It can be stored as a 5 bits code which directly indicates the least recently used way.