Performance reasoning — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 1: Foundations: understanding work, time, and resources

Prerequisites: Lesson 05 and the preceding foundations.

Learning outcomes

• Calculate latency budgets, utilization, throughput ceilings, and in-flight work under stated assumptions.
• Interpret tail percentiles and queueing models without treating model assumptions as measurements.
• Construct a benchmark comparison that preserves correctness, hardware, load, and timing boundaries.

A benchmark can stop asking at exactly the wrong time

A load generator sends one request, waits for the result, and then sends the next. When the service slows down, the generator sends fewer requests. The server reports an acceptable response-time distribution for the requests it received. Real users, however, continue arriving during the slowdown and accumulate in queues. The benchmark has changed its offered workload in response to the problem it was intended to reveal.

This is a form of coordinated omission: the measurement omits waiting that would occur under an arrival process independent of response completion. It is one reason a single throughput number and a latency histogram do not fully describe a performance experiment.

Performance reasoning starts by defining boundaries, units, workload, and assumptions. It then separates a capacity estimate from a measurement and a measurement from a causal explanation. Those distinctions prevent elegant equations from being mistaken for production guarantees.

Service time, waiting time, and response time

Service time is the time a resource spends doing work for an operation. Waiting time is time before that work can proceed. Response time includes the service and waiting inside the chosen boundary. An operation may use several resources and wait several times; total response time is not necessarily the sum of every resource’s service time because some work can overlap.

An end-to-end purchase trace might include client queueing, connection-pool wait, network transit, admission wait, lock wait, CPU execution, durable-log wait, and response delivery. A database’s internal execution timer may exclude most of these. A useful investigation aligns the product symptom with the measured boundary before optimizing anything.

Latency distributions matter because requests are not identical. Cache misses, skew, long transactions, compaction, retransmission, and scheduler pauses can produce a long tail. The median can remain stable while a small but important fraction of purchases becomes unusably slow. A p99 value means roughly 99% of observations at that boundary are at or below the reported value; it is not the maximum.

Percentiles do not add like ordinary means. Adding the p99 network time to the p99 database time does not generally produce the p99 end-to-end time. The slow events may occur on different requests, or their causes may be correlated. End-to-end traces and distributions provide the evidence needed to understand those relationships.

Resource-demand ceilings

A first-order capacity estimate divides available resource by demand per operation. If a transaction uses 40 microseconds of one CPU’s execution time, one fully utilized equivalent CPU-second can supply an ideal 25,000 such transactions per second. Eight equivalent resources provide an ideal 200,000 only if the work parallelizes and no other limit intervenes.

This is a ceiling under stated assumptions, not a forecast. Synchronization, cache misses, background work, replication, and skew can lower the useful rate. Operations can also have different demands. A weighted workload model sums each class’s rate times its resource requirement.

For an illustrative workload of 30,000 reads per second at 10 microseconds of CPU and 10,000 writes per second at 50 microseconds, CPU demand is 30000 × 10 us + 10000 × 50 us = 0.8 CPU-seconds/second. If writes generate 1 KB of log data each, the logical log rate is 10 MB/s using decimal units. Replication and device amplification add separate work.

A resource vector records CPU time, memory retained, storage bytes, storage operations, and network bytes. The first saturated dimension determines current capacity. Improving a different dimension may have little immediate effect. Once the bottleneck is removed, another dimension becomes visible, so measurements must be repeated after material changes.

Little’s Law and boundary consistency

For a stable system, average in-flight work L equals throughput lambda times average residence time W: L = lambda W. The units must match. At 8,000 completions per second and 25 milliseconds average residence, the average in-flight count is 8000 × 0.025 = 200.

The law does not say that 200 worker threads are required. In-flight requests may be waiting asynchronously, queued for admission, or using different resources. It also does not promise that increasing in-flight work raises throughput. Beyond saturation, additional concurrency primarily increases waiting.

The measurement boundary must be identical for all three quantities. Using database-only execution time with client-side in-flight counts mixes boundaries. An indefinitely growing queue is not a stable operating point. A short interval around a traffic transition may require more careful accounting than steady-state averages provide.

Little’s Law is especially useful for checking operational observations. If a dashboard claims 20,000 completions per second, 100-millisecond mean response time, and only 100 average in-flight operations at the same boundary, the values are inconsistent. The likely explanation is a boundary, sampling, aggregation, or definition mismatch that should be resolved before tuning.

