Snowflake in Java

IdGenerator.java

package snowflake;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.concurrent.atomic.AtomicLong;

/**
 * Generates unique 64-bit IDs based on a host ID, timestamp, and
 * incrementing counter. When each instance is given a unique host ID,
 * this is guaranteed to produce globally unique IDs for 69 years
 * from the epoch.
 * 
 * This is based on the Snowflake project from Twitter
 * ({@link https://github.com/twitter/snowflake/}), and uses the same
 * ID structure: an unsigned 64-bit integer, comprised of three sections:
 * <ul>
 * <li>Time - 41 bits
 * <li>Host ID - 10 bits
 * <li>Sequence - 12 bits
 * </ul>
 * 
 * This supports 4,096 (2^12) IDs per time unit (which is typically
 * milliseconds) per host ID. If the sequence rolls over during a
 * time unit, ID generation blocks until the next time unit. If the
 * clock should move backwards, IDs will continue to be generated with
 * the last timestamp until the sequence rolls over or the clock
 * advances.
 * 
 * When using multiple instances, the IDs generated will be time
 * ordered (i.e., if ID1 < ID2, ID1 happened before ID2) to the precision
 * of the time unit in use (two events that occur in the same
 * millisecond will not have a deterministic order).
 * 
 * Unlike the Twitter implementation, this is non-blocking and can
 * be used from multiple threads concurrently.
 * 
 * @author Andrew Minerd
 */
public class IdGenerator {
	/**
	 * Default epoch -- 2009-01-01 00:00:00.00
	 */
	private static final Logger log = LoggerFactory.getLogger(IdGenerator.class);
	public static final long EPOCH = 1230796800L;
	public static final long TIME_MASK = Long.MAX_VALUE << 22;
	private static final long SEQ_MASK = 0x0fffL;
	
	private final long epoch;
	private final long hostId;
	private final AtomicLong last = new AtomicLong(0L);
	
	/**
	 * Constructs an IdGenerator with the given host ID and the default
	 * epoch (2009-01-01 00:00:00.00).
	 * @param hostId Host ID
	 */
	public IdGenerator(long hostId) {
		this(hostId, EPOCH);
	}
	
	/**
	 * Constructs an IdGenerator with the given host ID and epoch.
	 * @param hostId Host ID
	 * @param epoch Epoch is milliseconds
	 */
	public IdGenerator(long hostId, long epoch) {
		this.hostId = hostId;
		this.epoch = epoch;
	}
	
	public long nextId() {
		final long id;
		while (true) {
			final long time = System.currentTimeMillis(),
				t = (time - epoch) << 22,
				l = last.get();
			long next;
			if (t <= (l & TIME_MASK)) {
				final long seq = (l + 1) & SEQ_MASK;
				if (seq == 0) {
					// sequence rolled over; block until time advances
					while (System.currentTimeMillis() <= time);
					continue;
				}
				next = (l & ~SEQ_MASK) | seq;
			} else {
				next = t | (hostId << 12);
			}
			if (last.compareAndSet(l, next)) {
				id = next;
				break;
			}
		}
		log.debug("Generating id {}.", id);
		return id;
	}
}