雪花id详解

1.1 概述

分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。
它是Twitter开源的由64位整数组成分布式ID，性能较高，并且在单机上递增

1.2分布式ID的特点

• 全局唯一性

不能出现有重复的ID标识，这是基本要求。

• 递增性

确保生成ID对于用户或业务是递增的。

• 高可用性

确保任何时候都能生成正确的ID。

• 高性能性

在高并发的环境下依然表现良好

1.3 结构

• snowflake的结构如下(每部分用-分开):
  0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

• 第 1 位标识位：符号标识，由于ID一般是正数，第一位一般固定 0,第一位未使用

• 后 41 位时间戳：毫秒级，可以存储起始时间到当前时间的时间戳的差值（取值范围是0~2^41 -1），最多可以使用约 69 年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69

• 后 10 位机器位：可以部署1024个节点，包含 5 位数据中心ID（取值范围是0~31）（dataCenterId）和 5 位工作机器ID（取值范围是0~31）（workerId）

• 后 12 位序列位：毫秒内的计算。12 位的计数顺序号支持每个节点，每毫秒生成 4096 个序号

• 总 64 位：Long,转换成字符串后长度最多19

• 整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由datacenter和workerId作区分)

  SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢：
  同一毫秒的ID数量 = 1024 X 4096 = 4194304

1.4源码

public class SnowflakeHelper {
    /**
     * 时间错位数
     */
    private static final int BIT_TIMESTAMP = 41;
    /**
     * 序列位数
     */
    private static final int BIT_SEQUENCE = 12;
    /**
     * 数据中心位数
     */
    private static final int BIT_DATA_CENTER = 5;
    /**
     * 工作机器位数
     */
    private static final int BIT_WORKER = 5;
    /**
     * 总位数
     */
    private static final int BIT_SNOWFLAKE = BIT_TIMESTAMP + BIT_DATA_CENTER + BIT_WORKER + BIT_SEQUENCE;

    /**
     * 最大序列值
     */
    private static final long MAX_SEQUENCE = ~(-1L << BIT_SEQUENCE);
    /**
     * 最大数据中心值
     */
    private static final long MAX_DATA_CENTER = ~(-1L << BIT_DATA_CENTER);
    /**
     * 最大工作机器值
     */
    private static final long MAX_WORKER = ~(-1L << BIT_WORKER);

    /**
     * 时间戳左移位数
     */
    private static final long LEFT_TIMESTAMP = BIT_DATA_CENTER + BIT_WORKER + BIT_SEQUENCE;
    /**
     * 数据中心左移位数
     */
    private static final long LEFT_DATA_CENTER = BIT_WORKER + BIT_SEQUENCE;
    /**
     * 工作机器左移位数
     */
    private static final long LEFT_WORKER = BIT_SEQUENCE;

    /**
     * 雪花ID开始时间，可以从起始时间开始使用 69 年
     */
    private final long START_TIMESTAMP;
    /**
     * 数据中心ID
     */
    private final long DATA_CENTER_ID;
    /**
     * 工作机器ID
     */
    private final long WORKER_ID;
    /**
     * 上一次的时间戳
     */
    private long latestTimestamp = 0L;
    /**
     * 序列
     */
    private long sequence = 0L;

    private long leftWorker = LEFT_WORKER;

    private long leftDataCenter = LEFT_DATA_CENTER;

    private long leftTimestamp = LEFT_TIMESTAMP;

    public SnowflakeHelper(long startTimeStamp, long dataCenterId, long workerId) {
        if (dataCenterId < 0 || dataCenterId > MAX_DATA_CENTER) {
            throw new IllegalArgumentException("Data center id must in 0 ~ " + MAX_DATA_CENTER);
        }
        if (workerId < 0 || workerId > MAX_WORKER) {
            throw new IllegalArgumentException("Worker id must in 0 ~ " + MAX_WORKER);
        }
        this.START_TIMESTAMP = startTimeStamp;
        this.DATA_CENTER_ID = dataCenterId;
        this.WORKER_ID = workerId;
    }

