雪花算法记录

引子

伴随着业务的日渐庞大，单库单表的数据库可能无法支持业务的读写，需要对数据库进行分库分表。
原来数据库中，通常使用自增id的方式生成主键。分库分表之后，如果仍然采用原来的方式，在多个表之间主键会发生重复。
分库分表后，如何保证多张表中的 id 是全局唯一性的呢？

方法

针对此问题，通常有三种解法

1. uuid
2. 数据库主键自增。eg：两张表，一张奇数、一张偶数
3. 雪花算法

此外，Redis 的自增原子性来生成唯一id，比较少用。

原理

雪花算法最早由Twitter提出，格式如下

• 最高 1 位固定值 0，因为生成的 id 是正整数，如果是 1 就是负数了。
• 接下来41位存储毫秒级时间戳，2^41/(1000606024365)=69，大概可以使用 69 年。
• 再接下 10 位存储机器码，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台机器。
• 最后 12 位存储序列号。同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。

思考

• 雪花算法有以下几个优点：

  • 高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
  • 基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
  • 生成单调自增的唯一ID，在innodb的b+数表中顺序插入不会造成页的分裂，性能高。（uuid的话每个id是随机的，大量的随机IO效率不但低，还会使innodb页造成分裂和合并，使得插入效率低）
  • 生成64位id，只占用8个字节节省存储空间。
  • 不依赖第三方库或者中间件。
  • 算法简单，在内存中进行，效率高。

• 雪花算法有如下缺点：

  • 依赖服务器时间：
    • 服务器时钟回拨时可能会生成重复 id。
    • 每台数据库的本地时间都要设置相同，否则会导致全局不递增

解法：
算法中可通过记录最后一个生成 id 时的时间戳来解决，每次生成 id 之前比较当前服务器时钟是否被回拨，避免生成重复 id。如果发生回拨

• 回拨时间较短，进行等待，直至时间达到最后一个生成id的时间+1，再继续产生。
• 回拨时间长，报错处理
• 选取两个bit，最初是00，接下来会有01、10、11三种情况，可以接受三次时间回拨。

代码

public class SnowFlakeUtils {
    /*
        起始时间时间戳：这个时间为第一次运行时的时间，这里设置为2021/11/23/19/17
        可以在未来的69年内稳定运行
     */
    private final static long START_STMP=1637666189914L;


    private final static long SEQUENCE_BIT=12;//序列号占用12bit
    private final static long MACHINE_BIT=5;//机器号占用5bit
    private final static long MACHINE_HOUSE_BIT=5;//机房号占用5bit
    /*
        -1的源码   10000001
        -1的反码   11111110
        -1的补码   11111111
        -1左移12位= 1111 1111 0000 0000 0000
        -1       = 1111 1111 1111 1111 1111
        异或运算  = 0000 0000 1111 1111 1111=4095
        因此MAX_SEQUENCE的值为4095
     */
    private final static long MAX_SEQUENCE=-1L^(-1L<<SEQUENCE_BIT);
    //同理 MAX_MACHINE为31
    private final static long MAX_MACHINE=-1L^(-1L<<MACHINE_BIT);
    //同理 MAX_MACHINE_HOUSE值为31
    private final static long MAX_MACHINE_HOUSE=-1L^(-1L<<MACHINE_HOUSE_BIT);
    //机器ID
    private long machineID;
    //机房ID
    private long machineHouseID;
    private long lastTime=0;//上一次生成ID的时间戳
    private long sequence=0;//序列号，默认为0

    public SnowFlakeUtils(long machineID, long machineHouseID) {
        this.machineID = machineID;
        this.machineHouseID = machineHouseID;
    }

    public long getMachineID() {
        return machineID;
    }

    public void setMachineID(long machineID) {
        this.machineID = machineID;
    }

    public long getMachineHouseID() {
        return machineHouseID;
    }

    public void setMachineHouseID(long machineHouseID) {
        this.machineHouseID = machineHouseID;
    }


    /***
     *产生下一个ID
     * 用long型来表示我们生成的64位ID，
     * @return
     */

    public  synchronized long nextId(){
        if(machineHouseID>MAX_MACHINE_HOUSE ||machineID>MAX_MACHINE){
            throw new RuntimeException("机房ID或机器ID超出最大值");
        }
        //获取当前时间戳
        long currentTime=System.currentTimeMillis();
        //如果当前时间小于上一次生成ID的时间，抛出异常
        if(currentTime<lastTime){
            throw new RuntimeException("当前时间为异常值，请勿回拨时间！");
        }
        //如果当前时间等于上一次生成ID时间，说明是在同一毫秒中生成，那么序列号加一
        else if(currentTime==lastTime){
            /*
                MAX_SEQUENCE: 0000 1111 1111 1111
                            &
                        4096: 0001 0000 0000 0000
                           = 0
                 当sequence小于4095时， (sequence+1)&MAX_SEQUENCE=sequence+1
                 当sequence等于4095时，(sequence+1)&MAX_SEQUENCE=0
             */
            sequence= (sequence+1)&MAX_SEQUENCE;
            if(sequence==0L){
                //获取下一个毫秒值
                currentTime=getNextMill();
            }

        }else{
            //毫秒值不同，sequence初始为0
            sequence=0L;
        }
        //更新最近一次生成时间的毫秒值
        lastTime=currentTime;
        return (currentTime-START_STMP)<<22//左移22位 空出机房ID5位+机器ID5位+序列号12位
                |machineID<<12//左移12位 空出序列号12位
                |machineHouseID<<17//左移17位 空出机器ID5位+序列号12位
                |sequence;//序列号部分
    }

    /**
     * 获取下一个毫秒值
     * @return
     */
    private  long getNextMill() {
        long mill=System.currentTimeMillis();
        //如果当前时间等于上一次的时间则一直自旋
        while(mill==lastTime){
            mill=System.currentTimeMillis();
        }
        return mill;

    }

    /**
     * Main方法测试
     * @param args
     */

    public static void main(String[] args) {
        //初始化一个雪花算法工具类，设置机房ID和机器ID都为0
        SnowFlakeUtils snowFlakeUtils=new SnowFlakeUtils(0,0);
        for (int i = 0; i <100; i++) {
            //生成100个ID
            System.out.println(snowFlakeUtils.nextId());
        }

    }
}
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