分布式系统中，有一些须要应用全局惟一 ID 的场景，这种时候为了避免 ID 抵触能够应用 36 位的 UUID，然而 UUID 有一些毛病，首先他绝对比拟长，另外 UUID 个别是无序的
有些时候咱们心愿能应用一种简略些的 ID，并且心愿 ID 可能依照工夫有序生成
什么是雪花算法
Snowflake 中文的意思是雪花，所以常被称为雪花算法，是 Twitter 开源的分布式 ID 生成算法
Twitter 雪花算法生成后是一个 64bit 的 long 型的数值，组成部分引入了工夫戳，根本放弃了自增
SnowFlake 算法的长处：
高性能高可用：生成时不依赖于数据库，齐全在内存中生成
高吞吐：每秒钟能生成数百万的自增 ID
ID 自增：存入数据库中，索引效率高
SnowFlake 算法的毛病：
依赖与零碎工夫的一致性，如果零碎工夫被回调，或者扭转，可能会造成 ID 抵触或者反复
雪花算法组成
snowflake 构造如下图所示：
蕴含四个组成部分
不应用：1bit，最高位是符号位，0 示意正，1 示意负，固定为 0
工夫戳：41bit，毫秒级的工夫戳（41 位的长度能够应用 69 年）
标识位：5bit 数据中心 ID，5bit 工作机器 ID，两个标识位组合起来最多能够反对部署 1024 个节点
序列号：12bit 递增序列号，示意节点毫秒内生成反复，通过序列号示意惟一，12bit 每毫秒可产生 4096 个 ID
通过序列号 1 毫秒能够产生 4096 个不反复 ID，则 1 秒能够生成 4096 * 1000 = 409w ID
默认的雪花算法是 64 bit，具体的长度能够自行配置。如果心愿运行更久，减少工夫戳的位数；如果须要反对更多节点部署，减少标识位长度；如果并发很高，减少序列号位数
总结：雪花算法并不是变化无穷的，能够依据零碎内具体场景进行定制
雪花算法实用场景
因为雪花算法有序自增，保障了 MySQL 中 B+ Tree 索引构造插入高性能
所以，日常业务应用中，雪花算法更多是被利用在数据库的主键 ID 和业务关联主键
雪花算法生成 ID 反复问题
假如：一个订单微服务，通过雪花算法生成 ID，共部署三个节点，标识位统一
此时有 200 并发，平均分布三个节点，三个节点同一毫秒同一序列号下生成 ID，那么就会产生反复 ID
通过上述假如场景，能够晓得雪花算法生成 ID 抵触存在肯定的前提条件
服务通过集群的形式部署，其中局部机器标识位统一
业务存在肯定的并发量，没有并发量无奈触发反复问题
生成 ID 的机会：同一毫秒下的序列号统一
标识位如何定义
如果能保障标识位不反复，那么雪花 ID 也不会反复
通过下面的案例，晓得了 ID 反复的必要条件。如果要防止服务内产生反复的 ID，那么就须要从标识位上动文章
咱们先看看开源框架中应用雪花算法，如何定义标识位
Mybatis-Plus v3.4.2 雪花算法实现类 Sequence，提供了两种构造方法：无参结构，主动生成 dataCenterId 和 workerId；有参结构，创立 Sequence 时明确指定标识位
Hutool v5.7.9 参照了 Mybatis-Plus dataCenterId 和 workerId 生成计划，提供了默认实现
一起看下 Sequence 的创立默认无参结构，如何生成 dataCenterId 和 workerId
public static long getDataCenterId(long maxDatacenterId) {
long id = 1L;
final byte[] mac = NetUtil.getLocalHardwareAddress();
if (null != mac) {id = ((0x000000FF & (long) mac[mac.length - 2])
| (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
id = id % (maxDatacenterId + 1);
}
return id;}
复制代码
入参 maxDatacenterId 是一个固定值，代表数据中心 ID 最大值，默认值 31
为什么最大值要是 31？因为 5bit 的二进制最大是 11111，对应十进制数值 31
获取 dataCenterId 时存在两种状况，一种是网络接口为空，默认取 1L；另一种不为空，通过 Mac 地址获取 dataCenterId
能够得悉，dataCenterId 的取值与 Mac 地址无关
接下来再看看 workerId
public static long getWorkerId(long datacenterId, long maxWorkerId) {
final StringBuilder mpid = new StringBuilder();
mpid.append(datacenterId);
try {mpid.append(RuntimeUtil.getPid());
} catch (UtilException igonre) {//ignore}
return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);}
复制代码
入参 maxWorkderId 也是一个固定值，代表工作机器 ID 最大值，默认值 31；datacenterId 取自上述的 getDatacenterId 办法
name 变量值为 PID@IP，所以 name 须要依据 @ 宰割并获取下标 0，失去 PID
通过 MAC + PID 的 hashcode 获取 16 个低位，进行运算，最终失去 workerId
调配标识位
Mybatis-Plus 标识位的获取依赖 Mac 地址和过程 PID，尽管能做到尽量不反复，但仍有小几率
标识位如何定义能力不反复？有两种计划：预调配和动态分配
预调配
利用上线前，统计以后服务的节点数，人工去申请标识位
这种计划，没有代码开发量，在服务节点固定或者我的项目少能够应用，然而解决不了服务节点动静扩容性问题
动态分配
通过将标识位寄存在 Redis、Zookeeper、MySQL 等中间件，在服务启动的时候去申请标识位，申请后标识位更新为下一个可用的
通过寄存标识位，延长出一个问题：雪花算法的 ID 是 服务内惟一还是全局惟一
以 Redis 举例，如果要做服务内惟一，寄存标识位的 Redis 节点应用本人我的项目内的就能够；如果是全局惟一，所有应用雪花算法的利用，要用同一个 Redis 节点
两者的区别仅是 不同的服务间是否专用 Redis。如果没有全局惟一的需要，最好使 ID 服务内惟一，因为这样能够防止单点问题
服务的节点数超过 1024，则须要做额定的扩大；能够扩大 10 bit 标识位，或者抉择开源分布式 ID 框架
动态分配实现计划
Redis 存储一个 Hash 构造 Key，蕴含两个键值对：dataCenterId 和 workerId
在利用启动时，通过 Lua 脚本去 Redis 获取标识位。dataCenterId 和 workerId 的获取与自增在 Lua 脚本中实现，调用返回后就是可用的标示位
具体 Lua 脚本逻辑如下：
第一个服务节点在获取时，Redis 可能是没有 snowflake_work_id_key 这个 Hash 的，应该先判断 Hash 是否存在，不存在初始化 Hash，dataCenterId、workerId 初始化为 0
如果 Hash 已存在，判断 dataCenterId、workerId 是否等于最大值 31，满足条件初始化 dataCenterId、workerId 设置为 0 返回
dataCenterId 和 workerId 的排列组合一共是 1024，在进行调配时，先调配 workerId
判断 workerId 是否 != 31，条件成立对 workerId 自增，并返回；如果 workerId = 31，自增 dataCenterId 并将 workerId 设置为 0
dataCenterId、workerId 是始终向下推动的，总体造成一个环状。通过 Lua 脚本的原子性，保障 1024 节点下的雪花算法生成不反复。如果标识位等于 1024，则从头开始持续循环推动
开源分布式 ID 框架
Leaf 和 Uid 都有实现雪花算法，Leaf 额定提供了号段模式生成 ID
美团 Leaf：https://github.com/Meituan-Dianping/Leaf
百度 Uid：https://github.com/baidu/uid-generator
雪花算法能够满足大部分场景，如无必要，不倡议引入开源计划减少零碎复杂度
最初
如果你感觉此文对你有一丁点帮忙，点个赞。或者能够退出我的开发交换群：1025263163 互相学习，咱们会有业余的技术答疑解惑
如果你感觉这篇文章对你有点用的话，麻烦请给咱们的开源我的项目点点 star: http://github.crmeb.net/u/defu 不胜感激！