分布式高并发下唯一标识算法 snowflake算法/Redis自增

￡神魔★判官ぃ 2022-05-18 08:55 188阅读 0赞

## ##

### 简介： ###

在系统小时，唯一标识的产生，可以利用公用模块来处理，比如数据库表的唯一键、或者缓存的唯一id等等方式。但在分布式高并发的系统中，如果还是这样使用公共模块，就会产生很大的风险和瓶颈。网上也有相关推荐的，twitter的snowflake就能解决这个问题。

snowflake满足了以下个要求：   
1. 只用64位就能达到要求；而无需128的方式。   
2. 考虑到排序的要求，标识的排序跟时间上基本能保持一致。   
3. 满足了预期服务时间内的，即在多少年内此算法适用。

### snowflake算法核心： ###

![这里写图片描述][SouthEast]

如图，64位。主要由3块构成：时间戳、工作机器id、序列号。   
\- 其中第一位不用，也可以理解作为正负数来使用，默认正数的。   
\- 随后41位表示时间戳，在实际使用时，可以当做时间差来使用，比如现在离2017-01-01 00:00:00的时间差。这样的话，时间范围就能达到： (2^41-1)/(1000\*60\*60\*24\*365)=69.7年。   
\- 中间10位用于工作机器的。可以用于 2^10-1=1023台机器。   
\- 最后12位表示序列号，一个机器在一个毫秒时最大能产生 2^12-1=4095个。   
\*\*在实际应用中，可能无需最大化的，比如时间戳只用30位就能达到要求的就无需41位，其他的同理。   
工作机器ID，可以是进程级别。机器级别的话，可以使用机器的mac地址或ip地址经过算法；如果是进程级别的话，可以使用path+进程标识；也可以混编，列如前5位标识机器，后5位标识进程。   
关于序列号有个注意点，如果一个毫秒内，序列号已经达到上限，就等到下一毫秒，同时序列号置零开始。\*\*

### 具体代码： ###

/**
     * @author zcl
     * @date 2017/7/12
     **/
    public class MagicSnowFlake {
    
        //其实时间戳   2017-01-01 00:00:00
        private final static long twepoch = 1483200000000l;
    
        //10bit（位）的工作机器id  中IP标识所占的位数 8bit（位）
        private final static long ipIdBits = 8L;
    
        //IP标识最大值 255  即2的8次方减一。
        private final static long ipIdMax = ~ (-1L << ipIdBits);
    
        //10bit（位）的工作机器id  中数字标识id所占的位数 2bit（位）
        private final static long dataCenterIdBits = 2L;
    
        //数字标识id最大值 3  即2的2次方减一。
        private final static long dataCenterIdMax = ~ (-1L << dataCenterIdBits);
    
        //序列在id中占的位数 12bit
        private final static long seqBits = 12L;
    
        //序列最大值 4095 即2的12次方减一。
        private final static long seqMax = ~(-1L << seqBits);
    
        // 64位的数字：首位0  随后41位表示时间戳 随后10位工作机器id（8位IP标识 + 2位数字标识） 最后12位序列号
        private final static long dataCenterIdLeftShift = seqBits;
        private final static long ipIdLeftShift = seqBits + dataCenterIdBits;
        private final static long timeLeftShift = seqBits  + dataCenterIdBits + ipIdLeftShift;
    
        //IP标识(0~255)
        private long ipId;
    
        // 数据中心ID(0~3)
        private long dataCenterId;
    
        // 毫秒内序列(0~4095)
        private long seq = 0L;
    
        // 上次生成ID的时间截
        private long lastTime = -1L;
    
        public MagicSnowFlake(long ipId, long dataCenterId) {
            if(ipId < 0 || ipId > ipIdMax) {
                System.out.println(" ---------- ipId不在正常范围内(0~"+ipIdMax +") " + ipId);
                System.exit(0);
            }
    
            if(dataCenterId < 0 || dataCenterId > dataCenterIdMax) {
                System.out.println(" ---------- dataCenterId不在正常范围内(0~"+dataCenterIdMax +") " + dataCenterId);
                System.exit(0);
            }
    
            this.ipId = ipId;
            this.dataCenterId = dataCenterId;
        }
    
        public synchronized long nextId() {
            long nowTime = System.currentTimeMillis();
    
            if(nowTime < lastTime) {
                System.out.println(" ---------- 当前时间前于上次操作时间，当前时间有误: " + nowTime);
                System.exit(0);
            }
    
            if(nowTime == lastTime) {
                seq = (seq + 1) & seqMax;
                if(seq == 0) {
                    nowTime = getNextTimeStamp();
                }
            } else {
                seq = 0L;
            }
    
            lastTime = nowTime;
    
            return ((nowTime - twepoch) << timeLeftShift)
                    | (ipId << ipIdLeftShift)
                    | (dataCenterId << dataCenterIdLeftShift)
                    | seq;
        }
    
        private long getNextTimeStamp() {
            long nowTime;
            do {
                nowTime = System.currentTimeMillis();
            } while(nowTime <= lastTime);
            return nowTime;
        }
    }
    
    ---------------------------------------------------------------
    
    /**
     * @author zcl
     * @date 2017/7/12
     **/
    public class ThreadSnowFlake extends Thread {
    
        MagicSnowFlake msf;
    
        int cnt = 0;
    
        public ThreadSnowFlake(MagicSnowFlake msf) {
            this.msf = msf;
        }
    
        public void run() {
            System.out.println();
            if(msf != null) {
                while(cnt < 10) {
                    System.out.print(Thread.currentThread().getId() + " : " + msf.nextId());
                    cnt ++;
                }
            }
        }
    }
    
    -----------------------------------------------------------------------
    /**
     * @author zcl
     * @date 2017/7/12
     **/
    public class AlgorithmMain {
    
        public static void main(String[] args) {
    
            MagicSnowFlake msf = new MagicSnowFlake(196, 2);
    
            ThreadSnowFlake t1 = new ThreadSnowFlake(msf);
            ThreadSnowFlake t2 = new ThreadSnowFlake(msf);
    
            t1.start();
            t2.start();
        }
    }

