0

I am trying to generate unique values in c# with the help of DateTime ticks and and incrementing number. Pseudo code:

  1. Take last 43 significant bits from DateTime.Now ticks (lets name it A)
  2. Take last 21 bits from increasing sequence (lets name it 'B')
  3. Left shift 'A' 21 times (lets name it 'C')
  4. Do binary OR in A and C

I ran the test for generating 2 million number and inserting in database column which has unique constraint set and it ran successfully.

Here is the piece of code that does that:

    private static long _sequence = 1;
    public static long GetUniqueNumber()
        {
            const int timeShift = 21;            
            var dateTime = DateTime.Now.Ticks;
            const long dateTimeMask = ~(0L) >> timeShift; 
            const long sequenceMask = ((~(0L) >> (64 - timeShift))); 
            var seq = Interlocked.Increment(ref _sequence);
            var dateTimeNo = (dateTimeMask & dateTime) << timeShift;
            var seqNum = (seq & sequenceMask);    
            var num = dateTimeNo | seqNum;
            return num;
        }

I have two questions: 1. Is this logic good enough to generate unique numbers ? 2. I find that some generated numbers are '-ve' which I didn't understand.

Any help/suggestions/improvements are welcome.

ZeNo
  • 1,648
  • 2
  • 15
  • 28
  • Do you need to worry about executing this in multiple processes, and/or on multiple machines? That may result in duplicates. Also, have you considered using `Guid`? That's a 128bit random number with a fairly good diffusion on it. –  Mar 28 '12 at 06:31
  • @Will, In near future it is supposed to be running on single machine and single process. I am thinking of using this number which can be indexed in sql server that why I am currently not focusing on Guid, in worst case scenario I will opt for Guid. – ZeNo Mar 28 '12 at 06:34
  • 1
    `Guid` is equivalent to `uniqueidentifier` in SQL server, and can be indexed by SQL Server. –  Mar 28 '12 at 06:37
  • @Will: I am sticking with Guid as suggested by you and Jon – ZeNo Mar 28 '12 at 07:51

2 Answers2

6

Is this logic good enough to generate unique numbers

Unique across what scope? Across multiple computers/processes/AppDomains?, certainly not. Within a single AppDomain? Not really. Generating 2 million numbers is irrelevant - that's just testing that your sequence part works. (221 is just over 2 million.)

If you can call GetUniqueNumber 221+1 times within the granularity of DateTime.Now (which is likely to be ~10-15ms) then you'll get a repeat. Have you measured how fast your computed can call this?

Then there's the fact that those 43 bits will be repeated in 243 ticks' time... or at least would be if you had a sufficiently fine-grained clock. (And sooner or later the granularity will work against you.)

I find that some generated numbers are '-ve' which I didn't understand.

Whenever dateTimeNo has its top bit (out of 43) set, you'll end up with a long with the top bit set - which means it'll be negative.

EDIT: Also note that your shifting is broken. This:

const long dateTimeMask = ~(0L) >> timeShift;

is performed a sign-extended shift - so you're just ending up with ~0L.

In short: use Guid.NewGuid. It's what it's there for.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • After giving another thought I realized that we might be running it on more than one process in near future. I am reverting to Guid for now. Thanks for the help. – ZeNo Mar 28 '12 at 07:52
  • Jon - what if i need temporal ordering like in: http://stackoverflow.com/questions/5608980/how-to-ensure-a-timestamp-is-always-unique What do you think of the solution presented there ? – JanivZ Jan 07 '13 at 15:36
0

Negative numbers are due to implementation of long. As it is a signed number, if MSB that is bit 64 becomes '1' after the bit wise manipulation, the number will become negative. Nothing to worry about that.

Apurv Gupta
  • 870
  • 7
  • 14