记一次 golang 实现Twitter snowFlake算法 高效生成全局唯一ID

折叠椅
1,729 阅读8分钟
原文链接： segmentfault.com

最近在着手准备一个H5游戏
因为这是我第一次接触游戏这个类目
即使量不大也想好好的做它一番
在设计表结构的时候想到了表全局唯一id这个问题
既然是游戏
那么一定是多人在线点点点(运营理想状态 哈哈哈)
一开始想使用mongoDB的objectId来作为全局唯一id
但是字符串作为索引的效率肯定不如整型来得实在

两者的主要差别就在于，字符类型有字符集的概念，每次从存储端到展现端之间都有一个字符集编码的过程。而这一过程主要消耗的就是CPU资源，对于In-memory的操作来说，这是一个不可忽视的消耗。如果使用整型替换可以减少CPU运算及内存和IO的开销。

所以最后考虑到理想状态下的效率及视觉效果(整型)，考虑找一个纯整型的id替代方案 无意间看到了Twitter的snowFlake算法

这篇内容大部分借鉴网络内容，整合在一起只为帮助自己和各位看官更好的理解snowFlake的原理

snowFlake 雪花算法

snowflake ID 算法是 twitter 使用的唯一 ID 生成算法，为了满足 Twitter 每秒上万条消息的请求，使每条消息有唯一、有一定顺序的 ID ，且支持分布式生成。

原理

其实很简单，只需要理解：某一台拥有独立标识(为机器分配独立id)的机器在1毫秒内生成带有不同序号的id 所以生成出来的id是具有时序性和唯一性的

构成

这里直接借鉴前人的整理，只为给大家更加清楚的讲解

snowflake ID 的结构是一个 64 bit 的 int 型数据。

clipboard.png

  • 第1位bit：
    二进制中最高位为1的都是负数，但是我们所需要的id应该都是整数，所以这里最高位应该为0
  • 后面的41位bit：
    用来记录生成id时的毫秒时间戳，这里毫秒只用来表示正整数(计算机中正整数包含0)，所以可以表示的数值范围是0至2^41 - 1（这里为什么要-1很多人会范迷糊，要记住，计算机中数值都是从0开始计算而不是1）
  • 再后面的10位bit：
    用来记录工作机器的id
    2^10 = 1024 所以当前规则允许分布式最大节点数为1024个节点 我们可以根据业务需求来具体分配worker数和每台机器1毫秒可生成的id序号number数
  • 最后的12位：
    用来表示单台机器每毫秒生成的id序号
    12位bit可以表示的最大正整数为2^12 - 1 = 4096，即可用0、1、2、3...4095这4096(注意是从0开始计算)个数字来表示1毫秒内机器生成的序号(这个算法限定单台机器1毫秒内最多生成4096个id，超出则等待下一毫秒再生成)

最后将上述4段bit通过位运算拼接起来组成64位bit

实现

这里我们用golang来实现一下snowFlake 首先定义一下snowFlake最基础的几个常量，每个常量的用户我都通过注释来详细的告诉大家

// 因为snowFlake目的是解决分布式下生成唯一id 所以ID中是包含集群和节点编号在内的

const (
    numberBits uint8 = 12 // 表示每个集群下的每个节点，1毫秒内可生成的id序号的二进制位 对应上图中的最后一段
    workerBits uint8 = 10 // 每台机器(节点)的ID位数 10位最大可以有2^10=1024个节点数 即每毫秒可生成 2^12-1=4096个唯一ID 对应上图中的倒数第二段  
    // 这里求最大值使用了位运算，-1 的二进制表示为 1 的补码，感兴趣的同学可以自己算算试试 -1 ^ (-1 << nodeBits) 这里是不是等于 1023
    workerMax int64 = -1 ^ (-1 << workerBits) // 节点ID的最大值，用于防止溢出 
    numberMax int64 = -1 ^ (-1 << numberBits) // 同上，用来表示生成id序号的最大值
    timeShift uint8 = workerBits + numberBits // 时间戳向左的偏移量
    workerShift uint8 = numberBits // 节点ID向左的偏移量
    // 41位字节作为时间戳数值的话，大约68年就会用完
    // 假如你2010年1月1日开始开发系统 如果不减去2010年1月1日的时间戳 那么白白浪费40年的时间戳啊！
    // 这个一旦定义且开始生成ID后千万不要改了 不然可能会生成相同的ID
    epoch int64 = 1525705533000 // 这个是我在写epoch这个常量时的时间戳(毫秒)
)

上述代码中 两个偏移量 timeShift 和 workerShift 是对应图中时间戳和工作节点的位置
时间戳是在从右往左的 workerBits + numberBits (即22)位开始，大家可以数数看就很容易理解了
workerShift 同理

Worker 工作节点

