Summary of "Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks"

03 Sep 2015

Summary of "Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks"

Dryad is a "general-purpose, high performance distributed execution engine. It's built under the inspiration of shader languages developed for GPU, Google's MapReduce and parallel databases. It focuses more on simplicity of the programming model and reliability, efficiency and scalability of the applications while side-stepped problems like high-latency and unreliable wide-area networks, control of resources by separate federated or competing entities and ACL, etc. It provides task scheduling, concurrency optimization in a computer level, fault tolerance and data distribution. One of the unique feature provided by Dryad is the flexibility of fine control of an application's data flow graph. This gives programmer the opportunity to optimize trade offs between parallelism and data distribution overhead thus gives "excellent performance" according to the paper.

A Dryad job consists of DAG where each vertex is a program and each edge is a data channel, data channel can be shared memory, TCP pipes, or temp files. In contrast to MapReduce, Dryad doesn't do serialization, for the vertex program's perspective, what they see is a heap object passed from the previous vertex, which will certainly save a lot of data parsing headaches.

A Dryad job is coordinated by a process called job manager, can be either within the compute cluster or remote workstation that has access to the compute cluster. the job manager constructs the DAG and schedules work across available resources. To discover available resources, each computer in the cluster has a proxy daemon running, and they are registered into a central name server, they job manager queries the name server to get available computers.

Dryad used C++ operator overloading and method calls to create a DAG operation DSL. It supports vertex creation, edge creation and graph merging operations. One interesting property provided by Dryad is it can turn a graph G into a vertex V(G), essentially similar to the composite design pattern, it improves the re-usability a lot. Primary API for writing Dryad vertex are C++ based, but it's straightforward to implement API wrappers for other languages such as C#. The runtime receives a closure from the job manager describing the vertex to be run and URIs for input and output of the vertex. It supports event-based programming style on vertex for you to write concurrent program. Which can potentially gives you more efficiency in a vertex execution.

In Dryad, a scheduler inside job manager tracks states of each vertex. If every vertex finishes successfully, the whole job is finished. If any vertex failed, the job is re-run, but only to a threshold number of times, after that if the job is still failing, the entire job will be failed. Dryad also provides visualizer and web interface for monitoring of cluster states. Dryad achieves fault tolerance through proxy communicating with job manager, but if proxy failed, a timeout will be triggered in job manager indicating a vertex has failed. Dryad also provides a backup task mechanism when noticing a vertex has been slower than their peers, similar to the one used to MapReduce.

Dryad's DAG based data parallelization makes it more expressive for solving different large scale problems. The dynamic refinement it provides also makes it efficient in a lot of cases. The performance is absolutely superior to a commercial database system for hand-coded read-only query. One caveat is you can only run 1 job in a cluster at a time, because the job manager assumes exclusive control over all computers within the cluster.