PHP implémente Snowflake pour générer un identifiant unique distribué

步履不停
Libérer: 2023-04-06 22:48:01
original
3980 Les gens l'ont consulté

PHP implémente Snowflake pour générer un identifiant unique distribué

Le flocon de neige de Twitter est largement utilisé dans la génération distribuée d'UUID uniques. Il existe également de nombreux algorithmes basés sur certaines variantes du flocon de neige sur Internet. De nombreux UUID générés à l'aide de Snowflake sont utilisés dans des scénarios distribués. J'ai lu plusieurs implémentations PHP sur Internet qui ne prenaient pas en compte la sécurité des threads. Maintenant que PHP prend en charge les verrous et les coroutines de Swoole, il est très pratique pour nous de développer des simulations thread-safe et à haute concurrence. Ici, nous utilisons PHP combiné avec Swoole pour apprendre à implémenter le flocon de neige le plus simple (je n'ai pas écrit). PHP depuis longtemps, et j'ai l'impression de ne pas avoir d'EDI. Je ne peux plus écrire PHP).

Regardez d'abord la structure de flocon de neige suivante :
PHP implémente Snowflake pour générer un identifiant unique distribuéLa valeur générée est de 64 bits, divisée en 4 parties :

  • Le premier bit est le bit de signe, le Le bit 0 le plus élevé indique un nombre positif
  • La deuxième partie de 41 bits est utilisée pour enregistrer l'horodatage lorsque l'ID est généré, en millisecondes, donc la plage de valeurs représentée par cette partie est 2 ^ 41 - 1 (69 ans), Il s'agit d'un décalage par rapport à un certain temps
  • Les 10 bits de la troisième partie représentent l'ID du nœud de travail, indiquant que la plage de valeurs est 2^10 - 1, ce qui équivaut à prendre en charge 1024 nœuds
  • La quatrième partie de 12 bits représente l'ID d'auto-incrémentation cyclique généré par chaque nœud de travail toutes les millisecondes. Il peut générer jusqu'à 2 ^ 12 -1 ID. S'il dépasse zéro, il attendra. la milliseconde suivante pour ré-incrémenter

Publiez d'abord le code :

<?php class Snowflake
{
    const EPOCH = 1543223810238;    // 起始时间戳,毫秒

    const SEQUENCE_BITS = 12;   //序号部分12位
    const SEQUENCE_MAX = -1 ^ (-1 << self::SEQUENCE_BITS);  // 序号最大值

    const WORKER_BITS = 10; // 节点部分10位
    const WORKER_MAX = -1 ^ (-1 << self::WORKER_BITS);  // 节点最大数值

    const TIME_SHIFT = self::WORKER_BITS + self::SEQUENCE_BITS; // 时间戳部分左偏移量
    const WORKER_SHIFT = self::SEQUENCE_BITS;   // 节点部分左偏移量

    protected $timestamp;   // 上次ID生成时间戳
    protected $workerId;    // 节点ID
    protected $sequence;    // 序号
    protected $lock;        // Swoole 互斥锁

    public function __construct($workerId)
    {
        if ($workerId < 0 || $workerId > self::WORKER_MAX) {
            trigger_error("Worker ID 超出范围");
            exit(0);
        }

        $this->timestamp = 0;
        $this->workerId = $workerId;
        $this->sequence = 0;
        $this->lock = new swoole_lock(SWOOLE_MUTEX);
    }

    /**
     * 生成ID
     * @return int
     */
    public function getId()
    {
        $this->lock->lock();    // 这里一定要记得加锁
        $now = $this->now();
        if ($this->timestamp == $now) {
            $this->sequence++;

            if ($this->sequence > self::SEQUENCE_MAX) {
                // 当前毫秒内生成的序号已经超出最大范围,等待下一毫秒重新生成
                while ($now timestamp) {
                    $now = $this->now();
                }
            }
        } else {
            $this->sequence = 0;
        }

        $this->timestamp = $now;    // 更新ID生时间戳

        $id = (($now - self::EPOCH) workerId sequence;
        $this->lock->unlock();  //解锁

        return $id;
    }

    /**
     * 获取当前毫秒
     * @return string
     */
    public function now()
    {
        return sprintf("%.0f", microtime(true) * 1000);
    }

}
Copier après la connexion

En fait, la logique n'est pas compliquée. Expliquez les opérations sur les bits dans le code :

-1 ^ (-1 <.>La dernière partie est décalée à gauche puis ORée : <p></p>
<pre class="brush:php;toolbar:false">(($now - self::EPOCH) workerId sequence;
Copier après la connexion
L'essentiel ici est de décaler les trois parties sauf le premier signe un peu vers la gauche du décalage correspondant, et de les réintégrer dans la structure en flocon de neige ci-dessus via l'opération OR. Par exemple, nous utilisons 3 parties et 4 bits pour démontrer l'opération de fusion :

0000 0000 0010  --左移0位--> 0000 0000 0010
0000 0000 0100  --左移4位--> 0000 0100 0000 --或操作-->1000 0100 0010
0000 0000 1000  --左移8位--> 1000 0000 0000
Copier après la connexion
Testons-la violemment à l'aide de la coroutine et du canal de Swoole pour voir si les identifiants générés seront répétés :

$snowflake = new Snowflake(1);

$chan = new chan(100000);
$n = 100000;

for ($i = 0; $i getId();
        $chan->push($id);
    });
}

go(function () use ($chan, $n) {
    $arr = [];
    for ($i = 0; $i pop();  // PHP Swoole的channel一定要写在go(func)的协程里面!?
        if (in_array($id, $arr)) {
            exit("ID 已存在");
        }
        array_push($arr, $id);
    }
});

$chan->close();

echo "ok";
Copier après la connexion
Après l'avoir exécuté, cela n'arrivera certainement pas. À propos, j'ai utilisé Golang pour implémenter snowflake et j'ai exécuté le même test en mode co-programme. 12 secondes, alors que Golang n'a pris que 1 seconde. Merci de me corriger s'il y a des erreurs dans l'article, merci.

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!

Étiquettes associées:
php
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!