Queueing and the nonlinear cost of utilization

Queueing models explain why latency can rise sharply as offered work approaches capacity. In a simplified M/M/1 model, arrivals are Poisson, service times are exponentially distributed, one server handles work, and the system is stable with arrival rate below service rate. Mean response time is 1 / (mu - lambda).

With illustrative service rate mu = 10000/s and arrival rate lambda = 9000/s, mean response is 1/1000 s = 1 ms. Mean service time alone is 1/10000 s = 0.1 ms. At 99% utilization, arrival rate is 9,900/s and modeled mean response rises to 10 ms. The resource became only slightly busier while waiting increased substantially.

Real databases rarely match every M/M/1 assumption. Service distributions can be heavy-tailed, arrivals can be bursty, resources can be parallel, and transactions can contend. The equation should be used as a teaching model, not fitted casually to claim exact p99 latency. Its durable lesson is that operating close to a capacity ceiling leaves little slack for variation.

A stable average also hides bursts. If arrivals exceed completions for a period, a queue accumulates. An illustrative excess of 5,000 requests per second for two seconds creates 10,000 queued requests. If the service later has only 2,000 requests per second of spare capacity, draining that backlog takes five seconds even after the spike ends. Retry amplification can prevent the spare capacity from appearing at all.

Amdahl’s Law and serialization

Amdahl’s Law describes the limit of speeding up only part of a computation. If fraction f of execution remains serial and the rest scales ideally across p workers, ideal speedup is 1 / (f + (1-f)/p). With a 20% serial fraction and eight workers, speedup is 1/(0.2+0.8/8) = 3.333..., not eight.

The model assumes a fixed amount of work and ignores new overhead. Real parallelization can add synchronization, communication, and memory traffic. A parallel implementation may therefore fall below the ideal bound or even become slower. Conversely, reorganizing the computation can change the serial fraction rather than merely adding workers.

For a contended inventory record, the important serial portion might be the interval during which the authoritative stock transition cannot overlap another transition. If that interval contains network waiting, reducing boundary crossings can shrink the serial portion. More machines do not independently decide the same exclusive ownership fact without some coordination or a changed business model.

The relevant fraction also depends on workload. A shared counter benchmark and independent tenant transactions have different parallel structure. A product can scale well for one and poorly for the other without contradiction. Capacity claims must describe both the operation and the distribution of shared dependencies.

Tail amplification through fan-out

A request that waits for many subrequests completes when its required slowest dependency completes. If each of 100 independent subrequests has a 1% chance of exceeding a threshold, the probability that at least one exceeds it is 1 - 0.99^100, approximately 63.4%. Independence is an illustrative assumption; correlated failures can make behavior worse or differently shaped.

This explains why distributed joins, scatter/gather reads, and global metadata operations need careful tail design. A component’s p99 can become an ordinary event when a parent depends on many components. The paper The Tail at Scale examines the broader importance of tail behavior in large services. The numerical example here is a constructed probability calculation.

Hedged requests can sometimes reduce latency by sending redundant work, but they consume capacity and require safe semantics. Uncontrolled hedging during overload can increase the very queues causing the problem. Cancellation may arrive too late to reclaim the duplicated work. The optimization must include eligibility, budgets, and the impact on other clients.

Open-loop and closed-loop experiments

A closed-loop generator keeps a fixed number of outstanding operations or waits for responses before sending more. It is useful for studying concurrency levels and client behavior with bounded outstanding work. Its arrival rate depends on the system’s response time.

An open-loop generator schedules arrivals independently, such as a fixed rate or a sampled arrival process. It can reveal the backlog and failures produced when demand exceeds capacity. The generator itself must have enough resources and must record scheduling delay rather than silently dropping intended arrivals.

Neither style is universally correct. The experiment should match the question. A protocol throughput test may use many outstanding operations to expose server capacity. A user-facing arrival-rate test should preserve the intended demand during stalls. Comparing systems under different outstanding-work limits can change both throughput and latency, so the limits belong in the methodology.

Warm-up and steady state also need definition. An LSM engine tested before compaction begins may show an unsustainable write rate. A warm cache may hide restart behavior. A short test may miss checkpoints, garbage collection, or periodic maintenance. The observation interval must include the mechanisms relevant to the proposed deployment.

A complete measurement record

