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