SnowFlake(雪花算法)

2019-11-08 本文已影响0人荒漠狂沙走万里

首先雪花算法就是生成一个64位的二进制数据，最终转换成长度为19的十进制正整数整型数据

0 0000000000 0000000000 0000000000 0000000000 0 00000 00000  000000000000

image.gif

解释一下这64位分别代表什么意思，从左往右。

符号位：第1个，也就是最高位0毫无疑问代表符号位（0代表正数，1代表负数），在这个场景中不需要负数，所以最高位恒为0，也就解释了为啥长度是19了。
时间戳位：从第2个到第42个这中间的41位是雪花算法最核心的东西了,它代表41位的时间戳，这个时间戳并非实际意义上的时间戳，他是当前时间戳减去一个时间戳常量(开始生成唯一ID的时间戳)的差值，所以他是从0开始的，能够取到的最大时间范围就是2的41次方(即1L<<41)，换算成年的话也就是约等于69.73年。换句话说也就是在生成ID的那一刻起到69.73之间生成的ID绝对是唯一的(前提是各个机器的时间一致)，在此之后生成的ID有几率碰撞(总是不知不觉中写bug</坏笑>)
机器位：从第43到53这10位是机器位，此ID也能适用于分布式系统中，前五位是数据中心为，后五位是机器标识，能够产生1024个数据节点。
序列号位：最后12位是序列号，作为支持并发处理。在一个数据中心的一个机器中一个毫秒单位内能够产生4096个不同的串号。
据说：snowflake每秒能够产生26万个ID，由此可见此算法还是十分强大的。

当然这个算法的强大并不仅仅如此而已，这个算法的时间位、机器位、序列号位都是可以根据不同场景来调整的，那么他们碰撞的几率也随着调整发生改变。

优点：生成唯一ID时间快，ID随时间变化而递增，支持分布式系统，在很长一段时间内不会重复。
缺点：过分依赖服务器时间（服务器时间调整，ID有可能会重复），生成的唯一ID过长(不算缺点吧)

接下来上干货

public class Snowflake {

    /**
     * 开始时间戳常量（2019-08-18 23:33:00）
     * 一旦开始就不能调整时间戳
     */
    private final static long START_TIME = 15661422735631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    //2的5次方1024
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    //2的5次方1024
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    //2的12次方4096
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastTime = -1L;//上一次时间戳

    public Snowflake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
           throw new IllegalArgumentException("datacenterId不能大于MAX_DATACENTER_NUM 或小于0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId不能大于MAX_MACHINE_NUM或者小于0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     */
    public synchronized long nextId() {
        long currStmp = System.currentTimeMillis();
        if (currStmp < lastStmp) {
            throw new RuntimeException("时间混乱，请调整时间");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp =getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_TIME) << TIMESTMP_LEFT//时间戳部分
                | datacenterId << DATACENTER_LEFT      //数据中心部分
                | machineId << MACHINE_LEFT            //机器标识部分
                | sequence;                            //序列号部分
    }

    private long getNextMill() {
        long mill = System.currentTimeMillis();
        while (mill <= lastStmp) {
            mill = System.currentTimeMillis();
        }
        return mill;
    }
}

image.gif

总体来说算法并不难，思路清晰，其中的牵扯到的知识点就是各个数据间进行位运算，这块知识薄弱的可以去补一补。
一篇文档不仅get到了雪花算法的思想，还发现了就像当初发现随机函数Random一样，随机只是在一定范围内随机，唯一只是在某一个时间段唯一。场景是度量算法的尺度，致敬Twitter。

SnowFlake(雪花算法)

猜你喜欢

热点阅读