一 背景

在分布式系统中，如何在各个不同的服务器产生 ID 值？例如，有一个订单系统部署在 A、B 两个节点上，那么如何在这两个节点上产生各自的订单 ID，并且保证 ID 值不会冲突。

通常有三种解决方案。

• 使用数据库的自增特性（或 Oracle 中的序列），不同节点直接使用相同数据库的自增 ID 值
• 使用 UUID 算法产生 ID 值
• 使用雪花算法生成 ID 值

二 雪花算法

1 说明

SnowFlake 被称为雪花算法，它是分布式 ID 生成器。

雪花算法是由 Twitter 公布的分布式主键生成算法，它能够保证不同表的主键的不重复性，以及相同表的主键的有序性。

核心思想：

长度共 64bit（一个 long 型）。

首先是一个符号位，1 bit 标识，由于 long 基本类型在Java中是带符号的，最高位是符号位，正数是 0，负数是 1，所以 id 一般是正数，最高位是 0。

41 bit 时间截(毫秒级)，存储的是时间截的差值（当前时间截 - 开始时间截)，结果约等于69.73年。

10 bit 作为机器的ID（5个bit是数据中心，5个bit的机器ID，可以部署在1024个节点）。

12 bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID）。

2 优点

• 毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的。整体上按照时间自增排序，并且整个分布式系统内不会产生 ID 碰撞，并且效率较高。
• 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的。可以根据自身业务特性分配 bit 位，非常灵活。

3 缺点

• 依赖机器时钟，如果机器时钟回拨，会导致重复 ID 生成。
• 可能在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况(此缺点可以忽略,，一般分布式 ID 只要求趋势递增，并不会严格要求递增，90% 的需求都只要求趋势递增 )。

4 思想

当多个节点需要生成多个 ID 值时，先判断这些节点是否在同一个时刻（精确到 ms ）生成的 ID。如果不是，可以直接根据 41 位时间戳区分 ID 值；如果是在同一时刻生成的，再根据“ 10 位机器码和12 位流水号”区分。

三 源码

1 代码

package snowflake;

// 本例将 10 位机器码看成是5位 datacenterId 和 5位 workerId
public class SnowFlake {
    private long workerId;
    private long datacenterId;
    // 每毫秒生产的序列号之从0开始递增；
    private long sequence = 0L;
    /*
        1288834974657L是1970-01-01 00:00:00到2010年11月04日01:42:54所经过的毫秒数；
        因为现在二十一世纪的某一时刻减去1288834974657L的值，正好在2^41内。
        因此1288834974657L实际上就是为了让时间戳正好在2^41内而凑出来的。
        简言之，1288834974657L（即1970-01-01 00:00:00），就是在计算时间戳时用到的“起始时间”。
     */
    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private long sequenceBits = 12L;
    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);
    private long lastTimestamp = -1L;

    public SnowFlake(long datacenterId, long workerId) {
        if ((datacenterId > maxDatacenterId || datacenterId < 0)
                || (workerId > maxWorkerId || workerId < 0)) {
            throw new IllegalArgumentException("datacenterId/workerId值非法");
        }
        this.datacenterId = datacenterId;
        this.workerId = workerId;
    }

    // 通过 SnowFlake 生成 id 的核心算法
    public synchronized long nextId() {
        // 获取计算 id 时刻的时间戳
        long timestamp = System.currentTimeMillis();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("时间戳值非法");
        }
        // 如果此次生成 id 的时间戳，与上次的时间戳相同，就通过机器码和序列号区分id值（机器码已通过构造方法传入）
        if (lastTimestamp == timestamp) {
            /*
                下一条语句的作用是：通过位运算保证sequence不会超出序列号所能容纳的最大值。
                例如，本程序产生的12位sequence值依次是：1、2、3、4、...、4094、4095
                （4095是2的12次方的最大值，也是本sequence的最大值）
                那么此时如果再增加一个sequence值（即sequence + 1），下条语句就会
                使sequence恢复到0。
                即如果sequence==0，就表示sequence已满。
             */
            sequence = (sequence + 1) & sequenceMask;
            // 如果 sequence 已满，就无法再通过sequence区分id值；因此需要切换到下一个时间戳重新计算。
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 如果此次生成 id 的时间戳，与上次的时间戳不同，就已经可以根据时间戳区分id值
            sequence = 0L;
        }
        // 更新最近一次生成id的时间戳
        lastTimestamp = timestamp;
        /*
            假设此刻的值是（二进制表示）：
                41位时间戳的值是：00101011110101011101011101010101111101011
                5位datacenterId（机器码的前5位）的值是：01101
                5位workerId（机器码的后5位）的值是：11001
                sequence的值是：01001
            那么最终生成的id值，就需要：
                1.将41位时间戳左移动22位（即移动到snowflake值中时间戳应该出现的位置）；
                2.将5位datacenterId向左移动17位，并将5位workerId向左移动12位
                （即移动到snowflake值中机器码应该出现的位置）；
                3.sequence本来就在最低位，因此不需要移动。
            以下<<和|运算，实际就是将时间戳、机器码和序列号移动到snowflake中相应的位置。
         */
        return ((timestamp - twepoch) << timestampLeftShift)
                | (datacenterId << datacenterIdShift) | (workerId << workerIdShift)
                | sequence;
    }

    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        /*
            如果当前时刻的时间戳<=上一次生成id的时间戳，就重新生成当前时间。
            即确保当前时刻的时间戳，与上一次的时间戳不会重复。
         */
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

2 测试代码

package snowflake;

public class TestSnowFlake {
    // 测试1秒能够生成的 id 个数
    public static void generateIdsInOneSecond() {
        SnowFlake idWorker = new SnowFlake(1, 1);
        long start = System.currentTimeMillis();
        int i = 0;
        for (; System.currentTimeMillis() - start < 1000; i++) {
            idWorker.nextId();
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
        System.out.println("生成id个数：" + i);
    }

    public static void main(String[] args) {
        generateIdsInOneSecond();
    }
}

3 测试结果

耗时：1000
生成id个数：4078490