分布式ID系列5Twitter的雪法算法Snowflake适合做分布式ID吗

36次阅读

共计 8604 个字符,预计需要花费 22 分钟才能阅读完成。

写到这里,分布式 Id 算是写到最后一篇了,在这一篇里,我会讲到目前网上最适合分布式 Id 的方法,什么方法呢,请您往下看:

介绍 Snowflake 算法

SnowFlake 算法是国际大公司 Twitter 的采用的一种生成分布式自增 id 的策略,这个算法产生的分布式 id 是足够我们我们中小公司在日常里面的使用了。我也是比较推荐这一种算法产生的分布式 id 的。

算法 snowflake 的生成的分布式 id 结构组成部分

算法 snowflake 生成 id 的结果是一个 64bit 大小的整数,它的结构如下图,

这里我么来讲一下这个结构:首先因为 window 是 64 位的,然后整数的时候第一位必须是 0,所以最大的数值就是 63 位的 111111111111111111111111111111111111111111111111111111111111111,然后呢 Snowflake 算法分出来 41 位作为毫秒值,然后 10 位作为 redis 节点的数量,然后 12 位做成 redis 节点在每一毫秒的自增序列值

41 位的二进制 11111111111111111111111111111111111111111 转换成 10 进制的毫秒就是 2199023255551,然后我们把 2199023255551 转换成时间就是 2039-09-07,也就是说可以用 20 年的(这里在网上会有很多说是可以使用 69 年的,他们说 69 年的也对,因为 1970 年 +69 年的结果就是 2039 年,但是如果从今年 2019 年来说,也就只能用 20 年了)

然后 10 位作为节点,所以最多就是 12 位的 1111111111,也就是最多可以支持 1023 个节点,

然后 10 位表示每一个节点自增序列值,这里最多就是 10 位的 111111111111,也就是说每一个节点可以每一毫秒可以最多生成 4059 个不重复 id 值

由于在 Java 中 64bit 的整数是 long 类型,所以在 Java 中 SnowFlake 算法生成的 id 就是 long 来存储的。

Java 实现 Snowflake 算法的源码

Snowflake 算法的源码如下所示(这个是我从网上找到的),这里我进行了测试了一波,结果如下所示

