{"id":22581,"date":"2022-03-03T21:56:33","date_gmt":"2022-03-03T20:56:33","guid":{"rendered":"https:\/\/blog.mi.hdm-stuttgart.de\/?p=22581"},"modified":"2023-08-06T21:39:32","modified_gmt":"2023-08-06T19:39:32","slug":"cascading-failures-in-large-scale-distributed-systems","status":"publish","type":"post","link":"https:\/\/blog.mi.hdm-stuttgart.de\/index.php\/2022\/03\/03\/cascading-failures-in-large-scale-distributed-systems\/","title":{"rendered":"Cascading failures in large-scale distributed systems"},"content":{"rendered":"\n

Internet service providers face the challenge of growing rapidly while managing increasing system distribution. Although the reliable operation of services is of great importance to companies such as Google<\/em>, Amazon<\/em> and Co., their systems fail time and again, resulting in extensive outages and a poor customer experience. This has already affected Gmail<\/em> (2012) [1], AWS DynamoDB<\/em> (2015) [2], and recently Facebook<\/em> (2021) [3], to name just a few examples. In this context, one often encounters so-called cascading<\/em> failures <\/em>causing undesirable complications that go beyond ordinary system malfunctions.<\/em> But how is it that even the big players in the online business cannot completely avoid such breakdowns, given their budgets and technical knowledge? And what are practical approaches to risk mitigation that you can use for your own system?<\/p>\n\n\n\n

With that said, the goal of this blog article is to learn how to increase the resilience of your large distributed system by preventing the propagation of failures.<\/p>\n\n\n\n\n\n\n\n

Cascading failures<\/h2>\n\n\n\n

A cascading failure<\/em> is a failure that increases in size over time due to a positive feedback loop<\/strong>. The typical behavior is initially triggered by a single node or subsystem failing. This spreads the load across fewer nodes of the remaining system, which in turn increases the likelihood of further system failures resulting in a vicious circle or snowball effect [4]. Cascading failures are highly<\/strong> critical<\/strong> for three reasons: First, they can shut down an entire service in a short period of time. Second, the affected system does not return to normal as it does with more commonly encountered problems, but it gets progressively worse. This ultimately leads to being dependent on human intervention. Finally, in the worst case, cascading failures can strike seemingly without warning because load distribution, and consequently failures, occur rapidly [4][5].<\/p>\n\n\n\n

Although this blog article will focus on cascading failures in the context of distributed computing, they can also occur in a variety of other domains: e.g., power transmission, finance, biology, and also ecosystems. So, they are a fairly widespread phenomenon that is somewhat similar to patterns found in nature [5]. To get a better idea of what a cascading failure in computer science looks like, let’s look at a specific case study.<\/p>\n\n\n\n

Case Study: The AWS<\/em> DynamoDB<\/em> Outage in 2015<\/h2>\n\n\n\n

AWS DynamoDB<\/em> is a highly scalable non-relational database service, distributed across multiple datacenters that offers strongly consistent read operations and ACID transactions [6]. It is, and at the time of the event was, being used by popular internet services such as Netflix<\/em>, Airbnb<\/em>, and IMDb<\/em> [7]. The incident we want to look at as an example of a cascading failure occurred on September 20, 2015, when DynamoDB<\/em> was unavailable in the US-East region for over four hours. There were two subsystems involved: storage servers and a metadata service. Both are replicated across multiple datacenters. The storage servers request their so-called membership<\/em> for their data partition allocations from the metadata service. This is shown in Figure 1.<\/p>\n\n\n\n

\"\"<\/a>
Figure 1: Storage servers and metadata service
(Own illustration based on [8])<\/figcaption><\/figure>\n\n\n\n

For the membership (and thus also for the allocation of data partitions) there are timeouts during which the request must be successful. If these are exceeded, the corresponding storage server retries and excludes itself from the service.<\/p>\n\n\n\n

An unfortunate precondition for the incident was a newly introduced DynamoDB<\/em> feature called Global Secondary Index<\/em> (GSI). This gives customers better access to their data but has the downside of significantly increasing the size of metadata tables. Consequently, the processing time was much longer. Regarding the capacity of the metadata service and the timeouts for membership requests, unfortunately no corresponding adjustments were made [9].<\/p>\n\n\n\n

The real problem began when a short network issue caused a few storage servers (dealing with very large metadata tables) to miss their membership requests. These servers became unavailable and kept retrying their requests. This overloaded the metadata service, which in turn slowed down responses and caused more servers to resubmit their membership requests because they had exceeded their timeouts as well. As a consequence, the state of the metadata service deteriorated even further. Despite several attempts to increase resources, the system remained caught in the failure loop for hours. Ultimately, the problem could only be solved by interrupting requests to the metadata service, i.e., the service was basically taken offline [9].<\/p>\n\n\n\n

The result is a widespread DynamoDB<\/em> outage in the US-East region and an excellent example of a cascading failure. However, what are the underlying concepts and patterns of the systems that are getting caught in such an error loop?<\/p>\n\n\n\n

Reasons for cascading failures<\/h2>\n\n\n\n

First, it should be mentioned that the trigger points for cascading breakdowns can look diverse: e.g., these could be new rollouts, maintenance, traffic drains, cron jobs, distributed denial-of-service (DDoS), throttling and so on. What they all have in common is that they work in the context of a finite set of resources, potentially implying effects such as server overload, resource exhaustion, and unavailability of services [4][10]. Let’s look at those in detail:<\/p>\n\n\n\n

Server overload<\/strong><\/p>\n\n\n\n

The most common cause is server overload or a consequence of it. When that happens, the drop in system performance often affects other areas of the system. As shown in Figure 2, in the initial scenario (left), load coming from two reverse proxies is distributed between clusters A and B, so that cluster A operates at an assumed maximum capacity of 1000 requests per second. In the second scenario (right), cluster B fails and the entire load hits cluster A, which can lead to an overload. Cluster A now has to process 1200 requests per second and starts to misbehave, causing the performance to drop well below the desired 1000 requests per second [4].<\/p>\n\n\n\n

\"\"<\/a>
Figure 2: Clusters A and B receiving load according to capacity (left) and cluster A receiving overload if cluster B fails (right). (Own illustration based on [4])<\/figcaption><\/figure>\n\n\n\n

Resource Exhaustion<\/strong><\/p>\n\n\n\n

Resources of a server are limited. If the load increases above a certain threshold, the server’s performance metrics, such as latency or error rates, deteriorate. This translates into a higher risk of a crash. The subsequent effects depend on the type of resource that is causing the bottleneck, for instance,<\/p>\n\n\n\n