Facebook Memcache - The Need For Speed | Distributed Systems Deep Dives With Ex-Google SWE

0:00 hello everyone and welcome back to the

0:03 channel for those of you who are

0:04 watching last uh week's video as well

0:07 unfortunately I did not get the job

0:09 offer to be a backend developer from my

0:11 girlfriend uh she told me that uh she's

0:13 on a bit of a hiring freeze at the

0:15 moment and then proceeded to give me two

0:16 lead code hards in 30 minutes which I

0:19 was not able to do uh nonetheless here

0:22 we are uh keeping my head high for this

0:24 week's video which is about cashing at

0:26 Facebook so let's go ahead and get into

0:28 it all righty as per usual we're going

0:30 to go ahead and freeball this one

0:32 because I simply do not remember what

0:34 I've written down on the page but uh I

0:37 think I'm just going to make it up as we

0:39 go so today we are talking about the

0:41 mcash paper which is out of Facebook in

0:43 2013 so it's worth noting that I

0:46 actually made a video on taao uh which

0:48 is a different Facebook paper on this

0:49 channel and the two of these papers in

0:51 many ways share a lot of similarities

0:53 toao is ultimately Facebook's graph

0:55 database that does a ton of caching and

0:57 memcache is basically just a separate

0:59 individual caching layer and they share

1:01 a lot in common to tries to build upon

1:03 the mcash work and improve upon it uh

1:05 but this ultimately lays the foundation

1:07 for that one so if you haven't seen the

1:08 to video that would be a solid followup

1:10 to this one anyways let's go ahead and

1:12 get into the background of this paper

1:15 basically the paper name is mem cach

1:17 there's also this technology called M

1:19 cached which is basically an open-

1:21 Source single server cache right so it's

1:23 basically just running a hashmap on a

1:25 server and uh you know entries can get

1:27 expired over time so basically the

1:29 reason that Facebook needs these is

1:31 because when you're loading a Facebook

1:32 page they may end up making 500

1:34 different API requests to a bunch of

1:36 different servers and loading results

1:37 from all these places and this level of

1:39 fan out is not really acceptable to go

1:41 to normal databases so ideally you want

1:44 to be keeping a bunch of data in memory

1:45 or at least as much as possible

1:47 especially for popular results so you

1:48 can get data back as fast as possible

1:50 it's also good because if you just have

1:52 a bunch of servers hitting a bunch of

1:53 databases at the same time you're going

1:55 to be putting too much stress on them

1:57 and they can go down so again in the

1:58 same way cash because they can handle

2:00 all these requests much faster are

2:02 basically shielding databases from the

2:04 load of the

2:05 system what's also really nice about a

2:07 caching layer is that you've got a bunch

2:09 of different heterogenous data sources

2:12 right so they may have databases they

2:13 may be reading from Hadoop and being

2:15 able to just have one unified cache

2:17 layer as opposed to coupling it with

2:19 each of those database storage tiers is

2:21 that you know it can work with any

2:23 particular storage system uh that's you

2:25 know keeping data on disk and then it

2:26 can store things separately or it can

2:28 even store things that aren't necessary

2:30 even being cached it could be storing

2:31 the result of some batch computation or

2:33 something like that so again the really

2:35 nice thing about this is that we get

2:37 this separate scaling piece right like

2:39 it's not tied to the number of database

2:40 servers I have it's more so tied to the

2:42 actual read loadad of the system

2:45 obviously keeping things in memory is

2:46 going to increase our read speeds and

2:48 then of course uh like I mentioned we're

2:50 shielding our storage tier so again uh

2:53 what they call their system here is just

2:55 memcache right so mem cach is a single

2:57 server and then when they say mem cach

2:59 in the paper it's referring to the

3:00 distributed system that they

3:02 built all right so at a very very high

3:06 level basically what we're doing here is

3:08 just a bunch of look aside caching right

3:10 so we've got all these clients so even

3:12 though I draw it as a person in reality

3:13 it's probably just some sort of

3:14 application server and the application

3:17 server is going to make a read from some

3:19 cache ideally you get a cash hit but if

3:21 you don't and we miss then okay we're

3:23 going to go ahead and read from the

3:24 database and uh once we get that data

3:27 from the database the client itself is

3:28 actually responsible for for setting the

3:30 key in the cache so we're going to

3:31 discuss some complications that arise

3:33 from that in a little bit uh same idea

3:35 here except a little bit different on

3:37 rights is that if we're a client which

3:39 again not a person really just an

3:41 application backend server uh ideally

3:44 we're going to go ahead and set some key

3:45 in a mySQL database and then the

3:48 database itself is going to go ahead and

3:50 invalidate the cache we'll talk about

3:52 why the database is doing that uh you

3:54 know it's there's a reason for it as

3:56 opposed to the client because in theory

3:57 the client could do the invalidation and

3:59 that's how they draw at the beginning of

4:00 the paper but then ultimately it turns

4:02 out it's the DB that does it another

4:04 question is okay rather than

4:05 invalidating the cach why don't we just

4:07 actually set the value of the key itself

4:10 well we could do that but what if two

4:12 clients were writing at the same

4:14 time and you know now you have some sort

4:16 of race condition between who is uh

4:19 actually going to be setting the value

4:21 and the cash at the same time you you

4:22 can have flip-flops here and then you

4:24 get the wrong result so invalidating is

4:26 typically easier and then uh the value

4:28 gets set on the read path

4:32 okay so like I mentioned we've got this

4:33 concept of a fan out pattern right so if

4:36 I'm an application server I literally

4:38 might reading might be reading from 500

4:41 uh memcached instances at once and that

4:43 means that we have a lot of fan out of

4:45 these Network requests so a few problems

4:47 of this is is that if one server is

4:49 super duper slow uh that's going to

4:50 bottleneck everyone from performing page

4:52 reads which is going to be problematic

4:54 there's also this concept of incast

4:56 congestion which is an interesting one

4:57 it's not a term that I've heard before

4:59 this is basically like if you've got

5:00 some network switch right in a Data

5:02 Center and then maybe it's connected to

5:04 all of these different mcash servers if

5:06 there are too many packets going into

5:08 the net uh network switch at a time uh

5:10 things may get dropped uh or things may

5:12 get slow and that's going to be

5:13 problematic as well and then finally if

5:17 I am basically you know a web server

5:19 right here and I've got a bunch of

5:21 different cache servers over down here

5:24 now I may have to be maintaining a

5:26 connection to each cache server and not

5:28 only am I doing that but may be having

5:30 to maintain a connection to each cach

5:31 server on every sle uh on every single

5:33 thread on this web server so if there

5:35 were 100 of these now I all of a sudden

5:37 I have 300 connections and we don't want

5:38 to maintain

5:40 those okay so how are we going to

5:42 improve those issues well first let's

5:44 talk about the high level overview of

5:46 memcache basically we've got a bunch of

5:48 caches and we're splitting them up with

5:49 consistent hashing and then we've got

5:51 this fan out pattern right here because

5:53 everyone's pretty much reading from

5:54 every cache as it's relevant to them so

5:56 note that uh this is kind of acting as

5:58 if we're doing key ranging in reality

6:00 this is going to be the range of the

6:02 hash of keys that's how consistent

6:03 hashing is going to work so these would

6:04 be our web servers or our clients and

6:06 these are going to be the

6:08 caches okay we're going to now get into

6:10 a few performance optimizations this is

6:12 where things are going to get a little

6:13 bit deeper and we're going to try and

6:15 solve some of the problems that we

6:16 mentioned before basically for one if

6:18 all of these web servers are fetching

6:20 results from every single one of these

6:21 caches and they're fetching a lot of

6:23 keys at a time ideally we want to batch

6:26 as many requests as we can at a time to

6:28 limit the actual overhead of sending all

6:30 these requests to cash instances so not

6:32 only should we be fetching these keys in

6:34 batch but we should also be doing so in

6:35 parallel right it would be stupid if we

6:37 went to one cach got all the data then

6:39 went to another cach got all the data

6:40 then went to another one we should be

6:42 doing that in

6:43 parallel another thing that I mentioned

6:45 was kind of the the threading issue

6:46 right if you have 100 threads running on

6:48 a server you don't want to have a 100

6:50 times the number of cache servers open

6:52 connections that would really bog down

6:54 the server so instead each one of those

6:56 client uh servers is going to be running

6:58 a single MC router process where the MC

7:01 router process is the only one that's

7:02 responsible for connecting to mcash

7:04 instances or separately another option

7:07 is you could be running MC router uh

7:09 that process embedded on some sort of

7:10 proxy server and then that way rather

7:12 than maintaining a connection to every

7:14 single mcash server you just maintain

7:16 one connection to the proxy so that's

7:18 possible as well finally uh for reads

7:22 they actually end up using UDP as

7:24 opposed to TCP which is an interesting

7:26 one uh the reason they do that is

7:28 because you know UDP is is just going to

7:30 have less information embedded in each

7:32 packet and also you don't necessarily

7:33 have to establish uh a handshake to uh

7:36 get data from a server you just go ahead

7:38 and uh send a packet over there and so

7:41 UDP uh is nice performance- wise but it

7:44 also has some complications associated

7:46 with it which is that you can have

7:47 dropped packets right there's not really

7:49 an automatic retry mechanism or packets

7:51 can even come out of order and so if

7:54 that does happen basically how the

7:55 client treats this is hey you know I

7:57 just had a cash miss that being said

8:00 uh one of the reasons that you may see

8:01 things like Drop packets or out of order

8:03 packets is because the server that

8:05 you're trying to hit or the cach that

8:06 you're trying to hit uh is overloaded

8:09 and you know is not in a good state

8:10 right now so there's extra logic

8:12 basically that if you know you dropped

8:13 packets and that's why you had a cash

8:15 Miss and then you do a read to the

8:16 database don't actually try and backfill

8:19 that value in the cache uh just avoid

8:21 that

8:21 altogether that being said for uh set

8:24 and delete operations right because we

8:26 invalidate keys in the cache and we also

8:28 set a key in a cach after we read from

8:30 the database we actually do that with

8:31 TCP the reason being that we want some

8:34 sort of Auto retry mechanism in theory

8:36 you could just do that on top of UC UDP

8:38 but there's not really any good reason

8:39 to do so so this is going to be nice for

8:41 retrying our failed operations and then

8:44 finally uh we're actually going to be

8:46 performing some amount of flow control

8:49 so we do flow control in TCP as well but

8:52 uh TCP flow control is based on

8:54 basically the capacity of one connection

8:56 right so the way flow control generally

8:58 works is you have some window you're

9:00 basically saying here are all my open

9:02 connections or or sorry my open requests

9:04 oh my request just got a

9:06 response now I only have three open

9:08 requests so I can actually you know get

9:10 another one in there because maybe my

9:11 limit is four so same concept uh and

9:14 we're doing this in the MC router but

9:16 rather than doing this at the level of

9:18 you know sending requests to one single

9:20 mcash instance we do it for all

9:22 cumulative requests to mcash instances

9:25 because we have so much fan out that uh

9:27 ideally you want all of the clients and

9:29 Shing that they're not sending too many

9:30 requests all over the place so that's a

9:32 really nice thing to do and you just do

9:34 that using a sliding window finally like

9:36 TCP this is kind of doing an additive

9:38 increase and multiplicative decrease so

9:40 as you continue to get successful

9:42 requests you can very slowly increase

9:44 the size of that sliding window and then

9:46 if for whatever reason you drop packets

