What is CONSISTENT HASHING and Where is it used?

Summary

The video script delves into the concept of consistent hashing, a technique used for load balancing in distributed systems without disrupting local data when servers are added or removed. It explains how hashing request and server IDs to a ring structure ensures a uniform distribution of requests, minimizing the impact of server changes. The script also discusses the practical challenges of server distribution and introduces the idea of virtual servers through multiple hash functions to maintain load balance and efficiency.

Takeaways

• 🔄 The core issue discussed is not about load balancing but the dynamic addition and removal of servers which affects local data distribution.
• 📐 The concept of a 'ring' is introduced where requests are hashed based on their IDs and mapped onto positions in a circular data structure.
• 🔄 Servers are assigned IDs and hashed using a function to determine their position on the ring, ensuring a uniform distribution of requests.
• 🔄 A clockwise approach is used to find the nearest server to handle a request, ensuring a simple and effective load distribution method.
• 📈 The expected load factor for each server is ideally one, meaning each server handles roughly an equal number of requests on average.
• 🔧 The addition of a new server adjusts the load by redistributing requests to the nearest clockwise server, minimizing the impact on existing servers.
• ⚠️ The loss of a server results in its requests being redistributed to the next clockwise server, which can lead to a skewed load if there are few servers.
• 🛠 To address potential load imbalances, the concept of 'virtual servers' is introduced, using multiple hash functions to create multiple points for each server on the ring.
• 🔢 By using K hash functions, each server effectively has K points on the ring, greatly reducing the likelihood of skewed load distribution.
• 💡 The choice of K, such as log(N) or log(M), can significantly mitigate the risk of load imbalance, promoting a more uniform distribution of requests.
• 🌐 Consistent hashing is a widely used technique in distributed systems such as web caches and databases, offering flexibility and efficient load balancing.

Q & A

What is the primary issue discussed in the script regarding server management?

The primary issue discussed is the problem of adding and removing servers, which changes the local data on each server, affecting load balancing.

What concept is introduced to address the problem of server data changes?

The concept of consistent hashing is introduced, which uses a ring structure to map hashed request IDs to server IDs, ensuring a more uniform load distribution.

How does the ring structure in consistent hashing work?

The ring structure maps hash values of both requests and server IDs to positions on a circular ring, allowing requests to be directed to the nearest server in a clockwise manner.

What is the significance of hashing server IDs in the consistent hashing algorithm?

Hashing server IDs allows each server to have multiple points on the ring, which helps distribute the load more evenly and minimizes the impact of adding or removing servers.

Why is it important to have a uniform load distribution among servers?

Uniform load distribution ensures that no single server is overwhelmed with requests, maintaining system performance and reliability.

What happens when a server is added in the consistent hashing model?

When a server is added, it is mapped to a point on the ring, and requests that fall between the new server's point and the next server's point are reassigned to the new server, reducing the load on the adjacent servers.

What is the impact of losing a server in the consistent hashing model?

Losing a server means that its requests are reassigned to the nearest clockwise server, which could potentially increase the load on that server, but the impact is minimized due to the distribution of points.

What is the role of virtual servers in the consistent hashing algorithm?

Virtual servers, created by using multiple hash functions for each physical server, increase the number of points on the ring and further reduce the likelihood of skewed load distribution.

Why is it recommended to use multiple hash functions for each server?

Using multiple hash functions for each server creates multiple points on the ring for each server, which helps to distribute the load more evenly and reduces the impact of server addition or removal.

How does consistent hashing provide flexibility in distributed systems?

Consistent hashing provides flexibility by allowing for efficient load balancing and easy scalability, as servers can be added or removed with minimal impact on the overall system.

What practical considerations are there for implementing consistent hashing?

Practical considerations include choosing the right number of hash functions (K), ensuring a sufficient number of servers to avoid skewed distributions, and handling edge cases where load might still become uneven.

Outlines

00:00

🔄 Consistent Hashing for Load Balancing

This paragraph introduces the concept of consistent hashing as a solution to the problem of load balancing in distributed systems. It explains that instead of using an array, a ring is used where both requests and servers are hashed to their respective positions on the ring. The load balancing is achieved by sending requests to the nearest server in a clockwise direction. The paragraph also discusses the uniform distribution of load and how adding or removing servers minimally affects the load distribution.

05:01

🔄 Impact of Server Additions and Failures

This section delves into the dynamics of server additions and failures within the consistent hashing model. It illustrates how the addition of a new server, such as SS four, redistributes the load by attracting requests from the nearest clockwise server, thus reducing the load on that server. Conversely, the failure of a server, like SS one, shifts its load to the next clockwise server, potentially leading to load imbalances if the number of servers is small. The paragraph emphasizes the importance of having a sufficient number of servers for a uniform load distribution and introduces the concept of virtual servers to mitigate the risk of skewed load.

10:01

🔄 Virtual Servers and Multiple Hash Functions

