PHP/MySQL Experts : How to Generate a Unique Sequence of Numbers?

14 years ago

Ok you have to keep track of each session increasing your number and based on that continue with the next binary number, I mean session 1, [1 .. 32] session 2 [33 ..64] session 3 [65 .. 96] and so on, so for each number you have to return an array of numbers as described above and then convert them from decimals to binary and from binary to chars, that is it.
Now let's make the formula, if N is any number (1,2,3,...)
base=(N-1)*32;
A[1]=base+1;
A[2]=base+2;
...
A[32]=base+32;
That will make it
Good luck

Thanks
1 reply

{{ DiscussionBoard.errors[2499197].message }}

xiaophil 14 years ago

Thanks for the reply, although I admit I don't understand the method you are suggesting.

Maybe I didn't explain well enough. There is nothing special about the tokens, they are just numbers.

If each session could get the new value from a sequence 1,2,3... that would be fine, I could hash them to make them look random.

The problem is really twofold:

1) Finding a unique sequence generator that doesn't repeat, but if it's sequential and not pseudo-random then that's not an issue.

2) Atomically selecting the next value from the sequence across multiple simultaneous sessions.

The MySQL auto_increment method is the only one I could come up with. The problem with that is it's impossible to get the next number without writing to the database first. Guess I will just have to take the hit.

Cheers,

Phil
- Thanks
{{ DiscussionBoard.errors[2499459].message }}

jaimegm

14 years ago

Why you don't take the seconds of the Greenwich time as a base plus milliseconds?
I mean the seconds from 1970 up to the moment.

[ 1 ] Thanks
1 reply

{{ DiscussionBoard.errors[2499646].message }}

xiaophil 14 years ago

It would be great to use time and I did consider this, but millisecond precision would steal 10 bits and leave only 22 for the seconds which would wrap in less than two months, and that's a bit soon.

The chances of a collision are probably quite slim but I still wouldn't rest easy.

If the token were larger, say 64-bits, MySQL has a UUID_SHORT function which is guaranteed unique.

Hopefully one day sequences will be built into MySQL. Until then I still think the auto_increment column is the only sensible way forward. Either that or increase the token size.

I miss PostgreSQL and Python. Looking forward to seeing them again.

Cheers,

