PHP对时间轮算法的简单实现

Souleigh ✨ 等级 806 0 0
标签: PHP

什么是时间轮算法?

把任务放到它需要被执行的时刻,然后等待时针转到这个时刻,取出该时刻的任务,执行并将任务从该时刻删除(消费)。

解决了什么问题?

以商品为例,如何实现商品的过保质期自动失效?
1:我们可以每分钟执行一个定时任务,扫描全表过期时间大于当前时间的商品,进行失效处理。(当然,也可以将该任务细化成秒级的)
2:商品添加时,将该商品的失效时间放入时间轮,当时间走到过期时间这个时间点时,发现该任务,将商品失效处理。
如上,1和2两种方法都能得到我们想要的结果。但是很明显,1方案每次都会有扫表的操作,如果细化成秒级,日均扫表86400次,即使加上索引,也会造成数据表的负担。而2和数据表无关,有任务就执行,没任务就移动到下一秒,效率明显更高。

分层时间轮的作用?

上述的例子有一个问题就是,我们的这个时间轮必须够大,才能将任务放到指定的年月日时分秒执行。这里就引入了分层时间轮的概念。
我们可以设计一个年轮,一个月轮,一个日轮,(时、分、秒轮),这样一组带着层级的时间轮。我们知道商品的过期时间是某年,那么我们将这个任务先投放到年轮里,只有到了指定的年轮,才会执行到这个任务,然后层层分发,将任务依次投放到月、日、时、分、秒轮(一直到任务被成功执行)。
这样,我们只需要6层,就能概括大多数的时间。但是这只是举例,我们不用局限于日常的这些单位,我们可以设计每30秒为一层,上一层对下一层负责。

用PHP简单模拟一个时间轮来解决的场景

required: redis-service、php-cli、phpRedis extension

0、业务需求场景(FROM 滴滴)

有一个APP实时消息通道系统,对每个用户会维护一个APP到服务器的TCP连接,用来实时收发消息,对这个TCP连接,有这样一个需求:“如果连续30s没有请求包(例如登录,消息,keepalive包),服务端就要将这个用户的状态置为离线”。
其中,单机TCP同时在线量约在10w级别,keepalive请求包较分散大概30s一次,吞吐量约在3000qps。

1、先写一个30秒一轮的时间轮,其实就是一个0到30的队列来模拟时间的推进。

<?php
    $redis = new Redis();
    $redis->connect('localhost', 6379);
    //$redis->auth('S'); //如果有密码要进行认证
    //写一个定时器,每秒对redis的key进行查询
    while (true) {
      //1分钟60秒,每30秒一个循环,当作当前的index
      $time = date('s')>30?date('s')/2:date('s');

      $set_key = $redis->lindex('testlist',(int)$time);
      //清空当前key中的slot的值,并将用户u_id设置为离线
      if($redis->exists($set_key)){
        $uid = $redis->smembers($set_key);
        //对uid进行处理
        foreach ($uid as  $value) {
          //将用户设置为离线并记录日志
          file_put_contents('offline.txt', $value.'离线了'.PHP_EOL,FILE_APPEND);
          //移出当前slot
          $redis->srem($set_key,$value);
        }
      }
      sleep(1);
    }
?> 

2、写一个模拟用户登录的系统

function connect(){
  $redis = new Redis();
  $redis->connect('localhost', 6379);
 // $redis->auth('S');
  return $redis;
}

function init(){
  $redis = connect();
  //初始化,只执行一次,维护一个初始的list
  if(!$redis->exists('testlist')){
      for ($i=0; $i <=30; $i++) { 
        $redis->lpush('testlist','slot-'.$i);
      }
  }
}

function login(){
  $redis = connect();
  //写一个登录系统,用户登录后记录日志,并放到定时器中
  $uid = 666666;
  //根据hash查找到当前用户uid对应的index
  $index = $redis->hget('timeline-index',$uid);
  if($index){
    //删除当前用户的slot_index,避免过期
    $redis->srem($index,$uid);
  }
  //放到新的index里,并记录当前用户对应的index
  $time = date('s')>30?date('s')/2:date('s');
  $time = $time>0?$time-1:30;
  //从队列获取当前的插槽
  $set_key = $redis->lindex('testlist',(int)$time);
  //插入插槽并记录index
  $redis->sadd($set_key,$uid);
  $redis->hset('timeline-index',$uid,$set_key);
  file_put_contents('online.txt', $uid.'上线了'.PHP_EOL,FILE_APPEND);
}

init();
login(); 

3、数据结构介绍

主要使用了redis的list数据结构做环形队列,redis的set结构做任务存储,redis的hash结构做uid和用户所在set结构所处的index映射。

4、执行流程介绍

登录流程:用户每次登录,都会把用户离线任务所在的时间轮查到,然后删除,避免时间轮执行到任务,把用户置为离线状态。然后给用户分配当前秒数的前一秒作为下次过期的时间,这样,下次执行到这个任务又是30秒。最后将index和uid做好映射关系。
轮询流程:每秒执行一次,判断当前秒有没有要执行的任务,如果有,将当前秒的任务取出来处理,时间过度到下一秒。

收藏
评论区

相关推荐

