Redis Secondary-Index Invalidation

Status: Implemented.

This document describes the current memento-redis secondary-ID invalidation model.

Summary

Redis secondary-ID invalidation relies on three mechanisms:

Mechanism	Purpose
Secondary indexes	Remove already-stored indexed entries during invalidation.
Redis secondary-ID epochs	Reject indexed loads that overlap an invalidation transition.
Active invalidation records	Hide matching entries and reject publication during write intervals.

Stored indexed entries are normally served directly. While an invalidation interval is active, the read script checks whether the entry belongs to an active secondary ID and waits instead of returning it. The invariant is that invalidation removes already-indexed entries atomically, while loads that overlap the interval are rejected at completion time.

Redis Keys

• epoch_key: key-generator-scoped Redis string incremented by start and finalize.
• sec_id_epochs_key: Redis hash mapping each secondary-index key to its latest invalidation epoch.
• active_invalidation_records_key: Redis set containing individually leased active-invalidation records.
• indexes_key: key-generator-scoped Redis set containing secondary-index set keys.
• id_key: Redis set for one secondary ID, containing associated reverse-index keys.
• entry_indexes_key: Redis hash for one entry. It stores the entry key plus every current id_key, allowing every plain or indexed replacement to remove obsolete memberships atomically.

An entry_indexes_key hash has this shape:

__memento_entry__ -> entry_key
id_key_1          -> 1
id_key_2          -> 1

__memento_entry__ is a reserved field. The other fields form a set of current secondary-index memberships; their value 1 is only a membership marker. Keeping both pieces in one hash allows invalidation to retrieve them with one HGETALL and remove all reverse metadata with one DEL.

Redis stores numbers as strings. Lua receives INCR results as numbers and GET/HGET results as strings, so scripts convert read values with tonumber when comparing epochs.

Entry Value Protocol

Every value stored under a cache entry key starts with one discriminator byte:

Byte	Shape	Layout
0x01	Plain value	[0x01][nippy(value)]
0x02	Indexed value	[0x02][nippy(secIds)][nippy(value)]
0x03	Load marker	[0x03][16 bytes UUID]

EntryMeta is not stored directly. EntryEnvelope.writeEnvelope unwraps it before serialization:

• plain values store just the user value;
• indexed values store secondary IDs and the user value;
• no-cache values are not stored.

Redis indexed envelopes do not serialize a write epoch. Redis epochs are used only for in-flight load completion checks.

Load Markers

Load markers prevent multiple processes from publishing different values for the same miss.

• fetch.lua installs [0x03][uuid-bytes] with a short TTL when a loader claims a missing key.
• Before every owner fetch attempt, Load.prepareFetch generates a fresh claim token and clears the validation epoch. Retrying on the same Load never reuses an earlier ownership token.
• Other callers seeing a load marker wait through the local/cross-JVM maintenance path rather than running the user function.
• Maintenance refreshes only non-null candidate/owned markers, including a candidate whose fetch reply may still be pending. Redis extends the lease only if the current marker equals the supplied token. Observing a foreign marker or an invalidation-blocked read clears the local marker, so waiters never refresh a foreign owner's lease.
• finish-load.lua and finish-load-w-sec.lua only publish if the marker under the entry key still matches the loader's marker.
• abandon-load.lua deletes a plain load marker only if it still belongs to the loader; abandon-load-w-sec.lua also validates indexed no-cache loads against active invalidations and epochs.

Lua scripts classify load markers by checking byte 1 for 0x03. Java uses Load.isLoadMarker for the full byte-array predicate.

Invalidation Script

sec-index-finalize.lua is authoritative for already-stored indexed values:

1. Increment epoch_key.
2. For each invalidated id_key, write the new epoch into sec_id_epochs_key.
3. Read and deduplicate the reverse-index keys from all invalidated secondary-index sets.
4. Read each reverse hash once and verify that it still owns at least one invalidated ID. A stale forward membership cannot delete an entry that has since been replaced with different IDs.
5. Delete the current entry and its reverse hash in bounded batches.
6. Group reverse-record removals by each surviving secondary index and apply them in bounded batches.
7. Delete the invalidated and newly empty secondary-index sets and remove them from indexes_key.

Redis executes the script atomically. No other Redis command observes a partially-cleaned index. Therefore, an already-stored indexed entry should be gone after invalidation completes.

In-Flight Load Rejection

Secondary-index deletion cannot remove a value that has not been written yet. Secondary-ID epochs catch that race.

Flow:

1. fetch.lua claims a missing key with a load marker and returns the current epoch_key as validation_epoch.
2. The user function runs and eventually returns an indexed value.
3. finish-load-w-sec.lua checks each returned ID's epoch in sec_id_epochs_key.
4. If any secondary ID is active, or its transition epoch is newer than validation_epoch, the load is stale.
5. For a completed invalidation, the script deletes the marker and returns -1. For an active interval it returns -2 and retains the marker while the owner waits.
6. Loader.get discards the stale computation and retries on the same local Load; its RedisPromise remains pending, so local joiners continue waiting for the final result.

