Hierarchical Heartbeat Aggregation and the Cost of Intermediate Levels

A flat membership protocol makes every node responsible for every other node’s liveness, and the cost of that responsibility is quadratic in the node count. The alternative is to elect a subset of nodes to do the watching and let everyone else learn the result, which reduces the traffic to linear but changes the failure semantics: the watchers become a new class of node whose own failure is the failure of the detection system.

The quadratic term and where it bites

With n nodes each probing n-1 peers once per interval I, the message rate is n(n-1)/I probe-and-acknowledgement pairs. The constant is small and the exponent is not. At n = 100 and I = 1 second, that is about 9,900 probes per second. At n = 1000 it is about a million. At n = 10,000 it is about a hundred million, which at a hundred bytes per message is on the order of ten gigabytes per second of pure liveness traffic. No network carries that, and no node’s socket layer processes it.

Gossip-style membership already avoids the full mesh by probing one random peer per period, which makes the per-node cost constant and the aggregate linear, as described in disseminating suspicion by gossip. The problem it leaves is detection latency and per-node state: each node must hold and merge the full membership list, and the suspicion about a specific node reaches everyone only after the gossip epidemic has run. Hierarchy attacks both by making a small set of nodes responsible for a contiguous slice of the cluster and having them report upward.

The tree and its arithmetic

Arrange the nodes in a tree of fan-out f. Each node monitors its f children; the leaves are the actual cluster members. The number of internal nodes is roughly n/f + n/f^2 + ..., which is n/(f-1). With f = 10 and n = 10,000, there are about 1,111 internal monitors, and the total number of monitoring edges is about n + n/f + ... ≈ 1.11n, which is linear.

The traffic follows the edge count: each edge carries one probe and one acknowledgement per interval, so the message rate is about 2nf/((f-1)I) rather than 2n(n-1)/I. The ratio between the two is (n-1)(f-1)/f. For n = 10,000 and f = 10, that is a factor of roughly 9,000.

The cost of the tree is depth. With fan-out f and n leaves, the height is log_f n. For n = 10,000 and f = 10, the height is four. A failure at a leaf must be observed by its parent, then reported to the grandparent, and so on to the root, so the detection time is the per-level detection plus the per-level reporting delay, multiplied by the height. If each level takes one interval to detect and one to report, the root learns of a leaf failure in roughly 2·log_f n intervals, or eight intervals in this example. At a one-second interval, that is eight seconds, which is worse than the flat protocol’s one or two but still bounded and independent of n in the sense that it grows only logarithmically.

There is a design choice hidden in the constant. A parent can report a child as failed as soon as its own probe fails, which makes the root’s information one level stale per level, or it can wait for the child’s own subtree to confirm, which is more accurate and much slower. The first is the usual choice: each level makes an independent judgement and reports it, and the root’s view is the OR of the failures along each path, which means a single false positive at any level propagates to the root unchallenged.

The aggregation loses the observer

In a flat protocol every node holds its own opinion, and the opinion carries the identity of who formed it. In a tree, the root holds a summary, and the summary’s provenance is the path rather than a set of independent observers. That difference is the important one for correctness.

Consider a leaf that is reachable from its parent but not from the root, because the link between the parent and the grandparent is broken. The parent sees the leaf as healthy and reports healthy upward; the grandparent’s probe of the parent fails and it reports the parent failed. The root concludes that a subtree is gone, which is true from the root’s perspective and false from the leaf’s. A flat protocol would have produced two opinions, one from the parent saying the leaf is fine and one from the root’s own probe saying the path is broken, and the difference between those opinions is the diagnosis. The tree collapses them into one.

The consequence is that a hierarchical detector is good at answering “can the root reach this node” and bad at answering “is this node alive”. For a system whose decisions are made at the root, such as a scheduler assigning work, the first question is the right one. For a system that needs to know whether a node’s data is still being served to some clients, the second question matters, and the tree cannot answer it. Per-observer partition diagnosis is the alternative when the second question is the one being asked.

Watchers as a failure domain

The internal nodes are a new failure domain, and their failure is worse than a leaf’s. If a leaf dies, one unit of capacity is lost. If an internal monitor dies, its entire subtree becomes invisible to the root, and the root will conclude that all of those nodes are dead unless the protocol has a rule for it.

The rule has to distinguish “the monitor is dead” from “the monitor’s children are dead”. A root that probes the monitor directly learns the monitor is unreachable, but not whether the children are. The usual resolution is to promote a child to take over the monitor’s role, which requires the children to know they are siblings and to have a deterministic election rule. That rule needs a total order on identities and a way to detect that the monitor is gone, which is the same detection problem one level down. The hierarchy recurses rather than eliminating the problem.

A second resolution is redundancy: each subtree is monitored by two independent parents, and the root believes a subtree is down only when both agree. That doubles the monitoring edges and restores the independence the tree gave up, at the cost of the linear factor becoming 2n/(f-1). The two parents must be in different failure domains for the redundancy to mean anything, which is the correlation argument from correlated timeouts and detection storms applied one level up.

Choosing the fan-out

Fan-out trades per-node state for depth. A large fan-out means few internal nodes, shallow depth, and fast propagation, but each internal node holds f timers and f peer records, and its own processing load grows with f. A small fan-out means deep trees, more internal nodes, and slower propagation, but each monitor is cheap and its failure affects a smaller subtree.

The per-monitor cost is not just memory. Each monitored peer needs a timer, and timers at scale are a real expense: a monitor with ten thousand children needs an efficient timer structure, typically a heap or a timing wheel, and it must process expiry events in batches. A monitor with ten children can afford a naive scan. The fan-out that a node can handle is therefore bounded by its timer and packet processing capacity, not by the protocol’s arithmetic.

There is also a latency floor. Each level adds at least one interval of detection and one of reporting, so the depth sets the minimum detection time regardless of how fast the network is. A tree of depth four cannot detect in less than four intervals, and a flat protocol can detect in one. For a system with a tight failover budget, the tree must be shallow, which forces a large fan-out, which forces capable monitors.

When the hierarchy is the wrong shape

A hierarchy assumes the failure domains nest. Racks contain hosts, hosts contain processes, and a monitor at the rack level can see everything below it. When the network does not nest, the assumption fails: a leaf that is reachable from a different rack but not from its own parent is a case the tree cannot represent, because the tree has only one path.

Modern cluster networks are often clos topologies with multiple equal-cost paths, and the path between two nodes is not a tree edge. A hierarchy built on the physical topology then either duplicates monitors across paths, which restores the flat cost, or ignores the paths, which reintroduces the blind spot. The practical compromise is a shallow hierarchy for the common case plus a gossip plane for cross-domain suspicion, with the two views reconciled by a rule that prefers the more specific observation.