PHP implementiert Snowflake, um verteilte eindeutige IDs zu generieren

Twitters Snowflake wird häufig bei der verteilten Generierung eindeutiger UUIDs verwendet, und im Internet gibt es viele Algorithmen, die auf einigen Varianten von Snowflake basieren. Viele mit Snowflake generierte UUIDs werden in verteilten Szenarien verwendet. Ich habe im Internet mehrere PHP-Implementierungen gelesen, die die Thread-Sicherheit nicht berücksichtigen.

Da PHP jetzt die Sperren und Coroutinen von Swoole unterstützt, ist es für uns sehr praktisch, Thread-sichere Simulationen mit hoher Parallelität zu entwickeln. Hier verwenden wir PHP in Kombination mit Swoole, um zu lernen, wie man die einfachste Schneeflocke implementiert (. Ich habe es schon lange nicht mehr geschrieben) PHP, ich habe das Gefühl, dass ich PHP nicht ohne eine IDE schreiben kann).

Sehen Sie sich zunächst die folgende Schneeflockenstruktur an:

Der generierte Wert ist 64 Bit groß und in 4 Teile unterteilt:

● First Each Bit ist das Vorzeichenbit und das höchste Bit ist 0, was eine positive Zahl angibt

● Die 41 Bits im zweiten Teil werden verwendet, um den Zeitstempel bei der ID-Generierung in Millisekunden aufzuzeichnen, also den Wertebereich Dieser Teil stellt 2^ 41 - 1 (69 Jahre) dar, was den Versatz relativ zu einer bestimmten Zeit darstellt

● Die 10 Bits im dritten Teil repräsentieren die ID des Arbeitsknotens und den Wertebereich ist 2^10 - 1, was der Unterstützung von 1024 Knoten entspricht

● Der vierte Teil von 12 Bits stellt die zyklische, sich selbst erhöhende ID dar, die von jedem Arbeitsknoten jede Millisekunde generiert wird. Er kann bis zu 2^12 generieren -1 IDs. Wenn es Null überschreitet, wird auf die nächste Millisekunde gewartet.

Fügen Sie zuerst den Code ein:

<?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);
    }
}

Tatsächlich ist die Logik nicht kompliziert Operationen im Code:

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

ist die binäre Darstellung von -1 als 1. Das Zweierkomplement entspricht eigentlich:

2**self::SEQUENCE_BITS - 1

Der letzte Teil wird nach links verschoben und dann die ODER-Verknüpfung:

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

Hier geht es hauptsächlich darum, die drei Teile mit Ausnahme des ersten Vorzeichenbits an ihre ursprüngliche Position zurückzusetzen und sie durch eine ODER-Operation wieder in die obige Schneeflockenstruktur zu integrieren und 4 Bits, um den Zusammenführungsvorgang zu demonstrieren:

0000 0000 0010  --左移0位--> 0000 0000 0010
0000 0000 0100  --左移4位--> 0000 0100 0000 --或操作-->1000 0100 0010
0000 0000 1000  --左移8位--> 1000 0000 0000

Lassen Sie uns die Coroutine und den Kanal von Swoole verwenden, um einen Brute-Force-Test durchzuführen, um zu sehen, ob es Duplikate in den generierten IDs gibt:

$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";

Nach dem Ausführen , es wird tatsächlich keine doppelten IDs geben. Ich habe übrigens auch Golang verwendet, um Snowflake zu implementieren und im Co-Programmiermodus auszuführen. Nach dem gleichen Test beträgt die Ausführungszeit von PHP etwa 12 Sekunden, und Golang dauert nur 1 Sekunde . Bitte korrigieren Sie mich, wenn der Artikel Fehler enthält. Vielen Dank.

Das obige ist der detaillierte Inhalt vonPHP implementiert Snowflake, um verteilte eindeutige IDs zu generieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!