Snowflake根据设备生成15位ID

Snowflake

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。

其核心思想是，生成64位即一个long类型的递增序列Id，保障有序及不重复，具体如下：

• 使用41bit作为毫秒数，
• 10bit作为机器的ID，5个bit是数据中心，5个bit的机器ID
• 12bit作为毫秒内的流水号，意味着每个节点在每毫秒可以产生 4096个ID
• 最后还有一个符号位，永远是0

规则

64位=符号位（1bit）+ 时间戳相对值（41bit）+ 数据标志（5bit）+ 机器标志（5bit）+ 递增序号（12bit）

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

Id位数长度

正数Long类型长度为最多19位,因此结果长度在1到19位之间,最小是0,最大9,223,372,036,854,775,807。

一般为18位，但时间超过一定值后，会变为19位。

消耗完18位所需的时间：110^18 / (3600 24 365 1000 * 2^22) ≈ 7.56年，即时间差超过7.56年，就会达到19位。

比如以2010年1月1日为epoch，则差不多到2017年中就19位了。

关于长度，可以通过数字2进制转10进制的长度比。一个用2进制表示的数字是用10进制表示长度的3.3倍。

正整数n，用10进制表示的长度为：
a=⌊log10n⌋+1a=⌊log10⁡n⌋+1
而用2进制表示为：
b=⌊log2n⌋+1b=⌊log2⁡n⌋+1
所以比值：
c=limn→∞ab=limn→∞⌊log10n⌋⌊log2n⌋=log210≈3.32

假设生成长度为15位，则需要字节长度为53。

根据设备生成15位Id

public class SnowFlakeGenerator {
    /**
     * 长度15
     */
    private static final int TOTAL_BITS = 53;
    /**
     * 毫秒级时间戳，可以用(2^41-1)/(1000*60*60*24*365)=69.7年，即2015+69.7=2084年
     */
    private static final int EPOCH_BITS = 41;
    /**
     * 最大31台，0-31一共32台
     */
    private static final int NODE_ID_BITS = 5;
    /**
     * 每毫秒自增最大127，0-127，一共128个
     */
    private static final int SEQUENCE_BITS = 7;

    /**
     * 最大节点
     * 移位算法可以很快的计算出几位二进制数所能表示的最大十进制数
     */
    private static final int maxNodeId = (int) (~(-1L << NODE_ID_BITS));
    /**
     * 最大自增数
     */
    private static final int maxSequence = (int) (~(-1L << SEQUENCE_BITS));

    /**
     * 偏移量，增大可用时间大概2015-1970=45年
     * 开始时间，2015-01-01T00:00:00Z
     */
    private static final long CUSTOM_EPOCH = 1420070400000L;

    /**
     * 当前节点
     */
    private volatile int nodeId;

    /**
     * 最后时间戳
     */
    private volatile long lastTimestamp = -1L;
    /**
     * 当前id，每次均+1
     */
    private volatile int sequence = 0;

    /**
     * 时间戳左移，空出节点和序列号位
     */
    private int EPOCH_SHIFT = TOTAL_BITS - EPOCH_BITS;
    /**
     * 节点位左移，空出序列号位
     */
    private int NODE_ID_SHIFT = TOTAL_BITS - EPOCH_BITS - NODE_ID_BITS;

    /**
     * 主动设置节点
     *
     * @param nodeId
     */
    public SnowFlakeGenerator(int nodeId) {
        if (nodeId < 0 || nodeId > maxNodeId) {
            throw new IllegalArgumentException(String.format("NodeId must be between %d and %d", 0, maxNodeId));
        }
        this.nodeId = nodeId;
    }

    /**
     * 生成节点默认id
     */
    public SnowFlakeGenerator() {
        this.nodeId = createNodeId();
    }

