Snowflake

算法介绍

Snowflake 是由 Twitter 提出的一个分布式全局唯一 ID 生成算法，算法生成 ID 的结果是一个 64bit 大小的长整，标准算法下它的结构如下图：

snowflake

  • 1 位，不用。

    • 二进制中最高位为符号位，我们生成的 ID 一般都是正整数，所以这个最高位固定是 0。

  • 41 位，用来记录时间戳（毫秒）。

    • 41 位 可以表示 2^41 - 1 个数字。
    • 也就是说 41 位 可以表示 2^41 - 1 个毫秒的值，转化成单位年则是 (2^41 - 1) / (1000 * 60 * 60 * 24 * 365) 约为 69 年。

  • 10 位，用来记录工作机器 ID。

    • 可以部署在 2^10 共 1024 个节点，包括 5 位 DatacenterId 和 5 位 WorkerId。

  • 12 位，序列号，用来记录同毫秒内产生的不同 id。

    • 12 位 可以表示的最大正整数是 2^12 - 1 共 4095 个数字，来表示同一机器同一时间截（毫秒)内产生的 4095 个 ID 序号。

Snowflake 可以保证：

  • 所有生成的 ID 按时间趋势递增。
  • 整个分布式系统内不会产生重复 ID（因为有 DatacenterId (5 bits) 和 WorkerId (5 bits) 来做区分）。

Hyperf 的 hyperf/snowflake 组件在设计上提供了很好的可扩展性，允许您通过简单的扩展就能实现其它基于 Snowflake 的变体算法。

安装

  1. composer require hyperf/snowflake

使用

框架提供了 MetaGeneratorInterface 和 IdGeneratorInterface，MetaGeneratorInterface 会生成 ID 的 Meta 文件，IdGeneratorInterface 则会根据对应的 Meta 文件生成 分布式 ID。

框架默认使用的 MetaGeneratorInterface 是基于 Redis 实现的 毫秒级别生成器。配置文件位于 config/autoload/snowflake.php，如配置文件不存在可通过执行 php bin/hyperf.php vendor:publish hyperf/snowflake 命令创建默认配置，配置文件内容如下：

  1. <?php
  3. declare(strict_types=1);
  5. use Hyperf\Snowflake\MetaGenerator\RedisMilliSecondMetaGenerator;
  6. use Hyperf\Snowflake\MetaGenerator\RedisSecondMetaGenerator;
  7. use Hyperf\Snowflake\MetaGeneratorInterface;
  9. return [
  10.     'begin_second' => MetaGeneratorInterface::DEFAULT_BEGIN_SECOND,
  11.     RedisMilliSecondMetaGenerator::class => [
  12.         // Redis Pool
  13.         'pool' => 'default',
  14.         // 用于计算 WorkerId 的 Key 键
  15.         'key' => RedisMilliSecondMetaGenerator::DEFAULT_REDIS_KEY
  16.     ],
  17.     RedisSecondMetaGenerator::class => [
  18.         // Redis Pool
  19.         'pool' => 'default',
  20.         // 用于计算 WorkerId 的 Key 键
  21.         'key' => RedisMilliSecondMetaGenerator::DEFAULT_REDIS_KEY
  22.     ],
  23. ];

框架中使用 Snowfalke 十分简单，只需要从 DI 中取出 IdGeneratorInterface 对象即可。

  1. <?php
  2. use Hyperf\Snowflake\IdGeneratorInterface;
  3. use Hyperf\Utils\ApplicationContext;
  5. $container = ApplicationContext::getContainer();
  6. $generator = $container->get(IdGeneratorInterface::class);
  8. $id = $generator->generate();

当知道 ID 需要反推对应的 Meta 时，只需要调用 degenerate 即可。

<?php
use Hyperf\Snowflake\IdGeneratorInterface;
use Hyperf\Utils\ApplicationContext;

$container = ApplicationContext::getContainer();
$generator = $container->get(IdGeneratorInterface::class);

$meta = $generator->degenerate($id);

重写 Meta 生成器

分布式全局唯一 ID 的实现方式多种多样，也有很多基于 Snowflake 算法的变体算法，虽然都是 Snowflake 算法，但也不尽相同。比如有人可能会根据 UserId 生成 Meta，而非 WorkerId。接下来，让我们实现一个简单的 MetaGenerator。简单的来讲，UserId 绝对会超过 10 bit，所以默认的 DataCenterId 和 WorkerId 肯定是装不过来的，所以就需要对 UserId 取模。

<?php

declare(strict_types=1);

use Hyperf\Snowflake\IdGenerator;

class UserDefinedIdGenerator
{
    /**
     * @var IdGenerator\SnowflakeIdGenerator
     */
    protected $idGenerator;

    public function __construct(IdGenerator\SnowflakeIdGenerator $idGenerator)
    {
        $this->idGenerator = $idGenerator;
    }

    public function generate(int $userId)
    {
        $meta = $this->idGenerator->getMetaGenerator()->generate();

        return $this->idGenerator->generate($meta->setWorkerId($userId % 31));
    }

    public function degenerate(int $id)
    {
        return $this->idGenerator->degenerate($id);
    }
}

use Hyperf\Utils\ApplicationContext;

$container = ApplicationContext::getContainer();
$generator = $container->get(UserDefinedIdGenerator::class);
$userId = 20190620;

$id = $generator->generate($userId);