This blog discusses the key concepts and approaches which come in handy while scaling out the distributed storage systems. Consistent hashing is beneficial and frequently applied to solving various system-related challenges and helpful in System Design Interviews. It is also useful for alleviating the bottlenecks while designing any back-end system and scaling an application.
Before diving deep into Consistent Hashing, let’s first understand what Hashing is? Hashing is a computationally efficient way of information retrieval and helpful in enhancing the performance of various programs. In hashing, a hash function is generally used to map the information to a storage pool by generating a hash value using a well-defined logic.
For example, we can generate a random number that can map to storage by taking mod using the total number of servers. Hence, the hashing is used to map the requests to various servers and get the work done. However, this concept is valid only when the servers don’t change and memory locations are known. Distributed systems often involve changing the underlying servers to handle the requests over a network. Hence to deal with such shortcomings of distributed systems and handle the requests over a network, we need a more efficient manner of handling and organizing requests for a scalable application. This is compensated using Consistent Hashing.
Consistent hashing is an improvement over normal Hashing. Here, the user and servers are located virtually in a circular ring structure called the Hash ring. The ring is considered infinite and can accommodate any number of servers with/having no fixed allocation and assign them to random locations based on some hash function.
The traditional hashing method is very ineffective to use and handling requests over a network. This classical method assumes that we have a fixed number of servers, and all the mapping location is known beforehand. This condition is quite problematic in dealing with distributed systems where multiple users are requesting multiple servers. If in case of some servers breakdown, then to map the work to different servers, it requires a large and heavy computation that is very inefficient and affects the throughput of the service and increases the latency of the application.
In distributed systems, multiple nodes keep on interacting with each other. Suppose we have five nodes in the system and there is a sudden increase in traffic, and to deal with this, we have to add more nodes to the system. Let us say we added two more nodes which make total nodes seven. If we are using normal hashing, we have again re-compute the mapping of requests as previously we were taking hash using five nodes, but now we have seven. Similarly, in case of maintenance or failure, the number of nodes decreases, and hence we again need to re-compute the mapping, which is genuinely very inefficient.
Hence in situations when we are not sure about the number of servers that are operational at any moment, we can not go with the classical hashing method as this requires a lot of redundant computations and reshuffling of the data or requests around the cluster. Moreover, when the number of servers increases, then this approach becomes more and more inefficient as there would be more and more re-computation and re-assignment of requests to the remaining nodes. We need some dynamic way to mitigate all these shortcomings, and hence the idea of Consistent Hashing comes in.
Consistent Hashing helps us in effective organization and distribution of resources by ensuring minimum reorganization of requests or users in any failure. In Consistent Hashing, a hash function is used to map servers to locations in a virtual ring. The position of the server is just a random position obtained using the hash function. Consistent Hashing is organized in the following manner:
Hence in this manner, the keys are assigned to the server in Consistent Hashing. The beauty of Consistent Hashing comes when we add or remove servers.
When a new server is added to the application, it is mapped using the hash function and allocated to the hash ring’s desired location. After its allotment, all the keys will map on these newly added servers passing its location. This is depicted in the figure below. When server 5 is added between 1and 4, all the requests after 4 are assigned to 5 instead of mapping to 1. Hence in this way, Consistent Hashing helps reduce loads of massive servers and proves highly effective in scaling and increasing the throughput, and improves the latency of the application.
Whenever any server fails in the system, then all the keys previously mapped to the failed server will redirect to the next server, which is located after the failed server in the clockwise direction. Hence in this manner, the service remains active and provides fault-tolerant service. This is depicted in the figure below. When server 4 breakdowns, then all the keys mapped to 4 are reallocated to 1, preventing the system from breaking down.
There is a shortcoming of this approach. All the keys may get mapped to the same server, and hence one server will get all the workload, and all the other servers will remain idle. This situation is very inefficient and is very prone to failure. To deal with this, a new concept has been introduced. All the servers are replicated and arranged at different positions in the ring. In this manner, with an increased number of servers, the distribution becomes much more uniform and helps in the service’s scaling. This is depicted in the figure below. All the servers are replicated and allocated to different locations, and hence this makes the distribution of keys uniform in the hash ring.
Consistent Hashing is one of the most crucial concepts in designing distributed systems as it tackles the scalability challenges with dynamic nodes assignment and provides fault tolerance. It is also very useful in system design interviews. This concept allows the distribution of requests or data in the servers and their mapping to servers efficiently. It helps in achieving Horizontal Scaling and increases the throughput and improves the latency of the application.
If you have any ideas/queries/doubts/feedback, please write us at email@example.com. Enjoy learning, Enjoy system design, Enjoy algorithms!
At its most basic level, a rate limiter restricts the number of events a certain object (person, device, IP, etc.) can do in a given time range. A rate limiter, in general, restricts the number of requests a sender can send in a given period of time. Once the cap is reached, Rate Limiter blocks requests.
Design a tiny-URL service. Tiny-URL is a URL-shortening web service that creates shorter aliases for long URLs. Whenever the user visits the short URL, he/she will be redirected to the original URL. The goal is to design a highly scalable service that could allow users to create shorter URLs, given long URLs, and have read and write functionality.
In the common client-server architecture, multiple clients will communicate with a central server. A peer-to-peer (P2P) architecture consists of a decentralized network of peers, which are nodes that can act as both clients and servers. Without a central server's need, P2P networks distribute workload among peers, and all peers contribute and consume resources within the network.
The Publish/Subscribe pattern, sometimes known as pub/sub, is an architectural design pattern that enables publishers and subscribers to communicate with one another. In this arrangement, the publisher and subscriber rely on a message broker to send messages from the publisher to the subscribers. Messages (events) are sent out by the host (publisher) to a channel, which subscribers can join.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.