开源地址：https://gitee.com/yu120/sequence

欢迎关注个人公众号查看原文：

1 简介

        基于Twitter的Snowflake算法（俗称雪花算法）实现64位自增ID算法。为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的ID，这些ID还需要一些大致的顺序（即时序性），并且在分布式系统中不同机器产生的ID必须不同。

2 标准Snowflake算法

Twitter的Snowflake算法数据划分如下：

Snowflake算法

信息说明：

• 1位：暂没有使用，二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0

• 41位：时间戳数据区，用来记录时间戳（毫秒）

  • 41位可以表示241−1个数字，

  • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 241−1，减1是因为可表示的数值范围是从0开始算的，而不是1。

  • 也就是说41位可以表示241−1个毫秒的值，转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年

• 10位：机器数据区，用来记录工作机器id

  • 可以部署在210=1024个节点，包括 5位datacenterId 和 5位workerId

  • 5位（bit） 可以表示的最大正整数是25−1=31，即可以用0、1、2、3、….31这32个数字，来表示不同的datecenterId或workerId

• 12位：序列号数据区，用来记录同毫秒内产生的不同id

  • 12位（bit） 可以表示的最大正整数是212−1=4096，即可以用0、1、2、3、….4095这4096个数字，来表示同一机器同一时间截（毫秒)内产生的4096个ID序号

SnowFlake优势：

• 所有生成的ID都是按时间趋势递增

• 整个分布式系统内不会产生重复ID

• 每个ID中都可以解读出，该ID是在哪个数据中心的哪台工作机器上产生

• 数值型的分布式ID（替换了UUID）

• 高性能的ID生成器（超高400w/s的超高性能）

