雪花算法简介

雪花算法简介

 
雪花算法(SnowFlake)称为雪花算法。
  是Twitter公司在其内部用于分布式环境下生成唯一ID
2014年开源scala 语言版本

 
首位:１bit,固定为0。
时间戳:41bit,((2^41 ) - 1) / (1000x60x60x24x365) 大约可以使用69年。
机器码:10bit,一般前5bit用户机房,后5bit用于服务器，共可部署2^5 x 2^5 = 1024 台服务器。
序列号:12bit,同一毫秒时间戳，通过序列号来递增区分,1ms可以容纳 (2^12) -1= 4095个id,
 超过则获取下一毫秒

java版雪花算法

package com.java265.utils;

public class SnowFlake {

    /**
     * 组成部分 最高符号位 + 时间戳 + （机房id+机房id） + 序列号
     */

    // 修复时间戳 2022-08-12 20:30:00
    private static final long FIX_TIME_STAMP = 1660307400L;

    // 机房id
    private final long computerRoomId;

    // 机器id
    private final long machineId;

    // 序列号
    private long sequence = 0L;

    /**
     * 所占用的bit个数
     */

    // 时间戳41bit

    // 5bit机房id
    private static final long COMPUTER_ROOM_BIT_CNT = 5L;

    // 5bit机器id
    private static final long MACHINE_BIT_CNT = 5L;

    // 12bit序列号
    private static final long SEQUENCE_BIT_CNT = 12L;

    /**
     * 位移的位数
     */

    // 机器id 左移12位
    private static final long MACHINE_ID_SHIFT = SEQUENCE_BIT_CNT;

    // 机房id 左移17位
    private static final long COMPUTER_ROOM_ID_SHIFT = MACHINE_ID_SHIFT + MACHINE_BIT_CNT;

    // 时间戳 左移22位
    private final static long TIME_STAMP_SHIFT = COMPUTER_ROOM_ID_SHIFT + COMPUTER_ROOM_BIT_CNT;

    /**
     * 聚合信息
     */

    // 支持最大的机房id机房id  5bit
    private static final long MAX_COMPUTER_ROOM_ID = ~(-1 << COMPUTER_ROOM_BIT_CNT);

    // 支持最大的机器id 5bit
    private static final long MAX_MACHINE_ID = ~(-1 << MACHINE_BIT_CNT);

    // 序列号支持的最大的个数 12bit
    private static final long SEQUENCE_MASK = ~(-1 << SEQUENCE_BIT_CNT);

    // 上一次生成的时间戳
    private long lastTimeStamp = -1L;

    /**
     * @param computerRoomId 机房id
     * @param machineId      机器id
     */
    public SnowFlake(long computerRoomId, long machineId) {
        if (computerRoomId < 0 || computerRoomId > MAX_COMPUTER_ROOM_ID) {
            throw new IllegalArgumentException("computerRoomId 不在范围");
        }

        if (machineId < 0 || machineId > MAX_MACHINE_ID) {
            throw new IllegalArgumentException("computerRoomId 不在范围");
        }

        this.computerRoomId = computerRoomId;
        this.machineId = machineId;
    }

    /**
     * @return 返回毫秒级时间戳
     */
    private long getCurrentTime() {
        return System.currentTimeMillis();
    }

    /**
     * @return 雪花刷法生成 id
     */
    public synchronized long getNextId() {
        // 拿到时间戳
        long currentTimeStamp = getCurrentTime();

        // 时间戳回拨问题
        if (currentTimeStamp < lastTimeStamp) {
            throw new RuntimeException(
                    String.format("可能出现服务器时钟回拨问题，
                    请检查服务器时间。当前服务器时间戳：%d，
                     上一次使用时间戳：%d", currentTimeStamp,
                            lastTimeStamp));
        }

        // 时间为同一毫秒时间,sequence + 1
        if (currentTimeStamp == lastTimeStamp) {
            // 序列号 + 1
            sequence = (sequence + 1) & SEQUENCE_MASK;
            // 序列号用完
            if (sequence == 0) {
                // 获取下一个毫秒级
                currentTimeStamp = getNextMillis();
            }
        } else {
            sequence = 0;
        }

        // 记录上一次时间戳
        lastTimeStamp = currentTimeStamp;
        // 生成唯一id
        return ((currentTimeStamp - FIX_TIME_STAMP) << TIME_STAMP_SHIFT) |
                (computerRoomId << COMPUTER_ROOM_ID_SHIFT) |
                (machineId << MACHINE_ID_SHIFT) |
                sequence;
    }

    /**
     * @return 下一毫秒
     */
    private long getNextMillis() {
        long currentTimeStamp = getCurrentTime();
        while (currentTimeStamp <= lastTimeStamp) {
            currentTimeStamp = getCurrentTime();
        }
        return currentTimeStamp;
    }

}

springBoot整合雪花算法

配置yaml

SnowFlake:
  computerRoomId: 0
  machineId: 0

引入上面编写的SnowFlake算法文件，注意加入@service注解

编写SnowFlakeConfig配置文件

package com.java265.config;

import com.java265.utils.SnowFlake;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Slf4j
@Configuration
public class SnowFlakeConfig {
    @Value("${SnowFlake.computerRoomId}")
    private long computerRoomId;

    @Value("${SnowFlake.machineId}")
    private long machineId;

    @Bean
    public SnowFlake snowFlake() {
        return new SnowFlake(computerRoomId,machineId);
    }
}

测试雪花算法

package com.java265;

import com.java265.utils.SnowFlake;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
class DemoApplicationTests {

	@Autowired
	SnowFlake snowFlake;

	@Test
	void contextLoads() {
	    //生成100个雪花算法
		for (int i = 0; i < 100; i++) {
			long flakeId = snowFlake.getNextId();
			System.out.println(i + " = " +flakeId);
		}
	}
}

算法优缺点

雪花算法优点：
  高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
  基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
  不依赖第三方库或者中间件。
  算法简单，在内存中进行，效率高。

雪花算法缺点：
  依赖服务器时间
  服务器时钟回拨时可能会生成重复 id
   算法中可通过记录最后一个生成 id 时的时间戳来解决
    每次生成 id 之前比较当前服务器时钟是否被回拨
    避免生成重复 id。