PHP implémente Snowflake pour générer des identifiants uniques distribués

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 ne l'ai pas écrit depuis longtemps) PHP, j'ai l'impression que je ne peux pas écrire PHP sans IDE).

Regardez d'abord la structure de flocon de neige suivante :

La valeur générée est de 64 bits et divisée en 4 parties :

● Première chaque bit est le bit de signe, et le bit le plus élevé est 0, indiquant un nombre positif

● Les 41 bits de la deuxième partie sont utilisés pour enregistrer l'horodatage lorsque l'ID est généré, en millisecondes, donc la plage de valeurs représenté par cette partie est 2^ 41 - 1 (69 ans), qui est le décalage par rapport à un certain temps

● Les 10 bits de la troisième partie représentent l'ID du nœud de travail, et 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 cyclique à croissance automatique 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.

Collez 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 <= $this->timestamp) {
                    $now = $this->now();
                }
            }
        } else {
            $this->sequence = 0;
        }
        $this->timestamp = $now;    // 更新ID生时间戳
        $id = (($now - self::EPOCH) << self::TIME_SHIFT) | ($this->workerId << self::WORKER_SHIFT) | $this->sequence;
        $this->lock->unlock();  //解锁
        return $id;
    }
    /**
     * 获取当前毫秒
     * @return string
     */
    public function now()
    {
        return sprintf("%.0f", microtime(true) * 1000);
    }
}

En fait, la logique n'est pas compliquée. le code :

-1 ^ (-1 << self::SEQUENCE_BITS)

est la représentation binaire de -1 sous la forme 1 Le complément à deux est en fait équivalent à :

2**self::SEQUENCE_BITS - 1

La dernière partie est décalée vers la gauche puis l'opération OU :

(($now - self::EPOCH) << self::TIME_SHIFT) | ($this->workerId << self::WORKER_SHIFT) | $this->sequence;

Ici, il s'agit principalement de décaler à gauche les trois parties sauf le premier bit de signe. Le décalage le ramène à sa position d'origine, et est réintégré dans la structure du flocon de neige ci-dessus via une opération OU. 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

Utilisons la coroutine et le canal de Swoole pour faire un test de force brute pour voir s'il y aura des doublons dans les identifiants générés :

$snowflake = new Snowflake(1);
$chan = new chan(100000);
$n = 100000;
for ($i = 0; $i < $n; $i++) {
    go(function () use ($snowflake, $chan) {
        $id = $snowflake->getId();
        $chan->push($id);
    });
}
go(function () use ($chan, $n) {
    $arr = [];
    for ($i = 0; $i < $n; $i++) {
        $id = $chan->pop();  // PHP Swoole的channel一定要写在go(func)的协程里面！？
        if (in_array($id, $arr)) {
            exit("ID 已存在");
        }
        array_push($arr, $id);
    }
});
$chan->close();
echo "ok";

Après l'avoir exécuté, il y a Il n'y aura en effet pas d'identifiant en double. D'ailleurs, j'ai également utilisé Golang pour implémenter snowflake et l'exécuter en mode co-programme, le temps d'exécution de PHP est d'environ 12 secondes, et Golang ne prend 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!