Google Senior Site Reliability Engineer Interview Preparation Guide

Direct answer

Detecting a directed cycle with depth-first search (DFS) and a recursion stack means maintaining two boolean arrays: visited (has this node been explored at all, ever) and inStack (is this node on the CURRENT recursion path right now). An edge into a node that is visited but no longer inStack is harmless, that node was already fully explored via some other path; an edge into a node that IS inStack is a back edge into a live ancestor, a genuine cycle. This runs in $O(V+E)$.

Structured elaboration

visited[u] and inStack[u] are both set the moment DFS enters u. inStack[u] is reset to false the moment DFS finishes exploring everything reachable from u (on backtrack), while visited[u] stays true forever once set. This is what lets the algorithm tell "already explored, but not currently an ancestor" (visited, not inStack, safe) apart from "currently an ancestor on my path" (both visited and inStack, a cycle if reached again).

Worked example

import java.util.*;

public class DirectedCycle {

    public boolean hasCycle(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        boolean[] inStack = new boolean[n];
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                if (dfs(v, graph, visited, inStack)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int u, List<List<Integer>> g, boolean[] visited, boolean[] inStack) {
        visited[u] = true;
        inStack[u] = true;
        for (int v : g.get(u)) {
            if (!visited[v]) {
                if (dfs(v, g, visited, inStack)) return true;
            } else if (inStack[v]) {
                return true; // back edge into a live ancestor
            }
        }
        inStack[u] = false; // backtrack: u is no longer on the active path
        return false;
    }

    // Also returns one concrete cycle as a list of node ids, or an empty list if none exists.
    public List<Integer> findCycle(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        boolean[] inStack = new boolean[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                int[] cycleStart = new int[]{-1};
                if (dfsFind(v, graph, visited, inStack, parent, cycleStart)) {
                    List<Integer> cycle = new ArrayList<>();
                    int cur = cycleStart[0];
                    int start = cur;
                    do {
                        cycle.add(cur);
                        cur = parent[cur];
                    } while (cur != start && cur != -1);
                    cycle.add(start);
                    Collections.reverse(cycle);
                    return cycle;
                }
            }
        }
        return Collections.emptyList();
    }

    private boolean dfsFind(int u, List<List<Integer>> g, boolean[] visited, boolean[] inStack, int[] parent, int[] cycleStart) {
        visited[u] = true;
        inStack[u] = true;
        for (int v : g.get(u)) {
            if (!visited[v]) {
                parent[v] = u;
                if (dfsFind(v, g, visited, inStack, parent, cycleStart)) return true;
            } else if (inStack[v]) {
                parent[v] = u;
                cycleStart[0] = v;
                return true;
            }
        }
        inStack[u] = false;
        return false;
    }

    public static void main(String[] args) {
        DirectedCycle dc = new DirectedCycle();

        List<List<Integer>> acyclic = new ArrayList<>();
        acyclic.add(Arrays.asList(1, 2));
        acyclic.add(Arrays.asList(2));
        acyclic.add(Collections.emptyList());
        System.out.println("Acyclic graph hasCycle: " + dc.hasCycle(3, acyclic));

        List<List<Integer>> cyclic = new ArrayList<>();
        cyclic.add(Arrays.asList(1));
        cyclic.add(Arrays.asList(2));
        cyclic.add(Arrays.asList(0));
        System.out.println("Cyclic graph hasCycle: " + dc.hasCycle(3, cyclic));
        System.out.println("Reconstructed cycle: " + dc.findCycle(3, cyclic));

        List<List<Integer>> disconnected = new ArrayList<>();
        disconnected.add(Arrays.asList(1));
        disconnected.add(Collections.emptyList());
        disconnected.add(Arrays.asList(3));
        disconnected.add(Arrays.asList(2));
        System.out.println("Disconnected graph (cycle in 2nd component) hasCycle: " + dc.hasCycle(4, disconnected));

        List<List<Integer>> selfLoop = new ArrayList<>();
        selfLoop.add(Arrays.asList(0));
        System.out.println("Self-loop hasCycle: " + dc.hasCycle(1, selfLoop));
    }
}

Output (actually compiled and run with javac/java):

Acyclic graph hasCycle: false
Cyclic graph hasCycle: true
Reconstructed cycle: [0, 1, 2, 0]
Disconnected graph (cycle in 2nd component) hasCycle: true
Self-loop hasCycle: true

The disconnected test graph (0 -> 1, no cycle in that component; 2 -> 3 -> 2, a genuine cycle in the second component) confirms the outer loop's for (int v = 0; v < n; v++) if (!visited[v]) correctly restarts DFS from every unvisited node, so a cycle anywhere in the graph is found even if it is not reachable from node 0.

A few points worth naming explicitly about how the two functions above work:

