Java에서 눈송이 알고리즘을 구현하는 코드를 작성하는 방법

1. 소개

SnowFlow 알고리즘은 Twitter에서 출시한 분산 ID 생성 알고리즘입니다. 주요 핵심 아이디어는 64비트 길이의 숫자를 전역 ID로 사용하는 것입니다. 분산 시스템에서 자주 사용되는데, ID에 타임스탬프 개념이 추가되어 기본적으로 반복되지 않고 계속해서 위쪽으로 증가합니다.

이 64비트 중 첫 번째 비트는 사용되지 않으며, 41비트는 밀리초로 사용되며, 10비트는 작업 기계 ID로 사용되며, 12비트는 일련번호로 사용됩니다. 아래 그림:

첫 번째 부분: 0, 이것은 부호 비트입니다. 왜냐하면 이진수의 첫 번째 비트가 1이면 음수이지만 우리가 생성하는 ID는 모두 양수이기 때문입니다. 비트는 기본적으로 모두 0

두 번째 부분: 41비트는 타임스탬프를 나타냅니다. 41비트는 최대 $2^{41} $-1의 숫자를 나타낼 수 있으며 2^{41}-1밀리초 값도 나타낼 수 있습니다. , 기본적으로 거의 69년입니다.

세 번째 부분: 5비트는 컴퓨터실 ID를 나타냅니다.

네 번째 부분: 5비트는 컴퓨터 ID를 나타냅니다.

다섯 번째 부분: 12비트는 전산실 ID를 나타내며, 표현된 일련번호는 이 밀리초 내에 특정 전산실의 특정 기계에서 동시에 생성된 ID의 일련번호, 0000 00000000입니다. 동일한 밀리초라면 , 그러면 이 눈송이 값이 증가합니다

간단히 말하면, 서비스 중 하나가 전역적으로 고유한 ID를 생성하려는 경우 SnowFlake 알고리즘을 배포하는 시스템에 요청을 보낼 수 있으며 SnowFlake 알고리즘 시스템은 고유한 ID를 생성합니다. ID.

이 알고리즘은 컴퓨터실에 있는 한 컴퓨터에서 동일한 밀리초 내에 고유 ID가 생성되도록 보장할 수 있습니다. 1밀리초 내에 여러 ID가 생성될 수 있지만 시퀀스 번호의 마지막 12비트로 구분됩니다.

이 알고리즘의 코드 구현 부분을 간략하게 살펴보겠습니다.

간단히 말하면 64비트 숫자의 각 비트 위치를 사용하여 서로 다른 플래그 비트를 설정하는 것입니다.

2. 코드 구현

package com.lhh.utils;

/**
 * @author liuhuanhuan
 * @version 1.0
 * @date 2022/2/21 22:33
 * @describe Twitter推出的分布式唯一id算法
 */
public class SnowFlow {
    //因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。

    //机器ID  2进制5位  32位减掉1位 31个
    private long workerId;
    //机房ID 2进制5位  32位减掉1位 31个
    private long datacenterId;
    //代表一毫秒内生成的多个id的最新序号  12位 4096 -1 = 4095 个
    private long sequence;
    //设置一个时间初始值    2^41 - 1   差不多可以用69年
    private long twepoch = 1585644268888L;
    //5位的机器id
    private long workerIdBits = 5L;
    //5位的机房id；。‘
    private long datacenterIdBits = 5L;
    //每毫秒内产生的id数 2 的 12次方
    private long sequenceBits = 12L;
    // 这个是二进制运算，就是5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 这个是一个意思，就是5 bit最多只能有31个数字，机房id最多只能是32以内
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    // -1L 二进制就是1111 1111  为什么？
    // -1 左移12位就是 1111  1111 0000 0000 0000 0000
    // 异或  相同为0 ，不同为1
    // 1111  1111  0000  0000  0000  0000
    // ^
    // 1111  1111  1111  1111  1111  1111
    // 0000 0000 1111 1111 1111 1111 换算成10进制就是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();
    }


    public SnowFlow() {
    }

    public SnowFlow(long workerId, long datacenterId, long sequence) {

        // 检查机房id和机器id是否超过31 不能小于0
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(
                    String.format("worker Id can&#39;t be greater than %d or less than 0",maxWorkerId));
        }

        if (datacenterId > maxDatacenterId || datacenterId < 0) {

            throw new IllegalArgumentException(
                    String.format("datacenter Id can&#39;t be greater than %d or less than 0",maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    // 这个是核心方法，通过调用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
        // 这个时候就得把seqence序号给递增1，最多就是4096
        if (timestamp == lastTimestamp) {

            // 这个意思是说一个毫秒内最多只能有4096个数字，无论你传递多少进来，
            //这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            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) {
//        System.out.println(1&4596);
//        System.out.println(2&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
//        System.out.println(6&4596);
        SnowFlow snowFlow = new SnowFlow(1, 1, 1);
        for (int i = 0; i < 22; i++) {
            System.out.println(snowFlow.nextId());
//		}
        }
    }
}

3. 알고리즘 장점과 단점

장점:

(1) 고성능 및 고가용성: 생성 시 문제 없음 데이터베이스에 종속되고 메모리에서 완전히 생성됩니다.

(2) 대용량: 초당 수백만 개의 자체 증가 ID를 생성할 수 있습니다.

(3) ID 자동 증가: 높은 인덱싱 효율성으로 데이터베이스에 저장됩니다.

단점:

시스템 시간과의 일관성에 의존합니다. 시스템 시간이 콜백되거나 변경되면 ID 충돌이나 중복이 발생할 수 있습니다(시계 재생으로 인한 ID 중복 문제)

위 내용은 Java에서 눈송이 알고리즘을 구현하는 코드를 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!