如何简单实现基于PHP的时间轮算法？

本文共计1863个文字，预计阅读时间需要8分钟。

时间轮算法是一种调度算法，它将任务分配到需要执行的时刻，然后等待时钟指针转到该时刻，取出任务执行，并将任务从该时刻删除。这种方法解决了任务调度问题。

以商品为例，如何实现时间轮？

假设我们有一个商品库存系统，需要按照预定时间点更新库存信息。我们可以采用以下步骤实现：

1. 创建一个时间轮，定义时间单位（如秒、分钟、小时等）。

2.将商品库存更新任务按照预定时间点分配到时间轮上。

3.当当前时间到达预定时间点时，从时间轮中取出对应任务执行。

4.执行任务后，将该任务从时间轮中删除。

具体步骤如下：

1. 定义时间单位：例如，我们选择以分钟为单位。

2.创建时间轮：初始化一个数组，长度为时间单位数（如60分钟）。

3.分配任务：将商品库存更新任务按照预定时间点分配到时间轮数组中，对应位置为任务ID。

4.运行时间轮：每过一分钟，检查当前时间是否到达预定时间点。如果是，则取出对应任务执行，并将任务从时间轮中删除。

示例代码（Python）：

python

class TimeWheel: def __init__(self, time_unit): self.time_unit=time_unit self.time_wheel=[None] * time_unit

def add_task(self, task_id, time_point): if time_point =self.time_unit: raise ValueError(Invalid time point) self.time_wheel[time_point]=task_id

def run(self): current_time=0 while True: if self.time_wheel[current_time] is not None: task_id=self.time_wheel[current_time] # 执行任务 print(fExecuting task {task_id} at time {current_time}) # 删除任务 self.time_wheel[current_time]=None current_time=(current_time + 1) % self.time_unit # 模拟时间流逝 time.sleep(60)

使用示例time_wheel=TimeWheel(60)time_wheel.add_task(1, 10) # 在第10分钟执行任务1time_wheel.add_task(2, 30) # 在第30分钟执行任务2time_wheel.run()

以上代码演示了如何使用时间轮算法实现商品库存更新任务。在实际应用中，可以根据需要调整时间单位、任务执行逻辑等。

什么是时间轮算法？

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

解决了什么问题？

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

分层时间轮的作用？

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

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

required:redis-service、PHP-cli、PHPRedisextension

0、业务需求场景（FROM滴滴）

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

1、先写一个30秒一轮的时间轮，其实就是一个0到30的队列来模拟时间的推进。<?PHP $redis=newRedis(); $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($uidas$value){ //将用户设置为离线并记录日志 file_put_contents('offline.txt',$value.'离线了'.PHP_EOL,FILE_APPEND); //移出当前slot $redis->srem($set_key,$value); } } sleep(1); }?>2、写一个模拟用户登录的系统functionconnect(){ $redis=newRedis(); $redis->connect('localhost',6379); //$redis->auth('S'); return$redis;}functioninit(){ $redis=connect(); //初始化，只执行一次，维护一个初始的list if(!$redis->exists('testlist')){ for($i=0;$i<=30;$i++){ $redis->lpush('testlist','slot-'.$i); } }}functionlogin(){ $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做好映射关系。轮询流程：每秒执行一次，判断当前秒有没有要执行的任务，如果有，将当前秒的任务取出来处理，时间过度到下一秒。