Distributed ID Generator – LLD / Machine Coding Walkthrough

Functional Scope (In-Scope)

Resilient Generation Strategies (Strategy Pattern): Support switching algorithms (Snowflake vs UUID) based on storage and sortability needs.
64-Bit k-Sortable Snowflake Layouts: Bitwise layout structuring timestamp (41 bits), machineId (10 bits), and millisecond sequences (12 bits).
Clock Skew Safety (Clock Providers): Decouple system clocks behind mockable providers, implementing active backoff sleeps.
Zero Inter-Node Coordination: Generate unique, collision-free numbers without database sequences.

Explicit Boundaries (Out-of-Scope)

No Automatic NTP Server Sync Sync: Out-of-scope to sync local server clocks using active NTP daemons.
No Human-Friendly String Obfuscation: Generates strict binary BigInt numbers; does not compile readable short hashes.

Clean reference designs demonstrating Snowflake generators in Java and Python:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

interface ClockProvider {
    long currentTimeMillis();
}

class SystemClockProvider implements ClockProvider {
    @Override
    public long currentTimeMillis() {
        return System.currentTimeMillis();
    }
}

// ─── STRATEGY PATTERN (GENERATOR STRATEGIES) ──────────────────────────────────
interface IdGenerationStrategy {
    String nextId();
}

class UUIDGenerationStrategy implements IdGenerationStrategy {
    @Override
    public String nextId() {
        return UUID.randomUUID().toString();
    }
}

class SnowflakeIdStrategy implements IdGenerationStrategy {
    private final long machineId;
    private final ClockProvider clockProvider;
    private final long epoch = 1609459200000L; // Custom Epoch: Jan 1, 2021

    private final long machineIdBits = 10L;
    private final long maxMachineId = -1L ^ (-1L << machineIdBits);
    private final long sequenceBits = 12L;

    private final long machineIdShift = sequenceBits;
    private final long timestampLeftShift = sequenceBits + machineIdBits;
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;
    private long sequence = 0L;
    private final ReentrantLock lock = new ReentrantLock();

    public SnowflakeIdStrategy(long machineId, ClockProvider clockProvider) {
        if (machineId < 0 || machineId > maxMachineId) {
            throw new IllegalArgumentException("Machine ID out of range");
        }
        this.machineId = machineId;
        this.clockProvider = clockProvider;
    }

    @Override
    public String nextId() {
        lock.lock();
        try {
            long timestamp = clockProvider.currentTimeMillis();

            if (timestamp < lastTimestamp) {
                // Clock-skew backoff handling
                long drift = lastTimestamp - timestamp;
                if (drift < 10) { // Graceful drift: wait a brief moment
                    try {
                        Thread.sleep(drift);
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                    timestamp = clockProvider.currentTimeMillis();
                }
                
                if (timestamp < lastTimestamp) {
                    throw new IllegalStateException("Clock moved backwards! Drift exceeds recovery threshold.");
                }
            }

            if (timestamp == lastTimestamp) {
                sequence = (sequence + 1) & sequenceMask;
                if (sequence == 0) {
                    timestamp = waitNextMillis(lastTimestamp);
                }
            } else {
                sequence = 0L;
            }

            lastTimestamp = timestamp;

            long id = ((timestamp - epoch) << timestampLeftShift)
                    | (machineId << machineIdShift)
                    | sequence;
            return String.valueOf(id);
        } finally {
            lock.unlock();
        }
    }

    private long waitNextMillis(long lastTimestamp) {
        long timestamp = clockProvider.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = clockProvider.currentTimeMillis();
        }
        return timestamp;
    }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        System.out.println("=== Distributed ID Generator ===");
        ClockProvider clock = new SystemClockProvider();
        IdGenerationStrategy snowflake = new SnowflakeIdStrategy(1, clock);

        // Thread Pool simulation
        ExecutorService executor = Executors.newFixedThreadPool(4);
        Set<String> generatedIds = ConcurrentHashMap.newKeySet();
        CountDownLatch latch = new CountDownLatch(100);

        for (int i = 0; i < 100; i++) {
            executor.submit(() -> {
                try {
                    String id = snowflake.nextId();
                    generatedIds.add(id);
                } finally {
                    latch.countDown();
                }
            });
        }

        latch.await();
        executor.shutdown();
        System.out.println("Generated unique IDs: " + generatedIds.size() + " / 100");
    }
}