Twitter 全局序列ID生成算法

女爷i 2022-05-17 12:23 225阅读 0赞

分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。

为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。

public class IdSeqGenerator {
        private final static long twepoch            = 1463108596098L;             //日期起始点
    
        private final long        workerId;
        private long              sequence           = 0L;
        private long              lastTimestamp      = -1L;
    
        private final static long workerIdBits       = 10L;                        //机器ID占用10bits
        private final static long sequenceBits       = 12L;                        //序列占用12bits
    
        public final static long  maxWorkerId        = -1L ^ -1L << workerIdBits;  //机器ID 最大值
    
        private final static long timestampLeftShift = sequenceBits + workerIdBits;//时间偏移位
        private final static long workerIdShift      = sequenceBits;               //机器ID偏移位
    
        public final static long  sequenceMask       = -1L ^ -1L << sequenceBits;  //序列掩码
    
        public IdSeqGenerator(final long workerId) {
            super();
            if (workerId > maxWorkerId || workerId < 0) {
                throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
            }
            LogKit.log().info(String.format("worker Id : greater than %d or less than 0", maxWorkerId));
            this.workerId = workerId;
        }
        //生成ID
        public synchronized long nextId() {
            long timestamp = this.timeGen();
            //如果是同一时间生成的，则自增
            if (this.lastTimestamp == timestamp) {
                this.sequence = (this.sequence + 1) & sequenceMask;
                if (this.sequence == 0) {
                    //生成下一个毫秒级的序列
                    timestamp = this.tilNextMillis(this.lastTimestamp);
                }
            } else {
                //如果发现是下一个时间单位，则自增序列回0，重新自增 
                this.sequence = 0;
            }
            if (timestamp < this.lastTimestamp) {
                try {
                    throw new Exception(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", this.lastTimestamp - timestamp));
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            this.lastTimestamp = timestamp;
            long nextId = ((timestamp - twepoch << timestampLeftShift)) | (this.workerId << workerIdShift) | (this.sequence);
            return nextId;
        }
    
        private long tilNextMillis(final long lastTimestamp) {
            long timestamp = this.timeGen();
            while (timestamp <= lastTimestamp) {
                timestamp = this.timeGen();
            }
            return timestamp;
        }
    
        private long timeGen() {
            return System.currentTimeMillis();
        }
    
        public static void main(String[] args) {
            Map<Long, Long> store = new ConcurrentHashMap<>();
    
            final int MAX_POOL_SIZE = 4;
            ExecutorService service = Executors.newFixedThreadPool(MAX_POOL_SIZE);
            for (int i = 0; i < MAX_POOL_SIZE; i++) {
                final int x = i;
                service.execute(() -> {
                    IdSeqGenerator seqKit = new IdSeqGenerator(x);
                    for (int j = 0; j < 100; j++) {
                        long id = seqKit.nextId();
                        if (store.containsKey(id)) {
                            System.out.println("dublicate:" + id);
                        } else {
                            store.put(id, id);
                            System.out.println(id);
                        }
                    }
    
                    System.out.println("thread" + x + " end.");
                });
            }
    
            service.shutdown();
        }
    }