Go实现分布式唯一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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//实现方法：
package main


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

/*
	雪花算法(snowFlake)的具体实现方案:
 */

type SnowFlake struct{
	mu sync.Mutex
	//雪花算法开启时的起始时间戳
	twepoch int64

	//每一部分占用的位数
	workerIdBits     int64 //每个数据中心的工作机器的编号位数
	datacenterIdBits int64 //数据中心的编号位数
	sequenceBits     int64 //每个工作机器每毫秒递增的位数

	//每一部分最大的数值
	maxWorkerId int64
	maxDatacenterId int64
	maxSequence int64

	//每一部分向左移动的位数
	workerIdShift int64
	datacenterIdShift int64
	timestampShift int64

	//当前数据中心ID号
	datacenterId int64
	//当前机器的ID号
	workerId int64
	//序列号
	sequence int64
	//上一次生成ID号前41位的毫秒时间戳
	lastTimestamp int64
}

/*
	获取毫秒的时间戳
 */
func (s *SnowFlake)timeGen()int64{
	return time.Now().UnixMilli()
}
/*
	获取比lastTimestamp大的当前毫秒时间戳
 */
func (s *SnowFlake)tilNextMills()int64{
	timeStampMill:=s.timeGen()
	for timeStampMill<=s.lastTimestamp{
		timeStampMill=s.timeGen()
	}
	return timeStampMill
}
func (s *SnowFlake)NextId()(int64,error){
	s.mu.Lock()
	defer s.mu.Unlock()
	nowTimestamp:=s.timeGen()//获取当前的毫秒级别的时间戳
	if nowTimestamp<s.lastTimestamp{
		//系统时钟倒退,倒退了s.lastTimestamp-nowTimestamp
		return -1,errors.New(fmt.Sprintf("clock moved backwards, Refusing to generate id for %d milliseconds",s.lastTimestamp-nowTimestamp))
	}
	if nowTimestamp==s.lastTimestamp{
		s.sequence=(s.sequence+1)&s.maxSequence
		if s.sequence==0{
			 //tilNextMills中有一个循环等候当前毫秒时间戳到达lastTimestamp的下一个毫秒时间戳
			nowTimestamp=s.tilNextMills()
		}
	}else{
		s.sequence=0
	}
	s.lastTimestamp=nowTimestamp
	return (nowTimestamp-s.twepoch)<<s.timestampShift| //时间戳差值部分
		s.datacenterId<<s.datacenterIdShift| //数据中心部分
		s.workerId<<s.workerIdShift| //工作机器编号部分
		s.sequence, //序列号部分
		nil
}

func NewSnowFlake(workerId int64,datacenterId int64)(*SnowFlake,error){
	mySnow:=new(SnowFlake)
	mySnow.twepoch=time.Now().Unix() //返回当前时间的时间戳(时间戳是指北京时间1970年01月01日8时0分0秒到此时时刻的总秒数)
	if workerId<0||datacenterId<0{
		return nil,errors.New("workerId or datacenterId must not lower than 0 ")
	}
	/*
		标准的雪花算法
	 */
	mySnow.workerIdBits =5
	mySnow.datacenterIdBits=5
	mySnow.sequenceBits=12

	mySnow.maxWorkerId=-1^(-1<<mySnow.workerIdBits)         //64位末尾workerIdBits位均设为1,其余设为0
	mySnow.maxDatacenterId=-1^(-1<<mySnow.datacenterIdBits) //64位末尾datacenterIdBits位均设为1,其余设为0
	mySnow.maxSequence=-1^(-1<<mySnow.sequenceBits)  //64位末尾sequenceBits位均设为1,其余设为0

	if workerId>=mySnow.maxWorkerId||datacenterId>=mySnow.maxDatacenterId{
		return nil,errors.New("workerId or datacenterId must not higher than max value ")
	}
	mySnow.workerIdShift=mySnow.sequenceBits
	mySnow.datacenterIdShift=mySnow.sequenceBits+mySnow.workerIdBits
	mySnow.timestampShift=mySnow.sequenceBits+mySnow.workerIdBits+mySnow.datacenterIdBits

	mySnow.lastTimestamp=-1
	mySnow.workerId=workerId
	mySnow.datacenterId=datacenterId

	return mySnow,nil
}



func main(){
	//模拟实验是生成并发400W个ID,所需要的时间
	mySnow,_:=NewSnowFlake(0,0)//生成雪花算法
	group:=sync.WaitGroup{}
	startTime:=time.Now()
	generateId:=func (s SnowFlake,requestNumber int){
		for i:=0;i<requestNumber;i++{
			s.NextId()
			group.Done()
		}
	}
	group.Add(4000000)
	//生成并发的数为4000000
	currentThreadNum:=400
	for i:=0;i<currentThreadNum;i++{
		generateId(*mySnow,10000)
	}
	group.Wait()
	fmt.Printf("time: %vn",time.Now().Sub(startTime))
}