KUID : identificateur universel unique compressé

KUID, un identifiant universellement unique, est essentiellement une version plus courte d’un UUID et est couramment utilisé pour identifier des enregistrements dans diverses applications.

Qu’est-ce que l’UUID ?

Un UUID (Universally Unique Identifier) ​​est un identifiant unique largement utilisé dans diverses applications et systèmes pour identifier les enregistrements. Il s’agit d’un nombre de 128 bits généralement représenté par une séquence de 32 chiffres hexadécimaux, regroupés en 5 sections, séparées par des tirets, comme dans le format suivant : xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx.

Les UUID sont conçus pour être uniques au monde, ce qui signifie qu’il est extrêmement peu probable que deux UUID soient identiques, même lorsqu’ils sont générés indépendamment par des systèmes différents. Cela rend les UUID utiles pour identifier et suivre les enregistrements dans les systèmes distribués, les bases de données et d’autres contextes où une identification unique est nécessaire.

Il existe différentes variantes et versions d’UUID, chacune avec sa propre façon de générer des identifiants uniques. Certaines variantes couramment utilisées incluent UUIDv1, UUIDv4 et UUIDv5. La variante et la version spécifiques d’un UUID peuvent être déterminées à partir du format et du contenu de l’identifiant.

Le KUID est généré en deux étapes

• Générer un UUID (utiliser n’importe quel algorithme comme V1, V2, V3, V4, etc.)
• Encoder un nombre 128 bits

KUID = Générer un UUID et l’encoder dans la base supérieure comme la base 32, 36 ou 62 ou même supérieure.

func encoder
   input: number # 128 bit number 
   output: encoded string 
   

func KUID:
  input UUID, encoder
  output KUID 
  return encode.encode( UUID )

La longueur du KUID dépend du schéma de codage utilisé. Si le schéma d’encodage base62 ([0–9A-Za-z]) est utilisé, KUID peut être encodé sur 22 octets. Cependant, si vous souhaitez stocker KUID en majuscules, codez-le à l’aide du schéma de codage base36, qui utilise des caractères [0–9A-Z], se traduira par une représentation codée pouvant être stockée sur 26 octets. Pour cet article, nous allons baser l’encodage 62.

Pourquoi devrions-nous utiliser KUID ?

KUID génère une chaîne plus petite, ce qui réduit l’espace de stockage et accélère le traitement de nombreuses opérations.

REMARQUE : Les instructions suivantes ne sont valides que lorsque KUID est traité comme une chaîne, et non comme un nombre de 128 bits.

• Hachage : L’utilisation de KUID avec sa longueur plus courte de 22 octets réduit la quantité de données à hacher. Il en résulte que moins d’instructions sont nécessaires pour effectuer l’opération de hachage par rapport à UUID, qui nécessite un hachage de 36 octets.
• Comparaison: En raison de la longueur plus courte de KUID, seuls 22 octets doivent être comparés au lieu de 36 octets, ce qui réduit le nombre d’instructions nécessaires à la comparaison.
• Lire écrire: L’utilisation de KUID, qui peut être codé sur 22 octets, entraîne une réduction de la mémoire et de l’espace disque requis pour les opérations de lecture et d’écriture. Cela contraste avec UUID, qui nécessite 36 octets pour les mêmes opérations. Avec KUID, moins d’instructions sont nécessaires pour lire ou écrire des données en raison de sa taille plus petite.
• Appels IO : L’envoi d’un UUID sur un réseau consomme 36 octets de données (sans tenir compte de la compression), tandis qu’un KUID ne nécessite que 22 octets. Par conséquent, KUID est un choix plus efficace pour la transmission réseau en raison de sa petite taille.
• Indexation de la base de données: En raison de la taille réduite du KUID, cela entraîne une diminution de la taille de l’index de la base de données. De plus, combiner KUID avec une autre colonne pour l’indexation secondaire peut être avantageux car les bases de données ont une largeur d’index limitée (par exemple, 767 octets dans MySQL) qui dépend de l’encodage utilisé pour la colonne ou la table. Par exemple, l’encodage UTF8 de MySQL peut limiter la largeur de l’index à seulement 255 octets.
• URL sûre: Comme UUID, KUID est sûr pour les URL puisqu’il n’utilise que [0–9A-Za-z] caractères pour représenter les données. KUID est couramment utilisé comme colonne unique, ce qui signifie que les URL contenant des KUID peuvent être utilisées pour représenter des ressources spécifiques, telles que /api/v1/products/:productId. Comme le KUID est inclus dans l’URL, il doit être sûr pour l’URL afin d’éviter des problèmes tels que des erreurs d’encodage ou une interprétation involontaire par le serveur Web ou le navigateur.
• Utilisation réduite de la mémoire/du disque: L’utilisation de KUID réduit l’utilisation de la mémoire/du disque par rapport à UUID. Étant donné que KUID ne nécessite que 22 octets, il utilise moins d’espace de stockage que UUID, qui utilise 36 octets. Cela peut être avantageux pour les systèmes qui nécessitent des opérations de lecture/écriture fréquentes ou qui ont une capacité de stockage limitée. Par exemple, si nous considérons le stockage de 200 millions d’enregistrements, en supposant que chaque KUID est stocké sous la forme d’une chaîne de 22 octets, l’espace consommé par les KUID serait d’environ 4,4 Go. En revanche, l’espace requis pour les UUID serait d’environ 7,2 Go. Par conséquent, l’utilisation de KUID peut entraîner une économie de stockage d’environ 39 %.

Implémentation Java :

/*
 * Copyright (c) 2023 Sonu Kumar, sonunitw12@gmail.com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * You may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and limitations under the License.
 *
 */
package sonus21.github.com;

import java.util.UUID;

/**
 * KUID, a universally unique identifier, is essentially a shorter version of a UUID due to BASE 62 encoding
 * <p>
 * This KUID implementation always generate 22 bytes string, but it can be further reduced.
 * <p>
 * For details read <a href="https://sonus21.medium.com/8aaa5d83368">KUID: Compressed Universally Unique Identifier</a>
 */

public class KUID implements java.io.Serializable, Comparable<KUID> {
    private static final long serialVersionUID = -485684636193249489L;

    private static final String BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    private static final int BASE = BASE62.length();
    private final long msb;
    private final long lsb;


    private KUID(long msb, long lsb) {
        this.msb = msb;
        this.lsb = lsb;
    }

    // A naive method to encode number to Base62
    private static String encodeLong(long value) {
        int size = 11;
        StringBuilder sb = new StringBuilder(size);
        while (value != 0) {
            int index = (int) (value % BASE);
            value = value / BASE;
            // for negative number flip the order instead of error it out as we need to encode all 64 bits
            if (index < 0) {
                index = BASE + index;
            }
            sb.insert(0, BASE62.charAt(index));
        }
        while (sb.length() < size) {
            sb.insert(0, BASE62.charAt(0));
        }
        return sb.toString();
    }


    /**
     * Static factory to retrieve a KUID from UUID
     *
     * @param uuid the UUID object
     * @return KUID object
     */
    public static KUID fromUUID(UUID uuid) {
        if (uuid == null) {
            throw new IllegalArgumentException("uuid can not be null");
        }
        return new KUID(uuid.getMostSignificantBits(), uuid.getMostSignificantBits());
    }

    /**
     * Static factory to retrieve a pseudo randomly generated KUID
     * <p>
     * The {@code KUID} is generated using a random UUID.
     *
     * @return A randomly generated {@code KUID}
     */
    public static KUID randomKUID() {
        return fromUUID(UUID.randomUUID());
    }

    @Override
    public int compareTo(KUID o) {
        return (msb < o.msb ? -1 :
                (msb > o.msb ? 1 :
                        (Long.compare(lsb, o.lsb))));
    }


    /**
     * Returns a {@code String} object representing this {@code KUID}.
     *
     * @return A string representation of this {@code KUID}
     */
    @Override
    public String toString() {
        return encodeLong(msb) + encodeLong(lsb);
    }

    /**
     * Returns a hash code for this {@code KUID}.
     *
     * @return A hash code value for this {@code KUID}
     */
    @Override
    public int hashCode() {
        long xor = msb ^ lsb;
        return ((int) (xor >> 32)) ^ (int) xor;
    }


    /**
     * Compares this object to the specified object.  The result is {@code
     * true} if and only if the argument is not {@code null}, is a {@code KUID}
     * object, and contains the same value.
     *
     * @param obj The object to be compared
     * @return {@code true} if the objects are the same; {@code false} otherwise
     */
    public boolean equals(Object obj) {
        if (!(obj instanceof KUID)) {
            return false;
        }
        KUID id = (KUID) obj;
        return msb == id.msb && lsb == id.lsb;
    }
}

MAIS Utilisez :

public class Main {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            KUID kuid = KUID.randomKUID();
            System.out.println(kuid.toString());
        }

    }
}

Cela produira quelque chose comme ceci :

LJVa90PC5N0LJVa90PC5N0
8SYCyPz9NXp8SYCyPz9NXp
8ucdhnCeYdk8ucdhnCeYdk
7QaHvqldPIL7QaHvqldPIL
8031jRPF3DS8031jRPF3DS
9oec5uzuIpg9oec5uzuIpg
4EAtrqG7CmF4EAtrqG7CmF
1vywu4ZzLz71vywu4ZzLz7
19YC4JE4W7619YC4JE4W76
8al7UWmt4Q28al7UWmt4Q2