Уникальный ключ (Алгоритм)?

Question

[Виталий Жук]

Привет всем хабра сообществу.


Поставленная задача:

Периодически создавать уникальные ключи в очень больших количествах (Примерно: 500 000 — 2 000 000). Все эти ключи должны быть полностью уникальны, для последующих функций приложения. Длина ключа может изменяться в зависимости от количества. Старт начинаеться с 8 символов. Ключ должен подлежать паттерну: /^[a-zA-Z0-9]+$/

Общее количество ключей неизвестно (Можеть быть даже более 1 млрд.)


Суть проблемы заключаеться в вычеслении этого ключа. Лично я бы предпочел использование:

1. uniqid, но увы, он не очень то и подходит, так как количество симоволов можеть быть разное (а здесь не менее 13).

2. Случайное вычесление (rand, mt_rand) — но они не гарантируют 100% уникальности.

3. md5(time() + $randHash) — но увы, длина аж 32 символа


Вопрос: Возможно кто-то знает какой-то хороший алгоритм генерации рандомного ключа по количеству символов? Если в алгоритме будут дополнительные параметры для генерации, которые нужно будет достать при генерации (модуль, часовую метку, другое), которые влияют на создания уникального ключа, то не проблема, ключи сохраяються в БД.


Примитивные пример в жизни — это скретч коды для пополнения телефонов. Есть набор ключей, которые просто напросто не совпадают :)


Спасибо!

Answer 1

[Anastasia_K]

вариант обрезать md5 до нужного числа символов по каким то причинам не подходит? уникальность можно проверять на этапе вставки в БД, если соответствующее поле будет «уникальным».

Comments

[Виталий Жук]

Как вариант, но как-то стремневато, а если по случайности пойдет зацыкливание (случайные совпадения)?
Хотелось бы узнать, есть ли какие-то математические алгоритмы генерации.

Answer 2

[FilimoniC]

Если ваши ключи не секретные, то просто берите таймштамп и какой-нибудь ID (например, последовательный) и кодируйте в Base62 (это Base64 без символов +-)
Таймштамп равен 4 байта (8 байт если планируете дожить до 2038).

Answer 3

[FilimoniC]

И почему просто не использовать последовательные ключи?

Comments

[Виталий Жук]

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

[FilimoniC]

Как чловек не особо знакомый с вашим продуктом, из ващих слов могу предположить что база — список серийников ПО. Потому предлагаю
1. Заранее нагенерировать их
2. Использовать постоянную длинну ключа с учетом возможного распространения (ее всегда можно будет увеличить). Дополнительно как пользователь я был бы благодарен постоянной длинне ключа

Далее, касательно переменной длинны — рекоммендую вам все же сделать постоянную. С ней работать существенно проще.
Например, ключи ABCDEFGH, 1ABCDEFGH и ABCDEFGH1 следуя вашему алгоритму у вас будут очень сильно разнесены по времени, но очень похожи.
Опять же, при работе с постояной длинной будет гораздо проще работать. Заложитесь просто сразу на миллиард
Например, алгоритм UUID дает вам 2^128 вариантов ( 340 282 366 920 938 463 463 374 607 431 768 211 456 ), занимая при этом 16 байт (32 символа альфанумерик)

Ну и для зашкаливающей паранойи возьмите Аппаратный генератор случайных чисел

[FilimoniC]

Касательно скретч-карт, пример:
Номер (8 символов) + rand()
12345678-1234
При этом RAND знает только база и обладатель карточки. Проверка — возможна. Подбор нецелесообразен.
Номер в вашем случае последовательный.
У Скретч-Карт есть дата «Использовать до». так что рост знакомест маловероятен. И дизайнерам проще — точно знать что знаков 13, а не 14 и не 17

Answer 4

[Виталий Жук]

Так, относительно ответов все понятно, что ничего не поняино. Каждый пишет то, что хочет, при это не чиатя самого вопроса: «есть ли какие-то математические алгоритмы при генерации случайных чисел?»

Причина не в том, что мы не можем использовать md5 от рандома или таймстампа, а в том, что на данный момент нам не известно конечное количество. Длина ключа должна быть не сложной для ввода простому пользователю. А если длина будет 32 символа? Ну давайте будем вводить! Наверное удобно будет… И при этом, если мы на данный момент возьмем все лишь 8 символов, а в результате нужно будет огромнейшее количество ключей, то что тогда?
Если знать, по какому алгоритму создавать, то потом совсем не будет проблем с увеличенеим ключа.

Answer 5

[rakot]

1. Напишите функцию для представления десятичного числа в нужный вам ключ. Только обязательно двухстороннюю, а не хеш(чтобы коллизий не было)(хотя можно не писать, а взять тот же Base62).
2. Возьмите начальную точку для генерации последовательностей, например число 123231314.
3. Прибавляйте rand(50000,100000) к числу и генереруйте по новому числу ключ.
4. После генерации требуемого колличества сохрание новую начальную точку.

Comments

[Виталий Жук]

Спасибо, очень даже хороший вариант. Но как быть, когда число перевалит за пределы integer?

[rakot]

Эту решаемую проблему думаю сами решите, удобным для вас способом.

Answer 6

[MikhailEdoshin]

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

Восемь символов каждый по пять бит дают 40 бит информации, то есть 1,099,511,627,776 номеров. Для миллиарда номеров достаточно 30 бит (2^30 = 1,073,741,824). Оставшиеся десять бит (которые, естественно, могут идти не по порядку) можно заполнить случайной информацией и/или использовать для контрольной суммы, дополнительных пометок (номер серии) и т. п. Разумеется, если у вас будут более длинные номера, то простора еще больше.