    public SnowflakeHelper(long startTimeStamp, long dataCenterId, long workerId,
                           Integer bitTimestamp,
                           Integer bitDataCenterId,
                           Integer bitWorkerId,
                           Integer bitSequence) {
        this(startTimeStamp, dataCenterId, workerId);
        bitTimestamp = bitTimestamp != null ? bitTimestamp : BIT_TIMESTAMP;
        bitDataCenterId = bitDataCenterId != null ? bitDataCenterId : BIT_DATA_CENTER;
        bitWorkerId = bitWorkerId != null ? bitWorkerId : BIT_WORKER;
        bitSequence = bitSequence != null ? bitSequence : BIT_SEQUENCE;
        Assert.isTrue((bitTimestamp + bitDataCenterId + bitWorkerId + bitSequence) == BIT_SNOWFLAKE,
                String.format("[Snowflake] The total length of the snowflake ID must be 63 bit (timestamp %d, data center %d, worker %d, sequence %d).", bitTimestamp, bitDataCenterId, bitWorkerId, bitSequence));
        leftWorker = bitSequence;
        leftDataCenter = leftWorker + bitWorkerId;
        leftTimestamp = leftDataCenter + bitDataCenterId;
    }

    public synchronized long next() {
        long now = now();
        if (now < latestTimestamp) {
            throw new CommonException("Snowflake ID clock abnormal.");
        }
        if (now == latestTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0L) {
                now = nextTime();
            }
        } else {
            sequence = 0L;
        }
        latestTimestamp = now;
        // 时间戳位
        return (now - START_TIMESTAMP) << leftTimestamp
                // 数据中心位
                | DATA_CENTER_ID << leftDataCenter
                // 工作机器位
                | WORKER_ID << leftWorker
                // 序列位
                | sequence;
    }

    private long nextTime() {
        long now = now();
        while (now <= latestTimestamp) {
            now = now();
        }
        return now;
    }

    private long now() {
        return SystemClock.now();
    }
}

我们需要传入的参数只有 只有
workerId – 终端ID
datacenterId – 数据中心ID
Redis下这两个参数的计算方式：

import java.io.Serializable;
import java.util.LinkedHashMap;
import java.util.Map;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.apache.commons.lang3.StringUtils;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.support.atomic.RedisAtomicLong;
public class SnowflakeInitiator {
    @Data
    @Builder
    @NoArgsConstructor
    @AllArgsConstructor
    public static class SnowIdDto implements Serializable, Comparable<SnowIdDto> {
        /**
         * 注册时的时间戳
         */
        private Long timestamp;
        /**
         * 数据中心节点  0~31
         */
        private Integer dataCenterId;
        /**
         * 工作节点 0~31
         */
        private Integer workerId;
        @Override
        public int compareTo(SnowIdDto o) {
            long ex = this.timestamp - o.getTimestamp();
            return ex > 0 ? 1 : -1;
        }
    }
    private static final Integer DATA_SIZE = 32;
    private static final String[] RADIX_STR = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v"};
    private static Map<String, Integer> RADIX_MAP = new LinkedHashMap<>();
    private static final String SNOW = "RedisPrefix";
    static {
        for (int i = 0; i < DATA_SIZE; i++) {
            RADIX_MAP.put(RADIX_STR[i], i);
        }
    }
    /**
     * 计算雪花算法参数的新算法
     *
     * @param redisTemplate
     * @param appName
     * @return
     */
    private SnowIdDto calculateDataIdAndWorkId(RedisTemplate redisTemplate, String appName) {
        String key = SNOW + appName;
        RedisAtomicLong redisAtomicLong = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        long andIncrement = redisAtomicLong.getAndIncrement();
        long result = andIncrement % (DATA_SIZE * DATA_SIZE);
        String str = StringUtils.leftPad(Integer.toString(Math.toIntExact(result), DATA_SIZE), 2, "0");
        Integer dataId = RADIX_MAP.get(str.substring(0, 1));
        Integer workId = RADIX_MAP.get(str.substring(1, 2));
        return new SnowIdDto(System.currentTimeMillis(), dataId, workId);
    }
}

