PHP implements Snowflake to generate distributed unique IDs

Twitter’s snowflake is widely used in distributed generation of unique UUIDs, and there are many algorithms based on some variants of snowflake on the Internet. Many UUIDs generated using snowflake are used in distributed scenarios. I have read several articles on the Internet that implement PHP without considering thread safety.

Now that PHP has the support of Swoole's locks and coroutines, it is very convenient for us to develop thread-safe and high-concurrency simulations. Here we use PHP combined with Swoole to learn to implement the simplest snowflake (I haven't written it for a long time) PHP, I feel like I can’t write PHP without an IDE).

Let’s first look at the following snowflake structure:

The generated value is 64 bits and divided into 4 parts:

● First Each bit is the sign bit, and the highest bit is 0, indicating a positive number

● The 41 bits in the second part are used to record the timestamp when the ID is generated, in milliseconds, so the value range represented by this part is 2^ 41 - 1 (69 years), which is the offset relative to a certain time

● The 10 bits in the third part represent the ID of the working node, and the value range is 2^10 - 1, which is equivalent to To support 1024 nodes

● The fourth part of 12 bits represents the cyclic auto-increment ID generated by each working node every millisecond. It can generate up to 2^12 -1 IDs. If it exceeds zero, it will wait for the next millisecond. Re-increment

First paste the 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);
    }
}

In fact, the logic is not complicated. Explain the bit operations in the code:

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

is the binary representation of -1 as 1 The complement code is actually equivalent to:

2**self::SEQUENCE_BITS - 1

The last part is left shifted and then ORed:

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

Here is mainly the left shift of the three parts except the first sign bit. The offset makes it return to its original position, and is reintegrated into the above snowflake structure through an OR operation. For example, we use 3 parts and 4 bits to demonstrate the merge operation:

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

Let’s use Swoole’s coroutine and channel to Do a brute force test to see if there will be duplicates in the generated IDs:

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

After running it, there are indeed no duplicate IDs. By the way, I also used Golang to implement snowflake and run it in parallel. After the same test, the execution time of PHP is about 12 seconds, and Golang only takes 1 second. Please correct me if there are any errors in the article, thank you.

The above is the detailed content of PHP implements Snowflake to generate distributed unique IDs. For more information, please follow other related articles on the PHP Chinese website!