How to ensure a timestamp is always unique?

Question

I'm using timestamps to temporally order concurrent changes in my program, and require that each timestamp of a change be unique. However, I've discovered that simply calling DateTime.Now is insufficient, as it will often return the same value if called in quick succession.

I have some thoughts, but nothing strikes me as the "best" solution to this. Is there a method I can write that will guarantee each successive call produces a unique DateTime?

Should I perhaps be using a different type for this, maybe a long int? DateTime has the obvious advantage of being easily interpretable as a real time, unlike, say, an incremental counter.

Update: Here's what I ended up coding as a simple compromise solution that still allows me to use DateTime as my temporal key, while ensuring uniqueness each time the method is called:

private static long _lastTime; // records the 64-bit tick value of the last time
private static object _timeLock = new object();

internal static DateTime GetCurrentTime() {
    lock ( _timeLock ) { // prevent concurrent access to ensure uniqueness
        DateTime result = DateTime.UtcNow;
        if ( result.Ticks <= _lastTime )
            result = new DateTime( _lastTime + 1 );
        _lastTime = result.Ticks;
        return result;
    }
}

Because each tick value is only one 10-millionth of a second, this method only introduces noticeable clock skew when called on the order of 10 million times per second (which, by the way, it is efficient enough to execute at), meaning it's perfectly acceptable for my purposes.

Here is some test code:

DateTime start = DateTime.UtcNow;
DateTime prev = Kernel.GetCurrentTime();
Debug.WriteLine( "Start time : " + start.TimeOfDay );
Debug.WriteLine( "Start value: " + prev.TimeOfDay );
for ( int i = 0; i < 10000000; i++ ) {
    var now = Kernel.GetCurrentTime();
    Debug.Assert( now > prev ); // no failures here!
    prev = now;
}
DateTime end = DateTime.UtcNow;
Debug.WriteLine( "End time:    " + end.TimeOfDay );
Debug.WriteLine( "End value:   " + prev.TimeOfDay );
Debug.WriteLine( "Skew:        " + ( prev - end ) );
Debug.WriteLine( "GetCurrentTime test completed in: " + ( end - start ) );

...and the results:

Start time:  15:44:07.3405024
Start value: 15:44:07.3405024
End time:    15:44:07.8355307
End value:   15:44:08.3417124
Skew:        00:00:00.5061817
GetCurrentTime test completed in: 00:00:00.4950283

So in other words, in half a second it generated 10 million unique timestamps, and the final result was only pushed ahead by half a second. In real-world applications the skew would be unnoticeable.

Answer 1

One way to get a strictly ascending sequence of timestamps with no duplicates is the following code.

Compared to the other answers here this one has the following benefits:

1. The values track closely with actual real-time values (except in extreme circumstances with very high request rates when they would get slightly ahead of real-time).
2. It's lock free and should perform better that the solutions using lock statements.
3. It guarantees ascending order (simply appending a looping a counter does not).

public class HiResDateTime
{
   private static long lastTimeStamp = DateTime.UtcNow.Ticks;
   public static long UtcNowTicks
   {
       get
       {
           long original, newValue;
           do
           {
               original = lastTimeStamp;
               long now = DateTime.UtcNow.Ticks;
               newValue = Math.Max(now, original + 1);
           } while (Interlocked.CompareExchange
                        (ref lastTimeStamp, newValue, original) != original);

           return newValue;
       }
   }
}

Also note the comment below that original = Interlocked.Read(ref lastTimestamp); should be used since 64-bit read operations are not atomic on 32-bit systems.

Answer 2

Er, the answer to your question is that "you can't," since if two operations occur at the same time (which they will in multi-core processors), they will have the same timestamp, no matter what precision you manage to gather.

That said, it sounds like what you want is some kind of auto-incrementing thread-safe counter. To implement this (presumably as a global service, perhaps in a static class), you would use the Interlocked.Increment method, and if you decided you needed more than int.MaxValue possible versions, also Interlocked.Read.

Answer 3

DateTime.Now is only updated every 10-15ms.

Not a dupe per se, but this thread has some ideas on reducing duplicates/providing better timing resolution:

How to get timestamp of tick precision in .NET / C#?

That being said: timestamps are horrible keys for information; if things happen that fast you may want an index/counter that keeps the discrete order of items as they occur. There is no ambiguity there.

Answer 4

I find that the most foolproof way is to combine a timestamp and an atomic counter. You already know the problem with the poor resolution of a timestamp. Using an atomic counter by itself also has the simple problem of requiring its state be stored if you are going to stop and start the application (otherwise the counter starts back at 0, causing duplicates).

If you were just going for a unique id, it would be as simple as concatenating the timestamp and counter value with a delimiter between. But because you want the values to always be in order, that will not suffice. Basically all you need to do is use the atomic counter value to add addition fixed width precision to your timestamp. I am a Java developer so I will not be able to provide C# sample code just yet, but the problem is the same in both domains. So just follow these general steps:

1. You will need a method to provide you with counter values cycling from 0-99999. 100000 is the maximum number of values possible when concatenating a millisecond precision timestamp with a fixed width value in a 64 bit long. So you are basically assuming that you will never need more than 100000 ids within a single timestamp resolution (15ms or so). A static method, using the Interlocked class to provide atomic incrementing and resetting to 0 is the ideal way.
2. Now to generate your id you simply concatenate your timestamp with your counter value padded to 5 characters. So if your timestamp was 13023991070123 and your counter was at 234 the id would be 1302399107012300234.

This strategy will work as long as you are not needing ids faster than 6666 per ms (assuming 15ms is your most granular resolution) and will always work without having to save any state across restarts of your application.

Answer 5

It can't be guaranteed to be unique, but is perhaps using ticks is granular enough?

A single tick represents one hundred nanoseconds or one ten-millionth of a second. There are 10,000 ticks in a millisecond.

Answer 6

Not sure what you're trying to do entirely but maybe look into using Queues to handle sequentially process records.