Design Message Storage at Scale

Understanding the problem

Warm into the shape before reaching for a database. A message store sounds like the easy half of a chat product, the part you get for free once fan-out works. It is the opposite. Delivery moves a message once and forgets it. Storage keeps it forever, and every person who opens a channel, scrolls its history, or jumps to a search result reads it back. So the volume that matters is the read rate against a corpus that only ever grows. The entire design comes down to one question. How do you lay trillions of messages out on disk so that fetching the last fifty in one channel is cheap? And how do you make sure one runaway channel never drags the rest of the cluster down with it?

The Discord angle

Discord has published how it built this system, twice, so the interviewer may have read the same post you did. The 2017 write-up on storing billions of messages and the 2023 follow-up on storing trillions lay out the real data model, the real partition key, and the real failure they hit. Interviewers point candidates at those posts on purpose. A strong answer reasons the way Discord's engineers wrote it up: partition by channel plus a time window, cluster by a sortable id, and treat the hot partition as the named enemy. A generic "throw it in a NoSQL table" answer stands out for the wrong reason here, because the concrete, documented shape is sitting right there for anyone who prepared. This is the lesson where naming ((channel_id, bucket), message_id) out loud does real work.

Functional requirements

Keep the core small and let the interviewer widen it. The chain is short and read-heavy. Someone sends a message into a channel and it has to be durably stored, in order. Someone opens that channel and the most recent messages load. Someone scrolls up and older pages come back, walking backward through time. And because messages are not truly immutable, an author can edit or delete one, and the store has to reflect that on the next read. Two requirements are worth naming on purpose. Ordering, because messages in a channel have to come back in the sequence they were sent, so the storage layout has to encode time. And history reads dominating writes, because a message is written once but read by everyone who ever opens or scrolls the channel.

Non-functional requirements

Reason each target from what a message store is for, because the data model falls out of them. Durability comes first. A sent message must never be silently lost, so writes replicate before they are acknowledged. Read latency is the target you feel. Opening a channel should return its recent messages in low tens of milliseconds, because that read sits directly in front of a person waiting to see the conversation. Name the load skew early, because reads outnumber writes heavily, and in this store reads are the more expensive operation. So the layout has to make the common read, the last N messages in one channel, land in a single partition rather than scatter across the cluster.

Then the relaxation worth banking now and cashing in later. Message reads tolerate eventual consistency of a beat or two. If a brand-new message takes a moment to appear on a cold history fetch it self-heals, because the real-time gateway already pushed it to connected clients. The store does not have to be the instant source of truth for the live view. That is what lets it lean on a highly available replicated design rather than a strictly consistent one. Availability is non-negotiable, because a store that is down means nobody can read any history anywhere, so the design favors staying up and converging over blocking a read for perfect freshness.

Sizing the message mountain

Put the numbers down, because the partitioning scheme lives or dies on them. Take the message rate first. Discord runs on the order of billions of messages a day. Call it four billion for the arithmetic. Spread evenly that is about four billion divided by eighty-six thousand seconds, roughly forty-five thousand writes a second on average. Traffic concentrates in the busy evening hours and spikes when a huge server goes off, so peak runs several times higher, into the low hundreds of thousands of writes a second. That is the write floor the store has to absorb without flinching.

Now the part that makes this Discord-shaped: the total is enormous and it only grows. Four billion a day across roughly a decade is on the order of fourteen trillion messages. That is why Discord's own numbers moved from billions in 2017 to trillions by 2022. At a conservative kilobyte per row with metadata, trillions of messages is petabytes on disk, so this was never going to fit on one machine and the question becomes how to shard it. The last piece is the read pattern. Reads outnumber writes by something like an order of magnitude, and almost every read is the same shape: the most recent messages in one specific channel, then older pages as the reader scrolls up. That single dominant access pattern, recent-first within one channel, is the thing the primary key has to serve cheaply.

• Messages per day: ~billions. Call it ~4B for the math, ~45k writes/s average
• Total stored: trillions. Petabytes on disk; grew from billions (2017) to trillions (2022)
• Peak write QPS: low 100k/s. Evening concentration plus viral-server spikes over the average
• Read pattern: recent-first. Reads dominate ~10:1; last N in one channel, then page backward

One relationship in that grid sets the whole architecture. The corpus is petabytes and unbounded, but the hot working set, the messages people read, is the recent tail of each active channel. So the design's real job is to keep each channel's recent messages physically together and cheap to fetch, while the cold trillions sit undisturbed until someone scrolls back to them. Get the partition key right and the common read touches one place; get it wrong and every channel open scatters reads across the cluster. That choice is the first deep dive, and everything before it is just earning the right to make it.

