How to implement Snowflake algorithm in Golang

Snowflake is a distributed ID generation algorithm open sourced by Twitter. It uses the following method to generate a globally unique ID:

1. 64-bit ID, of which 1 is the sign bit and 41 are the time. Stamp, 10 is the working machine ID, and 12 is the serial number.
2. For distributed systems, global uniqueness can generally be guaranteed by combining timestamps, worker machine IDs, and serial numbers.

In this article, we will introduce how to implement Snowflake in Golang.

1. Define structures and constants

First, we need to define a structure to save the data in the Snowflake algorithm, including machine ID, serial number and the last generated ID timestamp and other information.

const (
    workerIdBits     = 10  // 机器ID位数
    sequenceBits     = 12  // 序列号位数
    workerIdMax      = -1 ^ (-1 << workerIdBits) // 最大机器ID
    sequenceMask     = -1 ^ (-1 << sequenceBits) // 序列号掩码
    timeShiftBits    = workerIdBits + sequenceBits // 时间戳左移位数
    workerIdShift    = sequenceBits               // 机器ID左移位数
)

type Snowflake struct {
    lastTimestamp uint64
    workerId      uint16
    sequence      uint16
}

Among them, we use constants to represent the number of digits of each data, maximum value, mask and other information to facilitate subsequent calculations.

2. Implementing the ID generation method

Next, we need to implement a method to generate a globally unique ID. The specific process is as follows:

1. Get the current timestamp. If it is less than the timestamp of the last generated ID, wait until the timestamp is updated to be greater than the timestamp of the last generated ID.
2. If the current timestamp is equal to the timestamp of the last generated ID, increase the sequence number. If the sequence number reaches the maximum value, wait until the next timestamp.
3. If the current timestamp is greater than the timestamp of the last generated ID, reset the sequence number and record the current timestamp, and generate an ID.

The specific implementation is as follows:

func (s *Snowflake) NextId() uint64 {
    var currTimestamp = uint64(time.Now().UnixNano() / 1e6)

    if currTimestamp < s.lastTimestamp {
        panic("Invalid timestamp")
    }

    if currTimestamp == s.lastTimestamp {
        s.sequence = (s.sequence + 1) & sequenceMask
        if s.sequence == 0 {
            currTimestamp = s.waitNextMillis(currTimestamp)
        }
    } else {
        s.sequence = 0
    }

    s.lastTimestamp = currTimestamp

    return ((currTimestamp - 1483228800000) << timeShiftBits) |
            (uint64(s.workerId) << workerIdShift) |
            uint64(s.sequence)
}

func (s *Snowflake) waitNextMillis(currTimestamp uint64) uint64 {
    for currTimestamp <= s.lastTimestamp {
        currTimestamp = uint64(time.Now().UnixNano() / 1e6)
    }
    return currTimestamp
}

In the implementation, we use UNIX timestamp to represent time, but since the time when the Snowflake algorithm generates IDs starts in 2017, we need Subtract the fixed offset value (1483228800000) from the timestamp.

3. Initialize the Snowflake object

Finally, we need to initialize a Snowflake object and specify the machine ID. The machine ID should be an integer between 0 and 1023, and the IDs of different machines are guaranteed to be different.

func New(workerId int) *Snowflake {
    if workerId < 0 || workerId > workerIdMax {
        panic(fmt.Sprintf("Invalid worker ID, must be in [%d, %d]", 0, workerIdMax))
    }

    return &Snowflake{
        lastTimestamp: 0,
        workerId:      uint16(workerId),
        sequence:      0,
    }
}

In the above implementation, we used the timestamp function and binary operator in Golang to ensure the uniqueness and continuity of the ID, and the low-order sequence number ensures the trend of the ID increasing. Since timestamps are accurate to the millisecond level, the Snowflake algorithm can generate enough IDs to avoid ID conflicts in high-concurrency scenarios.

The above is the detailed content of How to implement Snowflake algorithm in Golang. For more information, please follow other related articles on the PHP Chinese website!