Phil
- Thanks
- 1 reply
{{ DiscussionBoard.errors[2499844].message }}
- wayfarer 14 years ago
  
  Originally Posted by xiaophil
  
  The chances of a collision are probably quite slim but I still wouldn't rest easy.
  
  So concatenate the time() with a PHP session_id, then hash it. Get a session id like this:
  
  PHP Code:
  
  <?php session_start(); $current_session_id = session_id(); ?>
  
  Now stick it together with time() and hash it. You'll never get a collision this way, not if you try for thousands of years:
  
  PHP Code:
  
  <?php $unique_string = time().$current_session_id; $32_bit_sequence = md5($unique_string); ?>
  
  I may not be totally clear what your aim is. Is there a reason you can't just use PHP's built in session management?
  
  [ 1 ] Thanks
  
  1 reply
  
  Signature
  I build web things, server things. I help build the startup Veenome. | Remote Programming Jobs
  
  {{ DiscussionBoard.errors[2500156].message }}
  
  xiaophil 14 years ago
  
  Originally Posted by MemberWing
  
  unique_token = md5(time().microtime());
  
  Originally Posted by wayfarer
  
  32_bit_sequence = md5(unique_string)
  
  Thanks for the replies guys but an MD5 digest is 128-bits.
  
  I may not be totally clear what your aim is. Is there a reason you can't just use PHP's built in session management?
  
  It's not for session management. I just mentioned sessions to remind that there may be simultaneous access to the sequence.
  
  The requirement is very simple: generate a unique 32-bit token, on demand.
  
  The fewer system resources used the better, although currently it's Hobson's choice because still the only way I can see to do it is the auto_increment method above.
  
  I racked my brain for some time over this one and would be very pleasantly surprised if there were a lighter weight solution available (on LAMP anyway).
  
  Cheers,
  
  Phil
  
  Thanks
  
  2 replies
  
  {{ DiscussionBoard.errors[2501536].message }}
  
  AnthonyThomson 14 years ago
  
  Originally Posted by xiaophil
  
  Thanks for the replies guys but an MD5 digest is 128-bits.
  
  Hi Phil,
  
  What do you think about taking the most/least significant 32 bits of a 128-bit MD5 hash?
  
  Kind regards,
  
  Anthony.
  
  [ 1 ] Thanks
  
  1 reply
  
  {{ DiscussionBoard.errors[2505235].message }}
  
  xiaophil 14 years ago
  
  Originally Posted by AnthonyThomson
  
  What do you think about taking the most/least significant 32 bits of a 128-bit MD5 hash?
  
  Hi Anthony,
  
  I would expect a collision rate of maybe 1 in 1000.
  
  We need to be really careful when truncating hashes to so few bits. I'm not an expert in these things but think it has something to do with the Birthday Problem. I once actually did use a digest truncated to 64-bits but had enough information (and RAM) to compute all the permutations I expected and verify the absence of collisions.
  
  As an aside, I often see MD5 being misused as a magic 'uniqifier' when of course the output domain can only be as unique as the input domain. If that's already unique, and its elements are small, then we don't need a digest.
  
  Also (just for interest's sake) the PHP session ID is a hash of time and microtime, amongst other things. For PHP-5.3.3 anyone interested can take a look at line 371 of session.c
  
  I would really prefer a deterministic approach and am surprised at the apparently limited options of implementing such a seemingly trivial task on the current platform.
  
  Still think I must be missing a trick
  
  Cheers,
  
  Phil
  
  Thanks
  
  1 reply
  
  {{ DiscussionBoard.errors[2506790].message }}
  
  AnthonyThomson 14 years ago
  
  Phil,
  
  I think the best way is to achieve your goal is to use some form of persistence, which unfortunately would involve DB transactions.
  
  The auto-increment approach you outlined in the initial post would work; let me suggest a method for generating a sequence of distinct 32-bit tokens, unique across different sessions:
  
  * Choose an initial value n, where 0≥n>2^32
  * Choose a prime number p, where p is co-prime with 2^32
  * Insert a row with the value of n to your MySQL table
  * For each token to be generated:
  - Read the value of n from your MySQL table
  - n:=n + p (mod 2^32)
  - Update the row in your MySQL table with the updated value of n
  - Issue the value of n as a token
  
  This method will generate a sequence of 2^32 tokens without repitition.
  
  Let me know if this sounds reasonable - feel free to PM me if you like.
  
  Kind regards,
  
  Anthony.
  
  [ 1 ] Thanks
  
  1 reply
  
  {{ DiscussionBoard.errors[2506920].message }}
  
  xiaophil 14 years ago
  
  Hi Anthony,
  
  Thanks for your reply.
  
  n:=n + p (mod 2^32)
  
  Should that be n:=n * p (mod 2^32)?
  
  Anyway I ended up going with a straight sequence from the DB and applying an integer hash according to Knuth's method where p is the golden ratio. The effect is the same as you described only the result doesn't need to be saved.
  
  The hash is computed within the DB from a single insert statement, atomically and without transactions using an on_duplicate hack. It's actual value is unknown however until selected so the net query cost is the same as your solution.
  
  Some problems are far too interesting. While increasing the token length was an option (and a quick fix) the original requirement did not seem overly stringent. Plus I enjoy a challenge.
  
  Thanks again for your input.
  
  Phil.
  
  Thanks
  
  1 reply
  
  {{ DiscussionBoard.errors[2507390].message }}
  
  AnthonyThomson 14 years ago
  
  Phil,
  
  Glad you found a solution to your problem.
  
  I'm pretty sure that n:=(n+p)%(2^32) generates a sequence without repetition; thanks to one of the cool properties of prime numbers.
  
  I could be wrong, but I think that n:=(n*p)%(2^32) isn't guaranteed to generate a sequence without repetition; say you were generating 4-bit keys, n:=(n*p)%(2^4) will unfortunately output a list of keys that repeats every 2 or 4 keys, depending on your choice of p .
  
  Kind regards,
  
  Anthony.
  
  Thanks
  
  1 reply
  
  {{ DiscussionBoard.errors[2507560].message }}
  
  xiaophil 14 years ago
  
  Originally Posted by AnthonyThomson
  
  I'm pretty sure that n:=(n+p)%(2^32) generates a sequence without repetition;
  
  Yes, right you are. I'll remember that one
  
  I could be wrong, but I think that n:=(n*p)%(2^32) isn't guaranteed to generate a sequence without repetition;
  
  Not if n is accumulated, but for m = (n*p)%e where n is sequential and p is the golden ratio of e it seems to shuffle things really well. I didn't see any repeats up to 24-bits anyway.
  
  Thanks again,
  
  Phil
  
  Thanks
  
  {{ DiscussionBoard.errors[2507860].message }}
  
  wayfarer 14 years ago
  
  Originally Posted by xiaophil
  
  Thanks for the replies guys but an MD5 digest is 128-bits.
  
  Ah, yes it is... An MD5 is 32 characters long... which is totally different, but what my brain was thinking of... lol
  
  Thanks
  
  1 reply
  
  Signature
  I build web things, server things. I help build the startup Veenome. | Remote Programming Jobs
  
  {{ DiscussionBoard.errors[2507629].message }}
  
  xiaophil 14 years ago
  
  Originally Posted by wayfarer
  
  An MD5 is 32 characters long...
  
  I tend to think in terms of binary - a hangover from hardware design I guess.
  
  If you printed a 128-bit number in base-16 (and left padded any zeros) then it could certainly be 32 characters long.
  
  5d41402abc4b2a76b9719d911017c592
  
  All of these are the same as the number above, assuming it's unsigned:
  
  1352024005257045452355345614731042005742622
  
  123957004363873451094272536567338222994
  
  5IR3T0OZOELRNAUHRWYU1XFGY
  
  10111010100000101000000001010101011110001001011001 01010011101101011100101110001100111011001000100010 000000101111100010110010010
  
  Cheers,
  
  Phil
  
  [ 1 ] Thanks
  
  {{ DiscussionBoard.errors[2507941].message }}

MemberWing

14 years ago

Originally Posted by xiaophil

I originally thought this would be quite simple but it now appears far from trivial. Perhaps I am missing something.

I want a way to create a sequence of 32-bit tokens that does not repeat and must be guaranteed unique across different sessions.

Preferably pseudo-random but sequential would be OK too.

Although MySQL does not support sequences one possible way is to create a table with an auto_increment column and for a new token insert NULL and then read back last_insert_id, but I would prefer to avoid an extra database write per session.

Any other ideas?

The tokens must be 32-bits long and the method work consistently on 32/64-bit servers without requiring any extensions or privileges beyond a typical default hosting account.

I'm beginning to think the above method may be the only way and would be interested in the thoughts of some more experienced PHP/MySQL developers.

Cheers,

Phil

$unique_token = md5(time().microtime());

Gleb

[ 1 ] Thanks

Signature

| Law of Attraction Coaching | Secure Fast Hosting | Law of Attraction |

{{ DiscussionBoard.errors[2500144].message }}

KirkMcD

14 years ago

Microshell Emulating nextval() function to get sequence in MySQL

[ 1 ] Thanks
1 reply

{{ DiscussionBoard.errors[2507247].message }}

xiaophil 14 years ago

Originally Posted by KirkMcD

Microshell Emulating nextval() function to get sequence in MySQL

Thanks Kirk,

That's an interesting idea although it's a fair bit of overhead just to get a number and I am not sure about its atomicity.

Also not sure if function creation is permitted by default on a typical shared host.

I think it's aimed more at a compatibility layer for PostgreSQL sequences?

Cheers,
Phil
- Thanks
{{ DiscussionBoard.errors[2507512].message }}

wayfarer

14 years ago

I was thinking about this post, and queried this: crc32. I wasn't even aware of this hash type, but apparently it's been available in PHP for quite some time now. According to this page, the chance of a random collision is 1 / 2^32

Thanks
1 reply

Signature

I build web things, server things. I help build the startup Veenome. | Remote Programming Jobs

{{ DiscussionBoard.errors[2514809].message }}

xiaophil

14 years ago

Originally Posted by wayfarer

I was thinking about this post, and queried this: crc32. I wasn't even aware of this hash type, but apparently it's been available in PHP for quite some time now. According to this page, the chance of a random collision is 1 / 2^32

Hi,

I think there may be some confusion about CRC32 on the page you referenced.

As it's not a 'perfect hash' a CRC32 will generate the same output even for many different inputs, and the chances of collision are much, much higher than the figure mentioned.

I think generally a common point of confusion is the difference between 'random' and 'unique'.

A good random number generator will repeat some numbers before using all the numbers in its range. That's what random is - each new selection is independent of all the previous selections, so having repeating numbers is normal and desirable for an RNG.

A 'unique' number generator is a little different. The simplest of course is to just start counting 1,2,3... but if we want the numbers to be unpredictable then what is really needed is a shuffle where each number will only be used once. See the discussion I had with Anthony for some ways to achieve this.

A unique sequence may look random, and the choice of number may be (pseudo) random, but the sequence itself is certainly not random.

Even with 2^32 unique inputs, a CRC32 would repeat many, many times and the collision rate can be no better than random numbers which I still think would generally average around 1 in 1000 for 32-bits.

Cheers,
Phil

Thanks

{{ DiscussionBoard.errors[2518314].message }}

bucksuper

14 years ago

Here you go man. If you just want numbers modify the function and remove the letters.

<?
//GET A RANDOM STRING
echo createRandomString('25');

//*****************************
//FUNCTION: CREATE RANDOM STRING
//*****************************
function createRandomString($stringLength) {
$chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVW XYZ0123456789";
srand((double)microtime()*1000000);
$i = 0;
$pass = '' ;
while ($i <= $stringLength) {
$num = rand() % 33;
$tmp = substr($chars, $num, 1);
$randomNum = $randomNum . $tmp;
$i++;
}
return $randomNum;
}

?>

Let me know if you need any help with it.
Best of luck!

[ 1 ] Thanks
1 reply

Signature

300% Traffic Return check out Trippy Wire Content Exchange! (100% FREE!)
Trippy Wire Content Exchage Network

Trippy Wire is looking for partners in these niches niches: Humor, Movies, Gaming, Celebrities, Entertainment, Sports, Food & Drinks, Hot Women, Technology & Transportation.

{{ DiscussionBoard.errors[2516830].message }}

xiaophil

14 years ago

Originally Posted by bucksuper

Here you go man. If you just want numbers modify the function and remove the letters.

//*****************************
//FUNCTION: CREATE RANDOM STRING
//*****************************
function createRandomString($stringLength) {
$chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS TUVW XYZ0123456789";
srand((double)microtime()*1000000);
$i = 0;
$pass = '' ;
while ($i <= $stringLength) {
$num = rand() % 33;
$tmp = substr($chars, $num, 1);
$randomNum = $randomNum . $tmp;
$i++;
}
return $randomNum;
}

Hi, and thanks for your reply.

Although using a PRNG is not suitable for my application I do have a few thoughts on the code you supplied and some suggestions for improvements if you are interested.

1) The number of selectable characters in the code you posted is 62 but the code is only selecting from the first 33.

