Хорошая ли идея использовать в качестве ID (первичного ключа) мд5 хеш?

Question

[Влад Мистецкий]

Собственно проектирую базу данных, сущностями в которой есть изображения. Хочу избежать проблем с дубликатами имен, дырками после удалений (если использовать просто инкремент айди) и везде в качестве айди использовать хешы. Вероятность коллизий вроде бы совсем не высокая на предполагаемом количестве объектов в базе.


Какие могут быть подводные камни?

Comments

[zerkms]

Т.е. пропуски в случае удаления в автоинкрементном ключе вас волнуют, а совершенно рандомные значения md5 — нет? Почему бы тогда автоинкрементный ключ не трактовать аналогично, представляя его функцией свёртки от времени?

[ComodoHacker]

Какие проблемы с дырками после удалений?

Answer 1

[Константин]

Мой учитель по Java мне говорил: «Каждый раз, когда вы используете hash как id, вы убиваете котёнка.»

Answer 2

[shushu]

Не очень хорошая идея. Инт всегда лучше для примари поля.
Я бы использовал int( или bigint) с автоинкрементоv, для внутренних целей, а наружу уже передавал бы md5, предварительно записанный в эту же таблицу отдельным полем, либо md5(id+salt)

Comments

[Влад Мистецкий]

Спасибо, видимо так и придется сделать.
А почему Инт лучше подходит?
Ну понятно, что много действий происходит, но 128 бит вроде не так и много

[xiWera]

а какой смысл в md5 по id? По моему это только лишние вычисления.
md5 имеет смысл когда он бесплатен (так или иначе всегда присутствует в данных), если блоки данных небольшие, с небольшим алфавитом, то коллизий не будет. И md5 ( вместе с размером блока данных, если он вариабелен ) можно использовать как ключ.

Answer 3

[Jazzist]

Да легко. Не ведитесь на старые учения — современные движки БД, и даже MyISAM работают с текстовыми индексами не существенно медленнее, чем с целочисленными.

Если есть сомнения — просто попробуйте оценить реальную нагрузку. Скорее всего, это место узким не будет. Помните о принципе «вреда преждевременной оптимизации», который гласит: «Преждевременная оптимизация — вредна.»

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

Comments

[Марк]

Как раз MyISAM нормально уживается с длинными первичными ключами, а InnoDB (за счет организации хранения данных) — не очень.

[Jazzist]

Как раз именно так и сказал ;)

[Марк]

Ну я хотел написать сначала просто «ага», но потом решил, что это как-то чересчур лаконично, и написал еще про InnoDB.

Answer 4

[Виталий Желтяков]

md5-хэш в качестве id следует использовать только, если он заменяет составной ключ (несколько ключевых полей). В остальных случаях мы используем int (bigint) с unsigned и auto_increment.

Answer 5

[Maxim Avanov]

В вашей задаче, вам не нужен ни MD5, ни автоинкрементный INT, как советовали выше.
Используйте в качестве первичного ключа бинарное поле и вписывайте в него 16-байтные UUID4-последовательности, а пользователям можете отдавать их в виде 32-символьной HEX-строки.

Про накладные расходы. По сравнению с int64, каким должен быть автоинкрементный счётчик, размер поля окажется больше всего на 8 байт (в 2 раза), что для вашего случая — совсем не проблема.
Убедитесь лишь, что ваши индексы всегда умещается целиком в физической памяти, а не хранятся частично или полностью в свопе на диске. Природа UUID такова, что он генерирует равномерно распределенные значения, а значит, поиск по такому индексу будет подвержен эффекту «случайного поиска» (random lookup). И если ваш индекс хотя бы частично хранится на диске, то это может привести к многочисленным random seeks и очень медленной

Comments

[Maxim Avanov]

выборке.

Answer 6

[Zorkus]

Просто вот это — дырками после удалений (если использовать просто инкремент айди) — а в чем тут проблема? Ну будут дырки и будут. Это же суррогатные ключи.

Да, если уйти глубоко в стек, можно поговорить по clustering factor на индексах и прочем ;) но это уже мелочи.
Повторю, я бы использовал внутри СУБД именно этот подход.

Answer 7

[Владимир Чернышев]

Если «Мд5 строить все равно придется», он будет заведомо уникальным (то есть логика не допускает добавления двух картинок с одним хэшем), то почему нет (при условии что индексы и основной, и связанных таблиц будут помещаться в памяти, если важно быстродействие). В любом случае, насколько я понимаю, хэш будет считаться только при попытке добавления картинки в базу, а количество выборок по ид будет много больше числа таких попыток.

