Ten Million Keys, One Missing Index

Open original cover image This article explores how a per-entity index improves Redis cache invalidation by replacing repeated full-keyspace scans with targeted lookups. All performance figures come from local benchmarks. The accompanying demo includes the implementation, benchmark scripts and recorded results. Run it locally to repeat the experiments, explore the code and test the approach under different workloads. ❗ The problem A cache often sits in front of a slower dependency: a third-party API, a busy database or a service with a rate limit. The read path is straightforward: request → check cache → hit? → return → miss? → fetch from origin → write to cache with a TTL → return An exact lookup needs a key that includes every input affecting the result: :::::::: subscriptions-api::brand-a::activeSubscription::u_9f3a21::{“includeAddons”:true} subscriptions-api::brand-a::planConfig::pro-monthly::{“currency”:“USD”,“billingPeriod”:“month”} Good design for reading: every lookup is one exact-match GET. And because the parameter tail varies and several services cache the same value independently, one entity’s cached state usually lives under five or ten different key strings. Then something upstream changes. A user’s subscription expires. A plan’s price is updated. You get one identifier and must remove everything cached about it. The identifier sits in the middle of the key. The service prefix varies. The tail is arbitrary. You cannot construct the key names from what you were given. To delete an entity’s cached state you first have to discover what it’s called. And then comes the interesting part: not how long each removal process takes, but what happens to every other request while it is running, because Redis executes commands on a single thread. For example, if you use the KEYS command to search for records matching an invalidation pattern across a dataset containing several million keys, the command can block the Redis thread for seconds. During that time, every other client — including one performing nothing more than a single GET — has to wait for the command to complete. 🔑 How the read path builds a key In the demo I built for this article, a decorator handles caching around the method that calls the billing provider: // The cached read of a user’s subscription. The caching is the decorator — this method never names a // key or touches Redis. configureCache must have run first (test-api’s bootstrap does it). import { Cache, CacheKey, CacheStrategy, TTL } from “@redis-entity-index/cache”; import type { Subscription } from “@redis-entity-index/fixture”; /** * Call parameters; they become the params segment of the cache key, so this type IS the key * contract. v selects the variant. Add nothing here that the bulk seeder does not also write. / export interface SubscriptionParams { v?: number; } /* What the service reads from on a miss — the S2S BillingClient, or a stub in tests. / export interface SubscriptionOrigin { getActiveSubscription(userId: string, params?: SubscriptionParams): Promise<Subscription | null>; } export class SubscriptionService { constructor(private readonly billing: SubscriptionOrigin) {} @Cache(CacheKey.ACTIVE_SUBSCRIPTION, TTL.MEDIUM, CacheStrategy.ENTITY_INDEX_CACHE) getActiveSubscription(userId: string, params: SubscriptionParams = {}): Promise<Subscription | null> { return this.billing.getActiveSubscription(userId, params); } } The service method delegates to the origin. The decorator handles lookup and cache population through the selected strategy. The key combines the configured service and tenant, the selected cache entity name, and the method’s arguments: /* * service::tenant::category::entityId::params. The entity ID is the first argument; params is the * canonical JSON of the second argument (or {} when absent), or of the whole tail when there are * several. An entity ID outside the segment character class throws — it is never escaped. / export function buildCacheKey( service: string, tenant: string, category: string, args: readonly unknown[], ): string { const [entityId, …rest] = args; if (typeof entityId !== “string”) { throw new TypeError(@Cache: the first argument must be the entity ID string, got {typeof entityId}); } assertSegment(“entityId”, entityId); const params = rest.length <= 1 ? canonicalJson(rest[0] ?? {}) : canonicalJson(rest); return [service, tenant, category, entityId, params].join(KEY_DELIMITER); } canonicalJson sorts object keys recursively, so {a:1,b:2} and {b:2,a:1} produce the same parameter segment. The first argument must be a valid entity ID; unsupported characters cause an error. That is the whole problem in one sentence: the key is generated by the read path and has to be reconstructed by the delete path, and only one of the two has the arguments. ⚠️ Keep origin failures out of the cache A related mistake is to turn an origin failure into a value that the cache treats as a valid response. Consider this illustrative anti-pattern, assuming the surrounding cache stores undefined as a negative result: try { return await BillingProvider.getActiveSubscription(userId); } catch (error) { ErrorLogger.error(‘Cannot fetch subscription’, userId, error); return undefined; // ← and now the decorator caches this } Under that policy, a temporary provider failure can become a cached “no subscription” response for the rest of the TTL. The problem is the combination of the catch block and the cache’s handling of its return value. The demo treats these outcomes separately. A rejected origin call propagates without writing a value. undefined is never cached. Caching null requires an explicit option, disabled by default. 🔥 Why a KEYS pattern search may appear cheap and fast during development, but becomes significantly more expensive once deployed to production. Now let’s return to the cache invalidation problem, where we are given a single record identifier — such as a UserID or PlanID — and need to find all complete cache keys associated with that identifier so they can be removed. Let’s say we decided to use the KEYS command for this lookup: KEYS u_9f3a21 It’s O(N) over the whole keyspace — every key examined, every time, to find just a few records. Redis executes commands on a single thread. While that scan runs, that Redis process serves nobody else. Every other client on it queues behind a scan it knows nothing about. The cost isn’t paid by the caller; it’s paid by everyone sharing that process or shard. And it isn’t even correct. u_9f3a21 is a substring match: it also matches u_9f3a210, and it will match those characters anywhere in the key — including inside the parameter tail of something unrelated. Convenient, not right. Would SCAN fix it? Partly. SCAN iterates with a cursor, so no single call holds the server for the whole traversal — that genuinely helps latency spikes. But a full pass still touches every key, and you still need a pass per entity. Better-behaved, same order of work. 💡 The design: a per-entity index A Redis cache can hold millions of composite keys and still have no direct way to answer: “Which cache keys belong to this entity?” I built a per-entity index to make that relationship explicit. Each entity has a Redis set containing its cache-key names, so invalidation can find them without searching the entire keyspace. Open full-resolution image Alongside the cache, keep one small Redis set per entity: KEY: entityIndex:::::: MEMBERS: the full cache keys currently written for that entity So entityIndex::brand-a::activeSubscription::u_9f3a21 contains: subscriptions-api::brand-a::activeSubscription::u_9f3a21::{} workflow-svc::brand-a::activeSubscription::u_9f3a21::{“includeAddons”:true} entitlement-api::brand-a::activeSubscription::u_9f3a21::{} Every service that writes the cache records the key it wrote. Invalidation reads one set and unlinks what it finds. Here is what that actually looks like in a running instance of the demo — two million cache records, one tenant: Open full-resolution image One cached value. The key carries every dimension that changes the answer, which is what makes reads a single exact-match GET — and what makes the key impossible to reconstruct from a user ID alone. Open full-resolution image The same user’s index: a three-member set, one member per cached variant, with its own TTL. This is the entire mechanism. Invalidating that user is SMEMBERS, UNLINK, SREM — no matter how many keys surround it. Why use a set and not a hash? My earlier design stored cache keys and their expiry timestamps in a hash. During invalidation, expired entries were skipped based on those timestamps. This introduced a correctness risk: if the client clock was ahead of Redis, a key could be considered expired even though Redis still held it. The current design avoids client-side expiry checks and simply deletes every key recorded in the index. Since no extra value is needed, a Redis Set is a better fit. Redis still manages the TTL of the index itself. Entities keep the approach reusable: subscriptions can be indexed by user ID, plans by plan ID, and only most critical pre-configured cache entities are indexed. 🏗️ The implementation All of it is quoted verbatim from msilberg/redis-entity-index — the working demo built with a plain TypeScript 5. Two strategies, one connection The base strategy owns the shared Redis connection and provides ordinary reads and writes: export class DefaultCacheStrategy { /* Shared with every subclass — the point of the base class. / protected readonly redis: RedisClient; constructor(redis: RedisClient, _options?: DefaultCacheStrategyOptions) { this.redis = redis; } /* A plain GET. null is a miss. / get(key: string): Promise<string | null> { return this.redis.get(key); } /* SET key value EX ttl. The TTL is validated before any command, so a rejected call writes nothing. / async set(key: string, value: string, ttlSeconds: number): Promise { assertValidTtl(ttlSeconds); await this.redis.set(key, value, “EX”, ttlSeconds); } The excerpt shows the constructor, get and set methods. The entity-index strategy inherits the connection and overrides set: /* * Write a cache value and register it in its entity’s index. * * Deliberately does NOT call super.set() on the indexed path. super.set() followed by a * separate registration is two round trips, and an invalidation landing between them would never * see the value — it would survive to its TTL with no reference pointing at it. registerMany * queues SET EX, SADD, EXPIRE NX and EXPIRE GT in one MULTI, so the value and its * reference land together. A key in a category this strategy does not own is a plain SET. / override async set(key: string, value: string, ttlSeconds: number): Promise { if (this.parse(key) === null) { await super.set(key, value, ttlSeconds); return; } await this.registerMany([{ cacheKey: key, value, ttlSeconds }]); } Read the comment abbove, because the code looks like a mistake and isn’t. The obvious implementation of “write the value, then register it” is await super.set(…) followed by a registration. That is two round trips, and an invalidation landing between them never sees the value — which then survives to its TTL with nothing pointing at it. Delegating to registerMany puts the SET in the same transaction as the SADD. A key in a category this strategy doesn’t own falls through to the parent and gets a plain SET, which is what the base class is for. 🎨 The decorator /* * Cache an async method’s result. On a hit the method is not called. On a miss the result is written * through the strategy’s set. Concurrent misses for one key in this process share one call. * * A rejection is never cached and writes nothing. undefined is never cached. null is cached only * with { cacheNegative: true }. / export function Cache(cacheKey: CacheKey, ttl: TTL | number, strategy: CacheStrategy, options: CacheOptions = {}) { assertValidTtl(ttl); const negativeTtl = options.negativeTtl ?? ttl; if (options.cacheNegative === true) assertValidTtl(negativeTtl); return function <This, Args extends [string, …unknown[]], Result>( target: AsyncMethod<This, Args, Result>, context: ClassMethodDecoratorContext<This, AsyncMethod<This, Args, Result>>, ): AsyncMethod<This, Args, Result> { const methodName = String(context.name); // Single-flight: one in-flight load per key, per decorated method, in this process. const inFlight = new Map<string, Promise>(); // async with no await on purpose: an unconfigured cache or a bad entity ID throws synchronously // below, and callers expect a rejected promise, not an exception from the call expression. return async function (this: This, …args: Args): Promise { const { service, tenant, strategies } = requireRegistry(@Cache on {methodName}()); const key = buildCacheKey(service, tenant, cacheKey, args); const store = strategies[strategy]; const pending = inFlight.get(key); if (pending !== undefined) return pending; const load = (async (): Promise => { const cached = await store.get(key); if (cached !== null) return JSON.parse(cached) as Result; // No try/catch here on purpose: a rejection must propagate and write nothing. const result = await target.apply(this, args); if (result === undefined) return result; if (result === null) { if (options.cacheNegative === true) await store.set(key, “null”, negativeTtl); return result; } await store.set(key, JSON.stringify(result), ttl); return result; })().finally(() => { inFlight.delete(key); }); // Registered synchronously, before load can settle, so a concurrent miss joins it. The cleanup // is chained onto the promise: returning load from inside a try/finally would run the finally // at once and end single-flight before the load had even started. inFlight.set(key, load); return load; }; }; } Four things in there are worth more than they look. The registry is resolved at call time, not at decoration time. A decorator evaluates when the class is defined, long before a Redis connection exists. So the strategies live in a small registry each service fills once at bootstrap, and a decorated method looks them up per call. Call one before configureCache and it throws a message naming the missing setup — it does not silently bypass the cache, which is the failure mode you would never notice. Single-flight. Fifty concurrent misses for one key make one call to the origin. Without it, a slow origin plus any warm-up loop is a self-inflicted thundering herd — the same failure this article criticises FLUSHALL for causing, arriving through the front door. There is deliberately no try/catch around the origin call. A rejection must propagate and write nothing. That is the bug from the last section, fixed by leaving code out. The cleanup is chained, not wrapped. inFlight.delete(key) hangs off .finally() on the promise rather than sitting in a try/finally around a return, because return inside a try leaves the block before the promise settles — single-flight would end before the load had started. 📝 Registering, and why the transaction shape matters /* * Register a batch using the same NX/GT rule as register(). Optional values are written with * SET EX inside the transaction, closing the write/registration interleaving window. * Validate the entire input before writes, then pipeline at most batchSize records per MULTI. * Returns the count of newly added references. Runtime Redis errors do not roll back writes; * callers must treat a rejection as potentially partial and retry or rebuild their fixture. / async registerMany(records: readonly Registration[]): Promise { const validated = records.map((record) => { assertValidTtl(record.ttlSeconds); const parsed = this.parse(record.cacheKey); if (parsed === null) { throw new Error(not a valid cache key for this index: {record.cacheKey}); } return { …record, indexKey: parsed.indexKey }; }); let added = 0; for (const batch of chunk(validated, this.batchSize)) { const multi = this.redis.multi(); const addOffsets: number[] = []; let commands = 0; for (const { cacheKey, indexKey, ttlSeconds, value } of batch) { if (value !== undefined) { multi.set(cacheKey, value, “EX”, ttlSeconds); commands += 1; } addOffsets.push(commands); multi.sadd(indexKey, cacheKey); multi.expire(indexKey, ttlSeconds, “NX”); multi.expire(indexKey, ttlSeconds, “GT”); commands += 3; } const replies = await multi.exec(); if (replies === null) throw new Error(“MULTI aborted while registering cache keys”); if (replies.length !== commands) { throw new Error(expected {commands} replies from register MULTI, got {replies.length}); } for (const [err] of replies) { if (err) throw err; } for (const offset of addOffsets) { if (replies[offset]?.[1] === 1) added += 1; } } return added; } The method validates the entire input before issuing writes, then processes bounded batches. When a record includes a value, its SET, SADD and index-expiry commands are queued in one transaction. The expiry commands serve separate purposes. NX establishes an expiry on a newly created set. GT extends an existing expiry when needed. Using GT alone is insufficient because Redis treats a persistent key as having an infinite TTL for that comparison. A transaction prevents other clients’ commands from interleaving during execution. It does not undo successful commands when another queued command fails at runtime. The method therefore checks every reply and treats a rejection as potentially partial. Recovery must account for the value and reference writes that may already have succeeded. See Redis transaction behavior. 🧹 Invalidating an entity This is the whole new design — invalidation processes each entity in three stages: read its references, delete the values, then remove the observed references. /* * Delete the cache for a set of entities through the index. * * Per entity, in this order: SMEMBERS → UNLINK the values (batched) → SREM the members we * observed (batched). Values before references, so an interrupted or failed run leaves the index * still listing exactly what remains to delete and the same call retried finishes it. * * Every recorded member is deleted unconditionally — no timestamp check. Deleting an absent key * is free; skipping a live one because a clock ran fast is a correctness bug. * Per-entity Redis errors are collected in incomplete; other entities continue. Counters include * acknowledged commands from partially completed entities. Invalid coordinates reject before I/O. / async invalidateEntities( tenant: string, category: string, entityIds: readonly string[], ): Promise { const entities = entityIds.map((entityId) => ({ entityId, indexKey: this.indexKeyFor(tenant, category, entityId), })); const result: InvalidationResult = { entities: 0, membersObserved: 0, valuesUnlinked: 0, referencesRemoved: 0, incomplete: [], }; let next = 0; const workerCount = Math.min(this.concurrency, entities.length); const runWorker = async (): Promise => { for (;;) { const entity = entities[next++]; if (entity === undefined) return; try { await this.invalidateOne(entity.indexKey, result); result.entities += 1; } catch (err) { result.incomplete.push({ entityId: entity.entityId, error: err instanceof Error ? err.message : String(err), }); } } }; await Promise.all(Array.from({ length: workerCount }, () => runWorker())); return result; } private async invalidateOne(indexKey: string, result: InvalidationResult): Promise { const members = await this.redis.smembers(indexKey); result.membersObserved += members.length; for (const batch of chunk(members, this.batchSize)) { // Use a local reply before +=: concurrent workers must not overwrite another’s update. const removed = await this.redis.unlink(…batch); result.valuesUnlinked += removed; } for (const batch of chunk(members, this.batchSize)) { const removed = await this.redis.srem(indexKey, …batch); result.referencesRemoved += removed; } } Delete values before clearing references. If UNLINK fails, the index retains references that can be used for another attempt. It may also retain names already deleted before a failure or lost reply; the references are an outstanding-work list, not an exact inventory of surviving values. Recovery depends on those references still being available when the retry runs. Remove observed members rather than the whole set. A newly added, different key name is left intact. Re-registration of the same key name is a separate race: set membership does not identify versions of a value. The concurrency section below describes that limitation. Report partial completion. An entity’s Redis error is recorded in incomplete; other workers continue. Counters include acknowledged operations, including work on an entity that later fails. A lost reply can make the reported count lower than the work Redis performed. Bound command arguments. UNLINK and SREM receive fixed-size groups. This avoids passing a very large member list into a single JavaScript call. The initial SMEMBERS still reads the full set. ✀ Pruning An entity with many short-lived variants would otherwise accumulate references forever. Pruning asks Redis what still exists rather than trusting a stored timestamp: /* * Drop index references whose cache value has already expired or been deleted out from under * the index. Never deletes the set itself. A maintenance operation, not part of the delete path. / async prune(tenant: string, category: string, entityId: string): Promise { const indexKey = this.indexKeyFor(tenant, category, entityId); let cursor = “0”; let membersChecked = 0; let membersRemoved = 0; do { // COUNT is a hint, not a hard limit; chunk each page before EXISTS/SREM. const [nextCursor, members] = await this.redis.sscan(indexKey, cursor, “COUNT”, this.batchSize); cursor = nextCursor; for (const batch of chunk(members, this.batchSize)) { const pipe = this.redis.pipeline(); for (const member of batch) pipe.exists(member); const replies = await pipe.exec(); if (replies === null || replies.length !== batch.length) { throw new Error(incomplete EXISTS pipeline while pruning {indexKey}); } const missing: string[] = []; replies.forEach(([err, reply], i) => { if (err) throw err; if (reply === 0) { const member = batch[i]; if (member !== undefined) missing.push(member); } }); membersChecked += batch.length; if (missing.length > 0) membersRemoved += await this.redis.srem(indexKey, …missing); } } while (cursor !== “0”); return { indexKey, membersChecked, membersRemoved }; } SSCAN traverses the set incrementally. Its COUNT argument is a hint, and a scan can return a member more than once. Accordingly, membersChecked counts observations rather than distinct members. The subsequent existence checks and removals are separate operations. A writer can recreate a value after EXISTS reports it missing but before SREM removes its reference. Pruning is therefore a best-effort maintenance operation, not an atomic check-and-remove procedure. It needs coordination with writers if losing such a reference is unacceptable. The method does not explicitly delete the whole index. Redis removes a set automatically when its last member is removed. See SREM behavior. 🐌 The legacy path, for comparison It can be seen in demo’s v1 endpoint, it utilizes the same deletion command, only discovery differs: /* * The legacy path for one user: enumerate the whole keyspace for keys naming this user, then * UNLINK them in batches. The pattern must keep both :: delimiters — *<userId>* would also * match entityIndex::demo::activeSubscription::<userId> (whose name ends at the id) and anything * with those characters in a params tail. */ private async invalidateLegacy(userId: string): Promise { const matches = await this.redis.keys(*::{userId}::*); let removed = 0; for (let i = 0; i < matches.length; i += BATCH_SIZE) { removed += await this.redis.unlink(…matches.slice(i, i + BATCH_SIZE)); } return removed; } ⏱️ Benchmark results The benchmark measures the latency of a simple GET operation while comparing cache-key discovery using KEYS with discovery using a per-entity index. It runs on Redis 7.0.15 using a fixture containing six cached values plus one index key per entity. Before collecting any measurements, the benchmark verifies that both discovery methods return the same set of cache keys. Each row includes two trials, alternating which method runs first. Each trial has a warm-up, a minimum duration and a minimum sample count. The table includes the number of lookup observations, n: Cached values Total keys KEYS median (n) Index median / p99 (n) Competing GET during KEYS During index 100,002 116,669 85 ms (47) 0.096 / 0.270 ms (33,999) 85 ms 0.096 ms 500,004 583,338 525 ms (10) 0.098 / 0.215 ms (33,260) 523 ms 0.099 ms 1,000,002 1,166,669 987 ms (10) 0.107 / 0.304 ms (29,431) 987 ms 0.107 ms 2,000,004 2,333,338 2,309 ms (10) 0.095 / 0.226 ms (34,223) 2,291 ms 0.095 ms 8,570,004 9,998,338 10,957 ms (10) 0.095 / 0.261 ms (35,437) 10,937 ms 0.095 ms The KEYS sample ranges were 83–116 ms, 514–550 ms, 951–1,062 ms, 2,224–2,588 ms and 10,844–12,091 ms, respectively. At approximately ten million total keys, the median KEYS lookup took 10.957 seconds. The indexed lookup took 0.095 ms. Across the five sizes, indexed medians ranged from 0.095 to 0.107 ms; each entity still had six variants. The competing client shows the effect on unrelated work. In the largest fixture, its median GET latency was 10.937 seconds while scans ran, compared with 0.095 ms during indexed lookups. The scan affected more than the client that requested it. These are key-discovery measurements, not timings of complete invalidation or cache population. 🚀 Run the demo yourself The whole proof of concept is on GitHub: github.com/msilberg/redis-entity-index — four Express services and one Redis, in Docker. Redis is populated with mock data through the three hops below, each crossing a real system boundary: benchmark (seed) —HTTP—> test-api —HTTP—> mock-billing (“the third party”) │ └── @Cache writes Redis on the miss git clone https://github.com/msilberg/redis-entity-index cd redis-entity-index && make up # seeds 2M records by default open http://localhost:3000 A Few Words on Building the Demo with an Agent Loop This demo was my first project built from scratch with the Ralph Wiggum loop — I wrote the specification and acceptance criteria up front, then let a single coding agent work through them iteratively until it could validate its own work, rather than steering it prompt by prompt. I used the snarktank/ralph implementation: a prd.json, task specifications with executable self-checks, and documented Redis schemas and HTTP contracts that the agent was instructed to follow rather than invent. The specifications and loop script are committed alongside the services, making the entire process inspectable. Ralph loop did a decent job. Across twelve stories, the loop produced four services, a deterministic seeder, a WebSocket chart, and a make verify command that can actually fail. Two things made the biggest difference, and neither was the loop itself: writing acceptance criteria that the agent could verify on its own, and reviewing the output carefully enough to catch where it drifted. And it eventually succeeded in satisfying the predefined criteria. That said, deciding whether those criteria are correct is still our job as human engineers. 🤔 What conclusions I’d take to the next system The local benchmarks show how repeated keyspace scans affect both the client requesting them and other clients sharing the Redis process. The repository includes the implementation, benchmark scripts and recorded samples so readers can examine the results and repeat the experiment. The design suggests several practical lessons: Design invalidation alongside reads. A composite key supports exact lookups, but an invalidation event may provide only an entity ID. An index supplies the relationship between that ID and its cache keys. Measure the effect on other clients. The duration of an expensive command is only part of its cost. Requests sharing the same Redis process can also be delayed. Preserve recovery information. Deleting cached values before removing their references supports retries after interrupted deletion. Expiration and concurrent writes still require explicit handling. Store only the information the index needs. If invalidation removes every recorded key, per-reference expiry timestamps add complexity without helping that operation. State the concurrency limits. An index improves discovery, but does not by itself prevent stale fills or races involving reused key names. Those require additional coordination. The implementation, benchmarks and setup instructions are available on github.com/msilberg/redis-entity-index. I’m Michael Silberg, a senior full-stack engineer specializing in Node.js, TypeScript and React, with experience in payments, subscriptions and platform infrastructure. I’m exploring senior engineering opportunities where I can contribute to backend architecture, performance and reliability. If that matches what your team is building, connect with me on LinkedIn.

View original article