So schreiben Sie Code zur Implementierung des Snowflake-Algorithmus in Java

1. Einführung

Der SnowFlow-Algorithmus ist ein von Twitter eingeführter verteilter ID-Generierungsalgorithmus. Die Hauptidee besteht darin, 64-Bit-lange Typnummern als globale IDs zu verwenden. Es wird häufig in verteilten Systemen verwendet und der ID wird das Konzept eines Zeitstempels hinzugefügt, wodurch sie sich grundsätzlich nicht wiederholt und weiterhin nach oben wächst.

In diesen 64 Bits wird das erste Bit nicht verwendet, und dann werden 41 Bits als Millisekunden verwendet, 10 Bits werden als Arbeitsmaschinen-ID verwendet und 12 Bits werden als Seriennummer verwendet Abbildung unten:

Der erste Teil: 0, das ist ein Vorzeichenbit, denn wenn das erste Bit im Binärformat 1 ist, dann ist es eine negative Zahl, aber die von uns generierten IDs sind alle positive Zahlen, also das erste Bit ist im Grunde alle 0

Der zweite Teil: 41 Bit, stellt einen Zeitstempel dar, der Zahlen bis zu $2^{41} $-1 darstellen kann, und kann auch 2^{41}-1 Millisekundenwerte darstellen. , im Grunde fast '69.

Der dritte Teil: 5 Bits stellen die Computerraum-ID dar.

Der vierte Teil: 5 Bits repräsentieren die Maschinen-ID.

Der fünfte Teil: 12 Bit stellen die Computerraum-ID dar, und die dargestellte Seriennummer ist die Seriennummer der ID, die gleichzeitig auf einer bestimmten Maschine in einem bestimmten Computerraum innerhalb dieser Millisekunde generiert wurde, 0000 00000000. Wenn es sich um dieselbe Millisekunde handelt , dann diese Schneeflocke Der Wert wird steigen

Einfach ausgedrückt: Wenn einer Ihrer Dienste eine global eindeutige ID generieren möchte, können Sie eine Anfrage an ein System senden, das den SnowFlake-Algorithmus bereitstellt, und das SnowFlake-Algorithmussystem generiert eine eindeutige ID AUSWEIS.

Dieser Algorithmus kann garantieren, dass auf einer Maschine in einem Computerraum innerhalb derselben Millisekunde eine eindeutige ID generiert wird. Innerhalb einer Millisekunde können mehrere IDs generiert werden, sie werden jedoch durch die letzten 12 Bits der Sequenznummer unterschieden.

Werfen wir einen kurzen Blick auf den Code-Implementierungsteil dieses Algorithmus.

Kurz gesagt geht es darum, jede Bitposition in einer 64-Bit-Zahl zu verwenden, um verschiedene Flag-Bits zu setzen

2. Code-Implementierung

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. Vor- und Nachteile des Algorithmus

Vorteile:

(1) Hohe Leistung und Hohe Verfügbarkeit: kein Problem bei der Generierung. Abhängig von der Datenbank und vollständig im Speicher generiert.

(2) Große Kapazität: Millionen von sich selbst erhöhenden IDs können pro Sekunde generiert werden.

(3) Automatische ID-Inkrementierung: In der Datenbank gespeichert, mit hoher Indizierungseffizienz.

Nachteile:

hängt von der Konsistenz mit der Systemzeit ab. Wenn die Systemzeit zurückgerufen oder geändert wird, kann es zu ID-Konflikten oder Duplikaten kommen (ID-Duplizierungsprobleme, die durch die Uhrwiedergabe verursacht werden)

Das obige ist der detaillierte Inhalt vonSo schreiben Sie Code zur Implementierung des Snowflake-Algorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!