    /**
     * 获取下一个id
     *
     * @return
     */
    public synchronized long nextId() {
        //当前时间戳
        long currentTimestamp = timestamp();

        //出现时间回拨
        if (currentTimestamp < lastTimestamp) {
            //换个节点
            nodeId = createNodeId(true);
        }

        //当前轮
        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) & maxSequence;
            if (sequence == 0) {
                //id用完，等下一毫秒
                currentTimestamp = waitNextMillis(currentTimestamp);
            }
        } else {
            //每轮开始
            sequence = 0;
        }

        lastTimestamp = currentTimestamp;

        //时间戳左移8位，即乘以2的8次方
        long id = currentTimestamp << EPOCH_SHIFT;
        //节点id左移3位，或运算拼id到一起
        id |= nodeId << NODE_ID_SHIFT;
        //或运算拼id到一起
        id |= sequence;
        //41bits|5bits|7bits
        return id;
    }


    /**
     * 获取秒
     *
     * @return
     */
    private static long timestamp() {
        return Instant.now().toEpochMilli() - CUSTOM_EPOCH;
    }

    private int createNodeId() {
        return createNodeId(false);
    }

    /**
     * 根据设备地址生成节点
     *
     * @return
     */
    private int createNodeId(boolean random) {
        int nodeId;
        try {
            if (random) {
                nodeId = (new SecureRandom().nextInt());
            } else {
                StringBuilder sb = new StringBuilder();
                Enumeration<NetworkInterface> networkInterfaces = NetworkInterface.getNetworkInterfaces();
                while (networkInterfaces.hasMoreElements()) {
                    NetworkInterface networkInterface = networkInterfaces.nextElement();
                    byte[] mac = networkInterface.getHardwareAddress();
                    if (mac != null) {
                        for (int i = 0; i < mac.length; i++) {
                            sb.append(String.format("%02X", mac[i]));
                        }
                    }
                }
                //hash
                nodeId = sb.toString().hashCode();
            }
        } catch (Exception ex) {
            nodeId = (new SecureRandom().nextInt());
        }
        //取余
        nodeId = nodeId & maxNodeId;
        if (nodeId == this.nodeId) {
            //重新随机
            nodeId = createNodeId(true);
        }
        return nodeId;
    }

    /**
     * 等一毫秒
     *
     * @param currentTimestamp
     * @return
     */
    private long waitNextMillis(long currentTimestamp) {
        while (currentTimestamp == lastTimestamp) {
            currentTimestamp = timestamp();
        }
        return currentTimestamp;
    }

    public static void main(String[] args) {
        SnowFlakeGenerator snowFlakeGenerator = new SnowFlakeGenerator();
        System.out.println(snowFlakeGenerator.nextId());
    }
}

用位运算计算n个bit能表示的最大数值

long maxNodeId = (int) (~(-1L << 5));

所以上面那行代码中，运行顺序是：

-1 左移 5，得结果a
-1 异或 a

二进制运算过程如下：

-1 左移 5，得结果a ：

        11111111 11111111 11111111 11111111 //-1的二进制表示（补码）
  11111 11111111 11111111 11111111 11100000 //高位溢出的不要，低位补0
        11111111 11111111 11111111 11100000 //结果a

-1 异或 a ：

        11111111 11111111 11111111 11111111 //-1的二进制表示（补码）
    ^   11111111 11111111 11111111 11100000 //两个操作数的位中，相同则为0，不同则为1
---------------------------------------------------------------------------
        00000000 00000000 00000000 00011111 //最终结果31

最终结果是31，二进制00000000 00000000 00000000 00011111转十进制可以这么算：
24+23+22+21+20=16+8+4+2+1=31
-1L ^ (-1L << 5L)结果是31，$2^{5}-1$的结果也是31，所以在代码中，-1L ^ (-1L << 5L)的写法是利用位运算计算出5位能表示的最大正整数是多少

防止溢出

sequence = (sequence + 1) & maxSequence

这段代码通过位与运算保证计算的结果范围始在0-maxSequence，其实就是取余操作。

用位运算汇总结果

|或运算符，也是一个位运算符。

其含义是：x的第n位和y的第n位，只要有一个是1，则结果的第n位也为1，否则为0。

正因为左移的操作，使四个不同的值移到了SnowFlake理论上相应的位置，然后做位或运算（只要有1结果就是1），就把几段的二进制数合并成一个二进制数。

最后转换成10进制，就是最终生成的id。