mufassall

Cheat sheet · Case studies

Case: how Discord stores messages

16 min · Advanced · mufassall.dtwin.uz/en/l/case-discord-messages/

← Open the lesson

The problem

From one MongoDB collection to Cassandra and then to ScyllaDB: how Discord kept trillions of chat messages readable. Partition keys, tombstones, hot partitions, data services with request coalescing, and a migration at 3.2 million messages a second. Sources: https://discord.com/blog/how-discord-stores-billions-of-messages and https://discord.com/blog/how-discord-stores-trillions-of-messages

What you learn

  • Why a partition key of (channel, time bucket) keeps partitions small
  • How deletes become tombstones and what they cost on reads
  • Hot partitions: one busy channel slows a whole node
  • Data services: request coalescing and routing by a consistent hash of the channel
  • How a large live migration was made fast, checked and finished
Final scene
30%40%40%40%

Diagram as code

The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.

Mermaid: flowchart

flowchart LR
  n_users(["Users"])
  n_api["API monolith"]
  n_ds["Data service A"]
  n_ds2["Data service B"]
  n_scylla[("ScyllaDB")]
  n_users --> n_api
  n_api --> n_ds
  n_api --> n_ds2
  n_ds --> n_scylla
  n_ds2 --> n_scylla

Mermaid: request sequence

sequenceDiagram
  participant n_api as API monolith
  participant n_mongo as MongoDB
  participant n_n2 as Cassandra node 2
  participant n_n1 as Cassandra node 1
  participant n_ds as Data service A
  participant n_ds2 as Data service B
  participant n_mig as Rust migrator
  participant n_scylla as ScyllaDB
  Note over n_api,n_mongo: 2015: one collection, one index
  n_api->>n_mongo: db.messages.find({ channel_id: 1234 }).sort({ created_at: -1 }).limit(50)
  Note over n_api,n_n2: Cassandra: a channel split into time buckets
  n_api->>n_n2: CREATE TABLE messages (
  Note over n_api,n_n2: Deleted messages still cost reads
  n_api->>n_n2: SELECT * FROM messages WHERE channel_id = 1234 AND bucket = 41 LIMIT 50#59;
  n_n2-->>n_api: 1 row (about 20 s)
  Note over n_api,n_n1: From 12 nodes to 177
  n_api->>n_n1: cluster cassandra-messages, early 2022
  Note over n_api,n_n2: One busy channel slows a whole node
  n_api->>n_n2: CONSISTENCY QUORUM#59;
  n_n2-->>n_api: slow: one (channel_id, bucket) partition, one set of replicas
  Note over n_api,n_n1: Compaction falls behind, GC pauses grow
  n_api->>n_n1: n1: pending compactions keep growing
  Note over n_api,n_ds: A data service between the API and the database
  n_api->>n_ds: gRPC: get messages (simplified)
  Note over n_ds,n_n2: Request coalescing: one query for many readers
  n_ds->>n_n2: many users ask for the same row at the same time
  Note over n_api,n_ds2: Route by channel with a consistent hash
  n_api->>n_ds2: routing key: channel_id
  Note over n_mig,n_scylla: Moving trillions of messages to ScyllaDB
  n_mig->>n_scylla: migrator (Rust): token range done, checkpoint saved to SQLite
  Note over n_ds,n_scylla: Fewer nodes, flat latency
  n_ds->>n_scylla: after the switch to ScyllaDB (May 2022)

D2

direction: right

n_users: "Users" {
  shape: rectangle
}
n_api: "API monolith" {
  shape: rectangle
}
n_ds: "Data service A" {
  shape: rectangle
}
n_ds2: "Data service B" {
  shape: rectangle
}
n_scylla: "ScyllaDB" {
  shape: cylinder
}

n_users -> n_api
n_api -> n_ds
n_api -> n_ds2
n_ds -> n_scylla
n_ds2 -> n_scylla

PlantUML: request sequence

@startuml
participant "API monolith" as n_api
database "MongoDB" as n_mongo
database "Cassandra node 2" as n_n2
database "Cassandra node 1" as n_n1
participant "Data service A" as n_ds
participant "Data service B" as n_ds2
participant "Rust migrator" as n_mig
database "ScyllaDB" as n_scylla
note over n_api, n_mongo : 2015: one collection, one index
n_api -> n_mongo : db.messages.find({ channel_id: 1234 }).sort({ created_at: -1 }).limit(50)
note over n_api, n_n2 : Cassandra: a channel split into time buckets
n_api -> n_n2 : CREATE TABLE messages (
note over n_api, n_n2 : Deleted messages still cost reads
n_api -> n_n2 : SELECT * FROM messages WHERE channel_id = 1234 AND bucket = 41 LIMIT 50;
n_n2 --> n_api : 1 row (about 20 s)
note over n_api, n_n1 : From 12 nodes to 177
n_api -> n_n1 : cluster cassandra-messages, early 2022
note over n_api, n_n2 : One busy channel slows a whole node
n_api -> n_n2 : CONSISTENCY QUORUM;
n_n2 --> n_api : slow: one (channel_id, bucket) partition, one set of replicas
note over n_api, n_n1 : Compaction falls behind, GC pauses grow
n_api -> n_n1 : n1: pending compactions keep growing
note over n_api, n_ds : A data service between the API and the database
n_api -> n_ds : gRPC: get messages (simplified)
note over n_ds, n_n2 : Request coalescing: one query for many readers
n_ds -> n_n2 : many users ask for the same row at the same time
note over n_api, n_ds2 : Route by channel with a consistent hash
n_api -> n_ds2 : routing key: channel_id
note over n_mig, n_scylla : Moving trillions of messages to ScyllaDB
n_mig -> n_scylla : migrator (Rust): token range done, checkpoint saved to SQLite
note over n_ds, n_scylla : Fewer nodes, flat latency
n_ds -> n_scylla : after the switch to ScyllaDB (May 2022)
@enduml

PlantUML: components

@startuml
left to right direction
agent "Users" as n_users
component "API monolith" as n_api
component "Data service A" as n_ds
component "Data service B" as n_ds2
database "ScyllaDB" as n_scylla
n_users --> n_api
n_api --> n_ds
n_api --> n_ds2
n_ds --> n_scylla
n_ds2 --> n_scylla
@enduml

Recap

What to take from Discord's story.

1) Choose the partition key by how you read, and bound it: channel plus a time bucket. 2) Deletes are writes; tombstones and compaction are part of the read cost. 3) Uneven keys make hot partitions; protect the database with a layer in front of it. 4) Coalesce identical reads and route by the same key so they meet. 5) For a big migration, make the copier fast and restartable, and compare reads from both stores before switching.

