Генерация 1млн билетов со случайными уникальными ID

Question

[ActioNk]

Добрый день!

Задача следующая:
Есть 1 млн «билетиков», которые могут покупаться игроками. При покупке игроку выдается билетик с номером от 1 до 999999. Номера должны быть случайные (не последовательные) и уникальные. Каждый игрок может купить сколько угодно билетиков.

Средства:
PHP + MySQL. Скорее всего, табличка (ticket_id, user_id).

Условия:
Высокая нагрузка. Вероятна продажа всех билетов.

Интересно, кто как решил бы такую задачу? Мне пока на ум пришло только:

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

2. Заранее сгенерить в базе 1млн записей с номерами билетов и выбирать WHERE user_id=0 ORDER BY RAND() LIMIT 1;

Пока склоняюсь ко второму варианту. Может кто-то еще знает (или придумает) какие-то решения?
Спасибо

Answer 1

[Андрей Привалов]

Как вариант заранее сгенерить табличку с 1млн записей, только уже в табличке эти записи перемешать.
А выдавать — по-порядку.

Answer 2

[evgeny_eJ]

Записать в базу 1 млн билетов в случайном порядке. После этого выбирать по порядку билеты.

Comments

[FloppyFormator]

Очень удобно, можно заранее узнать, какое случайное число следующее.

[evgeny_eJ]

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

Answer 3

[Stdit]

Как вариант, можно завести дополнительное поле (sort) у билетов и заполнить его уникальными случайными числами. После этого сделать индекс по user_id и sort. Тест на таблице в миллион записей (InnoDB):

mysql> SELECT * from ticket WHERE user_id = 0 ORDER BY sort LIMIT 10;
+--------+------+---------+
| id     | sort | user_id |
+--------+------+---------+
| 923164 |    1 |       0 |
| 171274 |    2 |       0 |
| 217458 |    3 |       0 |
| 182627 |    4 |       0 |
| 183120 |    5 |       0 |
| 483756 |    6 |       0 |
| 210156 |    7 |       0 |
| 362920 |    8 |       0 |
| 311591 |    9 |       0 |
| 545096 |   10 |       0 |
+--------+------+---------+
10 rows in set (0.00 sec)

mysql> UPDATE ticket SET user_id = 1 WHERE id IN (923164, 171274, 217458);
Query OK, 3 rows affected (0.01 sec)
Rows matched: 3  Changed: 3  Warnings: 0

mysql> SELECT * from ticket WHERE user_id = 0 ORDER BY sort LIMIT 10;
+--------+------+---------+
| id     | sort | user_id |
+--------+------+---------+
| 182627 |    4 |       0 |
| 183120 |    5 |       0 |
| 483756 |    6 |       0 |
| 210156 |    7 |       0 |
| 362920 |    8 |       0 |
| 311591 |    9 |       0 |
| 545096 |   10 |       0 |
| 230442 |   11 |       0 |
| 472816 |   12 |       0 |
| 138187 |   13 |       0 |
+--------+------+---------+
10 rows in set (0.00 sec)

Answer 4

[Koroed]

в случае с условием 1 млн от 0 до 999999 лучше все сгененрировать и перемешать заранее.
а вот если вам надо действительно много билетов, то вам может помочь GUID/UUID, благо где он только не реализован всеми возможными способами.

Comments

[Stdit]

Чем именно он может помочь?

[Koroed]

быстро придумать большое случайное уникальное* число
ну почти уникальное, и это поправимо

[Stdit]

Уникальное — да, но оно вовсе не случайное.

Answer 5

[antonevich]

захэшировать, отфильтровать по хэшу =))

Answer 6

[IDDQD]

простейший вариант:
$rand = rand(1, 1000000);
… WHERE ticket_id >=$rand AND user_id=0 LIMIT 1;

Если нагрузки действительно высокие, то генерируем заранее таблицу ticket_id(PK)|rand_num|user_id с уникальным rand_num, а в кеше храним инкремент от последнего купленного ID. Читаем и апдейтим исключительно по PK, и как фейловер — небольшая процедура получения ID последнего купленного билета из бд на случай падения кеша.

Comments

[Stdit]

Разве при таком подходе каждый купленный билет не повышает вероятность покупки следующего порядкового билета? К примеру, если куплены все билеты от 0 до 500000, то любое случайное число от 0 до 500000 приведёт к покупке 500001 билета. Таким образом, вероятность его покупки будет примерно 50%.

[IDDQD]

Будет. Но какова вероятность возникновения такой ситуации при случайном rand?

[Stdit]

