Characterizing Performance Bottlenecks

If you do a Google search using keywords like: performance, bottleneck, analysis, you get quite a bewildering list of responses, and none of them seems to clearly define what they mean by the term bottleneck.^†

The word bottleneck refers to a choke point or narrowing, literally like the neck of a bottle, that causes the flow to take longer than it would otherwise. The effect on performance is commonly seen on the freeway in an area undergoing roadwork. Multiple lanes of traffic are forced to converge into a single lane and proceed past the roadwork in single file. Going from parallel traffic flow to serial flow means the same number of cars will take longer to get through that same section of road. As we all know, the delay at a freeway bottleneck can be very significant.

The same is true on a single-lane country road. If you come to a section where roadwork slows down every car, it takes longer to traverse that section of the road. Bottlenecks are synonymous with slow downs and delays, but they really determine a lot more than delay.

Queueing Analysis

When it comes to computer performance analysis, we can draw on the terminology of queues to characterize a performance bottleneck more accurately. Figure 1 shows an arrangement of three queues in tandem with arrival rate $\lambda$ and respective service times: $S_a, S_b$ and $S_c$. In steady state, what goes in must come out, so the throughput ($X$) of the tandem system is also $\lambda$, i.e., $X=\lambda$.

Figure 1. Serial bottleneck based on service times.

Let's suppose that the service time of the middle queue $S_b$ is the longest of the service times (indicated in red). Service completions at the left queue must occur more rapidly than completions at the middle queue because $S_a < S_b$ so, those completions simply feed into the waiting line at the middle queue.

Service completions at the right queue also occur faster than completions at the middle queue because $S_c < S_b$. But that queue is downstream from the middle queue and therefore can have no impact on its performance. The right queue is generally waiting to service arrivals from the middle queue.

In Figure 1, the middle queue is the bottleneck resource. It is identifiable by having the longest service time $S_b > S_a,S_c$, and by Little's law, $\rho = \lambda S$, it is the busiest server.

A Parallel Puzzle

That all seems obvious enough because it's akin to driving on the country road mentioned earlier. Everything is flowing in a single file and one section, the bottleneck, is slower than all the others. But what does the queueing analysis look like if there's a bottleneck in parallel flow? Such a situation is shown in Figure 2.

Figure 2. Parallel bottleneck based on service times.

The flow out of the queueing resource on the left splits into two flows with a fraction of the original flow, say, $f = 95$% going to the bottom resource with service time $S_c$, and the remaining 5% going to the upper resource with the longest service time $S_b$ (also indicated in red, like Fig. 1). This is equivalent to the bottom resource seeing a request rate of $0.95\lambda$ and the upper (bottleneck) resource seeing a request rate of $0.05\lambda$.

The utilization of the top resource is given by: \begin{equation} \rho_b = (0.05\lambda) S_b \label{eqn:utilb} \end{equation} and the utilization of the bottom resource is given by: \begin{equation} \rho_c = (0.95\lambda) S_c. \label{eqn:utilcc} \end{equation} To keep the arithmetic simple, let's assume the service time at the bottleneck resource is twice as long as the service time at the lower resource, i.e., $S_b = 2 S_c$. Substituting, we can rewrite \eqref{eqn:utilb} as: \begin{equation} \rho_b = (0.10\lambda) S_c \label{eqn:utilbc} \end{equation}

Since all the other parameters are equivalent and 95% of the original traffic flow is going to the bottom resource, it's clear that $\rho_c$ is 9.5 times bigger than $\rho_b$. But wait!

If the bottom resource is busier than the bottleneck resource, how can the top resource be the bottleneck!?

A similar question was raised by Guerrilla alumnus, Ken Beer, in another context and it demonstrates how easy it is to become bamboozled when doing performance analysis. Nothing wrong with that; happens to all of us. The key is to unwind the line of argument to find the flaw in the logic. For me, that's where the equations are invaluable.

The Resolution

To make everything consistent again, we need to rearrange utilization equations \eqref{eqn:utilcc} and \eqref{eqn:utilbc} as follows: \begin{equation} \rho_b = \lambda (0.10 S_c) = \lambda D_b \end{equation} \begin{equation} \rho_c = \lambda (0.95 S_c) = \lambda D_c \end{equation} where I've written $D_b = 0.10 S_c$ and $D_c = 0.95 S_c$. But what do those $Ds$ mean?

Figure 3. Parallel bottleneck based on service demands.

In general, $D$ denotes the service demand, i.e., the total time it takes to service a request, if it makes more than a single visit to the server. It's the original service time, $S$, multiplied by the visit ratio or visit fraction, $V$. In other words, it reflects the fact that it takes $V_c = 95$ visits out of 100 to the bottom resource for every $V_b = 5$ visits out of 100 to the top resource, in order to service a request. Since the bottom resource has the longest service demand, $D_c > D_b$, it is the true bottleneck resource, now indicted correctly by the red server in Figure 3.

Figure 4. Serial bottleneck based on service demands.

So, a bottleneck queueing resource is properly determined by its service demand, not it service time. This distinction between service time and service demand is discussed in more detail in my Perl::PDQ book. As Figure 4 shows for the case of sequential queues, the bottleneck resource (in red, again) is the same, irrespective of applying the service time or service demand definition. This is only true, however, in the sequential case because the arrival rate is the same at each resource.

Bottlenecks in Practice

In practice, the approach taken to detecting bottlenecks is very much a function of the system being analyzed, the available instrumentation and the type of performance statistics provided in that environment. That's the reason for the bewildering Google list mentioned in the introduction.

That said, however, all bottleneck detection boils down to measuring, either by sampling or tracing, any of the following fundamental performance metrics:

• delays like waiting time, service time, or response time
• resource utilization
• queue length or buffer occupancy

and comparing them to find the largest one.

We know from the foregoing discussion that all these metrics are actually a function of the service demand. That dependency can be written schematically as: \begin{equation} \max(D_1,D_2,\ldots) \rightarrow \max(\rho_1,\rho_2,\ldots) \rightarrow \max(Q_1,Q_2,\ldots) \end{equation} Moreover, it's very valuable to establish the maximum service demand, if at all possible, because it controls the maximum system throughput according to: \begin{equation} \lambda \equiv X < \dfrac{1}{\max(D_1,D_2,\ldots)} \label{eqn:maxx} \end{equation} From the standpoint of queueing models, like those expressed in PDQ, the arrival rate and the service demand are essential input metrics; everything else is an output metric.

Equation \eqref{eqn:maxx} also accounts for the the following Guerrilla mantra:

You never remove a bottleneck, you just move it.

The red server in Figures 3 and 4 is called the primary bottleneck. If that service demand can be reduced by performance tuning, for example, then the secondary bottleneck becomes the new primary bottleneck. It's also possible to have different bottlenecks existing simultaneously in the same system.

---

^† The same comment about creating confusion also holds for the book The Goal, by E. M. Goldratt and J. Cox, which I was graciously presented as a gift by some appreciative Guerrilla alumni in 1998. Unfortunately, I had trouble seeing the merits of this book. Any author who takes 140 pages to explain the concept of a bottleneck, has already created a bottleneck for understanding bottlenecks.

---

POSTSCRIPT

There is a potential ambiguity in Figure 3. When you draw such diagrams, you have a choice:

1. Split the flow according to fractions $f$ and $(1 - f)$, but use the service time $S$ (not $D$) to label each server; as shown in Figure 3. The reason for doing this is to avoid a double multiplication by $f$. For example, that would happen when calculating the resource utilization with one $f$ coming from the split flow to the lower resource, and another $f$ coming from the demand $D = f S$ at that server. The utilization would then be calculated incorrectly as, $\rho = (\lambda f) \times (f S)$.
2. Use the service demand $D$ (not $S$) to label each server, but do not split the total flow $\lambda$. The trouble with this approach is that it looks wrong, even when drawn correctly. Since it's logically impossible for $\lambda$ to be going to only one resource and be split at the same time, you would have to show the total flow going to one resource for $f~\%$ of the time, but going to the other resource $(1-f)~\%$ of the time. That probably requires two diagrams.

Option 1 is recommended because it appears more intuitive. PDQ, on the other hand, uses option 2, internally.