Snowflake 雪花算法的 JavaScript 实现
🌙
手机阅读
本文目录结构
原理
Twitter 的雪花算法 SnowFlake
SnowFlake 算法产生的 ID 是一个 64 位的整型，结构如下（每一部分用“-”符号分隔）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
1位|--------------41位时间戳-----------------------|----10位节点----|---12位序列
-
1 位标识部分，二进制中最高位为 1 的都是负数，但是我们生成的 id 一般都使用整数，所以这个最高位固定是 0；
-
41 位时间戳部分，这个是毫秒级的时间，不会存储当前的时间戳，而是时间戳的差值（当前时间 - 固定的开始时间），这样可以使产生的 ID 从更小值开始；41 位的时间戳可以使用 69 年；
- 41 位可以表示
$2^{41}-1$个数字， - 如果只用来表示正整数（计算机中正数包含 0），可以表示的数值范围是：0 至
$2^{41}-1$，减 1 是因为可表示的数值范围是从 0 开始算的，而不是 1。 - 也就是说 41 位可以表示
$2^{41}-1$个毫秒的值，转化成单位年则是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
- 41 位可以表示
-
10 位节点部分，Twitter 实现中使用前 5 位作为数据中心标识，后 5 位作为机器标识，可以部署 1024 个节点；(32*32=1024)
-
12 位序列号部分，支持同一毫秒内同一个节点可以生成 4096 个 ID；
SnowFlake 算法生成的 ID 大致上是按照时间递增的，用在分布式系统中时，需要注意数据中心标识和机器标识必须唯一，这样就能保证每个节点生成的 ID 都是唯一的。或许我们不一定都需要像上面那样使用 5 位作为数据中心标识，5 位作为机器标识，可以根据我们业务的需要，灵活分配节点部分，如：若不需要数据中心，完全可以使用全部 10 位作为机器标识；若数据中心不多，也可以只使用 3 位作为数据中心，7 位作为机器标识。
snowflake 生成的 ID 整体上按照时间自增排序，并且整个分布式系统内不会产生 ID 碰撞（由 datacenter 和 workerId 作区分），并且效率较高。
代码在npm上
https://www.npmjs.com/package/@axihe/snowflake
安装
npm install @axihe/snowflake --save
SnowFlake 算法的优点：
- 生成 ID 时不依赖于数据库，完全在内存生成，高性能高可用。
- 容量大，每秒可生成几百万 ID。
- SnowFlake 算法在同一毫秒内最多可以生成多少个全局唯一 ID 呢？同一毫秒的 ID 数量 = 1024 * 4096 = 4194304
- 所有生成的 id 按时间趋势递增，后续插入数据库的索引树的时候，性能较高。
- 整个分布式系统内不会产生重复 id（因为有 datacenterId 和 workerId 来做区分）
SnowFlake 算法的缺点：
- 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成 ID 冲突，或者 ID 乱序。
- 还有，在启动之前，如果这台机器的系统时间回拨过，那么有可能出现 ID 重复的危险。
问题？
- workId 怎么保证唯一？
- 可以通过分布式缓存来保存机器 ID 和 workId 之间的映射关系。启动的时候访问分布式缓存查询当前机器 ID 对应的 workId，如果查询不到则获取一个并保存到分布式缓存中。
- 可通过 Zookeeper 管理 workId，免去手动频繁修改集群节点，去配置机器 ID 的麻烦。
- lastTimestamp 上次生成 ID 的时间戳，这个是在内存中，系统时钟回退 + 重启后呢？无法保证
- 目前好像只能流程上控制系统时钟不回退。
- 41 位 (timestamp - this.twepoch) « this.timestampLeftShift 超过长整型怎么办？
- this.twepoch 可以设置当前开始使用系统时的时间，可以保证 69 年不超
- Javascript 无法支持》 53 位的数字怎么办？
- js Number 被表示为双精度浮点数，最大值为 Number.MAX_SAFE_INTEGER = 2^53-1
- BigInt 是 JavaScript 中的一个新的原始数字类型，可以用任意精度表示整数。即使超出 Number 的安全整数范围限制，也可以安全地存储和操作大整数。https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/BigInt
- 要创建一个 BigInt，将
n作为后缀添加到任何整数文字字面量
- BigInt 支持大数，那怎么控制这里用 64bits 长整型，左移溢出会出现问题吗？
- 这里不做处理会出现问题，BigInt 可以用任意精度表示整数
- 如何处理？暂不处理
- 此问题本质还是上面的 41 位时间差问题，69 年不超，再长就超了，需要重新设计支持，也可以做溢出提示。
- 如果想限制为仅 64 位整数，则必须始终使用强制转换 BigInt.asIntN BigInt.asUintN
- 只要我们传递 BigInt 超过 64 位整数范围的值（例如，63 位数值 + 1 位符号位），就会发生溢出。
