Proposal: Hash Field Expiration (HFE)

[PragmaTwice]

Motivation

Redis 7.4 introduced per-field expiration for hashes (HEXPIRE, HPERSIST, HPTTL, etc.). This proposal describes how to implement HFE in Kvrocks on top of the existing hash encoding in RocksDB.

Goals

• Backward compatible: existing hash data should work as-is without migration.
• Pay only for what you use: if a hash never uses field expiration, the overhead should be zero.
• Low compaction pressure: avoid data races and minimize extra writes during compaction.

Design

Metadata

We extend the existing hash metadata with four new fields (mode, persist, lower, upper):

        +---------+---------+---------+---------+---------+---------+---------+--------+
key =>  |  flags  |  expire | version |  size   |  mode   | persist |  lower  | upper  |
        | (1byte) | (Ebyte) | (8byte) | (Sbyte) | (1byte) | (8byte) | (8byte) | (8byte)|
        +---------+---------+---------+---------+---------+---------+---------+--------+

Field	Description
size	Approximate number of field candidates. It is exact after repair and when there are no TTL candidates.
mode	Subkey format mode. 0 = legacy (compatible with old data), 1 = field expiration mode.
persist	Number of known persistent physical fields (expire == 0). Default 0.
lower	A lazy lower-bound hint for TTL candidate expiration times, in milliseconds. Default 0.
upper	A lazy upper-bound hint for TTL candidate expiration times, in milliseconds. Default 0.

The number of TTL candidates is derived from metadata:

ttl_candidates = size - persist

ttl_candidates is not necessarily the number of physical TTL subkeys. It may include expired TTL subkeys that have
already been dropped by the compaction filter without updating metadata. This is intentional: size may over-count until
the next repair, while persist remains a reliable count of persistent physical fields because compaction never removes
persistent subkeys.

The metadata must maintain these invariants:

• 0 <= persist <= size.
• ttl_candidates == 0 means there are no known TTL candidates; in that case size == persist and lower == upper == 0.
• lower and upper are conservative hints for TTL candidates. Writes may expand the interval, but they must not tighten
  it unless they can prove there are no TTL candidates left. Exact bounds are recomputed by SCAN_AND_REPAIR.

Migration rule:

• Existing hash keys keep mode=0 (extra fields absent, metadata decoded as legacy).
• Newly created hash keys use the mode selected by hash-encoding-mode.
• A mode=1 hash created with only persistent fields has size == persist and lower == upper == 0.

Subkey Encoding

when mode=0 (legacy):
                     +---------------+
key|version|field => |     value     |
                     +---------------+

when mode=1 (field expiration):
                     +----------------+---------+
key|version|field => | expire (8byte) |  value  |
                     +----------------+---------+

When mode=1, each subkey value is prefixed with an 8-byte expiration timestamp (ms). 0 means the field is persistent.

HLEN Algorithm

HLEN(key):
  ttl_candidates = size - persist
  if ttl_candidates == 0:
      return size                      // no TTL candidates, size is accurate
  if now < lower:
      return size                      // all TTL candidates are in the future
  if now > upper and persist == 0:
      DELETE(key)                      // no persistent fields and all TTL candidates expired
      return 0
  return SCAN_AND_REPAIR(key)          // slow path: scan and clean up

The fast-path branches avoid scanning. The last branch scans all subkeys, removes expired ones, and updates metadata.

Metadata Update Rules

Only write paths and repair paths that observe a physical subkey can update counters for that field. A missing subkey
must not be assumed to be a deleted TTL subkey: a single-field path cannot distinguish a field that never existed from a
TTL ghost removed by compaction.

In the transition table below, "TTL field" means a physical subkey with expire != 0. It can be live or already
expired. A "TTL ghost" means a TTL candidate that remains in metadata after compaction has removed the physical subkey.
Single-field writes cannot identify or subtract TTL ghosts; only SCAN_AND_REPAIR can recompute them.

For a touched field:

Transition	Metadata update
Missing field -> persistent field	size++, persist++
Missing field -> TTL field	size++, expand lower/upper
Persistent field -> TTL field	persist--, expand lower/upper
TTL field -> persistent field	persist++
Persistent field -> deleted field	size--, persist--
TTL field -> deleted field	size--
TTL field -> TTL field	expand lower/upper if the new timestamp falls outside the current hints

Expanding lower/upper with a new TTL timestamp ts means:

if metadata had no TTL candidates before this write (size == persist):
    lower = upper = ts
else:
    lower = min(lower, ts)
    upper = max(upper, ts)

When a write removes the last TTL candidate (size == persist), it must reset lower = upper = 0. Otherwise, writes
must leave stale lower/upper values in place unless they need to expand the interval for a newly written TTL.

Command semantics still decide whether an expired physical TTL field is treated as existing. Ordinary read commands treat
expired physical TTL fields as logically missing and do not update metadata or subkeys. Write paths such as HEXPIRE and
HPERSIST also treat expired physical TTL fields as logically missing; when they observe one, they may delete the
physical subkey as cleanup by using the "TTL field -> deleted field" transition, but must not turn it into a persistent
field or refresh its TTL.
Overwrite-style writes such as HSET, HSETNX when allowed, and HINCRBY/HINCRBYFLOAT may replace an expired
physical TTL field with a new persistent value. In that case they use the "TTL field -> persistent field" transition.

