GUID
Posted on
在点外卖或者网上购物的时候，每个订单中都会有一串独一无二的数字，但是处理订单的服务器肯定不止一台，如何保证多台服务器，也就是说一个计算机集群中，在相互独立的情况下（不沟通自己生成的订单号的信息）不生成相同的订单号码呢，下面我们就来介绍一种全球唯一标识符（ GUID ）的生成算法。
这里我们的 GUID 共64比特。sequence 部分占12比特，nodeID 占10比特，偏移10比特，时间戳 timestamp 占剩余的42比特，偏移22比特。
1
2
3
| +-------------------------------------------+----------+------------+
| timestamp |nodeIDBits|sequenceBits|
+-------------------------------------------+----------+------------+
|
1
2
3
4
5
6
7
8
9
| const (
nodeIDBits = uint64(10)
sequenceBits = uint64(12)
nodeIDShift = sequenceBits
timestampShift = sequenceBits + nodeIDBits
sequenceMask = int64(-1) ^ (int64(-1) << sequenceBits)
twepoch = int64(1288834974288)
)
|
1
2
3
4
5
| var (
ErrIDBackwards = errors.New("ID went backward")
ErrTimeBackwards = errors.New("time has gone backwards")
ErrSequenceExpired = errors.New("sequence expired")
)
|
下面我们定义一个生成 guid 的工厂， guid 由 timestamp ，nodeID 和 sequence 这三个部分构成，每个工厂有自己的 nodeID。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| type guid int64
type guidFactory struct {
sync.Metex
nodeID int64
sequence int64
lastTimestamp int64
lastID guid
}
func NewGUIDFactory(nodeID int64) *guidFactory {
return &guidFactory{
nodeID: nodeID,
}
}
|
在利用工厂模式生成 GUID 时，首先计算当前时间戳，并且除以1048576（2的20次方），这样是为了去除时间的假随机部分，如果新生成的timestamp 小于 lastTimestamp ，则返回 ErrTimeBackwards 错误，对于相同的时间戳，我们的 sequence 采取递增策略，如果 sequence 达到最大值后归0，则返回 ErrSequenceExpired 错误，如果时间戳不相同，则令 sequence 重新从0开始，最后使三部分拼接组成一个新的 guid ，如果生成的 guid 小于 lastID ，则返回 ErrIDBackwards 错误，如果正常则返回结果。整个计算的过程需要由锁来保护。
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
| func (g *guidFactory) Create() (guid, error) {
f.Lock()
ts := time.Now().UnixNano() >> 20
if ts < f.lastTimestamp {
f.Unlock()
return 0, ErrTimeBackwards
}
if f.lastTimestamp == ts {
f.sequence = (f.sequence + 1) & sequenceMask
if f.sequence == 0 {
f.Unlock()
return 0, ErrSequenceExpired
}
} else {
f.sequence = 0
}
f.lastTimestamp = ts
id := guid(((ts - twepoch) << timestampShift) |
(f.nodeID << nodeIDShift) |
f.sequence)
if id <= f.lastID {
f.Unlock()
return 0, ErrIDBackwards
}
f.lastID = id
f.Unlock()
return id, nil
}
|
为了方便结果的表示，我们会将10进制转换为16进制，利用标准库中的 hex 就可以轻松实现了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func (g guid) Hex() MessageID {
var h MessageID
var b [8]byte
b[0] = byte(g >> 56)
b[1] = byte(g >> 48)
b[2] = byte(g >> 40)
b[3] = byte(g >> 32)
b[4] = byte(g >> 24)
b[5] = byte(g >> 16)
b[6] = byte(g >> 8)
b[7] = byte(g)
hex.Encode(h[:], b[:])
return h
}
|
