Key Tagging Strategies for Bulk Cache Invalidation in Distributed Redis

This page decides how to invalidate thousands of logically related Redis keys in one operation without scanning the keyspace, comparing an explicit reverse-index built on Redis Sets against a generation-pointer indirection that expires whole domains in O(1).

Bulk invalidation that relies on KEYS or an unbounded SCAN is a well-documented production anti-pattern: KEYS blocks the event loop for the full O(N) sweep, and a naive SCAN loop still touches every slot before it finds the handful of keys that changed. Tag-driven invalidation replaces that blind search with a deterministic mapping between a logical domain — a tenant, a product category, a rendered fragment set — and the physical keys that belong to it. Two mappings dominate real deployments, and they sit at opposite ends of the memory-versus-precision spectrum. This page assumes the topology and consistency baseline from Advanced Cache Invalidation Patterns & Synchronization; the mechanics below are what you reach for once passive TTL expiration can no longer meet a freshness SLA.

# Architectural Trade-offs

Both approaches answer "invalidate everything tagged X" without a keyspace scan, but they pay for it differently. A reverse-index tag set stores an explicit membership list you delete from; generation-prefix tagging stores a single version counter and lets orphaned keys age out. The columns below are the axes that actually move an on-call decision.

The rest of the page develops each row into a runnable implementation, then gives concrete signals for choosing between them and the failure modes each one introduces.

# Approach A — Reverse-Index Tag Sets

The explicit approach maintains a Redis Set per logical domain whose members are the cache keys that belong to it. Each write registers its key into one or more tag sets with SADD; invalidation resolves the set and deletes every member. Because the membership is materialized, deletion is exact — when the sweep returns, no stale key survives, which is what read-after-write workloads require.

Registration happens on the write path. Every entity that must die together — the entity itself, its rendered fragments, and derived aggregates — is added to the same tag, a grouping pattern developed in Using Key Tags to Invalidate Related Data Sets:

# Register a user profile into two logical domains. The {tenant:acme} hash tag
# forces the set and its members onto one slot so a Lua sweep stays node-local.
redis-cli -c SADD "{tenant:acme}:tag:active" "{tenant:acme}:user:1042:v3"
redis-cli -c SADD "{tenant:acme}:tag:active" "{tenant:acme}:product:881:v1"

# Atomic sweeps with Lua

Resolving the set and deleting its members in two separate round-trips opens a race: a concurrent writer can SADD a fresh key between your SMEMBERS and your UNLINK, and that key survives the sweep as a stale orphan. Encapsulating resolve-and-delete in a single Lua script closes the window — the script runs to completion with no interleaved commands, so the tag set is always emptied atomically.

-- invalidate_by_tag.lua
-- KEYS[1] = tag set name
-- ARGV[1] = max allowed members (safety guard)
local tag_key = KEYS[1]
local max_members = tonumber(ARGV[1]) or 5000

local member_count = redis.call('SCARD', tag_key)
if member_count > max_members then
    return {0, "TAG_CARDINALITY_EXCEEDED", tostring(member_count)}
end

local keys = redis.call('SMEMBERS', tag_key)
if #keys == 0 then
    return {0, "EMPTY_TAG_SET", "0"}
end

