tldr: Naiad

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

Naiad: A Timely Dataflow System [2013]

Murray et. al

Introduction


Naiad is a distributed system for big data computation. It's motivated by computing on real-time streaming, incremental data. (In contrast, Spark handles iterative data that's reused but unchanged, so Spark would have to start over if new data is added.) Naiad's goal is to get high performance through parallelism. 

Timely Dataflow

Naiad is based on a new computing model that the authors call timely dataflow. It's a directed graph with stateful vertices that send and receive messages along the edges. Furthermore, there are input vertices which receive a sequence of messages from an external producer, and output vertices, which send a sequence of messages to an external consumer. Finally, there may be nested cycles, called loop contexts. The figure below shows an example of a simple dataflow graph:
The external producer that sends messages to the input vertex labels each message with an epoch. Specifically, each message looks like:
The epoch defines which interval of time the message belongs to, and the k loop counters keep track of the k loop contexts an edge is in. There are three kinds of vertices in a loop context:
  • Ingress vertex. In the figure above, vertex "I". Push a loop counter c into the array of loop counters.
  • Feedback vertex. In the figure above, vertex "F". Sets c to c+1 in the corresponding loop counter.
  • Egress vertex. In the figure above, vertex "E". Pops a loop counter c from the array of loop counters.

Vertex Programming Model

The API for handling vertices is: 
  • this.NotifyAt(t: Timestamp) 
    • Notify the app when at a specific timestamp 
    • Calling this results in a corresponding invocation of v.OnNotify(t)
  • this.SendBy(e: Edge, m: Message, t: Timestamp)
    • Send a message at a current or future timestamp 
    • Calling this results in a corresponding invocation of v.OnRecv(e, m, t)
  • Callback: v.OnNotify(t: Timestamp)
    • There are no more messages with timestamp <= t that will be sent to this vertex
  • Callback: v.OnRecv(e: Edge, m: Message, t: Timestamp)
    • Vertex is notified of message 
Although this low-level programming is complicated, most developers don't work with timely dataflows and timestamps. 

Conclusion

Naiad has impressive performance on PageRank, and performs well on applications with iterative batching, graph processing, and iterative ML. 

    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