An active result waits for all matching active invalidations to clear before retrying. The load marker remains in Redis during that wait so foreign JVMs join it rather than repeating stale work. The owner registers a MaintenanceWait.SecondaryIds on its Load and waits on a separate local latch. Maintenance signals that latch; the owner abandons its marker with an equality-protected Redis operation, then retries the full fetch.lua path. Neither the notification nor the discarded computation completes or rejects the result promise or releases joiners.

Local Owner and Joiners

One local owner keeps the same Load through Redis fetches, computation retries, and maintenance waits. Load holds a RedisPromise for the final result and a separate unified MaintenanceWait descriptor for the owner's current wait:

MaintenanceWait subclass	What the owner waits for
MaintenanceWait.ForeignLoad	The entry no longer contains a foreign load marker.
MaintenanceWait.InvalidationRecord	The active invalidation record returned by fetch.lua clears.
MaintenanceWait.SecondaryIds	No active invalidation matches the IDs of a rejected computation.

Successful maintenance notifications wake only the owner. It loops through the full fetch.lua path, which may return a value, claim a miss, or require another wait subclass on the same Load. A poll observation is not a cache read result. Joiners remain attached to the RedisPromise until the owner releases its final result or failure; they do not independently reread Redis after a successful load or poll. Explicit cancellation/invalidation of a local load can instead release the absent sentinel for an outer retry; maintenance never does this.

Successful result semantics are linearized at the Redis fetch returning a value or at successful Redis load completion. A later Redis secondary-ID invalidation does not retroactively revoke that result for already-attached callers, even if they have not yet received it. Fresh calls after the local load is removed reread Redis and observe the current state. Validated do-not-cache results are likewise shared with already-attached callers, but are never stored; the owner removes that load before delivering the transient result so new callers cannot join it.

Read Path

fetch.lua returns the following positional responses after RESP2/Carmine parse-raw decoding. Indexes are zero-based; null is Java null / Clojure nil, and Redis strings are raw byte arrays.

Count	Outcome	Slots
1	Observation-only miss (load=0)	[null]
2	Matching active invalidation	[null, invalidation-record-key-bytes]
3	Existing value or foreign load marker	[1, value-or-marker-bytes, 0]
3	Newly claimed miss	[null, our-load-marker-bytes, validation-epoch]

Callers must check for a two-element reply before interpreting slot 0 as hit/miss. For three-element replies, slot 0 indicates whether the key already existed; slot 1 holds its value/marker or our newly installed marker. Slot 2 is the captured invalidation epoch only for a claimed miss, otherwise zero. An invalidation reply needs no epoch: the owner fetches again after waiting and captures an epoch if it claims a miss.

Lua false preserves a null element in the reply; Lua nil truncates an array reply. The observation-only miss explicitly returns {false} rather than relying on truncation. Loader.get and Loader.ifCached then process results as follows:

• fetch.lua returns either a raw value envelope, a load marker, or a miss.
• Java dispatches by the first byte.
• 0x01 and 0x02 envelopes are decoded with EntryEnvelope.readEnvelope.
• 0x03 is treated as an in-flight foreign load.
• Unknown discriminators are deleted defensively by get/shared dispatch to avoid livelock.
• If active invalidations exist, fetch.lua checks their secondary indexes. A matching value is withheld until the interval ends; ifCached reports it as absent immediately.

Reads do not compare epochs because stored indexed entries do not carry write epochs. Secondary-index deletion handles stored stale entries; finish-load-w-sec.lua handles stale in-flight loads.

ifCached

ifCached checks an existing local load's released promise result without blocking, returning absent if it is pending or failed. When there is no local load, it uses LoaderSupport.fetchCachedEntry, an observation-only wrapper around fetch.lua with load=0.

This means:

• a miss never installs a load marker;
• a value hit can refresh fade, matching normal cache hit behavior;
• a load marker returns EntryMeta.absent immediately;
• indexed values use the same decode/dispatch path as get.

car/parse-raw decodes Lua true as 1 and Lua false as nil.

addEntries / putValue

RedisCache.addEntries delegates to Loader.putEntries.

Loader.putEntries:

• maps user args to Redis entry keys;
• passes raw values to EntryEnvelope.writeEnvelope; indexed EntryMeta values keep their secondary IDs;
• sends indexed entries one-by-one through LoaderSupport.putValue, which writes the value and indexes atomically;
• groups plain entries by expiry and writes them in batches.

Every write first removes the entry's prior reverse-index memberships. Indexed writes then create a new reverse record and add it to each secondary-ID set. This prevents a stale index pointer from blocking or deleting a replacement value with different secondary IDs. put-value-w-sec.lua does not touch epochs; explicit indexed writes are immediately indexed.

