Redis does a much better thing in recent versions: it uses a few samples per iteration, but instead of discarding the accumulated data, it takes a pool of good candidates to re-check in the next iteration, so the approximation to LRU is very close compared to vanilla "among 3" algorithms. Moreover since the performance was improved, now the default is to look at 5 items making the algorithm better. More than the precision of LRU itself, I'm more intrigued with the potential improvements that LFU (Redis >= 4.0) can provide, but being 4.0 just in RC state, most users are currently just using LRU.
