tldr: Memcached

-
Part of the tldr series, which summarizes papers I'm currently reading. Inspired by the morning paper.

Scaling Memcache at Facebook [2013]

Nishtala et al.

Introduction 

Although this paper does not introduce new ideas, it describes memcache, a real-world, large-scale, successful system deployed at Facebook.

Specifically, Facebook uses memcache in two ways: 
  • Query cache to lighten read load on databases. See the figure above.
  • Generic cache. For example, engineers can store pre-computed results from ML algorithms in memcached. 
The system's workload was dominated by fetching data, which steered its designers towards caching. Additionally, the reads were from a range of sources (like MySQL databases, HDFS installations, and backend services), so it had to have a flexible caching strategy. 

Memcached

The authors describe how Facebook used memcached, an in-memory key-value store running on a single server, to build a distributed key-value store. (Different from memcache, which is how they refer to their distributed system.) Memcached was a natural choice as a building block because it has a simple set of operation: set, get, and delete.  

Evolution 


The final design is shown in the figure above. Facebook evolved memcache in several stages, which we explain in the next few subsections.

Scaling within a cluster

At this point, Facebook was mostly focused on the following two goals:
  • Reducing latency of fetching cached data. 
    • One user web request can involve hundreds of memcache get requests. 
    • All-to-all communication between web servers and memcached servers. Items are distributed across memcached servers using consistent hashing. 
    • Parallel requests and batching. Web server uses directed acyclic graph of data dependencies to maximum number of items that can be fetched in parallel.
    • Client-server communication. Memcached servers don't communicate with each other. Thus, a memcache client on each server handles serialization, compression, request routing, etc. 
  • Reducing load imposed due to a cache miss.
    • Leases
      • Handles the issues of stale sets, which is when a web server sets a stale value in memcache. A memcached server hands a lease to a client. The lease is a 64-bit token bound to a key the client requested. The client provides the lease when setting a value in the cache. Memcached can use the lease to verify whether the data should be stored. Thus, stale sets are prevented.
      • Handles the issues of thundering herds, which is when a certain key is heavily bombarded by reads and writes. If a key's value is requested within 10 seconds of a lease being issued, the client has to wait. Then, when waiting clients retry, whichever client had the lease will have probably set the value successfully. 
      • Stale values. Sometimes, returning a slightly stale value is acceptable.
    • Pools. Since different applications result in different workloads, a cluster's memcached servers are partitioned into separate pools. 
    • Replication within pools. A category of keys within a pool is replicated if the application frequently fetches many keys simultaneously, the entire dataset fits in 1-2 memcached servers, or the request rate is higher than what one server can handle.
Facebook also used an automated recovery system to handle failures. Since there can be excessive load to backend services while the recovery procedure is running, more and more failures can appear and snowball. Thus, Facebook uses Gutter, a group of about 1% of memcached servers, to take over failed servers' responsibilities. 

Clusters within a region 

Web servers and memcached servers are split into multiple frontend clusters. Together, a frontend cluster and its corresponding storage cluster that contains the databases form a region. 

To reduce the number of replicas, multiple frontend clusters share the same set of memcached servers. This is called a regional pool. 

Conclusion

Some lessons we can learn from memcached are:

  • Caching is important for throughput, not just latency.
  • Consistency is tricky to get right.





Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each instance of a type that impleme
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients send commands to
Read more