使用redis的RedisAtomicLong可以生成分布式自增的ID值。   
SequenceFactory是封装的一个工具类，利用redisTemplate生成自增ID,实现如下：

import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.data.redis.core.RedisTemplate;
    import org.springframework.data.redis.support.atomic.RedisAtomicLong;
    import org.springframework.stereotype.Service;
    
    import java.util.Date;
    import java.util.concurrent.TimeUnit;
    
    @Service
    public class SequenceFactory {
        @Autowired
        RedisTemplate<String, String> redisTemplate;
    
        /**
         * @param key
         * @param value
         * @param expireTime
         * @Title: set
         * @Description: set cache.
         */
        public void set(String key, int value, Date expireTime) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            counter.set(value);
            counter.expireAt(expireTime);
        }
    
        /**
         * @param key
         * @param value
         * @param timeout
         * @param unit
         * @Title: set
         * @Description: set cache.
         */
        public void set(String key, int value, long timeout, TimeUnit unit) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            counter.set(value);
            counter.expire(timeout, unit);
        }
    
        /**
         * @param key
         * @return
         * @Title: generate
         * @Description: Atomically increments by one the current value.
         */
        public long generate(String key) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            return counter.incrementAndGet();
        }
    
        /**
         * @param key
         * @return
         * @Title: generate
         * @Description: Atomically increments by one the current value.
         */
        public long generate(String key, Date expireTime) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            counter.expireAt(expireTime);
            return counter.incrementAndGet();
        }
    
        /**
         * @param key
         * @param increment
         * @return
         * @Title: generate
         * @Description: Atomically adds the given value to the current value.
         */
        public long generate(String key, int increment) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            return counter.addAndGet(increment);
        }
    
        /**
         * @param key
         * @param increment
         * @param expireTime
         * @return
         * @Title: generate
         * @Description: Atomically adds the given value to the current value.
         */
        public long generate(String key, int increment, Date expireTime) {
            RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
            counter.expireAt(expireTime);
            return counter.addAndGet(increment);
        }
    }

[SouthEast]: /images/20220518/520bf5110f7e4a1492c3c86edac9d4ac.png