> Follow WeChat Official Account 【爱发白日梦的后端 (Daydreaming Backend Developer)】, which shares technical insights, reading notes, open source projects, practical experience, efficient development tools and more. Your follow is my motivation to keep updating!
Principle of the Snowflake Algorithm for Generating Globally Unique IDs
The Snowflake algorithm is an algorithm for generating globally unique IDs, originally developed by Twitter to solve the problem of ID generation in distributed systems. Its core idea is to divide a 64-bit long integer ID into multiple parts, each used to store different information, ensuring the uniqueness of generated IDs in distributed environments.
ID Structure
- Sign bit (1 bit): Always 0, used to ensure the ID is a positive number.
- Timestamp (41 bits): Represents the timestamp when the ID was generated, with millisecond precision.
- Worker node ID (10 bits): Represents the unique identifier of the machine generating the ID.
- Sequence number (12 bits): Represents the sequence number for multiple IDs generated within the same millisecond.
Generation Steps
- Get the current timestamp with millisecond precision.
- If the current time is earlier than the time when the last ID was generated, or the number of IDs generated within the same millisecond exceeds the maximum value, wait until the next millisecond to continue generation.
- If the current time is equal to the time when the last ID was generated, increment the sequence number by 1.
- If the current time is later than the time when the last ID was generated, reset the sequence number to 0.
- Combine the values of each part to get the final 64-bit ID.
Implementing a High-Concurrency ID Generator with the Snowflake Algorithm in Go
package mainimport (
“fmt”
“sync”
“time”
)const (
workerBits = 10
sequenceBits = 12
workerMax = -1 ^ (-1 << workerBits)
sequenceMask = -1 ^ (-1 << sequenceBits)
timeShift = workerBits + sequenceBits
workerShift = sequenceBits
epoch = 1609459200000
)type Snowflake struct {
mu sync.Mutex
lastTime int64
workerID int64
sequence int64
}func NewSnowflake(workerID int64) *Snowflake {
if workerID < 0 || workerID > workerMax {
panic(fmt.Sprintf(“worker ID must be between 0 and %d”, workerMax))
}
return &Snowflake{
lastTime: time.Now().UnixNano() / 1e6,
workerID: workerID,
sequence: 0,
}
}func (sf *Snowflake) NextID() int64 {
sf.mu.Lock()
defer sf.mu.Unlock()currentTime := time.Now().UnixNano() / 1e6
if currentTime < sf.lastTime {
panic(fmt.Sprintf(“clock moved backwards, refusing to generate ID for %d milliseconds”, sf.lastTime-currentTime))
}if currentTime == sf.lastTime {
sf.sequence = (sf.sequence + 1) & sequenceMask
if sf.sequence == 0 {
for currentTime <= sf.lastTime {
currentTime = time.Now().UnixNano() / 1e6
}
}
} else {
sf.sequence = 0
}sf.lastTime = currentTime
id := (currentTime-epoch)<<timeShift | (sf.workerID << workerShift) | sf.sequence
return id
}func main() {
sf := NewSnowflake(1) // Assume the worker node ID is 1for i := 0; i < 10; i++ {
id := sf.NextID()
fmt.Println(id)
time.Sleep(time.Millisecond)
}
}
Guaranteeing Uniqueness and Incrementality Under High Concurrency
In high-concurrency scenarios, the key to guaranteeing the uniqueness and incrementality of IDs generated by the Snowflake algorithm is as follows:
- Uniqueness: The worker node ID configuration ensures that IDs generated by different nodes do not conflict. Sequence number increment and bitwise operations guarantee that all IDs generated within the same millisecond are unique.
- Incrementality: Multiple IDs generated within the same millisecond are ordered by increasing sequence number. Even in the extreme case where the number of IDs generated in a single millisecond exceeds the maximum value, the algorithm waits for the next millisecond to restart generation, which still preserves incrementality.
Overall, the Snowflake algorithm is a reliable ID generation solution for high-concurrency environments. Its high performance and low collision probability have made it widely used in distributed systems.
This is a discussion topic separated from the original thread at https://studygolang.com/topics/17034