Problématique principale

Dans une architecture avec une seule base et une seule table, l'utilisation d'une clé primaire auto-incrémentée garantit l'unicité et l'ordre des identifiants. Cependant, après le partitionnement des données, si chaque fragment utilise son propre mécanisme d'auto-incrémentation, des chevauchements d'ID apparaissent à l'échelle globale, comme illustré ci-dessous :

Base de données 1 : Table_1 -> ID : 1, 2, 3, 5, 7...
Base de données 2 : Table_2 -> ID : 1, 2, 4, 6, 8...

À l'échelle du système, les identifiants ne sont plus uniques et ne respectent plus un ordre séquentiel global.

Approches de résolution

Plusieurs stratégies existent, depuis la couche applicative jusqu'au niveau base de données, chacune avec ses compromis.

1. Identifiants UUID

Utilisation d'un UUID (Universally Unique Identifier) comme clé primaire.

• Mise en œuvre : Génération côté applicatif d'une chaîne de 36 caractères, par exemple f47ac10b-58cc-4372-a567-0e02b2c3d479.
• Avantages :
  • Production décentralisée : Création locale sans appel réseau, offrant une excellente performance.
  • Unicité théorique : Probabilité de collision extrêmement faible.
• Inconvénients :
  • Espace de stockage élevé : Représentation textuelle volumineuse.
  • Désordre naturel : Défaut majeur qui provoque des fractions de pages fréquentes lors des insertions, dégradant fortement les performances en écriture.
  • Manque de lisibilité : Difficile à interpréter pour le débogage.

Bilan : Déconseillé comme solution principale pour les clés distribuées, sauf dans des contextes où les contraintes de performance et de stockage sont minimales.

2. Séquences en base de données (ex : TDDL Sequence)

S'appuyer sur une base de données dédiée pour générer des séquences uniques.

• Mise en œuvre : Configuration d'une instance de base distincte avec une table sequence. L'obtention d'un lot d'identifiants se fait via des opérations telles que REPLACE INTO ou des transactions, avec chargement en mémoire applicative.
• Avantages :
  • Identifiants numériques, séquentiels et intuitifs.
• Inconvénients :
  • Risque de point de défaillance unique et goulot d'étranglement potentiel.
  • Complexité architecturale : Nécessite la maintenance d'une infrastructure séquentielle hautement disponible.

Bilan : Solution historique, moins courante dans les architectures modernes en raison de ses risques opérationnels.

3. Algorithme Snowflake et ses variantes - Recommandé

Algorithme distribué pour la génération d'ID, open-sourcé par Twitter et devenu une référence.

• Principe : Production d'un nombre Long sur 64 bits avec la structure suivante : ``` 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

  
  
  - **1 bit de signe** : Toujours à 0.
  - **41 bits d'horodatage (en millisecondes)** : Couvre environ 69 ans.
  - **10 bits pour l'identifiant du nœud (DataCenter ID + Worker ID)** : Supporte jusqu'à 1024 instances.
  - **12 bits de séquence** : Permet 4096 identifiants par milliseconde et par nœud.
  

• Mise en œuvre :
  • Intégration directe dans les services applicatifs avec configuration d'un WorkerID unique par instance.
  • Déploiement en tant que service autonome (comme UidGenerator ou Leaf-snowflake) accessible via RPC.
• Avantages :
  • Haute performance : Génération locale, sans surcharge réseau.
  • Ordre chronologique : Les identifiants sont temporellement ordonnés, favorisant l'indexation en base.
  • Forte capacité : Peut produire des millions d'identifiants par seconde.
• Inconvénients :
  • Problème de régression d'horloge : Un désynchronisation de l'horloge serveur peut entraîner des doublons. Nécessite une gestion dans le code.
  • Allocation du Worker ID : Doit être garantie unique globalement.

Bilan : Solution la plus répandue et recommandée pour les environnements distribués. De nombreuses entreprises l'ont adaptée avec des variantes.

4. Leaf - Solution open-source de Meituan

Leaf est un système de génération d'ID distribué qui combine deux approches, améliorant le modèle Snowflake.

• Mode Leaf-snowflake :
  • Utilise ZooKeeper pour gérer automatiquement les Worker ID, simplifiant la configuration.
  • Optimise la gestion des régressions d'horloge : vérification au démarrée et pendant l'exécution ; en cas de décalage court, attente de rattrapage ; en cas de décalage important, arrêt du service pour intervention manuelle.
• Mode Leaf-segment :
  • Évolution de l'aproche par séquences en base. Au lieu d'obtenir un identifiant à la fois, récupère un lot (segment) depuis la base (ex : de 1 à 1000).
  • Le service charge le segment complet en mémoire et distribue les identifiants successivement. Après épuisement, un nouveau segment est récupéré.
  • Avantages : Réduit fortement la charge sur la base de données (une lecture pour 1000 ID), hautes performances et garantie d'ordre séquentiel absolu.
  • Inconvénients : Identifiants non continus mais incrémentés par segment. Au redémarrage, les identifiants non utilisés dans le segment courant sont perdus, créant des trous.

Bilan : Leaf est une solution mature de production, intégrant les avantages des deux modes, et constitue une implémentation robuste de Snowflake.

5. Modèle par segments (Segment)

Approche performante et simple, comme implémentée dans Leaf-segment.

• Mise en œuvre : Maintenance d'une table en base avec les champs biz_tag (type métier) et max_id (identifiant maximum). Chaque mise à jour incrémente max_id d'un pas (step) et retourne la nouvelle plage.
• Avantages :
  • Haute performance : Charge minimale sur la base de données.
  • Production d'identifiants globalement séquentiels.
  • Implémentation simple et flexible.
• Inconvénients :
  • Identifiants non continus mais incrémentés par segment.
  • Redémarrage du service pouvant gaspiller des identifiants.

Bilan : Idéal pour les scénarios nécessitant un ordre séquentiel strict, tolérant une faible perte d'idantifiants.

Tableau comparatif des solutions

Guide de choix

• Pour une architecture distribuée internet typique avec forte concurrence :
  • Privilégier Snowflake ou ses variantes (comme Leaf-snowflake). Conçu spécifiquement pour ce contexte.
• Pour un besoin strict d'ordre séquentiel absolu (ex : transactions financières) :
  • Envisager Leaf-segment (modèle par segments) ou une implémentation basée sur base de données avec segments.
• Pour des systèmes de moindre échelle, avec besoin de rapidité de mise en place :
  • Utiliser la commande INCR de Redis (principe similaire aux séquences en base, mais plus performante) ou un modèle par segments simple.
• Déconseiller l'utilisation pure d'UUID ou de séquences en base classiques comme solution principale pour le partitionnement de bases de données.