This 2 random cache scheme reminds me a lot of the 2 random load balancing scheme laid out in "The Power of Two Choices in Randomized Load Balancing" https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.... Which shows an exponential improvement in choosing the less loaded of two randomly chosen servers over just random.