Twitter: Redis with 105 TB of RAM

01 · CONTEXT

A cache for the most important service

This case starts from a summary, published on the High Scalability blog, of a talk about Redis at Twitter given by Yao Yue, from the company's cache team. The summary's title announces the totals: 105 TB of RAM, 39 million queries per second, and more than 10,000 instances.

At Twitter, Redis backed the Timeline, described as the company's most important service. A timeline is an index of tweets by identifier; chaining tweets into a list yields the Home Timeline, and the User Timeline, with the tweets the person themselves posted, is just another list. Redis was first used at Twitter in 2010, for the Timeline service, and is also used in the ads service.

1. When a tweet is generated, it needs to be written to all the relevant timelines; each write is a small item appended to a large list in the cache.

2. On read, the app asks for only a small batch of tweets; as the screen scrolls, another batch is loaded.

3. Because the timeline can be large and performance matters, reads should avoid the database and be served by the cache.

4. The cache is look-aside: if the key is missing, the requester fetches from storage and puts it back in the cache; the cache does not repopulate itself.

02 · WHY REDIS

Why Redis and not Memcache

According to the summary, the question was why consider Redis instead of Memcache, and two reasons answer it: the network bandwidth problem and the long common prefix problem.

Memcache worked worse than Redis for the timeline, and the problem was fanout. Twitter's reads and writes happen incrementally and are small, but the timelines themselves are large. A read-modify-write cycle, for incremental writes and small reads on large objects like the timeline, is too expensive and creates a network bottleneck. According to the speaker, on a gigalink with more than 100 thousand reads and writes per second, the network becomes the bottleneck when the average object exceeds 1K.

The second problem is long, repeated prefixes. With a flexible schema, each attribute can become its own key, which requires one request per attribute, and not all attributes can be in the cache. With metrics over time, the same name repeats at every sample, which changes only the timestamp. To save space in both cases, a hierarchical key space is desirable.

There is also a resource argument: a dedicated cache cluster underutilizes the CPUs, and Redis sees what the server could do and does not do it.

03 · CUSTOM STRUCTURES

Hybrid List and BTree

Twitter forked Redis 2.4 and added features, and so got stuck on that version. The changes included two data structure features, its own cluster management, and its own logging. Redis's disk features are not used.

The timeline is a list of tweet IDs, that is, small integers. Redis offers two kinds of list: the ziplist, space-efficient, and the linked list, flexible but with two pointers per item, a very high overhead for IDs this small. To use memory well, Twitter used exclusively ziplists.

Using only ziplists has costs. The ziplist limit becomes the maximum size of a timeline, so a product decision, how many tweets fit in a timeline, is tied to a low-level component. Inserting and removing in a very large ziplist is inefficient. Moreover, timelines vary widely in size and, when the cache runs out of memory, many small timelines may be evicted until there is enough contiguous memory for a large ziplist. Since writes are spread across many timelines, the chance of hitting a write latency trap increases, and it becomes hard to define an SLA for writes.

The Hybrid List is a linked list of ziplists, added to Redis for more predictable memory performance. Each ziplist has a size limit in bytes and, when the list exceeds it, the overflow goes to the next ziplist. Before it, a workaround was to expire large timelines earlier, which freed memory for the others but was expensive when the person went to view their own timeline.

The BTree was added for range queries on hierarchical keys, returning a list of results. In Redis, secondary fields live in a hash, which uses linear search and performs poorly with many fields; the sorted set, in turn, sorts by a double-type score, so an arbitrary name or secondary key does not work as a criterion. The BTree reuses a BSD implementation and allows lookup by key and by range.

The summary gives the numbers for one data center for each of the two structures.

04 · CLUSTER AND PROXIES

Who routes the keys

A cluster uses more than one Redis instance for the same purpose. When the data or throughput exceeds what one instance can handle, the key space must be particionado into shards, and routing is taking a key and finding which shard holds the data.

