CacheInvalidation.org

Using Key Tags to Invalidate Related Data Sets

When a single source-of-truth mutation must expire dozens of derived cache entries at once — a product edit that invalidates category listings, search facets, and rendered fragments — deleting keys one at a time leaves consistency gaps and inflates write latency. This page implements a deterministic tag index in Redis so one invalidation call atomically purges every key associated with a logical group, without maintaining relationship graphs in application memory or falling back to probabilistic TTL expiration. The pattern is the bulk-update primitive behind the broader Key Tagging Strategies for Bulk Updates approach and targets Python services running against Redis 7.x, including clustered deployments.

Prerequisites

  • Redis 7.0+ (for FUNCTION/FCALL support and improved UNLINK accounting) running standalone or in Cluster mode.
  • redis-py 5.x on Python 3.10+; examples use the async client (redis.asyncio).
  • Payload keys and their tag sets co-located on one hash slot via a shared hash tag (e.g. {tenant:acme}) so a single Lua script can touch them all. See Redis cluster slot allocation for how slots are assigned.
  • A memory policy that protects tag indices from eviction (noeviction on the tag namespace, or a dedicated instance) — mixing tags with an aggressive LRU eviction policy silently corrupts the index.

Step-by-Step Implementation

The core idea is an inverted index: each logical tag maps to a SET of the exact cache keys it governs, so invalidation is "read the set, delete its members, delete the set." Every step below is independently runnable against a local Redis.

1. Register each payload key into its tag sets on write. Couple the payload write and the tag membership in one transaction so the index can never drift from the data it tracks.

import redis.asyncio as redis

client = redis.Redis(host="localhost", port=6379, decode_responses=True)

async def cache_with_tags(key: str, value: str, *tags: str, ttl: int = 3600) -> None:
    # The payload key and every tag set share the {tenant:acme} hash tag, so they
    # land on the same hash slot and stay reachable from a single Lua script.
    async with client.pipeline(transaction=True) as pipe:
        pipe.set(key, value, ex=ttl)
        for tag in tags:
            pipe.sadd(tag, key)
        await pipe.execute()

# e.g. one product render tagged by product id and category
await cache_with_tags(
    "{tenant:acme}frag:product:42",
    rendered_html,
    "{tenant:acme}tag:product:42",
    "{tenant:acme}tag:category:electronics",
)

2. Author a Lua script that enumerates and deletes atomically. Redis has no foreign keys, so a server-side script is what makes "list members, delete them, delete the set" a single indivisible operation — closing the TOCTOU window where a stale write could re-register a key mid-purge.

-- invalidate_by_tag.lua
-- All payload keys and the tag key must share one hash slot (use a hash tag such
-- as {tenant:acme}) so this script executes on a single cluster node.
local tag_key = KEYS[1]
local members = redis.call('SMEMBERS', tag_key)
local deleted = 0

for _, key in ipairs(members) do
    -- UNLINK is non-blocking; prefer it over DEL for large objects.
    redis.call('UNLINK', key)
    deleted = deleted + 1
end

redis.call('DEL', tag_key)
return deleted

3. Load the script once at startup and invoke it by digest. Caching the SHA1 lets you call EVALSHA instead of shipping the script body on every invalidation, cutting network overhead on hot paths.

async def load_scripts() -> str:
    with open("invalidate_by_tag.lua") as f:
        return await client.script_load(f.read())

INVALIDATE_SHA = await load_scripts()  # cache the digest at boot

4. Wrap execution in bounded, idempotent retries. Master promotions, OOM errors, or a transient network partition can interrupt a script mid-flight; because the operation is idempotent (re-running a partially applied purge only deletes what remains), it is safe to retry with exponential backoff and jitter.

from tenacity import (
    retry, wait_exponential, stop_after_attempt, retry_if_exception_type,
)

@retry(
    wait=wait_exponential(multiplier=0.5, min=0.1, max=5),
    stop=stop_after_attempt(3),
    retry=retry_if_exception_type(redis.ConnectionError),
    reraise=True,
)
async def invalidate_tag(tag_key: str) -> int:
    # KEYS[1] = tag_key; returns the number of member keys unlinked.
    return await client.evalsha(INVALIDATE_SHA, 1, tag_key)
Inverted tag index: one invalidate call fans out to UNLINK every member key On the left, an invalidate call targets the tag SET tag:category:electronics. That set holds three member keys. Crimson dashed UNLINK edges run from the set to each of the three payload keys on the right — frag:product:42, listing:electronics, and search:tv — so a single call purges all three. Below it a second tag SET, tag:product:42, has a teal membership edge to frag:product:42, illustrating that a payload key can be registered under multiple tags. invalidate() tag:category:electronics tag:category:electronics SET · SMEMBERS → frag:product:42 listing:electronics search:tv tag:product:42 SET · { frag:product:42 } frag:product:42 rendered fragment listing:electronics category listing search:tv search facet EVALSHA UNLINK ×3 member of purged this call tag membership

5. Broadcast the invalidation so peer services reconcile. A single Redis holds one authoritative index, but stateless workers and local in-process caches need to hear about the purge; publish the event so consumers can drop their own copies. For durable, at-least-once fan-out prefer Redis Pub/Sub routing or Streams, and offload the sweep itself to async invalidation queues when the tag set is large.

