Caching: one entity under many keys (Part 2)

Quick recap

This is Part 2 of a series. If you haven't read Part 1, here is the short version. Every Go service at smritea.ai kept reinventing the same caching logic, so it moved into a small generic library called smartcache. The library offers a Cache[T] on a swappable backend, with read-through and write-through built in. Building it surfaced three real problems, each fixed in a few lines:

• A cache stampede, fixed with singleflight.
• Synchronized TTL expiry, fixed with jitter.
• Repeated database hits on keys that don't exist, fixed with negative caching.

Part 1 closed on a gap that none of those fixes solved. A User has three lookup paths: by ID, by email and by slug. That is one row with three doors into it. Cache it three times, and an update must land in three places at once. Miss one, and the email lookup serves stale data for a user whose name already changed. Cache it once under the ID, and the other two lookups get no caching at all. This post picks up there.

The trade-off at the center of this post rhymes with something more famous, the CAP theorem. CAP says a distributed system cannot maximize consistency, availability and partition tolerance all at once, so something has to give. What follows is not CAP itself, but it has the same shape.

Solving the three-keys gap turned into a small distributed-systems problem. The fix ended up as two different answers, depending on whether you run one Redis instance or a cluster. Before getting into why, the CAP comparison needs precision, because the comparison invites overstating.

A trade-off that rhymes with a famous theorem

Loosely, yes, but not literally. CAP is about consistency versus availability when a network partition splits your nodes apart. This post covers a trade-off between two different things. One side keeps every key of an entity atomic under one Lua call. The other side spreads those keys across a cluster, so no single node carries one entity's whole traffic. No partition occurs. The weaker option here does not give up correctness, only the atomic update of every key in one step. This is the same kind of problem CAP made famous: two good properties cannot both peak at once, so something has to give. This is not CAP itself, and the post offers no CAP proof.

Store the value once, point at it from everywhere else

The fix for "one row, three keys" is pointer indirection. The value lives at exactly one key. Every alias is a small key that resolves to it instead of holding a copy.

bc::{user}::5                          -> {"ID":"5","Name":"Ada",...}   (the value, stored once)
bc::grp::{user}::email::[email protected]    -> 5                             (pointer -> primary key)
bc::grp::{user}::slug::ada             -> 5                             (pointer -> primary key)

flowchart LR
    accTitle: One value key with alias pointers
    E["bc::grp::{user}::email::foo＠bar.com"] -->|resolves to primary key 5| V["bc::{user}::5<br/>the value, stored once"]
    S["bc::grp::{user}::slug::ada"] -->|resolves to primary key 5| V
    classDef value fill:#2EC4B6,stroke:#0E7C72,color:#101010
    class V value

A read through an alias takes two hops. Read the pointer, get the primary key, then read the value key built from that primary key. Delete the value key, and every alias breaks at the same instant. Each one resolves to a missing key, which reads as a miss and reloads from the database. The result: one value, no duplication, and eviction in one place.

Why this needs a Lua script

Writing or evicting a group takes more than one command. Evict-by-alias must read the pointer and find the primary key it points to. Next it reads that record's list of registered aliases. Then it deletes the value key and every one of those alias pointers. That means reading, branching on what the read returns, and deleting many keys. Redis transactions (MULTI/EXEC) cannot do that, because they queue commands blind. A transaction cannot read a value midway and decide what to delete from it. WATCH plus a retry loop can get there, but the cost climbs fast under concurrent writes to the same entity.

The straightforward fix is a Lua script. The read-branch-delete sequence runs atomically on the Redis server itself, with no client-side retry loop. Here is the whole read path for the single-instance version:

local pk = redis.call('GET', KEYS[1])
if not pk then return false end
local v = redis.call('GET', ARGV[1] .. pk)
if not v then return false end
return v

The script does the pointer lookup, the primary-key resolve and the value read in one round trip.

Atomicity creates a hotspot

For that script to be atomic, every key of one entity must live on the same Redis Cluster node. That covers the value, every alias pointer and the membership index. Lua scripts can only touch keys on one node at a time. Left alone, Redis Cluster hashes each key independently and scatters the keys across nodes by design. A Lua call that touches keys on different nodes does not degrade gracefully. Redis rejects it with the same CROSSSLOT error that any multi-key command spanning slots gets. Redis Cluster offers a way to force keys together: a hash tag. The part of a key wrapped in {} decides which slot the key lands on. Redis Cluster ignores the rest of the key name for hashing. Tag every key of one entity with {user}, and they all land on the same slot. That is exactly the constraint the atomic script needs.

// AliasColocated tags every key of an entity with {ns}: all of the entity's keys share one
// Cluster slot and every op is a single atomic Lua cascade. One slot per entity (hotspot risk
// on Cluster with a hot entity). Default.
AliasColocated AliasMode = iota

It works, and the update is genuinely atomic, but it pins one entity's whole key set to one node. Redis's own clustering best practices post is direct about this. Overusing hash tags gets you "an unbalanced cluster, or worse, one full node and many empty nodes," and the advice is to use them sparingly. A User with a normal amount of traffic is fine under this scheme. A User with heavy traffic puts its whole load on one node, no matter how many nodes the cluster has. The same holds for an entity type with a naturally hot member, like a popular org or a trending post. You can check this yourself with CLUSTER KEYSLOT: every key sharing a hash tag maps to the same slot number.

Two strategies, chosen per cache

Rather than pick one answer for every cache, smartcache exposes both and lets you choose:

type AliasMode int

