Какие алгоритмы хэширования лучше работают при сплитовании? Т | EXPF – математическая статистика и эксперименты

Какие алгоритмы хэширования лучше работают при сплитовании?

Таким вопросом мы совсем недавно задались. Самым популярным на текущий момент является старый добрый MD5. Почему? Просто никто не запаривается что выбрать. MD5 выбирают, потому что его легко заимплементить и он обладает нужным свойством детерминированности. По крайней мере, мы знакомы с десятками разных больших компаний, где он используется. Поэтому вопрос о том что выбрать не стоИт.

Однако, мы натолкнулись на статью, где сраниваются разные алгоритмы, в том числе и MD5. Из нее следует, что равномерность бакетов, которые дальше играют ключевую роль в равномерности распределения пользователей между ветками и экспериментами, зависит от их количества (тут Америку не открыли). И чем выше, тем лучше: 50 работают хуже, чем 100. Правда, тоже не было замечено, что кто-то берет именно такое число. Нормальный диапозон находится в отметке 1000-10000, что позволяет брать сотые доли трафика и получить нужную равномерность при >миллионном MAU.

Помимо того, что пользователи должны быть распределены согласно мат.ожиданию (50/50, например) и попадать в ту же ветку при повторном посещении сайта (свойство детерминированности), автор еще отмечает отсутствие корреляции между параллельными экспериментами (один эксперимент не должен влиять на вероятность того, что он будет назначен в каком-либо варианте в любом другом эксперименте) и монотонное нарастание пользователей в ветке без изменения в уже определившихся пользователей в соответствующей ветке. И бонусом – скорость, которую Microsoft отмечают как фактор эффективности алгоритма.

И вот MD5 тут проигрывает SpookyHash, входящий в семейство хеш-функций Дженкинса на ~50% по скорости. Было бы интересно среди прочих увидеть бенчи MurmurHash2, который тоже используют для сплитовщиков.