• inStack[u] = true on entry, inStack[u] = false on backtrack: this reset is what makes the distinction between "ancestor, still active" and "already finished elsewhere" possible; forgetting the reset would make every previously-visited node look like a live ancestor forever, turning any two paths into the same node into a false cycle report.
• The single-array visited check alone (without inStack) is exactly what a plain reachability check needs; inStack is the ONLY addition cycle detection requires on top of ordinary DFS.
• findCycle reuses the identical traversal shape, adding only a parent array (set on first discovery) and a cycleStart marker (set the moment a back edge is found), then reconstructs the path by walking parent from the back edge's source back up to the ancestor it points into.

Complexity

Time $O(V+E)$: each vertex is visited once (the visited guard), and each edge is examined exactly once, when its source vertex is processed. Space $O(V)$ for the recursion stack in the worst case (a graph that is one long chain), plus $O(V)$ for the visited, inStack, and (for findCycle) parent arrays.

Edge cases

• Self-loop (a node with an edge to itself): caught immediately, since the node is still inStack (it just entered) when its own edge is examined.
• Disconnected graph with a cycle only in one component: handled correctly by the outer loop restarting DFS from every unvisited node, as demonstrated above.
• Empty graph (n = 0): the outer loop never executes, hasCycle returns false immediately.
• A DAG with a shared descendant (multiple parents pointing to the same child, no actual cycle): correctly reported as no cycle, since by the time the second parent reaches the shared child, that child is visited but no longer inStack (already backtracked out of by the first parent's exploration).

Trade-offs and pitfalls

• Common mistake: forgetting to reset inStack[u] = false on backtrack. Without it, every node ever visited stays permanently marked as "on the stack," and the very next edge into any previously-visited node, cycle or not, would be misreported as a back edge.
• Common mistake: using only visited without inStack and expecting it to work for directed cycle detection; a plain visited check cannot distinguish a live ancestor from an already-finished, unrelated branch, which is exactly the diamond-shaped-DAG false positive this pattern is known to produce.
• Deep, chain-like graphs risk a stack overflow in the recursive Java implementation shown, the same risk an iterative, explicit-stack version avoids; worth naming as a follow-up concern for production code handling untrusted or very deep graphs, distinct from the correctness question this answer is scoped to.
• The findCycle reconstruction variant, returning the actual cycle path rather than a bare boolean, is a natural and common follow-up once the boolean version is understood; it changes nothing about the core traversal logic, only adds the parent/cycleStart bookkeeping needed to recover the path after detection.

Workload characteristics to replicate

• A message size distribution, not one fixed payload; use a mix matching production's actual spread, since mostly small messages with an occasional large one is a very different benchmark than one uniform size.
• Both serialize and deserialize paths measured separately, since they are often asymmetric in cost, a format can be fast to write and slow to parse, or vice versa.
• Representative field cardinality and nesting depth, since a flat struct with five fields benchmarks very differently than a deeply nested one.
• Both a cold pass, first use before any JIT (just-in-time) warm-up or cache fill (JIT is the runtime compiling or optimizing code the first time it runs, which is why a first call can be slower than later ones), and a hot, repeated pass, since protobuf and a custom packed format can behave very differently once schemas or buffers are already warmed versus on first use.
• A concurrency level matching production, since a single-threaded loop can hide allocator contention or GC pressure that only shows up when multiple threads serialize concurrently.

Measurement techniques to avoid noise

• Run explicit warm-up iterations and discard them before measuring, so JIT compilation or cache-filling is not counted as steady-state cost.
• Report a distribution, p50 and p95, not just a mean, since GC pauses or scheduler jitter create a long tail that a mean alone hides.
• Run on a quiet, dedicated machine, or at minimum pin to isolated cores and disable frequency-scaling variance, so background noise does not get misattributed to one format over another.
• Guard against dead-code elimination: an optimizing compiler can notice a serialized result is never used and simply skip the work. Consume the output, by writing it to a sink or checksumming it, to force the work to actually happen, and prefer a language's dedicated microbenchmark harness, such as Go's testing.B or Java's JMH, over a hand-rolled timing loop, since these harnesses already implement these guards correctly.
• Interleave the three implementations within the same run, alternating JSON, protobuf, custom, and repeating, rather than running each fully in sequence, so any environmental drift, like thermal throttling or a background process, is distributed evenly across all three instead of unfairly penalizing whichever ran last.

Fair and reproducible results

Run each implementation across multiple independent process runs, not just multiple iterations inside one process, since JIT and allocator warm state can silently carry information across iterations within a single process. Fix the exact input corpus, the same set of messages, across all three formats so any measured difference is purely about encoding efficiency, not about one format happening to see easier inputs. Pin library versions in the benchmark's dependency lockfile. Report both throughput, operations per second, and encoded payload size in bytes, since the fastest format is not necessarily the smallest, and which one to choose depends on which axis matters more for the actual use case, network-bound versus CPU-bound.

Direct answer

Build a correlation engine as a pipeline: ingest raw alerts, group them into candidate clusters using structural signals you already have (shared trace ID, same service-dependency edge, overlapping time window), then score each cluster's confidence that it represents ONE real incident rather than several unrelated blips, and only then hand the cluster to on-call as a single page.

Structured elaboration

Event model. Normalize every alert into a common shape before correlating anything: {source, entity (service/host), signal_type, severity, timestamp, trace_id (if present), dependency_edge (caller -> callee, if known)}. Correlation only works if every alerting system (metrics, synthetic probes, log-based alerts) lands in this shape first; otherwise you are correlating apples and oranges.

Correlation heuristics, layered cheapest-first:

1. Exact trace ID match - if two alerts share a trace ID, they are almost certainly the same incident. Free confidence, near-zero false-positive rate.
2. Time-window overlap - alerts firing within a short sliding window (say 60-120 seconds) are candidates for the same cluster. This alone is noisy (unrelated things break at the same time during, e.g., a deploy), so it is a filter, not a decision.
3. Dependency-graph adjacency - if service B calls service A, and A and B both alert within the window, that is much stronger evidence of one causal incident than two alerts on unrelated services. Maintain a live service-dependency graph (from your service mesh or a manually curated map) and check adjacency, not just co-occurrence.

Confidence scoring. Combine the heuristics into one number instead of a hard yes/no rule, because real incidents rarely satisfy every heuristic cleanly. A simple, auditable starting point is a weighted-rule score:

$\text{confidence} = w_1 \cdot \text{trace\_match} + w_2 \cdot \text{time\_overlap} + w_3 \cdot \text{dependency\_adjacency} + w_4 \cdot \text{signal\_count}$

where each term is normalized to [0, 1] and the weights are fit against a labeled set of past incidents (which alerts a human later confirmed belonged together). A logistic-regression or gradient-boosted-tree classifier (two common types of predictive model that learn a pattern from labeled historical examples rather than following fixed rules) over the same features works once you have enough labeled history; start with weighted rules because they are explainable to the on-call engineer who has to trust the page, and only move to a learned model once you can show it beats the rules on held-out incidents (past incidents deliberately kept aside and never shown to the model during training, used only to check how well it generalizes).

Human-facing output. The correlation engine should not just merge alerts silently. It should surface ONE page that says: "possible single incident, confidence 0.87, driven by: trace-ID match on 3 of 4 alerts, all within 45s, service B is a direct caller of service A" and a suggested first action if one is known (for example, "last deploy to service A was 6 minutes ago"). A page with the reasoning attached gets trusted; a page that just says "grouped 4 alerts" gets second-guessed and re-investigated from scratch, which defeats the purpose.

Integration points. The engine sits between your alert sources and your paging tool (PagerDuty/Opsgenie-style): alerts flow in, clusters flow out as a single "incident" object with a stable ID that the rest of your tooling (status page, chatops bot, postmortem generator) can reference.

Worked example

Four alerts arrive within a 90-second window: (1) checkout-service p99 latency alert, trace_id=T1; (2) checkout-service 5xx-rate alert, trace_id=T1; (3) payments-service timeout alert, trace_id=T1 (payments is a direct dependency of checkout); (4) image-cdn error-rate alert, no trace_id, unrelated dependency edge.

Correlation: alerts 1-3 share trace_id=T1 -> trace_match=1.0 for that trio. Alert 3's service (payments) is a direct callee of alert 1/2's service (checkout) -> dependency_adjacency=1.0. All three are within the 90s window -> time_overlap=1.0. With weights $w_1=0.4, w_2=0.2, w_3=0.3, w_4=0.1$ and signal_count normalized as $\min(\text{count}/3, 1)$: confidence $= 0.4(1.0) + 0.2(1.0) + 0.3(1.0) + 0.1(1.0) = 1.0$. Alerts 1-3 merge into one incident page with confidence 1.0. Alert 4 shares none of these signals with the trio (no trace match, no dependency edge to checkout or payments), so it scores near 0 against that cluster and is either its own incident or waits for more corroborating signals.

Trade-offs and pitfalls

The main trade-off is precision versus paging latency: a purely rule-based merge (trace ID only) is high-precision but misses incidents where the trace ID happens not to propagate (a common real-world gap when one hop is a legacy service that drops headers); adding time-window and dependency-graph signals catches more real incidents but increases the chance of merging two genuinely unrelated problems that happened to fire close together. Calibrate the confidence threshold against a labeled backlog of past incidents rather than guessing, and always keep a human override: on-call must be able to split a wrongly-merged incident or merge a wrongly-split one in one click, because a confident wrong merge (treating two real incidents as one) is worse than an unmerged page, since it can hide the second problem behind the first.

Direct answer

Watch the leading indicators of load, request rate, queue depth, and per-instance saturation trending up, rather than only the autoscaler's own trigger firing, which is a trailing signal by definition. Use rate-of-change and deviation-from-normal rather than a single static "you are about to scale" threshold, because the useful early warning is "load is climbing faster than usual," not "load crossed a fixed number." Keep it from paging on deploys and planned scaling by suppressing or downgrading alerts during a known deploy or scheduled scaling window, reusing the signal your CI/CD or scaling system already emits rather than inventing a second one.

How to design it

What to watch, and why each one leads the autoscaler's own trigger

• Request rate and throughput trend: rising faster than the recent baseline is the earliest signal available, before it shows up as CPU or memory pressure at all.
• Per-instance saturation, CPU, memory, queue depth: confirms rising demand is actually translating into per-instance load rather than being absorbed by existing headroom.
• Latency (p50/p95): a secondary confirming signal; rising latency alongside rising throughput suggests the current instance count is starting to struggle, not just handling more traffic comfortably.
• The autoscaler's own current-versus-desired capacity gap is a useful confirming signal that scaling is already in motion, not the early-warning signal itself; watching only this means finding out after the scaling decision is already being made.

Detecting the trend, not just a threshold

• A rate-of-change check, such as request rate up more than a set percentage over the last few minutes, catches a fast ramp earlier than a static "requests greater than N" threshold, because the ramp toward N gets flagged before it arrives.
• An anomaly or baseline-deviation approach, the same statistical shape used for any metric anomaly detection, catches an unusual trend relative to the service's own normal pattern, which matters because normal throughput varies a lot by time of day.

Keeping it from firing on deploys and planned scaling

• Suppress or downgrade to informational during a window CI/CD marks as an active deploy, sourced from the same deploy-event stream other alerts already use, rather than building a second, inconsistent suppression mechanism just for this alert.
• Treat scheduled or planned scaling events the same way: a marker the scaling system or an on-call runbook step sets before the event, checked by the alert rule.
• Require the trend to persist for a few consecutive evaluations before alerting; a rate-of-change alert with no persistence requirement is exactly as noisy as a static threshold with none.

Worked example

Consider a service whose request rate is normally close to flat within a given hour. A rate-of-change rule flags when the 5-minute request rate exceeds the previous 5-minute rate by more than 40%, sustained for two consecutive evaluations. During a genuine organic traffic ramp, such as a marketing push steadily driving up sign-ups, this fires while the autoscaler's own CPU-based trigger is still several evaluation cycles from tripping, because the request-rate signal moves before CPU saturation catches up. During a deploy, the same request-rate metric can also jump briefly, for example if a rolling restart momentarily concentrates load onto fewer healthy instances, so the rule checks the deploy-in-progress marker before evaluating and skips or downgrades if one is set, rather than trying to distinguish a good ramp from a deploy-caused one purely by magnitude.

Trade-offs and pitfalls

• A rate-of-change threshold that is too sensitive pages on normal daily ramp-up, such as the start of business hours, unless it accounts for the expected diurnal pattern rather than raw delta alone.
• Relying solely on the autoscaler's own trigger as the "early warning" defeats the purpose, since by definition it fires exactly when scaling is already happening, not before.
• Common wrong turn: suppressing all alerts globally during any deploy anywhere, instead of scoping suppression to the specific service or instance group actually being deployed.
• Common wrong turn: no persistence requirement on the trend check, so a single noisy evaluation window pages unnecessarily.

Direct answer

kubectl describe pod gives the immediate cause, OOMKilled, but distinguishing a leak from an undersized limit needs the memory trend over time. A leak climbs roughly monotonically regardless of load, while an undersized limit hits the ceiling fast and stays pinned even under light traffic.

Structured elaboration

• Confirm the reason via kubectl describe pod and check kubectl logs --previous.
• Graph RSS (Resident Set Size, the process's actual physical memory usage) over time; a third case, node-level memory pressure, shows the pod evicted despite flat usage because the node itself is starved.
• If it's node pressure, kubectl describe node shows pressure conditions and multiple unrelated pods affected together.
• Confirm a real leak by checking growth persists during low-traffic windows, ruling out "proportional to load."

Worked example

Suppose kubectl top pod (or your metrics) shows RSS grew from 100 MiB to 500 MiB over the last 10 hours, and the pod's memory limit is 512 MiB:

$\frac{500 - 100}{10} = 40 \text{ MiB/hour}, \quad \frac{512 - 100}{40} \approx 10.3 \text{ hours to OOM}$

A load-independent climb hitting the limit on that schedule regardless of traffic is the leak signature; a pod that jumps to the limit in 5 minutes and stays flat instead points at an undersized limit.

Trade-offs and pitfalls

Raising the limit "fixes" either case, which is exactly why it's a dangerous default: it delays a true leak while wasting cluster capacity, but is correct for an undersized limit. Watch the requests/limits gap for node-level competition disguised as one pod's problem.

What the interviewer probes next

How you'd use a runtime-specific heap profiler to pinpoint a confirmed leak, and how to set requests versus limits to avoid node-level pressure.

Direct answer

Influencing without authority means moving a decision using credibility, evidence, and reciprocity instead of a title. It's the same underlying competency whether the question calls it "influence" or "persuasion": build credibility before you need it, lead with the other person's problem, bring evidence or a low-cost prototype instead of an opinion, and find an ally rather than going in alone.

Structured elaboration

Core tactics:

1. Build credibility before you need it. A track record of reliable delivery makes the ask land differently than the same ask from a stranger.
2. Lead with their problem, not yours. Frame the ask around what the other person is trying to accomplish.
3. Bring evidence or a prototype, not an opinion. A small, low-cost demonstration beats an argument every time.
4. Trade, don't demand. Small, genuine reciprocity works better than a favor you feel owed.
5. Find one ally before the room. A two-person ask lands differently than a solo one.

Where this shows up. The same competency gets asked about in several shapes:

Worked example

Situation. On a platform team, a senior engineer with no authority over product prioritization noticed a shared upload flow causing repeated failures in a "quick-share" feature product wanted to ship as-is to hit a deadline.

Stakes. Shipping as-is risked a visible failure at launch, but the prioritization decision belonged to product, not engineering.

The influence moves.

• Led with credibility already in the bank: a track record of shipping reliable pieces of the same service, so the ask wasn't coming from a stranger.
• Brought evidence, not opinion: existing logs showing the retry-failure rate on the current flow.
• Built a small, low-cost prototype of just the two risky steps instead of asking for a full rewrite.
• Found an ally: a designer who had already flagged the same UX friction independently, turning a solo request into a two-person, cross-functional ask.
• Framed the pitch around product's incentive (a clean launch) rather than engineering's preference for correctness.

Resolution. Product accepted a scoped fix instead of the full reuse plan, without needing an executive to force the decision.

What a senior candidate does differently. Names the specific tactic used (evidence, prototype, ally, incentive-framing) rather than saying "I just talked to them and they agreed," and can say what they'd have done if it hadn't worked, since escalation is a last resort, not a first move.

Trade-offs and pitfalls

• Persistence is not influence. Repeating your opinion louder doesn't count.
• One tactic alone is weaker than combining them. A common weak answer only ever mentions "I built a good relationship" with nothing concrete behind it.
• Escalating too early burns the informal-influence capital that made the peer relationship work in the first place.

Direct answer

When two senior stakeholders give you contradictory direction on the same decision and both expect you to follow theirs, the right first move is not to pick a side or quietly satisfy whichever one you last spoke to, but to make the contradiction visible to both of them together and force an explicit resolution before proceeding.

Structured elaboration

1. Don't silently choose. Picking one direction without surfacing the conflict either burns the relationship with whoever you didn't follow, or produces work that gets undone when the conflict eventually surfaces anyway, at a later, more expensive point.
2. Bring the contradiction to both of them together, factually. A short message or meeting stating plainly "I've received direction X from one of you and direction Y from the other, and I need clarity on which to follow before proceeding" reframes the problem as theirs to resolve, not yours to guess at.
3. Provide the trade-off, not just the conflict. Where possible, lay out what each direction implies (cost, timeline, risk) so the conversation between them is grounded in consequences, not just preference.
4. If they can't resolve it between themselves, escalate to whoever can. A genuine stalemate between two people with equal standing over you needs a tie-breaker above both of them; naming that clearly rather than continuing to sit in the middle is the responsible move once direct resolution has been tried and failed.
5. Document the resolution. Once a direction is confirmed, write it down and share it back to both, so the same conflict doesn't quietly resurface a month later as a "misunderstanding."

Worked example

Two regional teams each push a different prioritized roadmap for the same shared platform, both expecting their preference to be honored. Rather than picking one, laying out both roadmaps side by side with their business rationale and cost of NOT doing the other, presented jointly to both regional leads, forces a real conversation about trade-offs between people who actually have standing to make that call, instead of an individual contributor guessing at organizational priorities they don't own.

Trade-offs and pitfalls

Surfacing the conflict too quickly, before doing any homework on the trade-offs, can look like you're avoiding the work of even a preliminary recommendation; where you have a well-reasoned view, offering it as input to their conversation (not as a decision you're making for them) is usually stronger than presenting a bare, unexamined conflict.

Direct answer

Maintain three running numbers per stream, a count n, the running mean, and M2 (the running sum of squared deviations from the mean-so-far), updated with Welford's one-pass recurrence; this is what keeps the variance numerically stable even after an arbitrarily long run, unlike accumulating sum(x) and sum(x*x) separately. Two such accumulators, one built independently on each machine, combine losslessly with Chan et al.'s parallel-merge formula: combine the counts, take the count-weighted mean, and add a correction term to M2 that accounts for how far apart the two machines' means were.

Structured elaboration

Why not just track sum and sum-of-squares

The textbook variance formula $\mathrm{Var}(X) = E[X^2] - (E[X])^2$ looks like a natural one-pass accumulator: keep sum_x and sum_x2, divide at the end. It is numerically unstable whenever the values share a large common offset relative to their spread (subtracting two large, nearly equal numbers loses precision, a catastrophic-cancellation problem), and the loss compounds as the stream grows. Welford's algorithm sidesteps this entirely by never squaring raw values; it only ever tracks deviations from a mean that is itself updated incrementally.

The update rule (Welford's algorithm)

For each new value $x$, with running count $n$, mean $\bar{x}$, and M2:

The sample variance is $M2 / (n - 1)$ (population variance is $M2 / n$).

Merging two accumulators (Chan, Golub, LeVeque)

Given accumulator $a$ (from one machine) and $b$ (from another), with counts $n_a, n_b$, means $\bar{x}_a, \bar{x}_b$, and $M2_a, M2_b$:

The $\delta^2 n_a n_b / n$ term is the "between-group" variance contribution: it accounts for the two machines' local means disagreeing, which the naive M2_a + M2_b alone would miss.

The exponential-moving-average variant, as a simpler special case, and where it stops being the same idea

A fixed-weight exponential moving average, $\bar{x}_t \leftarrow \bar{x}_{t-1} + \alpha (x_t - \bar{x}_{t-1})$, is the same one-pass, constant-memory update shape as Welford's mean term, specialized to a fixed decay rate $\alpha$ instead of the shrinking weight $1/n$. It is the right choice when you want to weight recent values more than old ones (e.g. tracking a metric that drifts over time) rather than a true all-time average. It does not, however, inherit the clean two-way merge above: each machine's exponential moving average encodes an implicit, ongoing recency-weighting of its own history, and there is no single count you can use to combine two such weighted means correctly, unlike Welford's exact, count-weighted merge. Combining two exponential-moving-average accumulators correctly generally requires tracking (or approximating) an effective sample size per side or aligning them by timestamped decay, a materially different problem from the exact merge above.

Worked example

class OnlineStats:
    def __init__(self):
        self.n = 0
        self.mean = 0.0
        self.M2 = 0.0

    def add(self, x):
        x = float(x)
        self.n += 1
        delta = x - self.mean
        self.mean += delta / self.n
        delta2 = x - self.mean
        self.M2 += delta * delta2

    def variance(self, ddof=1):
        if self.n <= ddof:
            return float('nan')
        return self.M2 / (self.n - ddof)

    @staticmethod
    def merge(a, b):
        if a.n == 0:
            return b
        if b.n == 0:
            return a
        out = OnlineStats()
        out.n = a.n + b.n
        delta = b.mean - a.mean
        out.mean = a.mean + delta * b.n / out.n
        out.M2 = a.M2 + b.M2 + delta * delta * a.n * b.n / out.n
        return out


import random
random.seed(7)
data = [random.gauss(10, 3) for _ in range(2000)]

whole = OnlineStats()
for x in data:
    whole.add(x)

mid = 837
left = OnlineStats()
for x in data[:mid]:
    left.add(x)
right = OnlineStats()
for x in data[mid:]:
    right.add(x)
merged = OnlineStats.merge(left, right)

print("one-pass mean:", whole.mean, "one-pass variance:", whole.variance())
print("merged mean:  ", merged.mean, "merged variance:  ", merged.variance())

This prints:

one-pass mean: 10.050413560803356 one-pass variance: 9.234143479024658
merged mean:   10.050413560803364 merged variance:   9.234143479024652

The two rows agree to within floating-point rounding (differences on the order of $10^{-15}$), confirming the merge formula reconstructs the same statistics as processing all 2000 samples in one pass.

Trade-offs & pitfalls

Complexity

add: $O(1)$ time, $O(1)$ space per call. merge: $O(1)$ time and space regardless of how many samples either side has already seen, this is the whole point of carrying only three numbers instead of the raw data.

Edge cases

• n=0: a fresh OnlineStats() has n=0; variance() returns nan since n <= ddof
  (0 <= 1); merge(a, b) treats an n=0 accumulator as the identity element
  (if a.n == 0: return b), so merging with an empty accumulator is a safe no-op that returns
  the other side unchanged.
• n=1: after one add(), n=1, mean=x, M2=0; variance() under the default
  ddof=1 still returns nan (1 <= 1), correctly reflecting that sample variance is
  undefined for a single point; population variance (ddof=0) would return 0.
• Single-element merge: merging an n=1 accumulator into another one needs no special
  case beyond the n=0 guards above; the standard Chan formula folds the single point into
  the aggregate correctly via the delta * delta * a.n * b.n / out.n cross term.
• Sample variance ($n-1$ denominator) is undefined for $n \le 1$; decide up front which convention (sample vs population) the accumulator reports and guard the edge case.
• Welford's method is far better conditioned than naive sum/sum-of-squares, but it is not infinitely immune to floating-point drift over an astronomically long run; if that matters, periodic re-basing (subtracting off a running offset) or higher-precision accumulation are options, at additional cost.
• A tempting shortcut, re-summing the whole stored history whenever precision looks suspect, defeats the entire "too large to store in full" constraint by silently reintroducing $O(n)$ memory or $O(n)$ per-update time.
• Reaching for the exponential-moving-average variant when the task actually needs the true all-time mean and variance (or an exact cross-machine merge) trades away exactness for recency-weighting you did not ask for.

Direct answer

Work outward from the guest operating system to the physical network, correlating loss timing at each
layer: mtr localizes WHERE on the path loss appears, varying-size ping separates generic loss from
MTU/fragmentation issues, and ethtool driver counters tell you whether the loss originates at the guest's
own virtual NIC (network interface card) before it ever reaches the hypervisor or physical network at all.

Diagnosis plan

1. mtr (a tool combining traceroute and continuous ping per hop): mtr -rc 100 <destination> for
   a 100-packet report showing loss percentage at every hop. Loss starting at hop 1 (the default gateway)
   points at something local to the VM or its immediate virtual network; loss appearing only mid-path
   points at the network beyond the host, not the VM itself.
2. Continuous ping with varying packet sizes: a normal-size ping (ping -s 1472, just under a common
   1500-byte MTU, maximum transmission unit, the largest frame size a link can carry) versus a stepped range
   of DF (don't-fragment) sizes at or below your OWN interface's configured MTU, for example
   for s in 1300 1350 1400 1450 1472; do ping -c 3 -M do -s $s <destination>; done. This distinguishes
   ordinary packet loss from a path MTU black hole: something downstream with a smaller MTU than your own
   interface silently dropping oversized frames instead of returning the ICMP "fragmentation needed"
   message PMTU discovery depends on (commonly because a firewall somewhere on the path blocks that ICMP
   message type). A size ABOVE your own interface's MTU with -M do is a different, useless test: the
   local kernel refuses to even transmit it, verified directly: ping -s 8000 -M do 8.8.8.8 on an
   ordinary 1500-MTU interface fails immediately with ping: local error: message too long, mtu=1500, a
   local rejection before the packet ever reaches the network, telling you nothing about the path. Only
   probe above your local MTU if the guest NIC itself is actually configured for jumbo frames (check with
   ip link show <iface> first) and you suspect the mismatch is further out.
3. ethtool -S <iface> (driver/NIC statistics): counters like rx_dropped, rx_missed_errors, or
   tx_dropped incrementing in step with observed ping loss mean the drops are happening at the guest's own
   virtual NIC or driver queue, before the packet ever leaves the VM, ruling out the physical network as the
   cause for those specific drops. ethtool -i <iface> additionally reports the driver and firmware
   version, useful for ruling out a known-buggy paravirtualized NIC driver version.
4. Guest-side counters over time: /proc/net/dev or ip -s link show <iface>, sampled at intervals and
   correlated against the timestamps of observed ping loss, to confirm the drop counters actually move at
   the same moments as the loss rather than being stale, unrelated numbers.
5. Localizing guest vs hypervisor vs physical NIC: if ethtool -S//proc/net/dev show real drops at the
   guest's virtual NIC while loss correlates with elevated st (steal time) in vmstat 1 during the same
   window, that points at the hypervisor starving the VM of CPU, delaying interrupt servicing until the
   NIC's receive ring fills and drops packets, a guest-visible symptom with a hypervisor-level root cause. If
   mtr shows loss consistently starting at the very first hop with clean local counters, escalate to
   whoever owns the physical network or hypervisor host, since the top-of-rack switch and physical NIC
   error counters aren't visible from inside the guest at all.
6. Ring buffer sizing: ethtool -g <iface> shows current versus maximum receive/transmit ring buffer
   sizes; an under-sized ring buffer under bursty traffic produces exactly the kind of intermittent,
   burst-correlated loss this question describes, and is a guest-side configuration fix, not a network
   problem.

Worked example

A VM shows 0.3% intermittent packet loss to an external service. mtr -rc 200 shows 0% loss from hop 2
onward but roughly 2% loss specifically at hop 1, the VM's own virtualized default gateway. ethtool -S eth0
shows rx_missed_errors incrementing at almost exactly the same rate as the observed ping loss, pointing at
the guest's own NIC queue, not the physical network beyond it. Correlating against vmstat 1 for the same
window shows st (steal time) spiking to around 15% during the loss bursts, meaning the hypervisor was
delaying this VM's vCPU (virtual CPU) time, which delayed servicing the NIC's interrupt queue until packets
were already dropped. The fix is a resize to an instance type or host pool with less contention, not a
network-side change at all.

Trade-offs and pitfalls

A single averaged loss percentage hides bursty loss; use mtr's interval report or timestamped continuous
ping logs so you can correlate loss bursts against other metrics (steal time, a specific process spiking)
rather than treating loss as a constant background rate. Flood-pinging (ping -f) a production path can add
enough load to cause the very loss you're trying to diagnose, keep it short and prefer an off-peak window.
ethtool -S counter names are driver-specific (a paravirtualized NIC driver names its drop counters
differently from a physical NIC driver), so always check the actual field names ethtool -S reports for the
driver in use rather than assuming a specific counter name exists. When testing for a path MTU black hole,
don't confuse a LOCAL rejection (ping: local error: message too long, printed instantly, before anything
is sent) with a genuine ON-PATH silent drop (a timeout with no response and no error): only the second one
is evidence of a real path MTU problem, the first just means you asked for a size your own interface cannot
send at all.

Standard SQL engines like PostgreSQL support exact percentiles via percentile_cont, but at very high per-service, per-day cardinality an exact sort-based percentile becomes expensive, so it's worth knowing both the exact form and a cheaper approximation.

Structured elaboration

The exact approach groups by service and day and applies an ordered-set aggregate; PostgreSQL's percentile_cont does this natively and is the right default unless proven too slow. When it IS too slow (a full sort per group, repeated across 30 days x many services), a nearest-rank window-function approach over pre-bucketed data, or a t-digest/histogram-based approximation computed incrementally at ingest time, trades a small amount of accuracy for avoiding the sort entirely.

Worked example (executed; sqlite3, nearest-rank approximation since PERCENTILE_CONT isn't in SQLite)

-- PostgreSQL exact form:
SELECT service, date_trunc('day', ts) AS day,
       percentile_cont(0.95) WITHIN GROUP (ORDER BY latency_ms) AS p95_latency_ms
FROM latency_logs
WHERE ts >= now() - interval '30 days'
GROUP BY service, date_trunc('day', ts);

-- Nearest-rank approximation (portable, verified here against a small dataset):
WITH ranked AS (
  SELECT service, date(ts) AS day, latency_ms,
         ROW_NUMBER() OVER (PARTITION BY service, date(ts) ORDER BY latency_ms) AS rn,
         COUNT(*)      OVER (PARTITION BY service, date(ts)) AS n
  FROM latency_logs
)
SELECT service, day, latency_ms AS p95_approx
FROM ranked
WHERE rn = CAST(CEIL(0.95 * n) AS INT)
ORDER BY day;

Run against a 7-row sample for one service: day 1 has 5 requests (100, 200, 300, 900, 1000 ms) and day 2 has 2 requests (120, 130 ms). For day 1, CEIL(0.95 * 5) = 5, so the nearest-rank query returns the 5th-ranked, i.e. largest, value, 1000ms; for day 2, CEIL(0.95 * 2) = 2, returning the 2nd-ranked, i.e. largest, value, 130ms. Executed directly against sqlite3, the query returned exactly (2026-07-01, 1000.0) and (2026-07-02, 130.0), confirming that for a small n the nearest-rank p95 collapses to the maximum observed value for that day, a real limitation worth flagging rather than a bug: a 5-request day simply doesn't carry enough samples for the 95th percentile to mean anything statistically different from the max.

Trade-offs and pitfalls

The nearest-rank method is exact for the DEFINITION it uses (a specific rank, no interpolation) but differs slightly from percentile_cont's linear-interpolation definition; for reporting purposes this difference is usually immaterial, but don't silently mix the two definitions across dashboards built by different teams. At true production volume (millions of rows per service-day), even the nearest-rank window-function form requires a full sort per partition; the real fix at that scale is to pre-aggregate into a histogram or t-digest at write time rather than computing any exact rank over raw rows at query time. The day-1/day-2 example above also illustrates why a p95 on a low-volume day should be treated with caution or suppressed entirely below some minimum sample-count threshold, since it degenerates to reporting the single worst observed latency rather than a genuine percentile.