Discord: Elixir with 5 million concurrent users

01 · CONTEXT

A real-time product built on pub/sub

According to Discord itself, almost everything the product does boils down to publish and subscribe (pub/sub). The user opens a WebSocket connection and gets a session process (a GenServer). That process talks to remote Erlang nodes that host the guild processes, the internal name for a Discord server.

Everything published in a guild is distributed to every session connected to it. When a user joins, the guild also publishes their presence to the other connected sessions.

1. The client opens a WebSocket connection to the gateway, and the connection gets a session process.

2. The session talks to the remote nodes that host the guild processes.

3. When something is published in a guild, the event is distributed to every session connected to it.

4. When a user joins, the guild publishes their presence to the other connected sessions.

5. The product's API was served by Python, separate from the real-time gateway.

In 2015 Discord chose Elixir and Python as its main languages. Elixir took the WebSocket gateway, responsible for relaying messages and replicating in real time, and Python took the API. According to the case study, the Python API was a monolith and the Elixir stack comprised about twenty services.

02 · FANOUT

When a large guild cannot publish

The design worked while Discord served groups of up to 25 people. Later, servers appeared with up to 30 thousand concurrent users. At peak, the guild processes stopped keeping up with their message queues, and features that generated messages had to be turned off manually to relieve the load.

The team benchmarked the hot paths of the guild processes and found an obvious culprit: sending messages between Erlang processes cost more than expected. A single call to send/2 took 30 to 70 microseconds of wall-clock time, because Erlang descheduled the calling process, and publishing an event from a large guild at peak could take 900 ms to 2.1 s. Since Erlang processes are effectively single-threaded, the way to parallelize is to partition them.

The first idea was to create one process per publish, but it was dropped: each publish could be scheduled at a different moment, and clients depend on the linearizability of events.

1. Sending messages between Erlang processes cost more than expected: a single call to send/2 took 30 to 70 microseconds of wall-clock time.

2. In a large guild, publishing an event at peak could take 900 ms to 2.1 s.

3. Manifold receives the recipients and groups them by the remote node where each one lives.

4. Instead of one send per recipient, the sender calls send/2 at most once per remote node, to that node's partitioner.

5. On the remote node, the partitioner applies consistent hashing to the PIDs, groups them by number of cores, and sends to child workers.

6. The workers deliver the messages to the actual processes, and the linearizability guaranteed by send/2 is preserved.

03 · CONSISTENT HASHING

The ring that says where each guild lives

Discord is a distributed system built on consistent hashing, which requires a ring structure to find the node responsible for an entity. The problem showed up in reconnection bursts: the process that owned the ring could not keep up with the requests and the whole system overloaded.

The hot-path numbers, according to the post: an average user is in 5 guilds, a sessions Erlang VM can have up to 500 thousand active sessions, and on connect each session queries the remote node of each guild of interest. A request/reply between processes costs about 12 microseconds and, if the sessions server went down and restarted, the ring lookups alone would take about 30 seconds.

1. On connect, the session queries the ring to find the remote node of each guild it is interested in.

2. In reconnection bursts, the process that owned the ring could not keep up with the requests and the whole system overloaded.

3. Moving the ring to ETS improved performance, but copying the large structure into and out of ETS was most of the cost.

4. With the mochiglobal technique, adopted in the version called FastGlobal, the data becomes a constant on a shared read-only heap, read without copying.

04 · BOUNDED CONCURRENCY

Speeding up the path moved the bottleneck

After speeding up the node lookup, the guild registry processes on the guild nodes began to accumulate queues. The slowness of the lookup had previously acted as backpressure that protected them; the problem became that almost 5 million session processes competed for ten registry processes, one on each guild node.

The worst part was the cycle: the session's call timed out and left the request in the registry's queue. The session retried after a backoff, and requests piled up to an unrecoverable state. The sessions' message queues bloated until the entire Erlang VM ran out of memory, with cascading crashes.

1. Almost 5 million sessions competed for ten guild registry processes, one on each guild node.

2. The call timed out and the request stayed in the registry's queue; the retry with backoff piled up requests to an unrecoverable state.

3. The sessions' message queues bloated until they blew the Erlang VM's memory, with cascading crashes.

4. The solution was a semaphore: an atomic counter in ETS of pending requests, so the session gives up early when the number is high.

5. When the presence service went down because of an unrelated problem, the sessions did not oscillate.

Discord ruled out a circuit breaker because it did not want a burst of timeouts to lead to a temporary state in which no attempts are made. In other languages, an atomic counter of pending requests would allow giving up early, which in practice is a semaphore. In Erlang, the key piece was :ets.update_counter/4, which does an atomic conditional increment on a number stored under an ETS key.

05 · LESSONS AND LIMITS

What to take into your design

The Elixir case study adds pieces of the ecosystem: Discord uses Cowboy for WebSocket connections and GenStage for back-pressure and load-shedding, and builds a partial mesh between Elixir services, with etcd for service discovery and shared configuration. According to the case study, the chat infrastructure team is made up of five engineers.