Snowflake算法生成分布式全局唯一ID

傷城~ 2023-10-08 23:05 24阅读 0赞

### Snowflake算法 ###

全局唯一ID结构：  
![在这里插入图片描述][57886448a1df4f458575669fbe1ae147.png_pic_center]  
总长度64位，从低到高位依次划分为：

1）0~11位（共12bit）表示序列号，最大值2^12=4096，意味着在一个时间单位（例如1毫秒）内最多可以生成4096个ID；

2）12~21位（共10bit）表示机器id，最大值2^10=1024，意味着支持的最大集群规模为1024台机器。

3）22~62位（共41bit）表示时间戳，最大值2^41=2 199 023 255 552（单位：ms），意味着在这么多时间内我们可以肆意妄为地制造ID。是多久呢？一年按365天算，2^41 / 1000 / 3600 / 24 / 365 ≈ 69.7（年）。系统运行之前我们设置一个起始时间，例如“2019-2-21 00:00:00”，然后从此时开始算，差不多能用到2088年。

4） 63位（共1bit）最高位是符号位，不使用，设置为固定值“0”。

### 生成分布式全局唯一ID ###

/**
     * 全局唯一id生成器
     * global unique id generator
     */
    public interface IdGenerator<T> {
        
        T generateId();
    }

/**
     * 基于workId的全局唯一Id生成器
     */
    public abstract class BaseWorkIdIdGenerator<T> implements IdGenerator<T> {
        
     
        @Resource(name = "dbWorkIdResolver")
        private WorkIdResolver workIdResolver;
     
        protected Long getWorkId() {
        
            return workIdResolver.resolveWorkId();
        }
     
    }

import org.springframework.stereotype.Service;
     
    import java.util.Calendar;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;
     
    /**
     *
     * <p>
     * 产生long类型的唯一id，基于Twitter的snow flake算法实现，单台机器每毫秒支持2^12=4096个id
     *
     * <p>
     * 第1位为0，符号位。第2-42位表示毫秒数，共41位，当前时间毫秒-2018年02月21日的毫秒数。第43-52位表示workId，即机器id，共10位，能支持1024台机器。第53-64位表示序列号，共12位
     */
    @Service("commonIdGenerator")
    public class CommonIdGenerator extends BaseWorkIdIdGenerator<Long> {
        
     
        public static final long START_TIME_MILLIS;
     
        private static final long SEQUENCE_BITS = 12L; // 12位序列号
     
        private static final long WORKER_ID_BITS = 10L; // 10位workId号
     
        private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;
     
        private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;
     
        private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;
     
        private long sequence;
     
        private long lastTime;
     
        private Lock lock = new ReentrantLock();
     
        static {
        
            Calendar calendar = Calendar.getInstance();
            calendar.set(2018, Calendar.FEBRUARY, 21);
            calendar.set(Calendar.HOUR_OF_DAY, 0);
            calendar.set(Calendar.MINUTE, 0);
            calendar.set(Calendar.SECOND, 0);
            calendar.set(Calendar.MILLISECOND, 0);
            START_TIME_MILLIS = calendar.getTimeInMillis(); // 从2019.02.21开始
        }
     
        @Override
        public Long generateId() {
        
            // time
            long currentTime;
            // seq
            long seq;
     
            // 此处加锁也可以使用synchronized关键字，用来在多线程并发执行时保护lastTime、sequence这两个变量
            lock.lock();
            try {
        
                currentTime = System.currentTimeMillis();
     
                //时钟被回拨，直接拒绝服务
                if (currentTime < lastTime) {
        
                    throw new IllegalStateException("Clock go back, refused generator guid service.");
                }
     
                if (currentTime == lastTime) {
        
                    //如果1ms内单台机器的4096个序号用完了，等待下一毫秒
                    if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
        
                        lastTime = waitUntilNextMillis(currentTime);
                    }
                } else {
        
                    lastTime = currentTime;
                    sequence = 0;
                }
                currentTime = lastTime;
                seq = sequence;
            }finally {
        
                lock.unlock();
            }
     
            return ((currentTime - START_TIME_MILLIS) << TIMESTAMP_LEFT_SHIFT_BITS)
                    | (getWorkId() << WORKER_ID_LEFT_SHIFT_BITS) | seq;
        }
     
        private long waitUntilNextMillis(final long fromMills) {
        
            long nextMills = System.currentTimeMillis();
            while (nextMills <= fromMills) {
        
                nextMills = System.currentTimeMillis();
            }
            return nextMills;
        }
    }

[57886448a1df4f458575669fbe1ae147.png_pic_center]: https://img-blog.csdnimg.cn/57886448a1df4f458575669fbe1ae147.png#pic_center