9:48 or a request doesn't get a response to

9:49 it you very quickly decrease the size of

9:52 that sliding window and that's to make

9:53 sure that we don't overload our cach

9:57 Fleet okay so now I'm going to describe

9:59 a couple of problems that also come up

10:01 in a system like this and then we're

10:02 going to talk about how we actually

10:03 solve them so the first is called a

10:06 stale set so it's a pretty simple system

10:08 basically the idea here is okay let's

10:10 say I've got one client on the left

10:13 who's a reader and one client on the

10:15 right who is a writer basically the

10:17 reader is going to attempt to read from

10:19 the cache maybe the value is not there

10:20 for whatever reason so we have a cache

10:22 Miss and we know that when we have a

10:23 cash Miss we go to the database we read

10:25 from the database and then we backfill

10:27 the value into the cache how however as

10:30 we're reading from the database the

10:31 writing client is actually going to set

10:33 a new value from that key which as we

10:35 know leads to invalidating the value of

10:37 that key in the cache so that's over

10:39 here in step four this is a race

10:41 condition right so finally in step five

10:43 the client who's doing the read actually

10:45 sets the old value of the key X into the

10:48 cache and now all of a sudden we're

10:50 reading stale data right so that's a

10:52 race condition we don't want that

10:54 happening the other thing that could

10:55 possibly happen here is this concept of

10:57 a Thundering Herd where basically we end

10:59 up getting a bunch of additional load on

11:00 a database where we shouldn't so in this

11:03 scenario basically we've got a writing

11:05 client over here and then we've got a

11:07 bunch of guys on the left who are doing

11:09 reading and basically the writer is

11:11 going to make a write which as we know

11:13 is going to invalidate the key in the

11:15 cach and then from there we've got a

11:17 bunch of readers who concurrently at the

11:20 same time are all going to read from the

11:22 cach and because they're all reading at

11:24 the same time the cash has not actually

11:26 gotten a value filled in yet for it and

11:28 so now all of those requests are going

11:30 to be cach misses and then they're all

11:32 going to go over here to the database

11:34 and this is particularly going to be a

11:35 problem with popular keys so because all

11:38 these readers are reading currently all

11:40 of a sudden our database gets a bunch of

11:41 extra load that can cause it to fail and

11:43 then we may even have cascading failures

11:45 just due to you know rebalancing or

11:47 something like that so you want to avoid

11:49 both of these problems so the mechanism

11:51 that we use in mcash to do so is

11:53 something known as a lease so a lease

11:56 very simply put is basically like a

11:58 compare and set and the cash is going to

12:00 return it but let's go ahead and

12:02 describe it so again over here we've got

12:04 one

12:06 reader uh over here we've got another

12:10 reader and over here we've got a writer

12:14 so let's imagine to start the leaste

12:17 token is ABC right so the the reason the

12:20 leaste token is ABC is because this

12:22 reader comes in it does a cash Miss and

12:24 so now right after the cash Miss happens

12:27 the cash says okay for the key that you

12:28 car about I'm setting a token called ABC

12:32 so that's going to be our lease right

12:33 there and we're going to return ABC back

12:36 to the

12:37 reader now another couple of nice things

12:39 happen as a result of this let's imagine

12:41 that because this was a cash Miss

12:43 there's no value currently in the cash

12:45 right so it's possible that we may have

12:46 one of those Thundering Herd scenarios

12:48 where another reader also comes in and

12:50 tries to read the same key and it's not

12:52 present so normally this would result in

12:55 a read to the database right or rather

12:57 sorry not like that but a read from this

12:59 guy to the database and we don't want

13:01 that happening we want them to

13:02 eventually just read the value from the

13:04 cache so if they read from the cach and

13:06 they see that there's an active token

13:07 for this key what they're actually going

13:09 to do is just go ahead and wait a couple

13:11 of seconds now this is completely

13:13 imperfect right because normally you

13:14 don't want to rely on like exponential

13:16 back off or anything but in practice it

13:18 actually works very nicely basically if

13:20 you wait a half second you know what's

13:22 probably going to happen is this reader

13:23 over here is going to go fetch a value

13:25 from the database and ultimately place

13:27 it in there so that works a lot of the

13:29 time which is really really nice so

13:32 that's one aspect of Bel is basically

13:35 preventing others from reading at the

13:36 same time as you from the database thus

13:38 preventing thundering herds but another

13:40 really nice aspect of it is also

13:42 preventing stateful sets because as we

13:44 mentioned what could happen is this

13:46 reader could actually go ahead and read

13:49 and try and you know set the value over

13:52 here after that key has already been

13:54 invalidated because in step five we have

13:56 a writer the writer is going to write to

13:58 the database in step six we invalidate

14:01 the key in the database which at the

14:03 same time is going to say ooh there was

14:04 a token ABC here let's go ahead and

14:07 remove it that's no longer valid the

14:09 reason why we remove it is because when

14:12 this reader ultimately reads from the

14:13 database a stale value and tries and

14:16 come in and say hey I'm using token ABC

14:19 to set a new value the cash is going to

14:21 say oh wait a second uh token ABC is no

14:24 longer valid because I've had my key

14:26 since invalidated and so I no longer am

14:28 going to except you're right so this way

14:30 this guy can go ahead and retry over

14:32 here uh you know he can do another cache

14:35 Miss and then go to the database and

14:37 then you know fill in the proper value

14:42 accordingly great another concept that

14:44 we have is going to be that of mcash

14:47 pools so basically um empirically after

14:50 you know running these mcash instances

14:52 for a while the developers at Facebook

14:54 found that data has different properties

14:56 right so uh keys and values can have

14:58 different sizes uh they can have

15:00 different churn where churn basically is

15:02 implying how often things are being like

15:03 evicted from the cash or are no longer

15:05 relevant or they can have different

15:07 access rates certain data is being

15:08 accessed really frequently certain data

15:10 is being accessed very infrequently and

15:13 so ideally what you want to do is store

15:15 data in the same mcash pool which is

15:17 basically just a set of mcash servers

15:19 that have similar properties because if

15:21 you don't you can have certain bad

15:22 scenarios that come about from different

15:24 access patterns so one example that they

15:27 gave was this concept of low turn keys

15:29 right so a low turn key is one that's

15:31 rarely being evicted from the cash or in

15:33 theory shouldn't be evicted from the

15:35 cash because you know it's always being

15:36 asked for but sometimes if it's paired

15:39 with a bunch of keys that are briefly

15:41 very very popular uh so for example you

15:44 know like a recent post or something but

15:46 you know very quickly will become

15:48 unpopular it's possible that if we run

15:49 out of space in the cache because the

15:51 high churn keys were very recently being

15:53 accessed a lot uh the low turn ones may

15:56 get replaced by the lru policy and then

15:58 all of a sudden we've got a bunch of

15:59 high churn keys in the cach and they're

16:01 no longer being accessed anymore anyway

16:03 so that would be wasteful so separating

16:05 these guys into different mcash pools

16:07 can have nice properties as

16:09 well sorry I'm noticing that sometimes

16:11 when I do like a little PowerPoint thing

16:14 it uh it gets messed up a little bit so

16:15 I just want ahead and fix that but the

16:17 idea here now is that in addition to

16:20 having a bunch of different pools we may

16:22 also perform some cach replication that

16:24 being said normally in mcash we try and

16:27 rely only on using partitioning to

16:29 partition the data set that being said

16:31 we'll also do replication in certain uh

16:34 unique scenarios so one scenario that uh

16:36 will do partitioning for or sorry

16:38 replication for is basically when we

16:40 have a very very small key set that's

16:42 very frequently accessed right so let's

16:44 say we've got 100 keys in our key set

16:47 and you know fairly small values such

16:49 that the entire thing can live on a

16:50 single node but it's just a super

16:52 popular key set and so you've maybe got

16:54 hundreds or thousands of client servers

16:56 that are reaching out to it all the time

16:58 in this case there's going to be a ton

16:59 of load on that server and it would be

17:01 great if we could go ahead and

17:03 distribute that a bit in theory you

17:04 could partition the key set but the

17:06 requests themselves individually are not

17:08 very expensive it's more so that there

17:10 are just a lot of them so partitioning

17:11 it is not really going to make a big

17:13 difference because the actual overhead

17:15 of returning the data was never that big

17:16 in the first place so instead what

17:18 you're better off doing is literally

17:20 just setting up a replica of the same

17:21 data set and now each of them are going

17:23 to have half the number of requests

17:25 which is going to be a lot better it's

17:27 worth noting that if it comes to

17:29 choosing replicas clients are basically

17:30 just going to randomly load balance

17:32 based on their own IP

17:35 address another concept that we have in

17:37 mcash is going to be this idea of gutter

17:39 servers so typically in the past with a

17:42 lot of the distributed systems that

17:43 we're talking about if servers go down

17:46 what we'll try and do is generally

17:47 rebalance the keys between them right

17:49 which is something that is not exactly

17:51 trivial uh but ultimately if it's

17:53 something like a database you have no

17:55 choice right the data's got to live

17:56 somewhere but the nice thing about this

17:58 stuff is that at the end of the day it's

17:59 cash data and so it doesn't have to be

18:01 perfect when you rebalance

18:04 basically rehashing or rebalancing is

18:06 also going to be very hard because

18:08 certain keys can be considered hot right

18:10 so if there's 10 keys that get a ton of

18:12 load right maybe up to 20% of the load

18:15 of a single server is the value that

18:16 they use in the paper actually taking

18:19 that key and then just putting it on a

18:20 random new server can cause that server

18:22 to get overloaded crash and now you have

18:23 cascading failures so instead they have

18:26 this concept of gutter servers where a

18:28 gutter server like this one over here or

18:30 gutter servers in general are only

18:32 responsible for like 1% of the servers

18:34 in the total cluster but basically if

18:36 this guy goes down over here what we'll

18:38 first try and do is make a request to it

18:40 and if that fails we'll go ahead and

18:42 request to see if the value exists in a

18:44 gutter server and you know if it doesn't

18:46 obviously we're going to pull it in from

18:47 some sort of

18:49 database so in this way you know any

18:52 other client is going to do the same

18:53 exact thing right it's going to make

18:54 that same request and then it's going to

18:56 Hash that request to the same gutter

18:57 server in the gutter pool so ideally

19:00 you'll still be able to get that key and

19:01 it's going to resolve a lot of the cash

19:02 misses that would have happened

19:04 otherwise and save a lot of load from

19:05 our database it's also worth noting that

19:08 you know the database doesn't

19:10 necessarily know that this gutter server

19:12 actually has cache data on it or it

19:14 doesn't know where the cash data for the

19:15 keys actually lives because now we've

19:17 kind of broken our consistent hashing

19:18 policy and so as a result of that uh we

19:22 basically want the data on gutter

19:23 servers to expire fairly quickly and so

19:25 we do you know it's fairly shortlived

19:27 and it'll basically Auto

19:30 expire cool let's go ahead and talk

19:33 about this concept of regions and

19:35 clusters because these are two keywords

19:36 that we're going to need to get through

19:37 the rest of this paper number one is a

19:40 cluster so this is basically just a

19:42 combination of mcash servers also a

19:44 bunch of client servers ideally

19:46 collocated in the same data center so

19:48 probably going to be the same failure

19:49 domains as well in terms of power and

19:51 network or stuff like that then you also

19:53 have a bunch of regions where a region

19:55 is comp uh comprised of multiple

19:57 clusters as well as probably one shared

20:00 storage layer where geographically

