mynotes/算法/雪花算法生成分布式ID.md

分布式主键ID生成方案

分布式主键ID的生成方案有以下几种：

• 数据库自增主键

缺点：

1. 导入旧数据时，可能会ID重复，导致导入失败
2. 分布式架构，多个Mysql实例可能会导致ID重复

• UUID

缺点：

1. 占用空间大
2. UUID一般是字符串存储，查询效率低
3. 没有排序，无法趋势递增

• 使用Redis生成ID

缺点：

1. 依赖Redis高可用

• 雪花算法 缺点：
  1. 依赖服务器时间，如果时间回调，将会导致ID重复

雪花算法原理

雪花算法是 Twitter 开源的主键生成算法 snowflake

它用64位二进制表示主键，由5部分组成：

• 最高位：0，表示正数
• 41 位 ：表示时间戳，毫秒为单位，最多表示 2^41 -1 毫秒，约69年
• 10 位 : 前5位用来表示机房ID，后5位表示服务器ID，最多表示 2^5 个机房，和 2^10 个服务器
• 最后12位：表示序列号，最多表示 2^12-1 = 4096，即每台服务器最多支持每毫秒4096次并发生成

雪花算法的优点：

1. 生成效率非常高
2. 占用空间相对较少，只用 64 位，即 Long 类型，转换成字符串长度最多19
3. 生成的主键趋势递增

雪花算法Java实现

import java.net.Inet4Address;
import java.net.UnknownHostException;
import java.util.Random;

public class SnowflakeIdGenerator {

    /**
     * 时间戳标识所占二进制位数
     */
    private static final int TIME_STAMP_BIT_LEN = 41;
    /**
     * 机房标识所占二进制位数
     */
    private static final int SERVER_ROOM_BIT_LEN = 5;
    /**
     * 服务器标识所占二进制位数
     */
    private static final int SERVER_BIT_LEN = 5;
    /**
     * 每毫秒中序列所占二进制位数
     */
    private static final int SEQ_BIT_LEN = 12;

    /**
     * 时间戳标识向左移动的位数（这里的1标识最高位）
     */
    private static final int TIME_STAMP_LEFT_BIT_LEN = 64 - 1 - TIME_STAMP_BIT_LEN;
    /**
     * 机房标识左移位数
     */
    private static final int SERVER_ROOM_LEFT_BIT_LEN = TIME_STAMP_LEFT_BIT_LEN - SERVER_ROOM_BIT_LEN;
    /**
     * 服务器标识左移位数
     */
    private static final int SERVER_LEFT_BIT_LEN = SERVER_ROOM_LEFT_BIT_LEN - SERVER_BIT_LEN;

    /**
     * 开始时间戳，此处为 2022年4月9日
     */
    private static final long START_TIME_STAMP = 1649497879948L;
    /**
     * 上次生成ID的时间戳
     */
    private static long LAST_TIME_STAMP = -1L;
    /**
     * 上一次毫秒内存序列值
     */
    private static long LAST_SEQ = 0L;

    /**
     * 获取机房标识（可以手动定义0-31之间的数）
     */
    private static final long SERVER_ROOM_ID = getServerRoomId();
    /**
     * 获取服务器标识（可以手动定义0-31之间的数）
     */
    private static final long SERVER_ID = getServerId();

    /**
     * 机房标识最大值 +1
     */
    private static final int SERVER_ROOM_MAX_NUM_1 = ~(-1 << SERVER_ROOM_BIT_LEN) + 1;
    /**
     * 服务器标识最大值 +1
     */
    private static final int SERVER_MAX_NUM_1 = ~(-1 << SERVER_BIT_LEN) + 1;
    /**
     * 毫秒内存列的最大值
     */
    private static final long SEQ_MAX_NUM = ~(-1 << SEQ_BIT_LEN);

    /**
     * 对服务器地址的哈希码取余作为服务器标识
     * TODO 根据实际环境修改该方法，该方法不能应用于开发环境，此处仅作为例子
     *
     * @return 服务器标识
     */
    private static int getServerId() {
        try {
            String hostAddress = Inet4Address.getLocalHost().getHostAddress();
            return (hostAddress.hashCode() & Integer.MAX_VALUE ) % SERVER_MAX_NUM_1;
        } catch (UnknownHostException e) {
            return new Random().nextInt(SERVER_MAX_NUM_1);
        }
    }

    /**
     * 对服务器名称的哈希码取余作为机房标识
     * TODO 根据实际环境修改该方法，该方法不能应用于开发环境，此处仅作为例子
     *
     * @return 机房标识
     */
    private static int getServerRoomId() {
        try {
            String hostName = Inet4Address.getLocalHost().getHostName();
            return (hostName.hashCode() & Integer.MAX_VALUE) % SERVER_ROOM_MAX_NUM_1;
        } catch (Exception e) {
            return new Random().nextInt(SERVER_ROOM_MAX_NUM_1);
        }
    }

    /**
     * 一直循环直到获取到下毫秒的时间戳
     *
     * @param lastMillis
     * @return 下一毫秒的时间戳
     */
    private static long nextMillis(long lastMillis) {
        long now = System.currentTimeMillis();
        while (now <= lastMillis) {
            now = System.currentTimeMillis();
        }
        return now;
    }

    /**
     * 生成唯一ID
     * 须加锁避免并发问题
     *
     * @return 返回唯一ID
     */
    public synchronized static long generateUniqueId() {
        long currentTimeStamp = System.currentTimeMillis();
        // 如果当前时间小于上一次ID生成的时间戳，说明系统时间回退过，此时因抛出异常
        if (currentTimeStamp < LAST_TIME_STAMP) {
            throw new RuntimeException(String.format("系统时间错误！ %d 毫秒内拒绝生成雪花ID", START_TIME_STAMP));
        }
        if (currentTimeStamp == LAST_TIME_STAMP) {
            LAST_SEQ = (LAST_SEQ + 1) & SEQ_MAX_NUM;
            if (LAST_SEQ == 0) {
                currentTimeStamp = nextMillis(LAST_TIME_STAMP);
            }
        } else {
            LAST_SEQ = 0;
        }
        // 上次生成ID的时间戳
        LAST_TIME_STAMP = currentTimeStamp;
        return ((currentTimeStamp - START_TIME_STAMP) << TIME_STAMP_LEFT_BIT_LEN | (SERVER_ROOM_ID << SERVER_ROOM_LEFT_BIT_LEN) | (SERVER_ID << SERVER_LEFT_BIT_LEN) | LAST_SEQ);
    }

    /**
     * 主函数测试
     *
     * @param args
     */
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int num = 100;
        for (int i = 0; i < num; i++) {
            System.out.println(generateUniqueId());
        }
        long end = System.currentTimeMillis();

        System.out.println("共生成 " + num + " 个ID，用时 " + (end - start) + " 毫秒");
    }
}