分布式唯一ID的几种实现

by: nestor 邵泰深 2019-12-29

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

什么是分布式唯一ID

这是一个老生常谈的话题了，随着业务系统的发展，数据日渐增长，我们需要对数据库进行分库分表，并逐渐形成分布式系统，这时就需要有一个全局唯一的ID来满足我们的需求。

对于这个ID我们有以下要求：

全局唯一性：不能生成重复的ID，这是最基本的要求
趋势递增：由于在MySQL InnoDB引擎中使用的是聚集索引（cluster index），所以尽量使用有序的主键可以保证写入性能
信息安全：不能轻易被人按照ID去遍历数据，或者根据ID猜出业务

UUID

UUID(Universally Unique Identifier)的 16 个 8 位字节表示为 32 个十六进制（基数16）数字，显示在由连字符分隔 ‘-‘ 的五个组中，格式为”8-4-4-4-12”，总共 36 个字符

示例：123e4567-e89b-12d3-a456-426655440000，到目前为止业界一共有5种方式生成UUID，详情可见IETF发布的UUID规范

优点：

性能非常高，本地生成ID，不需要进行远程调用

缺点：

不易于存储，36位字符串过长，常见优化方案为转化为两个uint64整数存储或者截取部分字符串进行存储，后者无法保证唯一性
无法保证趋势递增

Redis生成ID

Redis是单线程的，可以用来生成全局唯一ID，主要通过原子操作 INCR 和 INCRBY 来实现

比如说生成每天从0开始的流水号，流水号格式为日期+当日增长号，我们通过每天在Redis中生成一个key，使用INCR去累加就可以很方便的实现这个需求

优点：

不依赖于数据库，灵活方便，且性能优于数据库
可以保证趋势递增

缺点：

需要对Redis的数据持久化处理，否则挂了就有可能生成重复ID

Twitter 开源的 Snowflake 算法

这种方案的核心思想是通过划分命名空间把一个long型的数来生成全局唯一ID，如下图把64 bit分别划分成多段，分开来标示机器、时间等：

41bit作为毫秒数，可以表示69年的时间

10 bit作为机器编号，5 bit数据中心ID，5 bit机器ID，相当于最多支持部署1024个节点

12 bit作为毫秒内序列号，相当于支持每个节点每毫秒生成4096个序列号

优点：

可以保证趋势递增
灵活，可以根据自身业务需求分配bit含义
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。

缺点：

强依赖机器时钟，如果机器上时钟回拨，可能会导致ID重复

下面是PHP简单实现Snowflake：

<?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;    // 序号

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

    /**
     * 生成ID
     *
     * @return int
     */
    public function getId()
    {
        $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;

        return $id;
    }

    /**
     * 获取当前毫秒
     *
     * @return string
     */
    public function now()
    {
        return sprintf("%.0f", microtime(true) * 1000);
    }
}