Amdahl's Law

The first of these laws is about the influence of serialized access on the mean response time (or latency), and thereby on throughput. Despite the fact that we may always want to parallelize our work, there may come a point where it cannot be parallelized and we are required to serialize work instead. This might be the case if we have a coordinator worker, or an aggregation or reduction operator in the reactive flow, meaning we have to join all executions. Alternatively, it may be a piece of code that works only in serial mode, so it cannot be executed in parallel. In large microservice systems, this might be the load balancer or orchestration system. Therefore, we can refer to Amdahl's Law in order to calculate the throughput changes using the following formula:

In this formula, X(1) is the initial throughput, N is the parallelization or the number of workers, σ is a coefficient of contention (also referred to as the serialization coefficient), or in other words, the percentage of the overall time spent on executing code that can't be processed in parallel.

If we do a simple calculation and build a dependency graph of the throughput of parallelization with some random coefficient of contention, σ = 0,03 and initial throughput X(1) = 50 requests per second on the range of parallelization N = 0..500, then we achieve the following curve:

Diagram 6.4. Throughput changes depending on parallelization

As we can observe from the preceding diagram, with an increase in parallelization, the throughput of the system starts becoming slower and slower. Finally, the overall increase in throughput comes to an end and instead follows asymptotical behavior. Amdahl's Law says that the overall work parallelization does not give a linear rise of throughput, because we cannot process results faster than the serialized part of the code. From the perspective of scaling a common web application, this statement means that we do not gain any benefits from increasing the number of cores or nodes in the system if we have a single point of coordination or processing that cannot work faster. Moreover, we lose money by supporting redundant machines, and the overall increase in the throughput is not worth the cost.

From the preceding chart, we can see that the changes in throughput depend on parallelization. However, in many cases, we have to understand how latency changes as dependency on parallelization increases. For this purpose, we may combine the equations from Little's Law and Amdahl's Law. As we may remember, both equations contain the throughput (X). Hence, we have to rewrite Little's Law in order to combine both formulas:

After the preceding transformation, we may replace X(N) in Amdahl's Law, and derive the following:

Finally, in order to derive the latency (R), we have to do the following transformation:

From the preceding formula, we may conclude that the overall growth is linear. The following diagram shows the latency growth curve depending on the parallelization:

Diagram 6.5. Linear growth of latency depending on parallelization

That means that with an increase in parallelization, the response time decreases.

To conclude, as described by Amdahl's Law, a system that has parallel execution always has points of serialization, which causes additional overhead and does not allow us to reach higher throughput just by increasing the level of parallelization. The following diagram shows this system:

Diagram 6.6. Simultaneous processing example using Amdahl's Law

The previous diagram can be described as follows: 

  1. This is the worker representation. Note that, even here, the code cannot be split into smaller sub-tasks that can be executed independently, which should also be considered a point of serialization.
  2. This is the representation of actors in the queue or user requests.
  1. Here is the queue of actors or user requests before they have been assigned to a dedicated worker. The serialization point is coordination and assigning an actor to the worker.
  2. Actor coordination may be required in both directions. At this point, the coordinator may carry out some actions to send a response back to the user.

To summarize, Amdahl's Law states that the system has its bottlenecks and, because of this, we can't serve more users or have lower latency.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.135.191.86