Explication détaillée de l'algorithme SnowFlake pour générer un identifiant unique en PHP

Qu'est-ce que l'algorithme du flocon de neige ? Tout d'abord, permettez-moi de poser une question : comment générer un identifiant unique dans un système distribué et maintenir l'identifiant à augmenter de lui-même ? Il s'agit du scénario commercial le plus important sur Twitter, c'est pourquoi Twitter a lancé un algorithme de flocon de neige.

Avant-propos : J'ai récemment eu besoin de créer un système CMS, étant donné que les fonctions sont relativement simples et que les exigences sont flexibles, j'ai abandonné un système mature comme WP et j'en ai construit moi-même un relativement simple. L'URL de la page de détails de l'article doit être transformée dans un format d'URL pseudo-statique, c'est-à-dire que xxx.html xxx a envisagé d'utiliser directement une clé primaire auto-incrémentée, mais je pense que cela exposerait le nombre d'articles. a dit que la valeur initiale peut être définie plus haut, mais c'est toujours possible. Le nombre d'articles sur une période donnée est calculé via la différence d'ID, donc un algorithme capable de générer des ID uniques est nécessaire.

Les méthodes considérées incluent

1. l'utilisation directe des horodatages, ou une série de méthodes qui en dérivent

2. Le uuid fourni avec Mysql

Les deux méthodes ci-dessus peuvent être trouvées, donc je n'expliquerai pas grand chose

En fin de compte, j'ai choisi l'algorithme SnowFlake de Twitter

L'avantage de cet algorithme est très simple. Il peut générer environ 4 millions d'identifiants différents à 16 chiffres (décimaux) par seconde.

Le principe est très simple

L'ID se compose d'une composition de 64 bits

Le premier bit est vacant

41 bits sont utilisés pour stocker l'horodatage en millisecondes

10 bits sont utilisés pour stocker l'identifiant de la machine

12 bits est utilisé pour stocker l'auto-ajout d'ID

À l'exception du bit le plus élevé marqué comme indisponible, les trois groupes de positions de bits restants peuvent être flottants, en fonction des besoins spécifiques de l'entreprise. Par défaut, l'horodatage de 41 bits peut prendre en charge l'utilisation de cet algorithme jusqu'en 2082, l'ID de machine de travail de 10 bits peut prendre en charge 1023 machines et le numéro de série prend en charge 1 milliseconde pour générer 4095 ID de séquence à incrémentation automatique.
Ce qui suit est le code source PHP

<?php
namespace App\Services;

abstract class Particle {
  const EPOCH = 1479533469598;
  const max12bit = 4095;
  const max41bit = 1099511627775;

  static $machineId = null;

  public static function machineId($mId = 0) {
    self::$machineId = $mId;
  }

  public static function generateParticle() {
    /*
    * Time - 42 bits
    */
    $time = floor(microtime(true) * 1000);

    /*
    * Substract custom epoch from current time
    */
    $time -= self::EPOCH;

    /*
    * Create a base and add time to it
    */
    $base = decbin(self::max41bit + $time);


    /*
    * Configured machine id - 10 bits - up to 1024 machines
    */
    if(!self::$machineId) {
      $machineid = self::$machineId;
    } else {
      $machineid = str_pad(decbin(self::$machineId), 10, "0", STR_PAD_LEFT);
    }
    
    /*
    * sequence number - 12 bits - up to 4096 random numbers per machine
    */
    $random = str_pad(decbin(mt_rand(0, self::max12bit)), 12, "0", STR_PAD_LEFT);

    /*
    * Pack
    */
    $base = $base.$machineid.$random;

    /*
    * Return unique time id no
    */
    return bindec($base);
  }

  public static function timeFromParticle($particle) {
    /*
    * Return time
    */
    return bindec(substr(decbin($particle),0,41)) - self::max41bit + self::EPOCH;
  }
}

?>

La méthode d'appel est la suivante

Particle::generateParticle($machineId);//生成ID
Particle::timeFromParticle($particle);//反向计算时间戳

Ici, j'ai apporté une amélioration. Si l'ID de la machine passe à 0, les 10 bits seront supprimés car parfois nous ne pouvons pas utiliser autant d'ID

Ce qui précède représente l’intégralité du contenu de cet article, j’espère qu’il sera utile à tout le monde pour apprendre.

Recommandations associées :

php生 ennuméro uniqueid résumé de la méthode, php génère dans id résumé

[php] mysql global ID génère dans le schéma , phpmysql global id

php génère Explication détaillée de la méthode pour devenir le seul identifiant

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!