PHP генерирует короткие уникальные идентификаторы с помощью auto_increment?

Question

Я хотел бы сгенерировать короткий уникальный идентификатор без проверки на наличие коллизий.

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

Обычно беспокоиться о столкновениях не проблема, но уникальный идентификатор, который я хочу сгенерировать, представляет собой короткую уникальную строку из 5-8 символов, буквенно-цифровую, как это делает tinyurl.

РЕДАКТИРОВАТЬ: я хотел бы начать с 5 символов, и если я наберу 60 миллионов записей, затем перейти к 6 ... и так далее.

С этой целью я подумал, что мог бы использовать значение auto_increment, которое скрыто от пользователей, и вместо этого подарить им MD5 или какой-либо другой метод для генерации уникальной строки из этого.

Генерируемые строки не должны казаться линейными, поэтому простое преобразование идентификатора auto_incremented в base 36 [0-9A-Z] немного упрощено, но я собираюсь использовать функцию, подобную этой.

РЕДАКТИРОВАТЬ: Безопасность не является проблемой, так как она не будет использоваться для защиты информации. Это просто ярлык для более длинной строки. Спасибо.

Спасибо за ваши предложения и извините за задержку. Стоматолог ..

Answer 1

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

• инвертирование некоторых битов (например, с использованием XOR, ^ в PHP)
• поменять местами биты (($ i & 0xc) >> 2 | ($ i & 0x3) << 2) или просто поменять местами все биты </li>
• добавление постоянного значения по модулю вашего максимального диапазона (должно быть в два раза, если вы комбинируете это с вышеупомянутыми)

Пример: эта функция преобразует 0, 1, 2, 3, 5, .. в 13, 4, 12, 7, 15, .. для чисел до 15:

$i=($input+97) & 0xf;
$result=((($i&0x1) << 3) + (($i&0xe) >> 1)) ^ 0x5;

EDIT

Более простой способ - использовать линейный конгруэнтный генератор (LCG, который обычно используется для генерации случайных чисел), который определяется формулой вида:

X_n+1 = (a * X_n + c) mod m

Для хороших значений для a, c и m последовательность X_0, X_1 .. X_m-1 будет содержать все числа от 0 до m-1 ровно один раз. Теперь вы можете начать с линейно увеличивающегося индекса и использовать значение next в последовательности LCG в качестве «секретного» ключа.

EDIT2

Реализация: Вы можете создать свои собственные параметры LCG , но если вы ошибетесь, он не будет охватывать весь диапазон (и, следовательно, иметь дубликаты), поэтому я буду использовать здесь опубликованный и опробованный набор параметров из этот документ :

a = 16807, c = 0, m = 2147483647

Это дает вам диапазон 2 ** 31. С pack () вы можете получить результирующее целое число в виде строки, base64_encode () делает его читаемой строкой (до 6 значащих символов, 6 бит на байт), так что это может быть вашей функцией:

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)

Answer 2

вы можете использовать битовое XOR для шифрования некоторых битов:

select thefield ^ 377 from thetable;

+-----+---------+
| a   | a ^ 377 |
+-----+---------+
| 154 |     483 |
| 152 |     481 |
|  69 |     316 |
|  35 |     346 |
|  72 |     305 |
| 139 |     498 |
|  96 |     281 |
|  31 |     358 |
|  11 |     370 |
| 127 |     262 |
+-----+---------+

Answer 3

Вероятно, вы можете сгенерировать хеш MD5 текущего даты / случайного числа и обрезать его до необходимой вам длины (5-8 символов) и сохранить его в виде поля id.

Если вы используете хранение этой информации в базе данных, вам не нужно использовать цикл for для проверки столкновений, но вы можете просто сделать оператор select - что-то вроде

SELECT count(1) c FROM Table WHERE id = :id

где: id будет вновь сгенерированным идентификатором. Если c больше 0, то вы знаете, что он уже существует.

EDIT

Возможно, это не лучший способ сделать это. Но я сделаю это, так что я думаю, что вам нужно каким-то образом преобразовать числа в уникальную короткую строку, а это не в последовательности.

Полагаю, как вы сказали, кодировка base64 уже выполняет преобразование числа в короткую строку. Чтобы избежать проблемы с последовательностью, у вас может быть некоторое отображение между автоматически сгенерированными идентификаторами в какое-то «случайное» значение (уникальное отображение). Затем вы можете base64 кодировать это уникальное значение.

Вы можете создать это отображение следующим образом. Во временной таблице хранятся значения от 1 до 10 000 000. Сортируйте его в случайном порядке и сохраняйте в своей таблице.

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND()

Где MappingTable будет иметь идентификатор из 2 полей (ваш автоматически сгенерированный идентификатор будет противостоять этому) и mappedId (именно для этого вы будете генерировать кодировку base64).

Когда вы приблизитесь к 10 000 000, вы можете снова запустить приведенный выше код и изменить значения во временной таблице на 10 000 001-20 000 000 или что-то в этом роде.

Answer 4

В этом посте есть что-то похожее на то, что вам нужно.

http://kevin.vanzonneveld.net/techblog/article/create_short_ids_with_php_like_youtube_or_tinyurl/

Answer 5

Если вы не можете использовать поле с автоинкрементом и хотите получить абсолютно уникальное значение, используйте UUID . Если вы решите использовать что-то еще (кроме автоинкремента), глупо НЕ проверять наличие коллизий.

Answer 6

MD5 возрастающего числа должно быть хорошо, но я волнуюсь, что если вы обрезаете свой MD5 (который обычно 128 бит) до 5-8 персонажи, вы почти наверняка повредить его способность действовать как уникальная подпись ...

Совершенно верно. Особенно, если вы достигаете вероятности столкновения 80%, усеченный MD5 будет так же хорош, как любое случайное число, чтобы гарантировать уникальность, то есть бесполезную.

Но если вы все равно используете базу данных, почему бы просто не использовать УНИКАЛЬНЫЙ ИНДЕКС? Таким образом, проверка уникальности выполняется (гораздо более эффективным способом, чем использование цикла) самой MySQL. Просто попробуйте выполнить INSERT с вашим ключом, сгенерированным MD5, и, если он потерпит неудачу, попробуйте снова ...

Answer 7

MD5 с возрастающим числом должен быть в порядке, но я боюсь, что если вы урезаете свой MD5 (который обычно составляет 128 бит) до 5-8 символов, вы почти наверняка повредите его способность действовать как уникальная подпись ...

Answer 8

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