Pure Soul

  1. 首页
  2. Golang
  3. 正文

雪花算法及Golang实现

2022年1月2日 1381点热度 0人点赞 0条评论

目录

  • 雪花算法能解决什么问题?
  • SnowFlake的组成
  • SnowFlake的golang实现
  • 设置起始时间

雪花算法能解决什么问题?


雪花算法能够生成全局唯一的ID编码作为其他地方的标记。且生成一系列的ID满足如下的性质:

  • 生成的系列ID是递增的
  • 高可用性:任何时候都能够生成唯一的ID
  • 再高并发的条件下也能够保证服务

SnowFlake的组成


  • 最高位是符号位,始终为0
  • 41位的时间戳,精度位毫秒级,可使用69年
  • 10位的机器码,支持1024个节点
  • 12位的id,每毫秒可以生成4096个id
  • 12位的计数序列号,自增。同一节点,同一毫秒最多产生4096个序号

SnowFlake的golang实现


package snow

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

// 0(1位,且始终为0)|时间戳(41位)|工作机器id(10位)|序列号(12位)
type SNOW struct {
    machineID     int64
    snow          int64
    lastTimeStamp int64
    lock          sync.Mutex
}

func (snow *SNOW) initTimeStamp() {
    snow.lastTimeStamp = time.Now().UnixNano() / 1e6
}

func newSnow(machineID int64) (*SNOW, error) {
    snow := &SNOW{
        machineID:     0,
        snow:          0,
        lastTimeStamp: time.Now().UnixNano() / 1e6,
        lock:          sync.Mutex{},
    }
    err := snow.setMachineID(machineID)
    if err != nil {
        return &SNOW{}, err
    }
    return snow, err
}

func (snow *SNOW) setMachineID(id int64) error {
    if id > 1024 {
        return errors.New("Machine id must lower than 1024!")
    }
    snow.machineID = id << 12 // 左移12位变成机器号
    return nil
}

func (snow *SNOW) getID() int64 {
    // snow.lock.Lock()
    // defer snow.lock.Unlock()
    return snow.snowID()
}

func (snow *SNOW) snowID() int64 {
    curTimeStamp := time.Now().UnixNano() / 1e6
    if curTimeStamp == snow.lastTimeStamp { // 请求id的时间发生冲突
        // fmt.Println("current time is ", curTimeStamp, "last time is ", snow.lastTimeStamp, " cur snow is ", snow.snow)
        snow.snow++ // 防止冲突直接加一
        if snow.snow > 4095 {
            time.Sleep(time.Nanosecond) // 无法加一的时候直接睡眠并置0,一定不会冲突,相当于同时修改snow以及时间戳
            curTimeStamp = time.Now().UnixNano() / 1e6
            snow.lastTimeStamp = curTimeStamp
            snow.snow = 0
        }
        timeStampInSnmow := curTimeStamp & 0x1FFFFFFFFFF // 保留低41位的值
        timeStampInSnmow <<= 22                          // 作为时间戳的41位时间值
        return timeStampInSnmow | snow.machineID | snow.snow
    } else {
        snow.snow = 0
        snow.lastTimeStamp = curTimeStamp
        timeStampInSnmow := curTimeStamp & 0x1FFFFFFFFFF // 保留低41位的值
        timeStampInSnmow <<= 22                          // 作为时间戳的41位时间值
        return timeStampInSnmow | snow.machineID | snow.snow
    }
}

测试代码:

package snow

import (
    "fmt"
    "log"
    "os"
    "testing"
)

func Test_snowID(t *testing.T) {
    snow, err := newSnow(654)
    if err != nil {
        log.Println("ERROR!")
        os.Exit(2)
    }
    for i := 0; i < 10; i++ {
        fmt.Println(snow.getID())
    }
}

结果输出:

6883386281140215809
6883386281140215810
6883386281140215811
6883386281140215812
6883386281140215813
6883386281140215814
6883386281140215815
6883386281140215816
6883386281140215817
6883386281140215818

设置起始时间


之前提到过,算法的有效时间只有69.7年,Unix时间是从1970年开始计时的,因此在之前的绝大部分时间是被浪费的,所以我们可以对时间戳进行移动,让其不在1970年开始计时。

package snow

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

// 0(1位,且始终为0)|时间戳(41位)|工作机器id(10位)|序列号(12位)
type SNOW struct {
    machineID     int64
    snow          int64
    lastTimeStamp int64
    startStamp    int64
    lock          sync.Mutex
}

func (snow *SNOW) initTimeStamp() {
    snow.lastTimeStamp = time.Now().UnixNano()/1e6 - snow.startStamp
}

func newSnow(machineID int64) (*SNOW, error) {
    snow := &SNOW{
        machineID:     0,
        snow:          0,
        startStamp:    1640966400000, // 从2022-01-01 00::00:00开始计算
        lastTimeStamp: time.Now().UnixNano() / 1e6,
        lock:          sync.Mutex{},
    }
    snow.lastTimeStamp = snow.lastTimeStamp - snow.startStamp
    err := snow.setMachineID(machineID)
    if err != nil {
        return &SNOW{}, err
    }
    return snow, err
}

func (snow *SNOW) setMachineID(id int64) error {
    if id > 1024 {
        return errors.New("Machine id must lower than 1024!")
    }
    snow.machineID = id << 12 // 左移12位变成机器号
    return nil
}

func (snow *SNOW) getID() int64 {
    // snow.lock.Lock()
    // defer snow.lock.Unlock()
    return snow.snowID()
}

func (snow *SNOW) snowID() int64 {
    curTimeStamp := time.Now().UnixNano()/1e6 - snow.startStamp
    if curTimeStamp == snow.lastTimeStamp { // 请求id的时间发生冲突
        // fmt.Println("current time is ", curTimeStamp, "last time is ", snow.lastTimeStamp, " cur snow is ", snow.snow)
        snow.snow++ // 防止冲突直接加一
        if snow.snow > 4095 {
            time.Sleep(time.Nanosecond) // 无法加一的时候直接睡眠并置0,一定不会冲突,相当于同时修改snow以及时间戳
            curTimeStamp = time.Now().UnixNano()/1e6 - snow.startStamp
            snow.lastTimeStamp = curTimeStamp
            snow.snow = 0
        }
        timeStampInSnmow := curTimeStamp & 0x1FFFFFFFFFF // 保留低41位的值
        timeStampInSnmow <<= 22                          // 作为时间戳的41位时间值
        return timeStampInSnmow | snow.machineID | snow.snow
    } else {
        snow.snow = 0
        snow.lastTimeStamp = curTimeStamp
        timeStampInSnmow := curTimeStamp & 0x1FFFFFFFFFF // 保留低41位的值
        timeStampInSnmow <<= 22                          // 作为时间戳的41位时间值
        return timeStampInSnmow | snow.machineID | snow.snow
    }
}
标签: 暂无
最后更新:2022年1月2日

ycq

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

COPYRIGHT © 2021 oo2ee.com. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS