background

PHP has no timer and relies on system tools like Crontab, and there is no delay method like defer in Go. This paper introduces several postures for PHP to write delay queues.

Definition of delay queue

The normal queue is fifO, but the delay queue is not, but with the weight of time. It is expected to reach the point in time before execution.

In a sense, the structure of the delay queue is not like a queue, but more like a time-weighted ordered heap structure.

Hash

Use a unique identifier for key to ensure that each task is not repeated and easy to delete, and then add the function name and timestamp to be called, as well as parameters in value. No seconds to traverse, and then take out the time to execute, and then delete.

  • Team:hSet key:uuid value:{timestamp,function,param}
  • The team:timestamp > now do function(param)

The problem is obvious, traversal, hGetAll is a taboo spell.

ZSet

As I mentioned, a delay queue is an ordered heap, but with a time weight, so isn’t that what an ordered set looks like?

  • Team:ZADD KEY timestamp task, we added the tasks to be processed into ZSet as Score according to the delay processing time needed.
  • The team:ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES. This will take out the tasks that need to be performed. Delete after executing:Zremrangebyscore KEY -inf +inf limit

Time round

In fact, the above algorithm, there is a small problem, the task of the same time line priority problem, such as 00 a.m., how to who first who last? Because tasks have a priority or order, of course, you can set multiple keys according to the priority, there are many ideas.

Here’s an algorithm that’s used by a lot of message queuing software, the time wheel algorithm.

In fact, it is very simple, is to put a queue at each time point, and then use a task to scan the time wheel, just like a clock, so that the corresponding task can be executed at the point.

For example, when the task is scanned to 2, a task with a delay of 3 seconds needs to be added directly to 5.

Of course, for different time granularity, we must set up multiple time wheels, just like the hour minute hand second hand.

What are the benefits of this?

  • The first two methods, at the end of the day, require traversal + sorting, while the time wheel, you just need to gradually scan and gradually remove the task. It’s much more efficient, the more tasks you have, the more obvious it is.

conclusion

  • If something is wrong, please point it out.
  • If you don’t understand, please point out and LET me add chestnuts.
  • If you feel OK, you can like it and let more people see it.