20:02 they're in a similar location so still

20:03 fairly close to one another but still

20:05 different failure domains right so

20:06 different uh probably different physical

20:08 buildings or different network racks or

20:09 something like that and then there's

20:11 also this concept of a regional pool

20:14 because at the end of the day within

20:16 different clusters right you're

20:18 effectively replicating the cache data

20:20 because you have different clients using

20:21 different clusters a regional pool is

20:24 basically you have different clients

20:26 except they're all using uh MC servers

20:28 that span multiple uh you know like data

20:31 centers or something like that and so

20:33 because you know consistent hashing is

20:34 going to deterministically place a key

20:36 on one server what this means is that

20:38 we're doing less uh redundant

20:40 replication of the data uh basically the

20:42 cost of this is that even though we're

20:44 doing less redundant replication of data

20:46 um effectively we now have to actually

20:48 make requests from client servers in one

20:51 cluster to mcash servers in a different

20:53 Data Center building and so that's going

20:55 to incur some extra

20:57 latency okay next we've got this concept

21:00 of data

21:01 invalidations so up till this point I've

21:04 kind of implied that uh the database is

21:06 actually going to be the one that's

21:07 doing the invalidation on a cache but I

21:09 haven't really explained how that

21:10 process works so one option in theory if

21:14 I'm a client here and I'm writing a

21:15 database uh to a database is to make the

21:18 right and then after that go to a cache

21:21 and say

21:23 invalidate but if you think about it

21:25 that's actually a bit expensive uh in

21:28 theory you may have to actually go and

21:29 invalidate multiple caches and also if

21:32 I'm a client I'm just making one right

21:34 at a time so it's actually a lot more

21:36 efficient even though it's nice to just

21:38 operate stateless clients and have them

21:39 do things like that what's actually more

21:41 efficient is to run a demon process

21:43 which is basically just a background

21:45 process running on the database node

21:47 itself so they run one called MC squeal

21:50 where MC squeal is basically just

21:52 reading from the right ahead log on the

21:53 database taking all of the new rights

21:56 converting them to invalidations doing a

21:58 bunch of batching and then sending those

22:00 out to the MC routers themselves the

22:03 reason it's nice to do batching is so

22:04 that again there's less overhead right

22:06 we can send more invalidations at a time

22:09 and we're not being as wasteful of our

22:10 Network bandwidth the MC routers then

22:13 within each cluster for example we'll go

22:16 ahead and basically you know in addition

22:18 batch a bunch of requests figure out all

22:20 of the individual caches and and the

22:23 requests to where they go so again we're

22:24 doing batching we're sending multiple

22:26 invalidations to a cach at a time and

22:28 then sending them there so that way we

22:30 can batch as many of these invalidations

22:32 as possible it's going to limit the

22:33 number of packets that we send and the

22:35 load on all of our systems out out here

22:38 another nice thing about operating MC

22:40 squeal on the right ahead log is that if

22:42 we have a client over here and it's

22:43 responsible for invalidations and it

22:45 goes down uh before the invalidation can

22:48 be achieved uh now there's no

22:49 invalidation that being said MC squeal

22:52 is you know uh something that can run on

22:54 a persistent right ahead log so

22:56 replayability is going to be a lot

22:57 better because with the right head log

22:58 is ultimately kept on

23:01 disk okay another concept that we have

23:03 here is going to be known as cold

23:05 cluster warm-up so a cold set of caches

23:08 or a cold cluster is just a new set of

23:10 caches that doesn't have any data in

23:11 them yet right so we need to get new

23:13 data in them but the normal process of

23:15 getting data in a cache involves a lot

23:17 of cash misses which is going to be very

23:19 expensive and put a lot of load on our

23:21 databases so instead what we'll do is

23:24 we'll actually have this cold cache go

23:25 ahead and first proxy to a bunch of warm

23:27 caches so if I'm a client like this guy

23:30 and I'm performing reads I'll read from

23:31 the cold cluster if it's a Miss then

23:35 first I'll read from the warm cluster

23:36 and try and get an actual hit there and

23:38 if that doesn't work out for me then

23:40 I'll go to the database or you know then

23:42 um as the client I'll go to the database

23:43 and back fill into my cold cluster so

23:46 hopefully that all makes sense right

23:48 there however there is ultimately One

23:50 race condition that can happen here if

23:52 this is the client and we make a write

23:55 the database is going to invalidate both

23:58 the cold cluster and the warm cluster

24:01 for that key however there's a race

24:03 condition right maybe this invalidation

24:05 for whatever reason takes 10 seconds so

24:07 now if we then proceed to try and read

24:09 the key after that we're going to go

24:11 over here we're going to have a Miss

24:13 we're going to go over to our warm

24:15 cluster and then we're going to read

24:17 stale data because it hasn't been

24:18 invalidated yet and then we're going to

24:20 load that right back into our cold

24:22 cluster and now we have stale data over

24:24 there which is going to be problematic

24:26 because it's already been invalidated so

24:28 the way that this is fixed in practice

24:29 is you know pretty I guess hacky and

24:32 approximate but you know they find in

24:34 practice it's totally fine which is

24:36 basically if I'm the cold region after

24:39 an invalidation uh I'm not going to load

24:42 any data from the warm region for

24:43 another two seconds instead I'll just go

24:46 ahead and grab it from the database and

24:47 treat it like a normal cache

24:50 Miss okay let's go ahead and talk about

24:53 multi- region setups so to be expected

24:58 uh this is ultimately A system that

24:59 needs to be able to uh be Geor

25:01 replicated for a variety of reasons for

25:03 one uh we're more resilient to disasters

25:05 like hurricanes or tornadoes or

25:07 something like that that's just going to

25:08 take out a bunch of data centers in a

25:10 region number two is that we can put

25:12 data closer to the user which especially

25:13 when it's coming to caching is very

25:15 important because it just continues to

25:17 lower latency which is the objective of

25:18 this entire thing and then finally we

25:20 can also just get cheaper power costs

25:22 depending on the region that we put

25:23 these things in which is always very

25:25 nice certain countries are just going to

25:26 charge you less for that now this is

25:29 where things start really looking very

25:30 similar to toao which is basically um

25:33 that you're using asynchronous MySQL

25:35 replication uh across regions for the

25:37 storage tier where you have a master

25:38 region and then everyone else is a

25:40 follower and then within a region you're

25:42 always going to be reading from your

25:44 local database and your local caches

25:47 with a couple of slight exceptions now

25:49 finally it's worth noting that all of

25:51 the cach and validations themselves

25:54 rather than basically uh you know going

25:56 from the master database straight to all

25:58 of the caches in the follower regions

26:00 are actually going to first be embedded

26:02 in the replication Stream So

26:04 invalidations won't happen until the

26:06 data is actually uh you know until the

26:09 right that causes the invalidation is

26:11 actually applied on all of the replica

26:13 databases otherwise we could have a

26:15 bunch of race conditions where uh we

26:17 read from the database too early before

26:19 that uh replication stream has gotten

26:21 there and then we load stale data back

26:23 into the cache which would be

26:25 problematic okay sorry more weird

26:27 PowerPoints glitches which I can't seem

26:29 to hello there we go um basically let's

26:34 go ahead and now talk about read after

26:36 right uh consistency this is where

26:38 things get a little bit janky so let's

26:40 go ahead and go through them so we've

26:42 got this master region we've got a

26:44 follower region if I were a writer in

26:47 the master region you know I'm just

26:48 going to go ahead and write straight to

26:50 the database and everything looks very

26:52 normal if I'm actually going to be a

26:54 writer in the follower region this is

26:56 where things get a little bit more

26:57 interesting

26:59 basically we do something known as a

27:02 remote marker so if I'm writing to the

27:06 follower region I'm going to add a

27:08 remote marker into the cache that

27:10 basically says hey I'm going to go ahead

27:12 and write this key right now and as we

27:14 know all rights because this is single

27:16 leader replication have to go to the

27:18 master region so this comes over here

27:21 now what this means is that if I am a

27:23 different client in the same region

27:25 that's trying to read the value for that

27:27 key I'm going to go to the cache I'm

27:29 going to see hey I know this thing is

27:31 being overwritten so I can now go ahead

27:34 and actually read it from the master

27:35 region

27:37 instead then finally eventually what's

27:39 going to happen is you know this data is

27:41 going to get replicated to our follower

27:42 region and then the data base as part of

27:45 the invalidation process is also going

27:46 to remove the marker so basically when

27:48 we have a a remote marker present it

27:51 says you know go and read this from the

27:53 actual uh Master region as opposed to

27:55 your local follower region so what

27:57 they're doing here is they're trading

27:58 latency and staleness right uh you get

28:01 more latency because it takes a while to

28:03 read data from the master region but

28:05 you're not getting stale data because

28:07 otherwise you know we would go to the

28:08 cash and we would just read an old uh

28:11 value because it hasn't been invalidated

28:15 yet okay let's quickly go through a few

28:18 single server improvements so you know

28:20 in addition to this whole distributed

28:22 system that Facebook went ahead and

28:23 built out they also just made some small

28:25 changes to mcast itself in order to try

28:27 and squeeze squeeze the most out of

28:29 these servers and then some of these

28:30 changes were eventually open sourced as

28:32 well so basically we've got this

28:34 single-threaded implementation and then

28:36 they changed that uh to A fine grain

28:38 concurrent hash table so previously

28:40 mcash was single threaded they made it

28:41 multi-threaded obviously you're going to

28:43 get performance benefits there another

28:45 thing that they did is actually allow

28:46 the hash table to expand in size as

28:48 opposed to being fixed size the reason

28:50 being that you need a hash table getting

28:52 bigger over time or else if it

28:53 completely fills up uh your time

28:55 complexity on uh fetches is going to get

28:58 worse cuz you're going to have to do a

28:59 bunch of probing or chaining or

29:00 something like that and you're going to

29:01 approach linear time if you make a

29:03 bigger hash table uh then you're able to

29:05 actually get better time

29:07 complexity another thing to note is that

29:09 every single thread uh in the concurrent

29:11 implementation has its own UDP Port uh

29:13 which is just going to allow more

29:14 concurrent connections at once and then

29:17 also they do something known as slabs

29:19 toao did the same thing the idea of

29:21 slabs is that uh you know different

29:23 values in the hashmap themselves are

29:25 going to have different sizes and so you

29:27 basically put each value in the slab

29:29 class that corresponds to it um so you

29:32 know maybe there's a one megabyte slab

29:34 class and a 2 megabyte slab class and a

29:36 4 megabyte slab class or something like

29:38 that and the idea there is to basically

29:40 try and balance the eviction rates

29:41 between all of those slab caches now the

29:44 way that they do that is effectively

29:46 they try and balance the age of the

29:47 oldest item and this is going to allow

29:50 them to basically mimic like a global

29:52 least recently used policy across all of

29:54 those slab caches and uh or slab classes

29:58 and it's just going to be more efficient

30:00 um finally they're going to at least try

30:02 and handle items with a small tte better

30:05 so some items go into the cash and

30:07 they're explicitly meant to be expired

30:09 after a certain amount of time that

30:11 being said at least natively mcash did

30:13 uh lazy uh invalidations so you know the

30:17 data would still be in the hashmap and

30:18 then you know if you checked it and you

30:20 saw the tte was expired you would just

30:22 go ahead and get rid of it or garbage

30:23 collect it then that being said this was

30:25 taking up a bunch of extra memory

30:26 because there were a lot of these short

