分布式ID生成

为什么要用分布式 ID

随着业务数据量的增长，存储在数据库中的数据越来越多，当索引占用的空间超出可用内存大小后，就会通过磁盘索引来查找数据，这样就会极大的降低数据查询速度。如何解决这样的问题呢？一般我们首先通过分库分表来解决，分库分表后就无法使用数据库自增 ID 来作为数据的唯一编号，那么就需要使用分布式 ID 来做唯一编号了。

分布式id解决方案

雪花算法介绍(SnowFlake)

什么是雪花算法

雪花算法是Twitter公司发明的一种算法，主要目的是解决在分布式环境下，ID怎样生成的问题

特点：

分布式情况下多机器生成id不重复（id不能重复）
long类型单调自增（单调递增的整形便于索引）
高并发（并发的情况下也能够使用）
id不连续（如果连续，容易被计算出数量，比如用户数量）

其优点

经测试snowflake每秒能生成26万个自增可排序的ID
snowflake生成的ID结果是一个64bit大小的整数，为一个Long型（转换成字符串后长度最多19）
分布式系统内不会产生ID碰撞（datacenter和workerId作区分）并且效率高
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也非常高，可以根据自身业务分配bit位，非常灵活

雪花算法结构

第一个部分，是1个bit：0，这个是无意义的
- 因为二进制里第一个bit为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个bit统一都是0
第二个部分是 41 个 bit：表示的是时间戳
- 41 bit 可以表示的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间
第三个部分是10个bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。
- 但是 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），也可以根据自己公司的实际情况确定。
第五个部分是 12 个 bit：这个是用来记录同一个毫秒内产生的不同id
- 12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id

为了保证id的唯一性，我们是通过第二个部分的时间戳来保证了。那么这一部分的时间戳为当前的时间减去我们设置的时间的差值。比如说我设置起始时间为2022年1月1日，那么使用当前时间减去2022年1月1日时间戳，来保证每个毫秒生成的id唯一。但是这里会出现一个问题，那就是如果我动了设置的其实时间，那么时间差值就会发送改变，而可能造成生成id重复。这就是传统雪花算法所没有解决的问题，时间回拨

雪花算法问题

生成的ID太长。
- 主键值太长，超过前端 js Number 类型最大值，须把 Long 型转换为 String 型
瞬时并发量不够。
不能解决时间回拨问题。
不支持后补生成前序ID（时间回拨问题）。
可能依赖外部存储系统。

优化雪花算法

事实上，传统的雪花算法是有一些缺点的，那么我们可以优化传统雪花算法的缺点么？

1、SnowFlake IdGenerator雪花算法

2、seata优化在开源项目中看到一个改良版的雪花算法，现在它是你的了。 - 知乎 (zhihu.com)

实现seata概念版雪花算法，主要改良的核心

package corecode.core;

import properties.IdGeneratorOptions;

import java.net.NetworkInterface;
import java.net.SocketException;
import java.util.Enumeration;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 雪花
 *
 * @author zl
 * @date 2024/01/01
 */
public class SnowFlake {
    /**
     * 起始时间戳
     */
    protected final long StartStamp;
    /**
     * 时间戳
     */
    protected AtomicLong TimeStamp;
    /**
     * 节点ID
     */
    protected final  long WordId;
    /**
     * 节点ID长度
     */
    protected final byte WordIdBitLength;
    /**
     * 序列号长度
     */
    protected final byte SeqBitLength;
    /**
     * 节点ID最大值
     */
    protected final long MaxWordIdNum;
    /**
     * 序列号最大值
     */
    protected final long MaxSeqBitNum;
    protected final byte TimeStampLength=41;
    // 每部分向左的位移
    protected final  long WordIdLeft;
    protected final long TimeStampLeft;
    public SnowFlake(IdGeneratorOptions options){
        StartStamp= options.StartStamp<=0L?options.StartStamp:1704038400000L;
        WordIdBitLength=options.WordIdBitLength<=0?10:options.WordIdBitLength;
        WordId=options.WordId==-1?initWorkId(WordIdBitLength): options.WordId;
        SeqBitLength=options.SeqBitLength<=0?12:options.SeqBitLength;
        MaxWordIdNum=-1L ^ (-1L << WordIdBitLength);
        MaxSeqBitNum=-1L^(-1L<<SeqBitLength);
        TimeStampLeft=SeqBitLength;
        WordIdLeft=TimeStampLength+SeqBitLength;
        iniTimeStamp();
    }

