雪花算法

(adsbygoogle = window.adsbygoogle || []).push({});

简介

雪花算法的原理就是生成一个的 64 位比特位的 long 类型的唯一 id。 1：最高 1 位是符号位，固定值 0，表示id 是正整数 41：接下来 41 位存储毫秒级时间戳，2^41/(1000606024365)=69，大概可以使用 69 年。 10：再接下 10 位存储机器码，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台机器。 12：最后 12 位存储序列号。同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。 2^63=9,223,372,036,854,775,808 十进制下就是19位数

具体实现

常用的有mybatis-plus的，hutool等，主要介绍下mp的

mp默认的

com.baomidou.mybatisplus.core.toolkit.Sequence

/**
  * 数据标识id部分
  */
protected long getDatacenterId(long maxDatacenterId) {
    long id = 0L;
    try {
        if (null == this.inetAddress) {
            if (logger.isDebugEnabled()) {
                logger.debug("Use localhost address ");
            }
            this.inetAddress = InetAddress.getLocalHost();
        }
        if (logger.isDebugEnabled()) {
            logger.debug("Get " + inetAddress + " network interface ");
        }
        NetworkInterface network = NetworkInterface.getByInetAddress(this.inetAddress);
        if (logger.isDebugEnabled()) {
            logger.debug("Get network interface info: " + network);
        }
        if (null == network) {
            logger.warn("Unable to get network interface for " + inetAddress);
            id = 1L;
        } else {
            byte[] mac = network.getHardwareAddress();
            if (null != mac) {
                id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
                id = id % (maxDatacenterId + 1);
            }
        }
    } catch (Exception e) {
        logger.warn(" getDatacenterId: " + e.getMessage());
    }
    return id;
}


/**
 * 获取 maxWorkerId
 */
protected long getMaxWorkerId(long datacenterId, long maxWorkerId) {
    StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    String name = ManagementFactory.getRuntimeMXBean().getName();
    if (StringUtils.isNotBlank(name)) {
        /*
          * GET jvmPid
          */
        mpid.append(name.split(StringPool.AT)[0]);
    }
    /*
      * MAC + PID 的 hashcode 获取16个低位
      */
    return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}

/**
 * 获取下一个 ID
 *
 * @return 下一个 ID
 */
public synchronized long nextId() {
    long timestamp = timeGen();
    //闰秒
    if (timestamp < lastTimestamp) {
        long offset = lastTimestamp - timestamp;
        if (offset <= 5) {
            try {
                wait(offset << 1);
                timestamp = timeGen();
                if (timestamp < lastTimestamp) {
                    throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
                }
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        } else {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
        }
    }

    if (lastTimestamp == timestamp) {
        // 相同毫秒内，序列号自增
        sequence = (sequence + 1) & sequenceMask;
        if (sequence == 0) {
            // 同一毫秒的序列数已经达到最大
            timestamp = tilNextMillis(lastTimestamp);
        }
    } else {
        // 不同毫秒内，序列号置为 1 - 2 随机数
        sequence = ThreadLocalRandom.current().nextLong(1, 3);
    }

    lastTimestamp = timestamp;

    // 时间戳部分 | 数据中心部分 | 机器标识部分 | 序列号部分
    return ((timestamp - twepoch) << timestampLeftShift)
        | (datacenterId << datacenterIdShift)
        | (workerId << workerIdShift)
        | sequence;
}

问题

前端接收丢失末尾两位

现象： 1810559288063254529前端接收的为1810559288063254500 原因： 前端Number的最大整数是2 ** 53 -1 解决方案：

1. 改为string类型和前端传输
2. 并发量少的情况可以减少最后序列号的位数
3. 可以通过添加拦截器统一修改

参考： https://segmentfault.com/q/1010000038232026 https://blog.csdn.net/qq_42672839/article/details/130562170

重复ID，改进版(版本 >= 3.4.0)

k8s集群下,进程号pid为1导致生成重复ID的可能性大大增 具体示例

MAC地址	后两个转二进制	右移6位	十进制	对32取余
06:d0:6f:1f:96:f8	1001 0110 1111 1000	1001 0110 11	603	27
8e:a5:66:95:e6:c5	1110 0110 1100 0101	1110 0110 11	923	27

验证代码

package me.panxin.snowflake;

public class DatecenterId {

    public static final long generate(String macAddress) {
        long id = 0;
        String[] split = macAddress.split(":");
        byte[] mac = new byte[6];
        for (int i = 0; i < split.length; i++) {
            mac[i] = (byte) Integer.parseInt(split[i], 16);
        }
        if (null != mac) {
            id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
            id = id % (32);
        }
        return id;
    }
}

package me.panxin.snowflake;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DatacenterIdTest {

    @Test
    public void testDatacenterId() {
        List<String> list = Arrays.asList(
                "82:11:F3:FC:7B:7F",
                "AA:D7:3C:04:49:EE",
                "86:38:F4:94:AE:60",
                "5A:18:2C:B5:7D:E7",
                "AE:03:49:4F:B3:DF",
                "1E:EC:62:6C:91:2A",
                "A2:C4:DE:C4:27:F0",
                "36:6D:53:FF:6A:13"
        );
        for (String macAddress : list) {
            long id = DatecenterId.generate(macAddress);
            System.out.println(id);
        }
        /**
         * 输出结果
         * 29
         * 25
         * 2
         * 29
         * 30
         * 10
         * 0
         * 13
         */
    }

}

主要是pid相同，导致有一定概率中间的10位机器码相同 com.baomidou.mybatisplus.core.incrementer.ImadcnIdentifierGenerator 个人理解用redis生成中间10位置机器码应该也可以解决这个问题。

参考

https://github.com/baomidou/mybatis-plus/pull/6247 https://github.com/baomidou/mybatis-plus/issues/6177 https://blog.csdn.net/w1014074794/article/details/125607205