简介
雪花算法 也叫 SnowFlake， 是 Twitter 开源的分布式 id 生成算法，核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增的，生成的最终结果其实就是一个 long 类型的长整型数字。
算法所有的内容都是针对这个数字进行运算的。我们单说long类型，64位说的是数字转换为二进制形式时候的表现，其中第一位表示的是正负，也就是符号，剩下的63位表示的是字面数字
为什么要使用雪花算法
针对每个公司，随着服务化演进，单个服务越来越多，数据库分的越来越细，有的时候一个业务需要分成好几个库，这时候自增主键或者序列之类的主键 id 生成方式已经不再满足需求，分布式系统中需要的是一个全局唯一的 id 生成规则雪花算法孕育而生
雪花算法实现
雪花算法把时间戳，工作机器 ID， 序列号组合成一个 64 位 long 类型数字
第一位置零，
[2,42] 这 41 位存放时间戳
[43,52] 这 10 位存放机器 id
[53,64] 最后 12 位存放序列号
这 64 个 bit 中，其中 1 个 bit 是不用的，然后用其中的 41 bit 作为毫秒数，用 10 bit 作为工作机器 id，12 bit 作为序列号
golang 实现
package algorithm
import "time"
var (
machineID int64 // 机器 id 占10位, 十进制范围是 [ 0, 1023 ]
sn int64 // 序列号占 12 位,十进制范围是 [ 0, 4095 ]
lastTimeStamp int64 // 上次的时间戳(毫秒级), 1秒=1000毫秒, 1毫秒=1000微秒,1微秒=1000纳秒
)
func init() {
lastTimeStamp = time.Now().UnixNano() / 1000000
}
func SetMachineId(mid int64) {
// 把机器 id 左移 12 位,让出 12 位空间给序列号使用
machineID = mid << 12
}
func GetSnowflakeId() int64 {
curTimeStamp := time.Now().UnixNano() / 1000000
// 同一毫秒
if curTimeStamp == lastTimeStamp {
sn++
// 序列号占 12 位,十进制范围是 [ 0, 4095 ]
if sn > 4095 {
time.Sleep(time.Millisecond)
curTimeStamp = time.Now().UnixNano() / 1000000
lastTimeStamp = curTimeStamp
sn = 0
}
// 取 64 位的二进制数 0000000000 0000000000 0000000000 0001111111111 1111111111 1111111111 1 ( 这里共 41 个 1 )和时间戳进行并操作
// 并结果( 右数 )第 42 位必然是 0, 低 41 位也就是时间戳的低 41 位
rightBinValue := curTimeStamp & 0x1FFFFFFFFFF
// 机器 id 占用10位空间,序列号占用12位空间,所以左移 22 位; 经过上面的并操作,左移后的第 1 位,必然是 0
rightBinValue <<= 22
id := rightBinValue | machineID | sn
return id
}
if curTimeStamp > lastTimeStamp {
sn = 0
lastTimeStamp = curTimeStamp
// 取 64 位的二进制数 0000000000 0000000000 0000000000 0001111111111 1111111111 1111111111 1 ( 这里共 41 个 1 )和时间戳进行并操作
// 并结果( 右数 )第 42 位必然是 0, 低 41 位也就是时间戳的低 41 位
rightBinValue := curTimeStamp & 0x1FFFFFFFFFF
// 机器 id 占用10位空间,序列号占用12位空间,所以左移 22 位; 经过上面的并操作,左移后的第 1 位,必然是 0
rightBinValue <<= 22
id := rightBinValue | machineID | sn
return id
}
if curTimeStamp < lastTimeStamp {
return 0
}
return 0
}
QA
Q：为什么第一位不用
A：因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0
Q：41 bit：表示的是时间戳，单位为什么是毫秒
41 bit 可以表示的数字达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。
Q：为什么用 10 bit 表示工作机器 ID
10 bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。
但是 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），也可以根据自己公司的实际情况确定。
Q：序列号是什么
这个是用来记录同一个毫秒内产生的不同 id
12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。
