PHP 實作 Snowflake 產生分散式唯一 ID

Twitter 的 snowflake 在分散式產生唯一 UUID 應用還是蠻廣泛的，基於 snowflake 的一些變種的演算法網上也有不少。使用 snowflake 產生 UUID 很多都是在分散式場景下使用，我看了下網路上有幾篇 PHP 實作的都沒有考慮到線程安全。

現在PHP 有了Swoole 的鎖和協程的加持，對於我們開發線程安全和高並發模擬還是很方便的，這裡用PHP 結合Swoole 來學習下實現最簡單的snowflake（好久沒寫PHP，我覺得沒有IDE 真寫不了PHP 了）。

先來看以下snowflake 的結構：

#產生的數值是64 位，分成4 個部分：

● 第一個bit 為符號位，最高位元為0 表示正數

● 第二部分41 個bit 用於記錄產生ID 時候的時間戳，單位為毫秒，所以該部分所表示的數值範圍為2^ 41 - 1（69 年），它是相對於某一時間的偏移量

● 第三部分的10 個bit 表示工作節點的ID，表示數值範圍為2^10 - 1，相當於支援1024 個節點

● 第四部分12 個bit 表示每個工作節點沒毫秒產生的循環自增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

最後部分左移後或運算：

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

這裡主要是對除了第一位符號位以外的三個部分進行左移相應的偏移量使其歸位，並透過或運算重新整合成上面snowflake 的結構，例如我們用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 的協程和channel 來暴力測試一下，看看生成的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";

跑了一下，確實不會出現重複的ID，對了，我用Golang 同樣實現了snowflake 並協程序方式跑了同樣的測試，PHP 的執行時間大約是12 秒左右，Golang 只需要1 秒。文章有什麼錯誤還請指正，謝謝。

以上是PHP 實作 Snowflake 產生分散式唯一 ID的詳細內容。更多資訊請關注PHP中文網其他相關文章！