[NEW] Optimizing Cluster Topology Fetching with Hash Validation

[stavbsamzn]

The problem/use-case that the feature addresses
In large-scale deployments with numerous clients, repeatedly fetching the entire cluster topology can become costly, particularly when many clients perform this operation simultaneously. This results in network traffic, slower response times, and increased load on the cluster. There is no efficient way for clients to confirm if their slot-to-node mapping is still accurate, leading to clients fetching the full topology unnecessarily for minor or non-existent changes.

Description of the feature
This feature involves each node in the cluster maintaining a hash that represents the entire cluster topology. Clients can request this hash using a new command (e.g TOPOLOGY HASH) and compare it to their locally cached version. If the hashes match, no further action is needed. However, if the hashes differ, the client will request the full cluster topology via CLUSTER SLOTS or CLUSTER SHARDS.

Alternatives I've considered
Event-based Notification – This solution involves notifying clients of topology changes in real-time using RESP3 push messages or a dedicated Pub/Sub channel. When a relevant change (such as a node failure or slot migration) occurs, the cluster broadcasts an update. This approach can serve as an orthogonal solution to the hashing mechanism, providing real-time notifications of topology changes while the hash-based system focuses on validating the client’s view.
There are ongoing discussions regarding this solution, as seen in the following:

• Valkey Issue #57
• Valkey Pull Request #298

Additional information
While a new command for fetching just the hash is useful, we can further reduce complexity and save a round trip by implementing this into CLUSTER SLOTS and CLUSTER SHARDS. The commands will accept the client's current hash as input (i.e., CLUSTER SHARDS <client’s hash>). The commands would return the regular output with the new hash only if the engine’s hash differs from the client's. If the hashes match, it would return Nil, minimizing the need for redundant queries.

[madolson]

I suppose I would ship this. I would prefer the name CLUSTER HASH, which returns the topology hash. I think adding the optional CLUSTER SLOTS <HASH>, that only responds with when their is a hash mismatch is a good idea. Not as sure about shards, but would be OK adding that as well for symmetry.

I would like to see a deterministic way of computing the hash outlined, so if a client wants to they can compute it themselves.

[asafpamzn]

+1 on

I would like to see a deterministic way of computing the hash outlined, so if a client wants to they can compute it themselves.

Some more data:

1. Clients fetch the topology from several nodes and compare it in order to avoid split brain scenario. This could reduce the load on both the client side and the server side.
2. Even when caching the cluster slots, just sending the cached result can take 4ms at the server side, and more at the client side (depends on the language).

[zuiderkwast]

Ideally, clients shouldn't need to do periodic polling. We should eliminate the need for it.

If we solve #57, then clients don't need to do constant periodic updates. I think it's better to focus on #57.

To call CLUSTER SLOTS on all nodes is useful to check that the cluster has converged, but I think it should only be done when some change has happened and until the cluster has converged. When the cluster is stable, the clients should stop the periodic update.

Is there any other reason clients would do periodic polling?

[asafpamzn]

Even if we solve #57 on topology updates clients have to query multiple nodes to get the topology we cannot rely on a single node since it that case we may get to split brain scenario.

Lets take a scenario of 2000 client machines querying 5 nodes out of cluster of 50 nodes due to a MOVE error.

It is 2000*5 cluster slots calls. The client then has to compare the results to verify that there is a quorum.
A lot of work at the client side and the server side.

With this feature the client can update the topology, calculate the hash following the MOVE error and just query the cluster with the new hash. It is much more efficient from both sides. In the best case the server won't have to do anything, in case that there are more changes at the cluster the server will return 'cluster slots' from single node. In either case much more efficient.

That is, #57 and this feature are orthogonal.

Is there any other reason clients would do periodic polling?

No, AFAIK, The client is doing the periodic polling in order to identify and change at the topology, new primary, new replica, deletion of primary/replica...

[madolson]

We discussed this in the core meeting. The consensus is we would like to take a step back and have someone summarize all of the known concerns with client topology discovery and then summarize all the possible solutions. @ranshid will look into finding an owner.

[mgravell]

Random idea: rather than a true hash - just a random opaque token that is rev'd every time a particular server changes anything about the topology, taking care to avoid accidental repeats (repeat); this number means nothing and would be per server - it would not be expected to be the same between nodes on the cluster. Could even be included in info ([cluster]?) to avoid the need for a dedicated command. This could be a guid, an interlocked-counter, or just randomness. This avoids both the (albeit small) expense of computing a hash, and the (again, small) chance of hash collisions giving false negatives. It does not, however, make for a quick/convenient "do all the nodes agree about the topology" check (because the tokens are not required/expected to be consistent)

[yangbodong22011]

About periodic polling of topology, the case is like the one at redis/jedis#3595. This is the last protection.

I think push messages for the route table are not reliable, because Pub/Sub messages may be lost due to some network problems, so this can not solve this problem thoroughly.

About CLUSTER/TOPOLOGY HASH command, I try to stand client view to use it:

1. init and call cluster nodes and cluster hash
2. call set k v and meet moved.
    2.1 if return nil, do nothing.
    2.2 if not nil, update route.
3. retry set k v

I think that's OK. And do we have plan to compress route table?

[zuiderkwast]

I think push messages for the route table are not reliable, because Pub/Sub messages may be lost due to some network problems, so this can not solve this problem thoroughly.

@yangbodong22011 In a TCP connection, you can't miss some packet and still get other packets. The missing packets will be resent and appear in the correct order. If there is too much packet loss, the connection is broken and you need to reconnect. This is a discussion for #57 though.

[yangbodong22011]

I think push messages for the route table are not reliable, because Pub/Sub messages may be lost due to some network problems, so this can not solve this problem thoroughly.

@yangbodong22011 In a TCP connection, you can't miss some packet and still get other packets. The missing packets will be resent and appear in the correct order. If there is too much packet loss, the connection is broken and you need to reconnect. This is a discussion for #57 though.

Yes, I want to say if connection is broken, may be lose some sub message.

[zuiderkwast]

Yes, I want to say if connection is broken, may be lose some sub message.

Yeah, of course, after reconnect, the client needs to do CLUSTER SLOTS (or CLUSTER HASH). Messages can be lost during the time the connection was down.

[asafpamzn]

@stavbsamzn , will start to summarize the use cases and next we will create client/server spec.
@ranshid FYI