tldr: FaRM

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

Optimistic Concurrency Control + FaRM [2015]

Dragojević et al. 

Introduction

Before FaRM, distributed transactions were thought of as convenient for programmers, but slow. However, FaRM guarantees 90-100 million transactions/second on 90 machines! Those transactions are replicated 3 times (by default) and persistent. What is FaRM and how did it accomplish this? 

Systems often have to make tradeoffs between availability, consistency, performance, and simplicity. However, FaRM is a main memory platform for data centers that doesn't compromise on any of these because it minimizes network, storage, and CPU bottlenecks by:
  • Assuming the whole dataset can fit in RAM, so no disk I/O
  • Using non-volatile RAM, so no disk I/O
  • Using a one-sided RDMA for a fast network
  • Bypassing the OS kernel for fast network access
  • Designing transaction and replication protocols optimized for one-sided RDMA 

Programming model

An application using FaRM sees an abstraction of a global address space, divided into 2GB regions. Each region is replicated on a primary and some number of backups. Each server in a FaRM cluster stores several regions in non-volatile DRAM.

The figure below shows a cluster with 4 servers. Each server stores one incoming message queue for each of the other servers. Another server can send messages to its corresponding queue stored in the receiver through RDMA. The receiving server periodically polls. 
FaRM uses ZooKeeper to ensure machines agree on and store the configuration of the cluster. However, it does not use ZooKeeper for failure detection, recovery, or lease management. Instead,  FaRM uses RDMA for fast recovery.  

To execute a transaction, FaRM uses one-sided RDMA to read objects, and locally buffer writes. The coordinator keeps track of the addresses and version of all objects that were accessed. (Each object has a corresponding 64-bit version.) After executing the transaction, FaRM tries to commit, as shown in the below figure: 

Let's go through the steps of commit in more detail:
  • Lock. The coordinator writes LOCK to the log of each server that's the primary for an accessed written object. (In the diagram, that means servers P1 and P2.) 
    • The LOCK record consists of the transaction ID, IDs of regions with objects written by the transaction, and addresses, versions, and values of those objects. 
    • Upon receiving LOCK, primaries attempt to lock the objects at the versions, and reply if it was successful. (It can fail if the object's version changed since the transaction read it, or if another transaction locked it.)
    • If the locking attempt failed, the coordinator aborts the transaction.
  • Validate. The coordinator reads the versions of objects that were read but not written by the transaction from their corresponding primaries. (In the diagram, that means server P3.) 
    • Validation fails if any object has changed. The coordinator then aborts the transaction. 
    • Validation uses one-sided RDMA by default. 
  • Commit backups. The coordinator writes COMMIT-BACKUP to the non-volatile logs of each backup. (In the diagram, this means servers B1 and B2.) 
    • The COMMIT-BACKUP consists of the same data as a LOCK (which is described above.) 
    • The backups send back an ACK. 
  • Commit primaries. After the coordinator receives all ACKs, it writes a COMMIT-PRIMARY to the logs of each primary. (In the diagram, this means servers P1 and P2.) 
    • The COMMIT-PRIMARY contains the transaction ID to commit. 
    • Upon receiving COMMIT-PRIMARY, the primaries update the objects in place, increment their versions, and unlock them. 
    • As soon as one primary sends back an ACK, the coordinator reports to the application that the transaction was completed. 
  • Truncate. The coordinator can truncate logs in primaries and backups after receiving ACKs from all primaries. 
FaRM transactions use optimistic concurrency control. This means transactions can access a data object without acquiring a lock. Before it commits, the transaction must verify that no other transaction has modified the data object. If so, the commit is valid. Otherwise, it aborts and retries. 

Furthermore, FaRM guarantees strict serializability of successfully committed transactions. Reads of an object get the value of the most recent committed write. Reads across different objects are not necessarily atomic, but individual reads are. 

Handling Failures

Recovery from failure happens in 5 phases:
  • Failure detection. FaRM uses leases to determine whether a machine failed. Leases are extremely short, which help ensure the system's availability. 
  • Reconfiguration. This protocol moves a FaRM instance to a new configuration, and uses one-sided RDMA to get good performance.
  • Transaction State Recovery. FaRM uses logs distributed across the servers to recover transaction state. It does this quickly by giving work to threads and machines in parallel. 
  • Recovering data. FaRM recovers data at backups for each region. 
  • Recovering allocator state. The allocator splits regions into 1 MB blocks to allocate small objects. 
Overall, recovery is fast, and FaRM can bounce back from failure to peak throughput in less than 50 ms. 

Conclusion

FaRM shows that distributed transactions can be fast without sacrificing consistency and availability. It uses optimistic concurrency control, which is faster than locking provided that there aren't too many conflicts between transactions. 

Popular posts from this blog

Building A Toy Language Interpreter in Go

-
Image
In this post, I'll be giving a high-level overview of interpreters, why they're interesting, and how they work. I'll be referencing my repo, go_interpreter , which is a simple interpreter written in Go for a toy language. The figure below shows the structure of our interpreter with an example input: What is an interpreter?  An interpreter is a language processor that seems to directly execute the source program on user input: In contrast, a compiler first takes in a source program and translates it to an executable machine code target program. Then, the user can pass in inputs to this target program and get outputs. In general, an interpreter is better at reporting errors since it's processing statements one at a time, and a compiler is faster at generating outputs from inputs. In this post, we're going to go over a simple interpreter that is capable of supporting: integers, booleans, strings, arrays, hashmaps prefix, infix operators index opera
Read more

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