0

In this scenarion I have some managers(around 150 in numbers). One of their daily job is to generate 50(constant) authorisation code (6-8 digit numbers) which are stored in db with their Id. If any authorisation code is used that code is marked as used and triggers delete them when they are 15 days old and have been used.

In my table i have set authorisation code as unique key. i generate a random number then query the db if it exists i generate another or i else save it.

Every thing is fine except my logic of checking the existence of number in db.This round trip + checking is causing significant delay as of now there are over 1090083 pending authorisation code. Since these authorisation code are in circulation we cant revoke it and with current load it is taking sometime to find new numbers.

I need to implement it in a different logic for which execution speed should be low regardles of number of random number that has been used.

My table is designed as follows

slno(auth increment) || auth_code (random code) || auth_by (created by) || used (1=used/0=unused)

Ratna
  • 2,289
  • 3
  • 26
  • 50
  • Don't generate it with C# but in your database. That's more efficient and safer. – Tim Schmelter Jul 04 '13 at 11:50
  • 1
    there are in-build classes but chases are there to get duplicate numbers. You will have to keep the old values and check it from yourself. – शेखर Jul 04 '13 at 11:54
  • 2
    Out of curiosity why did they have to be random? Why couldn't they have been sequential? They would have been unique and much easier to calculate? Then simply roll over as / when required. – Belogix Jul 04 '13 at 11:56
  • 1
    Belogix: I assume if they are authorisation codes they are meant to be unguessable in some way. Though having over 1% of your possible codes being valid seems like guessing them isn't going to be that much of a problem anyway... – Chris Jul 04 '13 at 12:12
  • well, if your guess is correct also,you still have to guess serial no which is set to auto generate. and till time there have been no correct guess. – Ratna Jul 04 '13 at 13:51
  • If the auth. codes are in a database, shouldn't they be an index with a hash? Then finding a match really should not be a problem (even if it would be just an ordered list, it would take just O(log(n)) to check for a hit). You say you have 1M of auth. codes pending, that's 1% of your total pool, still 99% chance for generating a good number for the first try. However if that went up to 20% or so, then that could well indicate something is conceptually wrong with the system (how much time did it took to populate this 1% - will that ever happen)? – Jubatian Jul 04 '13 at 18:24

3 Answers3

0

The easiest thing to do is generate random numbers and generating a new random id if you get a duplicate. This works because with your figures the probability of getting a duplicate is pretty small.

If that doesnt convince you, you can think of many schemes that guarantee mathematically that the numbers will be unique and still look random, but it gets complex.

Joni
  • 108,737
  • 14
  • 143
  • 193
  • Please give link to those schemes, complexity wont be a problem as long as calculus is out is out of the scene. – Ratna Jul 04 '13 at 14:59
  • Two examples here: http://stackoverflow.com/questions/15073971/generate-random-looking-code-from-consecutive-integers – Joni Jul 04 '13 at 15:14
0

If your database does not support to create unique ids:
- Set up a table with all random numbers which are sorted by value and its size is stored and available.

  • Randomly select an element of this table.
  • Get the successor element. If the successor element is a neighbor of the element, take the next successor element. If you reach the last element, start over with the element from step 2 and take now the predecessor.
  • Now simply choose a random range with element-next element and get your random number.
  • Ready !

EXAMPLE: You stored all your ids in a sorted table. Lets assume this is e.g.
{890, 1045, 2345, 2346, 4087}

First step: Select one of them randomly. You get that e.g. by C# 

Random random = new Random();  
int indexOfNumber = random.Next(0, myTableSize);

Second step: You got the index, lets assume it is 2. You are now getting the next number at index 3, it is 2346. Unfortunately it is a direct neighbor, so you continue to index 4. This is 4087.

Third step: Create your number by 

int myRandomNumber = previousElement + random.Next(1,nextElement-previousElement);

in this case:

int myRandomNumber = 2346 + random.Next(1, 4087-2346);

Store the new random number. With this you will read mostly two elements from the database (probably some more) independent of the size of the database. Creating two random numbers is insignificant. You must only care for the edge cases if your index is at the end (simply reverse the search direction).

Thorsten S.
  • 4,144
  • 27
  • 41
0

Consider this. If randoms are unique and stored in a base in some kind of (code_id, code, other_data) table way, you can just add anoter table in your base: (code, code_id) with the code field being indexed granting you some nice logariphmycal search.

But given this, you can also create an additional key right in your first table instead. As soon as code is unique, it would work fine.

akalenuk
  • 3,815
  • 4
  • 34
  • 56