For HEXPIRE, setting an expiration on a live persistent field uses the "Persistent field -> TTL field" transition.
Updating a live TTL field keeps size and persist unchanged and only expands the hints if needed. A zero TTL deletes
the live field immediately and uses the corresponding delete transition.

For HPERSIST, a live TTL field uses the "TTL field -> persistent field" transition. A persistent field is unchanged.

For HDEL, deleting a persistent field decrements both size and persist; deleting a TTL field decrements only
size.

Expired Field Cleanup

Passive repairing — foreground commands (e.g. HLEN) use the fast-path conditions above and trigger
SCAN_AND_REPAIR when the exact live field count cannot be proven from metadata alone.

Compaction filter — drops expired TTL subkeys by checking the 8-byte expire prefix, but does NOT update metadata.
This avoids data races and keeps compaction fast. After compaction, size may still include removed TTL candidates.
persist remains valid because persistent subkeys are not removed by the compaction filter. Metadata is corrected by the
next passive repair.

Active repairing (optional, may not be in the first version) — a background thread with an expiration index in a separate CF:

expire_ms | key | version | field => nil

Scans entries up to now and deletes corresponding fields. Trade-off: HEXPIRE/HSETEX need an extra write to maintain this index.

The encoding here is just a rough draft; we still need to consider slots and namespaces for this CF.

New Config Options

# The encoding mode for newly created hash keys.
# - legacy: use the original subkey format (no per-field expire support).
#   Existing data written in this mode is always readable regardless of this setting.
# - field-expiration: use the new subkey format that prepends an 8-byte expire
#   timestamp to each field value. Required for HEXPIRE/HPERSIST/HPTTL commands.
# NOTE: this only affects newly created keys. Existing keys retain their original mode.
# Default: legacy (will migrate to field-expiration when this feature become stable)
# Available options: legacy, field-expiration
hash-encoding-mode legacy

# How HLEN computes the number of fields when some fields have a TTL.
# - accurate: return the exact count. O(1) when metadata proves there are no TTL
#   candidates, none have expired yet, or no persistent fields exist and all TTL
#   candidates have expired; otherwise performs a scan to remove expired fields
#   and update metadata.
# - approximate: always return the stored size without scanning. The count may include
#   expired or compaction-deleted TTL candidates that have not yet been repaired.
# This option has no effect when hash-encoding-mode is legacy.
# Default: accurate
# Available options: accurate, approximate
hash-length-mode accurate

Example of HLEN fast-path & repair logic

To illustrate why actual slow scans are infrequent, consider a hash with two TTL fields: field1 (expire=5) and
field2 (expire=10).
Initial metadata: lower=5, upper=10, size=2, persist=0.

• now=0 or 2: HLEN directly returns 2 (Fast path: now < lower).
• now=6: Triggers SCAN_AND_REPAIR. It removes field1, updates metadata to
  lower=10, upper=10, size=1, persist=0, and returns 1.
• now=7 or 9: HLEN directly returns 1 (Fast path: now < lower).
• now=11: Directly deletes the key and returns 0 (Fast path: now > upper and persist == 0).

As shown, thanks to the lazy bounds (lower and upper), SCAN_AND_REPAIR is only triggered when absolutely necessary, minimizing full scans in most scenarios.

Example of compaction-safe metadata

Consider a hash with one expired TTL field:

field1 expire=5
metadata: size=1, persist=0, lower=5, upper=5

If the compaction filter removes field1, metadata is unchanged:

metadata: size=1, persist=0, lower=5, upper=5

If a later HSET key field1 value sees the field as missing, it must use the "Missing field -> persistent field"
transition:

metadata: size=2, persist=1, lower=5, upper=5

size now over-counts by one TTL candidate, but persist=1 prevents the HLEN fast path from deleting the whole key when
now > upper. The next SCAN_AND_REPAIR scans physical subkeys and rewrites metadata to:

metadata: size=1, persist=1, lower=0, upper=0

HLEN spec

HLEN key [APPROX | REPAIR]

Returns the number of fields in the hash stored at key.

Options (mutually exclusive, at most one):

  APPROX    Return the stored size immediately without scanning.
            The result may include TTL candidates that have already expired
            or have been removed by compaction but not repaired yet.
            Overrides the hash-length-mode config for this call.

  REPAIR    Force a scan-and-repair pass if any TTL candidates
            may be expired, removing expired fields and updating
            metadata. Then return the accurate size.
            Overrides the hash-length-mode config for this call.

When neither option is given, behavior follows the hash-length-mode config:
  - accurate (default): equivalent to REPAIR semantics.
  - approximate: equivalent to APPROX semantics.

[git-hulk]

Nice proposal.

hash-length-mode accurate

For the HLEN, I'm wondering if it would be better to have an option like HLEN key [APPROXIMATE] to let users determine the behavior.

[PragmaTwice]

Yah that looks good to me. The option is for users who want all HLEN to be approximate regardless of how users call HLEN.

[git-hulk]

OK, makes sense.

[PragmaTwice]

NOTE: The proposal is updated. expsz is replaced by persist. The reason is that expsz can be approximate, but persist will be always accurate.