Как минимум, увеличение шансов на следующий билет при выборе любого билета, так как это образует «окно» в последосательности. И как следствие, увеличение этого «окна», поскольку шанс выбрать нижний элемент будет только увеличиваться при исчерпании билетов. Какие от этого могут быть побочные эффекты для лотереи — не могу сказать, но процесс выбора билетов получается не абсолютно случйный.

[IDDQD]

Вообще-то это нормально для ограниченного множества уникальных элементов, не находите?)

[Stdit]

Проверил свою теорию: jsfiddle.net/UqYgF/, это действительно не нормально.
Обратите внимание на динамику образования дырок при wrong = true и wrong = false.
Кроме того, ваше условие не сработает, если больше нет элементов с id > $rand.

Answer 7

[karellen]

Если это не синтетическая задача типа «как бы вы забили гвоздь, имея только молоток», то с такими задачами хорошо справляется Redis — в set можно записать заранее все номера (в любом виде — хоть числа, хоть строки, хранить миллион номеров понадобится всего пару-тройку МБ памяти) и через SPOP получать случайное число с алгоритмической сложностью О(1).

Comments

[karellen]

молоток = микроскоп :)

Answer 8

[CrazySquirrel]

CREATE TABLE t (ticket_id INT, user_id INT default 0, PRIMARY KEY (ticket_id));
INSERT INTO t(ticket_id) VALUES(rand()*1000000); //Генерация может занять долго, зато 1 раз :-)
UPDATE t SET user_id = 1 WHERE user_id = 0 limit 1; //Продаём билет.

Comments

[CrazySquirrel]

user_id = ID_ЧЕЛОВЕКА_КОТОРОМУ_ПРОДАЛИ_:-)

[fishbone]

Подход верный, но вы сильно упростили процедуру генерации. rand()*1000000 может вернуть одно и то же число.

[CrazySquirrel]

Мог бы, если бы не PK, в этом варианте просто будет больше чем 1000000 повторений.

Answer 9

[mithraen]

Сделать таблицу с _3-мя_ полями:
ticket_id (внутренний ID, последовательный)
ticket_number (номер билета)
user_id (ID купившего)

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

SELECT * FROM tickets WHERE user_id IS NULL ORDER BY ticket_id LIMIT 1;

индекс создаем один по двум полям — user_id и ticket_id. Этот индекс как ускорит этот запрос, так и поможет получить список билетов, принадлежащих конкретному пользователю.

только про блокировки надо не забывать — иначе при покупке билета могут быть коллизии.

Answer 10

[Edro]

Попробуйте это со своими коэффициентами. Где-то придется хранить предыдущее сгенерированное число.

Answer 11

[softm]

Разделите задачу на 100 частей, будет проще решать

Answer 12

[wscms]

ORDER BY RAND это будет жесть
Разбейте на интервалы с шагом, скажем, 5 000

Первый рандом — выбор интервала, скажем от 200000 до 205000
Потом проверка пробегитесь по этому интервалу и найдите все «пустые» значения. Среди них выберите случайное.
Если «пустых» нет — пометьте, что этот интервал занят полностью и больше его не используйте

Answer 13

[depporter]

В соседнем посте, как раз обсуждается вопрос рандомного выбора. habrahabr.ru/post/154905/

Answer 14

[MikhailEdoshin]

Мне нравится вариант с перемешать заранее, но если вам требуется не настоящая случайность, а просто чтобы номера не выглядели последовательными, то можно использовать последовательные номера с перемешанными битами. Например, если взять пять бит, перенумеровать биты по порядку справа налево 5, 4, 3, 2, 1 и перемешивать их, например, как 4, 1, 2, 5, 3, то последовательность 1, 2, 3, 4, 5, 6 превратится в 8, 4, 12, 16, 24, 20.

PS: Неужели MySQL затормозит на индексе в 1 млн. чисел?

Comments

[Hint]

Каким образом вы сохраните диапазон от 1 до 999999? А так, вместо перемешивания бит проще сделать xor.

[MikhailEdoshin]

Ну не в пяти же битах — пять для примера.

[Hint]

Да сколько бы не взяли, у вас всегда будут диапазоны от 1 до 2^n, а не от 1 до 999999.

[mejedi]

Можно посчитать md5 от порядкового номера + еще что-то и упорядочить по этому полю?

[MikhailEdoshin]

mejedi Не факт, что (урезанный?) MD5 даст уникальные хэши для каждого номера. Hint: согласен; тогда чтобы не выскочить за границы диапазона, можно перемешивать только младшие биты.

Answer 15

[Степан]

При количестве 1млн из 1мл допустимых значений ни какой рандомности не может быть. Думайте как выдавать вообще не используя таблицу.
Первое что пришло в голову мне, это использовать мемкеш для хранение уже выданных id.

