Sharding Session Data and the Size Ceiling

Session stores grow along two axes, and the limits they hit are different in kind. Horizontal growth is a partitioning problem: more records than one node can hold, or more operations per second than one node can serve. Vertical growth is a payload problem: more bytes per session than the transport will carry, or more bytes per request than the network and the parsers will tolerate. Both are usually discovered late, because a session store looks like a cache until it is large.

Partitioning by token, and the indirection that saves a resharding

The natural shard key is the session identifier itself. Hashing it spreads keys uniformly regardless of how users behave, since the identifier is random. The alternative — sharding by user identifier — puts all of one user’s sessions on one node, which makes “sign out everywhere” a single-node operation, but requires that the user be known before the lookup. That is only true if the user identifier is encoded in the token, which reintroduces exactly the enumeration and disclosure problems that a random opaque token avoids.

Uniformity is the property to protect. A shard key derived from anything correlated with load — signup date, tenant, geography — produces shards that grow at different rates and cannot be balanced by moving a fixed fraction of keys. Random keys make the distribution predictable from the law of large numbers: with $N$ shards and $K$ keys, the least-loaded shard holds close to $K/N$ keys, and the deviation shrinks as $K$ grows.

The complication is that changing $N$ remaps keys. Hashing to a fixed number of partitions and mapping partitions to nodes separates the two concerns. A token hashes to one of, say, 4096 partitions, and a small membership table maps 4096 ranges onto the current node set. Adding a node takes over a contiguous set of partitions, which is a bounded fraction of the keyspace and does not depend on the node count at the moment of the change. Redis Cluster does this implicitly with 16384 slots; the same construction works for any store with a routing layer in front.

Resharding a live partition is a copy followed by a switch. The copy streams the keys to the destination; writes during the copy must go somewhere. The two options are to block writes for the partition’s duration, which for a large partition is a visible outage, or to dual-write to both locations and read from the old one until the copy catches up, then flip. Dual-write requires the destination to be authoritative for nothing until the flip, and it requires the copy to be idempotent — replaying a key that has since changed overwrites the newer value unless the copy respects versions. Session records that carry a version make the copy a merge rather than an overwrite, and that is the practical reason to have one.

Hot partitions and the tenant that owns a node

Uniform hashing distributes keys, not work. A shard can be hot because the keys on it belong to users who make many requests, or because one tenant’s sessions all share a routing prefix. If the key is a hash of a random token, the first cause is self-correcting: load is proportional to request count, and a hot shard is hot because its users are active, which averages out over a population. The second cause is not, because a tenant-prefixed key concentrates all of that tenant’s sessions on one shard no matter how many other tenants exist.

The fix is to keep the shard key random and carry the tenant in the value rather than the key. Tenant isolation then becomes an authorization check per record instead of a routing property, which is weaker in a shared store but avoids the imbalance. Where isolation is a hard requirement, the usual design is a shard per tenant with a router that knows the assignment, and the cost is that a large tenant cannot be spread across shards without splitting its keyspace by a second dimension.

Per-shard rate limits matter as much as capacity. A shard serving ten thousand operations per second has a tail latency that a shard serving a thousand does not, because queueing delay grows nonlinearly as utilization approaches one. Keeping peak utilization well below saturation — a margin of two to three times headroom is a reasonable starting point — costs memory that sits idle but bounds the tail. Load Balancer Session Affinity and Its Failure Modes makes the same argument about backend utilization: averages hide the queue.

The payload leaves the server on every request

A cookie is sent on every request to the matching path and host, in full, with no negotiation about whether the server needs it. A 1 KB session cookie on a page that issues 50 requests moves 50 KB of header data for one page view, and none of it is compressible across requests in HTTP/1.1. At a thousand page views per second that is tens of megabytes per second of upstream traffic carrying the same bytes.

