UniqueID Generator in distributed systems | Implementation in Java ( Thread-Safe )

Understanding Unique IDs:

At its core, a unique ID (identifier) is a string of characters or binary data that distinguishes one entity from another within a given context. Unique IDs are essential for maintaining data integrity, enabling efficient retrieval, and facilitating system operations. They serve as primary keys in databases, session tokens in web applications, and transaction IDs in distributed systems.

How do we design a uniqueID Generator for distributed systems ??

It’s not as complex as it looks like. First, we will need a few assumptions/considerations:

1. Searching the ID in the persistent database should be fast. ( Number Search is faster than String search in RDBMS, hence we will stick to numbers ).
2. Let’s say we will be churning out 1000 uniqueIDs / milliSeconds, which means 1 million uniqueIDs / Seconds. That’s a lot…
3. Let’s assume we will have a maximum of 31 data centers and 31 nodes/servers per data center. [ Why 31 specifically ?? For easier calculation ]

High-Level Design of each uniqueID :

1. We will use 64-bit size to generate the uniqueIDs.
2. The first bit is reserved as 0 for now, as the timestamp we will be using will repeat after 68–69 years, we can then use 1 in that place to extend another 68 years.
3. We will use the timestamp of every millisecond. to store the timestamp we will need 41 bits. ( timestamp max size = 2⁴¹ — 1).
4. 5 bits are used for the datacenter, so ( 2⁵-1 = 31 datacenter at max can use it).
5. 5 bits are used for the machineID, so ( ²⁵-1 = 31 server/nodes at max can use it).
6. The last 12 bits are used for the sequence number, you can think of it as a counter for the next id for a unique millisecond. ( Max sequence number = 2¹²-1 = 4095 sequence/millisecond, i.e approx 4 times our requirement, 1000 / millisecond )

Example of ID generated by our algorithm :

1. We will need a reference EPOCH_OFFSET to subtract it from timeStamp in milliSeconds so that the resultant timestamp can be unique till 68 years at least w.r.t the EPOCH_OFFSET.
2. In Java we will use the below code for reference offset :

private static final long EPOCH_OFFSET = Instant.parse("2024-01-01T00:00:00Z").toEpochMilli();

3. Get the current timestamp in milliseconds and subtract it by reference EPOCH_OFFSET [ 1713539370599–1704067200000 == 9472170599 ].

4. left shift 9472170599 by 5+5+12 = 22 bits, so that the data center, server/nodes, and sequence number can use the remaining space.

5. Add datacentre ID after shifting left by 5+12 bits making space for nodes and sequence IDs. [ Say datacenter id = 27 ].

6. Add server/node id after shifting left by 12 bits making space for sequence ids. [ Say datacenter id = 21 ].

7. Finally add the sequence number. let’s say the sequence id is 972.

8. Final output will be the required unique ID, in this case : 39729163035694028

   String s = "9472170599";
   long ts = (Long.parseLong(s) << 22) | (27 << 17) | (21 << 12) | (972);
   System.out.println(ts);


Output :
39729163035694028

Complete program to generate the uniqueIDs :

import java.time.Instant;

public class UniqueIdGenertorBitManipulation {

    private static final long EPOCH_OFFSET = Instant.parse("2024-01-01T00:00:00Z").toEpochMilli();
    private static final int DATACENTER_ID_BITS = 5;
    private static final int NODE_ID_BITS = 5;
    private static final int SEQUENCE_BITS = 12;

    private static final long MAX_DATACENTER_ID = (1L << DATACENTER_ID_BITS) - 1;
    private static final long MAX_NODE_ID = (1L << NODE_ID_BITS) - 1;
    private static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;

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

    private final long datacenterId;
    private final long nodeId;

    public UniqueIdGenertorBitManipulation(long datacenterId, long nodeId) {
        if (datacenterId < 0 || datacenterId > MAX_DATACENTER_ID) {
            throw new IllegalArgumentException("Datacenter ID must be between 0 and " + MAX_DATACENTER_ID);
        }
        if (nodeId < 0 || nodeId > MAX_NODE_ID) {
            throw new IllegalArgumentException("Node ID must be between 0 and " + MAX_NODE_ID);
        }
        this.datacenterId = datacenterId;
        this.nodeId = nodeId;
    }

    public synchronized long generateUniqueId() {
        long currentTimestamp = System.currentTimeMillis();

        if (currentTimestamp < lastTimestamp) {
            throw new IllegalStateException("Clock moved backwards, refusing to generate ID for " + (lastTimestamp - currentTimestamp) + " milliseconds");
        }

        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) % (MAX_SEQUENCE + 1);
            if (sequence == 0) {
                // Sequence overflow, wait until next millisecond
                currentTimestamp = getNextTimestamp();
            }
        } else {
            sequence = 0L; // Reset sequence
        }

        lastTimestamp = currentTimestamp;

        long timestamp = currentTimestamp - EPOCH_OFFSET;

        return (timestamp << (DATACENTER_ID_BITS + NODE_ID_BITS + SEQUENCE_BITS)) |
                (datacenterId << (NODE_ID_BITS + SEQUENCE_BITS)) |
                (nodeId << SEQUENCE_BITS) |
                sequence;
    }

    private long getNextTimestamp() {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }

    public static void main(String[] args) throws InterruptedException {


        Thread server1 = new Thread(()->{
            UniqueIdGenertorBitManipulation idGenerator = new UniqueIdGenertorBitManipulation(1, 21); // Example datacenter ID and node ID

            for(int i=0 ; i<10; i++){
                System.out.println("Generated ID: " + idGenerator.generateUniqueId() + " by server : " + Thread.currentThread().getName() );
            }
        }, "1");

        Thread server2 = new Thread(()->{
            UniqueIdGenertorBitManipulation idGenerator = new UniqueIdGenertorBitManipulation(2, 1); // Example datacenter ID and node ID

            for(int i=0 ; i<10; i++){
                System.out.println("Generated ID: " + idGenerator.generateUniqueId() + " by server : " + Thread.currentThread().getName() );
            }
        },"2");

        Thread server3 = new Thread(()->{
            UniqueIdGenertorBitManipulation idGenerator = new UniqueIdGenertorBitManipulation(1, 27); // Example datacenter ID and node ID

            for(int i=0 ; i<10; i++){
                System.out.println("Generated ID: " + idGenerator.generateUniqueId() + " by server : " + Thread.currentThread().getName() );
            }
        },"3");

        server1.start();
        server2.start();
        server3.start();

        server1.join();
        server2.join();
        server3.join();

    }
}

Program Output :