PHP uses token bucket algorithm to implement flow control based on redis

This article introduces PHP based on redis and uses the token bucket algorithm to control access traffic. It provides a complete algorithm description and demonstration examples for everyone to learn and use.
Whenever there are long domestic holidays or important festivals, domestic scenic spots or subways will be crowded with people, resulting in excessive load. In some cases, flow limiting measures will be adopted to limit the number of people entering. When the number of people in the area is reduced to a certain value, no one will be allowed to enter again. Enter.

For example:
The maximum number of people allowed in the area is M
The current number of people in the area is N
Every entry One person, N 1, when N = M, is not allowed to enter
Every time a person leaves, N-1, when When N
Of course we can add servers to share the pressure. First of all, adding servers also takes a certain amount of time to configure, and if servers are added because of a certain activity, these server resources will be wasted after the activity is over.

Therefore, we can first use

current limiting to reduce server pressure according to the business type. Different from the traffic limit in scenic spots,

the time from visit to end of the system is very short

, so we only need to know the average duration of each visit and set the maximum number of simultaneous visitors. . Token Bucket Algorithm

1. First, there is a token bucket, and tokens are stored in the bucket. At the beginning, the tokens in the token bucket are full (the number of tokens in the bucket is The quantity can be set according to the server conditions).

2. Each visit takes a token from the bucket. When the token in the bucket is 0, no further visits are allowed.

3. Every once in a while, add tokens until the bucket is full of tokens. (You can put in several tokens at regular intervals according to the actual situation, or directly fill up the token bucket)

We can use the queue of

redis

as the token bucket container, Use lPush (enqueue), rPop (dequeue) to implement token addition and consumption operations.

TrafficShaper.class.php

<?php/**
 * PHP基于Redis使用令牌桶算法实现流量控制
 * Date:    2018-02-23
 * Author:  fdipzone
 * Version: 1.0
 *
 * Descripton:
 * php基于Redis使用令牌桶算法实现流量控制，使用redis的队列作为令牌桶容器，入队（lPush）出队（rPop)作为令牌的加入与消耗操作。
 *
 * Func:
 * public  add     加入令牌
 * public  get     获取令牌
 * public  reset   重设令牌桶
 * private connect 创建redis连接
 */class TrafficShaper{ // class start
    private $_config; // redis设定
    private $_redis;  // redis对象
    private $_queue;  // 令牌桶
    private $_max;    // 最大令牌数
    /**
     * 初始化
     * @param Array $config redis连接设定
     */
    public function __construct($config, $queue, $max){
        $this->_config = $config;        $this->_queue = $queue;        $this->_max = $max;        $this->_redis = $this->connect();
    }    /**
     * 加入令牌
     * @param  Int $num 加入的令牌数量
     * @return Int 加入的数量
     */
    public function add($num=0){
        // 当前剩余令牌数
        $curnum = intval($this->_redis->lSize($this->_queue));        // 最大令牌数
        $maxnum = intval($this->_max);        // 计算最大可加入的令牌数量，不能超过最大令牌数
        $num = $maxnum>=$curnum+$num? $num : $maxnum-$curnum;        // 加入令牌
        if($num>0){            $token = array_fill(0, $num, 1);            $this->_redis->lPush($this->_queue, ...$token);            return $num;
        }        return 0;
    }    /**
     * 获取令牌
     * @return Boolean
     */
    public function get(){
        return $this->_redis->rPop($this->_queue)? true : false;
    }    /**
     * 重设令牌桶，填满令牌
     */
    public function reset(){
        $this->_redis->delete($this->_queue);        $this->add($this->_max);
    }    /**
     * 创建redis连接
     * @return Link
     */
    private function connect(){
        try{            $redis = new Redis();            $redis->connect($this->_config[&#39;host&#39;],$this->_config[&#39;port&#39;],$this->_config[&#39;timeout&#39;],$this->_config[&#39;reserved&#39;],$this->_config[&#39;retry_interval&#39;]);            if(empty($this->_config[&#39;auth&#39;])){                $redis->auth($this->_config[&#39;auth&#39;]);
            }            $redis->select($this->_config[&#39;index&#39;]);
        }catch(RedisException $e){            throw new Exception($e->getMessage());            return false;
        }        return $redis;
    }
} // class end?>

demo:

<?php/**
 * 演示令牌加入与消耗
 */require &#39;TrafficShaper.class.php&#39;;// redis连接设定$config = array(    &#39;host&#39; => &#39;localhost&#39;,    &#39;port&#39; => 6379,    &#39;index&#39; => 0,    &#39;auth&#39; => &#39;&#39;,    &#39;timeout&#39; => 1,    &#39;reserved&#39; => NULL,    &#39;retry_interval&#39; => 100,
);// 令牌桶容器$queue = &#39;mycontainer&#39;;// 最大令牌数$max = 5;// 创建TrafficShaper对象$oTrafficShaper = new TrafficShaper($config, $queue, $max);// 重设令牌桶，填满令牌$oTrafficShaper->reset();// 循环获取令牌，令牌桶内只有5个令牌，因此最后3次获取失败for($i=0; $i<8; $i++){
    var_dump($oTrafficShaper->get());
}// 加入10个令牌，最大令牌为5，因此只能加入5个$add_num = $oTrafficShaper->add(10);
var_dump($add_num);// 循环获取令牌，令牌桶内只有5个令牌，因此最后1次获取失败for($i=0; $i<6; $i++){
    var_dump($oTrafficShaper->get());
}?>

