Make gossip message size configurable and deterministic

[hpatro]

Currently, a PING/PONG/MEET packet carries a subset (10%) of node information (gossip) which is relative the total number of nodes. Along with that, each packet also carries all of the nodes which have timed out i.e. in a partially failed (PFAIL) state.

There are two challenges with that:

1. Each gossip message is 106 bytes and in a large cluster setup, it could account for around 10-20KB and could consume lot of network bandwidth on each node.
2. If there are multiple PFAIL nodes observed from self view, it could also cause the increase in overall packet size and isn't bounded. This leads to indeterministic behavior and could cause high network usage/CPU utilization.

Solution:

Make the overall gossip size bounded and include PFAIL nodes within that. Provide this as a configuration cluster-node-gossip-percent to the administrator to control the rate of gossip transfer and information dissemination.

[sarthakaggarwal97]

Thanks @hpatro for filing the issue. I was also thinking on similar lines. The unbounded nature of gossip message size kind of irked me as well. Moreover, we should also experiment whether 10% of the nodes are really required in the gossip msg, or we can tune / lower that number for large scale cluster. I know it ensures that each node is gossiped to atleast 80% of the nodes in the cluster, but do we need such a high coverage.

I also feel we can prioritise PFAIL nodes for faster cluster convergence. It would be good to see how the failover times are affected in small and large clusters with this.

[zuiderkwast]

Antirez' reasoning about 1/10 is quite handwavy. I don't believe it's optimal.

With n/10 gossips per ping, a node needs to send 10 pings to include n gossips in total. In this formula, the number of pings to send (10) is constant which is nice, but the number of gossip section to include grows linearly with the cluster size (n).

Intuitively (to me) it feels like sqrt(n) is a good number of gossips.

If a node sends sqrt(n) pings to sqrt(n) nodes in a given time, it includes n gossips in total. Here the number of pings needed and the number of gossip sections both grow with the same "speed" with growing n.

This is not a complete proof but it's an idea...

[hpatro]

@sungming2 Do you want to take a stab at it?

[sungming2]

Sure

[hpatro]

If a node sends sqrt(n) pings to sqrt(n) nodes in a given time, it includes n gossips in total. Here the number of pings needed and the number of gossip sections both grow with the same "speed" with growing n.

This is quite intuitive @zuiderkwast. But the challenge is we don't want the number of direct pings to increase (dramatically) with the decrease in the gossip size. Hence, I feel making this configurable for end user would be good based on each preference. Folks could choose smaller packet size but more direct pings #1897 or bigger packet (with more gossip) but lesser direct pings.

We can tweak the default if the benchmark results are more promising with sqrt(n). Might be an independent task.

[sungming2]

I think this is a good idea, but even if we make it configurable, how would users determine the optimal percentage based on the number of nodes/configs? And what the best practice should be to validate or test that it actually improves their scenario?

[hpatro]

I think this is a good idea, but even if we make it configurable, how would users determine the optimal percentage based on the number of nodes/configs? And what the best practice should be to validate or test that it actually improves their scenario?

We should get the value of (No. of message * individual message size * number of nodes)/sec mathematically for O(N/10) / O(sqrt(N)) / O(log(N)) or run the experiments and get the results.

[zuiderkwast]

I think the configs ideally should control more high-level concepts that don't require too deep knowledge in the cluster algorithms.

Node timeout already controls failure detection, how long a node needs to be down to be considered failing.

This new config would control the balance between cluster bus traffic vs the precision for timely failure detection? Is this right?

If we add a config like this to reduce traffic, we can still tune the balance between ping frequency and gossip size to make it more optimal. We should reason about what it implies for failure detection time and propagation.

We could also think about primaries vs replicas. It seems more important to detect failing primaries quickly than failing replicas, to me.. (Sorry, different topic.)