Maintenance Path

The maintenance daemon refreshes active-invalidation leases, signals local owners waiting on foreign load markers or invalidation, and incrementally removes expired secondary-index metadata. Polling is status-only and never transfers cached values. Maintenance does not remove Load objects or deliver, reject, or release their RedisPromise results.

For active invalidations:

• this JVM periodically extends the lease of each invalidation record it owns;
• an unrefreshed record expires, preventing a dead process from causing permanent lockout;
• expired records are removed lazily from active_invalidation_records_key by scripts that encounter them.

For MaintenanceWait.InvalidationRecord and MaintenanceWait.SecondaryIds waits:

• maintenance snapshots registered waits and groups them by connection and active-record-set key;
• record keys are deduplicated by their wire bytes, and secondary-index keys are deduplicated across loads;
• invalidation-statuses.lua checks all distinct watched keys in one atomic observation per domain, scanning active records once for all secondary-ID waits. It uses loops rather than unpack, including for large input sets;
• cached-hit waits watch the record returned by fetch; completion waits watch all their secondary IDs, so overlapping intervals continue to block them;
• only the same Load and wait descriptor observed before polling may be signaled; replacement loads are untouched;
• polling failures are delivered to affected owners for their normal exception handling, not treated as completed invalidations;
• waits remain interruptible and retain the local diagnostic timeout of 60000 ms (60 seconds) by default, even if maintenance cannot make progress;
• polling uses memento.redis.invalidation_poll (40 ms by default), limited by daemon ticks. There are no per-loader polling loops, invalidation count maps/indexes, or Pub/Sub subscriptions.

For MaintenanceWait.ForeignLoad waits and load-marker refresh:

• Refresh snapshots include only non-null candidate/owned markers. refresh-load-markers.lua checks token equality in Redis before extending a lease.
• Foreign waiters are tracked as [entry-key, Load, MaintenanceWait] tuples.
• cached-entries.lua returns only status codes: 0 for a load marker, 1 for a value, and 2 for an absent key. It never returns the value bytes.
• Clojure returns the original request tuples for terminal statuses. Maintenance signals a wait only if both the Load and MaintenanceWait still match the registered objects. Stale snapshots cannot wake replacement loads or replacement waits.
• The owner then retries full fetch.lua, including active-invalidation checks, rather than trusting the poll snapshot. Local joiners keep waiting for that owner's final result.
• Polling failures are signaled to the matching owner for normal exception handling.
• Foreign-load waits are interruptible and have no added timeout; the invalidation timeout does not apply to MaintenanceWait.ForeignLoad.

For secondary indexes, the daemon samples index sets and detects reverse records whose entry key is missing or whose referenced cache entry no longer exists. Once it finds one, it removes that reverse record from all of its secondary indexes, then deletes empty secondary-index sets. Current writes and invalidation remove obsolete memberships eagerly; this maintenance handles metadata left by normal Redis expiry or cache-key deletion. If more than 20% of sampled memberships are expired, the daemon immediately takes another sample so cleanup adapts to large cache wipes.

No read-time epoch check happens in maintenance; the same stored-entry invariant applies.

Backend Invalidation Lifecycle

Invalidation is centralized per Redis connection/secondary-index domain, not per cache instance. Memento invokes Redis through backend-owned start and finalize phases. Redis snapshots every registered connection/key-generator domain during start and creates an individually leased record containing the affected secondary-index keys. Secondary indexes span all cache names in that domain; cache names isolate entry keys and cache-level clearing only. Finalize atomically advances the per-ID epoch, optionally deletes matching entries, and releases the record. Advancing the epoch even when a failed write finalizes without deletion ensures loads detect an interval after its active record has already cleared. Separate records allow overlapping invalidations of the same ID, and their leases prevent a dead process from leaving a permanent lockout.

Connection functions that rotate between Redis databases register each domain when it is observed. A database that has never been returned in the current process cannot be discovered or invalidated until it is first observed; applications should use stable connection domains or explicitly create one cache configuration per domain. Cache construction resolves and registers its initial connection so a write-only invalidator process participates without a prior cache call.

MaintenanceWait.InvalidationRecord and MaintenanceWait.SecondaryIds waits are interruptible and fail after one minute by default with a diagnostic for a leaked or self-owned invalidation. Configure this with memento.redis.invalidation_wait_timeout in milliseconds. MaintenanceWait.ForeignLoad waits remain interruptible without an added timeout.

Redis does not use JVM invalidation epochs, Pub/Sub, or invalidation count maps. Redis secondary-ID epochs and active records are the cross-process authoritative guards for overlapping loads. Secondary indexes identify already-stored entries that must be hidden or removed. Maintenance observations only prompt the local owner to fetch again; successful results are shared through its RedisPromise according to the linearization semantics above, not revoked by a later Redis invalidation.