30:27 short lived items so basically for

30:30 shortlived items only Facebook

30:32 implemented a system where they would

30:33 actually be eagerly deleted and then

30:35 everything else would be lazily garbage

30:37 collected and then the last Improvement

30:39 that they have uh helps a lot with

30:41 something like rolling upgrades or

30:42 restarts or something like that where

30:44 basically they use this concept of

30:46 system V shared memory for all the data

30:48 in mcache and what this means is that

30:50 this memory is persistent even after the

30:52 process ends and restarts so that way if

30:55 uh you know you kill an instance of the

30:56 cach and then you restart the process

30:58 you don't have to go basically have a

31:00 cold cache and warm up again uh you can

31:02 just get your data back really quickly

31:03 because it's going to be in the same

31:04 memory

31:06 addresses all right let's go ahead and

31:08 conclude this one basically the idea

31:11 here is that uh like many other systems

31:13 that we're seeing recently basically

31:15 separating a bunch of individual tiers

31:17 out is really nice because you can scale

31:18 them independently as needed so in this

31:20 case it's going to be your caching tier

31:22 that you're scaling independently

31:23 because at the end of the day you've got

31:25 a lot of requests they're all accessing

31:26 a ton of similar data and the data

31:28 itself is not that big so caches are

31:30 going to be super effective and you

31:31 don't want to have to build out a bunch

31:32 of extra database in uh you know

31:34 instances to just run local caches there

31:37 having a separate tier is very very nice

31:39 you can scale it yourself it's also just

31:41 nice because you know tying individual

31:43 caches to whatever database you're using

31:46 doesn't allow you to extend that to

31:47 using different data sources cool uh as

31:50 we mentioned caching is going to get

31:52 better read performance by virtue of

31:54 using memory instead of disk and also

31:56 things like hashmaps and then also it's

31:58 just going to stop us from having a

31:59 bunch of thundering herds on our

32:00 databases it is going to be the case

32:02 that if you have a 100 clients reading

32:04 from a database concurrently that's

32:06 going to put a lot of load on it but a

32:08 system that can very very quickly answer

32:10 and respond to all those requests over

32:11 UDP and multi-threaded is going to make

32:13 that process a lot easier and stop the

32:15 database from getting a ton of

32:17 load uh another thing that they do this

32:19 is more of a design philosophy on their

32:20 part is opt for Simplicity uh stateless

32:23 components like the client because the

32:25 client is you know responsible for

32:27 keeping the caches sync after they do a

32:29 read and that's completely stateless

32:30 right like the client is not remembering

32:32 anything it's just you know calling a

32:33 function read the database and then

32:35 calling another function update the

32:36 cache now obviously there are all sorts

32:39 of implications in terms of partial

32:40 failures here but evidently they found

32:42 in practice things weren't too bad and

32:45 then finally they only want to include

32:46 features in memcache that actively make

32:48 everyone's life better they don't want

32:50 to over complicate things and build all

32:52 these Half Bake solutions that only help

32:53 a percentage of the users they basically

32:56 only want to implement a change if it's

32:57 going to be super impactful anyways guys

33:00 I hope you enjoyed this video uh my

33:01 throat was given out a little bit by the

33:03 end there but that's okay uh you can

33:04 call me the throat goat uh maybe don't

33:07 actually and I will see you in the next

33:09 one

0:00 Xin chào mọi người, chào mừng trở lại kênh của mình. Nếu các bạn đã xem video tuần trước thì chắc biết, thật không may, mình đã không nhận được lời mời làm việc làm backend developer từ bạn gái mình.

0:11 Cô ấy bảo công ty đang tạm ngừng tuyển dụng, rồi "tặng" mình hai bài lead code khó, bắt làm trong 30 phút, chịu luôn. Nhưng không sao, chúng ta vẫn ở đây, sẵn sàng cho video tuần này, nói về việc lưu vào bộ nhớ đệm (caching) tại Facebook. Bắt đầu thôi!

0:28 Như thường lệ, mình sẽ "chém gió" thôi vì thú thật là mình chẳng nhớ gì những gì đã viết cả, nhưng mình nghĩ mình sẽ "bịa" ra được trong quá trình này. Hôm nay, chúng ta sẽ nói về bài báo "mcash", được Facebook công bố năm 2013.

0:43 Mình cũng đã làm một video về "taao", một bài báo khác của Facebook, và hai bài báo này có nhiều điểm tương đồng. TAO về cơ bản là cơ sở dữ liệu đồ thị của Facebook, sử dụng rất nhiều bộ nhớ đệm, còn memcache chỉ là một lớp bộ nhớ đệm riêng biệt, nhưng chúng có nhiều điểm chung.

1:01 TAO cố gắng xây dựng dựa trên những gì mcash đã làm và cải thiện nó, nhưng mcash đã đặt nền móng cho TAO. Vì vậy, nếu bạn chưa xem video về TAO, thì đó sẽ là một video nối tiếp rất hay cho video này.

1:10 Thôi, bắt đầu tìm hiểu về bối cảnh của bài báo này nhé.

1:15 Về cơ bản, tên bài báo là "mem cach". Ngoài ra còn có một công nghệ gọi là "M cached", về cơ bản là một bộ nhớ đệm máy chủ đơn mã nguồn mở, đúng không? Về cơ bản, nó chỉ chạy một hashmap trên một máy chủ và các mục có thể hết hạn theo thời gian.

1:29 Lý do Facebook cần những thứ này là vì khi bạn tải một trang Facebook, họ có thể thực hiện tới 500 yêu cầu API khác nhau đến rất nhiều máy chủ khác nhau, rồi tải kết quả từ tất cả những nơi này. Việc phải truy cập vào các cơ sở dữ liệu thông thường nhiều như vậy là không ổn.

1:41 Lý tưởng nhất là bạn muốn giữ một lượng lớn dữ liệu trong bộ nhớ, hoặc ít nhất là càng nhiều càng tốt, đặc biệt là đối với các kết quả phổ biến, để bạn có thể lấy lại dữ liệu nhanh nhất có thể. Điều này cũng tốt vì nếu có quá nhiều máy chủ cùng truy cập vào một loạt cơ sở dữ liệu cùng một lúc, bạn sẽ gây quá nhiều áp lực lên chúng và chúng có thể "tèo".

1:57 Vì vậy, một lần nữa, theo cách tương tự, cash có thể xử lý tất cả các yêu cầu này nhanh hơn nhiều, về cơ bản là đang bảo vệ cơ sở dữ liệu khỏi bị quá tải.

2:05 Điều thực sự tuyệt vời về một lớp bộ nhớ đệm là bạn có một loạt các nguồn dữ liệu không đồng nhất khác nhau, đúng không? Họ có thể có cơ sở dữ liệu, họ có thể đọc từ Hadoop, và việc chỉ có một lớp bộ nhớ đệm thống nhất thay vì ghép nó với từng tầng lưu trữ cơ sở dữ liệu đó là... nó có thể hoạt động với bất kỳ hệ thống lưu trữ cụ thể nào.

2:23 Ờ, nó có thể giữ dữ liệu trên đĩa, sau đó nó có thể lưu trữ mọi thứ riêng biệt, hoặc thậm chí nó có thể lưu trữ những thứ không nhất thiết phải được lưu vào bộ nhớ đệm. Nó có thể lưu trữ kết quả của một số tính toán hàng loạt hoặc một cái gì đó tương tự.

2:33 Vì vậy, một lần nữa, điều thực sự tuyệt vời về điều này là chúng ta có được khả năng mở rộng quy mô riêng biệt, đúng không? Nó không gắn liền với số lượng máy chủ cơ sở dữ liệu mà mình có, mà gắn liền với tải đọc thực tế của hệ thống hơn.

2:45 Rõ ràng, việc giữ mọi thứ trong bộ nhớ sẽ làm tăng tốc độ đọc của chúng ta, và tất nhiên, như mình đã đề cập, chúng ta đang bảo vệ tầng lưu trữ của mình.

2:50 Vì vậy, hệ thống của họ ở đây chỉ được gọi là "memcache", đúng không? "mem cach" là một máy chủ đơn, còn "mem cach" trong bài báo đề cập đến hệ thống phân tán mà họ đã xây dựng.

3:02 Ở cấp độ rất, rất cao, về cơ bản những gì chúng ta đang làm ở đây chỉ là một loạt các bộ nhớ đệm tìm kiếm, đúng không? Chúng ta có tất cả những khách hàng này, mặc dù mình vẽ nó như một người, nhưng trên thực tế, nó có thể chỉ là một loại máy chủ ứng dụng nào đó, và máy chủ ứng dụng sẽ đọc từ một số bộ nhớ đệm.

3:19 Lý tưởng nhất là bạn sẽ "trúng" bộ nhớ đệm (cache hit), nhưng nếu

3:21 bạn không "trúng" và chúng ta "trượt" (cache miss), thì chúng ta sẽ đọc từ cơ sở dữ liệu. Khi chúng ta nhận được dữ liệu đó từ cơ sở dữ liệu, chính khách hàng sẽ chịu trách nhiệm đặt khóa (key) trong bộ nhớ đệm. Chúng ta sẽ thảo luận về một số vấn đề phức tạp phát sinh từ điều đó sau.

3:35 Ờ, ý tưởng tương tự ở đây, ngoại trừ một chút khác biệt về quyền là nếu chúng ta là khách hàng, một lần nữa, không phải là một người, mà thực sự chỉ là một máy chủ phụ trợ ứng dụng, thì lý tưởng nhất là chúng ta sẽ đặt một số khóa trong cơ sở dữ liệu mySQL, và sau đó chính cơ sở dữ liệu sẽ vô hiệu hóa bộ nhớ đệm.

3:52 Chúng ta sẽ nói về lý do cơ sở dữ liệu làm điều đó. Có một lý do cho việc đó, trái ngược với việc khách hàng làm, bởi vì về lý thuyết, khách hàng có thể thực hiện việc vô hiệu hóa, và đó là cách họ vẽ ở đầu bài báo, nhưng cuối cùng hóa ra chính DB mới làm điều đó.

4:04 Một câu hỏi nữa là, thay vì vô hiệu hóa cache, tại sao chúng ta không cập nhật luôn giá trị của khóa đó? Chúng ta có thể làm vậy, nhưng nếu hai khách hàng cùng ghi vào một khóa cùng một lúc thì sao? Lúc đó sẽ xảy ra tình trạng tranh chấp (race condition) giữa hai bên, ai sẽ là người cập nhật giá trị vào cache trước?

4:21 Có thể xảy ra tình trạng dữ liệu bị ghi đè sai, dẫn đến kết quả không chính xác. Vì vậy, việc vô hiệu hóa thường dễ dàng hơn, và giá trị sẽ được cập nhật khi có yêu cầu đọc.

4:32 Như mình đã đề cập, chúng ta có khái niệm về mô hình lan tỏa (fanout), đúng không? Nếu mình là một máy chủ ứng dụng, mình có thể đọc từ 500 phiên bản memcached cùng một lúc, và điều đó có nghĩa là chúng ta có rất nhiều yêu cầu mạng lan tỏa.

4:45 Một vài vấn đề của việc này là nếu một máy chủ nào đó quá chậm, nó sẽ gây khó khăn cho mọi người khi tải trang, và điều này sẽ gây ra vấn đề. Ngoài ra còn có khái niệm về tắc nghẽn incast, một khái niệm khá thú vị.