PHP对时间轮算法的简单实现
什么是时间轮算法? 把任务放到它需要被执行的时刻,然后等待时针转到这个时刻,取出该时刻的任务,执行并将任务从该时刻删除(消费)。 解决了什么问题? 以商品为例,如何实现商品的过保质期自动失效? 1:我们可以每分钟执行一个定时任务,扫描全表过期时间大于当前时间的商品,进行失效处理。(当然,也可以将该任务细化成秒级的) 2:商品添加时,将该商品的
PHP手动安装扩展
#### 进入源码目录下的EXT cd php/ext/* #### 使用PHP安装扩展工具phpize /usr/local/php/bin/phpize #### 进入源码目录编译安装 可以看到再EXT目录下生成里一些文件,执行 ./configure --enable-* --with-php-c
Ubuntu 下 Apache2 和 PHP 服务器环境配置
Ubuntu 下 Apache2 和 PHP 服务器环境配置 ============================== 1、简介 ---- 本文主要是 Ubuntu 下 Apache2 和 PHP 服务器环境配置方法,同样适用于 Debian 系统:Ubuntu 20.0.4 注意:文中运行的命令基本上需要管理员权限 2、安装 Apache
11.32 php扩展模块装安装
1.32 php动态扩展模块安装 ---------------- **注:** 本节操作使用PHP7。 查看PHP模块: [root@cham002 ~]# /usr/local/php/bin/php -m [PHP Modules] bz2 Core ctype date dom e
Bootstrap 结合 PHP ,做简单的登录以及注册界面及功能
登录实现 ==== HTML代码 <div class="container"> <?php if (isset($error_msg)): ?> <div class="alert alert-danger" role="alert"><?php echo $error_msg; ?></div>
CentOS 6.4 安装 media wiki 1.23.6(转)
准备: === CentOS 6.4系统及Root或者sudo权限,系统正常连接网络 使用到的软件: ======= apache ,mysql-server ,php ,mediawiki ,memcached 软件包的安装 ====== 首先,需要安装apache, php, mysql-server, mysql-client等相关软件包
CentOS 7下搭建MediaWiki环境
一、安装php、httpd和mariadb [root@dellnode1 ~]# yum install -y mariadb-server mariadb httpd 导入php的repo源: rpm -Uvh http://rpms.famillecollet.com/enterprise/remi-release-7.rpm
Centos配置nginx+php
添加第三方源: yum install epel-release 安装nginx: yum install nginx 安装php: yum install php php-fpm php-mbstring php-mysql php-gd php-fastcgi php-cgi 安装redis: yum ins
Kafka学习之(三)Centos下给PHP开启Kafka扩展(rdkafka)
Centos版本:Centos6.4,PHP版本:PHP7。 在上一篇文章中使用IP为192.168.9.154的机器安装并开启了Kafka进行了简单测试,充当了Kafka服务器。 本篇文章新开启一台IP为192.16.9.157的机器给PHP开启扩展。 找到github的扩展下载地址,这里是php-rdkafka,虽然php有一个扩展是php-kaf
LNMP架构之php
本文索引: * php-fpm的进程pool设置 * php-fpm慢执行日志 * open\_basedir参数设置 * php-fpm进程管理 * * * ### php-fpm的pool php-fpm.conf可以设置多个pool,在其中一个pool资源耗尽,会导致其他站点无法访问资源,报502错误。有必要把站点进行分离,分别
Larave
作者 -- 本文由 张舫 童鞋投稿 > 同时也欢迎更多的小伙伴投稿 开发需求 ---- PHP >= 7.0.0OpenSSL PHP ExtensionPDO PHP ExtensionMbstring PHP ExtensionTokenizer PHP ExtensionXML PHP ExtensionApache/NginxMySQ
Linux下php安装Redis扩展
1 安装redis /usr/local/php/bin/phpize #用phpize生成configure配置文件 ./configure --with-php-config=/usr/local/php/bin/php-config #配置 1 make #编译 2 make install #安装
PHP7中用opcache.file_cache导出脚本opcode实现源代码保护
停止php-fpm(apache同理): sudo /png/php/7.0.0/png\_fpm stop 创建opcode缓存目录: mkdir -m 777 /png/php/opcache\_file\_cache 在php.ini中配置: zend\_extension=/png/php/7.0.0/lib/php/
PHP的前世今生
大家都知道,Facebook、淘宝等早期都是用PHP写的,在中国,PHP在百度、新浪、腾讯这三大互联网公司中应用比较多。 自1995年由丹麦人Rasmus Lerdorf(雷斯莫斯·勒道夫) 创建 PHP 以来, PHP 语言经历了激烈的演进。 ### PHP/FI - 1995年 _摘要:用Perl写的小工具_ PHP 继承自一个老的工程,名叫 P
PHP配置优化:php
> PHP-FPM是一个PHP FastCGI管理器,php-fpm.conf配置文件用于控制PHP-FPM管理进程的相关参数,比如工作子进程的数量、运行权限、监听端口、慢请求等等。 我们在编译安装PHP的时,在./configure的时候带 –enable-fpm参数即可开启PHP-FPM。PHP-FPM配置文件为 php-fpm.conf,其语法类似 p