golang：使用雪花算法实现生成唯一id
■实例说明原生Snowflake算法使用一个64 bit的整型数据，根据当前的时间来生成ID。 原生Snowflake结构如下：
因为最高位是标识位，为1表示为负数，所以最高位不使用。
41bit 保存时间戳，精确到毫秒。也就是说最大可使用的年限是69年。
10bit 的机器位，能部属在1024台机器节点来生成ID。
12bit 的序列号，一毫秒最大生成唯一ID的数量为4096个。雪花算法有很多不同实现，下面例子中是sony的实现（注意：例子中几部分的位数修改成了和上图一致）
1）原版：https://github.com/bwmarrin/snowflake/blob/master/snowflake.go
2）sony：https://github.com/sony/sonyflake/blob/master/sonyflake.go
■实例代码
package main
import (
"errors"
"fmt"
"net"
"sync"
"time"
)
func main() {
// 使用默认时间创建实例
idgen := NewSnowflake(Settings{})
// 生成一个id
uniqId, uniqIdErr := idgen.NextID()
fmt.Println(uniqId)
fmt.Println(uniqIdErr)
}
// 定义雪花算法生成id的组成部分的位数
// id：64bit（1，第一位，默认0，41位毫秒时间戳，12位序列号，10位机器号）
// 我们可以调整这里的数值以生成不同范围的id，这里值和sony算法中值不同
const (
// 41位毫秒时间戳
BitLenTime = 41
// 12位序列
BitLenSequence = 12
// 10位机器号
BitLenMachineID = 63 - BitLenTime - BitLenSequence
)
// Settings configures Snowflake:
//
// StartTime is the time since which the Snowflake time is defined as the elapsed time.
// If StartTime is 0, the start time of the Snowflake is set to "2014-09-01 00:00:00 +0000 UTC".
// If StartTime is ahead of the current time, Snowflake is not created.
//
// MachineID returns the unique ID of the Snowflake instance.
// If MachineID returns an error, Snowflake is not created.
// If MachineID is nil, default MachineID is used.
// Default MachineID returns the lower 16 bits of the private IP address.
//
// CheckMachineID validates the uniqueness of the machine ID.
// If CheckMachineID returns false, Snowflake is not created.
// If CheckMachineID is nil, no validation is done.
// Settings 算法配置信息
// StartTime
type Settings struct {
StartTime time.Time
MachineID func() (uint16, error)
CheckMachineID func(uint16) bool
}
// Snowflake is a distributed unique ID generator.
type Snowflake struct {
mutex *sync.Mutex
startTime int64
elapsedTime int64
sequence uint16
machineID uint16
}
// NewSnowflake returns a new Snowflake configured with the given Settings.
// NewSnowflake returns nil in the following cases:
// - Settings.StartTime is ahead of the current time.
// - Settings.MachineID returns an error.
// - Settings.CheckMachineID returns false.
func NewSnowflake(st Settings) *Snowflake {
sf := new(Snowflake)
sf.mutex = new(sync.Mutex)
sf.sequence = uint16(1<<BitLenSequence - 1)
if st.StartTime.After(time.Now()) {
return nil
}
if st.StartTime.IsZero() {
sf.startTime = toSnowflakeTime(time.Date(2014, 9, 1, 0, 0, 0, 0, time.UTC))
} else {
sf.startTime = toSnowflakeTime(st.StartTime)
}
var err error
if st.MachineID == nil {
sf.machineID, err = lower12BitPrivateIP()
} else {
sf.machineID, err = st.MachineID()
}
if err != nil || (st.CheckMachineID != nil && !st.CheckMachineID(sf.machineID)) {
return nil
}
return sf
}
// NextID generates a next unique ID.
// After the Snowflake time overflows, NextID returns an error.
func (sf *Snowflake) NextID() (uint64, error) {
const maskSequence = uint16(1<<BitLenSequence - 1)
sf.mutex.Lock()
defer sf.mutex.Unlock()
current := currentElapsedTime(sf.startTime)
if sf.elapsedTime < current {
sf.elapsedTime = current
sf.sequence = 0
} else { // sf.elapsedTime >= current
sf.sequence = (sf.sequence + 1) & maskSequence
if sf.sequence == 0 {
sf.elapsedTime++
overtime := sf.elapsedTime - current
time.Sleep(sleepTime((overtime)))
}
}
return sf.toID()
}
const snowflakeTimeUnit = 1e6 // nsec, i.e. 1 msec
func toSnowflakeTime(t time.Time) int64 {
return t.UTC().UnixNano() / snowflakeTimeUnit
}
func currentElapsedTime(startTime int64) int64 {
return toSnowflakeTime(time.Now()) - startTime
}
func sleepTime(overtime int64) time.Duration {
return time.Duration(overtime)*10*time.Millisecond -
time.Duration(time.Now().UTC().UnixNano()%snowflakeTimeUnit)*time.Nanosecond
}
func (sf *Snowflake) toID() (uint64, error) {
if sf.elapsedTime >= 1<<BitLenTime {
return 0, errors.New("over the time limit")
}
return uint64(sf.elapsedTime)<<(BitLenSequence+BitLenMachineID) |
uint64(sf.sequence)<<BitLenMachineID |
uint64(sf.machineID), nil
}
func privateIPv4() (net.IP, error) {
addrs, err := net.InterfaceAddrs()
if err != nil {
return nil, err
}
for _, addr := range addrs {
if ipnet, ok := addr.(*net.IPNet); ok && !ipnet.IP.IsLoopback() {
ip := ipnet.IP.To4()
if ip == nil {
continue
}
return ip, nil
}
}
return nil, errors.New("no private ip address")
}
func lower12BitPrivateIP() (uint16, error) {
ip, err := privateIPv4()
if err != nil {
return 0, err
}
return (uint16(ip)<<8 + uint16(ip)) & 0x0fff, nil
}
// Decompose returns a set of Snowflake ID parts.
func Decompose(id uint64) mapuint64 {
const maskSequence = uint64((1<<BitLenSequence - 1) << BitLenMachineID)
const maskMachineID = uint64(1<<BitLenMachineID - 1)
msb := id >> 63
time := id >> (BitLenSequence + BitLenMachineID)
sequence := id & maskSequence >> BitLenMachineID
machineID := id & maskMachineID
return mapuint64{
"id": id,
"msb": msb,
"time": time,
"sequence": sequence,
"machine-id": machineID,
}
}
页:
[1]