Building Distributed Graph-Processing Systems

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

- Leslie Lamport

The master/worker pattern is a popular approach for building fault-tolerant, distributed systems. The first part of this chapter explores this pattern in depth with a focus on some of the more challenging aspects of distributed systems, such as node discovery and error handling.

In the second part of this chapter, we will apply the master/worker pattern to build, from scratch, a distributed graph-processing system that can handle massive graphs whose size exceeds the memory capacity of most modern compute nodes. Finally, in the last part of this chapter, we will apply everything learned so far to create a distributed version of the PageRank calculator service for the Links...

Technical requirements

The full code for all topics discussed within this chapter has been published to this book's GitHub repository in the Chapter12 folder.

You can access the GitHub repository that contains the code and all required resources for each one of this book's chapters by pointing your web browser at the following URL: https://github.com/PacktPublishing/Hands-On-Software-Engineering-with-Golang.

Each example project for this chapter includes a common Makefile that defines the following set of targets:

Makefile target	Description
deps	Install any required dependencies.
test	Run all tests and report coverage.
lint	Check for lint errors.

As with all other chapters from this book, you will need a fairly recent version of Go, which you can download at https://golang.org/dl/.

To run some of the code in this chapter, you will need to have a working...

Introducing the master/worker model

The master/worker model is a commonly used pattern for building distributed systems that have been around for practically forever. When building a cluster using this model, nodes can be classified into two distinct groups, namely, masters and workers.

The key responsibility of worker nodes is to perform compute-intensive tasks such as the following:

• Video transcoding
• Training large-scale neural networks with millions of parameters
• Calculating Online Analytical Processing (OLAP) queries
• Running a Continuous Integration (CI) pipeline
• Executing map-reduce operations on massive datasets

On the other hand, master nodes are typically assigned the role of the coordinator. To this end, they are responsible for the following:

• Discovering and keeping track of available worker nodes
• Breaking down jobs into smaller tasks and distributing them to each...

Out-of-core distributed graph processing

Back in Chapter 8, Graph-Based Data Processing, we designed and built our very own system for implementing graph-based algorithms based on the Bulk Synchronous Parallel (BSP) model. Admittedly, our final implementation was heavily influenced by the ideas from the Google paper describing Pregel ^[4], a system that was originally built by Google engineers to tackle graph-based computation at scale.

While the bspgraph package from Chapter 8, Graph-Based Data Processing, can automatically distribute the graph computation load among a pool of workers, it is still limited to running on a single compute node. As our Links 'R' Us crawler augments our link index with more and more links, we will eventually reach a point where the PageRank computation will simply take too long. Updating the PageRank scores for the entire graphs might take...

Deploying a distributed version of the Links 'R' Us PageRank calculator

The PageRank calculator is the only component of the Links 'R' Us project that we haven't yet been able to horizontally scale on Kubernetes. Back in Chapter 8, Graph-Based Data Processing, where we used the bspgraph package to implement the PageRank algorithm, I promised you that a few chapters down the road, we would take the PageRank calculator code, and without any code modifications, enable it to run in distributed mode.

After completing this chapter, I strongly recommend, as a fun learning exercise, taking a look at using the dbspgraph package to build a distributed version of either the graph coloring or the shortest path algorithms from Chapter 8, Graph-Based Data Processing.

In this section, we will leverage all of the work we have done so far in this chapter to achieve this...

Summary

In this rather long chapter, we performed a deep dive into all of the aspects involved in the creation of a distributed graph-processing system that allows us to take any graph-based algorithm created with the bspgraph package from Chapter 8, Graph-Based Data Processing, and automatically distribute it to a cluster of worker nodes.

What's more, as a practical application of what we learned in this chapter, we modified the Links 'R' Us PageRank calculator service from the previous chapter so that it can now run in distributed mode. By doing so, we achieved the primary goal for this book—to build and deploy a complex Go project where every component can be independently scaled horizontally.

The next and final chapter focuses on the reliability aspects of the system we just built. We will be exploring approaches for collecting, aggregating, and visualizing...

Questions

1. Describe the differences between a leader-follower and a multi-master cluster configuration.
2. Explain how the checkpoint strategy can be used to recover from errors.
3. What is the purpose of the distributed barrier in the out-of-core graph processing system that we built in this chapter?
4. Assume that we are provided with a graph-based algorithm that we want to run in a distributed fashion. Would you consider a computation job as completed once the algorithm terminates?

Further reading

1. Consul: Secure service networking. https://consul.io
2. Docker: Enterprise container platform. https://www.docker.com
3. Lamport, Leslie: Paxos Made Simple. In ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001), S. 51–58
4. Malewicz, Grzegorz; Austern, Matthew H.; Bik, Aart J. C; Dehnert, James C.; Horn, Ilan; Leiser, Naty; Czajkowski, Grzegorz: Pregel: A System for Large-scale Graph Processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD '10. New York, NY, USA : ACM, 2010 — ISBN 978-1-4503-0032-2, S. 135–146
5. Ongaro, Diego; Ousterhout, John: In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC'14. Berkeley, CA, USA : USENIX Association, 2014 — ISBN...