分布式 ID

不同机器生成的 ID 全局唯一，且生成和处理效率高。

常用

  • UUID
  • 雪花算法

UUID

128 位二进制组成，表示成 8-4-4-4-12 形式的16进制字符，有 5 个版本

基本形式如下：

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
  • M 表示版本，1-5
  • N表示变体，8-b

版本

  1. V1

    时间戳 + MAC 地址

    一台机子跑2个进程可能会出现重复

  2. V2

    用户ID + 组ID + 时间戳 + MAC 地址

  3. V3

    namespace + MD5(content)

  4. V4

    随机数

  5. V5

    namespace + SHA1(content)

缺点

  • 无序

雪花算法

介绍

Twitter 开源的生成分布式全局唯一 ID 的算法

一共有 64 bit，第一位恒为 0，后面 41 bit 是时间戳，接着是 10 bit 的机器 ID，最后是有序序列号。

机器 ID也可以细分，分为节点 ID 和 机器ID

时间戳可以设置偏移量，设置开始时间。

基于时间和序列号生成的，所以是有序的。

7

缺点

依赖服务器的时间，如果服务器时间回拨，可能会生成重复 ID

手写实现

使用 Go 实现雪花算法

package snowflake

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

const (
    startTimeStr = "2023-08-01"

    timestampBits  = 41
    workerIDBits   = 10
    sequenceIDBits = 12

    timestampMax  = -1 ^ (-1 << timestampBits)  //求数据范围最大值
    workerIDMax   = -1 ^ (-1 << workerIDBits)   //求数据范围最大值
    sequenceIDMax = -1 ^ (-1 << sequenceIDBits) //求数据范围最大值
    t
    sequenceIDShift = 0 //存储位置
    workerIDShift   = sequenceIDShift + sequenceIDBits
    timestampShift  = workerIDShift + workerIDBits
)

var startTime, _ = time.Parse("2006-01-02", startTimeStr)

type Worker struct {
    mu sync.Mutex //同步
    //  也可以使用int64 定义，因为最高因为不使用，不会超出数据范围
    timestamp uint64 //时间戳
    workerID  uint64 //节点ID
    sequence  uint64 //序列号
}

func NewWorker(workerID uint64) (worker *Worker, err error) {
    if workerID < 0 || workerID > workerIDMax {
        return worker, errors.New("worker ID excess of quantity")
    }
    return &Worker{
        workerID: workerID,
    }, err
}
func (w *Worker) GetID() uint64 {
    w.mu.Lock()
    defer w.mu.Unlock()
    //为什么不能直接使用time.Now().UnixMilli()？
    currentTimestamp := uint64(time.Now().UnixNano() / 1e6)
    if currentTimestamp == w.timestamp {
        w.sequence++
        if w.sequence > sequenceIDMax {
            //如果超过了最大值，则进入死循环，直接到下一ms
            for currentTimestamp != w.timestamp {
                w.sequence = 0
                w.timestamp = currentTimestamp
            }
        }
    } else {
        w.sequence = 0
        w.timestamp = currentTimestamp
    }
    //生成ID
    ID := w.timestamp<<timestampShift | w.workerID<<workerIDShift | w.sequence<<sequenceIDShift
    return ID
}
func (w *Worker) GetIDHex() string {
    return strconv.FormatInt(int64(w.GetID()), 16)
}

测试

func Test_Snowflake(t *testing.T) {
    worker0, _ := snowflake.NewWorker(0)
    worker00, _ := snowflake.NewWorker(0)
    worker1, _ := snowflake.NewWorker(1)
    fmt.Printf("%v,%v,%v\n", worker0.GetIDHex(), worker00.GetIDHex(), worker1.GetIDHex())
    fmt.Printf("%v,%v,%v\n", worker0.GetIDHex(), worker00.GetIDHex(), worker1.GetIDHex())
}
626d624055000000,626d624055000000,626d624055001000
626d624055000001,626d624055000001,626d624055001001

第三方实现

bwmarrin/snowflake

func Test_Snowflake_bwmarrin(t *testing.T) {
    st, _ := time.Parse("2006-01-02", "2023-08-01")
    snowflakeb.Epoch = st.UnixNano() / 1e6
    worker0, _ := snowflakeb.NewNode(0)
    worker00, _ := snowflakeb.NewNode(0)
    worker1, _ := snowflakeb.NewNode(1)

    // Generate a snowflake ID.
    fmt.Printf("%v,%v,%v\n", worker0.Generate(), worker00.Generate(), worker1.Generate())
    fmt.Printf("%v,%v,%v\n", worker0.Generate(), worker00.Generate(), worker1.Generate())
}
503102344003584,503102344003584,503102344007680
503102344003585,503102344003585,503102344007681

参考

文章目录