一、业务背景:
将长链接转化成“指定的短域名+字母数字组合”不重复的URL短地址，用于业务线的常规业务及日常推广使用，基于此需求 需要实现一套简单高效的全局唯一的5位字母数字组合的短地址
在实现出上述需求的短地址之前 我们先讨论下 有几种办法可以生成一个全局唯一ID供后续生成5位字母组合使用
先说有几种唯一id的实现方法:
1、数据库自增长ID
优势：无需编码
缺陷：直接自增，不够随机，对外暴露信息过多。高并发下插入数据需要加入事务机制
2、时间戳+随机数
优势：编码简单
缺陷：随机数存在重复问题，即使在相同的时间戳下。每次插入数据库前需要校验下是否已经存在相同的数值
3、UUID
优势：简单
劣势：用户不友好，索引关联效率较低、影响性能。
4、今天想聊的是twitter开源的一款分布式自增ID算法snowflake
snowflake算法是一款本地生成的（ID生成过程不依赖任何中间件，无网络通信），保证ID全局唯一，并且ID总体有序递增，性能每秒生成10w＋、完全可以满足大部分的业务要求。
二、snowflake算法原理
snowflake生产的ID是一个18位的long型数字，二进制结构表示如下(每部分用-分开):
0 - 00000000 00000000 00000000 00000000 00000000 0 - 00000 - 00000 - 00000000 0000
第一位未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年，从1970-01-01
08:00:00)，然后是5位datacenterId（最大支持25＝32个，二进制表示从00000-11111，也即是十进制0-31），和5位workerId（最大支持25＝32个，原理同datacenterId），所以datacenterId*workerId最多支持部署1024个节点，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生2^12＝4096个ID序号）.
所有位数加起来共64位，恰好是一个Long型（转换为字符串长度为18）.
单台机器实例，通过时间戳保证前41位是唯一的，分布式系统多台机器实例下，通过对每个机器实例分配不同的datacenterId和workerId避免中间的10位碰撞。最后12位每毫秒从0递增生产ID，再提一次：每毫秒最多生成4096个ID，每秒可达4096000个。理论上，只要CPU计算能力足够，单机每秒实测10w+，效率之高由此可见。
三、snowflake算法源码（PHP版）
/**
* Description of SnowFlake
* 经典的分布式发号器 雪花算法
* @date 2018-4-19 16:23:21
*/
class SnowFlake
{
//开始时间,固定一个小于当前时间的毫秒数即可
const twepoch = 1482394743339;//2016/12/22 16:19:03
//机器标识占的位数
const workerIdBits = 5;
//数据中心标识占的位数
const datacenterIdBits = 5;
//毫秒内自增数点的位数
const sequenceBits = 12;
protected $workId = 0; //当前workid
protected $datacenterId = 0; //数据中心id
protected $maxWorkerId = 0; //最大workid
static $lastTimestamp = -1; //最新时间戳
static $sequence = 0; //发号频率
public function __construct($workId, $datacenterId){
//机器ID范围判断
$maxWorkerId = -1 ^ (-1 << self::workerIdBits); //31
$this->maxWorkerId = $maxWorkerId;
if($workId > $maxWorkerId || $workId< 0){
throw new Exception("workerId can't be greater than ".$this->maxWorkerId." or less than 0");
}
//数据中心ID范围判断
$maxDatacenterId = -1 ^ (-1 << self::datacenterIdBits); //31
if ($datacenterId > $maxDatacenterId || $datacenterId < 0) {
throw new Exception("datacenter Id can't be greater than ".$this->maxDatacenterId." or less than 0");
}
//赋值
$this->workId = $workId;
$this->datacenterId = $datacenterId;
}
//生成一个ID
public function nextId(){
$timestamp = self::timeGen();
$lastTimestamp = self::$lastTimestamp;
//判断时钟是否正常
if ($timestamp < $lastTimestamp) {
throw new Exception("Clock moved backwards. Refusing to generate id for %d milliseconds", ($lastTimestamp - $timestamp));
}
//生成唯一序列
if ($lastTimestamp == $timestamp) {
$sequenceMask = -1 ^ (-1 << self::sequenceBits);
self::$sequence = (self::$sequence + 1) & $sequenceMask;
if (self::$sequence == 0) {
$timestamp = self::tilNextMillis($lastTimestamp);
}
} else {
self::$sequence = 0;
}
self::$lastTimestamp = $timestamp;
//
//时间毫秒/数据中心ID/机器ID,要左移的位数
$timestampLeftShift = self::sequenceBits + self::workerIdBits + self::datacenterIdBits; //22
$datacenterIdShift = self::sequenceBits + self::workerIdBits; //17
$workerIdShift = self::sequenceBits; //12
//组合4段数据返回: 时间戳.数据标识.工作机器.序列
$nextId = (($timestamp - (self::twepoch)) << $timestampLeftShift) |
($this->datacenterId << $datacenterIdShift) |
($this->workId << $workerIdShift) | self::$sequence;
return $nextId;
}
//取当前时间毫秒
protected static function timeGen(){
$timestramp = (float)sprintf("%.0f", microtime(true) * 1000);
return $timestramp;
}
//取下一毫秒
protected static function tilNextMillis($lastTimestamp) {
$timestamp = self::timeGen();
while ($timestamp <= $lastTimestamp) {
$timestamp = self::timeGen();
}
return $timestamp;
}
}
四、snowflake算法推导和演算过程
说明：
演算使用的对象实例：$snowflake = new SnowFlake(1, 1);
运行时数据workerId＝1，datacenterId＝1，分别表示机器实例的生产者编号，数据中心编号；
sequence＝0表示每毫秒生产ID从0开始计数递增；
以下演算基于时间戳＝1482394743339时刻进行推导。
一句话描述：以下演算模拟了1482394743339这一毫秒时刻，workerId＝1，datacenterId＝1的id生成器，生产第一个id的过程。
图片.png
（图片转载自:https://blog.csdn.net/li396864285/article/details/54668031）
五、派号器根据snowflake去生成唯一的5位字母数字组合的短地址
/*
* 多进程 短地址发号器
* @date 2018-04-20 14:09
*/
public function ticketAction(){
//初始化成员属性
$this->initializeAttribute();
//检测队列剩余量 大于10万的话不生成
$queueNum = $this->redisService->llen($this->config->redisCommonShortUrlQueue);
if($queueNum > self::lastQueueNums){
echo "Date: " . date("Y-m-d H:i:s", time()) . "the data ".$queueNum." is full".PHP_EOL;
exit();
}
for ($i = 0; $i < 10; $i ++) {
$pid = pcntl_fork();
if ($pid == -1) {
echo 'could not fork';
continue;
} else if ($pid) {
pcntl_wait($status);
} else {
//通过pipeline批量生成
$pipe = $this->redisService->multi(Redis::PIPELINE);
for($j = 0; $j < self::perForkNums;$j ++) {
$newid = $this->patchTicketAction();
//压入队列
$pipe->lpush($this->config->redisCommonShortUrlQueue,$newid);
}
$result = $pipe->exec();
print_r($result);
unset($result);
echo "Date: " . date("Y-m-d H:i:s", time()) . "the ".$i." child process is end".PHP_EOL;
exit();
}
}
}
/*
* 发号器生成派发
* 压入队列 进入去重库
* @date 2018-04-20 14:09
* @return string
*/
public function patchTicketAction(){
//初始化成员属性
$this->initializeAttribute();
//先通过雪花算法 计算出一个key
$id = $this->snowflake->nextId();
//echo $id.PHP_EOL;
$secretKey = "a①d shor€t?";
$hex = md5($id.$secretKey);
$hexLen = strlen($hex);
$subHexLen = $hexLen / 8; //将长网址md5生成32位签名串，分为4段，每段8个字节；
$output = array();
for ($i = 0; $i < $subHexLen; $i++) {
$subHex = substr ($hex, $i * 8, 8); //对这四段循环处理，取8个字节
$int = 0x3FFFFFFF & (1 * ('0x'.$subHex)); //将他看成16进制串与0x3fffffff(30位1)与操作，即超过30位的忽略处理
$out = '';
//将这30位分成5段
for ($j = 0; $j < 5; $j++) {
$val = 0x0000001F & $int; //每5位的数字作为字母表的索引取得特定字符，依次进行获得5位字符串；
$out .= $this->base32[$val];
$int = $int >> 5;
}
$output[] = $out;
}
//总的md5串可以获得4个5位串；取里面的任意一个就可作为这个长url的短url地址；
$newid = $output[mt_rand(0, 3)];
unset($output,$out);
return $newid;
}
/**
* 初始化成员属性
* @return null
*/
public function initializeAttribute($totalProcess = 1, $pid = 1)
{
$this->workId = $pid + 1;
$this->datacenterId = 1;
$this->totalProcess = $totalProcess >= 1 ? $totalProcess : 1;
$this->pid = $pid;
//实例化redis
$this->redisService = new RedisService();
//实例化雪花算法
$this->snowflake = new SnowFlake($this->workId, $this->datacenterId);
//参与短地址计算的数组
$this->base32 = [
"a" , "b" , "c" , "d" , "e" , "f" , "g" , "h" ,
"i" , "j" , "k" , "l" , "m" , "n" , "o" , "p" ,
"q" , "r" , "s" , "t" , "u" , "v" , "w" , "x" ,
"y" , "z" , "1" , "2" , "3" , "4" , "5" , "6" ,
"7" , "8" , "9" , "A" , "B" , "C" , "D" , "E" ,
"F" , "G" , "H" , "I" , "J" , "K" , "L" , "M" ,
"N" , "O" , "P" , "Q" , "R" , "S" , "T" , "U" ,
"V" , "W" , "X" , "Y" , "Z" ];
return;
}
经多进程测试 上亿条 没出现重复
注意
多进程下 执行防止重复 将进程id 传入赋值给 workid 就可以保证单机下多进程不重复
