Varobj

2019-08-09

雪花算法 - PHP版本的简单实现



雪花算法是生成分布式唯一ID的一种算法思路,来源于 Twitter ,基本思路是:用一个 64 位无符号整数,表示和存储,主要有三部分组成,毫秒时间戳 + 机器 ID + 随机码。具体如何分配每一部分所占的位数,可以根据自己需要定制,没有特定的要求。和单机生成唯一ID的区别是,在单机上保证唯一相对来说简单很多。例如通过请求时间戳 + 进程 ID 就可以保证不同进程生成的 ID 一定不会冲突;同一进程内用随机数 + 时间戳也能保证 ID 不冲突,或者计数器等方式就可以最大可能地保证唯一性。但是分布式的难点在于,一般用了分布式,大多说明并发更高,意味着同一时刻,不同的机器都会同时生成大量的 ID ,不同机器的进程 ID大概率会冲突,所以更难保证唯一性。

雪花算法其实很简单,主要在于用不同的机器ID(事先分配好的,绝对不冲突的)来保证同一时刻不同机器生成的 ID 一定不一样,因为配置的机器ID 不一样,所以不唯一的风险只会在同台机器上。同一机器、同一时刻,就可以用累加计数法,很方便地生成绝对唯一的随机码。雪花算法中 ID 是用 64 位的整数来表示,可以按二进制位分割,分别表示“时间戳 + 机器ID + 随机码”例如:高 42 位表示时间戳,中 10 位表示机器ID,低 12 位表示随机码。根据自身需求,修改具体占用位数。

高 42 位表示毫秒时间戳

二进制最高位 1 表示负数,所以剩下 41 位表示时间戳的话,41 个二进制的 1 的十进制是 2^41 - 1 = 2199023255551, 对应的十进制如果折算成 Unix 毫秒时间戳的话,2199023255551 对应 2039-09-07 15:47:35:551, 假如 2019 年开始使用,高 42 位保存的就是下单时刻的毫秒时间戳,那么也可以使用 20 年,就算当前年份在 2039-01-01,只能用几个月了,你也可以通过设置上线时间(比如 2035-01-01, Unix 时间戳是 2051193600000)为固定值,用时间戳 0 开始计算,0 格林威治时间是 1970-01-01,但是我们知道系统上线时间,可以用 x (高 42 位记录值,eg:0) + 2051193600000 = 2051193600000(表示订单时间 2035-01-01),最大 2199023255551 + 2051193600000 = 4250216855551 (2104-09-07 15:47:35:551) 大约能用到上线开始后的 69 年。

PS: 说明在订单号规则升级之前,绝对有足够的时间。看看淘宝的订单号规则十年内升级了多少次就知道了。

中 10 位表示机器编码

中间 10 位二进制,全部为 1 的话是 2^10 - 1 = 1023, 从 0 开始就是最多可以表示 1024 台机器,只要保证集群中的每台机器的配置不一样即可。当然你的机器 > 1024, 可以从低 12 位借一位过来也可以。

低 12 位表示随机码

最低 12 位二进制,全部为 1 的话是 2^12 - 1 = 4095, 从 0 开始就是最多可以表示 4096 个唯一ID,单机 1ms x 4k 就是 400 万/s,目前单机性能几万 QPS 很牛逼了,所以和中间 10 位可根据自身适当调整。 PHP 实现主要用到移位运算,还有就是具体到单机时,如何保证多个 php-fpm 进程,同一个毫秒时间内,能生成唯一随机码?下面简单的示例代码,假设并发在 2k 一下,也就是每毫秒时间上最多几个请求,甚至不到一个请求,那么用完成随机生成随机码完全安全。

具体代码

/**
 * 分布式唯一ID生成算法 - 雪花算法
 * @param int $workId
 * @param array $options
 * @return string
 * @author deli
 * @date 2019-08-19
 */
function genUUID(int $workId = 0, array $options = [])
{
    $workId < 0 and $workId = 0;
    // 高中低三部分占位
    $hw = 42;
    $cw = 12;
    $lw = 10;
    // 偏移时间戳,默认0,hw 为生成毫秒数
    $offset = 0;
    !empty($options['hw']) and $hw = (int)$options['hw'];
    !empty($options['cw']) and $cw = (int)$options['cw'];
    !empty($options['lw']) and $lw = (int)$options['lw'];
    if ($hw + $cw + $lw !== 64) {
        throw new \RuntimeException('配置有误');
    }
    // 毫秒时间戳占据高位,
    $timestamp = microtime(true) * 1000;
    // 假设当前时间,偏移量为0时不可用了
    // $timestamp = strtotime('2039-09-08') * 1000;
    $timestamp = (int)$timestamp - $offset;
    if ($timestamp > 2 ** 41) {
        throw new \RuntimeException(sprintf('恭喜,代码从[%s]起,运行了[69]年+', date('Y-m-d', strtotime($offset)) ?: ''));
    }
    // 低位随机码
    try {
        $randId = (random_int(0, 2 ** $lw) * getmypid()) % (2 ** $lw);
    } catch (\Exception $e) {
        $randId = 100;
    }
    return ($timestamp << ($cw + $lw)) | ($workId << $lw) | $randId;
}