A reviewable result states the operation, dataset, access distribution, request mix, concurrency or arrival model, hardware, topology, software versions, durability, isolation, replication, warm-up, run duration, and failure accounting. It reports useful completions alongside rejects, errors, timeouts, retries, and resource usage.

Latency should be observed from the appropriate client boundary, with distribution data rather than only averages. Timeouts must not disappear from the report simply because they lack successful completion times. Histogram precision, aggregation, and sampling can affect interpretation. Combining percentiles from separate machines by averaging them is generally invalid.

A causal claim needs additional evidence. If p99 improves after adding RAM, it may be because cache misses fell, because background pressure changed, or because the workload shifted. Traces, profiles, and controlled comparisons help discriminate these explanations. Correlation between a configuration change and a result is a starting observation, not a complete mechanism explanation.

Variability determines how quickly queues hurt

The M/M/1 example uses exponential service times, which have a particular variance. Real transactional workloads may contain many 50-microsecond operations and a few 50-millisecond operations. The mean alone conceals the scheduling impact of those long requests. A single long operation can make many arrivals wait even when its contribution to average utilization seems modest.

For a stable first-come, first-served GI/GI/1 queue with independent interarrival and service sequences and finite variances, Kingman’s approximation offers intuition for arrival and service variability: mean waiting ≈ ((ca² + cs²)/2) × (rho/(1-rho)) × mean service. Here ca and cs are standard deviation divided by mean for interarrival and service times, and rho is utilization. This is an approximation under queueing assumptions, not a latency guarantee or a formula for percentiles. It is included to expose how burstiness and service-time variance amplify waiting. The historical foundation is Kingman’s 1961 heavy-traffic paper.

With illustrative mean service of 100 microseconds, utilization 0.8, and both squared coefficients equal to 1, modeled mean waiting is 1 × 4 × 100 = 400 microseconds. If service variability instead has squared coefficient 9 while arrival variability remains 1, the variability multiplier becomes 5 and waiting becomes approximately 2,000 microseconds. Mean service and utilization have not changed. The modeled response rises from 500 to 2,100 microseconds because variation matters.

This explains why bounding exceptionally expensive operations can improve many users’ latency. It also explains why separating analytical scans from short transactions may help even before total resource usage changes. Isolation changes which arrivals wait behind which service-time distribution. The real system still needs measurements because parallel execution, priority, locks, and storage queues depart from the simplified model.

Percentiles must be aggregated correctly

Suppose server A handles 99,000 requests with low latency while server B handles 1,000 requests with much higher latency. Averaging their reported p99 values gives neither the fleet p99 nor the customer p99. Percentiles describe ordered samples; they are not additive summary statistics. A correct aggregate needs raw observations or mergeable distributions with appropriate weighting and known precision.

Time aggregation can be equally misleading. Averaging sixty one-minute p99 values does not produce the hour’s p99. A brief incident might contribute enough requests to affect the overall tail, or it might be hidden when each minute receives equal weight despite very different traffic. Dashboards should state whether they show per-window percentiles, a percentile over the combined interval, or a maximum of window values.

Histogram buckets trade precision for storage and mergeability. If all values between 100 and 200 milliseconds occupy one bucket, an estimated p99 inside that bucket cannot be interpreted as precise to a fraction of a millisecond. The measurement’s resolution belongs in the interpretation. A separate timeout counter is also necessary when timed-out work never appears in the successful-response histogram.

Include unsuccessful and unfinished work

A load test can report excellent successful-request latency by quickly rejecting most traffic. That may be appropriate overload behavior, but it is not equivalent to serving the offered workload. Report arrivals, admissions, rejections, attempts, successful business outcomes, and infrastructure failures separately. Also report requests still in progress when the test stops; otherwise the slowest operations can disappear from the record.

For a constructed ten-second interval, assume 100,000 arrivals, 80,000 admissions, 70,000 completed responses, and 10,000 still queued or executing at the end. A success histogram over those 70,000 completions excludes the unfinished 10,000. Extending observation until work drains, or explicitly treating right-censored outcomes, is necessary to understand their residence time. Simply dropping them can make a saturated service appear faster.

The generator can be the bottleneck too. Serialization, encryption, operating-system limits, insufficient sockets, and response parsing can prevent it from producing the intended arrivals. Measure scheduled send time, actual send time, and server receipt where possible. If actual sends drift later than the intended schedule, the benchmark is no longer the requested open-loop workload unless that delay is included or clearly reported.