HTTP/2 changes the arithmetic through HPACK, which maintains a dynamic table of header fields on both ends so that a repeated cookie is encoded as a short index rather than a literal string. RFC 7541 defines the mechanism, and the practical effect is that a large but unchanging cookie costs the connection very little after the first request. Two caveats: the encoder may choose to send a field literally rather than index it, and intermediaries that terminate and re-originate connections rebuild the table at each hop. HTTP/3 uses QPACK, which has the same shape with a different synchronization mechanism.

The hard ceiling is the cookie itself. RFC 6265 requires support for at least 4096 bytes per cookie including name, value, and attributes; browsers enforce roughly that, and an oversized cookie is dropped rather than truncated. A dropped session cookie is not an error the server can see — the request arrives with no cookie at all.

Server-side header limits are the second ceiling, and they are lower than most applications assume. nginx’s default large_client_header_buffers is 8 KB per header line: a request line longer than one buffer produces a 414 and a header field a 400, both before the application runs. Apache’s LimitRequestFieldSize defaults to 8190 bytes. Node’s HTTP parser defaults to a 16 KB total header size, configurable through --max-http-header-size. Go’s http.Server uses a 1 MB default for MaxHeaderBytes. A cookie that fits in 4 KB fits under all of them, but a design that splits state across several cookies can approach the aggregate limit without any single cookie being oversized.

What should not be in the cookie

The size pressure comes from putting facts in the token, and the facts that grow are the ones that should not be there. A permission list grows with the account’s complexity, not with its needs on any given request. A feature-flag snapshot grows with the deployment’s flag count. Both are candidates for a server-side lookup with a cache, keyed by the subject, rather than for per-request transport.

The middle position is a reference plus a small amount of frequently needed data: an opaque identifier, a generation counter, and perhaps a tenant hint, with everything else fetched. The fetched data can be cached in the application process or in a shared cache, and the cache entry is keyed by a value that changes when the data does, which is the versioning pattern from Concurrent Mutations and Versioned Session Records.

Encoding choices matter at the margin. Base64url expands binary data by a third — every three bytes become four characters — so a 1 KB binary record becomes about 1.4 KB on the wire. JSON adds field names and quoting on top, and a payload with a dozen short keys can spend more bytes on names than on values. A compact binary format, or a fixed set of bit flags for boolean state, cuts the size by a factor that is worth having when the budget is 4 KB.

Splitting across cookies and the ordering consequences

When one cookie will not hold the state, the temptation is several. Browsers permit at least 50 cookies per domain in RFC 6265’s minimum, so the count is rarely the limit; the aggregate header size, the per-line limits described above, and the ordering rules are.

Ordering is the subtle part. Cookies with the same name on different paths or domains are all sent, ordered by path length and then creation time, and the server must decide which to trust. A session split into sess and sess_meta is fine because the names differ. A session that sets sess on / and again on /app is not, because both arrive and the parser’s choice determines which one wins. Cookie Scope, Attributes, and Transport Rules covers the matching and ordering rules in detail.

A second consequence of splitting is atomicity across the parts. Two cookies updated by one response are delivered in one response, so they are consistent at the client. Two cookies updated by two concurrent responses are not: the browser applies whatever arrives, and a rotation that updates the identifier in one cookie while leaving the metadata cookie stale produces a session whose parts disagree. If the parts must agree, they should be one cookie, and the payload should shrink instead.

Capacity planning that follows from the numbers

Records, not users, drive capacity, and in steady state the record count is bounded by the idle timeout times the arrival rate: a million logins a day averages about a dozen per second, so a thirty-minute idle timeout leaves roughly twenty thousand live records on average and perhaps three times that at peak, not a million. At 500 bytes per record the raw payload is a few tens of megabytes; key overhead, allocator fragmentation, and replication factor multiply it by a small integer, and the shard count follows from dividing by a per-node budget with headroom.

The transport ceiling is independent of all that. Whatever the store holds, the bytes the client carries should stay in the hundreds, and anything that pushes them into the kilobytes should be justified by a lookup it removes from the common path.