Key Design and Eviction in External Session Stores

Moving sessions out of process memory makes every request perform a lookup against a remote service. That service is usually a key-value store chosen for sub-millisecond reads and automatic expiry, and the design work that follows is mostly about three things: what the key contains, what the value costs to serialize and rewrite, and what happens when memory runs out.

The last of these is the one that produces outages. A store configured to evict under pressure will silently discard live sessions, and a store configured to refuse writes will fail logins at exactly the moment traffic is highest.

The key is a namespace, not an identifier

A session key combines a deployment-scoped prefix with a digest of the token. sess:prod:9f2c... is the shape: the prefix separates environments and record types that share one keyspace, and the digest ensures that a memory dump, a SCAN, or an operator running KEYS cannot read working credentials. Two applications sharing a Redis database without distinct prefixes will eventually collide, and the symptom is a session that resolves to another application’s record — a total authentication bypass that looks like random corruption.

Keys are also visible in slow-query logs, in MONITOR output, in cluster slot routing traces, and in any snapshot copied for debugging. Encoding a user identifier into the key makes those logs a directory of who is logged in and when. Hashing the token keeps the key opaque while remaining deterministic, so the same token always routes to the same slot.

In a clustered store the key determines placement. Redis Cluster partitions the keyspace into 16384 hash slots and assigns ranges to nodes; the CRC16 of the key, or of the substring inside {...} if a hash tag is present, selects the slot. A session record spread across several keys — profile, permissions, cart — is only operable with multi-key commands if all those keys carry the same hash tag, which means the tag must be derived from the session token and not from the field name. Without a tag, a transaction touching three keys fails whenever the keys land on different nodes.

What goes into the value

Record size drives both latency and memory. A few hundred bytes to a couple of kilobytes covers identity, scope, timestamps, and a CSRF token. Once the record includes a full permission set for an account with hundreds of group memberships, it grows into tens of kilobytes, and the cost is paid on every request that reads it, not once at login. Memcached’s default maximum item size is 1 MB, and its slab allocator makes size a first-class constraint: every item is placed in a slab class chosen for its size, and an item that fits no class is rejected even when the server has memory free. Keeping session records under a few kilobytes is a design constraint, not a micro-optimization.

Serialization choice matters less than versioning. JSON is readable and language-neutral at the cost of roughly two to three times the bytes of a compact binary encoding and a parse on every request. Whatever the format, the stored blob needs a schema version. When a deployment changes the record shape, records written by the previous version are still live, and a deserializer that assumes the new fields exist will fail on a fraction of requests for as long as the old records survive — up to one full idle timeout. A one-byte version prefix lets the reader treat unknown versions as “no session” and force a clean re-login, which is a visible but bounded outcome.

Read-modify-write is not atomic

A session lookup followed by an update is two operations, and requests for one session do not arrive in sequence. Two tabs, a polling widget, and a background fetch can all read the same record, each modify a different field, and each write back the whole blob. The later write wins entirely, erasing the other’s change.

Stores differ in what they offer. Redis executes a Lua script or a MULTI/EXEC transaction on a single node atomically, so a compare-and-set is expressible: read the version, apply the change, write only if the version is unchanged. Memcached offers cas with a per-item token and a gets/cas pair, and returns a distinct status when the token has changed, which the client retries. Plain SET on either store is last-write-wins.

-- KEYS[1] = session key; ARGV[1] = expected version, ARGV[2] = new payload,
-- ARGV[3] = ttl in seconds. Stored value is "version|payload".
local cur = redis.call('GET', KEYS[1])
if not cur then return 0 end
local ver = string.match(cur, '^(%d+)|')
if ver ~= ARGV[1] then return -1 end
redis.call('SET', KEYS[1], (tonumber(ARGV[1]) + 1) .. '|' .. ARGV[2], 'EX', ARGV[3])
return 1