Output:

boolean trueboolean trueboolean trueboolean trueboolean trueboolean falseboolean falseboolean falseint 5boolean trueboolean trueboolean trueboolean trueboolean trueboolean false

Regularly adding token algorithm

Regularly adding tokens, we can use crontab to implement it, and call the add method to add several tokens every minute. For the use of crontab, please refer to: "Linux crontab scheduled task execution command format and detailed examples"

The minimum execution interval of crontab is 1 minute. If the tokens in the token bucket have been consumed in the first few seconds , then the token cannot be obtained in the remaining tens of seconds, causing the user to wait for a long time.

We can optimize the algorithm for adding tokens and add several tokens every few seconds within a minute. This can ensure that there is a chance to obtain tokens every time within a minute.

The add token program called by crontab is as follows, automatically adding 3 tokens per second.

<?php /**
 * 定时任务加入令牌
 */require &#39;TrafficShaper.class.php&#39;;// redis连接设定$config = array(    &#39;host&#39; => 'localhost',    'port' => 6379,    'index' => 0,    'auth' => '',    'timeout' => 1,    'reserved' => NULL,    'retry_interval' => 100,
);// 令牌桶容器$queue = 'mycontainer';// 最大令牌数$max = 10;// 每次时间间隔加入的令牌数$token_num = 3;// 时间间隔，最好是能被60整除的数，保证覆盖每一分钟内所有的时间$time_step = 1;// 执行次数$exec_num = (int)(60/$time_step);// 创建TrafficShaper对象$oTrafficShaper = new TrafficShaper($config, $queue, $max);for($i=0; $iadd($token_num);    echo '['.date('Y-m-d H:i:s').'] add token num:'.$add_num.PHP_EOL;
    sleep($time_step);
}?>

The simulation consumption program is as follows, consuming 2-8 tokens per second.

<?php /**
 * 模拟用户访问消耗令牌，每段时间间隔消耗若干令牌
 */require &#39;TrafficShaper.class.php&#39;;// redis连接设定$config = array(    &#39;host&#39; => 'localhost',    'port' => 6379,    'index' => 0,    'auth' => '',    'timeout' => 1,    'reserved' => NULL,    'retry_interval' => 100,
);// 令牌桶容器$queue = 'mycontainer';// 最大令牌数$max = 10;// 每次时间间隔随机消耗的令牌数量范围$consume_token_range = array(2, 8);// 时间间隔$time_step = 1;// 创建TrafficShaper对象$oTrafficShaper = new TrafficShaper($config, $queue, $max);// 重设令牌桶，填满令牌$oTrafficShaper->reset();// 执行令牌消耗while(true){    $consume_num = mt_rand($consume_token_range[0], $consume_token_range[1]);    for($i=0; $iget();        echo '['.date('Y-m-d H:i:s').'] consume token:'.($status? 'true' : 'false').PHP_EOL;
    }
    sleep($time_step);
}?>

Demonstration

Set a scheduled task and execute it once every minute

* * * * * php /程序的路径/cron_add.php >> /tmp/cron_add.log

Execution simulation consumption

php consume_demo.php

Execution results :

[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:57] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:true[2018-02-23 11:42:58] consume token:false[2018-02-23 11:42:59] consume token:true[2018-02-23 11:42:59] consume token:true[2018-02-23 11:42:59] consume token:true[2018-02-23 11:42:59] consume token:false[2018-02-23 11:42:59] consume token:false[2018-02-23 11:42:59] consume token:false[2018-02-23 11:42:59] consume token:false[2018-02-23 11:43:00] consume token:true[2018-02-23 11:43:00] consume token:true[2018-02-23 11:43:00] consume token:true[2018-02-23 11:43:00] consume token:false[2018-02-23 11:43:00] consume token:false

Because the token bucket is full at the beginning (the maximum number of tokens is 10), tokens can be obtained in the first 10 times. After 10 times, the tokens consumed will be greater than the joining token. When the number of cards is exceeded, access is restricted.

This article explains how PHP uses the token bucket algorithm to implement traffic control based on redis. For more related content, please pay attention to the PHP Chinese website.

Related recommendations:

Redis master-slave synchronization, Relevant operations for read-write separation settings

##Introducing the method of MySQL to rebuild table partitions and retain data

PHP generates relevant content of the unique RequestID class

The above is the detailed content of PHP uses token bucket algorithm to implement flow control based on redis. For more information, please follow other related articles on the PHP Chinese website!