Caching: building smartcache (Part 1)

An old line, traced back to Phil Karlton at Netscape, holds that computer science has only two hard problems: cache invalidation and naming things.

The side quest at the end traces where that line comes from.

For years it read as a joke. Then a few weeks of living the first half of it ended the laughing. This is that story. It starts with the boring part, which is where it always starts.

At smritea.ai, the backend runs on Go. For a while, every piece of code that needed a cache wrote its own version of the same fifteen lines:

1. Check Redis and return the data on a hit.
2. On a miss, read the database, write the row to Redis, and return it.

That works, until the bugs that are hard to track show up. By the third or fourth service, the same bug was waiting to happen in slightly different clothes.

Before AI started doing the typing, this is what happened:

1. One developer forgot to set a TTL.
2. Another did not treat a cache error as a miss.
3. A third had to ship a quick fix and had no time to invalidate on write.
4. A look at the code said the team needed better engineering practice. A look at the pull requests said who had approved them: the author of this post. The clean-up went on the list for later.
5. Later never came.

Then AI arrived, and the same mismatches now appear in ten times as many places, ten times as often.

None of that is hard to fix on its own. The hard part is fixing it consistently across a growing number of services when the fix gets copy-pasted instead of shared.

The answer was a library, smartcache. It has one generic cache type, a few well-understood failure modes handled once, and a swappable backend.

The shape of the cache

The core type is Cache[T], generic over whatever you cache. It sits on a small backend interface:

type CacheStore interface {
	// Get returns the raw bytes for key, or ErrStoreMiss if the key is absent.
	Get(ctx context.Context, key string) ([]byte, error)
	// Set stores val under key with the given ttl. A ttl <= 0 means no expiry.
	Set(ctx context.Context, key string, val []byte, ttl time.Duration) error
	// Delete removes key. Deleting an absent key is not an error.
	Delete(ctx context.Context, key string) error
	// Exists reports whether key is present (and not expired).
	Exists(ctx context.Context, key string) (bool, error)
}

Cache[T] never touches Redis directly. It talks to CacheStore, so a Redis-backed store and an in-process map-backed store (memstore, built for tests) are interchangeable. Reads follow the read-through pattern:

func (c *Cache[T]) GetByKey(ctx context.Context, key string, loader Loader[T]) (*T, Outcome, error)

Call it with a key and a loader function. On a hit, you get the cached value. On a miss, loader runs, its result goes into the cache, and you get that back. Writing has the mirror shape: PutByKey runs a writer and caches exactly what it returns. The caller never has to remember to cache anything.

That was the simple part. The interesting part is what happened once services started using it.

Problem one: everyone misses at the same time

A cached key expires. In the next few milliseconds, twenty requests for that key arrive. All twenty see a miss, because none of them knows about the other nineteen. All twenty read the same row from the database at the same moment. This is the cache stampede, also called the thundering herd. It gets worse exactly when it hurts most: a hot key under load.

The fix needs no cleverness, only coordination between concurrent callers of the same key. Go's singleflight package does that. One call runs, and everyone else waiting on the same key gets its result:

var res any
var lerr error
if c.group != nil {
	res, lerr, _ = c.group.Do(key, doLoad)
} else {
	res, lerr = doLoad()
}

doLoad is the closure that calls the loader and fills the cache. group.Do keys on the cache key itself, so twenty concurrent misses on "user:5" collapse into one database call. The other nineteen callers get the shared result. Singleflight runs by default, and each cache can turn it off.

Problem two: everyone expires at the same time

Stampede protection covers concurrent misses on one key. A second version of the failure hits many keys. A batch of keys written with the same TTL all expire together, and the result is a wave of misses across different keys. The cause is the same, synchronized timing, with a different trigger.

The fix is jitter: shave a small random amount off each TTL, so keys written together do not expire together.

// defaultJitterFraction is the fraction of the base TTL that jitter may shave
// off when a cache does not override it. 0.10 => an effective TTL in
// [0.9*base, base].
const defaultJitterFraction = 0.10

var jitterRand = rand.Float64

