目录

雪花算法

算法原理

http://img.cana.space/picStore/20201122150325.png

  1. 1bit,不用,因为二进制中最高位是符号位,1表示负数,0表示正数。生成的id一般都是用整数,所以最高位固定为0。

  2. 41bit-时间戳,用来记录时间戳,毫秒级。

    41 bit 可以表示的数字多达 2^41 - 1,也就是可以标识 2 ^ 41 - 1 个毫秒值,换算成年就是表示 69 年的时间。

  3. 10bit-工作机器id,用来记录工作机器id,代表的是这个服务最多可以部署在 2^10 台机器上,也就是 1024 台机器。

    但是 10 bit 里 5 个 bit 代表机房 id,5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房(32 个机房),每个机房里可以代表 2 ^ 5 个机器(32 台机器),也可以根据自己公司的实际情况确定。

  4. 12bit-序列号,序列号,用来记录同毫秒内产生的不同id。

    12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096,也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。

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

SnowFlake可以保证:

  1. 所有生成的id按时间趋势递增
  2. 整个分布式系统内不会产生重复id(因为有datacenterId和workerId来做区分)

SnowFlake算法主要工作:

确定机器id和数据中心id

雪花算法中的核心就是机器id和数据中心id, 通常来说数据中心id可以在配置文件中配置, 通常一个服务集群可以共用一个配置文件, 而机器id如果也放在配置文件中维护的话, 每个应用就需要一个独立的配置, 难免也会出现机器id重复的问题

解决方案:

  1. 通过启动参数去指定机器id, 但是这种方式也会有出错的可能性
  2. 每个应用启动的时候注册到redis或者zookeeper, 由redis或zookeeper来分配机器id

确定sequence

确定毫秒数

算法实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
package com.eh.mall.order.service;

public class IdWorker {

    //因为二进制里第一个 bit 为如果是 1,那么都是负数,但是我们生成的 id 都是正数,所以第一个 bit 统一都是 0。
    //机器ID  2进制5位
    private long workerId;
    //机房ID 2进制5位
    private long datacenterId;
    //代表一毫秒内生成的多个id的最新序号  12位 4096 -1 = 4095 个
    private long sequence;
    //设置一个时间初始值    2^41 - 1   差不多可以用69年
    private long twepoch = 1585644268888L;
    //机器id位数
    private long workerIdBits = 5L;
    //机房id位数
    private long datacenterIdBits = 5L;
    //序列号位数
    private long sequenceBits = 12L;
    // 31
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 31
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    //机器id需要左移的位数,12位
    private long workerIdShift = sequenceBits;
    //数据中心id需要左移位数 12+5=17位
    private long datacenterIdShift = sequenceBits + workerIdBits;
    //时间戳需要左移位数 12+5+5=22位
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    //序列号掩码 2>>12 - 1,保证生成的序列号在0到2^12-1之间也就是1到4095
    private long sequenceMask = -1L ^ (-1L << sequenceBits);
    //记录产生时间的毫秒数,用于判断是否是同1毫秒
    private long lastTimestamp = -1L;

    public long getWorkerId() {
        return workerId;
    }

    public long getDatacenterId() {
        return datacenterId;
    }

    public long getTimestamp() {
        return System.currentTimeMillis();
    }


    /**
     * 初始化
     *
     * @param workerId     机器ID
     * @param datacenterId 机房ID
     */
    public IdWorker(long workerId, long datacenterId) {

        // 检查机房id和机器id是否超过31 不能小于0
        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;
    }

    // 这个是核心方法,通过调用nextId()方法,让当前这台机器上的snowflake算法程序生成一个全局唯一的id
    public synchronized long nextId() {
        // 这儿就是获取当前时间戳,单位是毫秒
        long timestamp = timeGen();
        // 防止时钟回拨
        if (timestamp < lastTimestamp) {

            System.err.printf(
                    "clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(
                    String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
                            lastTimestamp - timestamp));
        }

        // 下面是说假设在同一个毫秒内,又发送了一个请求生成一个id
        // 这个时候就得把sequence序号给递增1,最多就是4095
        if (lastTimestamp == timestamp) {

            // 这个意思是说一个毫秒内最多只能有4096个数字,无论你传递多少进来,
            //这个位运算保证始终就是在4096这个范围内,避免你自己传递个sequence超过了4096这个范围
            // 取模 2^12
            sequence = (sequence + 1) & sequenceMask;
            //当某一毫秒的时间,产生的id数 超过4095,系统会进入等待,直到下一毫秒,系统继续产生ID
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }

        } else {
            sequence = 0;
        }
        // 这儿记录一下最近一次生成id的时间戳,单位是毫秒
        lastTimestamp = timestamp;
        // 这儿就是最核心的二进制位运算操作,生成一个64bit的id
        // 先将当前时间戳左移,放到41 bit那儿;将机房id左移放到5 bit那儿;将机器id左移放到5 bit那儿;将序号放最后12 bit
        // 最后拼接起来成一个64 bit的二进制数字,转换成10进制就是个long型
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) | sequence;
    }

    /**
     * 当某一毫秒的时间,产生的id数 超过4095,系统会进入等待,直到下一毫秒,系统继续产生ID
     *
     * @param lastTimestamp
     * @return
     */
    private long tilNextMillis(long lastTimestamp) {

        long timestamp = timeGen();

        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    //获取当前时间戳
    private long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * main 测试类
     *
     * @param args
     */
    public static void main(String[] args) {
    }
}

使用雪花算法的问题

  • 时间回拨问题

    由于机器的时间是动态的调整的,有可能会出现时间跑到之前几毫秒,如果这个时候获取到了这种时间,则会出现数据重复

  • 机器id的分配和回收问题

    目前机器id需要每台机器不一样,这样的方式分配需要有方案进行处理,同时也要考虑,如果该机器宕机了,对应的workerId分配后的回收问题

业内方案

业内的方案中对以上三个问题有这么几种处理,这里简单表述下

  • 时间回拨问题
    • 采用直接抛异常方式:这种很不友好,太粗暴
    • 采用等待跟上次时间的一段范围:这种算是简单解决,可以接受,但是如果等待一段时间后再出现回拨,则抛异常,可接受
  • 机器id的分配和回收问题
    • 采用zookeeper的顺序节点分配:解决了分配,回收可采用zookeeper临时节点回收,但是临时节点不可靠,存在无故消失问题,因此也不可靠
    • 采用DB中插入数据作为节点值:解决了分配,没有解决回收