“We used consistent hashing. Finding a key under this algorithm requires a time complexity of O(log(N)), where N represents the number of cache shards.”
What’s the log-time hashing algorithm we’re using?
Course: Grokking Modern System Design Interview for Engineers & Managers - Learn Interactively
Lesson: Evaluation of a Distributed Cache's Design - Grokking Modern System Design Interview for Engineers & Managers
Hi Issac,
The log-time complexity we’re referring to with consistent hashing generally involves a structure like a sorted list or a binary tree to maintain the list of nodes or shards in the distributed cache. The time complexity refers to accessing those shards (to find a key) instead of applying hashing on them. The hashing algorithms (whichever we use) yield an O(N) time complexity.
We’ll update the description in our content for a better understanding of the learner. Feel free to contact us for further clarification. Happy learning at Educative!
Hey @Ali_Hassan!
Thanks for clarifying, good to know about the sorted list / tree.
The hashing algorithms (whichever we use) yield an O(N) time complexity.
What’s the linear time for? I’m used to hashing taking constant time.
Hi Isaac,
In a scenario with a perfect hash function that distributes keys uniformly across the ring and a small number of nodes, finding the responsible node for a key could be achieved in O(1) (constant time)
Most consistent hashing implementations use a data structure like a balanced search tree (e.g., AVL tree) to store the positions of nodes on the ring. In this case, finding the responsible node for a key involves a binary search on the sorted node positions, resulting in an average time complexity of O(log n).
In the worst case, particularly with a poor hash function or a large number of nodes, the search for the responsible node might degenerate into a linear search, leading to a time complexity of O(n).
Thank you.