分布式系统应用中生成全局唯一ID的算法（snowflake)----java 实现，单例模式

概述

在分布式系统中，有很多的地方需要生成全局id的场景，比方说，订单模块，用户id等。这种情况下大多数的做法是通过UUID来做处理。首先，UUID是36位的一个字符串，相对来说是比较长的，一般我们采用的数据库会是MySQL，因为大多数的情况下，我们都希望我们的数据是可以回滚的，那么我们的数据表会采用innoDB，innoDB采用B+Tree实现其索引结构。所以一般对主键有以下的要求！

• 越短越好——越短在一个Page中存储的节点越多，检索速度就越快。
• 顺序增长——如果每一条插入的数据的主键都比前面的主键大，那么B-Tree上的节点也是顺序增长的，不会造成频繁的B-Tree分割。

越短越好是为了查询的速度快，顺序增长是为了插入速度快，所以UUID就感觉不是太优秀。

并且在后期数据量非常大的时候，我们采用分库分表的情况下，可以更好的横向扩展！

结构

snowflake的结构如下(每部分用-分开):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）

一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID。

源码网上多的是，但是经过我的小范围测试，如果实例太多的话，单个系统就会出现重复的情况。如果采用spring来管理的话，应该来说是没有问题的，但是为了严谨期间，我把源码改造成一个单例模式的类。这样，不管怎么调用，单个系统生成的id永远不会重复！

package main.java;

/**
 * 生成分布式系统唯一的主键id
 * string类型
 * Snowflake 的结构如下
 * 0-00000000 00000000 00000000 00000000 00000000 00000000 - 00000 - 0000 -000000000000
 * 第一位是符号为，41位表示当前时间戳跟定义好的时间戳的差值，5位
 * 41位的表示(1L << 41) / (1000L * 3600 * 24 * 365L) == 69年;
 * 指定10位的机器位，可以部署1024台机器
 * 所有的数据加起来就是64位，正好是一个Long型数据
 */
public class SnowflakeIdWorker {
    /**
     * 开始时间戳
     */
    private final long startTime = 1420041600000L;
    /**
     * 机器id所占的位数
     */
    private final long workIdBits = 5L;
    /**
     * 数据id所占的位数
     */
    private final long dataIdBits = 5L;
    /**
     * 二进制中，负数采用其绝对值的值得补码得到
     * long型的-1 的值就32个1
     */
    private final long maxWorkerId = -1L ^ (-1L << workIdBits);
    /**
     * 同上
     */
    private final long maxDataGenID = -1L ^ (-1L << dataIdBits);
    /**
     * 12位的序列，表示1个毫秒内可生成 2的12次幂个数据，即4096个数据
     */
    private final long sequenceBits = 12L;
    /**
     * 数据id存放的位置应该是向左移动12位序列值和机器码
     */
    private final long dataShiftBits = sequenceBits + workIdBits;
    /**
     * 时间戳存放的位置应该是从22位开始的，左移22位
     */
    private final long timestampLeftShift = dataShiftBits + dataIdBits;
    /**
     * 4095 生成序列的最大值
     */
    private final long maxSequence = -1 ^ (-1 << sequenceBits);
    /**
     * 机器码id 小于31
     */
    private long worderId;
    /**
     * 数据中心id 小于31
     */
    private long dataId;
    /**
     * 毫秒内计数(0-4095)
     */
    private long sequence = 0L;
    /**
     * 上一次生成id的时间戳
     */
    private long lastTimeStamp = -1L;

    /**
     * 单例模式构造方法
     */
    private SnowflakeIdWorker() {
    }

    /**
     * 使用静态内部类实现单例
     */
    private static class SnowflakeIdWorkerInstance {
        private static SnowflakeIdWorker INSTANCE = new SnowflakeIdWorker();
    }

    public static SnowflakeIdWorker getInstance() {
        return SnowflakeIdWorkerInstance.INSTANCE;
    }

    /**
     * 初始化并配置机器码id和数据id
     *
     * @param workerId 0-31
     * @param dataId   0-31
     */
    public void init(long workerId, long dataId) {
        if (workerId > maxWorkerId || worderId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't greater than %d or less than 0", maxWorkerId));
        }
        if (dataId > maxDataGenID || dataId < 0) {
            throw new IllegalArgumentException(String.format("data Id can't greater than %d or less than 0", maxDataGenID));
        }
        this.worderId = workerId;
        this.dataId = dataId;
    }

    /**
     * 生成主键id，理论上应该在调用了init方法之后，调用生成的方式是有效的
     * 不然所有的id都默认是按照机器码和数据id都是0的情况处理
     *
     * @return 8个字节的长整型
     */
    public synchronized long genNextId() {
        long timeStamp = genTimeStamp();
        /**表示系统的时间修改了*/
        if (timeStamp < this.lastTimeStamp) {
            throw new RuntimeException(String.format("System clock moved;currentTimeStamp %d,lastTimeStamp = %d", timeStamp, this.lastTimeStamp));
        }
        if (timeStamp == this.lastTimeStamp) {
            /**查看序列是否溢出*/
            this.sequence = (this.sequence + 1) & maxSequence;
            if (this.sequence == 0) {
                /**当出现溢出的时候，阻塞到下一个毫秒*/
                timeStamp = this.toNextMillis(this.lastTimeStamp);
            }
        } else {  /**此时表示时间戳跟最后的时间戳不一致,需要重置序列*/
            this.sequence = 0L;
        }
        this.lastTimeStamp = timeStamp;
        //通过移位或运算拼接组成64ID号
        return ((timeStamp - startTime) << timestampLeftShift)
                | (dataId << dataShiftBits)
                | (worderId << sequenceBits)
                | sequence;
    }

    /**
     * 生成当前时间戳，单独写一个方法的原因是，若之后的时候修改扩展，不影响之前的业务，
     * 只在这个方法里面处理我们需要的数据
     *
     * @return
     */
    private long genTimeStamp() {
        return System.currentTimeMillis();
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimeStamp 上传生成id的时间戳
     * @return
     */
    private long toNextMillis(long lastTimeStamp) {
        long timeStamp = this.genTimeStamp();
        while (timeStamp <= lastTimeStamp) {
            timeStamp = this.genTimeStamp();
        }
        return timeStamp;
    }

    //--------------------------test--------------------------------------
    public static void main(String[] args) {
        SnowflakeIdWorker worker = SnowflakeIdWorker.getInstance();
        /**第一次使用的时候希望初始化*/
        worker.init(30, 14);
        for (int i = 0; i < 10000; i++) {
            long workerId = worker.genNextId();
            System.out.println(workerId);
            System.out.println(Long.toBinaryString(workerId));
        }
    }

}

下面是测试的结果，红框表示阻塞的情况！

参考链接

GitHub

结语：夜已深，休息啦，以后再有新的点子了跟大家分享！