Fork me on GitHub

雪花算法

发表于 | 分类于 ， | | 阅读次数
雪花算法

雪花算法

SnowFlake 算法，是 Twitter 开源的分布式 id 生成算法。其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增的。本文主要是是实现了单机版本的算法，使用多台计算机构成分布式的ID生成服务也是可以的，预留了相关的方法参数。

应用范围

  1. 在jdk中自带的uuid算法可以来生成唯一性的32位字符串【拼接上‘-’之后，是36位，如：’4211210a-ba56-41b4-b055-6262411970a4’】，uuid算法得到的id是无序的，而且是字符串，数据表记录多时，查询效率不高

  2. 基于数据库的sequence【通过表也可以模拟sequence】来生成，在分布式系统中更新记录不方便，只能操作主表的更新。

  3. 雪花算法在分布式系统中可以较好地使用

原理

把64位进行拆分，分为如下几个部份

  • 第1部份只占1位，而且必需为0，因为最高位0表示正数。
  • 第2部份是时间戳，占41位【为什么是41位，后面会介绍】，最多可以表示2^41，大约是69年
  • 第3部份是产生的机器号，占10位【也可以是其它位数，不一定非得是10位，官方约定是10位】，最多可以表示2^10，相当于1024台机器，这部分可以划成两个维度，如下：
    • 3.1 拿5位出来做为机房号，最多可以表示 2^5个机房号，也就是最多32个机房编号
    • 3.2 拿5位出来做为机器号，最多可以表示 2^5台电脑，也就是最多32台电脑编号
  • 第4部份是时间戳，占12位，相当于在同一个毫秒内，可以最大支持2^12，也就是4096个序号【普通的计算机根本达不到，我的电脑测试下来是远远用不完的】

如下图
图示

代码实现

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
public class IdGenerator {

    //定义属性 [机器码10位，如何分配成 机房码和电脑码，做为属性，这里默认都是5]
    private final long dataCenterBits = 5L; //机房码的位数
    private final long computerBits = 5L; //电脑码的位数
    //最后的序列码，默认从0开始
    private long sequence = 0L;
    //记录执行的最后时间，以毫秒为单位，默认初始化为-1L
    private long lastTimeStamp = -1L;

    //因为要做二进制运算，我们需要定义如下属性来记录每个部份所在的位置的偏移量
    private final long sequenceBits = 12; //序号占用12位
    private final long computerIdShift = sequenceBits; //电脑码的偏移量
    private final long dataCenterIdShift = computerIdShift + computerBits; //机房码的偏移量
    private final long timeStampShift = dataCenterIdShift + dataCenterBits; //时间戳的偏移量

    //根据机房码的位数，来计算出机房码最大值
    private final long MAX_DATA_CENTER = -1L ^ (-1L << dataCenterBits);   //相当于 11111， 也就是 31
    private final long MAX_COMPUTER = -1L ^ (-1L << computerBits); //同上
    private final long SEQUENCE_MASK = -1L ^ (-1L << sequenceBits); // 为防止序列号溢出而准备的掩码，相当于 11111111 111

    //定义属性
    private long computerId; //电脑的id 【在分布式系统中，记录这个雪花号是由哪一台电脑生成的】
    private long dataCenterId; //机房的id 【在分布式系统中，记录这个雪花号是由哪一个中心机房里的电脑生成的】
    //构造
    public IdGenerator(long computerId, long dataCenterId) {
        //对参数的有效性进行判断，由于机房码和电脑码都是5位，所以，它们的值最大都不能超过31
        if(computerId > MAX_COMPUTER || computerId < 0) {
            throw new IllegalArgumentException(String.format("电脑编号不能大于 %d 或者小于 %d \n",MAX_COMPUTER,0));
        }
        if(dataCenterId > MAX_DATA_CENTER || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("机房编号不能大于 %d 或者小于 %d\n",MAX_DATA_CENTER, 0));
        }
        //赋值
        this.computerId = computerId;
        this.dataCenterId = dataCenterId;
    }

    /***************
     * 核心方法，利用雪花算法来获取一个唯一性的ID
     * @return
     */
    public synchronized long nextId() {
        //1.获取当前的系统时间
        long currTime = getCurrentTime();
        //2. 判断是否在同一个时间内的请求
        if(currTime == lastTimeStamp) {
            //2.1 sequence 要增1, 但要预防sequence超过 最大值4095，所以要 与 SEQUENCE_MASK 按位求与
            sequence = (sequence + 1) & SEQUENCE_MASK;
            //2.2 进一步判断，如果在同一个毫秒内，sequence达到了4096【1 0000 0000 0000】，则lastTime时间戳必需跳入下一个时间，因为同一个毫秒内
            //sequence只能产生4096个【0-4095】，当超过时，必需跳入下一个毫秒
            // 【此情况极少出现，但不可不防，这意味着1个毫秒内，JVM要执行此方法达到4096次，我这个电脑执行远达不到。】
            if(sequence == 0) {
                currTime = unitNextTime();
            }
        } else {
            //如果不是与lastTime一样，则表示进入了下一个毫秒，则sequence重新计数
            sequence = 0L;
        }
        //3. 把当前时间赋值给 lastTime, 以便下一次判断是否处在同一个毫秒内
        lastTimeStamp = currTime;
        //4. 依次把各个部门求出来并通过逻辑或 拼接起来
        return (this.lastTimeStamp << timeStampShift) |               //把当前系统时间 左移22位
                (this.dataCenterId << dataCenterIdShift) |  //把机房编号 左移17位
                (this.computerId << computerIdShift) |      //把计算机号编号左移 12位
                this.sequence;                                   //最后的序列号占12位，无需移动
    }

    /******
     * 等待毫秒数进入下一个时间
     * @return
     */
    private long unitNextTime() {
        //1.再次获取系统时间
        long timestamp = getCurrentTime();
        //2. 判断 lastTime与currentTime是否一样
        while(timestamp <= lastTimeStamp) {
            //2.1 继续获取系统时间，直到上面的条件不成立为止
            timestamp = getCurrentTime();
        }
        //3. 返回
        return timestamp;
    }

    /*****
     * 用来获取当前的系统时间，以毫秒为单位
     * @return
     */
    private long getCurrentTime() {
        return System.currentTimeMillis();
    }
}

上面有详细的注释，这里就不再做解释了

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class UseIdGenerator {
	/****
     * 主方法
     * @param args
     */
    public static void main(String[] args) {
    	//这里两个参数都是1，表示1号机房和1号电脑【在分布式系统中，每个电脑知道自己所在的机房和编号】
        IdGenerator ig = new IdGenerator(1,1);
        //循环生成
        long result = -1;
        for(int i = 0;i<10000;i++) {
            result = ig.nextId();
            System.out.println(result+" , "+Long.toBinaryString(result));
        }
    }

}

上面循环了10000次，可以看到，生成的ID是在同一个毫秒内是连续的。

附录：时间戳为什么是41位？

我个人理解是目前计算机的系统时间是从1970年1月1号午夜开始到现在经过的毫秒数，刚好使用到了41位，有兴趣的可以自己写如下代码来验证一下

1
2
3
4
5
6
7
8
9
10
public class XXX {
	
	//
	public static void main(String[] args) {
		//
		long now = Sytem.currentTimeMillils();
		int bits = Long.toBinaryString(now).length();
		System.out.println(bits);
	}
}

这个结果刚好是41，所以，如果时间戳低于41位的话，则就不能精确到毫秒了。

关注

关注微信公众号后留言
扫码