package com.hello;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Test {
    /**
     * 开始时间截 (1970-01-01)
     */
    private final long twepoch = 0L;

    /**
     * 机器 id 所占的位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据标识 id 所占的位数
     */
    private final long datacenterIdBits = 5L;

    /**
     * 支持的最大机器 id,结果是 31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识 id,结果是 31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /**
     * 序列在 id 中占的位数
     */
    private final long sequenceBits = 12L;

    /**
     * 机器 ID 向左移 12 位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 数据标识 id 向左移 17 位(12+5)
     */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /**
     * 时间截向左移 22 位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 生成序列的掩码,这里为 4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作机器 ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心 ID(0~31)
     */
    private long datacenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成 ID 的时间截
     */
private long lastTimestamp = -1L;

    public Test(long workerId, long datacenterId) {if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    /**
     * 获得下一个 ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {long timestamp = timeGen();

        // 如果当前时间小于上一次 ID 生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        // 如果是同一时间生成的,则进行毫秒内序列
        if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒, 获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变,毫秒内序列重置
        else {sequence = 0L;}

        // 上次生成 ID 的时间截
        lastTimestamp = timestamp;

        // 移位并通过或运算拼到一起组成 64 位的 ID
        return ((timestamp - twepoch) << timestampLeftShift) //
            | (datacenterId << datacenterIdShift) //
            | (workerId << workerIdShift) //
            | sequence;
    }

    /**
     * 阻塞到下一个毫秒,直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成 ID 的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {return System.currentTimeMillis();
    }

    public static void parseId(long id) {
        long miliSecond = id >>> 22;
        long shardId = (id & (0xFFF << 10)) >> 10;
        System.err.println("分布式 id-"+id+"生成的时间是:"+new SimpleDateFormat("yyyy-MM-dd").format(new Date(miliSecond)));
    }

    public static void main(String[] args) {Test idWorker = new Test(0, 0);
        for (int i = 0; i < 10; i++) {long id = idWorker.nextId();
            System.out.println(id);
            parseId(id);
        }
    }
}

执行结果如下所示,此时我们可以看到,不仅可以可以把分布式 id 给创建处理,而且可以把这个创建的时间也打印出来,此时就可以满足我们的分布式 id 的创建了

6566884785623400448
分布式 id-6566884785623400448 生成的时间是:2019-08-13
6566884785812144128
分布式 id-6566884785812144128 生成的时间是:2019-08-13
6566884785812144129
分布式 id-6566884785812144129 生成的时间是:2019-08-13
6566884785812144130
分布式 id-6566884785812144130 生成的时间是:2019-08-13
6566884785812144131
分布式 id-6566884785812144131 生成的时间是:2019-08-13
6566884785812144132
分布式 id-6566884785812144132 生成的时间是:2019-08-13
6566884785816338432
分布式 id-6566884785816338432 生成的时间是:2019-08-13
6566884785816338433
分布式 id-6566884785816338433 生成的时间是:2019-08-13
6566884785816338434
分布式 id-6566884785816338434 生成的时间是:2019-08-13
6566884785816338435
分布式 id-6566884785816338435 生成的时间是:2019-08-13

缩小版 Snowflake 算法生成分布式 id

因为 Snowflake 算法的极限是每毫秒的每一个节点生成 4059 个 id 值,也就是说每毫秒的极限是生成 023*4059=4 152 357 个 id 值,这样生成 id 值的速度对于 twitter 公司来说是很符合标准的(毕竟人家公司大嘛),但是对于咱们中小公司来说是不需要的,所以我们可以根据 Snowflake 算法来修改一下分布式 id 的创建,让每秒创建的 id 少一些,但是把可以使用的时间扩大一些

这里我看廖雪峰老师的文章之后,采用了 53 位作为分布式 id 值的位数,因为如果后端和前端的 JavaScript 打交道的话,由于 JavaScript 支持的最大整型就是 53 位,超过这个位数,JavaScript 将丢失精度。因此,使用 53 位整数可以直接由 JavaScript 读取,而超过 53 位时,就必须转换成字符串才能保证 JavaScript 处理正确,所以我们的分布式 id 就用 53 位来生成

这 53 位里面,第一位还是 0,然后剩下的 52 位,33 位作为秒数,4 位作为节点数,15 位作为每一个节点在每一秒的生成序列值

33 位的二进制 111111111111111111111111111111111 转换成 10 进制的秒就是 8589934591,然后我们把 8589934591 转换成时间就是 2242-03-16,也就是说可以用 220 年的,足够我们的使用了

然后 4 位节点,所以最多就是 4 位的 1111,也就是最多可以支持 15 个节点,

然后 15 位表示每一个节点每一秒自增序列值,这里最多就是 10 位的 11111111111111111,也就是说每一个节点可以每一秒可以最多生成 131071 个不重复 id 值

这样算起来,就是说每一秒每一个节点生成 131071 个不重复的节点,所以极限就是每秒生成 15*131071=1 966 065 个分布式 id,够我们在开发里面的日常使用了

所以代码就可以变成下面这样,这里主要讲一下下面的 nextId()方法,
首先蓝色代码是获取当前秒,然后进行校验,就是把当前时间和上一个时间戳进行比较,如果当前时间比上一个时间戳要小,那就说明系统时钟回退,所以此时应该抛出异常
然后是下面的红色代码,首先如果是同一秒生成的,那么就把这一秒的生成序列 id 值一直增加,一直增加到 131071 个,如果在增加,那么下面的红色代码里面的 sequence = (sequence + 1) & sequenceMask; 的值就会是 0,那么就会执行红色代码里面的 tilNextMillis()方法进行阻塞,直到获取到下一秒继续执行
然后下面的绿色代码表示每一秒过去之后,都要把这个生成序列的 id 值都变成 0,这样在新的一秒里面就可以在继续生成 1 到 131071 个分布式 id 值了
然后下面的黄色代码就是把咱们的秒,节点值,节点每秒生成序列 id 值加起来组成一个分布式 id 返回

package com.hello;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Test {

    /**
     * 开始时间截 (1970-01-01)
     */
    private final long twepoch = 0L;

    /**
     * 机器 id,范围是 1 到 15
     */
    private final long workerId;

    /**
     * 机器 id 所占的位数,占 4 位
     */
    private final long workerIdBits = 4L;

    /**
     * 支持的最大机器 id,结果是 15
     */
    private final long maxWorkerId = ~(-1L << workerIdBits);

    /**
     * 生成序列占的位数
     */
    private final long sequenceBits = 15L;

    /**
     * 机器 ID 向左移 15 位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 生成序列的掩码,这里为最大是 32767 (1111111111111=32767)
     */
    private final long sequenceMask = ~(-1L << sequenceBits);

    /**
     * 时间截向左移 19 位(4+15)
     */
    private final long timestampLeftShift = 19L;


    /**
     * 秒内序列(0~32767)
     */
    private long sequence = 0L;

    /**
     * 上次生成 ID 的时间截
     */
    private long lastTimestamp = -1L;


    public Test(long workerId) {if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }

    /**
     * 获得下一个 ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        // 蓝色代码注释开始
        long timestamp = timeGen();

        // 如果当前时间小于上一次 ID 生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
         // 蓝色代码注释结束
         // 红色代码注释开始
        // 如果是同一时间生成的,则进行秒内序列
        if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;
            // 秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个秒, 获得新的秒值
                timestamp = tilNextMillis(lastTimestamp);
            }
        // 时间戳改变,秒内序列重置
        }
        // 红色代码注释结束
        // 绿色代码注释开始
        else {sequence = 0L;}
        // 绿色代码注释结束

        // 上次生成 ID 的时间截
        lastTimestamp = timestamp;
        // 黄色代码注释开始
        // 移位并通过或运算拼到一起组成 53 位的 ID
        return ((timestamp - twepoch) << timestampLeftShift)
            | (workerId << workerIdShift)
            | sequence;
        // 黄色代码注释结束
    }

    /**
     * 阻塞到下一个秒,直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成 ID 的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以秒为单位的当前时间
     *
     * @return 当前时间(秒)
     */
    protected long timeGen() {return System.currentTimeMillis()/1000L;
    }

    public static void parseId(long id) {
        long second = id >>> 19;
        System.err.println("分布式 id-"+id+"生成的时间是:"+new SimpleDateFormat("yyyy-MM-dd").format(new Date(second*1000)));
    }

    public static void main(String[] args) {Test idWorker = new Test(0);
        for (int i = 0; i < 10; i++) {long id = idWorker.nextId();
            System.out.println(id);
            parseId(id);
        }
    }
}

此时结果如下所示,都是 ok 的,؏؏☝ᖗ乛◡乛ᖘ☝؏؏

820870564020224
分布式 id-820870564020224 生成的时间是:2019-08-13
820870564020225
分布式 id-820870564020225 生成的时间是:2019-08-13
820870564020226
分布式 id-820870564020226 生成的时间是:2019-08-13
820870564020227
分布式 id-820870564020227 生成的时间是:2019-08-13
820870564020228
分布式 id-820870564020228 生成的时间是:2019-08-13
820870564020229
分布式 id-820870564020229 生成的时间是:2019-08-13
820870564020230
分布式 id-820870564020230 生成的时间是:2019-08-13
820870564020231
分布式 id-820870564020231 生成的时间是:2019-08-13
820870564020232
分布式 id-820870564020232 生成的时间是:2019-08-13
820870564020233
分布式 id-820870564020233 生成的时间是:2019-08-13

雪法算法 Snowflake 适合做分布式 ID 吗

根据一系列的分布式 id 讲解,雪法算法 Snowflake 是目前网上最适合做分布式 Id 的了,大家如果想用的话,可以根据我上面的缩小版的 Snowflake 算法来作为我们开发中的使用。؏؏☝ᖗ乛◡乛ᖘ☝؏؏

原文链接

其他分布式 ID 系列快捷键:
分布式 ID 系列(1)——为什么需要分布式 ID 以及分布式 ID 的业务需求
分布式 ID 系列(2)——UUID 适合做分布式 ID 吗
分布式 ID 系列(3)——数据库自增 ID 机制适合做分布式 ID 吗
分布式 ID 系列(4)——Redis 集群实现的分布式 ID 适合做分布式 ID 吗
分布式 ID 系列(5)——Twitter 的雪法算法 Snowflake 适合做分布式 ID 吗

大佬网址
https://www.itqiankun.com/art…
https://www.liaoxuefeng.com/a…
https://tech.meituan.com/2017…
https://segmentfault.com/a/11…
https://www.jianshu.com/p/9d7…

正文完
 0