🔫 Как выстрелить себе в ногу при помощи хэширования

В мае этого года я писал про алгоритм хэширования xxHash в .NET. Тогда я исследовал эту тему, чтобы использовать хэш для ускорения SQL-запросов. Некоторые таблицы БД фактически работали, как key-value хранилище.

В комментариях советовали так не рисковать, но я рискнул… и выстрелил себе в ногу. 😬 Объясняю, почему так делать не надо.

Недавно я случайно наткнулся на объяснение парадокса дней рождения. Суть в том, что в группе из 23 человек вероятность совпадения дня рождения (число и месяц) хотя бы у двоих людей превышает 50%. У этого утверждения есть математическое доказательство, можете ознакомиться с ним на Википедии, например.

В алгоритмах хэширования этот парадокс проявляется следующим образом. В нашем FinOps дашборде для аналитики трат, таблица Resources – одна из самых больших (не считая Fact-таблицы). В Resources использовалось хеширование. Размером она чуть больше 200 000 строк. Тип значения хэша был int32, то есть количество уникальных значений хэша 4 294 967 296. Кажется, что 200 тысяч – это мелочь, по сравнению с 4 миллиардами. И все хэши ресусов должны быть уникальными. Но сравнивать нужно не отдельные значения, а пары. А 200 тысяч ресурсов образуют примерно 20 миллиардов пар комбинаций.

Мои примерные расчёты показали, что в таблице Resources с вероятностью 99.98% были коллизии. Я полез проверять, а так ли это на самом деле. Оказалось, что математика не обманывает. На более чем 200 000 строк набралось около 15 записей с одинаковым хэшем, но разным InternalId (внутренний ID ресурса в облаке). На момент обнаружения, этот баг практически не влиял на точность аналитики, но очевидно, что дальше было бы только хуже. Поэтому пришлось потратить 1.5 дня на выпиливание этого функционала.

Вывод: не делайте как я. Сейчас мы всё также используем суррогатные первичные ключи, но их значения последовательно генерируются базой данных. Потоковая вставка реализована через денормализованную стейдж таблицу. Расскажу об этом подробнее в другой раз.

Под конец, анекдот в тему:

Один батюшка строил церковь. И всё бы хорошо, но колокольня всё время падала. Построят - упадёт. Снова построят - снова упадёт. И вот явился к батюшке ангел божий и изрёк: "Вмуруй жену свою в фундамент и в веках простоит Храм твой". Жену юную батюшка очень любил, но Господа тоже любил. И храм строить нужно. Погоревал, поплакал, попрощался с женой (а она была барышня богобоязненная, надо так надо) и таки замуровал. А колокольня все равно упала. Потому что сопромат не обманешь.