PHP は分散一意の ID を生成するために Snowflake を実装します

Twitter のスノーフレークは、一意の UUID の分散生成に広く使用されており、インターネット上にはスノーフレークのいくつかの変種に基づいたアルゴリズムが多数存在します。 Snowflake を使用して生成された多くの UUID は分散シナリオで使用されており、スレッド セーフを考慮せずに PHP を実装しているインターネット上の記事をいくつか読みました。

PHP が Swoole のロックとコルーチンをサポートするようになったので、スレッドセーフで同時実行性の高いシミュレーションを開発するのに非常に便利です。ここでは、PHP と Swoole を組み合わせて使用​​し、最も単純なスノーフレーク (長いこと書いていない）PHP、IDEがないとPHPは書けない気がする）。

まず、次のスノーフレーク構造を見てみましょう:

生成された値は 64 ビットで、4 つの部分に分割されます:

# 最初に各ビットは符号ビットで、最上位ビットは 0 で、正の数を示します。

# 2 番目の部分の 41 ビットは、ID 生成時のタイムスタンプをミリ秒単位で記録するために使用されるため、値はこの部分で表される範囲は 2^ 41 - 1 (69 年) で、これは特定の時刻を基準としたオフセットです。

# 3 番目の部分の 10 ビットは、動作中のノードの ID と値を表します。範囲は 2^10 - 1 で、これは「1024 ノードをサポートする」と同等です。

#● 12 ビットの 4 番目の部分は、各動作ノードによってミリ秒ごとに生成される周期的な自動インクリメント ID を表します。最大 2 個生成できます。 ^12 -1 ID。ゼロを超える場合は、次のミリ秒を待ちます。再インクリメント

まずコードを貼り付けます:

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

実際、ロジックは複雑ではありません。コード内のビット演算:

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

は、-1 を 1 として表すバイナリ表現です。 補数コードは実際には次と同等です:

2**self::SEQUENCE_BITS - 1

最後の部分は左シフトされてから OR されます:

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

ここでは主に、最初の符号ビットを除く 3 つの部分を左シフトします。オフセットにより元の位置に戻り、OR 演算を通じて上記のスノーフレーク構造に再統合されます。たとえば、 3 を使用します。マージ操作を示すためのパーツと 4 ビット:

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

Swoole のコルーチンとチャネルを使用して、生成された ID に重複があるかどうかを確認する総当たりテストを実行してみましょう:

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

実行後ちなみに、Golang を使って Snowflake を実装して並列実行したところ、同じテストを行った結果、PHP の実行時間は約 12 秒でしたが、Golang では 1 秒しかかかりませんでした。記事内に間違いがございましたら訂正させていただきますので、よろしくお願いいたします。

以上がPHP は分散一意の ID を生成するために Snowflake を実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。