System boundaries and queueing timelines

A service that needs 10 ms on average does not necessarily return a response within 10 ms. Queueing theory separates waiting for a resource from occupying it, then studies how arrivals, service, scheduling and capacity shape the wait.

Draw the boundary first

An application entrance, connection pool, worker pool and database can each have a queue. Decide when a job enters and leaves, and whether jobs in service count. The boundary below includes the waiting and service areas; admission rejection occurs outside it.

For job $i$, let $a_i$ be arrival, $b_i$ service start and $d_i$ departure. This chapter has uninterrupted service and completion as the only departure outcome:

$$W_{q,i}=b_i-a_i,S_i=d_i-b_i,T_i=d_i-a_i=W_{q,i}+S_i.$$

$W_q$ is waiting time, $S$ service time and $T$ system or response time. The number inside is $N(t)=Q(t)+B(t)$: $Q$ counts waiting jobs and $B$ jobs in service. A single server has $B\in \{0,1\}$; $c$ servers can have up to $c$ jobs in service.

Service time depends on the resource boundary. A connection's occupancy from checkout to return can include remote I/O waits; it is not CPU execution time. Asynchronous I/O may release a thread while retaining a connection, memory or downstream quota.

Calculate one trace

For a single, work-conserving FIFO / FCFS server:

$$b_i=\max (a_i,d_{i-1}),d_i=b_i+S_i.$$

Start empty with previous completion time zero. Arrivals $[0,1,2,3]$ s and services $[4,1,1,1]$ s produce starts $[0,4,5,6]$ and departures $[4,5,6,7]$. Waits are $[0,3,3,3]$, averaging 2.25 s. System times are all 4 s, even though mean service is only 1.75 s.

Write cumulative arrivals, starts and departures as $A(t),G(t),D(t)$. Starting empty with no removal other than completion gives $N=A-D$, $Q=A-G$ and $B=G-D$. Vertical differences between cumulative curves are counts. Horizontal distances for the same job are times.

Predict who is affected when only the first job gets longer. Then increase the arrival gap: waiting can disappear while service bars retain their width. Completions precede arrivals at equal timestamps so a just-released server is available.

From a trace to statistics

Arrival rate $\lambda$ and per-server service capacity $\mu =1/E[S]$ have units jobs/s. $L=E[N]$ and $L_q=E[Q]$ denote stationary mean counts. Actual completion throughput $X$ differs from offered traffic: an idle server does not continuously produce completions at rate $\mu$.

For one stable, work-conserving server with no losses, its busy fraction is $\rho =\lambda E[S]$. This is not automatically the CPU utilization of a system with several resources, nor is it concurrency divided by worker count. Stability and tails require additional model assumptions introduced later.

Check your understanding

1. A connection-pool boundary contains 100 requests, of which 20 hold connections. What are $N,Q,B$?

2. CPU utilization is 30% while response time rises. Does that rule out queueing?

Further reading

The CMU modeling course begins with system vocabulary and performance measures. Google SRE discusses differing request costs and resource constraints. Next, the same kind of trace yields Little's law.