The final paragraph discusses the implementation of virtual servers to enhance the consistent hashing method. By using multiple hash functions, each server can have multiple points on the ring, significantly reducing the likelihood of load skew. The choice of the number of hash functions, such as K being log in or log M, can almost entirely eliminate the chance of load imbalance. The paragraph also explains how the removal of a server would affect the load distribution and emphasizes the efficiency and practicality of consistent hashing in various distributed systems applications, such as web caches and databases.

Keywords

💡Load balancing

Load balancing is the process of distributing network or application traffic across multiple servers to ensure no single server bears too much demand, which can lead to performance issues. In the video, it's mentioned that the actual problem isn't load balancing itself but the impact on local data when servers are added or removed. The script discusses a solution to this problem using consistent hashing.

💡Hashing

Hashing is a process that maps data of arbitrary size to fixed-size values. In the context of the video, hashing is used to distribute requests and server IDs uniformly across a 'ring' or space, ensuring a balanced distribution of load. The script explains that request IDs and server IDs are hashed to determine their positions on the ring.

💡Ring

In the script, a 'ring' refers to a conceptual circular arrangement where both requests and servers are mapped to positions using hash functions. This ring structure is integral to the consistent hashing algorithm, allowing for a uniform distribution of requests around the circle.

💡Consistent hashing

Consistent hashing is a technique used in distributed systems to minimize the redistribution of data when servers are added or removed. The video describes how consistent hashing uses a ring to map requests to the nearest server in a clockwise direction, which helps maintain load balance even with changes in the number of servers.

💡Server IDs

Server IDs are unique identifiers for each server in a distributed system. In the video, the concept of hashing server IDs is introduced to determine their position on the ring, which is crucial for the consistent hashing algorithm to work effectively.

💡Virtual servers

The term 'virtual servers' in the script refers to the idea of using multiple hash functions to create multiple points for each server on the ring. This increases the number of points and thus reduces the likelihood of a single server being overloaded with requests, improving the efficiency of load distribution.

💡Hash functions

Hash functions are algorithms that convert input data into a fixed-size hash value. In the context of the video, multiple hash functions are used to create virtual servers, mapping server IDs to multiple points on the ring and thus improving the distribution of load.

💡Skewed distributions

A skewed distribution refers to an uneven allocation of resources or tasks. The video mentions that without enough servers, the distribution of requests can become skewed, with some servers handling a disproportionate amount of load. Consistent hashing aims to minimize this skew.

💡Uniform distribution

Uniform distribution in the video refers to the ideal state where requests are evenly spread across all servers. The consistent hashing algorithm aims to achieve this by using a ring structure and hashing to ensure that the load is as evenly distributed as possible.

💡Distributed systems

Distributed systems are computer systems that consist of multiple autonomous computers that communicate and coordinate actions through the network. The video discusses how consistent hashing is used in distributed systems for tasks like web caching and databases to efficiently balance the load.

💡System design

System design in the context of the video refers to the process of designing the architecture and components of a system to meet certain requirements, such as scalability and reliability. The script highlights how system design engineers use concepts like consistent hashing to solve practical problems in distributed systems.

Highlights

The core issue is not load balancing but the dynamic addition and removal of servers, which affects local data distribution.

A ring-based hashing system is proposed, where request IDs are hashed and mapped to positions on a ring.

Servers are also hashed using the same or different hash functions, with the results mapped onto the ring.

Requests are served by the nearest server in a clockwise direction on the ring.

The load is expected to be uniformly distributed across servers due to the randomness of the hash function.

Adding a new server involves mapping it onto the ring and reassigning requests from the nearest server.

Removing a server redistributes its load to the nearest clockwise server, minimizing the impact on load distribution.

The theoretical load factor is expected to be one, but practical implementations may face skewed distributions.

Insufficient number of servers can lead to uneven load distribution, making some servers overburdened.

Virtual servers can be created using multiple hash functions to increase the number of points on the ring and reduce load skew.

Choosing the number of hash functions (K) appropriately, such as log(N), can almost entirely eliminate skewed load.

Consistent hashing is a flexible and efficient method for load balancing in distributed systems.

The method is used extensively in web caches and databases for load balancing.

The concept of consistent hashing provides a clear and efficient way for load balancing.

The addition or removal of servers results in minimal changes in the load served by each server.

The proposed system design aims to solve practical problems in distributed systems by ensuring uniform load distribution.

The transcript encourages viewers to think about solutions and engage with the content through comments and suggestions.

Transcripts

So the problem is not actually load balancing.

The problem is adding and removing servers like we saw that completely

changes the local data that we have in each server, right? And to avoid that,

we are going to be using this concept where we are still going to be hashing

all the requests according to their IDs, right?

So request ID is still there. We still hash request IDs.

So what's different? Well, what I'm drawing is a ring.

And now I want you to imagine that instead of an array,

which can map this hash function value from zero to

M minus one, this is a ring which contains the positions

0, 1, 2, 3, so on and so forth,

up to M minus one, right?

It goes all the way around and M minus one six to zero. So it's a ring of hash

fine. So of course this thing can be mapped into a point over here.

Let's say that point is over here.

So this request is pointed over here. We are going to have multiple requests.

So these are what the requests are.