4:57 Đây không phải là một thuật ngữ mình từng nghe trước đây. Về cơ bản, nếu bạn có một số bộ chuyển mạch mạng (network switch) ngay trong trung tâm dữ liệu, và nó được kết nối với tất cả các máy chủ mcash khác nhau này, thì nếu có quá nhiều gói tin đi vào bộ chuyển mạch mạng cùng một lúc, mọi thứ có thể bị loại bỏ hoặc trở nên chậm chạp, và điều đó cũng sẽ gây ra vấn đề.

5:15 Và cuối cùng, nếu mình là một máy chủ web và mình có một loạt các máy chủ bộ nhớ đệm khác nhau ở phía dưới, thì bây giờ mình có thể phải duy trì kết nối với mỗi máy chủ bộ nhớ đệm. Không chỉ mình làm điều đó, mà có thể phải duy trì kết nối với mỗi máy chủ cache trên mọi luồng (thread) trên máy chủ web này.

5:35 Nếu có 100 cái như vậy, thì mình đột nhiên có 300 kết nối, và chúng ta không muốn duy trì nhiều kết nối như vậy.

5:40 Vậy làm thế nào để cải thiện những vấn đề đó? Trước tiên, hãy nói về tổng quan cấp cao về memcache.

5:46 Về cơ bản, chúng ta có một loạt bộ nhớ đệm và chúng ta đang chia chúng bằng cách băm nhất quán (consistent hashing). Sau đó, chúng ta có mô hình lan tỏa vì mọi người hầu như đều đọc từ mọi bộ nhớ đệm khi nó có liên quan đến họ.

5:56 Lưu ý rằng điều này đang hoạt động như thể chúng ta đang thực hiện phạm vi khóa (key range). Trên thực tế, đây sẽ là phạm vi của hàm băm của các khóa, đó là cách băm nhất quán sẽ hoạt động.

6:03 Đây sẽ là các máy chủ web hoặc máy khách của chúng ta, và đây sẽ là các bộ nhớ đệm. Được rồi, bây giờ chúng ta sẽ đi sâu vào một vài tối ưu hóa hiệu suất.

6:12 Đây là lúc mọi thứ sẽ trở nên sâu sắc hơn một chút, và chúng ta sẽ cố gắng giải quyết một số vấn đề mà chúng ta đã đề cập trước đó.

6:16 Về cơ bản, nếu tất cả các máy chủ web này đang tìm nạp kết quả từ mọi bộ nhớ đệm này, và chúng đang tìm nạp rất nhiều khóa cùng một lúc, thì lý tưởng nhất là chúng ta muốn xử lý hàng loạt càng nhiều yêu cầu càng tốt cùng một lúc để giảm chi phí thực tế của việc gửi tất cả các yêu cầu này đến các phiên bản cache.

6:32 Vì vậy, chúng ta không chỉ nên tìm nạp các khóa này theo lô (batch) mà chúng ta còn nên làm như vậy song song.

6:35 Sẽ thật ngớ ngẩn nếu chúng ta đến một cache, lấy tất cả dữ liệu, sau đó đến một cache khác, lấy tất cả dữ liệu, rồi đến một cache khác. Chúng ta nên làm điều đó song song.

6:43 Một điều khác mà mình đã đề cập là vấn đề về luồng, đúng không? Nếu bạn có 100 luồng đang chạy trên một máy chủ, bạn không muốn số lượng kết nối mở của máy chủ bộ nhớ đệm gấp 100 lần, điều đó sẽ thực sự làm chậm máy chủ.

6:54 Vì vậy, thay vào đó, mỗi một trong số các máy chủ khách hàng đó sẽ chạy một quy trình bộ định tuyến MC (MC router) duy nhất, trong đó quy trình bộ định tuyến MC là quy trình duy nhất chịu trách nhiệm kết nối với các phiên bản mcash.

7:04 Hoặc một tùy chọn khác là bạn có thể chạy MC router, quy trình đó được nhúng trên một số loại máy chủ proxy. Thay vì duy trì kết nối với mọi máy chủ mcash, bạn chỉ duy trì một kết nối với proxy, vì vậy điều đó cũng có thể xảy ra.

7:22 Cuối cùng, đối với việc đọc, họ thực sự sử dụng UDP thay vì TCP, điều này khá thú vị. Lý do họ làm điều đó là vì UDP sẽ có ít thông tin được nhúng trong mỗi gói hơn, và bạn cũng không nhất thiết phải thiết lập bắt tay (handshake) để lấy dữ liệu từ máy chủ.

7:38 Bạn chỉ cần gửi một gói qua đó. Vì vậy, UDP rất tốt về mặt hiệu suất, nhưng nó cũng có một số phức tạp liên quan đến nó, đó là bạn có thể có các gói bị loại bỏ, đúng không? Không thực sự có một cơ chế thử lại tự động hoặc các gói thậm chí có thể bị mất trật tự.

7:54 Nếu điều đó xảy ra, về cơ bản cách khách hàng xử lý điều này là, "Mình vừa bỏ lỡ một khoản tiền mặt." Một trong những lý do khiến bạn có thể thấy những thứ như gói bị loại bỏ hoặc các gói bị mất trật tự là vì máy chủ mà bạn đang cố gắng truy cập hoặc cache mà bạn đang cố gắng truy cập bị quá tải và không ở trong một trạng thái tốt.

8:10 Về cơ bản, có thêm logic rằng nếu bạn đã loại bỏ các gói, và đó là lý do tại sao bạn bỏ lỡ một khoản tiền mặt, và sau đó bạn đọc vào cơ sở dữ liệu, thì thực sự đừng cố gắng lấp đầy giá trị đó trong bộ nhớ đệm, chỉ cần tránh hoàn toàn điều đó.

8:21 Tuy nhiên, đối với các thao tác đặt (set) và xóa (delete), vì chúng ta vô hiệu hóa các khóa trong bộ nhớ đệm, và chúng ta cũng đặt một khóa trong cache sau khi chúng ta đọc từ cơ sở dữ liệu, chúng ta thực sự làm điều đó với TCP. Lý do là vì chúng ta muốn có một số cơ chế thử lại tự động.

8:36 Về lý thuyết, bạn có thể chỉ cần thực hiện điều đó trên UDP, nhưng thực sự không có lý do chính đáng nào để làm như vậy. TCP sẽ rất tốt để thử lại các thao tác không thành công của chúng ta.

8:44 Và cuối cùng, chúng ta thực sự sẽ thực hiện một số lượng kiểm soát luồng (flow control). Chúng ta cũng thực hiện kiểm soát luồng trong TCP, nhưng kiểm soát luồng TCP dựa trên dung lượng của một kết nối, đúng không?

8:56 Cách kiểm soát luồng thường hoạt động là bạn có một số cửa sổ (window), về cơ bản bạn đang nói đây là tất cả các kết nối mở của tôi, hoặc xin lỗi, các yêu cầu mở của tôi.

9:04 Yêu cầu của tôi vừa nhận được phản hồi, bây giờ tôi chỉ có ba yêu cầu mở, vì vậy tôi thực sự có thể nhận một yêu cầu khác vào đó vì giới hạn của tôi là bốn.

9:11 Khái niệm tương tự, và chúng ta đang thực hiện điều này trong bộ định tuyến MC, nhưng thay vì thực hiện điều này ở cấp độ gửi yêu cầu đến một phiên bản mcash duy nhất, chúng ta thực hiện điều đó cho tất cả các yêu cầu tích lũy đến các phiên bản mcash.

9:25 Vì chúng ta có quá nhiều sự lan tỏa, nên lý tưởng nhất là bạn muốn tất cả các máy khách biết rằng họ không gửi quá nhiều yêu cầu ở khắp mọi nơi. Đó là một điều thực sự tốt để làm, và bạn chỉ cần thực hiện điều đó bằng cách sử dụng một cửa sổ trượt (sliding window).

9:34 Cuối cùng, giống như TCP, điều này đang thực hiện một sự gia tăng cộng và giảm nhân (additive increase multiplicative decrease). Khi bạn tiếp tục nhận được các yêu cầu thành công, bạn có thể tăng rất chậm kích thước của cửa sổ trượt đó. Nếu vì bất kỳ lý do gì bạn loại bỏ các gói hoặc một yêu cầu không nhận được phản hồi, bạn sẽ giảm kích thước của cửa sổ trượt đó rất nhanh. Điều đó là để đảm bảo rằng chúng ta không làm quá tải Cach Fleet của mình.

9:57 Được rồi, bây giờ mình sẽ mô tả

9:59 một vài vấn đề cũng nảy sinh trong một hệ thống như thế này, và sau đó chúng ta sẽ nói về cách chúng ta thực sự giải quyết chúng. Vấn đề đầu tiên được gọi là "tập hợp cũ" (stale set), đó là một hệ thống khá đơn giản.

10:08 Về cơ bản, ý tưởng ở đây là, giả sử mình có một máy khách ở bên trái là người đọc và một máy khách ở bên phải là người viết. Người đọc sẽ cố gắng đọc từ bộ nhớ đệm.

10:19 Có thể giá trị không có ở đó vì bất kỳ lý do gì, vì vậy chúng ta bị "trượt" bộ nhớ đệm. Chúng ta biết rằng khi chúng ta bị "trượt" bộ nhớ đệm, chúng ta sẽ truy cập vào cơ sở dữ liệu, chúng ta đọc từ cơ sở dữ liệu, và sau đó chúng ta lấp đầy giá trị vào bộ nhớ đệm.

10:29 Tuy nhiên, khi chúng ta đang đọc từ cơ sở dữ liệu, máy khách ghi thực sự sẽ đặt một giá trị mới từ khóa đó. Như chúng ta biết, điều đó dẫn đến việc vô hiệu hóa giá trị của khóa đó trong bộ nhớ đệm, đó là bước bốn.

10:41 Đây là một tình trạng tranh chấp, đúng không? Cuối cùng, ở bước năm, máy khách đang thực hiện thao tác đọc thực sự đặt giá trị cũ của khóa X vào bộ nhớ đệm, và bây giờ đột nhiên chúng ta đang đọc dữ liệu cũ, đúng không? Đó là một tình trạng tranh chấp, chúng ta không muốn điều đó xảy ra.

10:54 Điều khác có thể xảy ra ở đây là khái niệm về "Thundering Herd", nơi chúng ta kết thúc việc nhận thêm một loạt tải trên cơ sở dữ liệu, trong khi đáng lẽ không nên như vậy.

11:03 Trong kịch bản này, chúng ta có một máy khách ghi ở đây, và sau đó chúng ta có một loạt người ở bên trái đang thực hiện thao tác đọc. Người viết sẽ thực hiện thao tác ghi, điều mà như chúng ta biết sẽ vô hiệu hóa khóa trong cache.

11:15 Từ đó, chúng ta có một loạt người đọc đồng thời cùng một lúc sẽ đọc từ cache. Vì tất cả họ đều đọc cùng một lúc, nên cache thực sự chưa nhận được giá trị nào được điền vào cho nó.

11:28 Vì vậy, bây giờ tất cả các yêu cầu đó sẽ bị "trượt" cache, và sau đó tất cả chúng sẽ chuyển đến cơ sở dữ liệu. Điều này đặc biệt sẽ là một vấn đề với các khóa phổ biến.

11:37 Vì tất cả những người đọc này đang đọc hiện tại, đột nhiên cơ sở dữ liệu của chúng ta nhận được một loạt tải bổ sung có thể khiến nó bị lỗi. Sau đó, chúng ta thậm chí có thể gặp các lỗi xếp tầng (cascading failures) chỉ do cân bằng lại hoặc một cái gì đó tương tự. Vì vậy, bạn muốn tránh cả hai vấn đề này.

