Bagaimana untuk menulis kod untuk melaksanakan algoritma kepingan salji di Jawa

1. Pengenalan

Algoritma SnowFlow ialah algoritma penjanaan ID teragih yang dilancarkan oleh Twitter Idea teras utama ialah menggunakan nombor jenis panjang 64-bit sebagai ID global. Ia sering digunakan dalam sistem yang diedarkan, dan konsep cap masa ditambah pada ID, yang pada asasnya memastikan ia tidak berulang dan terus meningkat secara menaik.

Dalam 64 bit ini, bit pertama tidak digunakan, dan kemudian 41 bit digunakan sebagai milisaat, 10 bit digunakan sebagai ID mesin yang berfungsi, dan 12 bit digunakan sebagai nombor siri seperti yang ditunjukkan dalam rajah di bawah Mewakili:

Bahagian pertama: 0, ini adalah bit tanda, kerana jika bit pertama dalam binari ialah 1, maka ia adalah negatif nombor, tetapi kami menjana ID ini semuanya nombor positif, jadi bit pertama pada asasnya ialah 0

Bahagian kedua: 41 bit, mewakili cap masa, 41 bit boleh mewakili sehingga $2^{41 } $-1 , juga boleh mewakili nilai 2^{41}-1 milisaat, yang pada asasnya hampir 69 tahun.

Bahagian ketiga: 5 bit mewakili ID bilik komputer.

Bahagian keempat: 5 bit mewakili ID mesin.

Bahagian kelima: 12 bit mewakili id ​​bilik komputer, dan nombor siri yang diwakili ialah nombor siri id yang dijana secara serentak pada mesin tertentu dalam bilik komputer tertentu dalam milisaat ini, 0000 00000000, jika ia adalah milisaat yang sama, maka nilai kepingan salji akan meningkat

Ringkasnya, jika salah satu perkhidmatan anda ingin menjana id unik secara global, maka anda boleh menghantar permintaan kepada sistem yang menggunakan algoritma SnowFlake ini sistem algoritma untuk menghasilkan id unik.

Algoritma ini boleh menjamin bahawa ID unik dijana pada mesin dalam bilik komputer dalam milisaat yang sama. Berbilang ID boleh dijana dalam satu milisaat, tetapi ia dibezakan oleh 12 bit terakhir nombor jujukan.

Mari kita lihat secara ringkas pelaksanaan kod algoritma ini.

Ringkasnya, ia adalah untuk menggunakan setiap kedudukan bit dalam nombor 64-bit untuk menetapkan bendera yang berbeza

2 Pelaksanaan kod

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 keburukan

Kelebihan:

(1) Prestasi tinggi dan ketersediaan tinggi: ia tidak bergantung pada pangkalan data semasa menjana, dan dijana sepenuhnya dalam ingatan.

(2) Kapasiti besar: berjuta-juta ID yang meningkat sendiri boleh dijana sesaat.

(3) Kenaikan automatik ID: disimpan dalam pangkalan data, dengan kecekapan pengindeksan yang tinggi.

Kelemahan:

bergantung pada ketekalan dengan masa sistem Jika masa sistem dipanggil semula atau ditukar, ia boleh menyebabkan konflik atau pertindihan ID (masalah penduaan ID yang disebabkan oleh main semula jam)

Atas ialah kandungan terperinci Bagaimana untuk menulis kod untuk melaksanakan algoritma kepingan salji di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!