3 ms·
> But what if we take two random choices (2-random) and just use LRU between those two choices? > Also, we can see that pseudo 3-random is substantially better
by bob1029 1y ago
> But what if we take two random choices (2-random) and just use LRU between those two choices?
> Also, we can see that pseudo 3-random is substantially better than pseudo 2-random, which indicates that k-random is probably an improvement over 2-random for the k. Some k-random policy might be an improvement over DIP.
This sounds very similar to tournament selection schemes in evolutionary algorithms. You can control the amount of selective pressure by adjusting the tournament size.
I think the biggest advantage here is performance. A 1v1 tournament is extremely cheap to run. You don't need to maintain a total global ordering of anything.
- nielsole 1y agoIt's also similar to load balancing. Least requests vs. best of two. Benefit being that you never serve the most loaded backend. I guess the feared failure mode of least requests and LRU is similar. Picking the obvious choice might be the worst choice in certain scenarios (fast failures and cache churning respectively)
- smusamashah 1y agoThere was an article about this phenomenon but with interactive visualisations showing packets moving and load balancing. And there was an optimal number of random, gong higher wasn't improving things.