Unique Number Server
by Roedy Green ©1996-2008 Canadian Mind Products
This essay is about a suggested
student project in
Java programming. This essay gives a rough overview of how it might work. It
does not describe an actual complete program. I have
no source, object,
specifications, file layouts or anything else useful to implementing this
project. Everything I have to say to help you with this project is written below.
I am
not prepared to help you implement it; I have too many other
projects of my own.
I do contract work for a living, which could include writing a program such as
this. However, I don’t do people’s homework
for them. That just robs them of an education.
You have my full permission to implement this project any way you please.
- Sample the system clock to the millisecond and use that as your identifier.
- Take a digest of the data such as MD-5
or SHA-1. The digest can
further be condensed by taking the modulus relative to some number, often a
prime.
You could use one of the above two techniques, then have a central registry that
detects the rare collisions and cleans up after the fact.
The obvious answer is to have a centralised RAM-resident counter that you
increment every time somebody needs a new unique number. There are three
problems with that simplistic approach.
- The centralised counter becomes a bottleneck. Everyone must line up behind it to
get a number.
- If the central counter goes down, the entire network is paralysed.
- If the counter computer crashes, when it wakes up, it does not remember
precisely which numbers it has already served. If it is not careful, it may
serve duplicates.
You might try to solve that with a redundant computer system, storing the
counter in a database record, with transaction processing. This adds huge
amounts of I/O overhead, slowing things to a crawl, and still does not let you
precisely determine which numbers have already been served.
Ok then, how do you handle it? A number server consists of three threads.
- The foreground thread just increments the counter and dispenses unique numbers (or
ranges of them).
- The second thread works in the background. It marks ranges of numbers on disk as
having been dispensed, before it releases them to the foreground thread.
- The third background thread, notices when the server is getting low on numbers
to serve and asks the mother server for a new large range of numbers to
replenish its supply. It uses the same protocol that clients of the satellite
number server do.
You need only concern yourself with dispensing unique longs. It is trivially
easy to turn these into account numbers with check digits or alphanumeric ids.
Another approach is to use the system clock as your basic unique number
generator. You must be very sure it is accurate. If you crash and pick up where
you left off, there is no danger of reissuing old numbers.
Most computers now have one or more Ethernet cards. Every ethernet card on the
planet is manufactured with a unique 48-bit MAC address. Unfortunately you need
JNI to get at it from Java. This gives you a way of stamping generated serial
numbers with the source that generated them.
There is now a IETF
UUID Universally Unique IDentifier specification. Safehaus
has implemented it. UUIDs are 128 bit integers.
Please email your feedback for publication, errors, omissions, broken/redirected link reports
