Why Twitter's write-heavy systems pose new challenges

This research paper from Carnegie Mellon in 2020, is an eye opener 👁️

It uses production log traces from Twitter to evaluate different caching strategies. The results are astounding.

Key Takeaways

1. Fitting more objects in a cache is more impactful than the choice of eviction policy

• That means data compression and reducing cache metadata is more important than the choice made between LRU and FIFO algorithms.
• The more objects you can stuff in a cache, the more performant it is.

2. Object sizes change over time

• This significantly impacts cache performance, since memory either fragments or calcifies (new objects can't be added because other size slabs have taken up space).

• There are no efficient proven algorithms to deal with this problem!

• Have a look at Gaurav Sen's Garbage Collection videos for more details about memory management.

  • a. Mark Sweep, Generation Hypothesis and JIT code injection
  • b. Concurrent Mark Sweep, Fragmentation and Compaction, Lost Writes
  • c. Concurrent Updates with Optimistic Locking

3. Object TTL (TIME TO LIVE) can be more important than cache eviction policy

• Despite its importance, there are no good proven algorithms for evicting expired objects.

• A full scan is inefficient, and algorithms like the timer wheel (explained at InterviewReady) don't work on all objects.

• Again, we notice that some principles of Java's garbage collection can be applied here (especially the generational hypothesis). Do check out the videos mentioned above.

4. Not all workloads are read-heavy

• Facebook has very read-heavy workloads, and Memcached is accordingly optimized for reads.

• Twemcache has some write-heavy workloads too (about 35-40% of the queries result in write operations).

• The result is a break of many expectations, like behavior changes in the TTL of objects and the number of times these objects are accessed.

• Understandably, with these expectations breaking, the cache performance of write-heavy clusters isn't great.

---

Overall, this paper is a must-read. It breaks commonly held assumptions about caches.

We often expect caching algorithms to do well looking at their time complexity. But in reality, practical considerations supersede optimizations.

Resources

1. Read the paper: A large-scale analysis of hundreds of in-memory cache clusters at Twitter.
2. Check out our list of whitepapers worth reading.
3. Our recorded whitepaper readings are available in the system design course.

Cheers!

P.S. Twitter calls its version of Memcache, "Twemcache". Just found it funny :p