Download the PHP package awdn/vigilant-queue without Composer

vigilant-queue

React-PHP based priority queue key-value storage for expiration time based object eviction.

Objective

The objective is to create a prioritized list ordered by an expiration time of the item. When querying the list if there is an expired item by a given threshold, the list should return the item with the lowest expiration time below the threshold and then remove the item from the list. Each item has a unique key (which is allowed to be only once within the list), as well as a data attribute and an expiration time. If an item should be added to the list and the key already exists, the values for the expiration time and data of the existing item have to be update within the list. The list has to be reordered based on the new priority of the item as well.

Use Case

Imagine a distributed web environment where actions in your application have to be taken based on frequently occurring events for the same entities. If these actions are very cost intensive it probably makes sense to execute them only once by buffering the events for a while and fetch the latest scheduled action from the queue as soon as the expiration time has been reached.

First Approach

This approach is based on a doubly linked list. Inserts have to be done ordered based on the expiration time, so that the item with the lowest expiration time is at the beginning of the list. From there it can be fetched with a pop() operation. When updating an existing item it has to be moved within the list, if the expiration time has changed. Advantage: Very intuitive. No redundant data. Everything can be implement within a list. Disadvantage: Needs to traverse the list very often when inserting or updating item. Cost intensive in terms of CPU time.

Second Approach

A PriorityQueue (implemented as min-heap), where each item is not necessarily unique, supported by two HashMaps holding the data and the most recent priority for a given key. When querying the queue for an item to be evicted the top element of the queue will be checked, if its expiration time is equal or lower than a given threshold (current time). To validate if this is the most recent version of the item, the expiration time of the top item from the queue will be compared with the latest known priority for the given key from the HashMap. If this is the the case, the item will be returned from the evict() function, otherwise it will return null. In both cases the item will be removed from the queue and from both HashMaps. Advantage: No need for cost intensive traversals of a list. Disadvantage: Redundant data within the PriorityQueue.

Pseudo code visualising the second approach

Run the example

Change directory into the examples sub folder, open three terminals and run the following commands.

Starting the process

Starting the queue server

Starting a consumer process which just collects the evicted messages

Starting a producer simulation which generates some data:

Output

Producer

Producing a new message which is then send to the queue:

Queue Server

See here how a message comes in which is evicted three seconds later:

Consumer

Consume the evicted message:

Benchmark

The benchmark shows how the server receives 1.000.000 messages, puts them on the queue and evicts based on the defined expiration timeout.