[golang] 分布式ID生成算法Snowflake
2017-10-19 本文已影响0人
king_wang
大部分分布式系统中，对一些互斥资源通常需要一个集群唯一的ID，比如消息id，订单号等。而且很多业务需求往往要求这些ID必须具有先后顺序，以方便分页或者排序。这就要求ID具有两个特性:
- 全局唯一
- 随时间递增
Snowflake
Twitter-Snowflake算法很好的解决了这种需求，它可以非常高效的生成ID，其核心思想如下(图片来自网络):
snowflake-64bit.jpg
- 时间戳。时间戳段位共41位，单位毫秒，可以使用约70年。为了增加剩余可用期限，一般都会把起始日期尽量后移而不是直接使用1970-01-01。（ps：如果是使用1970，你的程序只能支持到2039年了）
- 机器id。用于区分集群内不同机器，因为Snowflake生成ID是在每台机器上进行的。一般集群中每个节点都会有一个自己的id标示，如果实在没有也可以通过grpc，thrift等由master server生成。我们系统的nodeid是通过zookeeper来生成的。
- 序列号。由于高并发的特性，即使时间戳精确到了毫秒，也有可能出现重复。序列号用于同一时间戳下生成多个id。12位的长度，可以达到每秒上限1000*(2^12)=400W，完全够用了。
Golang实现
实现代码如下:
/*
* 1 42 52 64
* +-----------------------------------------------+------------+---------------+
* | timestamp(ms) | workerid | sequence |
* +-----------------------------------------------+------------+---------------+
* | 0000000000 0000000000 0000000000 0000000000 0 | 0000000000 | 0000000000 00 |
* +-----------------------------------------------+------------+---------------+
*
* 1. 41位时间截(毫秒级)，注意这是时间截的差值（当前时间截 - 开始时间截)。可以使用约70年: (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
* 2. 10位数据机器位，可以部署在1024个节点
* 3. 12位序列，毫秒内的计数，同一机器，同一时间截并发4096个序号
*/
const (
twepoch = int64(1483228800000) //开始时间截 (2017-01-01)
workeridBits = uint(10) //机器id所占的位数
sequenceBits = uint(12) //序列所占的位数
workeridMax = int64(-1 ^ (-1 << workeridBits)) //支持的最大机器id数量
sequenceMask = int64(-1 ^ (-1 << sequenceBits)) //
workeridShift = sequenceBits //机器id左移位数
timestampShift = sequenceBits + workeridBits //时间戳左移位数
)
// A Snowflake struct holds the basic information needed for a snowflake generator worker
type Snowflake struct {
sync.Mutex
timestamp int64
workerid int64
sequence int64
}
// NewNode returns a new snowflake worker that can be used to generate snowflake IDs
func NewSnowflake(workerid int64) (*Snowflake, error) {
if workerid < 0 || workerid > workeridMax {
return nil, errors.New("workerid must be between 0 and 1023")
}
return &Snowflake{
timestamp: 0,
workerid: workerid,
sequence: 0,
}, nil
}
// Generate creates and returns a unique snowflake ID
func (s *Snowflake) Generate() int64 {
s.Lock()
now := time.Now().UnixNano() / 1000000
if s.timestamp == now {
s.sequence = (s.sequence + 1) & sequenceMask
if s.sequence == 0 {
for now <= s.timestamp {
now = time.Now().UnixNano() / 1000000
}
}
} else {
s.sequence = 0
}
s.timestamp = now
r := int64((now-twepoch)<<timestampShift | (s.workerid << workeridShift) | (s.sequence))
s.Unlock()
return r
}
上面代码的benchmark结果如下：
$ go test -run=nonthingplease -bench=BenchmarkSnowflake -count=10
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
BenchmarkGenerate-4 5000000 243 ns/op 0 B/op 0 allocs/op
