64 bits Sufficiently Unique Id Generator

SUID.java

/****************************************************************************
 * Copyright 2009-2015 Jean-Philippe Gravel, P. Eng. CSDP
 * 
 * Modified 4/7/16 - Jean-Philippe Gravel (@formix) - Moved random number
 * generator into the method "if" statement.
 * 
 * Modified 6/8/15 - Osric Wilkinson (@Moosemorals) - No point messing with
 * random seeds. Just use SecureRandom.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ***************************************************************************/
package org.formix.utils;

import java.util.Random;
import java.util.SecureRandom;

/**
 * Sufficiently Unique Identifier
 * 
 * @author formix
 *
 */
final class SUID {

	private static final int SHORT_MAX = 65536;
	private static int counter = -1;

	private SUID() {
	}

	/**
	 * Creates a unique 64 bits ID by aggregating the current time in
	 * milliseconds since epoch (Jan. 1, 1970) and using a 16 bits counter. The
	 * counter is initialized at a random number. This generator can create up
	 * to 65536 different id per millisecond, which translate to 1 id every
	 * 16 microseconds.
	 * 
	 * @return a new id.
	 */
	public static synchronized long nextId() {
		if (counter == -1) {
			Random rnd = new SecureRandom();
			counter = rnd.nextInt(SHORT_MAX);
		}
		long now = System.currentTimeMillis();
		long id = (now << 16) | counter;
		counter = (counter + 1) % SHORT_MAX;
		return id;
	}
}

This generator never returned a colliding ID in production context of any of my projects. Before using it, you may do some statistical analysis based of your worst case scenario. I'm pretty confident that it should be okay for 99.9% of use cases.

woot, good luck with that

fix needed , as Random rnd = new Random(seed);

A.K.A. The Russian Roulette ID Generator

Thanks @asraful, I'll look into that.

System.currentTimeMillis() can go backwards as it synced to the system clock. You should be looking for the current time being less than the previous time to avoid repeats.

@bondolo that's right, especially during daylight saving time transitions maybe. I'll think about that and see how System.currentTimeMillis() behave in these transition periods. On another hand, the goal of the library is not to do something "crypographically" correct (if I can use the term here). I guess that the rolling counter would help avoid having the same ID twice given a user changes its time in the computer settings.

Updated from @Moosemorals fork since his implementation with SecureRandom is a good improvement.

It is worth noting that this algorithm is used to create private ids. Knowing an id in the sequence could allow an attacker to guess another id after some significant number of retries. Attacks for system with a lot of ids generated in a short period of time (burst) are especially vulnerable generated ids will be pretty close to one another. This is still better than incremental id generation though. Keep that in mind when using this implementation.