引子

伴随着业务的日渐庞大，单库单表的数据库可能无法支持业务的读写，需要对数据库进行分库分表。
原来数据库中，通常使用自增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;//序列号占用12bitprivate final static long MACHINE_BIT=5;//机器号占用5bitprivate 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为31private final static long MAX_MACHINE=-1L^(-1L<<MACHINE_BIT);//同理 MAX_MACHINE_HOUSE值为31private final static long MAX_MACHINE_HOUSE=-1L^(-1L<<MACHINE_HOUSE_BIT);//机器IDprivate long machineID;//机房IDprivate long machineHouseID;private long lastTime=0;//上一次生成ID的时间戳private long sequence=0;//序列号，默认为0public 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初始为0sequence=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都为0SnowFlakeUtils snowFlakeUtils=new SnowFlakeUtils(0,0);for (int i = 0; i <100; i++) {//生成100个IDSystem.out.println(snowFlakeUtils.nextId());}}
}