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$
  • 10 位节点部分,Twitter 实现中使用前 5 位作为数据中心标识,后 5 位作为机器标识,可以部署 1024 个节点;(32*32=1024)

  • 12 位序列号部分,支持同一毫秒内同一个节点可以生成 4096 个 ID;

SnowFlake 算法生成的 ID 大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的 ID 都是唯一的。或许我们不一定都需要像上面那样使用 5 位作为数据中心标识,5 位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部 10 位作为机器标识;若数据中心不多,也可以只使用 3 位作为数据中心,7 位作为机器标识。

snowflake 生成的 ID 整体上按照时间自增排序,并且整个分布式系统内不会产生 ID 碰撞(由 datacenter 和 workerId 作区分),并且效率较高。

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 位符号位),就会发生溢出。

AXIHE / 精选教程

浏览全部教程

HTML

CSS

JS

书籍推荐