3 Java实现代码

        由于在Java中64bit的整数是Long类型，所以在Java中Snowflake算法生成的ID就是Long来存储的。以下是基于JAVA代码实现的标准Snowflake算法（https://gitee.com/yu120/sequence）：

  1/**   2 * 基于Twitter的Snowflake算法实现分布式高效有序ID生产黑科技(sequence)   3 *    4 * <br>   5 * SnowFlake的结构如下(每部分用-分开):<br>   6 * <br>   7 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>   8 * <br>   9 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>  10 * <br>  11 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)  12 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>  13 * <br>  14 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>  15 * <br>  16 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>  17 * <br>  18 * <br>  19 * 加起来刚好64位，为一个Long型。<br>  20 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。  21 *   22 * @author lry  23 */  24public class Sequence {  25  26    /** 起始时间戳，用于用当前时间戳减去这个时间戳，算出偏移量 **/  27    private final long startTime = 1519740777809L;  28  29    /** workerId占用的位数5（表示只允许workId的范围为：0-1023）**/  30    private final long workerIdBits = 5L;  31    /** dataCenterId占用的位数：5 **/  32    private final long dataCenterIdBits = 5L;  33    /** 序列号占用的位数：12（表示只允许workId的范围为：0-4095）**/  34    private final long sequenceBits = 12L;  35  36    /** workerId可以使用的最大数值：31 **/  37    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);  38    /** dataCenterId可以使用的最大数值：31 **/  39    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);  40  41    private final long workerIdShift = sequenceBits;  42    private final long dataCenterIdShift = sequenceBits + workerIdBits;  43    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;  44  45    /** 用mask防止溢出:位与运算保证计算的结果范围始终是 0-4095 **/  46    private final long sequenceMask = -1L ^ (-1L << sequenceBits);  47  48    private long workerId;  49    private long dataCenterId;  50    private long sequence = 0L;  51    private long lastTimestamp = -1L;  52    private boolean isClock = false;  53  54    /**  55     * 基于Snowflake创建分布式ID生成器  56     * <p>  57     * 注：sequence  58     *  59     * @param workerId     工作机器ID,数据范围为0~31  60     * @param dataCenterId 数据中心ID,数据范围为0~31  61     */  62    public Sequence(long workerId, long dataCenterId) {  63        if (workerId > maxWorkerId || workerId < 0) {  64            throw new IllegalArgumentException(String.format("worker Id can\'t be greater than %d or less than 0", maxWorkerId));  65        }  66        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {  67            throw new IllegalArgumentException(String.format("dataCenter Id can\'t be greater than %d or less than 0", maxDataCenterId));  68        }  69  70        this.workerId = workerId;  71        this.dataCenterId = dataCenterId;  72    }  73  74    public void setClock(boolean clock) {  75        isClock = clock;  76    }  77  78    /**  79     * 获取ID  80     *  81     * @return  82     */  83    public synchronized Long nextId() {  84        long timestamp = this.timeGen();  85  86        // 闰秒：如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常  87        if (timestamp < lastTimestamp) {  88            long offset = lastTimestamp - timestamp;  89            if (offset <= 5) {  90                try {  91                    this.wait(offset << 1);  92                    timestamp = this.timeGen();  93                    if (timestamp < lastTimestamp) {  94                        throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));  95                    }  96                } catch (Exception e) {  97                    throw new RuntimeException(e);  98                }  99            } else { 100                throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset)); 101            } 102        } 103 104        // 解决跨毫秒生成ID序列号始终为偶数的缺陷:如果是同一时间生成的，则进行毫秒内序列 105        if (lastTimestamp == timestamp) { 106            // 通过位与运算保证计算的结果范围始终是 0-4095 107            sequence = (sequence + 1) & sequenceMask; 108            if (sequence == 0) { 109                timestamp = this.tilNextMillis(lastTimestamp); 110            } 111        } else { 112            // 时间戳改变，毫秒内序列重置 113            sequence = 0L; 114        } 115 116        lastTimestamp = timestamp; 117 118        /* 119         * 1.左移运算是为了将数值移动到对应的段(41、5、5，12那段因为本来就在最右，因此不用左移) 120         * 2.然后对每个左移后的值(la、lb、lc、sequence)做位或运算，是为了把各个短的数据合并起来，合并成一个二进制数 121         * 3.最后转换成10进制，就是最终生成的id 122         */ 123        return ((timestamp - startTime) << timestampLeftShift) | 124            (dataCenterId << dataCenterIdShift) | 125            (workerId << workerIdShift) | 126            sequence; 127    } 128 129    /** 130     * 保证返回的毫秒数在参数之后(阻塞到下一个毫秒，直到获得新的时间戳) 131     * 132     * @param lastTimestamp 133     * @return 134     */ 135    private long tilNextMillis(long lastTimestamp) { 136        long timestamp = this.timeGen(); 137        while (timestamp <= lastTimestamp) { 138            timestamp = this.timeGen(); 139        } 140 141        return timestamp; 142    } 143 144    /** 145     * 获得系统当前毫秒数 146     * 147     * @return timestamp 148     */ 149    private long timeGen() { 150        if (isClock) { 151            // 解决高并发下获取时间戳的性能问题 152            return SystemClock.now(); 153        } else { 154            return System.currentTimeMillis(); 155        } 156    } 157 158} 

以下是解决大并发场景中获取时间戳的性能问题：

 1import java.sql.Timestamp;  2import java.util.concurrent.Executors;  3import java.util.concurrent.ScheduledExecutorService;  4import java.util.concurrent.ThreadFactory;  5import java.util.concurrent.TimeUnit;  6import java.util.concurrent.atomic.AtomicLong;  7  8/**  9 * 高并发场景下System.currentTimeMillis()的性能问题的优化 10 * <p><p> 11 * System.currentTimeMillis()的调用比new一个普通对象要耗时的多（具体耗时高出多少我还没测试过，有人说是100倍左右）<p> 12 * System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道<p> 13 * 后台定时更新时钟，JVM退出时，线程自动回收<p> 14 * 10亿：43410,206,210.72815533980582%<p> 15 * 1亿：4699,29,162.0344827586207%<p> 16 * 1000万：480,12,40.0%<p> 17 * 100万：50,10,5.0%<p> 18 * @author lry 19 */ 20public class SystemClock { 21 22    private final long period; 23    private final AtomicLong now; 24 25    private SystemClock(long period) { 26        this.period = period; 27        this.now = new AtomicLong(System.currentTimeMillis()); 28        scheduleClockUpdating(); 29    } 30 31    private static class InstanceHolder { 32        public static final SystemClock INSTANCE = new SystemClock(1); 33    } 34 35    private static SystemClock instance() { 36        return InstanceHolder.INSTANCE; 37    } 38 39    private void scheduleClockUpdating() { 40        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(new ThreadFactory() { 41            public Thread newThread(Runnable runnable) { 42                Thread thread = new Thread(runnable, "System Clock"); 43                thread.setDaemon(true); 44                return thread; 45            } 46        }); 47        scheduler.scheduleAtFixedRate(new Runnable() { 48            public void run() { 49                now.set(System.currentTimeMillis()); 50            } 51        }, period, period, TimeUnit.MILLISECONDS); 52    } 53 54    private long currentTimeMillis() { 55        return now.get(); 56    } 57 58    public static long now() { 59        return instance().currentTimeMillis(); 60    } 61 62    public static String nowDate() { 63        return new Timestamp(instance().currentTimeMillis()).toString(); 64    } 65 66} 

4 性能测试数据

性能测试数据结果发现，QPS>400w/s（Mac Pro 4C/8GB）

性能测试结果数据

5 缺点分析

• 强依赖机器时间，如果发生回拨会导致可能生成id重复

• 夸毫秒ID都是偶数

5.1 时间回拨

产生原因
        分布式环境，每台机器上的时钟不可能完全同步。由于机器时间不一致，需要同步各个服务器的时间而导致时间回拨的产生。

解决方案

• 在流量最低的时间段进行时间回拨，如半夜没有流量或流量很低时

• 每次批量获取一批ID（至少这批ID用完前，即可完成时间回拨）

• 调整ID存储的数据结构

• 回拨时间小于timeout时间，则通过自旋的方式进行生成

• 回拨时间大于timeout时间，则通过更换workid来生成（精度有所降低，如可从400w降低至100w，但也完全足够了）

5.2 大量偶数

产生原因
        根据上述算法可知，在同一毫秒内是通过一个自增序列号进行区分不同ID，当时间跳至下一毫秒时，自增ID就会被重置为0。因此，如果线上的交易并发量不是很大时（即都是夸毫秒产生时），生成的所有ID的尾号基本都是0，即基本都是偶数。如果直接应用该ID来做分库分表，则极有可能出现数据不均匀的情况。

解决办法

• 自增ID满值后再重置

• 重置时使用范围随机

6 Snowflake扩展

        Snowflake算法并没有什么难度，其存放的数据区总长为64位，以上的数据区划分方式是Twitter给出的标准版，而算法是通用的。因此我们可以根据自己实际的需求，来制定属于我们自己的数据区（业界改造其数据存储结构的大牛也是不少的）。其次，以上算法生成的ID中存有一定是数据信息，因此我们可以解读这个ID来做更多的事，如获取出ID生成的时间、ID生成的数据中心、ID生成的机器ID等信息。