Generation of 1 million tickets with random unique IDs

Question

PHP

Good afternoon!

The task is as follows:
There are 1 million "tickets" that can be bought by players. Upon purchase, the player is given a ticket with a number from 1 to 999999. The numbers must be random (not sequential) and unique. Each player can buy as many tickets as they want.

Tools:
PHP + MySQL. Most likely, a sign (ticket_id, user_id).

Conditions:
High load. All tickets likely to be sold.

I wonder who would solve such a problem? The only thing that came to my mind so far is:

1. When buying a ticket, we generate a random number (ticket number) and check if there is one in the database (already purchased). If there is, we generate the following. I don’t like the fact that the more tickets sold, the longer it will work. And it seems impossible to buy the last ticket at all.

2. Generate 1 million records with ticket numbers in advance in the database and choose WHERE user_id=0 ORDER BY RAND() LIMIT 1;

For now, I'm leaning towards the second option. Maybe someone else knows (or comes up with) some solutions?
Thanks

Answer 1

As an option, generate a table with 1 million records in advance, only mix these records in the table.
And give out - in order.

Answer 2

Write 1 million tickets to the database in random order. After that, choose the tickets in order.

Answer 3

Alternatively, you can create an additional field (sort) for tickets and fill it with unique random numbers. After that, make an index by user_id and sort. Test on a table with a million records (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

in the case of the condition 1 million from 0 to 999999, it is better to generate everything and mix it in advance.
but if you really need a lot of tickets, then GUID / UUID can help you , since it is not implemented in all possible ways.

Answer 5

hash, filter by hash =))

Answer 6

the simplest option:
$rand = rand(1, 1000000);
… WHERE ticket_id >=$rand AND user_id=0 LIMIT 1;
If the loads are really high, then we generate the ticket_id(PK)|rand_num|user_id table with a unique rand_num in advance, and store the increment from the last purchased ID in the cache. We read and update exclusively by PK, and as a failover - a small procedure for obtaining the ID of the last purchased ticket from the database in case the cache falls.

Answer 7

If this is not a synthetic task like “how would you hammer a nail with only a hammer”, then Redis copes well with such tasks - you can write all numbers in advance in set (in any form - even numbers, even strings, you only need to store a million numbers -three MB of memory) and through SPOP get a random number with algorithmic complexity O(1).

Answer 8

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; //Продаём билет.

Answer 9

Make a table with _3_ fields:
ticket_id (internal ID, sequential)
ticket_number (ticket number)
user_id (buyer ID)
When creating a table, fill in the ticket_id field sequentially, and ticket_number in random order. As a result, we can easily get the following random unsold ticket:
SELECT * FROM tickets WHERE user_id IS NULL ORDER BY ticket_id LIMIT 1;
we create an index one by two fields - user_id and ticket_id. This index will both speed up this query and help you get a list of tickets owned by a particular user.
only you must not forget about blocking - otherwise there may be collisions when buying a ticket.

Answer 10

Try it with your odds. Somewhere you have to store the previous generated number.

Answer 11

Divide the problem into 100 parts, it will be easier to solve

Answer 12

ORDER BY RAND it will be tin
Break it into intervals with a step, say, 5,000
The first random is the choice of an interval, say from 200,000 to 205,000
Then check, run through this interval and find all the "empty" values. Pick a random one among them.
If there are no “empty” ones, mark that this interval is fully occupied and do not use it again

Answer 13

In the next post, the issue of random choice is just being discussed. habrahabr.ru/post/154905/

Answer 14

I like the shuffle-ahead option, but if you don't want true randomness and just want the numbers to not look consecutive, you can use bit-shuffled consecutive numbers. For example, if you take five bits, renumber the bits in order from right to left 5, 4, 3, 2, 1 and mix them, for example, like 4, 1, 2, 5, 3, then the sequence is 1, 2, 3, 4, 5 , 6 will become 8, 4, 12, 16, 24, 20.
PS: Will MySQL slow down on an index of 1 million numbers?

Answer 15

With an amount of 1 million out of 1 ml of valid values, there can be no randomness. Think about how to issue without using a table at all.
The first thing that came to my mind was to use a memcache to store the already issued id.
$rand = rand(1, 1000000);
$memkey ="ticket_".$rand;
if ($get_result = $memcache->get($memkey))
{
This ticket has already been sold, generate another one
}
{
The ticket has not been sold. Write to the database and
memcache $memcache->set($memkey, $rand, false);
}

Answer 16

no need to pre-generate anything. think about what you will do if, during the operation of the service, it suddenly turns out that the number of tickets needs to be increased or vice versa reduced.
www.php.net/manual/ru/function.uniqid.php
for each ticket we generate an identifier and save it to the database. we control that the number of records in the database does not exceed the limit we need. all. the logic is simple and efficient.

Answer 17

I (almost) solved such a problem as follows: we
generate strings from
“000000”
to
“999999”
and encrypt them, and we get a million different strings.
Moreover, in my case, the ticket numbers could not be stored in the database, they could be decrypted.

Answer 18

Something or I'm stupid or you are looking for a too complicated solution.
Make a free_tickets table with 1 million entries (and where each ticket has a GUID) and a purchased_tickets table with empty entries.
When buying a ticket, randomize from 0 to the number of entries in free_tickets . The serial number of the record in the table drops out. We move this ticket to purchased_tickets .
How would ... everything :) CHAYDNT?

Answer 19

Parampampam. CrutchesCrutchesCrutchesCrutchesCrutchesGenerate
your millions of tbl records
(type - MEMORY!!!!!)
id|crc Calculate
any hash (eg CRC32) of the record, take 5-8 characters from either side and write in the field (one long request like, update tbl set crc = substr (5,7,CRC(concat(id,'somerandsmthng'))) yeah) be sure to put an index on this CRC remainder.
insert into newtbl select id as tktid, 0 as uid from tbl order by crc;
As a result, millions of rather mixed records.
Something like this.

Answer 20

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

Primary key id and combined index on (id, flag)
on ​​a table of 36 million records takes 0.002 seconds.

Answer 21

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

Considering this comment:

Doesn't each purchased ticket increase the probability of buying the next sequential ticket with this approach? For example, if all tickets from 0 to 500000 are bought, then any random number from 0 to 500000 will lead to the purchase of 500001 tickets. Thus, the probability of buying it will be approximately 50%.

Changed the request. Now, in such a situation, a random number from 500,000 to 1,000,000 will be generated

Answer 22

What format should the number be?

Answer 23

I can suggest the following method:
A certain number is selected that is coprime with the total number of the ticket - in this case, with the number 999999. It is not difficult to choose such a number. Next - the first ticket is the remainder of dividing the selected number by the total number of tickets, the next is the remainder of the doubled selected number. Etc. I'll give you an example. If the selected number is 1, then we get the usual ascending order. If 2, then - 2,4,6,8… 999998,1,3… It is not difficult to show that such a sequence will contain all possible variants.
Pros of this approach:
1) Very easy generation of the next option
2) No problem getting the last ticket
Cons:
1) This is an approximate solution of the problem, and it is not possible to obtain any sequence in this way. In particular, the total number of distinct sequences = 999999 - [the number of numbers < 999999 and not coprime with it].
2) In the sequence, you can track some patterns. So, for example, the number of each 3rd ticket will be a multiple of 3rd.

Answer 24

Slightly corrected the IDDQD option, maybe it will suit you?
SELECT Count(*) as count_aviable from ticket WHERE user_id = 0;
$rand = rand(1, count_aviable);
... WHERE user_id=0 LIMIT $rand,1;