2) PHP's rand() function is really a terrible PRNG. On some platforms it's default range is only 15-bits. mt_rand() using the Mersenne Twister algorithm is better, but still only 31 bits on some platforms, I believe.

3) Seeding is done automatically since PHP 4.2. Reseeding every time is not necessary and probably won't make things any more random.

4) If you rearranged the selectable string a bit you could have a generic function for generating strings of random numbers for any base from 1 to 62.

Here's a function I use for generating pseudo-random keys, passwords and numbers of different bases.

function _random_key($length,$base) {
$chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm nopqrstuvwxyz';
$key = '';
for ( $i=0; $i<$length; $i++ ) {
$key .= $chars[ (mt_rand( 0, ($base-1) ))];
}
return $key;
}

(sorry about the formatting - the forum barfed on php or code tags, so plain text it is. That space after the 'm' in the chars string isn't really there either.)

So for a random 32-bit number as hex...

_random_key(8,16)

or whatever length and base you want, up to base 62.

Cheers,

Phil

[ 1 ] Thanks
1 reply

{{ DiscussionBoard.errors[2518441].message }}

wayfarer

14 years ago

Originally Posted by xiaophil

(sorry about the formatting - the forum barfed on php or code tags, so plain text it is. That space after the 'm' in the chars string isn't really there either.)

Before you submit your post, scroll down to "Additional Options" and uncheck the "Automatically parse links in text". This option messes with PHP highlighting on this forum for whatever reason.

Thanks

Signature

I build web things, server things. I help build the startup Veenome. | Remote Programming Jobs

{{ DiscussionBoard.errors[2519835].message }}

Johnny Slater

14 years ago

That code looks very familiar bucksuper... lol

It's almost exactly the same as the code I had in SMP to generate random passwords. It looks like an advanced workup of what I had.. but really nice use of a random character generator.

Thanks
1 reply

Signature

{{ DiscussionBoard.errors[2517158].message }}

bucksuper

14 years ago

Originally Posted by Johnny Slater

That code looks very familiar bucksuper... lol

It's almost exactly the same as the code I had in SMP to generate random passwords. It looks like an advanced workup of what I had.. but really nice use of a random character generator.

Johnny,
What's SMP?
I don't think I wrote that from scratch but I definetely modded it. Not sure but I've been using it for years.

Thanks

Signature

300% Traffic Return check out Trippy Wire Content Exchange! (100% FREE!)
Trippy Wire Content Exchage Network

Trippy Wire is looking for partners in these niches niches: Humor, Movies, Gaming, Celebrities, Entertainment, Sports, Food & Drinks, Hot Women, Technology & Transportation.

{{ DiscussionBoard.errors[2526326].message }}

Johnny Slater

14 years ago

Buck, sorry haven't been in this area of the forum for a few days and missed your question. SMP is Simple Member Pro. It's a membership script I wrote 3 years ago.

It does use some code from another script that I had PLR to, namely the admin and member logins and html formatting. The code you posted was almost line for line the same code that is in the common class that was in the code I modeled my script after. A lot of people do have rights to that particular block of code so it wouldn't surprise me if you did see it in another script some time in the past.

Thanks
1 reply

Signature

{{ DiscussionBoard.errors[2546067].message }}

Chris Jenkins 14 years ago

Guys I am looking for someone to Modify the Butterfly script to not include the the JV partners with my normal Autoresponder List.

If one of you would be interested or knows someone that would be please let me know I appreciate the help.

Chris
- Thanks
Signature

Become a Super Affiliate - See What Current Members Have To Say Here

Discover The Software That Creates Multiple Income Hybrid Affiliate Stores To Make
$500/Day... ON COMPLETE AUTOPILOT!
{{ DiscussionBoard.errors[2558912].message }}

PHP/MySQL Experts : How to Generate a Unique Sequence of Numbers?

Trending Topics

Best AI for spell checking & grammar (2024)?

Google Ads, landing pages, and Clickbank links

Carry out better target audience research

A Very Strange Internet Problem

YouTube gets shopping display tools and affiliate partnership updates