const (
	// AliasColocated tags every key of an entity with {ns}: all of the entity's keys share one
	// Cluster slot and every op is a single atomic Lua cascade. One slot per entity (hotspot risk
	// on Cluster with a hot entity). Default.
	AliasColocated AliasMode = iota
	// AliasSharded tags value+members with {ns:pk} (one slot per record) and reverse pointers with
	// {ns:field:value} (one slot per alias), distributing load. GetByAlias is a two-hop resolve with
	// validate-on-read; writes/evicts are a record-slot atomic Lua plus best-effort reverse-pointer
	// ops. No hotspot, no stale reads, weaker cross-key atomicity (self-healing).
	AliasSharded
)

flowchart TB
    accTitle: Sharded and colocated alias keys compared
    subgraph Colocated["Colocated: one slot per entity"]
        direction LR
        C1["bc::{user}::5"]
        C2["bc::grp::{user}::email::foo＠bar.com"]
        C3["bc::grp::{user}::slug::ada"]
    end
    subgraph Sharded["Sharded: one slot per record, one per alias"]
        direction LR
        R1["bc::{user::5}<br/>record slot"]
        P1["bc::grp::{user::email::foo＠bar.com}<br/>own slot"]
        P2["bc::grp::{user::slug::ada}<br/>own slot"]
    end
    classDef colocated fill:#E63946,stroke:#A3202B,color:#FFFFFF
    classDef sharded fill:#2EC4B6,stroke:#0E7C72,color:#101010
    class C1,C2,C3 colocated
    class R1,P1,P2 sharded

The obvious question: if tagging every key with {user} gives perfect atomicity in one Lua hop, why not always do that? Because it permanently ties that entity's whole key set to whichever single node its hash tag lands on. That works for most entities. It fails for the one entity that turns out to be unusually busy or large. No routing gets around it without changing the tag, and changing the tag gives up the atomicity in the first place.

Colocated is the default: one atomic call, correct everywhere, and fine while no single entity's traffic outgrows one node. Sharded spreads the value and each alias pointer across different slots. A read then takes two network hops through two different nodes instead of one atomic call on one node. That is a small, real latency cost, paid so that no node absorbs an entire entity's traffic. This part needs its own correctness argument.

Making the distributed version correct anyway

Spreading keys across slots gives up atomicity: a pointer and the record it points to no longer update together. The one thing that must not happen is a stale pointer returning the wrong value. The fix is to check the pointer's claim against the record before trusting it:

local v = redis.call('GET', KEYS[1])
if not v then return false end
if redis.call('HGET', KEYS[2], ARGV[1]) ~= ARGV[2] then return false end
return v

KEYS[1] is the value, and KEYS[2] is the record's own membership index, which lists the fields that point at it and the value of each. If the record's index no longer lists this alias, the script returns nothing: a miss, not a wrong answer. A pointer left stale by a race resolves to "not found" and reloads. This check runs on every read. It turns "the pointer might be stale" into "a stale pointer can only ever produce a safe miss."

Cleanup gets the matching treatment. The script deletes a pointer only if it still points at the record that is going away:

if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
end
return 0

That is compare-and-delete. Without it, evicting user 5 right after their email moved to user 99 could delete the pointer that now correctly belongs to user 99. With it, the delete fires only if the pointer still agrees with the record the eviction targets.

Sharded gives up less than it sounds like. It does not give up correctness, because the read-time check rules out a wrong value for any caller. It does not give up strong consistency of the data either. It gives up atomicity across keys. The price is an extra network hop per read. Occasionally a stale reverse pointer also lingers until something overwrites or compare-deletes it. That shows up as a few extra cache misses while the cache heals itself, never as stale data reaching a caller. This is the actual trade: a little bounded latency and cache-miss noise, spent to keep one hot entity from owning a node.

Both strategies expose the same public interface, and Cache[T] never knows which one it talks to:

type AliasOps interface {
	GetValue(ctx context.Context, primary string) ([]byte, error)
	PutValue(ctx context.Context, primary string, val []byte, ttl time.Duration) error
	EvictByPrimary(ctx context.Context, primary string) error
	GetByAlias(ctx context.Context, ref AliasRef) ([]byte, error)
	PutByAlias(ctx context.Context, primary string, ref AliasRef, val []byte, ttl time.Duration) error
	EvictByAlias(ctx context.Context, ref AliasRef) error
}

And picking a strategy is one field on registration:

ttl := time.Hour
sharded := smartcache.AliasSharded
cache, err := smartcache.RegisterAliasGroup[User](mgr, "user", &smartcache.EntityOptions{
	TTL:       &ttl,
	AliasMode: &sharded, // omit this and you get AliasColocated, the default
})

Where this leaves things

Use Colocated for a single Redis instance, or a cluster where no entity should get disproportionately hot.

Use Sharded once you are on a cluster and that assumption stops holding. Neither one is a half-measure.

Colocated is fully atomic by design. Sharded stays correct by construction, even under races, with a different set of properties.

One real gap remains. Every operation on an alias-group cache goes through the Lua path. That includes a plain lookup by primary key that never belonged to an alias group. The result is correct, but the Lua call wastes work for the common case.

The fix on paper is a Bloom filter in front of the Lua call. It checks membership cheaply first, and skips straight to a plain GET when no one registered the key as an alias. The filter is not built yet, because it only optimizes performance and has no correctness story attached.

The real code is public: smartcache. Stay tuned for more chapters, in this story and in the project itself.

Thanks for reading this far. If it helped, find the author on these sites:

• Medium
• Dev.to
• LinkedIn
• X
• GitHub