The set-up

Core entities

Name the objects before drawing. Three carry the design, and the one worth fixing early is the message id, because it is not a random uuid. It is a Snowflake, a 64-bit id whose high bits are a timestamp, which means ids sort in the same order as time. That single property is what turns "fetch the newest messages" into an ordered range scan instead of a sort, and it is why the id is also the clustering key inside a partition.

Then state the storage choice and the key plainly, because interviewers ask both. Messages go in a wide-column store, the Cassandra-and-then-ScyllaDB family. The workload is enormous, write-heavy at ingest, and read as ordered ranges within a partition, and a partitioned, clustered wide-column layout is built for exactly that. The primary key is ((channel_id, bucket), message_id). The partition key is the pair (channel_id, bucket), so all of one channel's messages for one ten-day window sit together on the same replicas. The clustering key is message_id, so within that partition the messages are already stored in time order. Recent-first history is then a bounded, ordered scan of one partition, no cross-node fan-out and no sort.

API

Keep the external surface thin. Writing a message appends a row, reading history is a bounded backward scan anchored on a message id, and edits and deletes are targeted updates on a single row. Reference these by name in the walkthrough and the deep dives.

Two calls carry the weight. GET /channels/{channelId}/messages is the hot path, and its before cursor is doing something specific. It anchors the scan on a message id the client already holds, so paging backward means "give me the fifty messages with ids just below this one." That is an ordered range read inside the partition, not an offset the database has to count to. When before crosses the start of a bucket, the read walks into the previous bucket, which is the one seam pagination has to handle. POST /channels/{channelId}/messages looks trivial but sets everything up: it mints the Snowflake id, and because the id carries a timestamp, the bucket is computed from the id rather than stored or looked up.

High-level design

Build it one requirement at a time and name each bottleneck as it surfaces. The write path is thin and the read path is where the interesting work lives. In front of the database sits a data-services layer, a role Discord fills with a purpose-built Rust service. Its job is to protect the store from the read pattern. It routes every request for a given channel to the same place and collapses duplicate concurrent reads into one. Behind it is the wide-column store itself, holding the messages, with a separate search index fed asynchronously off to the side so full-text queries never touch the hot path. The diagram codes each box by role: blue for clients, violet for our services, green for the data stores. The walkthrough tags the same components.

1) Write a message. A message author posts to the message API through POST /channels/{channelId}/messages. The API mints a Snowflake message_id, and because the id's high bits are a timestamp, it computes the ten-day bucket straight from the id rather than storing or looking it up. It hands the write to the Rust data services layer, which routes it to the instance that owns this channel and appends one row to the wide-column store under the partition key (channel_id, bucket). Writes replicate across a few nodes before the ack, so a message is durable the moment the author sees it land. The bottleneck being punted is what happens when this channel is the one that is a thousand times busier than the rest, which the partitioning deep dive takes up.

2) Load recent history. A history reader opens the channel and calls GET /channels/{channelId}/messages?limit=50. The message API forwards it to the Rust data services layer, which routes by channel to the owning instance and asks the wide-column store for the top of the current partition. Because the messages are clustered by message_id and Snowflakes sort by time, the newest fifty are the first fifty rows of the partition, an ordered range read with no sort and no cross-node fan-out. The reader sees the conversation in low tens of milliseconds. The hard part deferred here is the celebrity case: 500,000 people open the same channel in the same second, and every one of them wants the same rows. That is the coalescing deep dive.

3) Page backward through history. As the reader scrolls up, the client re-calls the same endpoint with before set to the oldest message_id it currently holds. The Rust data services layer turns that into "the fifty rows with ids just below this cursor," another bounded ordered scan of the same partition. When the cursor crosses the start of the ten-day bucket, the read steps into the previous bucket and continues. History becomes a walk across a small sequence of partitions instead of one unbounded scan. The seam being punted is exactly that bucket boundary, and how a sparse channel that spans empty buckets avoids a slow crawl, which the pagination deep dive resolves.

4) Edit, delete, and search. An author edits or deletes through PATCH or DELETE on a single message id. The Rust data services layer turns that into a targeted update on one row. The id and its position in the partition never move, so ordering is untouched and only that row's content or delete flag changes. Separately, every write also flows asynchronously into the search index, an inverted index that answers keyword queries off the hot path, so a full-text search over history never competes with channel reads. Two threads run off this stage: how mutation coexists with an append-mostly, replicated store, and why edits and deletes have to be idempotent. Those close out the deep dives.