Construct an interpretable experiment

Begin with a hypothesis such as “the hot inventory key limits successful purchases before aggregate CPU saturates.” Keep the invariant and durability setting fixed. Vary hottest-key concentration while holding total offered business arrivals approximately constant. Observe lock or owner-queue wait, committed outcomes, CPU, log throughput, and per-class latency. This design can connect a causal mechanism to a result more convincingly than changing several settings at once.

Run long enough for relevant background cycles. An LSM engine may accumulate compaction debt during a short test and pay it afterward. A versioned engine may postpone cleanup while a long snapshot remains active. A buffered writer may initially absorb work into memory faster than storage can persist it. The test needs to reach a sustainable state or explicitly identify itself as a burst-absorption experiment.

Repeat measurements to expose variance. Record the dataset seed, key distribution, hardware, software versions, topology, warm-up, cache state, and test duration. A result without these conditions is difficult to reproduce or compare. A single fastest run is weak evidence because it selects favorable noise and may exclude the events responsible for production tails.

Scenario: a fast backend and an unchanged user experience

Assume a constructed operation spends 40 milliseconds on network travel, 20 milliseconds waiting in a pool, 5 milliseconds executing, 4 milliseconds waiting for durability, and 11 milliseconds on other client and service work. Its total is 80 milliseconds. A tenfold execution improvement reduces 5 milliseconds to 0.5, giving 75.5 milliseconds, about a 5.6% end-to-end reduction. The backend optimization is real, but its fraction of the total limits the visible benefit.

Now assume the same execution stage is near saturation and contributes 50 milliseconds of queueing in addition to its 5 milliseconds of service. Reducing service demand can reduce utilization enough to remove much of that queue. The end-to-end improvement can then exceed the direct 4.5-millisecond service-time savings. This is why Amdahl-style fixed-component reasoning and queueing reasoning need to be used together. A component’s waiting cost can change nonlinearly with its service demand.

A careful report therefore separates direct work removed from indirect queueing changes. If the test uses different arrival rates before and after optimization, the causal interpretation becomes harder. Holding offered workload fixed first helps establish the effect; a second experiment can then explore the new capacity ceiling.

Read benchmark claims as conditional statements

A throughput figure implicitly says that a particular implementation, hardware configuration, workload, and guarantee set produced a measured rate. It does not independently establish a maximum user count. Converting rate to users requires action frequency, retries, contention, background work, and fan-out. Converting rate to latency requires an arrival process and a latency observation at the desired operating point.

Likewise, the same number of CPU cores does not establish equal cost or equal available capacity when memory bandwidth, storage, network, accelerators, or cloud resource limits differ. A useful comparison exposes the resources and guarantees that differ rather than hiding them behind one headline. The purpose of a benchmark is to support a decision about a workload, not to assign a universal ranking to architectures.

A queue diagram and a utilization table describe different evidence

arrivals -> [admission boundary] -> [waiting queue] -> [server] -> outcomes
                                    waiting Wq       service S
                  measured residence W = Wq + S for this boundary

The diagram identifies one consistent measurement boundary. A request rejected at admission should be counted separately rather than assigned an invented execution time. A request waiting in an upstream connection pool lies outside this diagram unless the boundary is expanded to include it.

All rows use the same 0.1 ms mean service time and the model’s Poisson/exponential assumptions. They are computed examples, not observations of a database. The table shows why capacity planning needs headroom and why a “99% busy” resource is not simply 9% slower than a “90% busy” resource.

A real system can have a smaller or larger tail depending on arrival bursts, service variance, parallelism, and scheduling. Its p99 cannot be read from this mean-response table. The useful next step is to compare a measured workload with the model’s assumptions and identify which effects the model omits, rather than forcing measurements to match an attractive equation.

Design conclusion

Performance engineering is the practice of connecting a workload contract to a cost model and then testing the model against observation. Equations provide bounds and consistency checks. Measurements reveal distributions and real interactions. Neither replaces the other.

The next part turns the logical data into physical representations and access paths. That is where many of the demands in this lesson originate: how many bytes a lookup touches, how much work an update maintains, and how a query’s shape changes the amount of data the engine must examine.

Sources and further reading

• The Tail at Scale, 2013
• Kingman: The single server queue in heavy traffic, 1961
• CMU database systems curriculum

Course index · Lesson plan