Now what we can do is we can take the servers and we

actually need to send these requests to those servers.

So the servers themselves have IDs which are from

0 1, 2, 3, 4. Right? First we had just four servers.

So These are the server IDs.

What I can do is hash these server IDs also using the same

hash function, right?

Or a different hash function. It doesn't really matter.

What I want to do is then take the remainder with the search space,

which is M. So

I take the remainder with M

and as an example, if I hash zero

mod M is 30,

then let's say H of zero is 49.

MOD 30 gives you 19.

So server one will be hash deposition 19.

So let's say that is over here, right? SS one.

Similarly, let's say SS two is hashed. Here

we have SS three here

and SS four here.

Now whenever a request comes into this ring that we

have, what we do is we go clockwise.

We go clockwise and find the nearest server.

This server is going to be serving this request. That's it. Simple algorithm.

This one is gonna be sold by SS two. This one is going be served by SS three,

or rather this one is gonna be sold by S four. This by S two. This by SS three,

this by S one.

In fact it, it goes over here to S one. Okay? So S one has

Load of two requests. This has load of one,

load of one and a load of one, right?

So why is this the architecture we're choosing?

Because the hashes are uniformly random.

You can expect the distance between them to be also uniform,

in which case, because the distance is uniform, the load is uniform,

the requests are uniform of course. So they're being mapped to the right places.

So the load factor turns out to be on average,

expected one by, and

that's the smart bit. But you already had that earlier. That's not the problem.

The special thing is now if I lose a server,

let's say SS one or let, let's first add a server, in fact.

So I have a fifth server, right?

Which is mapped onto this point.

Where should I add it over here? Yeah,

this is SS four.

Then any requests which come in here

are going to be served by S four.

So initially these two requests would be served by S three,

which would have a load factor of let's say three.

But because of SS four,

these two requests find the nearest clockwise server,

which gives S four. The load factor of two and SS three comes down to one.

Now what you're seeing is that the change in each of these servers loads

is going to be much less so than what was there previously.

SS one is not affected, S four is not affected. SS two is not affected.

Only S three is affected. Okay?

Now let us say S one goes down

for some reason there was a crash. This, this thing lost its power cord.

So we lose this. And good news,

all of these requests are now going to be served by SS four

and S four is a happy guy. Not really.

The problem with this architecture is that

although theoretically the load should be one by end practically,

you can have skewed distributions over here. And why is that?

Because you know, you do not have enough servers. If you had a lot of servers,

the chance of this happening was really low.

You would have a lot of red points and it would be evenly distributed.

But you just have four now and that's why you have about half of the load on a

single server, which is terrible.

So we know how to add servers and you know,

map requests to them. We know how to remove servers and add requests to them.

We also know that theoretically it's going to be the minimum change,

But practically, how do we make this work?

And this is the place where system design actually engineers actually solve

problems, right? Take your time, try to think of a solution,

okay?

What you can do is you can start making virtual servers.

When I say virtual servers it doesn't mean that you have virtual boxes or you

start buying more servers because those are expensive.

What you can do instead is use multiple hash functions.

This is etch,

why not make it edge one for all of these guys and then have another

hash function ET two

through which you pass the server IDs and get different numbers.

So if you have K hash functions

from which you pass each, each of the server IDs,

then each server will have K points.

So let's say S three maps to two other points. One is this,

S three, one is this,

S three is right here.

SS four is mapped to this point and

to this point, and what you're effectively seeing is if K is equal to three,

then you'll have, instead of just four points, you have 12 points.

And the likelihood of one server getting a lot of the load is much,

much lesser If you choose the K value appropriately. For example, let's say

log in or log M,

you can almost entirely remove the chance of a skewed

load on one of the servers, right? So

Now if, if a server is removed,

you need to remove key points from it and clockwise assign to the nearest

servers. But in this case,

you can see that the chance of the load

being skewed is really, really low and it is efficient. So if you had a pie,

now it's more likely that you are going to just take some load from this server,

some load from this server, some load from this server,

and some load from this server, right?

The reason for that is because there are multiple points where they exist.

Multiple places are going to get removed if you remove one server and those

places will hit multiple regions.

So their loads will increase uniformly expected uniformly.

Similarly, if you add a server, again, the same thing's gonna happen.

You are going to have expected minimum change in

the numbers that they serve.

So if you're wondering where this can be used, it's used in many, many places.

Lower balancing is a concept which is used in distributed systems extensively,

right? You have this being used by web caches.

You have this being used by databases.

Consistent hashing is something that gives you flexibility and gives you load

balancing in a very, very clear and efficient way.

Alright? So you should definitely know about this and you can have a look in the

description below for relevant links.

I'll be sharing the code for this in the description below again,

and if you have any doubts, then you can leave them in the comments below.

If you have any suggestions for competitive programming or system design videos,

you can leave them in the comments below. I'll be happy to have a look at them.

Best of luck.

And this is what we want to avoid. You know, why we wanna avoid this?

Because when people are making requests to different servers,

what you don't want to happen is that if one request depends on the response

from this server, you don't want go.