This video explains consistent hashing, a method for distributing requests among servers efficiently. It describes how requests and servers are mapped onto a circular 'hash ring' and how requests are assigned to the nearest server clockwise. The video also shows how consistent hashing minimizes changes in server load when servers are added or removed, and how using virtual servers (multiple hash functions) helps prevent uneven load distribution.
Key Takeaways
1
The core problem consistent hashing solves is the complete remapping of data when servers are added or removed, which happens with traditional load balancing.
2
In consistent hashing, both requests and servers are mapped to points on a circular 'hash ring' using a hash function.
3
When a request comes in, it is assigned to the nearest server found by moving clockwise around the hash ring from the request's point.
4
Adding or removing a server with consistent hashing only affects a small portion of the requests, minimizing the overall data movement and re-assignment compared to other methods.
5
A potential issue with consistent hashing with a small number of servers is that load can become unevenly distributed among servers.
6
To prevent skewed load distribution, 'virtual servers' are used by applying multiple hash functions to each server ID, creating multiple points for each physical server on the hash ring.
7
Having multiple virtual server points for each physical server increases the likelihood of an even load distribution and minimizes the impact of server additions or removals.
8
Consistent hashing is widely used in distributed systems for load balancing, such as in web caches and databases, because of its flexibility and efficiency.
No matching segments found
0:02
So the problem is not
actually load balancing.
0:05
The problem is adding and removing
servers like we saw that completely
0:10
changes the local data that we have in
each server, right? And to avoid that,
0:15
we are going to be using this concept
where we are still going to be hashing
0:21
all the requests according
to their IDs, right?
0:25
So request ID is still there.
We still hash request IDs.
0:30
So what's different? Well,
what I'm drawing is a ring.
0:35
And now I want you to imagine
that instead of an array,
0:39
which can map this hash
function value from zero to
0:44
M minus one, this is a ring
which contains the positions
0:48
0, 1, 2, 3, so on and so forth,
0:53
up to M minus one, right?
0:56
It goes all the way around and M minus
one six to zero. So it's a ring of hash
1:02
fine. So of course this thing can
be mapped into a point over here.
1:07
Let's say that point is over here.
1:15
So this request is pointed over here.
We are going to have multiple requests.
1:22
So these are what the requests are.
1:32
Now what we can do is we
can take the servers and we
1:37
actually need to send these
requests to those servers.
1:41
So the servers themselves
have IDs which are from
1:44
0 1, 2, 3, 4. Right? First
we had just four servers.
1:49
So These are the server IDs.
1:55
What I can do is hash these
server IDs also using the same
1:59
hash function, right?
2:04
Or a different hash function.
It doesn't really matter.
2:06
What I want to do is then take the
remainder with the search space,
2:10
which is M. So
2:14
I take the remainder with M
2:18
and as an example, if I hash zero
2:24
mod M is 30,
2:27
then let's say H of zero is 49.
2:31
MOD 30 gives you 19.
2:34
So server one will be hash deposition 19.
2:39
So let's say that is
over here, right? SS one.
2:44
Similarly, let's say
SS two is hashed. Here
2:50
we have SS three here
2:54
and SS four here.
3:01
Now whenever a request
comes into this ring that we
3:06
have, what we do is we go clockwise.
3:10
We go clockwise and
find the nearest server.
3:15
This server is going to be serving this
request. That's it. Simple algorithm.
3:20
This one is gonna be sold by SS two.
This one is going be served by SS three,
3:24
or rather this one is gonna be sold by
S four. This by S two. This by SS three,
3:30
this by S one.
3:35
In fact it, it goes over here
to S one. Okay? So S one has
3:41
Load of two requests.
This has load of one,
3:46
load of one and a load of one, right?
3:49
So why is this the
architecture we're choosing?
3:53
Because the hashes are uniformly random.
3:56
You can expect the distance
between them to be also uniform,
4:01
in which case, because the distance
is uniform, the load is uniform,
4:04
the requests are uniform of course. So
they're being mapped to the right places.
4:09
So the load factor turns
out to be on average,
4:14
expected one by, and
4:19
that's the smart bit. But you already
had that earlier. That's not the problem.
4:24
The special thing is
now if I lose a server,
4:29
let's say SS one or let, let's
first add a server, in fact.
4:33
So I have a fifth server, right?
4:38
Which is mapped onto this point.
4:43
Where should I add it over here? Yeah,
4:47
this is SS four.
4:51
Then any requests which come in here
4:58
are going to be served by S four.
5:01
So initially these two requests
would be served by S three,
5:04
which would have a load
factor of let's say three.
5:09
But because of SS four,
5:10
these two requests find the
nearest clockwise server,
5:15
which gives S four. The load factor
of two and SS three comes down to one.
5:21
Now what you're seeing is that the
change in each of these servers loads
5:26
is going to be much less so
than what was there previously.
5:30
SS one is not affected, S four is
not affected. SS two is not affected.
5:35
Only S three is affected. Okay?
5:38
Now let us say S one goes down
5:42
for some reason there was a crash.
This, this thing lost its power cord.
5:47
So we lose this. And good news,
5:53
all of these requests are now
going to be served by SS four
5:58
and S four is a happy guy. Not really.
6:03
The problem with this architecture is that
6:07
although theoretically the load
should be one by end practically,
6:12
you can have skewed distributions
over here. And why is that?
6:16
Because you know, you do not have enough
servers. If you had a lot of servers,
6:21
the chance of this
happening was really low.
6:22
You would have a lot of red points
and it would be evenly distributed.
6:26
But you just have four now and that's
why you have about half of the load on a
6:30
single server, which is terrible.
6:35
So we know how to add
servers and you know,
6:40
map requests to them. We know how to
remove servers and add requests to them.
6:43
We also know that theoretically
it's going to be the minimum change,
6:49
But practically, how do we make this work?
6:52
And this is the place where system
design actually engineers actually solve
6:56
problems, right? Take your time,
try to think of a solution,
7:03
okay?
7:05
What you can do is you can
start making virtual servers.
7:10
When I say virtual servers it doesn't
mean that you have virtual boxes or you
7:15
start buying more servers
because those are expensive.
7:19
What you can do instead is
use multiple hash functions.
7:24
This is etch,
7:25
why not make it edge one for all
of these guys and then have another
7:30
hash function ET two
7:33
through which you pass the server
IDs and get different numbers.
7:38
So if you have K hash functions
7:45
from which you pass each,
each of the server IDs,
7:48
then each server will have K points.
7:50
So let's say S three maps to
two other points. One is this,
7:55
S three, one is this,
8:00
S three is right here.
8:04
SS four is mapped to this point and
8:10
to this point, and what you're effectively
seeing is if K is equal to three,
8:14
then you'll have, instead of just
four points, you have 12 points.
8:18
And the likelihood of one server
getting a lot of the load is much,
8:22
much lesser If you choose the K value
appropriately. For example, let's say
8:29
log in or log M,
8:33
you can almost entirely
remove the chance of a skewed
8:38
load on one of the servers, right? So
8:44
Now if, if a server is removed,
8:46
you need to remove key points from it
and clockwise assign to the nearest
8:51
servers. But in this case,
8:52
you can see that the chance of the load
8:57
being skewed is really, really low and
it is efficient. So if you had a pie,
9:03
now it's more likely that you are going
to just take some load from this server,
9:08
some load from this server,
some load from this server,
9:10
and some load from this server, right?
9:13
The reason for that is because there
are multiple points where they exist.
9:18
Multiple places are going to get removed
if you remove one server and those
9:22
places will hit multiple regions.
9:24
So their loads will increase
uniformly expected uniformly.
9:29
Similarly, if you add a server,
again, the same thing's gonna happen.
9:32
You are going to have
expected minimum change in
9:38
the numbers that they serve.
9:41
So if you're wondering where this can
be used, it's used in many, many places.
9:46
Lower balancing is a concept which is
used in distributed systems extensively,
9:50
right? You have this
being used by web caches.
9:53
You have this being used by databases.
9:56
Consistent hashing is something that
gives you flexibility and gives you load
10:01
balancing in a very, very
clear and efficient way.
10:06
Alright? So you should definitely know
about this and you can have a look in the
10:11
description below for relevant links.
10:14
I'll be sharing the code for this
in the description below again,
10:17
and if you have any doubts, then you
can leave them in the comments below.
10:20
If you have any suggestions
for competitive programming
or system design videos,
10:25
you can leave them in the comments below.
I'll be happy to have a look at them.
10:28
Best of luck.
10:30
And this is what we want to avoid.
You know, why we wanna avoid this?
10:33
Because when people are making
requests to different servers,
10:38
what you don't want to happen is that
if one request depends on the response
10:42
from this server, you don't want go.
Start a conversation
Ask anything about What is CONSISTENT HASHING and Where is it used?
100/100 free messages remaining
AI responses may be inaccurate. Verify important information.
What is CONSISTENT HASHING and Where is it used?
Gaurav Sen