Why not just make the nodes even from the start? Place new nodes in the largest existing gap between any pair of nodes.

lsecondario 6 months ago | parent | next [-]

In a distributed system all clients would need to agree on the largest existing gap under various messaging anomalies. If you have a mechanism to reach that agreement then you can probably use a simpler deterministic load balancing algo. Consistent hashing gives you eventually consistent routing without (synchronous) agreement.

	▲	__turbobrew__ 6 months ago \| parent [-]
		You don’t need agreement. A newly added node can try best effort to find the optimal placement based upon the known state of the cluster and then advertise that it is going to a specific place in the hash ring. When clients learn about the new node they will also learn where that node has decided to put itself into the ring. No coordination is needed. There are probably moments that a client learns about the node they also atomically learn about where that nodes is placed. There are probably other issues where simultaneously added nodes may try to insert themself into the same position in the ring, you could add some jitter in the placement to compensate for this, but then I guess you are now introducing randomness which is one step closer to just having vnodes again.

▲

sfilipov 6 months ago | parent | prev | next [-]

Worth mentioning that virtual nodes also ensure that the order of servers is random. Which helps when a server is removed - the keys that need to be moved will be spread across all other servers. If we were to evenly chop up the hash ring, server B will always be after server A. And when we remove server A, all keys residing on it will need to be moved exclusively to server B.

	▲	__turbobrew__ 6 months ago \| parent [-]
		That makes sense, thank you.

▲

remram 6 months ago | parent | prev [-]

Whatever balanced configuration you make, it will become imbalanced if you add or remove a node.