// applyJitter returns a downward-jittered TTL: base - jitterRand()*fraction*base.
// It returns base unchanged when base <= 0 (infinite/none) or fraction <= 0
// (jitter disabled). The result is always in [(1-fraction)*base, base] and is
// never negative, since jitterRand() is in [0,1) and fraction is in [0,1).
func applyJitter(base time.Duration, fraction float64) time.Duration {
	if base <= 0 || fraction <= 0 {
		return base
	}
	delta := time.Duration(jitterRand() * fraction * float64(base))
	return base - delta
}

Every TTL, positive and negative (more on that below), passes through this before use. A 10% jitter on a 10-minute TTL means each key expires somewhere between 9 and 10 minutes. Across a few thousand keys, the expiry wave becomes a trickle.

Problem three: negative caching

The third problem shows up with lookups that can legitimately miss: a user ID that does not exist, or a slug someone mistyped. If requests for a missing key keep arriving, each one falls through to the database, finds nothing, and does the same again next time. The cache cannot help, because there is nothing to cache. The way out is to cache the fact that the key is missing, not the missing thing itself.

// negativeMarker is stored in place of a real value to negative-cache "not found".
var negativeMarker = []byte("\x00smartcache\x00negative\x00")

When the loader reports ErrNotFound and you set a negative TTL, GetByKey writes this marker instead of a real value:

case errors.Is(lerr, ErrNotFound):
	if c.opts.NegativeTTL > 0 {
		if sErr := c.setValue(ctx, key, negativeMarker, c.negativeTTL()); sErr != nil {
			return nil, ErrNotFound
		}
	}
	return nil, ErrNotFound

The next request for that key hits the marker, recognizes it, and returns "not found" without touching the database. The marker lives for a shorter TTL than a real hit, because a newly created record should show up sooner than an updated one. Negative caching stays off by default. Turn it on with NegativeTTL, and only where a flood of missing-key lookups is plausible.

Keep that TTL low. The cache should not stand in the way for long, in case the database changes. One open idea: remove the negative key whenever a write touches that key, which makes it truly write-through. That might be too much.

Putting it together

sequenceDiagram
    accTitle: How smartcache handles a read
    participant A as Request A
    participant B as Request B
    participant C as Cache[T]
    participant SF as singleflight
    participant DB as Database

    A->>C: GetByKey("user:5", loader)
    B->>C: GetByKey("user:5", loader)
    C->>SF: group.Do("user:5", doLoad)
    Note over SF: B arrives while A's load is in flight, so it joins the same call
    SF->>DB: loader(ctx) runs once
    DB-->>SF: value
    SF-->>C: value, shared with both callers
    C-->>A: Loaded
    C-->>B: Loaded (same value, no second DB call)

Wrap a Manager around all this and you get per-cache OTLP metrics for free. They cover hit, miss and load counts, plus load latency, so no service hand-rolls its own instrumentation. Register a cache once, and stampede protection, jitter and negative caching are already there. Turn on only what a given cache needs.

None of these three problems is unusual. They are the standard failure modes of caching anything at scale. Redis's own docs on the cache-aside pattern and its cache layer architecture guide cover the same ground. The theory did not change anything. One shared place for the fixes did, instead of re-deriving them per service.

What it didn't solve

Everything above assumes one key maps to one value. That held until a repository needed to look up a User three ways: by ID, by email and by slug. What does "cache the user" mean when three doors lead into the same room? Caching the value three times means an update must hit three keys, and a bug leaves two of them stale. Caching it once under the ID means the email and slug lookups never use the cache.

The difficulty has a precise location. On a single Redis instance, none of this causes trouble, because with everything on one node nothing can hotspot. On Redis Cluster, it becomes one. Updating the value and its aliases atomically requires Redis to keep all those keys on the same node. Forcing that onto a busy or large entity puts its whole traffic on one node, no matter how big the cluster is. Part 2 picks up there, and the fix took two tries to get right.

Browse the real code in smartcache. Part 2 goes deeper into the trade-offs.

Side quest

The Karlton line at the top is real, but its trail on the internet is thinner than its fame suggests. The detour was worth taking.

The earliest known appearance online is Tim Bray's blog, from December 2005. Bray says he first heard it from Karlton around 1996 to 1997. Martin Fowler's 2009 bliki entry popularized the line. Karlton's own son has written about hearing him say it as early as around 1970 at Carnegie Mellon. The son cannot say whether that was the first time either.

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

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