High-Performance Network Systems Notes

Performance

What is performance?

• Throughput
• Latency
• Resource usage

Why do we care about performance?

• User experience
• Resource costs

Specialization can improve performance. For example, Google designed TPUs to better perform matrix multiplication and convolutions.

On the other hand, "premature optimization is the root of all evil" (Donald Knuth). We should also make sure to evaluate the costs of improving our performance.

Measuring Performance

Open, Closed, and Partially-Open Systems

In a closed-loop system, there is a fixed number of clients which make a request, wait for a response from the server, and then make another request. New requests only arrive when the server responds.

$\rho = X \times E[S]$, where:

• $\rho$ is server load
• $X$ is mean throughput, or req/s
• $E[S]$ is mean service demand, or work/req

In an open-loop system, there is a set rate of requests that are sent to the server, independent of whether the server responds to requests.

$\rho = \lambda \times E[S]$, where:

• $\rho$ is server load
• $\lambda$ is average arrival rate (req/s)
• $E[S]$ is mean service demand, or work/req

In a partially-open-loop system, there is a set rate of users that visit the server. Each user has some probability $p$ that, after receiving a response, makes another request. Thus, there is a variable number of requests per user session.

$\rho = \lambda \times E[R] \times E[S]$, where:

• $\rho$ is server load
• $E[R]$ is mean number of req/session, or $1 / (1 - p)$
• $E[S]$ is mean service demand, or work/req

References: Open Versus Closed: A Cautionary Tale

Principles of Workload Generators

In order to accurately evaluate a system, we must identify whether the system is in reality open, closed, or partly-open. Shroeder et al. suggests that we should first model each system as a partially-open system, and then decide whether an open or closed model is appropriate.

1. For a given load, mean response times are significantly lower in closed systems than in open systems.
   • Because an open-loop system has a fixed number of clients, there is an upper bound on the number of requests in the queue, and thus a limit on queuing delay.
   • A closed-loop system can have a queue that grows indefinitely. This problem is generally addressed by dropping requests, buffering in a message queue, or applying backpressure on the clients.
2. As the number of clients increases, closed systems become more similar to open systems.
3. While service demand variability has a large effect in open systems, the effect is much smaller in closed systems.
   • When there is service demand variability, short tasks become stuck behind long tasks in a queue (head-of-line blocking)
   • Open systems have an unbounded queue size, so many short jobs can be stuck behind long jobs
   • Closed systems have a fixed queue length, so fewer short jobs are stuck behind long jobs
4. While open systems benefit significantly from scheduling with respect to response time, closed systems improve much less.
   • Scheduling can prevent small jobs from queueing behind large jobs, which has a higher impact in open systems
5. Closed systems only improve if there is moderate think time and a large number of clients.
   • If think time is very low, then the scheduler cannot distinguish between clients
   • If think time is very high, then server load is small, there is very little queuing delay, and thus scheduling does not have much of an effect
6. Scheduling can limit the effect of variability in both open and closed systems, although the effect is less for closed systems due to principle (3)
7. A partly-open system behaves similarly to an open system when the mean number of reqs per session is small. It behaves similarly to a closed system when the mean number of reqs per session is big.
8. In a partly-open system, think time has little effect on mean response time.

References: Open Versus Closed: A Cautionary Tale

Issues with Measuring Tail Latency

1. Most load-testers use a closed-loop system, underestimating tail latency.
2. With enough load, clients may start to experience queuing delay, leading to a bias in latency measurements.
3. Load testers that maintain an internal histograms with static buckets can lose information when latency exceeds the upper bound of the histogram. Histogram binning needs to be adaptive.
4. For some systems, the estimated latency can converge to different values, even after running for a long time (hysteresis). If there is a pattern of hysteresis, then the measurement must be run multiple times, and the converged values should be aggregated (e.g. mean, median).
5. A load-generator should have a warm-up, calibration (for histogram buckets), and measurement phase.

References: Treadmill: Attributing the Source of Tail Latency through Precise Load Testing and Statistical Inference

Attempted, Offered, and Achieved Load

Assume that an open loop request generator can achieve an infinitely high load (req/s). To decrease the load, increase the wait time between requests. To set an achieved load of $T$ tasks per second, we must wait $1/T$ seconds per task.

There are several ways to implement wait:

• sleep is a system call that tells the operating system to pause a thread for a set amount of time. One issue is that the CPU scheduler will not necessarily start the process at exactly the desired time.
• Busy loops are more accurate but are limited by the number of cores on the machine.

Assume that a closed loop request generator achieves a low load (req/s) because it needs to wait for a response. To increase the load (req/s) of a closed loop request generator, increase the number of threads performing work. If one request generator can achieve $T$ tasks per second, we can scale to $nT$ tasks per second by having $n$ threads. Note that we can only increase load by a discrete amount.

Note that there is a difference between attempted load, offered load, and achived load:

• Attempted load ($T$): the condition in which we want to measure the system; usually a configuration parameter in the workload generator
• Offered load: the number of req/s we actually generated with our workload generator
• Achieved load: the number of req/s the system actually did

In most cases, our offered load will be approximately equal to our attempted load. Any difference in attempted load and offered load is caused by implementation bugs. Our achieved load will always be equal or less than our offered load.

Poisson Process

A Poisson process models events as ocurring independently and at a constant average rate $\lambda$. It has two nice properties:

• It is memoryless, which means that the probability of an event in the next instant doesn't depend on how long we've already waited
• Events in non-overlapping time windows don't affect each other The convolution of multiple independent Poisson random variables results in another Poisson random variable whose mean is the sum of the two individual means. If packet arrivals follows a Poisson process with rate $\lambda$, then the number of events $k$ in a fixed window of length $t$ is:

For example, if $\lambda = 0.5$, then the probability that load is greater than $1$ is

And if $\lambda = 1$, then the probability that load is greater than $1$ is

In a real system, we might queue up requests instead. If $\lambda$ is less than the amount of load that the server can manager, then the queue probably will not grow forever. There is a stable probability even when the timescale is infinite.

Metrics

Using this model with a Poisson distribution of offered load and queuing delay, there will be a latency distribution for each offered load:

Question: How can we report a metric capturing both latency and throughput?

Generally, we establish an SLO (service-level objective) or SLA (service-level agreement) that promises that at Y latency, the system will satisfy an offered load of X.

Question: What happens to latency when offered load is greater than the capacity of the system?

In some sense, we stop measuring the system at this point.

1. If our queue can grow infinitely, then queuing delay will grow arbitrarily. At that point, there is no stable equilibrium.
2. If the queue is finite length, we will start dropping packets. The latency will be the same as that of the latency at capacity.
3. If the attempted load is too high, the client will start experiencing TCP backpressure, causing the offered load to drop. This will give the server a chance to recover, possibly decreasing latency.

If achieved load < offered load, the system is not in a constant state.

Performance Engineering

perf and flamegraphs

During the execution of a program, perf will interrupt the program many times and take a snapshot of the stack at the time of execution.

Flame graphs collects this data and shows frequent datapaths. My prefered profiling utility is samply.

Because perf writes to a buffer, it is possible for perf to drop samples. Make sure to set the sample rate such that it does not drop samples.

perf can also be used to cach the number of L1 cache misses. It can also be embedded directly in the running process with the perf-event Rust crate, which is a wrapper around the perf_event_open syscall.

References:

• perf Wiki

Block I/O

Note that perf can only interrupt the CPU and take a snapshot of the stack. Consider the latency of a single query, where the work mostly involves writing to the disk.

From the client's perspective, the majority of the latency comes from block I/O. However, from the CPU's perspective, it can hand off work to the slow disk and concurrently run other processes. Thus, disk I/O will not be represented in the flame graph despite causing most of the latency.

Cache Locality

An L1 cache can hold 32-128 KB of data per CPU core.

Consider the following workloads:

• Random reads to a hashmap
• Reads to the same key in a hashmap
• Reads to sequential keys in a hashmap

Reads to the same key will be much faster than random reads because the key fits within the L1 cache.

Reads to the sequential keys will be faster than random reads, but slower than reads to the same key. Because keys are hashed, the values are likely randomly dispersed in hashmap memory. However, if the values are heap allocated, it is likely that those have cache locality.

Consider sequential reads of a HashMap<Arc<Vec<u8>>>:

BTreeMap supports very efficient range lookups. It achieves this by laying out the memory of the values sequentially.

The C10K Problem

The C10K problem is where the synchronization overhead of threads starts dominating the application's performance.