Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

Introduction — The Problem Was Not Requests per Second, It Was the Deploy
Steady-State Cost and Startup Cost Are Different Problems
Where the Number Twelve Hours Came From
Why Redis Was Not Added
How to Put a Sliding Window in an Object Store
Sixteen Bytes — Representation Is Performance
Why a Quadratic-Complexity Worker Was Good Enough
Correctness Lives in the Conditional PUT and Leader Election Is an Optimization
References

Introduction — The Problem Was Not Requests per Second, It Was the Deploy

Session handling is usually optimized like this. Encrypt the session information into a cookie and the gateway no longer has to query the database on every request. That removes one network round trip per request, which is a large win in a system handling hundreds of thousands of requests per second.

But when a logout or a permission change happens, an already-issued cookie has to be revoked. So every gateway has to hold a "list of revoked sessions" in memory. Lookups stay close to free.

The problem Session revocations at scale, which Canva published on July 22, 2026, addresses is what comes next: how you seed that in-memory list in the first place.

In the original wording, hundreds of gateway pods each pulling more than a million revocation records from MySQL at startup turned "deploys into an organized stampede against the database."

Steady-State Cost and Startup Cost Are Different Problems

The heart of this story is here. The metrics we look at when we evaluate a cache are mostly about the steady state. Hit rate, lookup latency, memory usage. All of those can be excellent and the system can still fall over.

An in-memory cache has a second cost that the metrics do not capture well.

Steady-state cost — the per-request lookup. Here it is effectively zero.
Startup cost — the cost of fetching the entire dataset from somewhere when a process comes up. Looking at a single pod it is unremarkable, but a deploy restarts not one pod but the entire fleet at once.

Startup cost scales with pod count, repeats as often as you deploy, and lands at the most sensitive moment of all, the rollout. It is a completely different axis from steady-state load.

The stopgap Canva used shows exactly this character. They got by adding a lot more read replicas. Those read replicas existed not to serve steady-state query volume but to absorb the spike at the moment of deploy. Which means that outside deploy windows they were mostly idle.

Where the Number Twelve Hours Came From

How long do you have to hold the revocation list in memory? Not forever.

Canva session cookies are refreshed periodically. At refresh time the database is queried anyway, so a token that has been through a refresh does not depend on the in-memory cache. So they keep only 12 hours of revocations in memory and check tokens that need refreshing through the slow MySQL lookup.

What is good about this design is that the upper bound on cache size is derived from the token lifetime. The size is decided by a time window rather than by the number of users. Double the users and the rate of revocations doubles, but the length of the window stays the same.

In cache design, once you have an answer to "what is safe to throw away," the size problem usually solves itself. Here the refresh path is the safety net, so discarding anything older than 12 hours does not break correctness.

Why Redis Was Not Added

The standard way to scale reads is to put a cache between the database and the readers. Canva considered Redis too. The picture would be that the gateway requests the whole dataset from Redis at startup and then polls periodically for new revocations.

There were two reasons for rejecting it, and both apply to technology choices generally.

First, Redis is usually not deployed in a fully durable configuration. If the revocation list is lost, logged-out sessions come back to life. This is not a performance cache but a security boundary.

Second, in the original wording, it "would only move the problem from one datastore to another while adding considerable complexity to keep the caches consistent." The burden of operating the Redis cluster itself remains as it was.

This is the trap of the solution that stacks on one more layer. A new layer brings new failure modes, new operational burden, and new consistency problems along with it. The burden on the original layer went down, but the burden on the system as a whole can go up.

How to Put a Sliding Window in an Object Store

So they chose S3. Strong durability guarantees and efficient bulk downloads of large files were exactly the properties needed.

The problem is that S3 handles static blobs well, whereas this data is a window that keeps sliding. It is always the most recent 12 hours, and at every moment the front comes in and the back falls off.

The solution was to cut the window into 30-minute chunks and map one chunk to one S3 object. Three things follow from this decision at once.

There is no need to delete old revocations individually. The gateway just fetches the recent chunks.
The update unit gets smaller. You rewrite 30 minutes worth, not the whole 12 hours.
If you put the start time of the 30-minute window in the chunk name, you can walk the keys in sorted order and pick out only the chunks after the cutoff.

That last item is especially practical. S3 has no query for "just give me the recent ones," but if you name keys so they sort chronologically, a prefix listing gets you the same effect.

Sixteen Bytes — Representation Is Performance

This is the most instructive part of the write-up.

A single revocation has to carry two pieces of information: who it applies to (the principal), and up to which login time it applies. Lay the bits out frugally and it fits in 16 bytes. A chunk is a flat array of these 16-byte elements.

Add sorting on top. Sort by principal and binary search within a chunk becomes possible. As a result the gateway uses the downloaded bytes as they are, without converting them into another representation.

The previous implementation tracked one revocation as several Java objects. Switching to the dense binary representation shrank the in-memory cache size to one eighth, an 87.5 percent reduction.

In reality there are several kinds of revocation. Some invalidate only the information cached in the cookie without logging the user out, and some target an entire brand rather than an individual. So a few bits were reserved for flags, and as long as the sort by principal is maintained, several kinds can be mixed into one array.

To summarize: what reduced the cost of seeding the cache was not a new layer but a representation that requires no deserialization. When the download finishes, the cache is finished.

Why a Quadratic-Complexity Worker Was Good Enough

Keeping the chunks up to date is a different problem. Rewriting a chunk every time a revocation occurs would be unaffordable.

So an asynchronous worker takes this job. It keeps scanning the database, pulls revocations not yet uploaded to S3 in large batches, fetches the latest chunk, splices them into the sorted array, and uploads it again.

As the original points out itself, this looks at first like it does not scale. Filling a chunk with N records means processing the entire chunk once per fixed-size batch, which takes close to quadratic time in N. On top of that, the lost update problem makes horizontal scaling awkward.

But when measured, even an unoptimized implementation processing a few hundred records per batch delivered write throughput of more than 2000 per second, which exceeds the requirements of the foreseeable future. The original conclusion is exact: the worker was bottlenecked on network latency, not on computation.

Theoretical complexity only tells you the slope as the input grows; it does not tell you the actual time in your input range. Sorting a dense array of a few hundred thousand elements is nearly free for a modern CPU. In the range where constants dominate, you have to measure the constants.

Correctness Lives in the Conditional PUT and Leader Election Is an Optimization

The worker runs in multiple copies for availability and deployment. Implement it naively and you get a race against S3, where one worker's update quietly disappears between another worker reading and writing.

Canva uses two things.

Conditional PUT implements optimistic concurrency control. Every chunk update carries the precondition that "this chunk has not changed since it was first read," and when creating a new chunk it also checks that another process has not already created the same chunk. This precondition turns read-modify-write into an operation that only ever appends, guaranteeing that no data disappears no matter how the executions interleave.

ZooKeeper leader election is an optimization that keeps continuous conflicts from loading the system.

The order of those two sentences matters. The original writes explicitly that correctness cannot depend on leader election. A node can pause for an arbitrary length of time right before writing, and when it wakes up another node may already have become leader and written its own changes. Without the PUT precondition, the node that woke from its nap overwrites them.

In distributed systems, leader election almost always belongs in this position. It is a device for reducing conflicts, not a device for making conflicts impossible. Correctness has to hang on the atomic conditional operation the storage layer provides.

References

The figures in this post (more than a million revocations, a 12-hour window, 30-minute chunks, 16 bytes, an 87.5 percent memory reduction, more than 2000 per second, 2 read replicas) are all carried over as written from the Canva post above. They are not measurements I reproduced myself.