11:50 Cơ chế mà chúng ta sử dụng trong mcash để làm như vậy là một thứ được gọi là "cho thuê" (leasing).

11:56 Một hợp đồng thuê, nói một cách rất đơn giản, về cơ bản giống như một so sánh và đặt (compare and set), và cache sẽ trả lại nó. Hãy tiếp tục và mô tả nó.

12:02 Ở đây chúng ta có một người đọc, ở đây chúng ta có một người đọc khác, và ở đây chúng ta có một người viết.

12:14 Hãy tưởng tượng để bắt đầu mã thông báo thuê (lease token) là ABC. Lý do mã thông báo thuê là ABC là vì người đọc này đến, nó thực hiện một Cache Miss. Ngay sau khi Cache Miss xảy ra, Cache nói, "Đối với khóa mà bạn quan tâm, tôi đang đặt một mã thông báo có tên là ABC."

12:32 Vì vậy, đó sẽ là hợp đồng thuê của chúng ta ngay tại đó, và chúng ta sẽ trả lại ABC cho người đọc.

12:37 Bây giờ, một vài điều tốt đẹp khác xảy ra do kết quả của việc này. Hãy tưởng tượng rằng vì đây là một Cache Miss, nên hiện tại không có giá trị nào trong Cache, đúng không?

12:45 Có thể chúng ta có một trong những kịch bản Thundering Herd, nơi một người đọc khác cũng đến và cố gắng đọc cùng một khóa, và nó không có ở đó.

12:52 Thông thường, điều này sẽ dẫn đến việc đọc vào cơ sở dữ liệu, đúng không? Hay đúng hơn, xin lỗi, không phải như vậy, mà là một lần đọc từ anh chàng này đến cơ sở dữ liệu, và chúng ta không muốn điều đó xảy ra.

13:01 Chúng ta muốn cuối cùng họ chỉ đọc giá trị từ bộ nhớ đệm. Vì vậy, nếu họ đọc từ cache và họ thấy rằng có một mã thông báo đang hoạt động cho khóa này, những gì họ thực sự sẽ làm là chỉ cần đợi một vài giây.

13:11 Điều này hoàn toàn không hoàn hảo, đúng không? Bởi vì thông thường bạn không muốn dựa vào việc giảm dần theo cấp số nhân (exponential backoff) hoặc bất cứ điều gì, nhưng trên thực tế, nó thực sự hoạt động rất tốt.

13:18 Về cơ bản, nếu bạn đợi nửa giây, điều có thể xảy ra là người đọc này ở đây sẽ đi tìm nạp một giá trị

13:25 từ cơ sở dữ liệu và cuối cùng đặt nó vào đó. Điều đó hoạt động rất nhiều lần, điều này thực sự, thực sự tốt.

13:32 Đó là một khía cạnh của việc ngăn những người khác đọc cùng lúc với bạn từ cơ sở dữ liệu, do đó ngăn chặn các đàn sấm sét. Một khía cạnh thực sự tốt khác của nó cũng là ngăn chặn các tập hợp có trạng thái (stale sets).

13:44 Như chúng ta đã đề cập, điều có thể xảy ra là người đọc này thực sự có thể tiếp tục và đọc và cố gắng đặt giá trị ở đây sau khi khóa đó đã bị vô hiệu hóa.

13:54 Ở bước năm, chúng ta có một người viết, người viết sẽ ghi vào cơ sở dữ liệu. Ở bước sáu, chúng ta vô hiệu hóa khóa trong cơ sở dữ liệu, đồng thời sẽ nói, "Ồ, có một mã thông báo ABC ở đây, hãy tiếp tục và xóa nó, nó không còn hợp lệ nữa."

14:09 Lý do tại sao chúng ta xóa nó là vì khi người đọc này cuối cùng đọc từ cơ sở dữ liệu một giá trị cũ và cố gắng đến và nói, "Tôi đang sử dụng mã thông báo ABC để đặt một giá trị mới," cache sẽ nói, "Ồ, đợi một chút, mã thông báo ABC không còn hợp lệ nữa vì tôi đã có khóa của mình kể từ khi bị vô hiệu hóa, và vì vậy tôi không còn chấp nhận bạn nữa."

14:29 Bằng cách này, anh chàng này có thể tiếp tục và thử lại ở đây. Anh ta có thể thực hiện một Cache Miss khác, sau đó truy cập vào cơ sở dữ liệu, và sau đó điền vào giá trị thích hợp cho phù hợp.

14:42 Tuyệt vời, một khái niệm khác mà chúng ta có sẽ là khái niệm về các nhóm mcash (mcash pools). Về cơ bản, sau khi chạy các phiên bản mcash này trong một thời gian, các nhà phát triển tại Facebook nhận thấy rằng dữ liệu có các thuộc tính khác nhau.

14:56 Các khóa và giá trị có thể có kích thước khác nhau, chúng có thể có độ biến động (volatility) khác nhau, trong đó độ biến động về cơ bản ngụ ý tần suất mọi thứ bị loại khỏi cache hoặc không còn liên quan, hoặc chúng có thể có tốc độ truy cập khác nhau.

15:07 Một số dữ liệu nhất định đang được truy cập rất thường xuyên, một số dữ liệu nhất định đang được truy cập rất không thường xuyên. Vì vậy, lý tưởng nhất là bạn muốn lưu trữ dữ liệu trong cùng một nhóm mcash, về cơ bản chỉ là một tập hợp các máy chủ mcash có các thuộc tính tương tự.

15:19 Nếu bạn không làm như vậy, bạn có thể có một số kịch bản xấu phát sinh từ các mẫu truy cập khác nhau. Một ví dụ mà họ đưa ra là khái niệm về các khóa có độ biến động thấp.

15:29 Một khóa có độ biến động thấp là một khóa hiếm khi bị loại khỏi cache, hoặc về lý thuyết không nên bị loại khỏi cache vì nó luôn được yêu cầu.

15:36 Nhưng đôi khi nếu nó được ghép nối với một loạt các khóa rất, rất phổ biến trong thời gian ngắn, ví dụ như một bài đăng gần đây hoặc một cái gì đó, nhưng rất nhanh chóng sẽ trở nên không phổ biến. Có thể là nếu chúng ta hết dung lượng trong bộ nhớ đệm vì các khóa có độ biến động cao gần đây đã được truy cập rất nhiều, các khóa có độ biến động thấp có thể bị thay thế bởi chính sách LRU (Least Recently Used). Sau đó, đột nhiên chúng ta có một loạt các khóa có độ biến động cao trong cache, và chúng không còn được truy cập nữa, vì vậy điều đó sẽ lãng phí.

16:03 Việc tách những người này thành các nhóm mcash khác nhau cũng có thể có các thuộc tính tốt.

16:09 Xin lỗi, mình nhận thấy rằng đôi khi khi mình thực hiện một thứ PowerPoint nhỏ, nó sẽ bị rối một chút, vì vậy mình chỉ muốn tiếp tục và sửa nó.

16:17 Ý tưởng ở đây bây giờ là ngoài việc có một loạt các nhóm khác nhau, chúng ta cũng có thể thực hiện một số sao chép cache (cache replication).

16:24 Thông thường trong mcash, chúng ta cố gắng chỉ dựa vào việc sử dụng phân vùng (partitioning) để phân vùng tập dữ liệu. Tuy nhiên, chúng ta cũng sẽ thực hiện sao chép trong một số kịch bản duy nhất.

16:34 Một kịch bản mà chúng ta sẽ thực hiện sao chép là khi chúng ta có một tập hợp khóa rất, rất nhỏ được truy cập rất thường xuyên.

16:42 Giả sử chúng ta có 100 khóa trong tập hợp khóa của mình, và các giá trị khá nhỏ sao cho toàn bộ có thể tồn tại trên một nút duy nhất. Đó là một tập hợp khóa siêu phổ biến, và bạn có thể có hàng trăm hoặc hàng nghìn máy chủ khách hàng đang tiếp cận nó mọi lúc.

16:58 Trong trường hợp này, sẽ có rất nhiều tải trên máy chủ đó, và sẽ rất tuyệt

17:01 nếu chúng ta có thể phân phối nó một chút. Về lý thuyết, bạn có thể phân vùng tập hợp khóa, nhưng bản thân các yêu cầu riêng lẻ không tốn kém lắm.

17:08 Điều quan trọng hơn là có rất nhiều yêu cầu trong số đó. Việc phân vùng nó thực sự sẽ không tạo ra sự khác biệt lớn vì chi phí thực tế của việc trả lại dữ liệu chưa bao giờ lớn ngay từ đầu.

17:16 Thay vào đó, điều tốt hơn bạn nên làm là thiết lập một bản sao của cùng một tập dữ liệu. Bây giờ, mỗi bản sao trong số chúng sẽ có một nửa số yêu cầu, điều này sẽ tốt hơn rất nhiều.

17:27 Điều đáng chú ý là khi chọn bản sao, khách hàng về cơ bản sẽ chỉ cân bằng tải ngẫu nhiên dựa trên địa chỉ IP của riêng họ.

17:35 Một khái niệm khác mà chúng ta có trong mcash sẽ là ý tưởng về các máy chủ máng xối (gutter servers). Thông thường trong quá khứ với rất nhiều hệ thống phân tán mà chúng ta đang nói đến, nếu các máy chủ ngừng hoạt động, những gì chúng ta sẽ cố gắng làm là thường cân bằng lại các khóa giữa chúng, đúng không?

17:49 Đây là điều không hoàn toàn tầm thường, nhưng cuối cùng nếu đó là một thứ như cơ sở dữ liệu, bạn không có lựa chọn nào khác, đúng không? Dữ liệu phải sống ở đâu đó.

17:56 Nhưng điều tuyệt vời về những thứ này là cuối cùng thì đó là dữ liệu cache, và vì vậy nó không cần phải hoàn hảo.

18:01 Khi bạn cân bằng lại, việc băm lại hoặc cân bằng lại cũng sẽ rất khó vì một số khóa có thể được coi là "nóng", đúng không?

18:10 Nếu có 10 khóa nhận được rất nhiều tải, có thể lên đến 20% tải của một máy chủ duy nhất (đó là giá trị mà họ sử dụng trong bài báo thực tế), lấy khóa đó và sau đó chỉ cần đặt nó trên một máy chủ mới ngẫu nhiên có thể khiến máy chủ đó bị quá tải, gặp sự cố, và bây giờ bạn gặp các lỗi xếp tầng.

18:25 Thay vào đó, họ có khái niệm về các máy chủ máng xối. Một máy chủ máng xối như máy chủ này ở đây, hoặc các máy chủ máng xối nói chung, chỉ chịu trách nhiệm cho khoảng 1% số máy chủ trong toàn bộ cụm.

18:34 Về cơ bản, nếu anh chàng này ngừng hoạt động ở đây, điều đầu tiên chúng ta sẽ cố gắng làm là thực hiện một yêu cầu đến nó. Nếu điều đó không thành công, chúng ta sẽ tiếp tục và yêu cầu xem giá trị có tồn tại trong một máy chủ máng xối hay không.

18:44 Nếu không, rõ ràng chúng ta sẽ kéo nó vào từ một số loại cơ sở dữ liệu.