-- Redis embeds Lua 5.1 where the global unpack() function is used.
-- (Lua 5.2's table.unpack does not exist in this sandbox.)
redis.call('UNLINK', unpack(keys))
redis.call('DEL', tag_key)

return {#keys, "SUCCESS", "DELETED"}

The SCARD guard is not optional. An unbounded set turns a single invalidation into a multi-millisecond block while Lua walks the members, and a large UNLINK argument vector spikes memory during the call. Enforce a ceiling (5,000 members is a safe default) and split or shard the tag when the application approaches it. The driver-side wiring uses the async client from redis-py 5.x and register_script, which caches the script's SHA1 so subsequent calls dispatch as EVALSHA rather than re-shipping the source:

import redis.asyncio as redis

client = redis.RedisCluster(
    host="redis-cluster.internal",
    port=6379,
    ssl=True,
    decode_responses=True,
)

# Registered once at startup; the SHA1 is reused for every later call.
with open("invalidate_by_tag.lua") as f:
    invalidate_script = client.register_script(f.read())


async def bulk_invalidate(tag: str, max_members: int = 5000) -> dict:
    """Atomically delete every key registered under {tag}:tag."""
    try:
        # The hash tag {tag} pins the set and its members to one slot.
        count, status, detail = await invalidate_script(
            keys=[f"{{{tag}}}:tag"], args=[max_members]
        )
        return {"count": int(count), "status": status, "detail": detail}
    except redis.RedisError as exc:
        return {"count": 0, "status": "ERROR", "detail": str(exc)}

Using UNLINK rather than DEL hands memory reclamation to a background thread, so a large sweep never blocks the foreground event loop the way a synchronous DEL of thousands of keys would.

# Cluster-safe co-location

A Lua script may only touch keys that live in the same hash slot. Redis Cluster maps every key onto one of 16,384 slots by hashing the key, or, when braces are present, only the substring inside them. A tag set and its members that hash to different slots make the script fail with CROSSSLOT; worse, a bulk delete that spans slots fans MOVED/ASK redirections across nodes and exhausts the connection pool. Prefixing both the tag set and every member with the same {hash tag} guarantees single-slot placement:

# Both keyslots must be identical for the Lua sweep to execute.
redis-cli -c CLUSTER KEYSLOT "{tenant:acme}:tag:active"
redis-cli -c CLUSTER KEYSLOT "{tenant:acme}:user:1042:v3"

This is the same co-location discipline that keeps a rebalance cheap during zero-downtime slot migration: related keys that share a slot move as a unit instead of fragmenting across the topology.

# Approach B — Generation-Prefix Tagging

The indirection approach stores no membership list at all. Each domain owns a single integer — a generation counter — and every cache key embeds the current generation in its name. Reads look up the counter, build the key for the current generation, and cache misses populate it. To invalidate the entire domain you increment the counter once: every key built on the previous generation is now unreachable, because no future read will ever construct its name. Those orphaned keys are never deleted explicitly — they age out under their TTL. Invalidation is therefore O(1) no matter whether the domain holds ten keys or ten million.

import redis.asyncio as redis


async def read_through(client: redis.Redis, tenant: str, entity_id: str, loader) -> str:
    """Read via the current generation; miss populates a generation-scoped key."""
    gen = await client.get(f"{{{tenant}}}:gen") or "0"
    key = f"{{{tenant}}}:{gen}:{entity_id}"

    cached = await client.get(key)
    if cached is not None:
        return cached

    value = await loader(entity_id)
    # A TTL is MANDATORY here — it is the only thing that reclaims the keys
    # left orphaned when the generation advances.
    await client.set(key, value, ex=3600)
    return value


async def invalidate_domain(client: redis.Redis, tenant: str) -> int:
    """Invalidate every key in the domain in constant time."""
    # One INCR retires the whole generation; old keys expire on their own.
    return await client.incr(f"{{{tenant}}}:gen")

The consistency character is different from Approach A. New reads are correct immediately — they resolve the bumped counter and miss into a fresh generation — but the old-generation keys physically remain in memory until their TTL fires. That is acceptable when the domain is a cache of derived data with a bounded staleness budget, and unacceptable when you must guarantee that a purged secret or revoked record is gone from RAM. The write path is also far cheaper: there is no per-write SADD and no index to keep consistent, only one extra GET of the counter on reads, which itself caches trivially in the client.

# When to Choose Which

The decision turns on four production signals, not preference:

1. Reclamation urgency. If invalidation must free memory or scrub data on the spot — compliance deletion, secret rotation, tenant offboarding — use reverse-index sets, because generation-prefix keys linger until TTL. If invalidation only needs to stop serving stale reads, generation prefixing is cheaper and simpler.
2. Domain size and skew. When a domain can hold hundreds of thousands of keys, or when one tag would blow past the SCARD cardinality guard, the O(1) counter bump wins outright — a reverse-index sweep of that set is a multi-millisecond Lua block. For small, bounded domains (a single user's fragments), the set-based sweep is precise and its cost is trivial.
3. Write amplification budget. Write-heavy workloads pay the reverse index's SADD-per-tag on every mutation, which compounds with fan-out. If your write path is already latency-sensitive — see the persistence trade-offs in Write-Through vs Write-Behind Caching — the counter approach adds nothing to writes.
4. TTL discipline. Generation prefixing is only safe if every cached key carries a TTL sized to your memory headroom and eviction policy; without it, orphaned generations accumulate until eviction starts churning hot keys. Teams that cannot guarantee TTLs on every write should prefer the explicit sets.

A common production shape combines both: generation prefixing for coarse, high-cardinality domains (a whole tenant), and reverse-index sets for the narrow, must-be-exact groups nested inside them.

# Propagating a bulk sweep across services

Neither approach is confined to a single process. In a polyglot deployment the same domain is cached by several services, and a bump or a sweep in one must reach the others. Broadcast the tag over a domain-specific channel rather than a global one, so each service reacts only to the domains it owns:

# Publisher: announce the invalidation with the new generation/version.
redis-cli PUBLISH "invalidate:tenant:acme:active" \
  '{"domain": "tenant:acme:active", "generation": 8}'

Native Pub/Sub is fire-and-forget, so a service offline during the broadcast never learns the domain changed. The durable routing — consumer groups, replay on reconnect, and a channel matrix that prevents broadcast storms — is worked through in Pub/Sub Routing for Cross-Service Invalidation. When the sweep is large or must be retried, move it off the request path entirely with Asynchronous Invalidation Workflows.

# Failure Modes and Diagnostics

Each approach breaks in a characteristic way. Name the mode so on-call can confirm it in one command.

CROSSSLOT on the Lua sweep (Approach A). The tag set and one or more members hashed to different slots, so the script aborts before deleting anything and the invalidation silently no-ops. It surfaces the moment a key was written without the domain's hash-tag prefix. Confirm by comparing keyslots:

# If these differ, the member escaped the tag's slot — fix the key template.
redis-cli -c CLUSTER KEYSLOT "{tenant:acme}:tag:active"
redis-cli -c CLUSTER KEYSLOT "{tenant:acme}:user:1042:v3"

Tag-cardinality blowup (Approach A). A tag that grows without bound turns each sweep into a long Lua block and a large UNLINK vector, showing up as latency spikes on the invalidation path. Find oversized tags before they trip the guard:

# Rank tag sets by member count; anything near 5,000 needs splitting.
redis-cli --scan --pattern "*:tag:*" | while read -r key; do
  printf "%s\t%s\n" "$(redis-cli SCARD "$key")" "$key"
done | sort -rn | head -20

# Confirm the sweeps themselves are the slow commands.
redis-cli SLOWLOG GET 10

Orphaned-generation bloat (Approach B). A cached key written without a TTL — or with one longer than your memory headroom allows — never gets reclaimed after the generation advances, so used_memory climbs monotonically after each bump. Detect the untagged-TTL keys and watch fragmentation:

# Keys with no expiry are the leak; TTL of -1 means "never expires".
redis-cli -c TTL "{tenant:acme}:7:user:1042"
redis-cli INFO memory | grep -E "used_memory_human|mem_fragmentation_ratio"

# Verification

Confirm correct behavior in a live cluster before and after promoting an invalidation change.

• Slot alignment. Every member of a tag must return the same CLUSTER KEYSLOT as its tag set; run the comparison above in a staging sweep across a sample of live keys.
• Sweep completeness. After bulk_invalidate, assert the tag set is gone (EXISTS "{tenant:acme}:tag:active" returns 0) and a spot-check of former members returns nil.
• Generation retirement. After invalidate_domain, read the same entity and assert a cache miss populated a key under the new generation, while the old-generation key still resolves only if its TTL has not fired.
• Memory reclamation. Track mem_fragmentation_ratio and evicted_keys from INFO across a bump so a generation change never silently triggers eviction of hot keys.

Instrument both paths so latency regressions are visible as trend breaks, not incidents. A counter plus a histogram covers the essentials:

from prometheus_client import Counter, Histogram

INVALIDATION_COUNT = Counter(
    "cache_invalidation_keys_total", "Keys invalidated by tag", ["tag", "status"]
)
INVALIDATION_LATENCY = Histogram(
    "cache_invalidation_duration_seconds", "Invalidation execution time", ["tag"]
)


async def bulk_invalidate_observed(tag: str) -> dict:
    with INVALIDATION_LATENCY.labels(tag=tag).time():
        result = await bulk_invalidate(tag)
        INVALIDATION_COUNT.labels(tag=tag, status=result["status"]).inc(result["count"])
    return result

For distributed traces, opentelemetry-instrumentation-redis captures each Lua execution as a span; annotate it with cache.operation=bulk_invalidate and cache.tag=<tag> so a latency spike ties back to the exact domain that triggered it.

# Operational Checklist

• Enforce a SCARD ceiling in application code before every reverse-index sweep.
• Prefix tag sets and their members with a shared {hash tag} and verify with CLUSTER KEYSLOT.
• Use UNLINK, never DEL, inside Lua so reclamation stays off the event loop.
• Put a TTL on every generation-prefixed key and size it to your memory headroom.
• Instrument invalidation count and latency, and alert on trend breaks per domain.
• Watch SLOWLOG for Lua sweeps creeping toward the cardinality ceiling.
• Route cross-service invalidation over durable channels, not fire-and-forget broadcasts.

# Where This Fits

Up: Advanced Cache Invalidation Patterns & Synchronization

Related

• Using Key Tags to Invalidate Related Data Sets
• Write-Through vs Write-Behind Caching
• Pub/Sub Routing for Cross-Service Invalidation
• Asynchronous Invalidation Workflows
• TTL vs Explicit Invalidation