Comment écrire du code pour implémenter l'algorithme de flocon de neige en Java

1. Introduction

L'algorithme SnowFlow est un algorithme de génération d'identifiants distribués lancé par Twitter. L'idée principale est d'utiliser des nombres de type 64 bits comme identifiants globaux. Il est souvent utilisé dans les systèmes distribués, et le concept d'horodatage est ajouté à l'ID, ce qui le maintient essentiellement non répétitif et continue d'augmenter de manière ascendante.

Dans ces 64 bits, le premier bit n'est pas utilisé, puis 41 bits sont utilisés comme millisecondes, 10 bits sont utilisés comme identifiant de la machine de travail et 12 bits sont utilisés comme numéro de série. figure ci-dessous :

La première partie : 0, c'est un bit de signe, car si le premier bit en binaire est 1, alors c'est un nombre négatif, mais les identifiants que nous générons sont tous des nombres positifs, donc le premier le bit est fondamentalement Ils sont tous 0

La deuxième partie : 41 bits, représente un horodatage. 41 bits peuvent représenter des nombres jusqu'à 2 $^{41} $-1, et peuvent également représenter des valeurs de 2^{41}-1 millisecondes. , en gros presque '69.

La troisième partie : 5 bits représentent l'identifiant de la salle informatique.

La quatrième partie : 5 bits représentent l'ID de la machine.

La cinquième partie : 12 bits représentent l'identifiant de la salle informatique, et le numéro de série représenté est le numéro de série de l'identifiant généré simultanément sur une certaine machine dans une certaine salle informatique dans cette milliseconde, 0000 00000000. Si c'est la même milliseconde , alors ce flocon de neige La valeur augmentera

En termes simples, si l'un de vos services souhaite générer un identifiant globalement unique, vous pouvez alors envoyer une demande à un système qui déploie l'algorithme SnowFlake, et le système d'algorithme SnowFlake générera un identifiant unique IDENTIFIANT.

Cet algorithme peut garantir qu'un identifiant unique est généré sur une machine dans une salle informatique dans la même milliseconde. Plusieurs identifiants peuvent être générés en une milliseconde, mais ils se distinguent par les 12 derniers bits du numéro de séquence.

Jetons un bref aperçu de la partie implémentation du code de cet algorithme.

En bref, il s'agit d'utiliser chaque position de bit dans un nombre de 64 bits pour définir différents bits de drapeau

2. Implémentation du code

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. Avantages et inconvénients de l'algorithme

Avantages :

(1) Hautes performances et haute disponibilité : aucun problème lors de la génération Dépendant de la base de données et généré entièrement en mémoire.

(2) Grande capacité : des millions d'identifiants auto-croissants peuvent être générés par seconde.

(3) Auto-incrémentation des identifiants : stockés dans la base de données, avec une efficacité d'indexation élevée.

Inconvénients :

repose sur la cohérence avec l'heure du système. Si l'heure du système est rappelée ou modifiée, cela peut provoquer des conflits d'ID ou des duplications (problèmes de duplication d'ID causés par la relecture de l'horloge)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!