18:49 Bất kỳ máy khách nào khác cũng sẽ làm chính xác điều tương tự, đúng không? Nó sẽ thực hiện cùng một yêu cầu đó, và sau đó nó sẽ băm yêu cầu đó đến cùng một máy chủ máng xối trong nhóm máng xối.

18:57 Lý tưởng nhất là bạn vẫn có thể nhận được khóa đó, và nó sẽ giải quyết rất nhiều lỗi cache lẽ ra đã xảy ra nếu không, và tiết kiệm rất nhiều tải từ cơ sở dữ liệu của chúng ta.

19:07 Điều đáng chú ý là cơ sở dữ liệu không nhất thiết biết rằng máy chủ máng xối này thực sự có dữ liệu bộ nhớ đệm trên đó, hoặc nó không biết dữ liệu bộ nhớ đệm cho các khóa thực sự nằm ở đâu vì bây giờ chúng ta đã phá vỡ chính sách băm nhất quán của mình.

19:18 Do đó, về cơ bản chúng ta muốn dữ liệu trên các máy chủ máng xối hết hạn khá nhanh. Chúng ta biết rằng nó tồn tại khá ngắn, và về cơ bản nó sẽ tự động hết hạn.

19:30 Tuyệt vời, hãy tiếp tục và nói về khái niệm về các khu vực (regions) và cụm (clusters) này vì đây là hai từ khóa mà chúng ta sẽ cần để hiểu phần còn lại của bài báo này.

19:37 Đầu tiên là một cụm. Đây về cơ bản chỉ là một sự kết hợp của các máy chủ mcash, cũng như một loạt các máy chủ khách hàng lý tưởng được đặt cùng vị trí trong cùng một trung tâm dữ liệu.

19:48 Có lẽ cũng sẽ là các miền lỗi (fault domains) tương tự về mặt nguồn điện và mạng hoặc những thứ tương tự.

19:51 Sau đó, bạn cũng có một loạt các khu vực. Một khu vực bao gồm nhiều cụm, cũng như có thể là một lớp lưu trữ dùng chung, nơi chúng nằm ở một vị trí tương tự về mặt địa lý.

20:03 Vẫn khá gần nhau, nhưng vẫn là các miền lỗi khác nhau, đúng không? Có lẽ các tòa nhà vật lý khác nhau hoặc các giá mạng khác nhau hoặc một cái gì đó tương tự.

20:11 Cũng có khái niệm về một nhóm khu vực (region pool). Cuối cùng trong các cụm khác nhau, bạn đang sao chép dữ liệu bộ nhớ đệm một cách hiệu quả vì bạn có các máy khách khác nhau sử dụng các cụm khác nhau.

20:23 Một nhóm khu vực về cơ bản là bạn có các máy khách khác nhau, ngoại trừ tất cả chúng đều đang sử dụng các máy chủ MC trải rộng trên nhiều trung tâm dữ liệu hoặc một cái gì đó tương tự.

20:33 Vì bạn biết rằng việc băm nhất quán sẽ xác định vị trí một khóa trên một máy chủ, điều này có nghĩa là chúng ta đang thực hiện ít sao chép dự phòng hơn của dữ liệu.

20:41 Chi phí của việc này là mặc dù chúng ta đang thực hiện ít sao chép dự phòng dữ liệu hơn, nhưng chúng ta phải thực hiện các yêu cầu từ các máy chủ khách hàng trong một cụm đến các máy chủ mcash trong một tòa nhà trung tâm dữ liệu khác, và điều đó sẽ phát sinh thêm một số độ trễ.

20:57 Tiếp theo, chúng ta có khái niệm về việc vô hiệu hóa dữ liệu này. Cho đến thời điểm này, mình đã ngụ ý rằng cơ sở dữ liệu thực sự sẽ là nơi thực hiện việc vô hiệu hóa trên bộ nhớ đệm, nhưng mình chưa thực sự giải thích quá trình đó hoạt động như thế nào.

21:10 Một tùy chọn về lý thuyết là nếu mình là một máy khách ở đây và mình đang ghi vào một cơ sở dữ liệu, mình sẽ thực hiện ghi, và sau đó truy cập vào bộ nhớ đệm và nói "vô hiệu hóa".

21:23 Nhưng nếu bạn nghĩ về nó, điều đó thực sự hơi tốn kém. Về lý thuyết, bạn có thể phải thực sự đi và vô hiệu hóa nhiều bộ nhớ đệm. Ngoài ra, nếu mình là một máy khách, mình chỉ thực hiện một ghi tại một thời điểm, vì vậy điều đó thực sự hiệu quả hơn rất nhiều.

21:36 Mặc dù thật tuyệt khi chỉ vận hành các máy khách không trạng thái (stateless) và để chúng thực hiện những việc như vậy, nhưng điều thực sự hiệu quả hơn là chạy một quy trình daemon, về cơ bản chỉ là một quy trình nền chạy trên chính nút cơ sở dữ liệu.

21:47 Họ chạy một cái gọi là MC squeal, trong đó MC squeal về cơ bản chỉ đọc từ nhật ký WAL (Write-Ahead Logging) trên cơ sở dữ liệu, lấy tất cả các ghi mới, chuyển đổi chúng thành các lần vô hiệu hóa, thực hiện một loạt các lô (batch) và sau đó gửi chúng đến chính các bộ định tuyến MC.

22:02 Lý do tốt để thực hiện theo lô là để có ít chi phí hơn. Chúng ta có thể gửi nhiều lần vô hiệu hóa hơn cùng một lúc, và chúng ta không lãng phí băng thông mạng của mình.

22:10 Sau đó, các bộ định tuyến MC trong mỗi cụm sẽ tiếp tục và xử lý hàng loạt một loạt các yêu cầu, tìm ra tất cả các bộ nhớ đệm riêng lẻ và các yêu cầu đến nơi chúng đi.

22:23 Chúng ta đang thực hiện theo lô, chúng ta đang gửi nhiều lần vô hiệu hóa đến một cache cùng một lúc, và sau đó gửi chúng đến đó để chúng ta có thể xử lý hàng loạt càng nhiều lần vô hiệu hóa này càng tốt.

22:32 Nó sẽ giới hạn số lượng gói mà chúng ta gửi và tải trên tất cả các hệ thống của chúng ta ở đây.

22:38 Một điều tuyệt vời khác về việc vận hành MC squeal trên nhật ký WAL là nếu chúng ta có một máy khách ở đây và nó chịu trách nhiệm cho việc vô hiệu hóa, và nó ngừng hoạt động trước khi có thể đạt được việc vô hiệu hóa, thì bây giờ không có việc vô hiệu hóa nào.

22:49 MC squeal là một thứ có thể chạy trên nhật ký WAL liên tục, vì vậy khả năng phát lại (replay) sẽ tốt hơn rất nhiều vì nhật ký WAL cuối cùng được giữ trên đĩa.

23:01 Một khái niệm khác mà chúng ta có ở đây sẽ được gọi là khởi động cụm lạnh (cold cluster bootstrap). Một tập hợp bộ nhớ đệm lạnh hoặc một cụm lạnh chỉ là một tập hợp bộ nhớ đệm mới chưa có bất kỳ dữ liệu nào trong đó, đúng không?

23:11 Chúng ta cần đưa dữ liệu mới vào chúng, nhưng quy trình bình thường để đưa dữ liệu vào bộ nhớ đệm liên quan đến rất nhiều lỗi cache, điều này sẽ rất tốn kém và gây nhiều tải cho cơ sở dữ liệu của chúng ta.

23:21 Thay vào đó, chúng ta sẽ có bộ nhớ đệm lạnh này tiếp tục và trước tiên ủy quyền (delegate) cho một loạt các bộ nhớ đệm ấm (warm caches).

23:27 Nếu mình là một máy khách như anh chàng này và mình đang thực hiện các thao tác đọc, mình sẽ đọc từ cụm lạnh. Nếu đó là một Miss, thì trước tiên mình sẽ đọc từ cụm ấm và cố gắng nhận được một lượt truy cập thực tế ở đó. Nếu điều đó không hiệu quả với mình, thì

23:40 mình sẽ truy cập vào cơ sở dữ liệu. Với tư cách là máy khách, mình sẽ truy cập vào cơ sở dữ liệu và điền lại vào cụm lạnh của mình. Hy vọng rằng tất cả đều có ý nghĩa, đúng không?

23:48 Tuy nhiên, cuối cùng có một tình trạng tranh chấp có thể xảy ra ở đây.

23:52 Nếu đây là máy khách và chúng ta thực hiện một thao tác ghi, cơ sở dữ liệu sẽ vô hiệu hóa cả cụm lạnh và cụm ấm cho khóa đó.

24:01 Tuy nhiên, có một tình trạng tranh chấp. Có thể việc vô hiệu hóa này vì bất kỳ lý do gì mất 10 giây.

24:07 Nếu chúng ta tiếp tục cố gắng đọc khóa sau đó, chúng ta sẽ chuyển đến đây, chúng ta sẽ có một Miss, chúng ta sẽ chuyển đến cụm ấm của mình, và sau đó chúng ta sẽ đọc dữ liệu cũ vì nó chưa bị vô hiệu hóa. Sau đó, chúng ta sẽ tải lại dữ liệu đó vào cụm lạnh của mình, và bây giờ chúng ta có dữ liệu cũ ở đó, điều này sẽ gây ra vấn đề vì nó đã bị vô hiệu hóa.

24:28 Cách khắc phục điều này trong thực tế là khá "hacky" và gần đúng. Họ thấy trong thực tế nó hoàn toàn ổn. Về cơ bản, nếu mình là khu vực lạnh sau khi vô hiệu hóa, mình sẽ không tải bất kỳ dữ liệu nào từ khu vực ấm trong hai giây nữa.

24:43 Thay vào đó, mình sẽ tiếp tục và lấy nó từ cơ sở dữ liệu và coi nó như một Cache Miss bình thường.

24:50 Hãy nói về các thiết lập đa khu vực (multi-region setups). Như mong đợi, đây là một hệ thống cần có khả năng được sao chép địa lý (geo-replicated) vì nhiều lý do.

25:03 Thứ nhất, chúng ta có khả năng phục hồi tốt hơn trước các thảm họa như bão hoặc lốc xoáy sẽ lấy đi một loạt các trung tâm dữ liệu trong một khu vực.

25:10 Thứ hai là chúng ta có thể đặt dữ liệu gần hơn với người dùng, điều này đặc biệt quan trọng khi nói đến bộ nhớ đệm vì nó tiếp tục giảm độ trễ, đó là mục tiêu của toàn bộ điều này.

25:18 Cuối cùng, chúng ta cũng có thể giảm chi phí điện tùy thuộc vào khu vực mà chúng ta đặt những thứ này vào, điều này luôn rất tốt.

25:25 Một số quốc gia nhất định sẽ tính phí cho bạn ít hơn cho điều đó. Bây giờ đây là nơi mọi thứ bắt đầu trông rất giống với TOAO (TAO - The Associations and Objects graph database at Facebook). Về cơ bản, bạn đang sử dụng sao chép MySQL không đồng bộ trên các khu vực cho tầng lưu trữ, nơi bạn có một khu vực chính (primary region), và sau đó mọi người khác là người theo dõi (followers). Trong một khu vực, bạn sẽ luôn đọc từ cơ sở dữ liệu cục bộ và bộ nhớ đệm cục bộ của mình với một vài ngoại lệ nhỏ.

