Home >Backend Development >PHP Tutorial >PHP implements Snowflake to generate distributed unique ID

PHP implements Snowflake to generate distributed unique ID

步履不停
步履不停Original
2019-07-01 15:15:514070browse

PHP implements Snowflake to generate distributed unique ID

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 how to implement the simplest snowflake (I haven't written PHP for a long time, and I feel like I don't have an IDE. Can't write PHP anymore).

Let’s first look at the following snowflake structure:
PHP implements Snowflake to generate distributed unique IDThe generated value is 64 bits, divided into 4 parts:

  • The first bit is the sign bit, the highest Bit 0 indicates a positive number
  • The second part of 41 bits is 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), It is an offset relative to a certain time
  • The 10 bits in the third part represent the ID of the working node, indicating that the value range is 2^10 - 1, which is equivalent to supporting 1024 nodes
  • The 12 bits in the fourth part represent the cyclic self-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 to re-increment.

Post the code first:

<?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 timestamp) {
                    $now = $this->now();
                }
            }
        } else {
            $this->sequence = 0;
        }

        $this->timestamp = $now;    // 更新ID生时间戳

        $id = (($now - self::EPOCH) workerId 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 <p>The last part is shifted left and then ORed: </p><pre class="brush:php;toolbar:false">(($now - self::EPOCH) workerId sequence;

The main thing here is to shift the three parts except the first sign bit to the left by the corresponding offset, and reintegrate them into the above snowflake structure through the 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 violently test it with the help of Swoole’s coroutine and channel to see if the generated IDs will be repeated:

$snowflake = new Snowflake(1);

$chan = new chan(100000);
$n = 100000;

for ($i = 0; $i getId();
        $chan->push($id);
    });
}

go(function () use ($chan, $n) {
    $arr = [];
    for ($i = 0; $i pop();  // PHP Swoole的channel一定要写在go(func)的协程里面!?
        if (in_array($id, $arr)) {
            exit("ID 已存在");
        }
        array_push($arr, $id);
    }
});

$chan->close();

echo "ok";

After running it, it is indeed not the case Duplicate IDs appeared. By the way, I used Golang to implement snowflake and ran the same test in co-program mode. The execution time of PHP was about 12 seconds, while Golang only took 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 ID. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn