php + redis + lua 实现发号器

今天药忘吃喽~ 2022-02-01 23:34 204阅读 0赞

## 1、为什么要实现发号器 ##

很多地方我们都需要一个全局唯一的编号，也就是uuid。举一个常见的场景，电商系统产生订单的时候，需要有一个对应的订单编号。在composer上我们也可以看到有很多可以产生uuid的优秀组件。那么，为什么我们还要自己实现发号器，来产生uuid呢？想了一下，主要有两个原因吧：

1、我希望uuid是可反解的，通过反解uuid可以得出和我业务相关的数据。而我看到的composer关于uuid的相关组件，生成的都是一串指定格式的字符串，我很难将它同具体的业务关联起来。

2、我希望通过uuid是可以随着并放量进行调整的。比如说原有支持1秒钟可以产生1000个uuid，但随着业务规模增长，我希望变成可以支持1秒钟产生一万个。而且，最好改下配置就可以了。

出于以上两个原因，我们需要自己的发号器来产生uuid。那么，下一个问题是，我们应该如何实现发号器，实现发号器的原理又是什么呢？

## 2、snowFlake算法 ##

关于发号器的实现原理，可能大家都听过鼎鼎大名的snowflake算法 -- 雪花算法，Twitter的分布式自增Id算法。国内的新浪微博也有自己实现的发号器算法，具体实现细节虽有不同，但是原理相通，明白其中一个即可。这里我们主要介绍snowflake。

关于snowflaw的介绍，已经有很多文章进行介绍，而且写的也很不错，我没有必要在重写一遍，拿来粘贴即可，出于对作者的尊重，我会将原文链接添加到参考链接中。

推特的分布式自增ID算法，使用long （8 × 8 = 64 byte）来保存uuid。其中1bit留给固定符号位0，41bit留给毫秒时间戳，10bit给MachineID，也就是机器要预先配置，剩下12位留Sequence（可支持1毫秒内4096个请求）。

也许有的人会问如果超过了1毫秒4096个请求怎么办？一般的做法是，让它等上1毫秒，促使41bit的时间戳变化。

这里我们将MachineId进行了拆分，5byte留给机器（最多可以支持32机器），5byte留给了业务号（最多可支持32种业务）

这里的时间戳保存的是当前时间与固定过去时间得一个差值，不是当前时间。这样的好处是能使用更长时间，而且不受年份限制，只取决于从什么时候开始用的，2^41 / 1000360024\*365=69年。

如果保存的是当前时间戳，最多只能使用到2039年。2^41=2199023255552=2039/9/7 23:47:35

理论上单机速度：2^12\*1000 = 4 096 000/s

## 3、如何保证在单位时间内持续递增 ##

通过对snowflake的初步了解，发现，其实发号器也是建立在时间戳基础之上的，因为时间是天然的唯一元素。但是，如何在单位时间内，比如说一秒钟或者一毫秒之内，保证Sequence持续递增才是发号器实现的关键。

这里我们实现的方式比较简单，直接使用redis的incr进行计数，对应的key就是毫秒时间戳。出于redis内存回收的考虑，我们需要将每一个key设置过期时间。如果key是秒级别的时间戳，那么过期时间就是1秒；如果key毫秒级别的时间戳，那么过期时间就是1毫秒。

与此同时，为了保证执行incr，expire（pexpire）具有原子性，我们使用lua来进行实现。

好了，实现的思路大致如此。由于能力和水平有限，难免会有纰漏，希望及时指出。

## 1、基础知识 ##

发号器的实现主要用到了下面的一些知识点：

1. php中的位运算的操作和求值

2. 计算机原码、补码、反码的基本概念

3. redis中lua脚本的编写和调试

如果你对这些知识已经熟悉，直接往下看即可, 不了解的话就猛戳。

## 2、具体实现 ##

先上代码吧，然后再慢慢分析

class SignGenerator
        {
            CONST BITS_FULL = 64;
            CONST BITS_PRE = 1;//固定
            CONST BITS_TIME = 41;//毫秒时间戳 可以最多支持69年
            CONST BITS_SERVER = 5; //服务器最多支持32台
            CONST BITS_WORKER = 5; //最多支持32种业务
            CONST BITS_SEQUENCE = 12; //一毫秒内支持4096个请求
    
            CONST OFFSET_TIME = "2019-05-05 00:00:00";//时间戳起点时间
    
            /**
             * 服务器id
             */
            protected $serverId;
    
            /**
             * 业务id
             */
            protected $workerId;
    
            /**
             * 实例
             */
            protected static $instance;
    
            /**
             * redis 服务
             */
            protected static $redis;
    
            /**
             * 获取单个实例
             */
            public static function getInstance($redis)
            {
                if(isset(self::$instance)) {
                    return self::$instance;
                } else {
                    return self::$instance = new self($redis);
                }
            }
    
            /**
             * 构造初始化实例
             */
            protected function __construct($redis)
            {
                if($redis instanceof \Redis || $redis instanceof \Predis\Client) {
                    self::$redis = $redis;
                } else {
                    throw new \Exception("redis service is lost");
                }
            }
    
            /**
             * 获取唯一值
             */
            public function getNumber()
            {
                if(!isset($this->serverId)) {
                    throw new \Exception("serverId is lost");
                }
                if(!isset($this->workerId)) {
                    throw new \Exception("workerId is lost");
                }
    
                do{
                    $id = pow(2,self::BITS_FULL - self::BITS_PRE) << self::BITS_PRE;
    
                    //时间戳 41位
                    $nowTime = (int)(microtime(true) * 1000);
                    $startTime = (int)(strtotime(self::OFFSET_TIME) * 1000);
                    $diffTime = $nowTime - $startTime;
                    $shift = self::BITS_FULL - self::BITS_PRE - self::BITS_TIME;
                    $id |= $diffTime << $shift;
                    echo "diffTime=",$diffTime,"\t";
    
                    //服务器
                    $shift = $shift - self::BITS_SERVER;
                    $id |= $this->serverId << $shift;
                    echo "serverId=",$this->serverId,"\t";
    
                    //业务
                    $shift = $shift - self::BITS_WORKER;
                    $id |= $this->workerId << $shift;
                    echo "workerId=",$this->workerId,"\t";
    
                    //自增值
                    $sequenceNumber = $this->getSequence($id);
                    echo "sequenceNumber=",$sequenceNumber,"\t";
                    if($sequenceNumber > pow(2, self::BITS_SEQUENCE)) {
                        usleep(1000);
                    } else {
                        $id |= $sequenceNumber;
                        return $id;
                    }
                } while(true);
            }
    
            /**
             * 反解获取业务数据
             */
            public function reverseNumber($number)
            {
                $uuidItem = [];
                $shift = self::BITS_FULL - self::BITS_PRE - self::BITS_TIME;
                $uuidItem['diffTime'] = ($number >> $shift) & (pow(2, self::BITS_TIME) - 1);
    
                $shift -= self::BITS_SERVER;
                $uuidItem['serverId'] = ($number >> $shift) & (pow(2, self::BITS_SERVER) - 1);
    
                $shift -= self::BITS_WORKER;
                $uuidItem['workerId'] = ($number >> $shift) & (pow(2, self::BITS_WORKER) - 1);
    
                $shift -= self::BITS_SEQUENCE;
                $uuidItem['sequenceNumber'] = ($number >> $shift) & (pow(2, self::BITS_SEQUENCE) - 1);
    
                $time = (int)($uuidItem['diffTime']/1000) + strtotime(self::OFFSET_TIME);
                $uuidItem['generateTime'] = date("Y-m-d H:i:s", $time);
    
                return $uuidItem;
            }
    
            /**
             * 获取自增序列
             */
            protected function getSequence($id)
            {
                $lua = <<<LUA
                local sequenceKey = KEYS[1]
                local sequenceNumber = redis.call("incr", sequenceKey);
                redis.call("pexpire", sequenceKey, 1);
                return sequenceNumber
    LUA;
                $sequence = self::$redis->eval($lua, [$id], 1);    
                $luaError = self::$redis->getLastError();
                if(isset($luaError)) {
                    throw new \ErrorException($luaError);
                } else {
                    return $sequence;
                }
            }
    
            /**
             * @return mixed
             */
            public function getServerId()
            {
                return $this->serverId;
            }
    
            /**
             * @param mixed $serverId
             */
            public function setServerId($serverId)
            {
                $this->serverId = $serverId;
                return $this;
            }
    
            /**
             * @return mixed
             */
            public function getWorkerId()
            {
                return $this->workerId;
            }
    
            /**
             * @param mixed $workerId
             */
            public function setWorkerId($workerId)
            {
                $this->workerId = $workerId;
                return $this;
            }
        }

## 3、运行一把 ##

获取uuid

$redis = new Redis;
    
    $redis->connect("127.0.0.1", 6379);
    
    $instance = SignGenerator::getInstance($redis);
    
    $instance->setWorkerId(2)->setServerId(1);
    
    $number = $instance->getNumber();
    
    //于此同时，为了方便同可反解操作做对别，分别记录下来 diffTime,serverId,workerId,sequenceNumber, 运行结果如下图

反解uuid

$redis = new Redis;
    
    $redis->connect("127.0.0.1", 6379);
    
    $instance = SignGenerator::getInstance($redis);
    
    $item = $instance->reverseNumber(1369734562062337);
    
    var_dump($item);die();
    
    打印结果如下， 通过对比发现和之前的一致

## 4、代码解析 ##

从上面的代码上看，里面大量的使用了php的位运算操作，可能有些同学接触的不多，这里以getNumber为例，简单解释一下上面的代码，如果你已经很清楚了，那就请直接忽略本段。

首先明白一个基础的概念，计算机所有的数据都是以二进制补码的形式进行存储的，正数的原码 = 反码 = 补码

分析getNumber方法的实现过程：

1、初始化发号器

$id = pow(2,self::BITS_FULL - self::BITS_PRE) << self::BITS_PRE;
    
    我们可以认为：pow(2,self::BITS_FULL - self::BITS_PRE)我们向计算机申请了一块内存，它大概长下面这个样子：
    
    高位  <----------------------------------------------------------   低位
    10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
    
    执行位运算，由低位向高位移动，空位使用0补齐，变成了现在的这个样子
    高位  <----------------------------------------------------------   低位
    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
    
    这不就是0么，对的，经过实验测试，直接将$id = 0,效果是一样的
    
    所以$id 的初始化有下面三种
    // $id = pow(2, self::BITS_FULL);
    // $id = pow(2,self::BITS_FULL - self::BITS_PRE) << self::BITS_PRE;
    // $id = 0;

2、为发号器添加时间属性

//时间戳 41位
    $nowTime = (int)(microtime(true) * 1000);
    $startTime = (int)(strtotime(self::OFFSET_TIME) * 1000);
    
    //计算毫秒差，基于上图，这里 diffTime=326570168
    $diffTime = $nowTime - $startTime;
    
    //计算出位移 的偏移量
    $shift = self::BITS_FULL - self::BITS_PRE - self::BITS_TIME;
    
    //改变uuid的时间bit位
    $id |= $diffTime << $shift;
    
    $id 与 $diffTime 执行位移前的二进制形式
    
    |-------------BITS_PRE + BITS_TIME------------||--------shift---------|
    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
                                           10011 01110111 00010000 10111000
    
    $diffTime 执行位移后的二进制形式
    
    |-------------BITS_PRE + BITS_TIME------------||--------shift---------|
    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
                  100 11011101 11000100 00101110 00|--------shift---------|
    
    紧接着同$id进行或操作，得到如下结果
    |-------------BITS_PRE + BITS_TIME------------||--------shift---------|
    00000000 00000100 11011101 11000100 00101110 00000000 00000000 00000000

3、为发号器添加服务器编号

//在新的$shift 计算出位移 的偏移量
    $shift = $shift - self::BITS_SERVER;
    
    //改变uuid的服务器bit位
    $id |= $this->serverId << $shift;
    
    $id 与 $serverId 执行位移前的二进制形式
    |-------BITS_PRE + BITS_TIME + BITS_SERVER---------||------shift------|
    00000000 00000100 11011101 11000100 00101110 00000000 00000000 00000000
                                                                          1
    
    $serverId 执行位移后的二进制形式
    |-------BITS_PRE + BITS_TIME + BITS_SERVER---------||------shift------|
    00000000 00000100 11011101 11000100 00101110 00000000 00000000 00000000
                                                       10 00000000 00000000
    紧接着同$id进行或操作，得到如下结果
    |-------BITS_PRE + BITS_TIME + BITS_SERVER---------||------shift------|
    00000000 00000100 11011101 11000100 00101110 00000010 00000000 00000000

4、为发号器添加业务编号

//在新的$shift 计算出位移 的偏移量
    $shift = $shift - self::BITS_WORKER;
    
    //改变uuid的业务编号bit位
    $id |= $this->workerId << $shift;
    
    $id 与 $workerId 执行位移前的二进制形式, $workerId = 2
    |---BITS_PRE + BITS_TIME + BITS_SERVER + BITS_WORKDER----||---shift---|
    00000000 00000100 11011101 11000100 00101110 00000010 00000000 00000000
                                                                         10
                                                                         
    $workerId 执行位移后的二进制形式
    |---BITS_PRE + BITS_TIME + BITS_SERVER + BITS_WORKDER----||---shift---|
    00000000 00000100 11011101 11000100 00101110 00000010 00000000 00000000
                                                            100000 00000000
    
    紧接着同$id进行或操作，得到如下结果
    |---BITS_PRE + BITS_TIME + BITS_SERVER + BITS_WORKDER----||---shift---|
    00000000 00000100 11011101 11000100 00101110 00000010 00100000 00000000

5、为发号器添加sequence

//这里$sequenceNumber = 1
    $id |= $sequenceNumber;
    
    |--BITS_PRE + BITS_TIME + BITS_SERVER + BITS_WORKDER + BITS_SEQUENCE--|
    00000000 00000100 11011101 11000100 00101110 00000010 00100000 00000000
                                                                          1  
    紧接着同$id进行或操作，得到如下结果
    |--BITS_PRE + BITS_TIME + BITS_SERVER + BITS_WORKDER + BITS_SEQUENCE--|
    00000000 00000100 11011101 11000100 00101110 00000010 00100000 00000001

## 5、参考资料 ##

分布式ID生成器PHP+Swoole实现(下) - 代码实现

原码，反码，补码杂谈

由于能力和水平的有限，难免会有错误，希望读者及时支出！

原文链接：

1.  https://segmentfault.com/a/1190000019103001；
2.  https://segmentfault.com/a/1190000019117046