16

I need to generate a unique 10 digit ID in Java. These are the restrictions for this ID:

  • Only Numeric
  • Maximum 10 digits
  • Possible to create up to 10 different IDs per second
  • Has to be unique (even if the application re-starts)
  • Not possible to save a number in the Database
  • As fast as possible NOT to add much lattency to the system

The best solution I found so far is the following:

private static int inc = 0;

private static long getId(){

    long id = Long.parseLong(String.valueOf(System.currentTimeMillis())
            .substring(1,10)
            .concat(String.valueOf(inc)));
    inc = (inc+1)%10;
    return id;
}

This solution has the following problems:

  • If for any reason there is a need to create more than 10 IDs per seccond, this solution won't work.
  • In about 32 years this ID could be repeated (This is probably acceptable)

Any other solution to create this ID?

Any other problem I haven't thought of with mine?

Thanks for your help,

magodiez
  • 741
  • 2
  • 10
  • 23
  • 2
    Can several instances of the application run at the same time? – assylias Aug 14 '13 at 09:32
  • Only one instance is running right now, but may be possible in the future. We also have a seccondary instance in case the primary goes down, but only one of them (primary or seccondary) would be running at the same time. – magodiez Aug 14 '13 at 09:37
  • As pointed in some of the answers below, my implementation will fail in multi instance or multi threading environment, so lets assume that a single instance with a single thread will be running. – magodiez Aug 14 '13 at 10:04
  • It is not possible to guarantee unicity across instances without introducing some form of communication (such as a database, file or web service). – assylias Aug 14 '13 at 10:53

4 Answers4

10

This is a small enhancement to yours but should be resilient.

Essentially, we use the current time in milliseconds unless it hasn't ticked since the last id, in which case we just return last + 1.

private static final long LIMIT = 10000000000L;
private static long last = 0;

public static long getID() {
  // 10 digits.
  long id = System.currentTimeMillis() % LIMIT;
  if ( id <= last ) {
    id = (last + 1) % LIMIT;
  }
  return last = id;
}

As it is it should manage up to 1000 per second with a comparatively short cycle rate. To extend the cycle rate (but shorten the resolution) you could use (System.currentTimeMillis() / 10) % 10000000000L or (System.currentTimeMillis() / 100) % 10000000000L.

OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • Using the (System.currentTimeMillis() / 100) will actually solve the problem if more tha 10 ID have to be created in the same seccond, since this will never be something continuous. Thanks, ;) – magodiez Aug 14 '13 at 10:17
  • 1
    Do remember that `System.currentTimeMillis()` has a minimum resolution. I have found it stepping by around 15ms on MS systems so `/100` may not be as smooth as you think, although this algorithm will deal with that for you. – OldCurmudgeon Aug 14 '13 at 10:21
  • I was thinking about using /100, and I just saw a problem: Simple example when this would fail: time: 1376479263900 id: #3764792639 time: 1376479263950 id: #3764792640 time: 1376479264000 id: #3764792641 time: 1376479264050 id: #3764792640 (repeated) – magodiez Aug 14 '13 at 11:30
  • @magodiez - With `/100` you should get @t=1376479263900 id=13764792639, @t=1376479263950 id=3764792640, @t=1376479264000 id=3764792641, @t=1376479264050 id=3764792642 ... until you back off long enough for the time to catch up. It will NEVER return an id <= the last one unless you go around the 10-digit limit or restart. Note that I tweaked the algorithm a little after first post so get latest and you should see it is ok. – OldCurmudgeon Aug 14 '13 at 15:04
  • 1
    this could have problems if there are multiple ids created in the seccond 1999999999, but still no problem until 2033 (good enough) Thanks, :) – magodiez Aug 16 '13 at 07:27
2

This may be a crazy idea but its an idea :).

  • First generate UUID and get a string representation of it with java.util.UUID.randomUUID().toString()

  • Second convert generated string to byte array (byte[])

  • Then convert it to long buffer: java.nio.ByteBuffer.wrap( byte digest[] ).asLongBuffer().get()

  • Truncate to 10 digits

Not sure about uniqueness of that approach tho, I know that you can rely on uniqueness of UUIDs but haven't checked how unique are they converted and truncated to 10 digits long number.

Example was taken from JavaRanch, maybe there is more.

Edit: As you are limited to 10 digits maybe simple random generator would be enough for you, have a look into that quesion/answers on SO: Java: random long number in 0 <= x < n range

Community
  • 1
  • 1
Kris
  • 5,714
  • 2
  • 27
  • 47
  • [UUIDs are *not* guaranteed to be unique](http://stackoverflow.com/questions/5728205/is-unique-id-generation-using-uuid-really-unique). Although the probability of getting two identical UUID is very small. – assylias Aug 14 '13 at 09:33
  • 1
    Exactly, but as I wrote 'you can rely on their uniqueness', not that they are unique :) – Kris Aug 14 '13 at 09:35
1
private static AtomicReference<Long> currentTime = new AtomicReference<>(System.currentTimeMillis());

public static Long nextId() {
    return currentTime.accumulateAndGet(System.currentTimeMillis(), (prev, next) -> next > prev ? next : prev + 1) % 10000000000L;
}
Shafin Mahmud
  • 3,831
  • 1
  • 23
  • 35
abhineet
  • 195
  • 1
  • 1
  • 11
0

What means that it has to be unique? Even across more currently running instances? It break your implementation.

If it must be unique across universe, the best solution is to use UUID as it's mathematically proven identifier generator as it generates unique value per universe. Less accurate number brings you collisions.

When there is only one concurrent instance, you can take current time in millis and solve 10ms problem using incrementation. If you sacrifice proper number of last positions in the number you can get many number within one milliseconds. I would than define the precision - I mean how much unique numbers do you need per seconds. You will solve the issue without any persistence using this approach.

Martin Podval
  • 1,097
  • 1
  • 7
  • 16