Technology choices

None of these boxes is a specific product yet; each is a slot you fill in the room. Put a concrete tool in every slot, defend the category behind it, and know the failure mode, because the pressure lands on how the pick degrades under the exact skew this system has.

• The message store is a wide-column database, Cassandra originally and ScyllaDB today, partitioned by (channel_id, bucket) and clustered by message_id. This category fits because the workload is a massive, ever-growing set of small rows read as ordered ranges within a partition. A partitioned-and-clustered layout serves that cheaply, and it scales by adding nodes instead of sharding a relational database by hand. The failure mode to name is the hot partition: one blazing channel-bucket concentrates reads on a few replicas and drags tail latency across the whole cluster, because reads cost more than writes here. Discord moved from Cassandra to ScyllaDB, a C++ rewrite that is shard-per-core with no garbage collector. The fleet shrank from 177 nodes to 72, and historical-read p99 fell from tens of milliseconds to around 15, largely because Cassandra's JVM GC pauses were gone.
• The Rust data-services layer is a stateful intermediary tier that does consistent-hash routing plus request coalescing. A dedicated tier in front of the database fits because of the read pattern. Many clients want the same recent rows of the same channel at once, a thundering-herd problem the database should never see. It routes all requests for a channel to one instance so that a burst of identical reads becomes a single in-flight database query whose result fans back to every waiting caller. The failure follow-up is an instance dying with in-flight work. Routing is by consistent hash, so the channel rehashes to another instance and coalescing resumes. The store behind it is the durable record, so nothing is lost; reads are only briefly slower.
• The message API is a stateless service pool behind a load balancer, minting Snowflake ids on write. Stateless is right because each request is self-contained once the id is minted, so you add workers as traffic climbs and any node can serve any request. The subtle correctness point is id generation. Snowflake ids must be monotonic and unique across all API nodes, so each node carries a worker id and the ids embed a timestamp plus a per-node sequence. That keeps them sorting by time without a central coordinator. The failure mode is clock skew across nodes; bounding it and never letting the sequence wrap within a millisecond keeps ordering intact.
• The search index is a separate inverted index, something like Elasticsearch, fed asynchronously from the message write stream. Keeping search out of the primary store is right because full-text ranking is a different access pattern that would pollute the row cache and steal IO from channel reads. State the freshness tradeoff plainly. The index lags the store by the length of the async pipeline, so a just-sent message may be searchable a second or two late. That relaxation is fine, because live reading already comes from the gateway and the store. In the failure mode, the indexer falls behind under a write burst. Users see staler search results while message reads stay fast and succeed, and that is where you want the pain to land.

One contrast is worth naming, because it is a common probe. The wide-column store and the search index both hold every message, so why not one system. They are different animals. The store is the durable, ordered record optimized for one access pattern, recent-first within a channel, and it must never lose a write. The index is a derived, best-effort view optimized for a completely different pattern, keyword lookup across everything, and it is allowed to lag and to be rebuilt from the store at any time. Collapsing them means one workload's queries starve the other's, which is why they stay separate. Down the whole list, name the brand so the interviewer knows you have run one, then defend the category, because the category is what the follow-up questions test.

Potential deep dives

The rest of the score is made here. The interviewer picks a component and pushes. These four are where this prompt leans, and the first two are the ones a Discord loop almost always reaches.

1) How do you pick a partition key that survives a giant channel?

This is the decision the whole design rests on. In a wide-column store the partition key decides which rows live together on the same replicas, and it decides which reads are cheap. Pick it wrong and either your common read scatters across the cluster, or one channel grows a single partition without bound until it becomes the thing that breaks. The tension is real. You want a channel's messages together for cheap history reads, but a server with hundreds of thousands of members can send orders of magnitude more messages than a quiet DM. "A channel" as the unit is both the right grain and a landmine.

The Discord angle

The ((channel_id, bucket), message_id) key is the most quotable fact about how Discord stores messages. Naming it, with the ten-day window and the sub-100-MB reason, separates a prepared answer from a generic one. Discord's engineering write-ups say reads cost more than writes in this store. A busy channel-bucket becomes a hot partition that hurts latency across the whole cluster, and that is why the bucket exists. An interviewer may ask how your scheme handles "a server with a small group of friends versus a server with hundreds of thousands of people." They want to hear that both are the same shape, channel plus time bucket. The second one is exactly the hot partition your read-side layer is built to absorb. Framing the bucket as a deliberate size bound rather than an arbitrary detail is the tell that you understood the real system.

2) A celebrity posts and 500,000 people load the same channel at once. What breaks?