Sources: https://discord.com/blog/how-discord-stores-billions-of-messages and https://discord.com/blog/how-discord-stores-trillions-of-messages

Numbers: at the start and at the end

MetricStartEnd
Read p995 ms15 ms
Insert p9970 ms5 ms
DB nodes1272

Steps

  1. Case 2015: one collection, one index

    Discord first kept every message in one MongoDB collection with a compound index on channel_id and created_at.

  2. Fix Cassandra: a channel split into time buckets

    Discord moved messages to Cassandra.

  3. Problem Deleted messages still cost reads

    In Cassandra a delete is a write: a tombstone that hides the old value until compaction removes both.

  4. Case From 12 nodes to 177

    By early 2022 the messages cluster had 177 nodes and trillions of messages.

  5. Problem One busy channel slows a whole node

    A big server posts an announcement and a huge number of people open the same channel at once.

  6. Problem Compaction falls behind, GC pauses grow

    Cassandra merges its files in the background (compaction).

  7. Fix A data service between the API and the database

    Discord put data services between the API monolith and the database clusters.

  8. Fix Request coalescing: one query for many readers

    When many users ask for the same row at the same time, the data service queries the database only once.

  9. Fix Route by channel with a consistent hash

    Requests are routed by a key; for messages the key is the channel id.

  10. Fix Moving trillions of messages to ScyllaDB

    ScyllaDB is compatible with Cassandra, written in C++, has no garbage collector and splits work per CPU core.

  11. Case Fewer nodes, flat latency

    Discord switched to ScyllaDB in May 2022.

  12. Recap Recap

    What to take from Discord's story.