Hashing Explained in 5 minutes

in its simplest form hashing is the

process of converting an arbitrary piece

of data into fixed size values typically

an integer value the data can be a

username IP address or anything that can

be hashed or transformed into an integer

value to understand hashing further

let's take a simple example of load

balancer which is used to distribute

network traffic across multiple servers

here we have three clients C1 C2 and C3

there are three servers the clients can

talk to but instead of making them talk

directly we'll have a load balancer in

between so that client requests are

routed and evenly distributed across

servers when a load balancer redirects

or routes a request from a client to the

server it needs to have a server

selection strategy that is which request

should be served by which server one way

of server selection could be randomly

selecting the servers another approach

could be around robin wherein the load

balancer goes through each server in a

specific order maybe starting from top

server A then going to B and then C and

then going back to A like a loop however

depending upon the nature of the traffic

these strategies can be problematic

let's say each of the requests going

from the client to server takes a long

time to process by the server that is

they are computationally very expensive

request one way to deal with the request

is caching that is each server will have

some inmemory cache so instead of

computing the request every time the

server checks if the request has been

cached if it hasn't been then it

actually performs the operation

otherwise it skips the operation and

immediately returns the cache response

which it already computed for a similar

request previously

as you can imagine if your load balancer

is simply selecting the servers randomly

or following round robin there can be

lot of cash misses and unnecessary

computation let's take an example let's

say client one sends a request the load

balancer uses a roundrobin approach and

routes a request to server A the server

checks the cache and finds it empty and

performs a long operation stores the

response in cache and returns the

response to client one now if client one

sent the same request again with

roundroin approach the load balancer

routes the request to server B and since

server B never saw the request earlier

so it doesn't have the response in its

cache so basically it has to perform the

same operation even though server A

already performed the operation and has

it in it cache which is essentially a

server A cache mess by the load balancer

that is cache built by server A was not

utilized by the load balancer

we need to have a better server

selection strategy in which the same

request can be sent to the same server

every time utilizing the cache and

avoiding unnecessary

recomputations this is one of the places

where hashing can be useful we can hash

each of the client request coming to the

load balancer and based on the hash

value we can route the request according

to the position of the server so for the

sake of simplicity let's say we have a

hashing function given to us which takes

the name of each client and transforms

it to an integer value from the

definition of our hash function we know

it takes an arbitrary piece of data and

transforms into a fixed integer value so

say when we pass C1 through the hashing

function it is transformed to 11 C2 is

transformed to 12 and C3 to 13 a

simplest form of hashing strategy is to

use the modulo operator which is in fact

the percentage sign on all the hashes

and divide it by the number of servers

we have so if we do 11 modulo 3 the

result will be two that is the remainder

when you divide 11 by 3 for 12 it is

zero for 13 it's one so all requests

from C1 will now go to this server

request from C2 will go to this server

and request from C3 will go to this

server maximizing our cache hits and

minimizing unnecessary recompetition now

it's important to have hashing function

that evenly distributes requests from

each client to server like in our case

you don't want requests to be bombarded

to a single server creating a server

hotspot typically engineers don't write

their own hash function from scratch

they use industry gate hashing function

such as MD5 SSH1 and decret and so on

you can be assured that these hashing

functions provide even distribution by

default now if you're working on a large

scale distributed system there are high

chances that you would end up either

adding or removing servers depending

upon network traffic or demand so if we

add another server four and do a mod now

server 3 will never be called and we

lose even distribution of all the

request a brute force approach to avoid

this is to recomputee all the hashes and

then apply the mod but that can be

extremely expensive we need a better

solution check out my video on

consistent hashing which solve this

[Music]