关于golang:学会雪花算法就看这一篇就够了go版本

原文链接

前言

嗨，everybody，我是 asong，这是我的第十二篇文章，明天给大家介绍一下雪花算法。介绍雪花算法是主要的，因为大家都太相熟了，次要目标是举荐一下我的新系列。明天，我突发奇想，想创立一个新系列。这个系列次要是存储咱们日常工作开发中应用的算法，比方雪花算法、哈希算法等等。网络上对于这些算法的常识还是很多的，然而很杂，想找一个算法很不容易，还要看各种各样的博客，形形色色的。所以咱们当初的想法就是想将这些算法整顿到一起，全副采纳 go 实现，并附带基础知识学习，代码阐明这样的具体文档，这样咱们想要学习一门新算法时，都能够在这里找到，如果没有也能够提交 issues 一块欠缺。目前也是刚刚起步，当初只有雪花算法的代码文档，当前会缓缓欠缺起来的，有趣味的小伙伴欢送退出进来，咱们一起欠缺。详情请看 github 阐明：https://github.com/asong2020/…。

雪花算法背景

雪花算法产生的背景当然是 twitter 高并发环境下对惟一 ID 生成的需要，得益于 twitter 外部牛逼的技术，雪花算法可能流传于至今并且被宽泛应用，是因为它有几个特点

• 能满足高并发分布式系统环境下 ID 不反复
• 生成效率高
• 基于工夫戳，能够保障根本有序递增
• 不依赖于第三方的库或者中间件
• 生成的 id 具备时序性和唯一性

雪花算法原理

先来看一个图片吧，来源于网络：

由图咱们能够看进去，snowFlake ID构造是一个 64bit 的 int 型数据。

• 第 1 位 bit

在二进制中最高位为 1，示意的是正数，因为咱们应用的 id 应该都是整数，所以这里最高位应该是 0。

• 41bit 工夫戳

41 位能够示意 2^41-1 个数字，如果只用来示意正整数，能够示意的数值范畴是：0 – (2^41 -1)，这里减去 1 的起因就是因为数值范畴是从 0 开始计算的，而不是从 1 开始的。

这里的单位是毫秒，所以 41 位就能够示意 2^41-1 个毫秒值，这样转化成单位年则是 (2^41-1)/(1000 * 60 * 60 * 24 * 365) = 69

• 10bit- 工作机器 id

这里是用来记录工作机器的 id。2^10=1024示意以后规定容许分布式最大节点数为 1024 个节点。这里包含 5 位的 workerID 和 5 位的dataCenterID，这里其实能够不辨别，但我上面的代码进行了辨别。

• 12bit- 序列号

用来记录同毫秒内产生的不同 id。12bit 能够示意的最大正整数是 2^12-1=4095，即能够用0,1,2,3,......4094 这4095个数字，示意同一机器同一时间戳 (毫秒) 内产生的 4095 个 ID 序号。

原理就是下面这些，没有什么难度吧，上面咱们看代码如何实现：

go 实现雪花算法

1. 定义根本常量

先看代码，咱们顺次介绍：

const (workerIDBits =  uint64(5)  // 10bit 工作机器 ID 中的 5bit workerID
    dataCenterIDBits = uint64(5) // 10 bit 工作机器 ID 中的 5bit dataCenterID
    sequenceBits = uint64(12)

    maxWorkerID = int64(-1) ^ (int64(-1) << workerIDBits) // 节点 ID 的最大值 用于避免溢出
    maxDataCenterID = int64(-1) ^ (int64(-1) << dataCenterIDBits)
    maxSequence = int64(-1) ^ (int64(-1) << sequenceBits)

    timeLeft = uint8(22)  // timeLeft = workerIDBits + sequenceBits // 工夫戳向左偏移量
    dataLeft = uint8(17)  // dataLeft = dataCenterIDBits + sequenceBits
    workLeft = uint8(12)  // workLeft = sequenceBits // 节点 IDx 向左偏移量
    // 2020-05-20 08:00:00 +0800 CST
    twepoch = int64(1589923200000) // 常量工夫戳(毫秒)
)

