The Reddit problem: Learning from mistakes
royans.net
royans.net
Even if your error was not using consistent hashing, what's preventing you to modify the program in order to use two caching systems for a limited period (the time needed to rebuild the cache)?
So you can use a better distribution strategy, and finally shut down the old cache and use the new.