hello everyone my name is Lorraine and
indecision let's learn system design for
distributed cache before we go to system
design here is a short announcement a
big shout out to warren Watts who
implemented core using java for
consistent hashing calmly sketch and
bloom filter and he's are encoding hero
you can also implement core for all my
system design or any of the algorithm
which i teach and then send the links to
me and i'm going to update those links
in the respective videos description
thank you in competition caching is
high-speed data storage system which
saves the transient data so that the
further request will not hit the main
memory or will not compute
the actual computation and all the data
will be served from the cache system and
also all the computations results will
be reused using the cache the data in
the caching system usually is stored in
faster access hardware like RAM RAM
provides you faster i/o operation so
that you can retrieve the data which is
save in the RAM faster so that the
further queries will be much faster or
reduced latency caching is used
everywhere it is used in different
layers of technology like operating
system CDN or DNS for example and also
it is being used in many applications
like for example websites social
networking websites say for example
Amazon acceptable etc and also it cash
is being heavily used in games to
improve the performance or latency for
the read and write of the media content
so caching best practices before you
cash something you need to understand
the validity of the data when you know
the validity of the data or when you
understand how long I can save this
particular data so that's when we get
high literate that means that the cache
the data was cached in the caste system
would be so from the cache otherwise it
will cause you to cache miss that means
that the data was not found in cache
which results in more query to the
actual database or operating system so
we need to properly set the TTL
that is time to leave
as I always say in all of my videos
before designing any system please take
a couple of minutes to think about all
the features or estimation you want to
if you don't know please talk to your
interviewer so for caching system here
is distribution say we want to save up
to terabytes of data in the cache
because we are trying to build a very
big cache system say for example for
amazon.com or even for google.com or
Gmail calm so what is it UPS we are
expecting anywhere from 50,000 to 1
million queries per second ok and also
what is the latest we are expecting is
up is almost about one millisecond
latency to get or set our gate output ok
and what is the eviction policy if you
want to use we let's go for LRU and I am
going to explain something new eviction
policy also so the fifth one is the
availability so we are expecting
obviously a hundred percent availability
because no one expects 50 percent or 80
percent already
we want our four servers to be up and
running all this and obviously I
mentioned that be able to design
distributed cache system that means that
it is scalable kind of scalable we need
to add more and more servers so that we
can scale the system horizontally so now
let's learn what are the different kind
of cache access patterns are there in
any application there will be a cache
and there will be memory in this case we
are considering it as dB so the first
one is right through system in this case
right through as the name mentions it is
true that means that whenever there is a
write request constant it actually goes
through the cache system and then this
write actually will also happen in the
DB and the acknowledgement of write
successful will be sent back only when
the data is completely saved in cash and
also in the DB only that's when the
acknowledgement will be sent back that
the light is successful and the second
pattern is right around in this case as
the name says this is a right around
system in which the request the write
request will be going around the cache
that means that the right right of us
will go to the main memory or the DB
in this case the BB will confirm that
the right is complete in this case the
acknowledgement will be sent back and
the data will not be sent to the cache
the data will be sent to the cache or
retrieved from the cache only when there
is a mid read request and the cache miss
happens for the first time and then the
cache will get that data back and then
sales in the cache and then it responds
and the third one is right back in this
case so in the write-back cache system
what happens is first the write update
will go to the cache and then the data
will be saved first in the cache then
the acknowledgement will be sent back
immediately and there will be one more
service which will be syncing the rights
which happen to the cache into the DB a
synchronously that means that the
service will take care of syncing the
data or updating the data which is there
in the cache to the DB so this is called
as a write back cache access pattern
when we say we have to design a caching
system which has less latency or it
should perform get or put operation
faster what is the data structure we can
use to implement the cache the
kolodziejczak of the cache so the answer
is that is hash table so as you know the
hash table is much simpler it works in a
very beautiful fashion so all we need is
we need to have a hashing function we
need a key and the value and also we
need a case in the memory and each
buckets should be numbered like this say
for example we have 10 buckets over here
so the size of this pocket is 10 ok we
have the total size is 10 consider I
want to save a value with the key taught
to value say for example value something
and the key is stopped what do we need
to do is we had to pass this car to a
hash function and we had to take that
output suppose I got the output as 53
what we need to do is we are to divide
the 53 with the total size of the bucket
and then we have to take the reminder so
that's the remainder is 3 in this case
because 53% of 10 we get 3 so
we had to go to the third bucket in the
hash table and save this key and the
value both here say will be saving Todd
and gives value over here okay and then
similarly if I want to say Hulk and its
value we have to pass this help to the
hash function we get a hash value called
71 and then we have to divide the
certainty one by ten and you have to
take the reminder okay and then that is
one where did I go to that particular
bucket and save the key and its
respective value that is Hulk in its
value and suppose take some case like we
want to say hand and man in this case if
we pass ant-man to the hash function we
get 93 when I divide this we get the
remainder three if you go to the
location there is a collision because we
have already saved our value in this
particular bucket what do we do we can
do there are different strategies to
solve that one simple strategy is
instead of saving that value directly
beep in the linked list over here okay
in here the value will be thought as a
key and its value and here the value
will be ant-man and its value so we
build the chain like that so no matter
how many collisions happen because of
hashing property we will keep on saving
those key and value respectively when
the get operation happens similarly if
you have to I will take the key and then
get a hashing divided by 10 take the
remainder come to that package and then
check in the linked list for that
particular key and value exactly for
that key and get the value and then
return back that's how fast it works and
I have already explained how the
distributed hashing works and how
hashing works in another video which I
have already posted in YouTube and the
link is available over here and also
this link I will post in the description
of this video
in that video I have already explained
how hashing works briefly and also I
have explained how we can distribute the
hash in horizontal manner or how we can
scale the hash using consistent hashing
so we had to use consistent
hashing to make this cash system
distributed so that is the reason I'm
not going to explain how to distribute
the cash or how consistent hashing works
or how hashing works descriptively
please refer to that video to understand
this so now I will directly general two
cash addiction policies how do we get
cash so when do we need to having the
cash election means basically deletion
or removing the key and value entry from
the cache memory so what do we need to
do that because cash is a lot expensive
because RAM is expensive we can't keep
on scaling that way and also we know
that not all the cleared values pays
which are saved in the cache will be
always used so we know that or we have
to somehow figure out what is the key
value pair which is Bill not used
recently or which is never used and that
is simply sitting in the memory idle so
we have to remove them so that we can
make space for the new key value pair
which the application is writing to the
cache and that is called as cash
election policy and we have to build an
algorithm around it
to make those unused or never used key
value pairs which is saved in the cache
so the best strategy is LRU LRU stands
for least recent use there are different
cash erection policies are there
something like mru or our of that and
the most algorithm which makes sense is
LRU because it says that at least
recently used that means that that
particular key value pair or the cache
entry was least recently used so if it
is not used then it doesn't make sense
to keep that in memory occupying a
particular pocket in the hash table so
Vanita Epic Touch so that other cache
entry can be saved on that bucket bucket
so the interesting problem is how do we
implement least recently used cached say
for example now we have two entries
in a hash table so let's add one more
entry say for example flash for flash
suppose we got 57 or 56 ok consider we
got 56 so when we divided by 10 the
remainder we got 6 so we have to save
flash at system bucket okay now all good
now consider we are full of memory
because we have saved even more given
value pair so now there is one more
entry coming in say for example in
Spidey
or maybe an already here so now we are
trying to save this key and some value
associated with it so consider this is
our phone ok now we want to save this
guy in somewhere so there is no space
what we need to do so we need to do
cache eviction that is we have to LRU so
we have to somehow somehow figure out
what is the least recently used key
value of the bucket so that we can
delete that bucket ok so there is a
space available something like that so
we keep on deleting the least recently
used buckets so we have enough space to
save this guy so if we don't have space
anyway there is a collision occurs
because linear probing or what having
linked list we need memory right so we
need to free up the memory in the hash
table so we need to do LRU so how do we
do that so let's take a simple approach
consider we have a say something unless
we maintain a list in which we keep on
saving the keys which are recently used
say first we accessed car so I say then
maybe our access flash so I say - say
consider we have saved this guy
somewhere here so I access so that is PI
e and then again access to car ok so
this way we can keep on saving it the
list this particular list
keep on growing it will be growing like
like crazy because we are accessing a
lot of key in value pair because as I
mentioned we are expecting about 50 K -
1 million query in the whole system for
this particular server we might be
expecting about thousands of requests
right so this list will be growing in
the weight of thousand keys added to
this so in this case if I want to figure
out what is the least recently used it
is a lot difficult because I can't do
anything with this ok
even if I can do something say if I'm
associated some date and time date a
month and year and say for example time
and minutes along with the keys even
though what I want to do is even I have
to keep on iterating with the list so it
could easily take order of n so and
since the list is already growing and we
have a lot for injuries in the list it
will take order n times and and that's
not efficient we need to have some sort
of mechanism in which we can easily
figure out in order 1 that what is the
least recently used cash so that we can
edit that particular entry so how do we
solve this problem of figuring out what
he was accessed what he was not accessed
at all or what he was least accessed so
to do that let's take something which we
know that is linked list a
bi-directional linked list so to
implement LRU so we need two data
structures one is hash table and the
other one is separate linked list which
is bi-directional so what we do is say
we haven't saved any of this let's come
in on order first one and second one and
third one okay now what a save thought
to this particular hash table so thomas
hash we got 53 and we know that bucket
12 in each set so I really what we do is
we will say the value key and value over
here right that is tar and its value so
now instead of doing that over here
let's give this a deal so before
say something over here in our
by-election latest will have to create a
first node okay and here we will save
the key and the value that is and its
value and the address to this node will
be saved over here so I'll on just mark
the size of one or maybe I'll use a
different color to mark that so mark
this as one and I'll save that over here
so whenever so this way we have
everything intact say next time I wanna
access the value in the keytar what what
happens
53 you know third bucket and address to
the linked list we go to that address
Isis the value and return it back and
still we are having the time complexity
of order one and the same thing happens
for Hulk also say for Hulk 71 we know
bucket one so next we create okay
we'll create the next node attached to
that okay so every time when we create
consider we are saving the last known
our city these say start and n addresses
okay so in this case start is this so
that is 1 and earlier the end node also
was one because we never had this okay
consider that way so now to get that
address so using the start the venoms
went here and then we created this node
and then we link it but make it by
direction and then save the value Hulk
here so consider this is the address to
and the value hug Sarki hug and its
respective value so we know that here
now we update n to 2 so all good okay
now any time if you are access this link
list we can use the start and end
addresses and we can access this data
similarly if I want to say flash 56 go
six package from oh I forgot to update
the address here right so the address to
will go here okay similarly for fire
flash where you go to cyst window or
bucket and here before doing that so now
we have to access the end okay so we
know that we come here and then we
create one more than world okay consider
this services three we update the into
three and here we will save flash and we
connect bi-directional and also value of
flash is same and then this is that you
should be updated over here so so now
I'm all good right so now anytime if we
get any key we can get the value in
order of one time say for example beyond
access hug hug
seven is the hash value we go to one
bucket one we know the address of the
north so we go directly to this
particular node and then we get the
value for associated with Hulk which is
written it back so everything is still
working the way it was supposed to work
now how this particular bi-directional
link list will help us to figure out LRU
so that's the trickiest part
so if you see over here this Lincoln is
represent the order at which these keys
were accessed say we accessed card first
second Hulk and flash third so at any
point of the time okay if I want to know
that what was accessed very early R
which was accessed recently so we know
that flash files access to police entry
and tar was accessed very first if one
want to clear something off I can easily
clear this off because this was accessed
first and this was accessed very
recently so now I can easily remove
because when and if this data was
accessed recently this diagram being in
the first of the wrist I mean from this
Android to the right side of the linked
list because it is in the left side we
know that this was the very first
element which was accessed and we can
easily clear that off okay so that way
somehow this representation is telling
us the order at which these keys were
accessed so anytime we can figure out
what was recently accessed what was
accessed what was the old and key which
was accessed so okay now consider what
happens the same keys are accessed again
and again so consider Hulk was accessed
again what happens now 71 we got a
bucket run so we know the address over
here we go to 2 so now since this is
access for now this is the latest record
which was accessed what we need to do is
we'll have to remove this guy from here
so in linkage removal is out of one
because it's bi-directional all we need
to do is we have to remove this Hulk
here okay and then link these two guys
so it is still by directional linguist
and I paint that guy which we remove to
the first of linked list ok how do we do
the first because we know the end of the
linked list from this entry
so three lately over here and then say
for example we got B I just say let us
say 2 and then we update the value same
thing is Hulk and its value over here
and now the end value is 2 so let's take
that also so now still all good now this
representation is again telling us the
order at which the keys are the data
from the cash flows axis no still I know
that this was very taxes very first and
this is the very latest record which we
axis so now if I want to clear that off
I can easily clear from the right side
left side of the linked list I can clear
this I can clear this I can rename this
alright if I have a bigger chain I can
keep on clearing it from the left side
or the starting end of the linked list
that way we know the order at which the
keys are accessed anytime when the key
is accessed
we can delete the node in the double
interest in order of 1 and we can reopen
to the right side of the bi-directional
linked list in order phone so everything
isn't is working still in constant time
the only thing is it is the linked list
is taking extra memory and that is fine
because we have to have LRU addiction
policy so this way we we know that what
are the keys we can delete what are the
keys which are least accessed so LRU is
the most used cache addiction policy
because of its simplicity and simple to
implement but the problem with that is
it just keeps record of which was the
least accessed or which was the most
recently accessed key and value pair but
it doesn't anyway count the frequency of
access or what key was accessed how many
times for that there are other
implementations which uses count biscuit
I have already made a video on continent
sketch on how we can calculate the
frequency of any given key value pair
which is coming in much faster frequency
efficiently please go and watch the
particular video to understand how we
can actually use common sketch to
calculate frequency with less memory
with less accuracy
so now how do we design the internals of
our caching system so we know we have
hash table and we know we are using RAM
we know we have LRU cache eviction
policy and everything but still we need
to have a service which accepts the
requests like get put delete requests
and then we have to you know update the
data into hash table and then we have to
read the data if there is a get request
and if there is a delete request me to
delete that since we know that we are
using RAM even though it is faster it is
kind of blocking call right so we need
to have an efficient way of serving
these requests one way we can do is we
can spawn n number of threads as and
when we get the request or we can have a
bigger thread pool which can handle that
and these things will not scale and it
will cause lot of problems
the easiest way we can handle E is
event-driven logic in which say for
example and here we will have an event
queue in which any requests I get put
are delete request will first be placed
into the event queue and then we will
have a event loop which is running which
is a single threaded operation which
will be running indefinitely and we have
a thread pool here which just takes care
of the i/o operation to the RAM what
happens when I get request output
request is enter a is requested that
particular request will be placed into
the event queue the even true on the
other hand will be keep on reading the
queue and handing over the request to
the threads which are free in the thread
pool and once it hiders to the thread it
will come back and then which reads the
next event that way the event group is
never blocked the text will do their
homework the thread which receives the
request will do the i/o operation and
gets the data and also the the human
proof would have given the callback
function and that particular thread it
will execute the callback or it
transfers the data to event so it will
execute the callback and the the
response will be sent back to the
request either through the event loop or
some of the
cancer and this is how we can handle the
requests more efficiently so now how do
we make our caching system
fault-tolerant are persistent as we know
order for cash table and the data is
saved in the bank for faster access our
faster I go operation what if our system
for some reason movie stars or something
happens and all the data in the lamp is
lost that means that our caste system is
not persistent so to make it persistent
we have to do something ok
somehow we can retrieve back all of that
data so there are two approaches to that
so first one is regular interval
snapshot so the name snapshot indicates
that we take a picture at a certain
state and keep all of the data savings
somewhere something like hard disk so
what we do is so the so there is a read
and write operation happening here on
the hash table so we'll have a service
running in the background that is a
synchro monster running in the
background so it would take a frozen
copy of the hash table and place into
the dump file and this will be saved in
the hardest okay that's one way to keep
our snapshots in the dumps file
regularly a particular interval of the
time and that's how the Vettes also does
so the second way we can do is by log
construction or sorry by log of
reconstruction so in this case what we
do is so instead of having a synchronous
service - which takes a snapshot of the
hash table and save it somewhere what we
can have is the service which retrieves
the hash table or see the key value data
from the hash table we'll keep on doing
its job and also it will be logging the
entry or the operation into one log file
so what happens is say read write say
write key and value read key and value
say delete key and bang something
like this it should we keep on entering
all the operation and the key in the
value data into a log file which is the
in harness so since it can't be part of
the synchronous requests going on make
this as a a sync call which we keep on
updating into the log file or we'll have
a some kind of over in here queue or
something which enters the log so that
the performance of the reader boy it
will not be affected and in the queue
we'll have one more service which leaves
from the queue and then update into the
buffer so what do we need this is not
file as I already said log
reconstruction if we have each and every
you know operation will be performed on
this particular hash table even though
if your machine goes down and it
restarts and come back if you have
access to this log file we can
reconstruct the whole data or the final
copy of the data which was supposed to
be there in the hash table by executing
each and every instruction in now in the
time sorted order that way we can still
recreate the hash table because we know
the operation we have the key we have
the value all in it is we had to
recreate the whole scenario in in in the
flash of time and then we fill the data
in a hash table so with these two
strategies we can think that we made our
cache system
persistent or fault tolerant so now
we'll learn how do you make our fault
tolerant or persistence now let's learn
how do we make our system available or
100% available okay
so consider in a node we have or in our
cluster we have two nodes that is known
one are several one our server two and
both have its own cache a table say we
are using consistent hashing consider
this is handling some key and value and
this handing some care value so this all
is good so the problem with this
strategy is what if this server goes
down okay now if this server is not
available all the requests which are
coming to
- will how cache miss are 21 response so
what happens is all the requests which
are coming to this supposed to go to the
server will will be go will be going to
the DB and hence the reader drives on
the DB will increase so we have to make
something to avoid this kind of problems
when the several goes down so what we
can do is we can have a replica of this
server say for example say we will say
as a replication factor - that means
that we'll have to replicate every data
into two copies same we'll have one more
server which acts as a mirror image okay
okay that is one compliment or something
okay
but this also will have one more server
so whatever the data which does that has
the same bit of in this guy also have
now the advantages of this setup is now
the load is also reduce because the
request which is going to the server one
can also be shared with the several one
compliment or the copy of sever one that
way the real requests are kind of
distributed we get the little less
latency and the performance is a lot
better but the problem is we have to
keep seeking the updates from which
happens between these two server there
is a little latency even it gets a
bright or read there is a latency for
syncing between the data between these
two servers the same happens here also
when we have network between these two
machine there can be inconsistency
whether they beat the data so that's the
problem with this solution so how do we
solve this mmm or if you can actually do
is instead of having the copy of the
server which can be used for read and
write both operation what we can simply
do is instead of making the server as a
mirror image let's make that server as
the slave simply it has a slave one
machine
this is slave to machine so in this case
also the data page and everything
in here the second servers database rice
and Asians all will be updated basically
that it is synced between this but the
recent rice always happens on the master
servers that is on these two servers and
the requests will never be touching the
slave server until this masters goes
down okay so this is one way to solve
the problem yes that's the end of system
design for distributed caching system
please go through the videos which I
mentioned in between the explanation one
is consistent hashing that exactly tells
you how to distribute the cache system
okay and the second - count means sketch
which exactly tells you how we can
actually calculate or keep track of the
frequency of access for any given key
based on that also you can devise an
algorithm which can predict which key to
be dropped or which key to be evicted
okay I have provided those links in the
description please make sure you go
through those videos and these are
really good videos so task for this
video is I know it is a lot difficult to
implement the whole caching system
instead at least try to implement the
hash table or the whole hash map
implementation and also if possible try
to implement consistent hashing and
please provide the links of your core
which is for student get about anywhere
and I'm going to update those links on
this video's description if you like
this video please subscribe tell your
friends to subscribe and also like share
and comment thank you