欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

增强版雪花算法-防重复

程序员文章站 2022-07-12 17:13:27
...

一、介绍

简单介绍下雪花算法:核心思想就是使用一个64位bit的long型数字作为全局id;那么这个64位的bit由如下几部分组成

第一部分:1bit;0,表示为正数

第二部分:41bit,时间戳

第三部分:10bit(如果是多机房可以拆分成两部分,即机房部分+机器部分),机器的唯一标识

第四部分:12bit,表示的序号,就是某个机房某台机器上这一毫秒内同时生成的 id 的序号

 

由以上的组成部分 我们可以直观看出 集群模式下只要保证第三部分唯一,就可以保证集群模式下不会出现重复的id;

 

我们可以借助于数据库,即每次项目启动时,初始化雪花算法的第三部分(机器唯一标识),去数据库里取当前自增id,拿取道的自增id % 2^10(第三部分长度为10bit),这样做的目的是为了自增id超过2^10仍然可以使用;

 

二、上代码

/**
 * ID 生成器
 * <p>
 * 整个ID算法很简单,
 * 1. 参考Flickr ID生成算法, 使用MYSQL获得一个自增ID, 然后对ID取模, 算出一个服务器ID
 * 2. 参考Twitter的雪花算法, 算出一个long型ID
 * <p>
 * 该算法保证在30年内, 6万台机器, 单机每秒可以产出128, 000个不重复ID
 * <p>
 * |1, 000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0 |000, 0000, 0000, 0000, 0 |000, 0000           |
 * | |                   时间戳(40位)                                |   服务器ID(16位)         | 单个时间戳内的Id(7位) |
 */
@Service
public class IDGeneratorService implements CommandLineRunner {

    private static final Logger LOG = LoggerFactory.getLogger(IDGeneratorService.class);

    // 时间戳从哪一年开始计时
    private static final int START_YEAR = 2020;

    // 时间取40位
    private static final int timeBitsSize = 40;
    private static final int serverIdBitsSize = 16;
    private static final int countBitsSize = 7;

    private long maxIdPerMill;

    // 时间开始时间戳, 相当于System.currentTimeMillis()的1970年
    private long startDateTime;
    // 服务器ID表示位, 在集群中表示一个节点
    private long serverIdBits;
    // 单机中, 某个时刻生长得id
    private long currentID;

    private long maxTime;

    private long lastGenerateTime = System.currentTimeMillis();
    private Object lock = new Object();

    @Resource
    private PLServiceIdMapper plServiceIdMapper;

    public void init() {
        // 1. 计算出开始生成ID的起始时间戳
        LocalDateTime start = LocalDateTime.of(START_YEAR, 1, 1, 0, 0);
        startDateTime = start.toInstant(ZoneOffset.of("+8")).toEpochMilli();

        // 2. 算出支持最大年限的时间
        maxTime = ((Double) Math.pow(2, timeBitsSize)).longValue();

        // 3. 算出每毫秒能产出多少ID
        maxIdPerMill = ((Double) Math.pow(2, countBitsSize)).longValue();

        /**
         * 4. 根据Mysql自增ID取模, 算出每个服务器ID, 在生产环境中, 应该保证服务器数量是该值的一半, 如此一来就可以避免, 服务器集群整体
         * 重启时, 不会拿到与重启之前的服务器相同的Id
         * 这个值的计算是为了适应这种场景, 在服务器灰度上线的时候, 有可能是原来的服务器还没有关闭, 但是新的服务器已经起来了, 此时会有俩套
         * 服务器同时在处理业务逻辑, 那么它们就有可能拿到一样的服务器ID, 从而导致产生一样的ID号
         */
        long serverSize = ((Double) Math.pow(2, serverIdBitsSize)).longValue();

        DBManager.select(DataSourceTypes.MASTER_PL_FINANCE);
        PLServiceId plServiceId = new PLServiceId();
        plServiceIdMapper.nextId(plServiceId);
        long serverId = (int) (plServiceId.getId() % serverSize);
        DBManager.remove();

        /**
         * 5. 算出每个服务器ID在long类型中的数据位置, 然后缓存起来
         */
        serverIdBits = (serverId << (countBitsSize));

        LOG.info("[ID生成器] 开始时间:{}, 时间戳:{} ", new Date(startDateTime), startDateTime);
        LOG.info("[ID生成器] 结束时间:{}, 时间戳:{} ", new Date(startDateTime + maxTime), maxTime);
        LOG.info("[ID生成器] 每毫秒生成最大ID数:{} ", maxIdPerMill);
        LOG.info("[ID生成器] 当前serverId: {}, serverIdSize:{}", serverId, serverSize);
        LOG.info("[ID生成器] serverIdBits: {}", Long.toBinaryString(serverIdBits));
    }

    /**
     * 生成一个64位的GUID
     * <p>
     * 在next()方法中, 没有使用任何的对象, 如此一来就可以减轻GC的压力.
     */
    public long next() {

        synchronized (lock) {
            long curTime = System.currentTimeMillis() - startDateTime;
            if (curTime >= maxTime) {
               LOG.error("[ID生成器] 超过负载, {}, {}!返回 -1", curTime, maxTime);
                throw new RuntimeException("[ID生成器] 超过负载");
            }

            if (lastGenerateTime != curTime) {
                currentID = 0;
            } else {

                if (currentID >= maxIdPerMill) {
                   LOG.error("[ID生成器] 同一毫秒[" + curTime + "]内生成" + currentID + "个ID!返回 -1");
                    return -1;
                }

                ++currentID;
            }

            lastGenerateTime = curTime;
            long gid = (curTime << countBitsSize + serverIdBitsSize) | serverIdBits;
            gid |= currentID;

            return gid;
        }
    }

    public long tryNextId() {
        for (int i = 0; i < 1000; i++) {

            long start = System.currentTimeMillis();
            long id = next();
            long diff = System.currentTimeMillis() - start;
            if (diff > 3) {
                String tid = Thread.currentThread().getName();
                LOG.warn("[ID生成器] 线程{} 生成ID: {} 大于3毫秒: {}", tid, id, diff);
            }

            if (id == -1) {
                try {
                    TimeUnit.MILLISECONDS.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                continue;
            }
            return id;
        }
        return -1;
    }

    public String tryNextStrId() {
        return String.valueOf(tryNextId());
    }

    public String nextStrId() {
        return String.valueOf(next());
    }


    @Override
    public void run(String... args) throws Exception {
        init();
    }

}

 

数据库部分:

@Repository
public interface PLServiceIdMapper extends BaseMapper<PLServiceId> {

    @Insert("REPLACE INTO pl_server_id (stub) VALUES ('a');")
    @SelectKey(statement = "SELECT LAST_INSERT_ID()", keyProperty = "id", before = false, resultType = Long.class)
    Long nextId(PLServiceId plServiceId);

}

 

表:

create table pl_server_id
(
    id   bigint unsigned auto_increment primary key,
    stub char null,
    constraint stub
        unique (stub)
);