Хранение хэшей в mysql и потребление памяти. Какой алгоритм выгодней?

Question

[wanomgn]

Понадобилось хранить в mysql хэши. Много. Несколько миллиардов.
В каком виде это делать выгоднее по памяти и производительности? Видимо чем меньше памяти это будет занимать тем лучше?
Получается что при нескольких миллиардах 32 битный хэш неприемлим?
Остается 64 битный.. Например murmur3. А это получается около 20 цифр в столбце хэша..
Может существуют хэши не только цифровые? Тогда получается что символов в столбце будет гораздо меньше чем 20... Или короткий символьный хэш это хуже чем длинный цифровой ?

Answer 1

[Дмитрий Энтелис]

Уточните пожалуйста условия задачи.
Что за хеши, от чего они, зачем, какой к ним планируется доступ.
Существует огромное количество разных хеш функций.
google "хеш функции"

т.к 20 символов в bigint не влезут, вам придется хранить это дело в текстовом виде, а тут однозначно лучше использовать символьный хеш.
Может быть как то его дополнительно пережимать в непечатные символы и хранить как BINARY какой нибудь

И да, миллиарды в одной таблицe mysql это уже экстрим :)

UPD

таблица "справочник" из двух столбцов.
1.хэш
2.текст до 200 символов.
Есть готовый хэш. Дергаем таблицу что бы узнать какой строке соответствует этот хэш?

1. Не надо держать в одной таблице контент и хеш. Правильно иметь 2 таблицы: хеш,ид_текста; ид_текста,текст
2. хеш в любом случае не дает ответа "точно да". он дает ответ "может быть да"
исходя из этого я бы выбрал какую то хеш функцию которая влазит по длине в UNSIGNED INT, и дополнительно проверял результат уже с текстом.

Comments

[wanomgn]

"незначительное" количество коллизий - приемлемо
UNSIGNED INT в mysql это всего 4294967295 вариантов - при миллиарде записей количество коллизий будет просто адское.
получается что использовать UNSIGNED INT нельзя.
верно я размышляю?
так как же быть?

[Дмитрий Энтелис]

@wanomgn: UNSIGNED INT это 4 294 967 295. 4 миллиарда.
При миллиарде записей и идеальном распределении - вероятность коллизии (вообще) 25%.
Даже если будет коллизия из 10 значений - выбрать их по primary key и отфильтровать - не долго.

[Дмитрий Энтелис]

@wanomgn: и кстати я не уверен что на данном объеме данных mysql будет себя приемлемо вести, особенно если будут частые запросы.
Возможно Вам стоит посмотреть в сторону Redis например.
blog.zawodny.com/2010/07/25/1250000000-keyvalue-pa...
stackoverflow.com/questions/10478794/more-than-4-b...
память сейчас дешевая, а грузить этим mysql как то не очень правильно

Answer 2

[Rsa97]

1. Хранить можно по разному. Можно, например, разбить таблицу на 2ⁿ таблиц по первым битам хэша (table_00, table_01, ... table_ff).
2. Хэш, как таковой, не гарантирует однозначного отображения, то есть вполне вероятен вариант, когда две разные строки будут иметь один и тот же хэш. Для n-битного хэша перебор 2^n/2 строк выдаст два одинаковых значения хэша с вероятностью 63% (парадокс дней рождения). По таблице можете оценить, какая вероятность коллизии будет для вашего количества строк при разной длине хэша.

Answer 3

[wanomgn]

таблица "справочник" из двух столбцов.
1.хэш
2.текст до 200 символов.

Есть готовый хэш. Дергаем таблицу что бы узнать какой строке соответствует этот хэш?

Comments

[Дмитрий Энтелис]

@wanomgn не пишите ответы на свой же вопрос, лучше обновить сам вопрос.
обновил свой ответ