因为是分布式下的ID生成算法，所以我们要生成多个Worker，所以这里抽象出一个woker工作节点所需要的基本参数

// 定义一个woker工作节点所需要的基本参数
type Worker struct {
    mu sync.Mutex // 添加互斥锁 确保并发安全
    timestamp int64 // 记录上一次生成id的时间戳
    workerId int64 // 该节点的ID
    number int64 // 当前毫秒已经生成的id序列号(从0开始累加) 1毫秒内最多生成4096个ID
}

实例化工作节点

由于是分布式情况下，我们应该通过外部配置文件或者其他方式为每台机器分配独立的id

// 实例化一个工作节点
// workerId 为当前节点的id
func NewWorker(workerId int64) (*Worker, error) {
    // 要先检测workerId是否在上面定义的范围内
    if workerId < 0 || workerId > workerMax {
        return nil, errors.New("Worker ID excess of quantity")
    }
    // 生成一个新节点
    return &Worker{
        timestamp: 0,
        workerId: workerId,
        number: 0,
    }, nil
}
可以通过redis来为分布式环境下的每台机子生成唯一id
该部分不包含在算法内

生成id

// 生成方法一定要挂载在某个woker下，这样逻辑会比较清晰 指定某个节点生成id
func (w *Worker) GetId() int64 {
    // 获取id最关键的一点 加锁 加锁 加锁
    w.mu.Lock()
    defer w.mu.Unlock() // 生成完成后记得 解锁 解锁 解锁

    // 获取生成时的时间戳
    now := time.Now().UnixNano() / 1e6 // 纳秒转毫秒
    if w.timestamp == now {
        w.number++

        // 这里要判断，当前工作节点是否在1毫秒内已经生成numberMax个ID
        if w.number > numberMax {
            // 如果当前工作节点在1毫秒内生成的ID已经超过上限 需要等待1毫秒再继续生成
            for now <= w.timestamp {
                now = time.Now().UnixNano() / 1e6
            }
        }
    } else {
        // 如果当前时间与工作节点上一次生成ID的时间不一致 则需要重置工作节点生成ID的序号
        w.number = 0
        // 下面这段代码看到很多前辈都写在if外面，无论节点上次生成id的时间戳与当前时间是否相同 都重新赋值  这样会增加一丢丢的额外开销 所以我这里是选择放在else里面
        w.timestamp = now // 将机器上一次生成ID的时间更新为当前时间
    }

    ID := int64((now - epoch) << timeShift | (w.workerId << workerShift) | (w.number))
    return ID
}

很多新入门的朋友可能看到最后的ID := xxxxx << xxx | xxxxxx << xx | xxxxx 有点懵
这里是对各部分的bit进行归位并通过按位或运算(就是这个‘|’)将其整合
用一张图来解释

clipboard.png
想必大家看完后就很清晰了吧
至于某一段一开始位数可能不够？ 别担心二进制空位会自动补0！

针对这个"|"多解释一下

参加运算的两个数，换算为二进制(0、1)后，进行或运算。只要相应位上存在1，那么该位就取1，均不为1，即为0

clipboard.png

同样 看完图就很清楚啦(百度会不会说我盗图啊T.T)

Test

接下来我们用golang的测试包来测试一下我们刚才生成的代码

package snowFlakeByGo

import (
    "testing"
    "fmt"
)

func TestSnowFlakeByGo(t *testing.T) {
    // 测试脚本

    // 生成节点实例
    worker, err := NewWorker(1)

    if err != nil {
        fmt.Println(err)
        return
    }

    ch := make(chan int64)
    count := 10000
    // 并发 count 个 goroutine 进行 snowflake ID 生成
    for i := 0; i < count; i++ {
        go func() {
            id := worker.GetId()
            ch <- id
        }()
    }

    defer close(ch)

    m := make(map[int64]int)
    for i := 0; i < count; i++  {
        id := <- ch
        // 如果 map 中存在为 id 的 key, 说明生成的 snowflake ID 有重复
        _, ok := m[id]
        if ok {
            t.Error("ID is not unique!\n")
            return
        }
        // 将 id 作为 key 存入 map
        m[id] = i
    }
    // 成功生成 snowflake ID
    fmt.Println("All", count, "snowflake ID Get successed!")
}
结果

用的是17版 13寸macbook pro(非Touch Bar)进行测试

wbyMacBook-Pro:snowFlakeByGo xxx$ go test
All 10000 snowflake ID Get successed!
PASS
ok      github.com/holdno/snowFlakeByGo 0.031s

并发生成一万个id用时0.031秒
如果能跑在分布式服务器上 估计更快了~
够用了够用了

本文结合网络内容加上自己的一些小小的优化整理而成
最后附上github地址：github.com/holdno/sno.…
觉得有用可以给颗星星哦
不早了要去洗洗睡了
晚安~

avatar
文章
阅读
粉丝

友情链接：