How to generate unique order number?

Question

I'm looking for a good way to generate a unique order ID. Can you see any problems with the code below?

int customerId = 10000000;

long ticks = DateTime.UtcNow.Ticks;

long orderId = customerId + ticks;

int orderNumber = orderId.GetHashCode();

I'm going to check that the number is unique in the database before creating the order.

Answer 1

If you are storing your records in a database, you should really look into the capabilities available there to generate unique surrogate keys. In SQLServer this would be an IDENTITY field and in Oracle it would be a field that uses a SEQUENCE to generate a new value.

If there's a compelling reason why you can't use your database to generate a unique key, you should look at something like a Guid - which has a mucher higher probability than date-time manipulation to generate a unique value. Guids can be trivially converted into strings, so your identifier would be a string in this case.

What you are doing with hashes is not a good idea - nothing gaurantees that hashes will be unique - and in many cases they do indeed collide. Guids - don't provide a 100% guarantee of uniqueness across machines but on a single machine they should always be unique. And even across machines, their chances of collision are extremely remote. Also, using machine time as a way to build up the underlying value is subject to race conditions (like those Eric describes).

Guids are 128-bit values, so you can't represent them as a simple int or long. It would require you to use string as your IDs, which may or may not be possible in your case, depending on other considerations (like whether or not you control the data model). If can use them, using a Guid is really easy:

string customerId = Guid.NewGuid().ToString(); // fetch new guid and save as string
string orderNumber = Guid.NewGuid().ToString(); // same story here...

If you really must use a numeric identifier, and you are willing to abandon easily scaling your application across multiple servers, you could use an auto-incrementing global number to supply a unique key. You would have to seed this number with the next available value (max+1) from your database when the application starts up. You would also have to then protect this value from concurrent use from multiple threads. I would wrap this responsibility in a class:

class static UniqueIDGenerator 
{
    // reads Max+1 from DB on startup
    private static long m_NextID = InitializeFromDatabase(); 

    public static long GetNextID() { return Interlocked.Increment( ref m_NextID ); }
}

EDIT: In this day and age, compelling reasons for generating unique IDs in your application layer rather than at the database are very uncommon. You should really use the capabilities that the database provides.

Answer 2

Suppose you have two customer ids that differ by 100, and they happen to both make an order that is 100 time units apart. Your uniqueness just went out the window.

You say that you're going to check the database for uniqueness; you don't say what you're going to do if there's a collision. You also don't say what you're going to do about race conditions; suppose two colliding order ids are created at the same time, neither is in the database. You ask the database on two different threads whether the item is unique; it is. You then enter both, and uniqueness has been violated even though the check has been done.

This is a really, really bad way to get uniqueness. What would be better is to move this into the database layer. You can maintain a global, threadsafe counter of orders and assign each new order the next highest order number.

Incidentally, for many years I have asked a variation on this question as a technical interview question. I've noticed a strong correlation between the set of people who attempt to use time as a source of uniqueness and the set of people who don't get hired. Time is a terrible source of uniqueness; lots of different things can happen at the same time.

What is even worse is using random numbers. Random numbers are an even worse source of uniqueness than timestamps. Suppose you have a truly random number generator that generates random 32 bit integers for order IDs. How many orders do you need to have before the odds are better than fifty-fifty that you've generated two orders with the same ID? The answer surprises a lot of people: it's only about 77 thousand before there is a 50% chance that you've generated two orders with the same number (and only 9300 until there's a 1% chance.)

Remember: what you are after is a guarantee of uniqueness. Not a probable uniqueness, but an iron-clad guarantee that one order number refers to exactly one order. If that's what you need, then make sure you implement that.