    /**
     * INI 时间 Stamp
     *
     * @return long
     */
    private void iniTimeStamp() {
        long currentTimeStamp=System.currentTimeMillis()-StartStamp;
        long newTimeStamp = currentTimeStamp << SeqBitLength;
        TimeStamp = new AtomicLong(newTimeStamp);
    }

    /**
     * 初始化工作 ID
     *
     * @param wordIdBitLength 字 ID 位长度
     * @return short
     */
    private long initWorkId(byte wordIdBitLength) {
        //根据seata现在的方案是获取Mac值
         try{
             return generateWordIdByMac(wordIdBitLength);
         }catch (Exception e){
             return generateRandomWordId(wordIdBitLength);
         }
    }

    /**
     * 生成随机词ID
     *
     * @param wordIdBitLength 字 ID 位长度
     * @return short
     */
    private synchronized long generateRandomWordId(byte wordIdBitLength) {
        return  ThreadLocalRandom.current().nextLong(1<<wordIdBitLength);
    }

    /**
     * 通过 Mac 生成 Word ID
     *
     * @param wordIdBitLength 字 ID 位长度
     * @return short
     */
    private long generateWordIdByMac(byte wordIdBitLength) throws SocketException {
        Enumeration<NetworkInterface> network = NetworkInterface.getNetworkInterfaces();
        while(network.hasMoreElements()){
            NetworkInterface networkInterface = network.nextElement();
            boolean isLoopback = networkInterface.isLoopback();
            boolean isVirtual = networkInterface.isVirtual();
            if(isLoopback||isVirtual){
                continue;
            }
            byte[] mac = networkInterface.getHardwareAddress();
            return ((mac[4] & 0B11) << 8) | (mac[5] & 0xFF)&MaxWordIdNum;
        }
        throw new RuntimeException("没有发现可用的mac");
    }


    public long nextId(){
        long next = TimeStamp.incrementAndGet();
        return WordId<<WordIdLeft|next;
    }
}

package properties;

import io.swagger.annotations.ApiModel;
import io.swagger.annotations.ApiModelProperty;
import lombok.Data;


/**
 * @author: 王富贵
 * @description: 雪花算法配置参数
 * @createTime: 2022年05月19日 11:19:59
 * 雪花算法使用的参数
 * 参数说明，参考 README.md 的 “配置参数” 章节。
 */
@Data
@ApiModel("雪花算法配置信息实体")
public class IdGeneratorOptions {
    /**
     * 起始时间戳
     */
    @ApiModelProperty(value = "起始时间戳",notes = "默认为2024-01-01 00:00:00，不能超过当前系统时间")
    public  long StartStamp=1704038400000L;
    /**
     * 节点ID
     */
    @ApiModelProperty(value = "机器码", notes = "该实例机器码，必须唯一，必须由外部设定，最大值 2^WorkerIdBitLength-1")
    public long WordId=-1;
    /**
     * 节点ID长度
     */
    @ApiModelProperty(value = "机器码位长", notes = "决定项目集群能使用id最大机器数， 默认值10，取值范围 [1, 10]（要求：序列数位长+机器码位长不超过22）")
    public byte WordIdBitLength=6;
    /**
     * 序列号长度
     */
    @ApiModelProperty(value = "序列号长度", notes = "决定项目集群能使用id最大机器数， 默认值12，取值范围 [1, 15]（要求：序列数位长+机器码位长不超过22）")
    public  byte SeqBitLength=6;
}

标签：雪花,生成,算法,protected,bit,id,ID,分布式
From： https://www.cnblogs.com/wzl66/p/17939463