The coin flip method you describe breaks the same-query same-server locality (unless adding or removing servers) that is one motivation for the consistent hashing method.

You could solve that by storing the new-query flip result, but the goal was reducing storage…