上面对这段代码的每一个常量进行解释：

• worerIDBits：这里就是对应上图中的 10bit- 工作机器 id，我这里进行拆分了。这是其中 5bit`worerIDBits
• dataCenterIDBits：这里就是对应上图中的 10bit- 工作机器 id，我这里进行拆分了。这是其中 5bitdataCenterIDBits
• sequenceBits：对应上图中的 12bit 的序列号
• maxWorkerID：这里就是求最大，只不过咱们采纳了异或的形式，因为 - 1 的二进制示意为 1 的补码，说艰深一点，这里其实就是2^5-1，还不懂的同学，能够本人验证一下
• maxDataCenterID：原理同上
• maxSequence：原理同上
• timeLeft：工夫戳向左偏移量，这么你们可能不懂，看下面的图片，由有向左的偏移量是不是 22，这么说你们懂了吗？
• dataLeft：原理同上，也是求偏移量的
• workLeft：原理同上；
• twepoch：41bit 的工夫戳，单位是毫秒，这里我抉择的工夫是2020-05-20 08:00:00 +0800 CST，这个 ID 一但生成就不要改了，要不会生成雷同的 ID。

2. 定义 worker 工作节点

因为这个是在分布式下应用的 ID 生成算法，所以咱们要生成多个worker，所以要把节点参数形象进去。

type Worker struct {
    mu sync.Mutex
    LastStamp int64 // 记录上一次 ID 的工夫戳
    WorkerID int64 // 该节点的 ID
    DataCenterID int64 // 该节点的 数据中心 ID
    Sequence int64 // 以后毫秒曾经生成的 ID 序列号(从 0 开始累加) 1 毫秒内最多生成 4096 个 ID
}

代码解释：

• mu sync.Mutex：增加互斥锁，确保并发安全性
• LastStamp int64：记录上一次生成 ID 的工夫戳
• WorkerID int64：该工作节点的 ID 对上图中的 5bit workerID 一个意思
• DataCenterID int64：原理同上
• Sequence int64：以后毫秒曾经生成的 id 序列号(从 0 开始累加) 1 毫秒内最多生成 4096 个 ID

3. 创立一个 worker 对象

// 分布式状况下, 咱们应通过内部配置文件或其余形式为每台机器调配独立的 id
func NewWorker(workerID,dataCenterID int64) *Worker  {
    return &Worker{
        WorkerID: workerID,
        LastStamp: 0,
        Sequence: 0,
        DataCenterID: dataCenterID,
    }
}

这里没有什么好解释的～～～。

4. 生成 id

先看代码：

func (w *Worker) getMilliSeconds() int64 {return time.Now().UnixNano() / 1e6}

func (w *Worker)NextID() (uint64,error) {w.mu.Lock()
    defer w.mu.Unlock()


    return w.nextID()}

func (w *Worker)nextID() (uint64,error) {timeStamp := w.getMilliSeconds()
    if timeStamp < w.LastStamp{return 0,errors.New("time is moving backwards,waiting until")
    }

    if w.LastStamp == timeStamp{w.Sequence = (w.Sequence + 1) & maxSequence

        if w.Sequence == 0 {
            for timeStamp <= w.LastStamp {timeStamp = w.getMilliSeconds()
            }
        }
    }else {w.Sequence = 0}

    w.LastStamp = timeStamp
    id := ((timeStamp - twepoch) << timeLeft) |
        (w.DataCenterID << dataLeft)  |
        (w.WorkerID << workLeft) |
        w.Sequence

    return uint64(id),nil
}

代码有点长，我先来顺次解释一下：

• getMilliSeconds()：封装的一个办法，用来获取以后的毫秒值
• func (w *Worker)NextID() (uint64,error)

这个代码的内容没有什么，具体生成 ID 算法封装在 func (w *Worker)nextID() (uint64,error) 这里了，这里不过是为理解藕作用；对了还有一个特地重要的中央，加锁、开释锁，这个步骤很重要。

• func (w *Worker)nextID() (uint64,error)

这里是真正的生成 id 代码了。分为几个步骤：

• 获取以后工夫戳，进行判断，要确保以后工夫戳值大于上一次生成 ID 的工夫戳，否则会呈现反复。
• 如果想等了，首先获取以后的以后毫秒曾经生成的 id 序列号。这里你们可能没看懂，其实他等效于if w.sequence++ > maxSequence

, 如果以后毫秒曾经生成的 id 序列号溢出了，则须要期待下一毫秒，如果不期待，就会导致很多反复。

• 咱们在 else 里将 w.sequence 置零了，这里解释一下，如果以后工夫与工作节点上一次生成 ID 的工夫不统一 则须要重置工作节点生成 ID 的序号。
• 最初一步，比拟重要，采纳了或运算，这里的目标就是各局部的 bit 进行归位并通过按位或运算 (就是这个‘|’) 将其整合。<<这个就是向左偏移的作用进行归位，而 | 运算就是为了整合。可能大家还没懂，看上面这一张图片吧：

怎么样，是不是晓得什么意思了。

5. 测试

写好了代码，咱们就来测试一下吧，这里我并发 10000 个 goroutine 进行生成 ID，存入到 map，查看是否呈现反复，来看代码：

var wg sync.WaitGroup

func main()  {w := idgen.NewWorker(5,5)

    ch := make(chan uint64,10000)
    count := 10000
    wg.Add(count)
    defer close(ch)
    // 并发 count 个 goroutine 进行 snowFlake ID 生成
    for i:=0 ; i < count ; i++ {go func() {defer wg.Done()
            id,_ := w.NextID()
            ch <- id
        }()}
    wg.Wait()
    m := make(map[uint64]int)
    for i := 0; i < count; i++  {
        id := <- ch
        // 如果 map 中存在为 id 的 key, 阐明生成的 snowflake ID 有反复
        _, ok := m[id]
        if ok {fmt.Printf("repeat id %d\n",id)
            return
        }
        // 将 id 作为 key 存入 map
        m[id] = i
    }
    // 胜利生成 snowflake ID
    fmt.Println("All", len(m), "snowflake ID Get successed!")

}

验证后果：

All 10000 snowflake ID Get successed!

总结

好啦，这一篇文章到这里完结啦，雪花算法并没有咱们设想的那么难，还是很好实现的，你学会了吗？没学会不要紧，下载源代码，再看一看，对你不是问题的～～～。

GitHub：https://github.com/asong2020/… 欢送 star 感激各位～～～

敌人们，还记得我结尾说的那些吗？有趣味的欢送退出进来呦，咱们一起提高～～～。

结尾给大家发一个小福利吧，最近我在看 [微服务架构设计模式] 这一本书，讲的很好，本人也收集了一本 PDF，有须要的小伙能够到自行下载。获取形式：关注公众号：[Golang 梦工厂]，后盾回复：[微服务]，即可获取。

我翻译了一份 GIN 中文文档，会定期进行保护，有须要的小伙伴后盾回复 [gin] 即可下载。

我是 asong，一名普普通通的程序猿，让我一起缓缓变强吧。我本人建了一个 golang 交换群，有须要的小伙伴加我vx, 我拉你入群。欢送各位的关注，咱们下期见~~~

举荐往期文章：

• 详解 Context 包，看这一篇就够了！！！
• go-ElasticSearch 入门看这一篇就够了(一)
• 面试官：go 中 for-range 应用过吗？这几个问题你能解释一下起因吗
• 学会 wire 依赖注入、cron 定时工作其实就这么简略！
• 据说你还不会 jwt 和 swagger- 饭我都不吃了带着实际我的项目我就来了
• 把握这些 Go 语言个性，你的程度将进步 N 个品位(二)
• go 实现多人聊天室，在这里你想聊什么都能够的啦！！！
• grpc 实际 - 学会 grpc 就是这么简略
• go 规范库 rpc 实际
• 2020 最新 Gin 框架中文文档 asong 又捡起来了英语，用心翻译
• 基于 gin 的几种热加载形式
• boss: 这小子还不会应用 validator 库进行数据校验，开了～～～