What is the lookup time complexity of Consistent Hashing Design?

Question

While reading Alex Xu's book on designing large systems, I had a question about the part about consistent hashing.

The book says that in a stable hash, the server where the key will be stored is a linear search in a clockwise direction, looking for the first server it encounters.

If so, I'm wondering if there is a time complexity penalty for searching than the hashing method using modulo. (modulo means. general hashing)

Answer 1

Let's look at this diagram which depicts how the consistent hashing based lookup works.

The hash ring

• you have hash ring which represents the entire hash internal
  • the beginning and the end of the interval is interconnected
• you try to place your servers on the ring by having identical spaces between them
  • that's the initial state, whenever you add/remove a server the distances between them might not be the same (example: s4)

Lookup

• You calculate the hash for a given key
• You locate the hashed key on the hash ring
• You try to find the nearest server node by moving toward clockwise

In the above example we wanted to place key0 on to the server 0. But due to a server failure it has been removed the cluster. A new server server 4 has been added to cluster to replace server 0. Because s4 has been placed between s3 and s1 nodes that's why that's the closest server node clockwise to the k0 hash.

Time complexity

To better understand consistent hashing I highly recommend to you to read this excellent article: http://highscalability.com/blog/2023/2/22/consistent-hashing-algorithm.html

Please allow me to quote here the time complexity table for binary-search-tree

Operation	Time Complexity	Description
Add a node	O(k/n + logn)	O(k/n) for redistribution of keys O(logn) for binary search tree traversal
Remove a node	O(k/n + logn)	O(k/n) for redistribution of keys O(logn) for binary search tree traversal
Add a key	O(logn)	O(logn) for binary search tree traversal
Remove a key	O(logn)	O(logn) for binary search tree traversal

where k = total number of keys, n = total number of nodes [2, 7].