This is the failure the bucket alone cannot fix. Time-bucketing bounds how big a hot partition gets, but it does nothing about a sudden read stampede against it. Picture a huge announcement channel: someone posts, a notification goes out, and half a million clients open that one channel in the same few seconds. Every one of them wants the same recent rows of the same partition. Naively that is 500,000 near-identical database reads landing on the handful of replicas that own the partition. Reads are the expensive operation here, so those replicas saturate and latency climbs for everyone, well beyond that channel. The question is how to keep one viral channel from turning into a cluster-wide brownout.

The caching patterns lesson generalizes read-through caching and the thundering-herd problem that coalescing solves.

3) How does backward pagination work across bucket boundaries?

History reads are the dominant traffic, and scrolling up is the part that looks simple until the buckets get in the way. Within one ten-day bucket, paging back is clean: anchor on the oldest message id the client holds and read the fifty rows with ids just below it. The trouble starts at the edges. A cursor eventually reaches the start of its bucket, and the next older message lives in a different partition. Worse, a channel that has been quiet for months has empty buckets in between, so a naive "read the previous bucket" can return nothing and force another hop. The question is how to keep pagination a bounded number of cheap reads rather than an open-ended crawl.

4) How do edits and deletes live in an append-mostly store?

A message store is append-heavy but not append-only, because people edit and delete. That has to coexist with a design tuned for ordered appends and replicated for availability. The shape helps here. A message is one row identified by (channel_id, bucket, message_id), so an edit or a delete is a targeted update on exactly that row. The id never changes, so the message keeps its position and ordering is untouched. The interesting questions are what a delete does to a partition, and how mutation behaves when the store is eventually consistent and clients retry.

The Discord angle

The Cassandra-to-ScyllaDB migration shows you have read past the data model into how Discord operates this store, and it is a clean case of picking a tool to kill a specific failure. Discord's account is concrete. The Cassandra fleet had grown to 177 nodes holding trillions of messages. The pain was the JVM garbage collector, whose stop-the-world pauses on hot partitions caused latency spikes the on-call team had to babysit. Discord moved to ScyllaDB, a C++ reimplementation of the same data model with a shard-per-core design and no garbage collector. The cluster shrank to 72 nodes, and historical-read p99 dropped from tens of milliseconds to around 15. A one-time Rust migrator backfilled the data at millions of messages a second. If an interviewer asks how you would evolve this store, keep the data model. It was already right, and the win came from removing GC pauses from the hot path. That reads as someone who understands the system Discord runs, not just the diagram.

What is expected at each level

That is a lot of surface, and how much you have to land depends on the level the loop is calibrated for. Treat the inferred rungs below as directional: a mid engineer, Senior as the independent bar, and a Lead-and-beyond scope above it. The design round carries more weight the more senior the role.

Mid-level engineer

Breadth leads here, roughly 80/20. Reach a working end-to-end shape: messages land in a wide-column store partitioned by channel, recent history is an ordered read of one partition, and the API pages backward with a message-id cursor. The non-negotiable is choosing the partition key deliberately and explaining why "the last fifty messages in a channel" should be one cheap read rather than a scatter-gather. You do not have to arrive at time-bucketing or coalescing unprompted, but you should recognize that a giant channel is a problem when the interviewer raises it. The bar: a coherent skeleton you can defend, with the interviewer smoothing the rough edges.

Senior engineer

Depth enters, roughly 60/40, and this is the primary independent bar. Reach a great tier on your own somewhere: the (channel_id, bucket) partition key with the sub-100-MB sizing reason, or the data-services layer that routes by channel and coalesces the celebrity-post stampede. You should raise the hot-partition failure mode and the read-heavy skew before being asked, and defend why reads cost more than writes in this store rather than treating it as symmetric. The bar: a near-complete design where you found the hot partition and the thundering herd yourself and had a concrete answer for each.

Lead and beyond

Depth leads across several components as scope widens, roughly 40/60. Expect to drive the coalescing layer end to end, including why it is written for predictable low latency with no GC pauses and how it degrades when an owning instance dies. Reason about pagination across bucket boundaries and sparse channels, edits and deletes as idempotent mutations under eventual consistency with last-write-wins, and the operational reality of tombstones and compaction. Treat the ScyllaDB migration as an example of choosing a tool to remove a specific failure, GC pauses on the hot path, rather than as trivia. You lead, the interviewer steers rather than rescues. The bar: you own the partition-plus-coalescing model and keep durability, read latency, and mutation correctness as separate, defensible decisions through every refinement.