avatar

GO版snowflake(雪花算法)

Snowflakes是Twitter开源的分布式唯一ID生成算法,其结果为64bit的长整形数值。

  • 优点:高性能、不依赖第三方组件、总体有序递增
  • 缺点:依赖机器时间,如果发生回拨会导致可能生成id重复
  • 适用场景:分布式应用环境的数据主键

code

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
package gosnowflake

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

var (

// 开始计时时间
epoch = time.Now().UnixNano() / int64(time.Millisecond)
// 时间戳最大值
timestampMax int64 = -1 ^ (-1 << 41)
workerBits = uint(5)
dataCenterBits = uint(5)
sequenceBits = uint(12)
maxWorkerId int64 = -1 ^ (-1 << workerBits)
maxDataCenterId int64 = -1 ^ (-1 << dataCenterBits)
workerIdShift = sequenceBits
dataCenterIdShift = sequenceBits + workerBits
timestampLeftShift = sequenceBits + workerBits + dataCenterBits
sequenceMask int64 = -1 ^ (-1 << sequenceBits)
)

type IdWorker struct {
mutex sync.Mutex
workerId int64
dataCenterId int64
epoch int64
sequence int64
lastTimestamp int64
}

// NewIdWorker new worker
func NewIdWorker(workerId, dataCenterId, epoch int64) (error, *IdWorker){
if workerId > maxWorkerId || workerId < 0 {
return errors.New(fmt.Sprintf("worker Id can't be greater than %d or less than 0", maxWorkerId)), nil
}
if dataCenterId > maxDataCenterId || dataCenterId < 0 {
return errors.New(fmt.Sprintf("datacenter Id can't be greater than %d or less than 0", maxDataCenterId)), nil
}
id := &IdWorker{}
id.workerId = workerId
id.dataCenterId = dataCenterId
id.sequence = 0
id.lastTimestamp = -1
id.epoch = epoch
id.mutex = sync.Mutex{}
return nil, id
}

// NextId 生成一个ID
func (i *IdWorker) NextId() (error, int64){
// 加锁, 防止数据被更改
i.mutex.Lock()
defer i.mutex.Unlock()
timestamp := i.GenTime()
// 如果时间出现活泼, 直接抛弃
if timestamp < i.lastTimestamp {
// "clock is moving backwards. Rejecting requests until %d.", lastTimestamp
err := errors.New(fmt.Sprintf("Clock moved backwards. Refusing to generate id for %d milliseconds", i.lastTimestamp - timestamp))
return err, 0
}
// 同一毫秒内出现多个请求, sequence +1
// 最大值是4095, 超过4095则调用tilNextMillis进行等待
if i.lastTimestamp == timestamp {
i.sequence = (i.sequence + 1) & sequenceMask
if i.sequence == 0 {
timestamp = i.tilNextMillis(i.lastTimestamp)
}
}else {
i.sequence = 0
}
i.lastTimestamp = timestamp
return nil, ((timestamp - i.epoch) << timestampLeftShift) |
(i.dataCenterId << dataCenterIdShift) |
(i.workerId << workerIdShift) |
i.sequence
}

// tilNextMillis 等待下一毫秒
func (i *IdWorker) tilNextMillis(lastTimestamp int64) int64{
timestamp := i.GenTime()
for timestamp <= lastTimestamp {
timestamp = i.GenTime()
}
return timestamp
}

// GenTime 获取当前时间, 单位是毫秒
func (i *IdWorker) GenTime() int64{
return time.Now().UnixNano() / int64(time.Millisecond)
}

// GetWorkerId 获得workerID
func (i *IdWorker) GetWorkerId() int64{
return i.workerId
}

// GetDataCenterID 获得datacenterID
func (i *IdWorker) GetDataCenterID() int64 {
return i.dataCenterId
}

仓库地址:https://gitee.com/lingdun/gosnowflake

详细原理可以看看这篇文章