Distributed ID Generation Techniques Discussed in an Interview with Java Implementations

The interview begins with the interviewer recalling a previous session and asking the candidate about distributed ID generation methods. The candidate lists several common approaches:

Database auto‑increment ID

Database horizontal sharding with custom initial values and a common step

Batch allocation of auto‑increment IDs

UUID generation

Redis‑based ID generation

Snowflake algorithm

Baidi UidGenerator algorithm

Meituan Leaf algorithm

The interviewer asks for analysis of each method. The candidate explains that simple database auto‑increment IDs are easy but cause duplicate IDs in a distributed environment and generate high DB load because each ID requires a round‑trip to the database.

To solve these problems, the candidate describes two database‑centric schemes: horizontal sharding with different initial values and a common step, and batch allocation of ID ranges. For sharding, each database instance is given a distinct initial offset and a step equal to the number of shards, e.g., with three databases the offsets are 1, 2, 3 and the step is 3. The SQL to set these values is shown below:

set @@auto_increment_offset = 1;      // set initial offset
set @@auto_increment_increment = 2;  // set step

When the system needs to scale, the step can be increased in advance to reserve space for future shards.

Next, the candidate discusses Redis‑based ID generation. Redis provides atomic INCR and INCRBY commands, which generate ordered IDs in memory with high performance. However, this approach adds a middleware layer, requires custom implementation, and introduces persistence concerns (RDB snapshots vs. AOF logs). The Java implementation using RedisAtomicLong is presented:

@Service
public class RedisSequenceFactory {
    @Autowired
    RedisTemplate<String, String> redisTemplate;

    public void setSeq(String key, int value, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.set(value);
        counter.expireAt(expireTime);
    }

    public void setSeq(String key, int value, long timeout, TimeUnit unit) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.set(value);
        counter.expire(timeout, unit);
    }

    public long generate(String key) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        return counter.incrementAndGet();
    }

    public long incr(String key, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.expireAt(expireTime);
        return counter.incrementAndGet();
    }

    public long incr(String key, int increment) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        return counter.addAndGet(increment);
    }

    public long incr(String key, int increment, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.expireAt(expireTime);
        return counter.addAndGet(increment);
    }
}

If Redis is unavailable, the fallback method increments a hash and, on exception, generates an ID using a random UUID hash:

public Long getSeq(String key, String hashKey, Long delta) throws BusinessException {
    try {
        if (null == delta) {
            delta = 1L;
        }
        return redisTemplate.opsForHash().increment(key, hashKey, delta);
    } catch (Exception e) {
        int first = new Random(10).nextInt(8) + 1;
        int randNo = UUID.randomUUID().toString().hashCode();
        if (randNo < 0) {
            randNo = -randNo;
        }
        return Long.valueOf(first + String.format("%16d", randNo));
    }
}

The candidate then covers UUID generation, noting that it combines MAC address, timestamp, and a random number, but suffers from large size (128‑bit) and lack of ordering, making it unsuitable for most distributed ID scenarios.

Finally, the Snowflake algorithm is introduced. It uses a 64‑bit ID composed of a sign bit, 41‑bit timestamp (relative to a custom epoch), 5‑bit datacenter ID, 5‑bit worker ID, and 12‑bit sequence number, allowing up to 4096 IDs per millisecond per node. The candidate explains handling of clock rollback by throwing an exception or waiting for the clock to catch up. The full Java implementation is shown:

/**
 * Snowflake algorithm
 * @author：黎杜
 */
public class SnowflakeIdWorker {

    /** start timestamp */
    private final long twepoch = 1530051700000L;

    /** worker id bits */
    private final long workerIdBits = 5L;

    /** datacenter id bits */
    private final long datacenterIdBits = 5L;

    /** max worker id */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** max datacenter id */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** sequence bits */
    private final long sequenceBits = 12L;

    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long workerId;
    private long datacenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    public synchronized long nextId() {
        long timestamp = getCurrentTime();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds");
        }
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        return ((timestamp - twepoch) << timestampLeftShift) |
               (datacenterId << datacenterIdShift) |
               (workerId << workerIdShift) |
               sequence;
    }

    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = getCurrentTime();
        while (timestamp <= lastTimestamp) {
            timestamp = getCurrentTime();
        }
        return timestamp;
    }

    protected long getCurrentTime() {
        return System.currentTimeMillis();
    }
}

The interview wraps up with brief mentions of Meituan Leaf (which relies on a database and ZooKeeper) and Baidu UidGenerator (a Snowflake‑based solution with customizable bit allocations). The candidate acknowledges limited deep knowledge of these two algorithms.