Вот только я бы посоветовал хорошо подумать, а действительно ли вам нужна уникальность хэша, не может ли это требование потом измениться. Или, скажем, решите сменить алгоритм хэша — изменение отдельного уникального поля куда менее дешевая операция, чем изменение основного ключа и всех индексов связанных таблиц.

Плюс, если я правильно понял идею (что-то вроде фотохостинга, хэш картинки используется для урлов) могут быть интересные ситуации типа: один пользователь добавил картинку, получил её новый урл, потом второй добавил её же, система засекла дубликат и выдала уже существующий хэш. Затем первый пользователь удалил картинку, система засекла, что есть ещё ссылки и удалила только ссылку из альбомов первого пользователя, не удаляя саму картинку — в итоге первый пользователь может увидеть, что несмотря на удаление картинка осталась доступна по старому урлу. Кому-то может всё равно, а кто-то может поднять крик про личные данные и т. п.

Comments

[Владимир Чернышев]

*менее дорогая операция

Answer 8

[Zorkus]

Какие веские причины не использовать autogenerated surrogate key?

Comments

[Влад Мистецкий]

Если честно, не очень знаю что это такое? Автоинкремент?
Сейчас понимаю, что веских причин наверное нету…

[Zorkus]

В разных СУБД называются они по разному, а я ораклист… В общем, поле типа целочисленного типа и большой вместимости (типа long), значения в котором вставляются СУБД автоматически при вставке новой записи в таблицу, каждый раз значения поле увеличивается на 1 (ну, или на заданный шаг). Тем самым гарантируется уникальность на уровне СУБД.

Answer 9

[Пума Тайланд]

Не иди по пути идиотизма.

Comments

[Maxim Avanov]

В вашей задаче, вам не нужен ни MD5, ни автоинкрементный INT, как советовали выше.
Используйте в качестве первичного ключа бинарное поле и вписывайте в него 16-байтные UUID4-последовательности, а пользователям можете отдавать их в виде 32-символьной HEX-строки.

Про накладные расходы. По сравнению с int64, каким должен быть автоинкрементный счётчик, размер поля окажется больше всего на 8 байт (в 2 раза), что для вашего случая — совсем не проблема.
Убедитесь лишь, что ваши индексы всегда умещается целиком в физической памяти, а не хранятся частично или полностью в свопе на диске. Природа UUID такова, что он генерирует равномерно распределенные значения, а значит, поиск по такому индексу будет подвержен эффекту «случайного поиска» (random lookup). И если ваш индекс хотя бы частично хранится на диске, то это может привести к многочисленным random seeks и очень медленной выборке.

[Maxim Avanov]

Выбрал не то поле для ответа, прошу прощения.

Answer 10

[xiWera]

А каков размер поля по которому строится md5-хэш? И что там за данные?

Comments

[Влад Мистецкий]

Картинки, различных размеров.
Мд5 строить все равно придется, просто хотелось бы понять почему не стоит использовать его в качестве праймери ки

[xiWera]

Можете попробовать, до первой коллизии :)
Простая арифметика подсказывает что множество разнообразных картинок гораздо больше чем количество md5 сумм и коллизии неизбежны. Тогда уж sha сумму + размер + формат картинки как id. Тогда коллизии сведуться в этом случае практически к минимуму.
Но я бы не стал.

[Андрей]

Интересная у Вас «простая арифметика». Приведите расчет?

[xiWera]

2^128 — вариантов md5 сумм
2^(n*8) вариантов картинок, где n размер картинки в байтах.
очевидно что n во втором случае очень часто больше 16 :)

[Андрей]

По «парадоксу дней рождения» для появления первой коллизии с вероятностью 1/2 для хеш-функции разрядностью 128 бит, необходимо создать 2^64 объектов (в нашем случае файлов).

Если каждый житель земли (2^33) будет создавать ежесекундно днем и ночью по одному файлу, то первая коллизия на земном шаре произойдет примерно через 64 года.

P.S. Кстати, как Вы себе представляете базу на (2^64) файлов? Если каждая картинка хотя бы 10 байт, то Вам потребуется 167.772.160 Терабайт.

[xiWera]

Ага, только забывают что и входящий набор (картинки) это не случайные данные (например первые несколько байт у картинок повторяются, так как там заголовок да и в разных картинках разные битовые последовательности более часты). А исходящий набор это не случайная величина, и получена путем алгоритмических действий из первой

[Андрей]

Если я правильно понял последнее сообщение, Вы указываете на то, что случайно может сформироваться коллизия из-за того, что хеш — суть детерминированный алгоритм и если его применить над слегка отличающимися данными, то возможны совпадения?