$rand = rand(1, 1000000);
$memkey =«ticket_».$rand;
if ($get_result = $memcache->get($memkey))
{
Такой билет уже продан, генерим другой
}
{
Билет не продан. Записываем в БД и в мемкеш
$memcache->set($memkey, $rand, false);
}

Comments

[Степан]

Хотя нет, попробовал запустить выборку 1млн ключей. Секунд 10 это много…

[adminimus]

ваш говнокод покажет просто адское быстродействие при продаже последнего билета :)

[Степан]

Зачем писать то, о чем я сам написал сразу же после кода.

Answer 16

[tenshi]

не надо заранее ничего генерировать. подумайте, что вы будете делать если в процессе работы сервиса вдруг выяснится, что число билетов надо увеличить или наоборот уменьшить.

www.php.net/manual/ru/function.uniqid.php

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

Comments

[Stdit]

А выбирать случайный как?

[tenshi]

а я ссылку для чего приложил?

[tenshi]

ну добавить www.php.net/manual/ru/function.md5.php если зачем-то нужна большая «случайность»

[Stdit]

Использовать функции и алгоритмы не по назначению — это плохая практика. В противном случае, это может привести к заблуждениям и багам, как например довольно распространена ошибка считать uniqid случайным числом, а на самом деле там закодирован штамп времени, из-за чего возвращаемые строки идут в алфавитном порядке и поэтому могут быть удобны для построения индекса первичного ключа. Хеши предназначены для проверки данных. А для генерации случайного числа есть генераторы псевдослучайных чисел (mt_rand).

[tenshi]

рандомайзер не гарантирует уникальности. впрочем, да, рандомайзер эффективней связки uniqid+md5, которая также не гарантирует уникальность. так что лучше использовать рандом.

[Stdit]

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

[tenshi]

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

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

Answer 17

[stg34]

Я (почти) такую задачу решал следующим образом
генерируем строки от
«000000»
до
«999999»
и шифруем их, и получаем миллион разных строк.

При чем, в моем случае, номера билетов можно было не хранить в базе, их можно было расшифровывать.

Answer 18

[DemiGray]

Что-то или я туплю или вы ищете слишком сложное решение.
Сделайте таблицу free_tickets в которой будет 1 миллион записей (и где у каждого билета будет GUID) и таблицу purchased_tickets с пустыми записями.

Когда покупают билет — кидайте рендом от 0 до количества зписей в free_tickets. Выпадает порядковый номер записи в таблице. Этот билет перемещаем в purchased_tickets.

Как бы… всё :) ЧЯДНТ?

Comments

[Stdit]

Попробуйте выбрать 999999-й элемент в таблице на миллион элементов, не зная его ключа, в таблице на миллион элементов.

[tenshi]

порядковый номер и есть ключ

[Stdit]

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

[tenshi]

угу, плохо въехал в предлагаемое решение.

[DemiGray]

Хм… Предположим, нам нужен тикет 555.
Вариант №1: (Красивый :)
set @n = 0;
select `ticket_guid` from `free_tickets` LIMIT 555, 1 order by `ticket_guid`;
Вариант №2 (тупой в лоб если нужно показать свою крутизну манагерам):
set @n = 0;
select `ticket_guid`, @n:=@n+1 from `free_tickets` where @n==555 order by `ticket_guid`;

В обоих случаях мы получили GUID билета который имеет порядковый номер 555. Его надо так или иначе перенести в другую таблицу. Лучше всего транзакцией.
P.S. Вариант со счётчиком не прогонял. Лимитный, проверил :)

[DemiGray]

Чёрт, не оттуда копи-паст.

select `ticket_guid` from `free_tickets` order by `ticket_guid`  LIMIT 555, 1

[DemiGray]

Написал и подумал, а зачем нам 2 таблицы. Можно в выборке сделать where purchased=0.

select `ticket_guid` from `free_tickets` where `purchased`=0 order by `ticket_guid`  LIMIT 555, 1

Получив же номер можно с ним что угодно сделать.

Answer 19

[la0]

Парампампам. КостылиКостылиКостылиКостылиКостылиКостыли

Генерируйте ваш мильён записей
tbl (тип — MEMORY!!!!!)
id|crc
Считаете любой хеш (напр.CRC32) записи, берёте 5-8 символов с любой стороны и пишите в поле (один долгий запрос вида, update tbl set crc = substr (5,7,CRC(concat(id,'somerandsmthng'))) ага) обязательно ставите индекс по этому остатку CRC.
insert into newtbl select id as tktid, 0 as uid from tbl order by crc;
В итоге мильён довольно перемешанных записей.
Как-то так.

