分布式ID生成解决方案——雪花生成算法Golang实现

一、前言

在分布式系统中生成唯一ID的方案有很多，常见的方式有以下几种。

二、雪花算法

2.1、雪花算法概述

雪花算法生成的ID是纯数字且有序的，最早是 Twitter 公司在其内部用于分布式环境下生成唯一 ID，其原始版本是scala版。

2.2、ID组成

由首位无效符、时间戳差值，机器编码（由机器id和服务id组成），序号四部分组成。

• 首位无效位：第一个bit作为符号位，因为我们生成的都是正数，所以第一个bit统一都是0。
• 时间戳：占用41bit，精确到毫秒。41位最好可以表示2^41-1毫秒，转化成单位年为69年。
• 机器编码：占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，最多可以容纳1024个节点。
• 序列号：占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。

注意，默认的雪花算法是 64 bit，具体的长度可以自行配置。

如果希望运行更久，增加时间戳的位数；如果需要支持更多节点部署，增加标识位长度；如果并发很高，增加序列号位数。

雪花算法并非一成不变的，可以根据具体场景进行定制。

2.3、优缺点

优点：

• 高性能高可用：生成时不依赖数据库，完全在内存中生成。
• 容量大：每秒钟能生成数百万自增ID。
• ID自增：存入数据库中，索引效率高。

缺点：

• 雪花算法在单机系统上ID是递增的，但是在分布式系统多节点的情况下，所有节点的时钟并不能保证不完全同步，所以有可能会出现不是全局递增的情况。

三、代码实现

实现代码由golang编写

代码：

const (
	workerBits  uint8 = 10                      //机器码位数
	numberBits  uint8 = 12                      //序列号位数
	workerMax   int64 = -1 ^ (-1 << workerBits) //机器码最大值（即1023）
	numberMax   int64 = -1 ^ (-1 << numberBits) //序列号最大值（即4095）
	timeShift   uint8 = workerBits + numberBits //时间戳偏移量
	workerShift uint8 = numberBits              //机器码偏移量
	epoch       int64 = 1656856144640           //起始常量时间戳（毫秒）,此处选取的时间是2022-07-03 21:49:04
)

type Worker struct {
	mu        sync.Mutex
	timeStamp int64
	workerId  int64
	number    int64
}

func NewWorker(workerId int64) (*Worker, error) {
	if workerId < 0 || workerId > workerMax {
		return nil, errors.New("WorkerId超过了限制！")
	}
	return &Worker{
		timeStamp: 0,
		workerId:  workerId,
		number:    0,
	}, nil
}

func (w *Worker) NextId() int64 {
	w.mu.Lock()
	defer w.mu.Unlock()
	//当前时间的毫秒时间戳
	now := time.Now().UnixNano() / 1e6
	//如果时间戳与当前时间相同，则增加序列号
	if w.timeStamp == now {
		w.number++
		//如果序列号超过了最大值，则更新时间戳
		if w.number > numberMax {
			for now <= w.timeStamp {
				now = time.Now().UnixNano() / 1e6
			}
		}
	} else { //如果时间戳与当前时间不同，则直接更新时间戳
		w.number = 0
		w.timeStamp = now
	}
	//ID由时间戳、机器编码、序列号组成
	ID := (now-epoch)<<timeShift | (w.workerId << workerShift) | (w.number)
	return ID
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

测试：

func main() {
   worker, err := snow.NewWorker(0)
   if err != nil {
      fmt.Println(err)
   }
   for i := 0; i < 5; i++ {
      id := worker.NextId()
      fmt.Println(id)
   }
}

// 结果：
// 7783621591040
// 7783621591041
// 7783621591042
// 7783621591043
// 7783621591044

func BenchmarkID(b *testing.B) {
	worker, _ := NewWorker(0)
	for i := 0; i < b.N; i++ {
		worker.NextId()
	}
}
//BenchmarkID-16           4902658（执行次数）              244.5 ns/op（平均每次执行所需时间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

四、参考

https://developer.aliyun.com/article/862409

https://juejin.cn/post/7082669476658806792