type
status
date
slug
summary
tags
category
icon
password
雪花算法（Snowflake）是一种分布式唯一 ID 生成算法，适用于分布式系统中生成全局唯一的、趋势递增的、64 位的长整型 ID。雪花算法的设计目标是在分布式系统中生成 ID，以取代传统的数据库自增 ID，可以保证在分布式系统中生成的每个 ID 都是唯一且有序的。

基本构成

notion image
雪花算法的 ID 结构如下：
  1. 符号位：始终为 0，表示正数。
  1. 时间戳：占 41 位，精确到毫秒级。简单计算一下2^41-1的毫秒值转换成时间为69年
  1. 数据中心 ID：占 5 位，代表数据中心的唯一标识，可以部署 32 个数据中, 简单理解为机房。
  1. 机器 ID：占 5 位，代表每个数据中心中的唯一机器标识，可以部署 32 台机器, 每个机房可以部署的机器上限
  1. 序列号：占 12 位，范围在 0~4096，同一个毫秒值生成的个数

Mybatis-plus版雪花源码

使用雪花算法生成 ID 的步骤如下：
  1. 获取当前时间戳，精确到毫秒级。
  1. 判断当前时间戳与上次生成 ID 的时间戳是否相等，如果相等，则说明在同一毫秒内生成多个 ID，需要通过自增序列号来区分。
  1. 如果当前时间戳与上次生成 ID 的时间戳不相等，说明已进入下一毫秒，则将序列号重置为 0，并更新上次生成 ID 的时间戳。
  1. 使用时间戳、数据中心 ID、机器 ID 和序列号组合生成最终的 64 位长整型 ID。

雪花的优势和问题

雪花算法具有以下优点：
  1. 高性能：ID 生成速度快，每秒可生成上千万个 ID。
  1. 唯一性：全局唯一，分布式系统中不会出现重复的 ID。
  1. 有序性：生成的 ID 是趋势递增的，方便数据索引和排序。(无法保证按机器严格有序递增不过这并不算一个问题)
  1. 不依赖数据库，完全内存生成
需要注意的是，在使用雪花算法生成 ID 时，需要保证数据中心 ID 和机器 ID 的唯一性，并且每个数据中心的机器数量不能超过 32 台。另外，雪花算法对系统的时钟要求较高，需要保证系统的时钟回拨不会造成 ID 的重复。
依赖与系统时间的一致性，如果系统时间被回调，或者改变，可能会造成id冲突或者重复。
实际中我们的机房并没有那么多，我们可以改进改算法，将10bit的机器id优化，成业务表或者和我们系统相关的业务。

SPS系统问题复盘

经过上述分析得知，在同一台机器上并不可能出现这种情况，SPS在生产中出现的问题也是2号机器和4号机器出现id冲突情况。初步判断是datacenterId和 workeId重复导致的问题。接下来直接上代码模拟这种情况

结论

因为线上部署是虚拟机部署，如果在同一个物理机中，DataCenterId必然会发生冲突，另一种DataCenterId的取值范围为32，如果超过32也会发生DataCenterId碰撞。
再考虑WorkerId，由于前者DataCenterId相同，workerId采取低16微散列计算，这样重复概率也会大大增加。
在不指定DataCenterId和WorkerId的情况下，采取默认生成的策略重复id概率还是较高
同时行内也有很多类似的部署情况如果采取默认配置很肯能出现类似情况，另外考虑上云之后的行内应用，基于k8s部署的情况，很多应用打包系统进程号可能是默认的守护进程。workerId随机性也就失去了所以也应该避免采用默认配置。

后续处置和优化

  • mybatis-plus自定义生成器指定WorkerId，DataCenterId，通过系统参数或者配置文件读取
  • 由于行内应用有集成zk，可以通过zk分配workerId