Comments

[Stdit]

Больше костылей, хороших и разных! А ещё вот:

SET @i = 0;
UPDATE ticket SET sort = (@i := @i + 1) ORDER BY RAND();

[la0]

Для меня приоритет скорость и количество действий)

[Stdit]

Почему бы тогда не записывать вместо crc просто случайный float от 0 до 1?

Answer 20

[DeathCore]

SELECT t.id, t.flag FROM test t,
    (SELECT id mn FROM test WHERE flag = 0 LIMIT 1) tmp1,
    (SELECT ROUND((SELECT MAX(id) FROM test)*rand()) rnd FROM test LIMIT 1) tmp2
WHERE t.id >= rnd AND t.id > mn AND t.flag = 0
LIMIT 1

Первичный ключ id и комбинированный индекс на (id, flag)

на таблице в 36 миллионов записей проходит за 0.002 секунды.

Comments

[DeathCore]

t.id >= mn
Простите, а то первый билет так и не продадите…

[DeathCore]

Замечу, что НЕ НУЖНО добавлять индекс на поле flag ( в вашем случае user), ибо будет в запросе использовать именно этот ключ, а не primary_key.

Answer 21

[DeathCore]

SELECT t.id, t.flag FROM test t,
    (SELECT id mn FROM test WHERE flag = 0 LIMIT 1) tmp1,
    (SELECT ROUND(((SELECT id FROM test WHERE flag = 0 ORDER by id DESC LIMIT 1)-(SELECT id FROM test WHERE flag = 0 LIMIT 1))*rand()+(SELECT id FROM test WHERE flag = 0 LIMIT 1)) rnd FROM test LIMIT 1) tmp2
WHERE t.id >= rnd AND t.id >= mn AND t.flag = 0
LIMIT 1

Учитывая вот этот вот комментарий:

Разве при таком подходе каждый купленный билет не повышает вероятность покупки следующего порядкового билета? К примеру, если куплены все билеты от 0 до 500000, то любое случайное число от 0 до 500000 приведёт к покупке 500001 билета. Таким образом, вероятность его покупки будет примерно 50%.

Переделал запрос. Теперь в такой ситуации будет генерироваться случайное число от 500 000 до 1 000 000

Comments

[Stdit]

Наворочен, не могу понять логику… А если куплены билеты от 200000 до 800000, он будет работать? :)

[DeathCore]

Логика проста. ищем минимальное значение. Потом ищем количество элементов между максимумом и минимумом, не зависимо от флага. Далее с помощью этого диапазона получаем случайное число, которое >= минимума и <= максимума.

Потом все это сравниваем в WHERE.

Хм… второе сравнение на id >= mn уже не нужен… хватит только t.id >= rnd AND t.flag = 0.

Все будет искать довольно шустро. По крайней мере по началу так точно.

За один оставшийся билет не могу ничего сказать…

[DeathCore]

Оставил в таблице единственное значение флага 0…

Даже самый простой запрос:

SELECT id mn FROM test WHERE flag = 0 LIMIT 1

Отрабатывает за 4 секунды… не говоря уже про остальные. Наверное, все же лучше будет с самого начала генерировать таблицу…

Answer 22

[Евгений Безымянников]

Какого формата номер должен быть?

Answer 23

[GreenPeace]

Могу предложить следующий способ:

Выбирается некоторое число, взаимно простое с общим числом билет — в данном случае с числом 999999. Выбрать такое число несложно. Далее — первый билет это остаток от деления выбранного числа на общее число билетов, следующий — это остаток удвоенного выбранного числа. И т.д. Приведу пример. Если выбранное число 1 — то получим обычный порядок по возрастанию. Если 2, то — 2,4,6,8… 999998,1,3… Не трудно показать, что такая последовательность будет содержать все возможные варианты.

Плюсы такого подхода:
1) Очень простая генерация следующего варианта
2) Нет проблем с получением последнего билета

Минусы:
1) Это приближенное решение задачи, и получить любую последовательность таким образом не получиться. В частности общее число различных последовательностей = 999999 — [количество чисел < 999999 и не взаимно простых с ним].
2) В последовательности можно отследить некоторые закономерности. Так, например, номер каждого 3-го билета будет кратен 3-м.

Answer 24

[Samuel_Leonardo]

Немного скоректировал вариант IDDQD, может вам подойдет?
SELECT Count(*) as count_aviable from ticket WHERE user_id = 0;
$rand = rand(1, count_aviable);
… WHERE user_id=0 LIMIT $rand,1;