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

Souleigh ✨
• 阅读 1226

什么是时间轮算法?

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

解决了什么问题?

以商品为例,如何实现商品的过保质期自动失效?
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做好映射关系。
轮询流程:每秒执行一次,判断当前秒有没有要执行的任务,如果有,将当前秒的任务取出来处理,时间过度到下一秒。

点赞
收藏
评论区
推荐文章
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
小森森 小森森
4个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
艾木酱 艾木酱
3个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Stella981 Stella981
1年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Stella981 Stella981
1年前
Linux的定时任务
任务计划的条件:1.在未来的某个时间点执行一次某个任务(atbatch)2.周期性的执行某个任务(cron)at在指定时间执行任务_用法_at\选项参数\\时间\_选项参数_\l      查看作业\c      显示即将执行任务的细节\d      使用任务id号
Stella981 Stella981
1年前
Linux 定时任务调度(crontab命令)
1.crond是Linux下用周期性的执行某种任务或者等待处理某些事件的一个守护进程,crond进程会每分钟定期检查是否有要执行的任务,如果有要执行的任务则自动执行该任务2.Linux下的任务调度1.系统任务调度:系统周期性所要执行的工作,如:写缓存数据到硬盘、清理日志等。系统任务调度的配置文件/etc/c
Wesley13 Wesley13
1年前
PHP中的NOW()函数
是否有一个PHP函数以与MySQL函数NOW()相同的格式返回日期和时间?我知道如何使用date()做到这一点,但是我问是否有一个仅用于此的函数。例如,返回:2009120100:00:001楼使用此功能:functiongetDatetimeNow(){
Wesley13 Wesley13
1年前
Java 定时任务 & 任务调度
任务调度是指基于给定时间点,给定时间间隔或者给定执行次数自动执行任务。方式1:通过Thread来实现例如如下的代码,可以每隔1000毫秒做一次打印操作。publicclassJob_Schedule_Test1{publicstatic
helloworld_28799839 helloworld_28799839
4个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue