Solve the problem of clock callback in Java

Snowflake is a distributed unique ID generation algorithm open source on Twitter, which is used to generate globally unique IDs in distributed systems. The ID generated by the snowflake algorithm is a 64-bit integer, usually represented as a long integer.

Structure of Snowflake Algorithm

The ID generated by the snowflake algorithm consists of the following parts:

• Symbol bit (1 bit): Always 0, ensuring that the generated ID is a positive number.
• Timestamp (41 bits): Record the timestamp of the generated ID, accurate to the millisecond level. Can be used for about 69 years.
• Machine ID (10 bits): Identify the machine that generates ID and can support 1024 machines.
• Serial number (12 digits): The serial number of multiple IDs generated within the same millisecond, which can support the generation of 4096 IDs per millisecond.

Clock callback problem

The clock callback problem refers to the fact that in a distributed system, the system time of some nodes may fall back to a past point in time for various reasons (such as NTP time synchronization). This will cause duplicate IDs generated by the snowflake algorithm to be generated because the timestamp parts will be repeated.

How to solve the clock callback problem

• Waiting mechanism：

  • When a clock callback is detected, the generator can wait for the time to catch up with the timestamp of the last generated ID and then generate a new ID. This approach is simple and straightforward, but may cause the generator to fail to generate a new ID while waiting.

• Extended bit：

  • Additional bits are added to the ID structure to handle clock callbacks. For example, additional bits can be used to record the number of clock callbacks, thereby avoiding ID duplication.

• Reserved timestamp：

  • When generating the ID, some timestamp range is reserved for processing clock callbacks. For example, some timestamp range can be reserved, and when a clock callback is detected, a new ID is generated using the reserved timestamp.

• Logical clock：

  • Use a logical clock, such as a Lamport clock or a Vector clock, instead of a physical clock. Logical clocks can ensure the order of events in distributed systems and avoid clock callback issues.

Sample code

Here is an example of the implementation of snowflake algorithm that uses the waiting mechanism to solve the clock callback problem:

public class SnowflakeIdGenerator {
    private final long twepoch = 1288834974657L; // Start timestamp, such as Twitter's Snowflake start time    private final long workerIdBits = 10L;
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private final long sequenceBits = 12L;
    private final long workerIdShift = sequenceBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits;
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

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

    public SnowflakeIdGenerator(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
         = workerId;
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            // The clock is called back, waiting for the time to catch up            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                    wait(offset << 1);
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                        throw new RuntimeException(("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
                    }
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                throw new RuntimeException(("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
            }
        }

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

        lastTimestamp = timestamp;

        return ((timestamp - twepoch) << timestampLeftShift) |
                (workerId << workerIdShift) |
                sequence;
    }

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

    protected long timeGen() {
        return ();
    }

    public static void main(String[] args) {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1);
        (());
    }
}

Code explanation

• Detect clock callback：

  • When generating the ID, the current timestamp is first obtained and compared with the timestamp of the last generated ID.
  • If the current timestamp is smaller than the timestamp of the last generated ID, it means that a clock callback has occurred.

• Waiting mechanism：

  • If the time difference of clock callback is less than or equal to 5 milliseconds, the generator will wait for the time to catch up with the timestamp of the last generated ID.
  • If the time difference of clock callback is greater than 5 milliseconds, an exception is thrown and the ID is refused to be generated.

• Generate a new ID：

  • If the clock does not call back, or waits for the time to catch up, generate a new ID.

Summarize

The clock callback problem is an important issue that needs to be solved when using the snowflake algorithm to generate unique IDs in distributed systems. By using wait mechanism, extended bits, reserved timestamps or logical clocks, the ID duplication problems caused by clock callback can be effectively avoided. In practical applications, the appropriate solution can be selected according to the specific needs.

This is the article about solving the problem of clock callback in Java. For more related Java Snowflake Algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!