Feature request type

API addition

Is your feature request related to a problem? Please describe

We would like to support HEXPIRE and its variants in Garnet. The key goal is to support expiration of individual keys in a HASH object.

Describe the solution you'd like

The proposal is to keep two dictionaries:

• Dictionary<byte[], byte[]> as it currently exists
• Dictionary<byte[], long>, a secondary map that defaults to null, and only has entries for items that have expiration times.

That way, in the common case where there is no expiration for a hash object, we only incur one extra comparison (obj == null). Keeping it separate also allows the no-expiration case to have no memory overheads.

On a read operation into the hash object, we have to check this table to prune out the results that are sent to the user. We might have wrapper methods for accessing the hash object to perform this pruning (gated by the null check on the object, for performance). Note that under read lock, we cannot update the data structure to remove the expired elements, we can only ignore the expired entries.

On any write operation such as HSET, we have the opportunity to clean up the data structure by deleting the expired entries. To support this, we keep a priority queue:

• PriorityQueue<byte[], long>

The priority queue orders by expiration time, so that we can efficiently Peek and determine whether keys in the hash have expired (i.e., their expiration timestamp is less than DateTime.Now). This is similar to CheckExpiry in the main store. The expired keys are removed from the main dictionary and the expiration dictionary. The priority queue is popped.

We add a HCOLLECT key operation that will prune the expirations for the hash with that key. There might be a HCOLLECT * as well which will scan and collect all the hash keys.

Finally, need some background prune thread that will handle expiration pruning for the whole system. Perhaps it can be similar to compaction with a ExpirationPruneFrequency periodicity. It could be a periodic task similar to this: https://github.com/microsoft/garnet/blob/main/libs/server/StoreWrapper.cs#L393C22-L393C26.

Describe alternatives you've considered

See #674 where the expirations are stored in the same dictionary that holds values. This is problematic due to the additional allocation of the wrapper and the memory/cpu overhead even in the common case where expirations are not being used for individual keys in the HASH object.

Additional context

No response