Distributed systems

Introduction

A distributed system is a collection of computers that present themselves to the user as a single, coherent system. The components of the system are spread over multiple computers that communicate over a network. The benefit of distributed systems is that they allow us to achieve levels of reliability and performance that are unobtainable on a single machine. The problem is that it is very difficult to design and run distributed systems correctly. They introduce whole new classes of sometimes very subtle bugs that can make it hard to reason about how the system operates. Leslie Lamport, a computer scientist renowned for his work in distributed computing, wryly describes them thus: “A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.”

By their very nature, distributed systems force us to think about the physical limitations of time and space. Latency is the time it takes for a result to become apparent to an observer. When you click a hyperlink, it takes some time for your request to reach the server. During that period of latency, the request has been initiated but it is not yet visible to the server. Communication, even at the speed of light, can never be completely instantaneous and so some latency is inevitable. We know from the architecture chapter that latency within a single machine needs to be handled carefully but for the most part we can leave it to the computer architects to worry about. In a distributed system, spread over multiple machines possibly at great physical distances from each other, the effects of latency are too obvious to ignore. Much of the challenge of distributed systems comes from understanding and managing the effects of latency. As we’ll see, the more a distributed system tries to behave like a single-node system, the greater the latency cost.

Distributed systems are increasingly common and some familiarity with them is essential for web developers. Simply put, all web work involves distributed systems to some degree. A web application running in the client’s browser and communicating with a back end service forms a distributed system. Front end developers need to understand the problems latency introduces and how to mitigate them. The back end service itself is probably made up of at least an application server and a separate database server. Even that simple design is a distributed system. A production-ready architecture will probably have multiple services, load balancers, caches and who knows what else.

In this chapter we’ll first review why distributed systems are so useful. We’ll see what kinds of problems they can solve and the new challenges they bring. We’ll then build a simple conceptual model of a distributed system and use that to determine the theoretical limitations of distributed computing. We’ll then explore a few distributed system architectures via a discussion of consistent replication. Maintaining a consistent view of state across the whole system is essential for many use cases and so understanding the challenges of consistent replication is a good entry point to thinking about distributed systems.

Why we need distributed systems

Why do we now find ourselves surrounded by distributed systems? In large part it’s because we users have become so demanding. We used to be content with a PC sat in the corner by itself. Then we got the Internet and wanted to be able to talk to other computers. Fast forward a few more years and now we have multiple, mobile computing devices and we expect all of them to remain in sync all of the time. What we want to do online has become more demanding too. Back in the 1990s, web services could get away with having regularly scheduled downtime to perform updates. An unexpected outage would be irritating but not critical for many businesses. In our modern, globalised world, we expect online services to be always available at any time. We want to be able to search the entire Internet in seconds and download any content rapidly whenever we feel like it. The sheer scale of modern demands makes distributed systems essential. Below are the three reasons distributed systems help.

1. More machines can handle more

Tasks are easier when they can be handled by one machine. Sorting an input is a relatively straightforward job when the input fits in memory. Running a web server is easier if a single machine can handle all of the requests. When the problem becomes too big for a single machine, we need to change our approach.

Scalability is the ability of a system to cope with increased demand. We’ll take “demand” to have a fairly loose meaning of “the work to be done”. That might refer to a single, large job, such as indexing the web, but it could also mean a large number of small jobs such as requests to a web server. The first solution is to scale up: get bigger and better hardware so that one machine can handle more. This works very well but only up to a certain point. If you’re trying to index the entire web then no amount of scaling up will do. No single machine, no matter how beefy, can handle the task. The second solution is to scale out: add more machines to the system. Now you have multiple machines coordinating to solve a problem. Congratulations – you have a distributed system!

Distributed systems can handle huge workloads by dividing them into smaller tasks and spreading those tasks across multiple machines known as nodes. They can cope with increased demand by scaling out. This makes them more flexible and probably more cost effective. For example, online retailers predictably experience huge spikes in demand at certain points in the year. The spikes require a high server capacity to handle the load. It would be wasteful to provision the same capacity throughout the rest of the year when demand is predictably much lower. This is the problem with scaling up. A server powerful enough to handle the huge, albeit brief, spikes would spend most of its time working at a small fraction of its full capacity. That’s a waste of resources. If the retailer chose to scale out instead, they could provision only the capacity they needed and easily add extra machines when required.

2. More machines improve performance

We know from the concurrency chapter that some problems are parallelisable: they can be solved more quickly by having multiple machines solve parts of the problem in parallel. So for tasks that are easily parallelisable, some form of distributed system will deliver a performance boost.

A different performance benefit comes from globally distributed systems. Remember that communication is never instantaneous and transmission delay has a lower bound determined by the distance between the two nodes. By hosting the same data in multiple data centres dispersed around the globe, a system can serve the user’s requests from the physically nearest data centre. Shorter distances result in lower latency and faster response times. Big content providers such as Netflix do this to make their services appear faster and more responsive. Having the same data in multiple locations introduces the challenge of maintaining consistency across all of those data sources.

3. More machines increase resilience and fault tolerance

Global web services don’t have the luxury of regular maintenance downtime. They are in constant use. For many online businesses, a brief outage could cost millions in lost revenue. Even non-tech companies would be hobbled if their internal systems became unavailable.

We want our systems to be available for use and functioning correctly as much as possible. A fault is when one component of the system (e.g. a node’s hard drive) stops working correctly. Faults are sadly inevitable. Software contains bugs and hardware eventually breaks. What we can control is how we respond to faults. Resilience means that the system can recover from faults. The user may observe some sign of failure but the rest of the system continues to work. Resilience itself doesn’t require a distributed system. A simple example is a web application running on a single server. It might return an error response to one request but continue accepting and correctly processing other requests.

Distributed systems enter the scene when we aim for high availability. It’s an imprecisely defined term but simply means that the service tries to have very little downtime (i.e. periods of unavailability). Normally this involves having redundant components arranged in a distributed system so that there is no single point of failure. Fault tolerance is an even more stringent requirement. It means that the system can continue correct operation even if some components fail. The user doesn’t see any sign of failure, apart from maybe some increased latency. This obviously requires some form of distributed system, since a single node cannot provide fault tolerance.

The problem for designers of distributed system is that more hardware means more complexity and more places for things to go wrong. Most hardware failures are relatively unlikely for any given machine, but when you are running thousands of machines they become almost inevitable. Stats from Google indicated that a new Google cluster might experience thousands of individual machine failures in a single year. Worse, entirely new classes of errors arise due to the interactions of so many components. Faults can cascade across the system in unexpected ways. We cannot achieve fault tolerance simply by throwing more hardware at the problem. True fault tolerance is difficult to achieve and requires a lot of careful planning.

A theoretical model

In this section we will define a basic, theoretical model of a distributed system. We’ll use it to explore the distinguishing characteristics and limitations of distributed systems in general. This is analogous to how we used automata to analyse computation way back in the theory of computation chapter. Our model takes the form of a set of assumptions about the system’s environment and components. The assumptions are deliberately very simple to make analysis easier.

We assume that a single program is executing concurrently on multiple, independent nodes. Each node has its own local, volatile memory and persistent storage. It also has its own internal clock. The program running on each node allows the user to read and modify a single, system-wide variable. This is known as a “register” after a processor register. “Independent” here means that each node can fail and reboot without affecting the others.