SnowflakeID

什么是SnowFlakeID

• SnowFlakeID是twitter公司内部分布式项目采用的ID生成算法

• SnowFlakeID的最大的特性就是天然去中心化，通过时间戳、工作机器编号两个变量进行配置后，通过SnowFlake算法会生成唯一的递增ID。在任何机器上，只要保证工作机器编号不同，就可以确保生成的ID唯一，且整体趋势是递增的

• 分布式自增ID的广泛选择

结构

0 - 0000000000 0000000000 0000000000 0000000000 0 - 0000000000 - 000000000000

• 第一段1位未使用，永远固定为0，因为ID为正数
• 第二段41位，为毫秒级时间（41位的长度可以使用69年）
• 第三段10位，为workID（10位的长度最多能部署1024个节点）
• 第四段为12位，表示每毫秒内的计数（12位的计数顺序号支持每个节点每毫秒支持产生4096个ID序号）

按照 1024个节点计算：每毫秒可以生成的ID序列号有 1024*4096=4194304，足以满足绝大多数业务场景

算法

((当前时间 - 服务时间) << timestampLeftShift) 
        | (机器ID << workerIdShift) 
        | sequence;

SnowFlakeID的问题

SnowFlake强依赖 时间戳，所以时间的变动会造成SnowFlake的算法产生错误

使用时需要注意时钟回拨的现象

具体的实现

package main

import (
	"errors"
	"fmt"
	"sync"
	"time"
)

const (
	workerIDBits     = 10                      // 节点ID长度
	sequenceBits     = 12                      // 序列号长度
	workerIDShift    = sequenceBits            // 节点ID左移位数
	timestampShift   = sequenceBits + workerIDBits // 时间戳左移位数
	sequenceMask     = -1 ^ (-1 << sequenceBits)   // 序列号掩码
	epoch            = int64(1577836800000)    // 起始时间戳（2020-01-01）
	maxWorkerID      = -1 ^ (-1 << workerIDBits)   // 最大节点ID
)

type Snowflake struct {
	mu        sync.Mutex
	timestamp int64
	workerID  int64
	sequence  int64
}

func NewSnowflake(workerID int64) (*Snowflake, error) {
	if workerID < 0 || workerID > maxWorkerID {
		return nil, errors.New("worker ID out of range")
	}
	return &Snowflake{
		timestamp: 0,
		workerID:  workerID,
		sequence:  0,
	}, nil
}

func (s *Snowflake) tilNextMillis(lastTimestamp int64) int64 {
	timestamp := time.Now().UnixNano() / int64(time.Millisecond)
	for timestamp <= lastTimestamp {
		timestamp = time.Now().UnixNano() / int64(time.Millisecond)
	}
	return timestamp
}

func (s *Snowflake) NextID() (int64, error) {
	s.mu.Lock()
	defer s.mu.Unlock()

	timestamp := time.Now().UnixNano() / int64(time.Millisecond)
	if timestamp < s.timestamp {
		return 0, fmt.Errorf("clock moved backwards. Refusing to generate id for %d milliseconds", s.timestamp-timestamp)
	}

	if timestamp == s.timestamp {
		s.sequence = (s.sequence + 1) & sequenceMask
		if s.sequence == 0 {
			timestamp = s.tilNextMillis(s.timestamp)
		}
	} else {
		s.sequence = 0
	}

	s.timestamp = timestamp

	id := ((timestamp - epoch) << timestampShift) |
		(s.workerID << workerIDShift) |
		s.sequence

	return id, nil
}

func main() {
	sf, err := NewSnowflake(1)
	if err != nil {
		fmt.Printf("Error initializing Snowflake: %v\n", err)
		return
	}

	for i := 0; i < 10; i++ {
		id, err := sf.NextID()
		if err != nil {
			fmt.Printf("Error generating ID: %v\n", err)
			continue
		}
		fmt.Println(id)
	}
}