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

Souleigh ✨ 等级 443 0 0

什么是时间轮算法?

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

解决了什么问题?

以商品为例,如何实现商品的过保质期自动失效?
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指的是什么?
PHP(全称:Hypertext Preprocessor,即“PHP:超文本预处理器”)是一种开源的通用计算机脚本语言,尤其适用于网络开发并可嵌入H
PHP对时间轮算法的简单实现
什么是时间轮算法? 把任务放到它需要被执行的时刻,然后等待时针转到这个时刻,取出该时刻的任务,执行并将任务从该时刻删除(消费)。 解决了什么问题? 以商品为例,如何实现商品的过保质期自动失效? 1:我们可以每分钟执行一个定时任务,扫描全表过期时间大于当前时间的商品,进行失效处理。(当然,也可以将该任务细化成秒级的) 2:商品添加时,将该商品的
PHP程序员必须会的 45 个PHP 面试题(第三部分)
Q25:此代码将返回什么?解释结果。 主题:PHP 难度:⭐⭐⭐ 考虑代码。结果将返回什么? $something 0; echo ('password123' $something) ? 'true' : 'false'; 答案是true。您永远不要将其用于字符串比较。即使将字符串与字符串进行比较,PHP也会将它们隐式转
PHP程序员必须会的 45 个PHP 面试题(第二部分)
Q20: require\_once 和 require 在什么场景下使用? Topic: PHP Difficulty: ⭐⭐⭐ require\_once() 作用与 require() 的作用是一样的,都是引用或包含外部的一个 php 文件,require\_once() 引入文件时会检查文件是否已包含,如果已包含,不再包含 (requir
PHP程序员必须会的 45 个PHP 面试题(第一部分)
Q1: 和 之间有什么区别? 话题: PHP 困难: ⭐ 如果是两个不同的类型,运算符 则在两个不同的类型之间进行强制转换 操作符执行’_类型安全比较_‘ 这意味着只有当两个操作数具有相同的类型和相同的值时,它才会返回 TRUE。 1 1: true 1 1: true 1 "1
请纠正这5个PHP编码小陋习
在做过大量的代码审查后,我经常看到一些重复的错误,以下是纠正这些错误的方法。 在循环之前测试数组是否为空 $items ; // ... if (count($items) 0) { foreach ($items as $item) { // process on $item ...
使用PHP生成网站Sitemap,Laravel风格
PHP生成网站Sitemap,包含默认、分类、文章、标签、profile等 <?php namespace AppLibs; use AppS
2017最新PHP经典面试题目汇总(上篇)
2017最新PHP经典面试题目汇总(上篇) 2017最新PHP经典面试题目汇总(上篇) 本文章将持续更新,希望能在评论区发表自己的见解和认为比较经典的题目,后续笔者会在适当的节点对本文章进行分类和层次
nginx安全配置
安全是一个重要的问题,必须引起注意。 1. nginx介绍 nginx本身不能处理PHP(http://www.ttlsa.com/php/ "php"),它只是个web服务器,当接收到请求后,如果是php请求,则发给php解释器处理,并把结果返回给客户端。nginx一般是把请求发fastcgi管理进程处理,fastcgi管理进程选择cgi子
为什么要从php 加入到 go 的潮流
为何我要说加入go开发是一种潮流,尤其是对于php开发人员,我加入了很多go的开发群或者爱好群,发现大部分人都是从php过来的,原本google开发golang是想让更多的c/c人员来使用。 PHP 语言作为当今最热门的网站程序开发语言,它也是我多年来一直使用的语言,它具有成本低、速度快、可移植性好、 内置丰富的函数库等优点,因此被越来越多的企业应用于网站
PHP学习笔记之PHP的函数应用
目录一、函数的定义 二、自定义函数 三、函数的工作原理和结构化编程 四、PHP变量的范围 五、声明及应用各种形式的PHP函数 六、递归函数 七、使用自定义函数库 一、函数的定义一个被命名的、独立的代码段,它执行特定的任务,并可能给调用它的程序返回一个值。定义中的各部分如下: 函数是被命名的:每个函数都
PHP 微信公众号消息加解密
公众号配置根据提示设置即可:【图中信息均为无意义数据,仅供参考。注意服务器地址需可接收 GET/POST 两种请求】 AESKey 直接点一下随机生成即可,Token 可以生成一个 UUID 再把 UUID 进行 MD5 一次即可。 接收关注事件消息示例 请求参数校验这一步根据项目情况,可供参考:(Lumen 框架)php$valida
PHP 获取国家、省、市、区及街道区域数据
地址: 分支 new 为全新获取方法,只需要 5 分钟,master 分支 fork 自 https://github.com/foxiswho/taobaoareaphp,补上了街道地址 该分支执行效率略低,但支持 CSV。output 中的 area.sql 文件为目前最新,可直接食用。根据淘宝开放平台获取国家、省、市、区数据,自动生成 SQL文件根
列举一些糟糕的PHP代码
10例糟糕的PHP代码 10例糟糕的PHP代码 这篇文章在很早以前就看到了,由于最近要自己做一些主题方面的东西,代码需要更加规范,用这些反面的例子来约束自己,告诉自己代码不应该这样写,虽然它也能实现功能,但那样做并不明智,
dubbo网关演进之路
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 背景随着公司业务的飞速发展,基于php的模块化架构难以支持未来业务的发展: php模块化架远远落后于行业主流架构(微服务–云原生),而php生态的服务治理开源组件匮乏,研发投入过大 杭州php人才匮乏,导致新鲜血液招聘困难 基于php的多进程架构难以支撑