Returning three distinct outcomes — missing, version conflict, written — is what makes retry logic possible. The alternative, retrying a blind overwrite, converts a conflict into silent data loss. Where the store supports neither script nor CAS, the design has to avoid shared mutable fields: keep each independently updated value under its own key, or accept that only one writer may exist per session at a time, enforced by a lock. Concurrent Mutations and Versioned Session Records works through the locking and versioning options in more depth.

Expiry is lazy, and eviction is not expiry

Both stores treat expiry as a hint. Redis removes expired keys in two ways: lazily, when a key is accessed and found stale, and by a background cycle that samples keys with a TTL set and deletes the expired ones. A key that is never accessed again and never sampled occupies memory past its nominal expiry. For session data the effect is small, since the volume of never-touched expired keys is bounded by the churn rate multiplied by the sampling latency, but it is not zero, and memory graphs of session stores routinely show a plateau above the number of live sessions.

Eviction is a different mechanism with a different trigger: memory pressure. Redis takes a maxmemory limit and a policy. allkeys-lru evicts any key, expired or not; volatile-lru and volatile-ttl only consider keys with an expiry set; noeviction refuses writes and returns an error. The policy interacts directly with session semantics. Under noeviction, a full store means SET fails, so a user who authenticates successfully cannot be given a session — the login appears to loop. Under allkeys-lru, sessions are evicted in favour of other data sharing the instance, so a cache-heavy neighbour can log users out by filling memory.

Dedicating an instance to sessions and configuring volatile-lru narrows the blast radius: only keys with a TTL are candidates, which is all session keys, and a missing key is indistinguishable from an expired one. A logical database does not isolate anything here, since maxmemory and eviction apply to the whole instance. The application must still handle a miss as “unauthenticated” rather than as an internal error, and must never treat a miss as “the store is down” — the difference determines whether the user sees a login page or a 500.

Memcached has no configurable eviction policy of the same kind: it is LRU, applied within slab classes, and items are evicted regardless of remaining TTL when the assigned slab is full. Its expiry field is a 32-bit value with a peculiarity worth knowing — a value up to 30 days (2592000 seconds) is interpreted as a relative offset from now, and anything larger is interpreted as an absolute Unix timestamp. A relative TTL just above the boundary is read as a timestamp near the start of 1970, so the item is stored and immediately expired.

Durability decides what a store failure means

Whether the store is a cache or a system of record changes the entire failure analysis. If sessions are a cache and losing them merely forces re-authentication, then an eviction, a restart, or a failed replication does not need to be survived. If a session is the system of record for a long-running workflow — a multi-step checkout, an upload in progress — losing it loses work, and the store needs persistence, replication, and a recovery story.

Redis offers snapshotting and append-only logging, both of which are asynchronous by default; a crash can lose the writes since the last snapshot or the last append sync. For sessions that is usually acceptable and should be stated as a decided trade rather than discovered during an incident. Making it synchronous on every write puts a disk operation on the login path and cuts throughput sharply, which is rarely worth it for authentication state.

Replication introduces the read-your-writes problem: a write goes to the primary, a subsequent read is served by a replica that has not applied it yet, and the user’s freshly rotated session appears invalid. Read-Your-Writes Across Replicated Session Stores treats the consistency techniques; the short version is that session reads must be pinned to the primary for a bounded interval after any write, or the write must carry a token the reader can wait on.

Sizing the store

Capacity follows from concurrency rather than from user count. The number of records is roughly the number of sessions active within the idle timeout, which for a site where a tenth of daily users are active at peak is far below the daily total. At 500 bytes per record, a million concurrent sessions occupy about 500 MB before allocator and key overhead, which in practice adds a meaningful fraction; planning at two to three times the raw payload is the honest starting point. The larger risk is not the average but the tail: a feature that stores an unbounded list in the session record turns a fixed per-user cost into one that grows with usage, and the growth is invisible until memory pressure triggers the eviction policy that logs everyone out.