Stragglers: two regimes that need different answers

How do random and deterministic stragglers differ, and how does peer comparison tell them apart?

A straggler is a task or node that finishes much later than its peers. Mixing up the two kinds is a common error, so separate them.

Random stragglers are statistical. A request lands behind a GC pause, a compaction, a scheduler hiccup or a cold page. Any node can produce one, and the identity of the slow node is uncorrelated across requests. The right response is redundancy in time: hedged requests (send a second copy of a slow request to another node and use whichever answers first), tied requests, and speculative re-execution. These work precisely because independence holds: a second attempt lands on a different node whose delay is uncorrelated with the first. (The mechanism is hedging; its budget and its off switch under overload are in retry and hedge budgets.)

Deterministic stragglers are a property of a node: the throttled NIC, the dying disk, the host with a noisy neighbor. The identity is stable across requests. Hedging is now nearly useless. It doubles load, and in a scatter-gather where the query must touch every shard it cannot avoid the bad node, because there is no alternative replica for that shard's data. Worse, hedging under a deterministic straggler adds load to a system that is already short of capacity. This mitigation is correct in one regime and harmful in the other: the regime-flip principle, cleanly.

Peer-relative comparison

So the detector must tell them apart, and threshold-based detection cannot. An absolute latency threshold must be set for the worst legitimate case (the largest partition, the coldest cache), and is therefore far above the signal of a degraded node.

The mechanism that works is peer comparison. Nodes doing similar work are controls for each other. A node that is persistently in the 99th percentile of the peer distribution is a straggler, even if it is comfortably inside its absolute SLO (service-level objective, the promised latency). This is the single most useful detection idea in this article.

Its blind spot is exact: peer comparison is blind to correlated degradation. If every node is slow, no node is an outlier, and the detector reports health. So run both: peer-relative detection for gray failure and absolute thresholds for systemic degradation. They fail in complementary places, which is the argument for running both instead of choosing.

def slow_peers(latency_p99_by_node, factor=3.0):
    # a node is an outlier if its p99 is more than 3x the median of its peers
    values = sorted(latency_p99_by_node.values())
    median = values[len(values) // 2]
    return [n for n, v in latency_p99_by_node.items() if v > factor * median]