[RESOLVED] Keycode generation (in millions)

[bike5]

What is the best way to generate random unique keys in the millions. Is there a better way then creating a random key, querying the database to see if it already exists. That is A LOT of queries, especially if in high numbers I keep getting keys generated that already exists. I was thinking maybe generating them into an array and doing an array_unique but a few million 10-20character strings I thought would be too much memory to handle? Any suggestions or ideas?

Thanks

[Weedpacket]

If your key generator has a much larger range of possible values than mere millions there shouldn't be many duplicates, but sooner or later every key is going to have to be checked against every other key to ensure they're not duplicates.

You can use PHP's internal hashtable array lookup to do the checking.

$keys = array();
for($i=0; $i<$number_of_keys_wanted; $i++)  $keys[generate_key()] = true;
while(count($keys)<$number_of_keys_wanted) $keys[generate_key()] = true;

Could you explain what you're after in a bit more detail? Like, where does the database come in? Where do you get your keys from, and why do you need so many all at once? If you've already got millions of keys assigned and want to assign another one then the "generate/check" cycle would be the way to go - again, if the pool of possible keys is much larger than you need there shouldn't be much trouble. Like, if you have a billion possible keys and you've assigned a million of them, the chances of generating one that's already assigned and therefore having to generate another is one in a thousand; and the chances are less than one in a million that you'll have to do that twice. On the other hand, if you've only got a million possible keys and you've assigned 750,000 - you've got a 3/4 chance of picking a key that's already assigned, and a 9/16 chance of doing it twice.

[dagon]

sounds like you could just use an auto increment column in a db, if you need something better than 1,2,3 there's md5 hash of the auto increment column and I'm personally quite found of: md5(uniqid(rand(), true)).

But as Weedpacket said, its not that clear what approach would be best from what you have said you want.

[bike5]

This is for a online game sweepstakes sorta thing. It varies based on params so sometimes I might need to send a store a million keys to print on receipts, maybe 20+million depending on the area. The letters/number and length have to be configurable to meet client wishes if possible so if they need a million but want the lowest possible characters to meet that mark to make it easier for people to type (or wanting all uppcase or a mix or only certain letters) ect. Some games a key wont be generated until a signup so they can be made on the fly, some will be a combination where I need to create a batch and then add them on the fly or another batch depending on participants.

If it works better I could even create a much larger pool then required and instead of assigning new keys on the fly grab a key not taken from the existing pool that way all my actualy key processing is done up-front. My biggest concern is the processing time to create a new key on the fly if the mysql query takes too long to lookup to see if a key exists and repeat until it finds a key that doesn't exist. I assume the time would be negligible until you get into the millions. I am not sure however how long a query would take against a larger data set.

Do you have any idea how long a query would take to lookup on 1 unique column on say 10/20/30/40million records? I will probably have to end up testing each way just to verify everything but if anyone has any experience/advice in this type of thing let me know. Thanks for the replies.

[NogDog]

I'm thinking that you could populate a database table with the strings in one column, then have a second tinyint or bool column to indicate which have been used, (0 for available and 1 for used). If you index that "used" column, then I think you could do something like:

mysql_query("UPDATE table_name SET used = 1 WHERE used = 0 AND @value := key_column LIMIT 1");
$result = mysql_query("SELECT @value"); // get the key saved in the MySQL variable
$key = mysql_result($result, 0);

[Weedpacket]

There won't be any appreciable delays in checking to see if a possible key has already been assigned unless and until you (a) you have a lot of keys assigned already, and (b) the number of keys assigned is close to the number of possible keys. Even then, assuming decent indexing, the increase in the number of tree branches/hash probes required to verify the presence or otherwise of the key grows only slowly with the number of keys assigned.

[NogDog]

Or you could go for the unique-but-not-really-random approach:

function genKey()
{
   $mtime = microtime();
   $parts = explode(' ', $mtime);
   $parts[0] = '1' . substr($parts[0], 2);
   $key = base_convert($parts[0], 10, 36) . base_convert($parts[1], 10, 36);
   return $key;
}