HFE backlog - improve active expiration job

Problem

Valkey’s current active expiration works by scanning volatile keys (and separately keys with volatile items) using the hashtable consistent scanning algorithm. While this is a simple design which eventually converge to delete all the expired keys and/or items, it has several drawbacks:

1. Since the existing volatile key tracking is not kept order in anyway, many CPU cycles are wasting iterating over entries which are not expired.
2. In order to make sure we allocate enough CPU resources for the active expiration job, the current algorithm is managing some heuristic based on the previous sampling to try and "guess" the percentage of stale expired keys and adjust the rate of the FAST expiration cron job to use more CPU resources in case the percentage is estimated to be high. This method is based on statistical "guess" and might lead to extra CPU resources allocated when there is no real need to.

We could do better. In https://github.com/valkey-io/valkey/pull/2089 we introduces the new vset which provides an efficient way to track volatile items. The vset keeps items in time-range buckets which provides a good semi-sorted tracking abilities. While the coarse bucket approach for tracking volatile fields works well, it comes with tradeoffs:

1. Bucket counts can grow unbounded when expirations are highly fragmented, leading to higher memory usage.

2. There is no efficient way to answer: “How many items are currently expired?” — which makes it harder to dynamically tune the expiration job rate.

Proposal

Introduce a Hierarchical Timer Wheel as a new optional bucket type within the vset. Hierarchal Timer Wheels are a subset of the coarse bucket algorithm, which makes their implementation using RAX (to hold the expiration buckets) great fit in order to expend the exisiting vset implementation. The Algorithm is very similar to the coarse bucket algorithm, however it is different in the sense that it logically keeps a "fixed" number of time buckets matching the different time frames (different for each wheel level). One of the main reasons we did not use the timer wheel algorithm in our existing implementation for tracking volatile hash fields, was the need to perform "cascading" of elements when the timer wheel wraps a complete wheel cycle. This might be less efficient for managing items in multiple objects, but managing cascading for a per-database index might come with very low impact.

Key benefits:

Bounded number of buckets: Unlike naive coarse bucketing, a timer wheel has a fixed number of slots per level, keeping memory overhead predictable. This will also allow placing a secondary BIT (binary index tree) matching the buckets sizes. using BIT will allow us to get better results querying the number of elements with expiration time higher than a specific time (Since the

Efficient cascading: Expired elements can be incrementally cascaded to finer-grained levels as time advances.

Binary Indexed Tree (BIT) support: Maintain a parallel BIT with per-bucket counts to efficiently compute the number of expired elements. This enables better control over the expiration rate (e.g., speeding up or slowing down the job based on backlog).

Natural vset extension: The timer wheel can be implemented as another bucket type, similar to the existing radix-tree bucket type, requiring minimal changes to the vset API.

Design Sketch

TimerWheel Structure

• Backed by a rax (Radix Tree) keyed by time bucket.

• Each bucket contains a hashtable/single/vector encoded container of elements expiring in that bucket.

• Levels allow progressively finer-grained time windows.

• TimerWheelStep() will need to be introduced as part of the existing scan for expired elements. It will need to advance the wheel, expire elements, and re-inserts those that still have time remaining into future slots. Doing so will make cascading done incrementally, spreading work across iterations instead of spiking CPU usage.

BIT Integration

Maintain a Binary Indexed Tree to store counts of elements per slot.

Allows O(log n) queries like “how many elements have expired?” which can guide the active expiration job’s rate limiter. However since 'n' is a constant by the number of buckets (few hundreds) it can be treated as constant comlexity.

Benefits

• More predictable memory footprint (bounded buckets).

• Reduced wasted CPU cycles scanning unexpired data.

• Ability to make active expiration rate adaptive based on real backlog size.

• Minimal disruption to the existing vset interface.