分布式ID生成

王富贵 (lmlx66.top)

为什么要用分布式 ID

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

分布式id解决方案

分类

我们所能够了解到的解决方案有以下几种

• UUID
• 数据库自增ID
• 数据库多主模式
• 号段模式
• Redis原子性自增
• 雪花算法（SnowFlake）
• 滴滴出品（TinyID）
• 百度 （Uidgenerator）
• 美团（Leaf）

事实上，实用的方案总结起来就是三种

1. 数据库自增
2. 数据库自增演变的号段模式
3. 雪花算法

雪花算法介绍(SnowFlake)

什么是雪花算法

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

特点：

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

其优点

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

雪花算法结构

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

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

雪花算法问题

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

优化雪花算法

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

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;
}

本栏目推荐文章
• 分布式限流——基于Redis的Lua脚本限流实现
• 分布式代码执行分析
• .net core分布式定时任务调度系统
• 分布式缓存的实现和使用
• 开源：Taurus.DTC 微服务分布式事务框架，支持 .Net 和 .Net Core 双系列版本
• Java中单体应用锁的局限性&分布式锁
• 一键构建分布式云原生平台
• springcloud分布式微服务
• ECharts极坐标散点图：如何展示数据分布情况
• 中间件 ZK分布式专题与Dubbo微服务入门 5-1 集群的一些基本概念

分布式分布式 事务 分布式redis 分布 分布式minio 分布式ceph 分布式 缓存 分布式 武器 事务 分布式 系统 分布式jmeter 分布式session