运算方式：

1.5 通用Mapper中如何集成雪花Id?

对于Mybatis来说，他提供自定义的生成主键的策略，提供了一个抽象的接口

我们需要实现这个接口并且在Mybatis的拦截器里面调用他，去生产雪花Id
首先是一个mybatis的拦截器

在拦截器中处理主键的id

接着下一步
如果是Insert的语句我们有一个before的处理：

![在这里插入图片描述](https://img-blog.csdnimg.cn/5bfcfb28364b4ace9923ccf9d7538bdb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5pe256m65oGL5peF5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16hzero 提供了两种，mybatis也有默认的实现
![在这里插入图片描述](https://img-blog.csdnimg.cn/a5d768e4840f49f685ea53617bf8ae3f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5pe256m65oGL5peF5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16然后我们进入雪花Id的Id生成器里面

批量和非批量的都调用generateKey方法

然后就会生成这个id

自己写的MyBatis InsertSQLb并不会出现用到雪花Id,如果想要实现参考：https://blog.csdn.net/dai909237869/article/details/111176110

1.6 SnowFlake算法的缺点：

• 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序。
• 还有，在启动之前，如果这台机器的系统时间回拨过，那么有可能出现ID重复的危险。

1.7问题？

workId 怎么保证唯一？

1. 可以通过分布式缓存来保存机器ID和workId之间的映射关系。启动的时候访问分布式缓存查询当前机器ID对应的workId，如果查询不到则获取一个并保存到分布式缓存中。
   2.可通过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 的安全整数范围限制，也可以安全地存储和操作大整数。
要创建一个 BigInt，将 n 作为后缀添加到任何整数文字字面量

BigInt 支持大数，那怎么控制这里用 64bits 长整型，左移溢出会出现问题吗？

这里不做处理会出现问题，BigInt 可以用任意精度表示整数
如何处理？暂不处理
此问题本质还是上面的41位时间差问题，69年不超，再长就超了，需要重新设计支持，也可以做溢出提示。
如果想限制为仅64位整数，则必须始终使用强制转换 BigInt.asIntN BigInt.asUintN
只要我们传递 BigInt 超过 64 位整数范围的值（例如，63 位数值 + 1 位符号位），就会发生溢出。

时钟回拨问题和解决方案讨论

首先看看时钟为什么会发生回拨？机器本地时钟可能会因为各种原因发生不准的情况，网络中提供了NTP服务来做时间校准，做校准的时候就会发生时钟的跳跃或者回拨的问题。

因为雪花算法强依赖机器时钟，所以难以避免受到时钟回拨的影响，有可能产生ID重复。原标准实现代码中是直接抛异常，短暂停止对外服务，这样在实际生产中是无法忍受的。所以要尽量避免时钟回拨带来的影响，解决思路有两个：

不依赖机器时钟驱动，就没时钟回拨的事儿了。即定义一个初始时间戳，在初始时间戳上自增，不跟随机器时钟增加。时间戳何时自增？当序列号增加到最大时，此时时间戳+1，这样完全不会浪费序列号，适合流量较大的场景，如果流量较小，可能出现时间断层滞后。
依然依赖机器时钟，如果时钟回拨范围较小，如几十毫秒，可以等到时间回到正常；如果流量不大，前几百毫秒或者几秒的序列号肯定有剩余，可以将前几百毫秒或者几秒的序列号缓存起来，如果发生时钟回拨，就从缓存中获取序列号自增。

参考链接：
https://github.com/cloudyan/snowflake