一文读懂“Snowflake（雪花）”算法

🚕 一、了解Snowflake

🛵 1.1 何为Snowflake算法

Snowflake 中文的意思为雪花，所以 Snowflake算法 常被称为 雪花算法，是 Twitter（现“X”）开源的分布式 ID 生成算法，是一种分布式主键ID生成的解决方案。

雪花算法生成后是一个 64bit 的 long 型的数值，组成部分引入了时间戳，基本保持了自增。

🚐 1.2 为何要使用雪花算法

在讲解雪花（Snowflake）算法前，让我们先思考下面的场景：

现在的服务基本是分布式、微服务形式的，而且大数据量也导致分库分表的产生，对于水平分表就需要保证表中 id 的全局唯一性。 对于 MySQL 而言，一个表中的主键 id 一般使用自增的方式，但是如果进行水平分表之后，多个表中会生成重复的 id 值。那么如何保证水平分表后的多张表中的 id 是全局唯一性的呢？

有多种方案，如：

1、数据库主键自增

可以让不同表初始化一个不同的初始值，然后按指定的步长进行自增。例如有3张拆分表，初始主键值为1，2，3，自增步长为3。

2、UUID

用 UUID 来作为主键，但是 UUID 生成的是一个无序的字符串，对于 MySQL 推荐使用增长的数值类型值作为主键来说不适合。

3、Redis

使用 Redis 的自增原子性来生成唯一 id，但是这种方式业内比较少用。

当然还有其他解决方案，不同互联网公司也有自己内部的实现方案。雪花算法是其中一个用于解决分布式 id 的高效方案，也是许多互联网公司在推荐使用的。

🥯 1.3 雪花优缺点

优点：

缺点：

依赖服务器时间，服务器时间回拨时可能会生成重复 id。

在获取时间的时候，可能会出现时间回拨的问题，什么是时间回拨问题呢？就是服务器上的时间突然倒退到之前的时间。

1. 人为原因，把系统环境的时间改了；
2. 有时候不同的机器上需要同步时间，可能不同机器之间存在误差，那么可能会出现时间回拨问题。

小小的解决方案：算法中可通过记录最后一个生成 id 时的时间戳来解决，每次生成 id 之前比较当前服务器时钟是否被回拨，避免生成重复 id。

由于时间回拨导致的生产重复的ID的问题，其实百度和美团都有自己的解决方案了，有兴趣可以去看看。

🍌 二、深入雪花

🥗 2.1 雪花算法组成

雪花结构如下图所示：

上面有说过雪花算法会生成 64bit 的 long 型的数值，而这64bit 可以分为四个组成部分：

固定值：

1bit，最高位是符号位，0 表示正，1 表示负，固定为 0，如果是 1 就是负数了。

时间戳：

41bit，存储毫秒级时间戳（41 位的长度可以使用 69 年）。

标识位（存储机器码）：

10bit，上面中的 机器id（5bit）和 服务id（5bit）统一叫作“标识位”，两个标识位组合起来最多可以支持部署 1024 个节点。

序列号：

12bit，用于表示在同一毫秒内生成的多个ID的序号。如果在同一毫秒内生成的ID超过了4096个（2的12次方），则需要等到下一毫秒再生成ID。

默认的雪花算法是 64 bit，具体的长度可以自行配置。

如果希望运行更久，增加时间戳的位数；如果需要支持更多节点部署，增加标识位长度；如果并发很高，增加序列号位数。

总结：雪花算法并不是一成不变的，可以根据系统内具体场景进行定制。

🍱 2.2 雪花算法适用场景

因为雪花算法有序自增，保障了 MySQL 中 B+ Tree 索引结构插入高性能。

所以，日常业务使用中，雪花算法更多是被应用在数据库的主键 ID 和业务关联主键。

🍧 三、分析雪花

🥯 3.1 生成 ID 重复问题

假设场景：

一个订单微服务，通过雪花算法生成 ID，共部署三个节点，标识位一致。此时有 200 并发，均匀散布三个节点，三个节点同一毫秒同一序列号下生成 ID，那么就会产生重复 ID。

通过上述假设场景，可以知道雪花算法生成 ID 冲突存在一定的前提条件：

1. 服务通过集群的方式部署，其中部分机器标识位一致；
2. 业务存在一定的并发量，没有并发量无法触发重复问题；
3. 生成 ID 的时机：同一毫秒下的序列号一致。

解决方案：如果能保证标识位不重复，那么雪花 ID 也不会重复，有三种方案：

预分配：

应用上线前，统计当前服务的节点数，人工去申请标识位。这种方案，没有代码开发量，在服务节点固定或者项目少可以使用，但是解决不了服务节点动态扩容性问题。

动态分配：

通过将标识位存放在 Redis、Zookeeper、MySQL 等中间件，在服务启动的时候去请求标识位，请求后标识位更新为下一个可用的。

统一分配ID：

启动一个专门分配ID的服务，它来统一分配各个业务或服务需要的ID。

🍷 3.2 第一位为什么不使用

在雪花算法中，第一位是符号位，0表示整数，第一位如果是1则表示负数，我们用的ID默认就是正数，所以默认就是0，那么这一位默认就没有意义。

🍬 3.3 标识位怎么用

标识位一共10 bit，如果全部表示机器，那么可以表示1024台机器，如果拆分，5 bit 表示机房，5bit表示机房里面的机器，那么可以有32个机房，每个机房可以用32台机器。

🌹 四、开源分布式 ID 框架

Leaf 和 Uid 都有实现雪花算法，Leaf 额外提供了号段模式生成 ID。

美团 Leaf：https://github.com/Meituan-Dianping/Leaf

百度 Uid：https://github.com/baidu/uid-generator

雪花算法 可以满足大部分场景，如无必要，不建议引入开源方案增加系统复杂度。

🍗 五、总结

雪花算法依赖于时间的一致性，如果发生时间回拨，可能会导致问题。为了解决这个问题，通常会使用拓展位来扩展时间戳的位数。原本雪花算法只能支持69年的时间范围，但根据实际需求，可以增加时间戳的位数来延长可使用的年限，比如使用42位可以支持139年的时间范围。然而，对于很多公司来说，首要任务是生存下来，因此可能会权衡取舍，不过度追求时间戳位数的增加。

需要注意的是，雪花算法也有一些缺点。在单机上，生成的ID是递增的，但在多台机器上，只能大致保持递增趋势，并不能严格保证递增。这是因为多台机器之间的时钟不一定完全同步。因此，在多机器环境下，对于严格的递增需求，需要考虑其他解决方案。

总而言之，雪花算法是一种常用的分布式唯一ID生成算法，但并非完美解决方案。在使用时，需要根据实际需求和限制条件进行权衡和选择，以寻找适合自己情况的解决方案。