最近在着手准备一个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 型数据。
- 第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这个常量时的时间戳(毫秒) )@H_404_59@上述代码中 两个偏移量 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 }@H_404_59@实例化工作节点
由于是分布式情况下，我们应该通过外部配置文件或者其他方式为每台机器分配独立的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 }@H_404_59@可以通过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 }@H_404_59@很多新入门的朋友可能看到最后的ID := xxxxx << xxx | xxxxxx << xx | xxxxx 有点懵
这里是对各部分的bit进行归位并通过按位或运算(就是这个‘|’)将其整合
用一张图来解释
想必大家看完后就很清晰了吧
至于某一段一开始位数可能不够？ 别担心二进制空位会自动补0！针对这个"|"多解释一下
参加运算的两个数，换算为二进制(0、1)后，进行或运算。只要相应位上存在1，那么该位就取1，均不为1，即为0
同样 看完图就很清楚啦(百度会不会说我盗图啊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!") }@H_404_59@结果
用的是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@H_404_59@并发生成一万个id用时0.031秒
如果能跑在分布式服务器上 估计更快了~
够用了够用了本文结合网络内容加上自己的一些小小的优化整理而成
最后附上github地址：https://github.com/holdno/sno... 觉得有用可以给颗星星哦 不早了要去洗洗睡了 晚安~
