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, expsz, lower, upper):

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

Field	Description
size	Approximate number of fields. Accurate when expsz == 0.
mode	Subkey format mode. 0 = legacy (compatible with old data), 1 = field expiration mode.
expsz	Number of fields that currently have an active TTL. Default 0.
lower	A hint timestamp ≤ all field expiration times in this key (persistent fields excluded), in milliseconds. Default 0.
upper	A hint timestamp ≥ all field expiration times in this key (persistent fields excluded), in milliseconds. Default 0.

Migration rule:

• Existing hash keys keep mode=0 (extra fields absent, metadata decoded as legacy).
• Newly created hash keys always set mode=1, expsz=0, lower=0, 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):
  if expsz == 0:
      return size                      // no TTL fields, size is accurate
  if now < lower:
      return size                      // all TTLs in the future
  if now > upper and expsz == size:
      DELETE(key)                      // all fields expired
      return 0
  return SCAN_AND_REPAIR(key)          // slow path: scan and clean up

The first two branches are O(1). The last branch scans all subkeys, removes expired ones, and updates metadata.

HPERSIST / HEXPIRE Algorithms

HPERSIST(key, field):
  if old_expire != 0:
      expsz--

HEXPIRE(key, field, new_ts):
  if old_expire == 0:
      expsz++
  lower = min(lower, new_ts)
  upper = max(upper, new_ts)

lower and upper are only tightened lazily — they may become stale. This is fine because they are hints for the fast path and get corrected during SCAN_AND_REPAIR.

HDEL of a field with TTL should decrement expsz as well.

Expired Field Cleanup

Passive repairing — foreground commands (e.g. HLEN) check lower < now < upper and trigger SCAN_AND_REPAIR when needed.

Compaction filter — drops expired subkeys by checking the 8-byte expire prefix, but does NOT update metadata. This avoids data races and keeps compaction fast. 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 no fields have TTL or none have
#   expired yet; otherwise performs a scan to remove expired fields and update metadata.
# - approximate: always return the stored size without scanning. The count may include
#   fields that have already expired but have not yet been cleaned up.
# 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 fields: field1 (expire=5) and field2 (expire=10).
Initial metadata: lower=5, upper=10, size=2, expsz=2.

• 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, 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 expsz == size).

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.

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 fields that have already expired
            but have not been cleaned up yet.
            Overrides the hash-length-mode config for this call.

  REPAIR    Force a scan-and-repair pass if any fields have a TTL
            and may expire, 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.