11 ответов в теме

[nikitas]

Такое дело. В БД (MySQL) будет хранится текстовая инфа которая в своей сути будет уникальна.
Длина записей от 5-6 символов до 50000-60000, вероятно будет больше (mediumtext должно хватить, он до 16 метров). Проверку на дубликаты при добавлении новой хотел реализовать через хеши, так как проще сравнить не 50000 символов, а лишь 128 (это длина хеша на sha512).
На выбор есть 2 алгоритма (можете предложить больше), MD5 и SHA2 (SHA256/384/512). Прочитал, что для MD5 высока вероятность совпадения, когда md5(aaa) вернет тоже значение, что и md5(bbb). Для SHA2 все получше.

Суть вопроса такова: если кто сталкивался с похожей задачей, какой алгоритм для хеша вы использовали (или как реализовывали проверку на дубли при добавлении новой записи)?

Ожидаемое количество записей ~2-3 миллиона.

Так же прикручен Redis (для минимизации нагрузки), по которому и будет происходить выборка id:hash (id записи в mysql, и hash оттуда, если запись в redis найдена, то будет запрос к mysql на выдирание текста).

[Каровод]

MD5 вроде как взломан. И использовать его небезопасно.

[Denadan]

MD5 вроде как взломан. И использовать его небезопасно.

в данном конкретном случае - глубоко пофик. ему хеши нужны

[glkudr]

Суть вопроса такова: если кто сталкивался с похожей задачей, какой алгоритм для хеша вы использовали (или как реализовывали проверку на дубли при добавлении новой записи)?

Sha1

Ожидаемое количество записей ~2-3 миллиона.

Для такого количества записей можно использовать любой алгоритм. Коллизии почти невероятны. Речь ведь не идет о криптостойкости, а просто о надежности выборки по ключу.

[Abuser]

Для такого количества записей коллизий даже с MD5 можно не ожидать. Так что заморачиваться с навернутыми хэшами не вижу смысла.

[Taupwnz]

Глубоко пофиг, имхо, как именно ты хэш будешь брать(sha/md5/we), гораздо важнее, какой длинны этот хэш. Больше длинна - меньше коллизий.
И да, 2-3кк не такое большое значение.

[nikitas]

Denadan, да, цель только хеши.
glkudr, верно, криптостойкость не нужна, главное, чтобы при добавлении пользователем новой записи не возникло исключения что, мол, такая запись уже есть из-за того, что совпали хеши.
Abuser, Taupwnz, хеш md5 и sha256 равен 64 символам (в байтах же там около 16, если память не изменяет, так как длинные абракадабры - это байты переведенные в hex систему и выданные в виде строки). sha512 это 128 "человеческих" символов, на 3 миллиона записей будет около 180 метров экономии, но в масштабах базы (ее размера) это неважно.
Касаемо быстродействия - нашел в гугле заметку, что так как sha512 оперирует блоками по 64 бита, она дает выигрыш более 30% в сравнении с sha256/sha384 при взятии хешей от 4к и выше на x64 процессорах (на сервере как раз 64 бита железка).
В общем почитаю еще, и если ничего не найду дельного - буду использовать sha512.

Всем спасибо за комментарии, жаль никто не сталкивался с такой проблемой.
Кратко: добавление текстов произвольных размеров (до 16 метров макс) в базу и *минимальное поддержание их уникальности.

*минимальное: "qweqweqwe123" и "qweqweQwe123" это разные тексты. Регистр имеет значение.


редактирование: отщепятки

Сообщение отредактировал nikitas: 12 December 2012 - 10:35

[Abuser]

С каких пор длина хэша у md5 стала в 64 символа, всегда же 32 была

Сообщение отредактировал Abuser: 12 December 2012 - 11:34

[nikitas]

С каких пор длина хэша у md5 стала в 64 символа, всегда же 32 была

да ты прав
md5 = 32
sha256 = 64
sha384 = 96
sha512 = 128

[Chaek]

Бери md5 и не заморачивайся, праймори кей вешай на md5 хэш и вперед.
Если будешь пытаться решить проблему коллизии, то потребуются дополнительные затраты времени в любом случае. На вскидку приходит 2 очевидных варианта:
1. Если md5 этого текста уже есть в базе, то потом сверяешь текст полностью на идентичность. Если тексты отличаются, то добавляешь в конец текста какой-нить <anti collision tag #i> i = 0, 1, 2, ..., etc. Потом при выводе текста эту строку придется вырезать.
Минусы:
- если много повторного текста вводится, то узкое место - сверка текста
- пры выводе информации, особенно если текст большой, много времени займет обработка регуляркой для замены нашего anti collision tag
2. Primary Key это строка md5+sha256, вот тут уже вероятность коллизии резко уменьшается
Минусы:
- замедленный поиск по бд - строка из 96 символов вместо 32, хотя в случае с Primary Key будет бинарный поиск с O(log n), так что я бы использовал именно этот способ
- больше времени требуется на хэширование, 1 раз прохэшировали и забыли, так что норм все тут

Можно еще придумать что-либо, все зависит от конкретной ситуации. Дерзай!

Сообщение отредактировал Chaek: 12 December 2012 - 14:37

[nikitas]

Бери md5 и не заморачивайся, праймори кей вешай на md5 хэш и вперед.
Если будешь пытаться решить проблему коллизии, то потребуются дополнительные затраты времени в любом случае. На вскидку приходит 2 очевидных варианта:
1. Если md5 этого текста уже есть в базе, то потом сверяешь текст полностью на идентичность. Если тексты отличаются, то добавляешь в конец текста какой-нить <anti collision tag #i> i = 0, 1, 2, ..., etc. Потом при выводе текста эту строку придется вырезать.
Минусы:
- если много повторного текста вводится, то узкое место - сверка текста
- пры выводе информации, особенно если текст большой, много времени займет обработка регуляркой для замены нашего anti collision tag
2. Primary Key это строка md5+sha256, вот тут уже вероятность коллизии резко уменьшается
Минусы:
- замедленный поиск по бд - строка из 96 символов вместо 32, хотя в случае с Primary Key будет бинарный поиск с O(log n), так что я бы использовал именно этот способ
- больше времени требуется на хэширование, 1 раз прохэшировали и забыли, так что норм все тут

Можно еще придумать что-либо, все зависит от конкретной ситуации. Дерзай!

Весь поиск будет в Redis, как только в редиске найдена запись по хешу, то ей соотв. запись в mysql с тем же ID и уже из БД будет выдираться "текст" (по id, который числовой и primary key для таблицы). В любом случае спасибо за идею с тагом, можно для страховки ввести, а потом просто регулярным выражением от нее избавлятся (при выводе).

З.Ы, плюс не могу поставить, за сегодня исчерпал. Поставлю завтра!