async def invalidate_and_announce(tag_key: str, version: int) -> int:
    deleted = await invalidate_tag(tag_key)
    # Attach a monotonic version so consumers ignore out-of-order replays.
    await client.publish("cache:invalidations", f"{tag_key}:{version}")
    return deleted

The critical path — from an invalidation event through the Lua script to the returned deletion count — is:

Critical path: one atomic EVALSHA call reads, unlinks, and deletes, then returns a count Left to right. An invalidate event for a tag feeds into a boundary labelled EVALSHA — single atomic call. Inside that boundary three chained steps run without interruption: SMEMBERS reads the tag set, UNLINK removes each member key, and DEL removes the tag set. Control then leaves the boundary and returns the deleted count on the right. Invalidate event for a tag EVALSHA — single atomic call SMEMBERS read the tag set UNLINK each member key DEL the tag set Return deleted count

Failure Modes

CROSSSLOT error on invalidation. In Cluster mode, if a payload key and its tag set hash to different slots the script aborts with CROSSSLOT Keys in request don't hash to the same slot. Diagnose by comparing slots directly:

redis-cli CLUSTER KEYSLOT "{tenant:acme}tag:category:electronics"
redis-cli CLUSTER KEYSLOT "{tenant:acme}frag:product:42"

If the numbers differ, a key is missing the shared hash tag. Fix it by wrapping the co-located portion in braces ({tenant:acme}) on both the payload and the tag key so only that substring is hashed. This constraint survives resharding — see zero-downtime slot migration.

Orphaned payloads from index drift. If a tag set is evicted while its member payloads survive, later invalidations skip those keys and serve stale data indefinitely. Detect orphans by asserting the tag exists before relying on it:

redis-cli EXISTS "{tenant:acme}tag:category:electronics"   # 0 = index gone

Fix by setting maxmemory-policy noeviction on the tag namespace (or isolating tags on a dedicated instance) and running a periodic reconciliation sweep that rebuilds sets from source-of-truth metadata.

Blocking on oversized tag sets. SMEMBERS on a set with hundreds of thousands of members blocks the single-threaded server, spiking p99 latency for every other client. Catch it in the slow log:

redis-cli SLOWLOG GET 10

For sets above ~10,000 members, iterate with SSCAN in batches inside the worker instead of enumerating the whole set in one Lua call, and unlink in chunks.

Verification

Confirm the full round-trip against a live instance:

# Seed two tagged keys, then invalidate by tag and expect a count of 2.
redis-cli SET "{t}frag:a" 1
redis-cli SET "{t}frag:b" 1
redis-cli SADD "{t}tag:grp" "{t}frag:a" "{t}frag:b"
redis-cli EVALSHA "$(redis-cli SCRIPT LOAD "$(cat invalidate_by_tag.lua)")" 1 "{t}tag:grp"
# => (integer) 2

# Assert both payloads and the tag set are gone.
redis-cli EXISTS "{t}frag:a" "{t}frag:b" "{t}tag:grp"   # => (integer) 0

For ongoing health, track MEMORY USAGE on hot tag keys to catch index bloat, watch used_memory_overhead and evicted_keys in INFO memory, and export EVALSHA durations from redis-py via OpenTelemetry so a p99 above ~50ms alerts before it degrades write endpoints. Gate deployments on a CI job that runs the script against an ephemeral Redis and lints the Lua:

- name: Validate Invalidation Logic
  run: |
    docker run -d --name ci-redis -p 6379:6379 redis:7.2-alpine
    pytest tests/test_cache_invalidation.py --redis-url=redis://localhost:6379
    luacheck scripts/invalidate_by_tag.lua

FAQ

Why use a tag SET instead of SCAN with a key pattern? SCAN MATCH frag:product:42:* walks the entire keyspace and returns keys by name shape, not by logical relationship — it is O(N) in total keys and cannot express "everything in the electronics category" unless that fact is encoded in the key name. A tag set is an explicit O(members) membership list that survives arbitrary key-naming schemes.

Should the tag set carry a TTL? Generally no. If the set expires before its members, invalidation silently misses them. Let the set live as long as its longest-lived member, or run on noeviction and prune sets explicitly when the last member is deleted.

Does this work without Redis Cluster? Yes — on a standalone instance every key is on one slot, so the hash-tag requirement is moot and the Lua script runs unchanged. The {tenant:acme} braces are harmless in standalone mode, so writing them from day one lets you migrate to Cluster later without touching key names.

Why UNLINK instead of DEL inside the script? DEL frees memory synchronously, so deleting a few large payloads can stall the event loop for milliseconds. UNLINK removes the key from the keyspace immediately but reclaims memory on a background thread, keeping the atomic purge fast even for big values.

How do I stop a stale replay from resurrecting deleted keys? Attach a monotonic version or UUID to every invalidation and have consumers apply only versions higher than the last one they saw. A late-arriving message carrying an older version is then discarded instead of re-populating the cache.

Up next: return to Key Tagging Strategies for Bulk Updates for the full tagging model, or the Advanced Cache Invalidation Patterns & Synchronization overview.