[NEW] Performance bottleneck in clusterNodeCleanupFailureReports under heavy failure load

[sungming2]

The current implementation of clusterNodeCleanupFailureReports walks the entire fail reports in the list on every invocation and performs a listDelNode() for each expired or non‑voting entry. When a cluster node has accumulated hundreds or thousands of failure reports, this function becomes a CPU hotspot.

valkey/src/cluster_legacy.c

Lines 1702 to 1721 in 3ceae81

	void clusterNodeCleanupFailureReports(clusterNode *node) {
	list *l = node->fail_reports;
	if (!listLength(l)) return;
	listNode *ln;
	listIter li;
	clusterNodeFailReport *fr;
	mstime_t maxtime = server.cluster_node_timeout * CLUSTER_FAIL_REPORT_VALIDITY_MULT;
	mstime_t now = mstime();
	listRewind(l, &li);
	while ((ln = listNext(&li)) != NULL) {
	fr = ln->value;
	if (now - fr->time > maxtime) {
	listDelNode(l, ln);
	} else if (!clusterNodeIsVotingPrimary(fr->node)) {
	listDelNode(l, ln);
	}
	}
	}

(The above result was observed during a 2,000‑node cluster failover scenario)

Current behavior:

• Where N is the number of failure reports, O(N) scan on every call, regardless of how many reports are actually expired.

Improvement ideas:

• Use a priority queue with expiration time, so expired nodes can be removed in O(RlogN) rather than scanned in full. (R is # of actually expired reports)
• Use lazy deletion instead of removing them on every call
• Use early exit when meeting quorum

[sarthakaggarwal97]

Thanks @sungming2 for filing the issue. We had seen this as one of the major bottleneck during the failure of large number of nodes.

Use a priority queue with expiration time, so expired nodes can be removed in O(RlogN) rather than scanned in full. (R is # of actually expired reports)
There will be cost associated while we are adding a bunch of nodes to the priority queue. We should account for that time as well.

Some of the other ideas from the top of my head ~

1. If there is a way to automatically evict the old failed reports, maybe using clusterCron(), that would be great. It should be O(1) when there are no failovers since the queue is empty.

2. Have we considered other data structures? Is there a way to store the failed reports in the dictionary, and maybe use the time of expiry as the key, and nodes as the values, so we can even evict the nodes in the O(K)?

It would be good to come up with a proposal so we can discuss pros / cons in the community.

[sarthakaggarwal97]

We should also consider if we need to throttle the cleanup of failure reports itself. The failed nodes reports isn't the source of truth but an indicator, so maybe we don't need to perform cleanup so frequently? The con is that we may lose up some cluster convergence time as the number of failure report is used to form consensus.

[sungming2]

@sarthakaggarwal97 Thanks for the suggestion

If there is a way to automatically evict the old failed reports, maybe using clusterCron(), that would be great

Yes, I thought about that too. It should be part of the Use lazy deletion instead of removing them on every call that I mentioned above. I think we also should be careful of not overloading cluster cron. if it tries to clean up too many entries at once, it could introduce another CPU bottleneck and delay other critical tasks.

There will be cost associated while we are adding a bunch of nodes to the priority queue. We should account for that time as well.

Yes, It is true

[sungming2]

what about this early exit method

while (ln = listNext(iterator)) {
    fr = ln.value

    if (now - fr.time > TTL) {
        listDelNode(node.fail_reports, ln)
        continue
    }

    count += 1
    if (count >= quorum) {
            // quorum reached
    }
}

In this way, we can avoid cleanup on every gossip call.
The best case: O(K) (valid, recent reports only) and early exit when quorum is met.
The worst case: O(N) (e.g., half the primaries down)

[hpatro]

@sungming2 IIUC this method doesn't deal with figuring out if we have reach quorum or not. So, I don't see how the early exit would help.

Also, what % of CPU gets spent on clusterNodeCleanupFailureReports ?

[sarthakaggarwal97]

Also, what % of CPU gets spent on clusterNodeCleanupFailureReports

We end up spending somewhere between 30-60% of the compute when a bunch of primary nodes are killed. During that time, a lot of nodes are evaluated if they are deemed to be in the fail state or not. The CPU recovers automatically once this phase is over, and all the killed nodes are marked as failed.

[sungming2]

@hpatro

This optimization allows to determine if quorum is reached without having to iterate through the entire failure report list. For example, if only 3 out of 1000 primaries are down, and the list contains 900 reports, we can send fail broadcast message as soon as the quorum condition is met. It can replace current clusterNodeFailureReportsCount and remove clusterNodeCleanupFailureReports

    count += 1
    if (count >= quorum) {
            // quorum reached
    }

To further optimize, we could introduce a cleanup task in clusterCron() to periodically prune stale reports. Keeping the list healthy would reduce unnecessary iterations and improve overall efficiency.

[hpatro]

For example, if only 3 out of 1000 primaries are down, and the list contains 900 reports, we can send fail broadcast message as soon as the quorum condition is met. It can replace current clusterNodeFailureReportsCount and remove clusterNodeCleanupFailureReports

The failure report is per node. You would be performing the cleanup at each node level. So, you're reducing the iteration count by half at the max. For your example stated above, you would need to go through atleast 501 reports for each of the node.

[sungming2]

you're reducing the iteration count by half at the max. For your example stated above, you would need to go through atleast 501 reports for each of the node.

Yes, I will think about other ways too, but doesn't it improve at least in the best case? I know its probably minor thing though

[hpatro]

you're reducing the iteration count by half at the max. For your example stated above, you would need to go through atleast 501 reports for each of the node.

Yes, I will think about other ways too, but doesn't it improve at least in the best case?

Give it a try. We would need to perform the cleanup somewhere else though so it's not completely eliminated. I would also try to think on the lines of representing this information in some other form to avoid this O(N) operation.

[sungming2]

avoid this O(N) operation.

Yes that is the ultimate goal