golang：使用雪花算法实现生成唯一id

admin

■实例说明
原生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

■实例代码

[Golang] 纯文本查看 复制代码

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[2])<<8 + uint16(ip[3])) & 0x0fff, nil
}

// Decompose returns a set of Snowflake ID parts.
func Decompose(id uint64) map[string]uint64 {
        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 map[string]uint64{
                "id":         id,
                "msb":        msb,
                "time":       time,
                "sequence":   sequence,
                "machine-id": machineID,
        }
}