Поверьте, ученые 14 лет (с 1991 по 2005) искали возможность умышленно построить ну хоть какие-нибудь коллизии к MD5 — безуспешно.

[xiWera]

во первых вы опять случайность сравниваете с умышленностью, во вторых повторюсь, входящие данные не случайны. Они представляют собой определенные байтовые наборы, md5 работает с 64 байтовыми блоками, соответственно если у файлов одинаковое начало (у картинок вполне может быть, так как там зачастую заголовок) то уже первый блок будет иметь одинаковую сумму и разнообразие уменьшается.

Только что ради подтверждения своей мысли прогнал пользовательскую вебфайлопомойку:
уникальных sha хешей: 1951
уникальных md5 хешей: 1605
Не случайные данные, тут ничего не поделаешь.

[Владимир Чернышев]

А сколько файлов? sha корректно «подписала»?

[xiWera]

по sha совпадает только на полностью одинаковых файлах, но тоже повезло, но тут конечно в 2^32 везения больше :)

[Андрей]

Только что ради подтверждения своей мысли прогнал пользовательскую вебфайлопомойку:
уникальных sha хешей: 1951
уникальных md5 хешей: 1605

Проверьте работоспособность Вашего md5 или алгоритма поиска уникальных значений. Уникальных MD5 и SHA-1 хэшей должно быть одинаково.

[xiWera]

не обязано. полсотни миллионов файлов, справедливости ради скажу что размер у файлов таки разный.

[xiWera]

тьфу блин, 20 миллионов это в другом месте, тут только пара тысяч. Те файлы на которых образовалась коллизия довольно специфические.

[andoriyu]

Как это безуспешно? На хабре не так давно проскакивала статья — habrahabr.ru/blogs/infosecurity/113127/

А то, что часть файлов одинаковая это мало на, что влияет — Лавинный эффект никто не отменял.

[Андрей]

Я писал, что до 2005 алгоритмов умышленного построения не было — это говорит о многом.
Ваш термин «лавинный эффект» я называю «парадоксом дней рождения», как это принято в криптографии (см. раздел «Приложения»). Его действие учтено мною — я отдельно это подчеркнул в посте про расчет вероятности первой случайной коллизии.

На моей выборке 17051 уникальных MD5 и 17051 уникальных SHA-1 из 18569 файлов. Файлы примерно однотипные, длиной от 3000 до 15000 байт.

[xiWera]

Я всё таки настаиваю на том, что вы путаете применяя «случайные» коллизии к совсем не случайным файлам.

Answer 11

[Алексей]

Используйте SHA1, как в Git.

Answer 12

[Андрей Шайдуров]

а какая БД? у MongoDB на этот случай прекрасное решение в качестве ID: 12-ти байтное число, которое формируется исходя из узла (при шардинге), timestamp'а, process ID и всего трёх байт автоинкремента (подробнее здесь). Возможно есть подобное для РБД.

Answer 13

[ComodoHacker]

Помимо уже упомянутых подводных камней (размеры таблиц и индексов, производительность) и других по мелочи, не назвали самый главный — использование естественного ключа для PK вместо суррогатного. На эту тему написано много умных статей и глупых холиваров на форумах, я тут расписывать не буду, просто приведу одну ситуацию:

«Ой, не ту картинку загрузили! Надо срочно исправить!… Ой, это было месяц назад, на нее уже куча ссылок в куче таблиц… Ой, там такие констрейнты, простой UPDATE не прокатит… Ой, часть данных уже в архиве, что с ними делать?..»

Answer 14

[kapitansky]

Cогласен с учителем Norraxx (17 мая в 23:58 «Мой учитель по Java мне говорил: «Каждый раз, когда вы используете hash как id, вы убиваете котёнка.»») и VitaZheltyakov (md5-хэш в качестве id следует использовать только, если он заменяет составной ключ (несколько ключевых полей). В остальных случаях мы используем int (bigint) с unsigned и auto_increment). Причём только в том случае если суммарная сложность поиска по нескольким ключевым полям будет выше, чем у хеша…

Чем меньше ключ — тем быстрее происходит поиск по нему, поэтому всегда надо стремиться минимизировать его размер.

Поиск по числовому ключу зачастую много быстрее (бывает, что и до 4х раз быстрее, возможно и ещё быстрее) нежели поиск по числу той же длинны… и это верно не только для реляционных СУБД, но и для подавляющего большинства языков программирования (вполне вероятно, что потребуется искать в множестве, полученном ранее из БД).

Исходя из вашей задачи, для начала, в качестве типа PK я бы выбрал unsigned mediumint (16,777,215 — 1 записей)- его всегда можно будет расширить до int, а затем и bigint (если, конечно, это потребуется).