Ускорить мои индексы в MySQL - CRC или MD5?

У меня есть огромная таблица с чем-то вроде 8 300 000 строк (никогда не будет редактироваться или удаляться).

Мой первый столбец выглядит примерно так P300-4312B_X16_S, и запись не уникальна, поэтому я использую в этом поле обычный ИНДЕКС.

Однако MySQL намного быстрее, используя двоичное поле вместо varchar, поэтому я кодирую свой INDEX в MD5, используя BINARY(16) для хранения данных.

Этим утром я впервые начал использовать CRC32 и увидел, что CRC32 можно вывести в виде шестнадцатеричной строки, используя 8 символов.

Мой вопрос: если я использую CRC32 вместо MD5, это будет быстрее. Однако, когда CRC32 пройден, скажем, 2 000 000 уникальных значений, результат будет уникальным, или, может быть, когда-нибудь у меня будет дважды одна и та же строка для двух разных строк? Я спрашиваю об этом, потому что результат имеет длину всего 8 символов (32b) вместо 32 (128b), как у MD5.

Спасибо.


mysql php crc32
person David Bélanger    schedule 01.10.2012    source источник
comment
взгляните на эту страницу: dslreports.com/forum/remark,13525942   -  person jcho360    schedule 01.10.2012
comment
Конечно, вы получите больше коллизий с CRC32. Это инструмент для проверки целостности данных, а не хэш-функция, как md5. Хеш-функции предназначены для создания как можно меньшего количества коллизий (одинаковые результаты для разных входных данных). КПР нет.   -  person dmitry    schedule 01.10.2012
comment
However, MySQL is WAY faster using a binary field instead of a varchar so I encode my INDEX in MD5 using BINARY(16) to store the data. Похоже, ваши индексы не работают. Индексация по VARCHAR должна работать нормально..   -  person Brendan Long    schedule 02.10.2012
comment
Для Дмитрия получение большего количества коллизий с crc32 по сравнению с md5 почти не связано с дизайном, а связано с количеством битов. Crc32 приведет к тому же количеству коллизий, что и любая другая хорошая 32-битная хеш-функция. Точно так же 128-битная контрольная сумма будет иметь ту же вероятность коллизии, что и md5. Помимо crc, у md5 есть еще одно требование к дизайну, заключающееся в том, что он не может быть обратимым для использования в криптографических приложениях. Это свойство не влияет на случайные столкновения. Все, что он делает, это предотвращает или, вернее, создает очень сложные искусственные столкновения.   -  person Mark Adler    schedule 02.10.2012
comment
@Mark Adler Не могу согласиться с дизайном. Md5 - это алгоритм хеширования по дизайну. Crc — это контрольная сумма, предназначенная для обнаружения битовых ошибок и коллизий в том контексте, который находится вне домена.   -  person dmitry    schedule 02.10.2012
comment
Почему бы вам просто не использовать *_bin-collation?   -  person Jimmy T.    schedule 11.03.2014

Ответы (1)


arrow_upward
10
arrow_downward

Ожидаемое количество коллизий — это количество пар по количеству возможных значений проверки. Таким образом, для 2 000 000 значений есть (2000000 * 1999999) / 2 пары, что составляет примерно 2x1012. Для 32-битной CRC ожидаемое количество коллизий превышает 232, то есть 466. Таким образом, в этом случае коллизии практически гарантированы.

Для 128-битного контрольного значения MD5 ожидаемое количество коллизий составляет примерно 6x10-27. Для малых значений ожидаемого числа это также вероятность одного столкновения.

Если вам важно иметь очень низкую вероятность столкновения, то вам нужно выбрать что-то другое, кроме CRC-32.

Однако вам не нужны накладные расходы MD5, где его криптографическая стойкость не важна для вашего приложения. Вам все равно, сможет ли кто-то из злоумышленников найти способ сфабриковать запись с тем же контрольным значением, что и другая запись. Поэтому вы можете использовать 64-битный некриптографический хеш, разработанный для этой цели, который будет работать намного быстрее и даст вероятность коллизии 10-7 в вашем случае с 2 000 000 значений. Или вы можете использовать 128-битный некриптографический хеш и получить ту же вероятность, что и для MD5, но намного быстрее. Взгляните на семейство алгоритмов хеширования CityHash.

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

person Mark Adler    schedule 01.10.2012
comment
Мне нравится ваш ответ, потому что теперь я понимаю логику хеша. Мне все равно, найдет ли посетитель закодированный хэш, это только для определения поездки на автобусе. Если он найдет его, то найдет случайную автобусную поездку... ничего страшного. Я посмотрю на семейство CityHash. Спасибо. - person David Bélanger; 02.10.2012