25:49 Điều đáng chú ý là tất cả các cache và xác thực đều không phải là về cơ bản đi từ cơ sở dữ liệu chính thẳng đến tất cả các bộ nhớ đệm trong các khu vực người theo dõi, mà thực sự sẽ được nhúng đầu tiên trong luồng sao chép (replication stream).

26:04 Việc vô hiệu hóa sẽ không xảy ra cho đến khi dữ liệu thực sự được áp dụng trên tất cả các cơ sở dữ liệu bản sao.

26:13 Nếu không, chúng ta có thể có một loạt các tình trạng tranh chấp, nơi chúng ta đọc từ cơ sở dữ liệu quá sớm trước khi luồng sao chép đó đến đó, và sau đó chúng ta tải dữ liệu cũ trở lại bộ nhớ đệm, điều này sẽ gây ra vấn đề.

26:25 Xin lỗi, nhiều trục trặc PowerPoint kỳ lạ hơn. Hãy tiếp tục và bây giờ nói về tính nhất quán đọc sau khi ghi (read-after-write consistency).

26:38 Đây là nơi mọi thứ trở nên hơi khó khăn, vì vậy hãy xem qua chúng.

26:42 Chúng ta có khu vực chính, chúng ta có khu vực người theo dõi. Nếu mình là một người viết trong khu vực chính, mình sẽ tiếp tục và ghi thẳng vào cơ sở dữ liệu, và mọi thứ trông rất bình thường.

26:52 Nếu mình thực sự là một người viết trong khu vực người theo dõi, đây là nơi mọi thứ trở nên thú vị hơn một chút.

26:59 Về cơ bản, chúng ta làm một cái gì đó được gọi là điểm đánh dấu từ xa (remote marker). Nếu mình đang ghi vào khu vực người theo dõi, mình sẽ thêm một điểm đánh dấu từ xa vào bộ nhớ đệm, về cơ bản nói rằng, "Tôi sẽ tiếp tục

27:12 và ghi khóa này ngay bây giờ." Như chúng ta đã biết, tất cả các ghi vì đây là sao chép một người lãnh đạo phải chuyển đến khu vực chính.

27:21 Nếu mình là một máy khách khác trong cùng một khu vực đang cố gắng đọc giá trị cho khóa đó, mình sẽ truy cập vào bộ nhớ đệm, mình sẽ thấy, "Tôi biết thứ này đang bị ghi đè," vì vậy bây giờ mình có thể tiếp tục và thực sự đọc nó từ khu vực chính thay thế.

27:37 Dữ liệu này sẽ được sao chép sang khu vực người theo dõi của chúng ta, và sau đó cơ sở dữ liệu như một phần của quy trình vô hiệu hóa cũng sẽ xóa điểm đánh dấu.

27:48 Về cơ bản, khi chúng ta có một điểm đánh dấu từ xa hiện diện, nó nói rằng hãy đi và đọc điều này từ khu vực chính thực tế chứ không phải khu vực người theo dõi cục bộ của bạn.

27:55 Họ đang giao dịch độ trễ và độ cũ, đúng không?

28:01 Bạn nhận được nhiều độ trễ hơn vì mất một thời gian để đọc dữ liệu từ khu vực chính, nhưng bạn không nhận được dữ liệu cũ vì nếu không, chúng ta sẽ truy cập vào cache và chúng ta sẽ chỉ đọc một giá trị cũ vì nó chưa bị vô hiệu hóa.

28:15 Hãy nhanh chóng xem qua một vài cải tiến máy chủ đơn (single server improvements). Ngoài toàn bộ hệ thống phân tán này mà Facebook đã tiếp tục xây dựng, họ cũng chỉ thực hiện một số thay đổi nhỏ đối với mcast để cố gắng tận dụng tối đa các máy chủ này, và sau đó một số thay đổi này cuối cùng cũng được mở nguồn.

28:32 Chúng ta có triển khai đơn luồng (single-threaded) này, và sau đó họ đã thay đổi điều đó thành một bảng băm đồng thời hạt mịn (fine-grained concurrent hash table).

28:38 Trước đây mcash là đơn luồng, họ đã làm cho nó đa luồng (multi-threaded), rõ ràng bạn sẽ nhận được lợi ích về hiệu suất ở đó.

28:43 Một điều khác mà họ đã làm là thực sự cho phép bảng băm mở rộng kích thước thay vì kích thước cố định.

28:48 Lý do là bạn cần một bảng băm lớn hơn theo thời gian. Nếu nó đầy hoàn toàn, độ phức tạp thời gian của bạn trên các lần tìm nạp sẽ trở nên tồi tệ hơn vì bạn sẽ phải thực hiện một loạt các thăm dò (probing) hoặc xâu chuỗi (chaining) hoặc một cái gì đó tương tự, và bạn sẽ tiếp cận thời gian tuyến tính.

29:03 Nếu bạn tạo một bảng băm lớn hơn, thì bạn có thể thực sự có được độ phức tạp thời gian tốt hơn.

29:08 Một điều khác cần lưu ý là mọi luồng duy nhất trong triển khai đồng thời đều có Cổng UDP riêng, điều này sẽ cho phép nhiều kết nối đồng thời hơn cùng một lúc.

29:17 Họ cũng làm một cái gì đó được gọi là "slab". TOAO đã làm điều tương tự.

29:21 Ý tưởng về các slab là các giá trị khác nhau trong chính hashmap sẽ có kích thước khác nhau. Bạn về cơ bản đặt mỗi giá trị vào lớp slab tương ứng với nó.

29:32 Có thể có một lớp slab một megabyte, một lớp slab 2 megabyte và một lớp slab 4 megabyte hoặc một cái gì đó tương tự.

29:38 Ý tưởng ở đó là cố gắng cân bằng tỷ lệ trục xuất (eviction rate) giữa tất cả các bộ nhớ đệm slab đó.

29:44 Cách họ làm điều đó là họ cố gắng cân bằng tuổi của mục cũ nhất. Điều này sẽ cho phép họ bắt chước một chính sách LRU (Least Recently Used) trên toàn cầu trên tất cả các bộ nhớ đệm slab đó, và nó sẽ hiệu quả hơn.

30:00 Cuối cùng, họ sẽ ít nhất cố gắng xử lý các mục có TTL (Time To Live) nhỏ tốt hơn.

30:05 Một số mục đi vào cache và chúng được dự định rõ ràng sẽ hết hạn sau một khoảng thời gian nhất định.

30:11 Mcash gốc đã thực hiện các lần vô hiệu hóa lười biếng (lazy invalidations).

30:17 Dữ liệu vẫn sẽ nằm trong hashmap, và nếu bạn kiểm tra nó và bạn thấy TTL đã hết hạn, bạn sẽ tiếp tục và loại bỏ nó hoặc thu gom rác (garbage collect).

30:23 Điều này đang chiếm một loạt bộ nhớ bổ sung vì có rất nhiều mục tồn tại trong thời gian ngắn này.

30:29 Dành cho các mục tồn tại trong thời gian ngắn, Facebook

30:32 đã triển khai một hệ thống nơi chúng sẽ thực sự bị xóa một cách háo hức (eagerly), và sau đó mọi thứ khác sẽ được thu gom rác một cách lười biếng.

30:37 Cải tiến cuối cùng mà họ có giúp ích rất nhiều cho những thứ như nâng cấp hoặc khởi động lại luân phiên (rolling restarts), nơi họ sử dụng khái niệm về bộ nhớ dùng chung hệ thống V (System V shared memory) cho tất cả dữ liệu trong mcache.

30:48 Điều này có nghĩa là bộ nhớ này vẫn tồn tại ngay cả sau khi quá trình kết thúc và khởi động lại.

30:52 Nếu bạn tiêu diệt một phiên bản của cache và sau đó bạn khởi động lại quá trình, bạn không cần phải có một bộ nhớ đệm lạnh và khởi động lại. Bạn có thể lấy lại dữ liệu của mình thực sự nhanh chóng vì nó sẽ ở trong cùng một địa chỉ bộ nhớ.

31:06 Hãy kết luận cái này. Về cơ bản, ý tưởng ở đây là giống như nhiều hệ thống khác mà chúng ta đang thấy gần đây, việc tách một loạt các tầng riêng lẻ ra là thực sự tốt vì bạn có thể mở rộng chúng một cách độc lập khi cần thiết.

31:18 Trong trường hợp này, đó sẽ là tầng bộ nhớ đệm của bạn mà bạn đang mở rộng một cách độc lập vì cuối cùng bạn có rất nhiều yêu cầu, tất cả chúng đều truy cập vào rất nhiều dữ liệu tương tự, và bản thân dữ liệu không lớn lắm. Bộ nhớ đệm sẽ siêu hiệu quả, và bạn không muốn phải xây dựng một loạt cơ sở dữ liệu bổ sung chỉ để chạy bộ nhớ đệm cục bộ ở đó.

31:37 Có một tầng riêng biệt là rất tốt, bạn có thể tự mở rộng nó. Nó cũng tốt vì việc gắn các bộ nhớ đệm riêng lẻ vào bất kỳ cơ sở dữ liệu nào bạn đang sử dụng không cho phép bạn mở rộng điều đó để sử dụng các nguồn dữ liệu khác nhau.

31:49 Bộ nhớ đệm sẽ có được hiệu suất đọc tốt hơn nhờ sử dụng bộ nhớ thay vì đĩa, và cả những thứ như hashmaps.

31:58 Nó cũng sẽ ngăn chúng ta có một loạt các "thundering herd" (đàn gia súc giẫm đạp) trên cơ sở dữ liệu của chúng ta.

32:01 Nếu bạn có 100 máy khách đọc từ cơ sở dữ liệu đồng thời, điều đó sẽ gây ra rất nhiều tải cho nó. Một hệ thống có thể trả lời và phản hồi rất nhanh chóng tất cả các yêu cầu đó qua UDP và đa luồng sẽ giúp quá trình đó dễ dàng hơn rất nhiều và ngăn cơ sở dữ liệu nhận được rất nhiều tải.

32:17 Một điều khác mà họ làm điều này là triết lý thiết kế về phía họ là chọn sự đơn giản các thành phần không trạng thái như máy khách. Máy khách chịu trách nhiệm giữ cho bộ nhớ đệm đồng bộ sau khi chúng thực hiện thao tác đọc, và điều đó hoàn toàn không trạng thái, đúng không?

32:30 Máy khách không nhớ bất cứ điều gì, nó chỉ gọi một hàm đọc cơ sở dữ liệu và sau đó gọi một hàm khác cập nhật bộ nhớ đệm.

32:36 Rõ ràng có tất cả các loại hàm ý về các lỗi một phần ở đây, nhưng họ thấy trong thực tế mọi thứ không quá tệ.

32:45 Cuối cùng, họ chỉ muốn bao gồm các tính năng trong memcache giúp cuộc sống của mọi người tốt hơn một cách tích cực.

32:48 Họ không muốn làm mọi thứ trở nên phức tạp và xây dựng tất cả các giải pháp "half-baked" (nửa vời) chỉ giúp một tỷ lệ phần trăm người dùng.

32:53 Về cơ bản, họ chỉ muốn triển khai một thay đổi nếu nó có tác động lớn.

32:59 Dù sao đi nữa, các bạn, tôi hy vọng các bạn thích video này. Cổ họng của tôi đã hơi đau vào cuối đó, nhưng không sao.

33:04 Bạn có thể gọi tôi là "dê họng" (goat throat) có lẽ... đừng thực sự, và tôi sẽ gặp bạn trong cái tiếp theo.