Аккуратный способ реализовать Linear Congruential Generator для идентификаторов в MySQL?

Небольшое введение: после размышлений о том, какие уникальные идентификаторы будут отображаться в URL-адресах и в других местах для использования, я выбрал линейные конгруэнтные генераторы (http://en.wikipedia.org/wiki/Linear_congruential_generator). Почему не UUID или автоинкремент?

  • UUID слишком длинные и их сложнее хранить в db (рекомендуемый способ — преобразовать их в VARBINARY(16)).
  • Auto_increment показывает последовательность регистраций и добавлений новых объектов и дает возможность прогнозировать следующие идентификаторы. Например, если сервис становится популярным, пользователи могут сделать несколько регистраций, чтобы заполучить красивый id, а затем попробовать продать такой аккаунт, id даст какой-то статус: чем раньше регистрация, тем круче. Я предпочитаю избегать таких вещей.

В LCG последовательность рандомизирована, и я могу выбирать параметры так, чтобы возможные значения хорошо вписывались в тип данных для конкретной цели. Например, используйте INT UNSIGNED для идентификаторов пользователей и выберите параметры, чтобы задать период 2^32.

Проблема в том, что для генерации следующего идентификатора мне нужно получить значение последнего идентификатора:

nextId = (a * lastId + c) % m
  1. Как я понимаю, я должен сам установить самый первый id? Важно, какой номер я выберу?
  2. Каков аккуратный способ создания новых идентификаторов? Возможно, создать таблицу со списком последних сгенерированных идентификаторов для каждой таблицы? Или добавить столбец auto_increment в каждую таблицу, чтобы отслеживать последний сгенерированный идентификатор? И как избежать проблем при большом количестве регистраций за короткое время?

Update1: я нашел один подход, который является безопасным для нескольких пользователей, используя информацию отсюда: http://dev.mysql.com/doc/refman/5.5/en/information-functions.html#function_last-insert-id

CREATE TABLE sequences (users INT UNSIGNED NOT NULL, posts BIGINT UNSIGNED NOT NULL);
INSERT INTO sequences VALUES(123456,123456789);

А затем, чтобы получить новый идентификатор:

UPDATE sequences SET users=LAST_INSERT_ID((a * users + c) % m);
SELECT LAST_INSERT_ID();

mysql userid primary-key auto-increment
person MidnightCoder    schedule 03.06.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы сделать это надежно в MySQL, вам нужно написать хранимую процедуру и использовать таблицу из одной строки с последним идентификатором в ней.

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

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

Другой способ выполнить то, что вы хотите, - написать хранимую процедуру, которая генерирует многозначное случайное число (я бы выбрал не менее 48 двоичных цифр), а затем пытается вставить его в качестве первичного ключа таблицы. Пока вставка не удалась из-за конфликта клавиш, попробуйте другое случайное число. Эти длинные случайные числа еще сложнее предсказать, чем вашу последовательность LCG.

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

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

person O. Jones    schedule 03.06.2013
comment
Спасибо за ваш ответ. Я обновил вопрос и призываю вас оценить решение, которое я нашел. Я не хочу использовать UUID для идентификаторов пользователей, потому что мне не нужны такие URL-адреса, как example.com/user/550e8400-e29b-41d4-a716-446655440000 или example.com/user/140282366920938463463374607431768211456. - person MidnightCoder; 04.06.2013