In the speaker's opinion, cluster management is the main reason Redis adoption did not explode. Part of the problem is that many Redis operations are not idempotentes: after a network failure the call must be repeated, and the data can be corrupted, and corrupted data is hard to detect. In Memcache, many clusters use client-side consistent hashing and accept inconsistent data.

Twitter saw three options: the servers agree among themselves on what the cluster looks like, use a proxy, or let the client manage the cluster, with the clients forming a quorum.

The weight of the client shows in the numbers: about 100 projects at Twitter use a cache cluster, and changing anything in the client would require propagating the change to all of them, which could take years.

Of the two reasons, one is to separate the fast path, the data path, from the slow path, the command-and-control path. The other is that, with cluster management inside the server, any fix or update to that code would require restarting Redis, which has state, and that can discard a lot of data.

1. The client service sends the command to a proxy and doesn't care which one handles it.

2. The proxy does the routing: it takes the key, finds the shard that holds the data, and forwards the command.

3. There is no sharding at the proxy level and all proxies are stateless; to scale throughput, just add proxies.

4. Cluster management stays off the data path: the leader maintains the cluster view and, if a node goes down, moves the shard to another node.

5. If cluster management lived inside the server, fixing or updating that code would require restarting Redis, which is stateful and could lose data.

6. If the key is missing from the cache, the client itself fetches it from storage and puts it back in the cache.

There was a worry that the proxy would add one more network hop between client and server, but profiling showed that this extra hop is a myth, at least in their environment. Latency through the Redis server was under 0.5 millisecond, while the path through Finagle was close to 10 milliseconds. The problem, they conclude, is inside the JVM.

The proxy has a cost: resources allocated just to forward traffic. There is also no reason to close connections, and some instances run fine with 100 thousand open connections, with better latency when they stay open. The summary also says the proxy layer is moving back to C and C++.

The clusters work as a look-aside cache: the cache does not refill the data, and the client is the one that fetches the missing key from storage and puts it in the cache. If a node goes down, the shard is moved to another node, and the failed machine is wiped when it comes back, so no stale data remains. The cluster leader does all of this, and a central view helps keep the cluster easy to understand.

05 · VISIBILITY

Proving what the cache is doing

When someone complains that the cache is misbehaving, most of the time the cache is fine: clients are misconfigured, ask for too many keys, or ask for the same key over and over, saturating the server or the link. Whoever is accused of abusing the system wants proof, and a service-oriented architecture does not, by itself, give problem isolation or easier debugging.

That is why Twitter built visibility into the cache itself. Logging every command is possible, and only metadata is kept, not the values. Shipping all of that log off the machine would be too much data and economically unviable, so the log is summarized on the machine itself and only the summary travels.

1. The cache instance logs metadata for each command, but not the values.

2. A process on the machine itself reads the log and produces a summary, sent periodically and much smaller than the original log.

3. Storm aggregates the summaries from the machines.

4. The views are stored and displayed, showing for example the most-used keys and traffic per second.

With this you can see the most-used keys, traffic per second, which shows whether the pattern is bursty, and the number of unique keys, useful for capacity planning. Frequent packet loss can be tied to a hot key or bursty traffic. Hot keys are a problem, and Twitter was building a tiered cache solution, with a client-side cache that automatically holds those keys.

06 · LESSONS

What the speaker takes away from it

Scale demands predictability: the bigger the cluster and the number of clients, the more predictable and deterministic you want the service to be. Tail latencies matter: in a query that fans out across many shards, a single slow shard is enough to make the whole query slow.

In a container environment, Redis causes external fragmentation, that is, it uses more memory to store the same amount of data, and compensating for that with overallocation creates large potential for waste. According to the summary, very-low-latency services do not fit well with Mesos and are therefore isolated from other workloads.

Another lesson is to bring computation to the data, such as summarizing logs on the machine itself. As for Lua scripts inside Redis, the speaker considers them unsuitable for production: a loaded script can do anything and, as a result, whoever operates the service cannot guarantee the SLA. She prefers a deployment model, which would allow code review and benchmarking.

The Redis wish list includes explicit memory management, deployable scripts, and multithreading, which would make cluster management easier by reducing the number of instances per machine.