Discord: from Go to Rust (GC spikes)

01 · CONTEXT

The service that knows what you have already read

This case comes from a Discord engineering account of the Read States service. Its job is to track which channels and messages each person has already read. It is accessed when someone connects, when a message is sent, and when a message is read, that is, it sits on the product's critical path.

The data volume is large: there are billions of Read States, one per user per channel. Each one carries counters that need to be updated atomically and that often reset to zero, such as the number of mentions you have in a channel.

In the Go version, the service was fast most of the time, but every few minutes a large latency spike appeared that hurt the experience. The investigation attributed the spikes to Go's memory model and garbage collector (GC). The initial port to Rust was completed in May 2019.

02 · ARCHITECTURE

In-memory LRU cache, Cassandra behind it

Each Read States server keeps an LRU cache (Least Recently Used) of Read States, to get fast atomic counter updates. According to the account, each cache has millions of users, tens of millions of Read States, and hundreds of thousands of updates per second.

For persistence, the cache is backed by a Cassandra cluster. The Read States of an evicted key are written to the database, and every update also schedules a write for 30 seconds later; according to the account, there are tens of thousands of database writes per second.

1. Clients access Read States when they connect, when they send a message, and when they read a message.

2. The server keeps the Read States and their counters in an in-memory LRU cache, to update counters atomically and quickly.

3. When a key is evicted from the cache, its Read States are written to the Cassandra cluster.

4. Besides eviction, every update schedules a write to the database for 30 seconds later.

03 · THE PROBLEM

Periodic spikes and the cache size dilemma

In the peak-hour charts, the latency and CPU usage of the Go service had spikes roughly every 2 minutes. The charts are from Go version 1.9.2; versions 1.8, 1.9, and 1.10 were also tested, with no improvement.

In Go, the memory of a key evicted from the cache is not freed right away: the garbage collector runs from time to time to find memory with no references and free it, and that work can slow the program down. The code was already efficient and made few allocations, so the team was not generating much garbage.

Studying Go's source code, the team saw that it forces a garbage collection when none has run in 2 minutes, regardless of heap growth. Tuning the GC percent, however, changed nothing, because the service was not allocating memory fast enough to force more frequent collections.

1. At peak hour, the Go service shows latency and CPU spikes roughly every 2 minutes.

2. The garbage collector has to scan the entire LRU cache to know whether memory is free of references, and that is what makes the spikes so large.

The spikes were large because the collector had to scan the entire LRU cache to know whether memory was really free of references. With a smaller cache, collection produced smaller spikes, and the team moved to several LRU caches partitioned per server. The trade-off was higher latency at the 99th percentile, since the user's Read State is less likely to be in the cache and, when it is not, a database read is needed.

1. The team moved to several LRU caches partitioned per server, and with smaller caches the garbage collector produced smaller spikes.

2. In exchange, with smaller caches the Read State is less likely to be in memory, so more requests go to the database and the 99th percentile latency goes up.

04 · THE CHANGE

No garbage collector: immediate freeing

Rust has no garbage collection. It tracks who can read and write memory and enforces the memory rules at compile time. In the Rust version of Read States, when a user's Read State is evicted from the LRU cache, the memory is freed immediately, without waiting for a collector.

The choice of this service had practical reasons: it was small and self-contained, and the team wanted to build the frameworks and libraries for building new services entirely in Rust. There was an obstacle, because at the time stable Rust did not have a good solution for async Rust. The team committed to using Rust nightly until async was fully supported on stable.

05 · RESULTS

Load test, canary and larger cache

The rewrite started as a direct translation and was then trimmed down. In the load test, the Rust version's latency was as good as Go's, with no latency spikes. Even with basic optimization, Rust outperformed the hand-tuned Go version, and after profiling and optimizing, the Rust version beat the Go one on latency, CPU and memory.

The optimizations included swapping the HashMap for a BTreeMap in the LRU cache to use less memory, swapping the metrics library for one that uses Rust's modern concurrency, and reducing the number of memory copies. The rollout was smooth thanks to the load test.

1. In Rust, the memory of a Read State evicted from the cache is freed immediately, without waiting for a collector.

2. The service was first deployed to a single canary node.

3. The canary surfaced a few missing edge cases, and the team fixed them.

4. Soon after, the Rust version was rolled out to the entire fleet.

5. In Go, a larger cache lengthened garbage collections. After a few days running successfully in Rust, and without that problem, the team increased the LRU cache capacity to 8 million Read States.

With the larger cache, average time came to be measured in microseconds and the maximum in milliseconds. Upgrading tokio, the async runtime the team uses, also gave a free CPU gain.