tldr: Bayou

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

Bayou, a Weakly Connected Replicated Storage System [1995]

Terry et. al

Introduction

Bayou is motivated by providing a storage system for applications that are:
  • Collaborative (conflicting, concurrent activity)
  • Weakly connected (mobile computers with poor network connectivity)
  • Non real-time 
For example, it can support shared calendars. 

In fact, Bayou only requires occasional, pairwise communication between computers. Furthermore, it follows a weakly consistent, replicated data model. Finally, it implements domain-specific, automatic conflict resolution. This allows the system to remain available. 

System Overview 

Applications (represented in the above figure as clients) interact with servers through the Bayou API. Although clients interact with a single server at a time, they can switch between interacting with different servers. Each server has a storage system that consists of an ordered log of writes and resulting data from executing those writes.

The API consists of two operations:
  • Read
    • Data queries
    • Client reads data from server 
  • Write
    • Insert, modify, and delete data
    • Client writes to a server, without waiting for write to be accepted by other servers. 
    • Each write contains the desired updates, information to help server handle any possible conflicts, and a globally unique WriteID that's assigned by the server that first accepted the write.
    • Servers syncs writes pairwise in what the authors call "anti-entropy sessions". Once each pair of servers finish syncing, they have agreed on the which writes are seen and their order. 

Conflict Detection and Resolution

Bayou has two mechanisms to handle conflicts:
  • Dependency checks
    • Responsible for application-specific conflict detection 
    • Before a write operation executes, it calls a dependency check with two parameters: an application-supplied query, and its expected result. 
    • The check reports a conflict if the query doesn't return the expected result. Then, the update is not executed. Instead, the write resolves the conflict.  
  • Merge procedures 
    • Responsible for conflict resolution 
    • Written by application programmers 

Consistency 

Bayou is eventually consistent due to two properties:
  • Writes are executed in the same order on all servers.
  • Conflict detection and resolution is deterministic, so servers resolve same conflicts the same way.
When writes are accepted by a server, they are marked tentative and ordered by timestamp. The timestamps are monotonically increasing at each server. Servers don't need synchronized clocks, but fairly close clocks are preferred. 

Eventually, writes are marked committed and ordered by the time they were committed, and before all tentative writes. A tentative write is committed on a server if it's been executed for the last time by that server. This happens when the set of preceding writes are fixed. Bayou uses a primary commit scheme procedure, where one primary server is in charge of committing. Other servers get the propagated commit. 

Storage System Implementation 

As shown in the above figure, the storage system can be divided into three components:
  • Write Log
    • Contains writes received a server, sorted by global committed/tentative order. 
    • Specifically, contains a tail of committed entries, and all tentative entries.
    • Each server maintains a timestamp vector to keep track of the timestamps of the latest write each server has discarded. 
  • Tuple Store
    • Database of values from executing writes in order.
    • Responsible for processing read requests.
  • Undo Log
    • Rolls back tentative writes that were applied to the tuple store, so they can be re-executed in some other order. 

Conclusion

Bayou tries to handle scenarios where computers communicate through a weak network. It shows that we need ordering even when implementing weak consistency. Finally, Bayou shows us that conflict resolution is more efficient when it's application-specific. 

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