CMU Database Group · 1:19:21 · https://www.youtube.com/watch?v=mbelzgz-97s
1. <Untitled Chapter 1>
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:28 pistol is that how you should bu system yes we laugh but like that's actually what big databas vendors do right they they there's some standard benchmarks like tpcc tpch TPC DS the queries are you know the things the quer has been around since 1992 you know what the schema is so you say okay well like if I know exactly what workload you're trying to test me on I'll do some shortcuts and make things faster so for example on tpcc there's a there's this table for the warehouse like think of like it's like an Amazon fulfillment center so there's a warehouse there's a district and customers customers have orders customers have items right so this tree structure the nor Warehouse is limited
1:09 and you never really update that table so instead of defining a B+ tree when you call create index you say all right well I know a table this is a warehouse table for tpcc I'll just make an array
1:19 then you're jumping in exactly the right offset to find things and it's super fast like an array where you know exactly the the the the offl set to jump into it's way faster than a B+ tree that's 01 uh so they do tricks like that so his question is like is it okay to optimize your datab system just for the workloads we're giving you yes but yes but in Industry you're not supposed to do that but people still do it
1:42 right all right let make sure we're recording all right so a lot to cover a lot to get uh let's get started um so this is another good one right this is this is another key aspect of what we want to build in our database system to make sure you know people can actually save their data not lose anything and it's why you don't want to write your own you know databas system if you're building an application you want to use an existing one because this is going to be hard all right again for everyone uh in the class project 3 is due this Sunday uh we have the Saturday office hours coming up on the 16th this Saturday 3 to 5 same location same location and Gates on the fifth floor
2:16 project 4 has been posted last night uh and that'll be due on December 8th which I think is the the week right before the finals and then again the final exam will be due on December 13th um or will be at December 13th uh I forget where the room is but it' be 8:30 a.m. okay again don't travel before this date there won't be a you can't come and take exam early
2:39 okay all right so last class was the was us wrapping up the discussion on concurrency control protocols uh and in particular we looked at last class we looked at multiversion conc control and despite the name being concurrency control the the concept of maintaining multiple versions in a database system is going to affect the entire architecture or we saw at the end of the in case indexes your index is kind of to be aware like oh I may be pointing at different versions of the same logical Tu same pH same logical Tuple and you have to account for that and the execution engine has to be aware of these things all parts of system have to be aware of it um so for concurrency control the the protocols that we talked about are going to provide us with atomicity consistency and isolation
3:22 guarantees right of the four things in acid and so the big thing that we've been dancing around are not really discussing and I've mentioned it for a little bit you know oh this is the right how log will handle this right but the the the last piece of the puzzle we need for acid is the D durability now we're also going to Al rely on recovery protocols to give us atomicity as well in case some transaction write some stuff to you know to a database and half it makes the disc and half doesn't make the dis right we we need to handle that case case as well so right so it should be pretty obvious anybody here why we want durability in our database right but the basic setup something like this
4:01 right we have our transaction uh running T1 and when it calls begin the it starts reading a and so that's not in our buffer pool so we're just going to go out the disc and and fetch that in put that in a frame we talked about before you got built that in Project one we know how to do that that's fine now they go ahead and do a right on a right and that's no big deal we just apply the change to the the record or the object
4:26 in a page in our in memory in our buffer pool right and then that's fine and then now when they go ahead and commit right the guarantee or the the the property that we want to provide under under acid is that if we tell the outside world upon commit that your commit was successful then no matter what happens to the database system within reason right if it catches on fire and melts like you're still supposed we still have to handle that but we'll get that in a second like but if we tell the outside world that yes your transaction is successful committed
5:01 then no matter what happens we they should be able to come back and read that data right so let's say in this scenario here we tell the outside world that your transaction is committed the worst person in the world comes along zaps the the you know the the the power station for the the data center that's running your database system and your buffer pool gets blown away because it's in memory right so now of course the problem in this case here going back
5:26 this this transaction modified a equals 2 we told the outside that committed but we never put it actually on disk so now when the system comes back assuming we get power again when we go fet to that page back in we're going to get a equals 1 again under asset properties of durability that should not
5:44 happen so today's class and next class will be about how to handle the situation and the This falls under the broad category of description of of of recovery recovery protocols for database system and again it's going to provide us the consistency durability and anity guarantees we need despite there being
6:02 failures right so if it you know if transaction rolls back on their own we got to make sure we clean that up if a the power gets pulled and we told the outside world transaction committed we have to go clean that
6:14 up now it may be this in some case that we a transaction go ahead and commits and we say it's committed but we but we about to send the message back to the client to the application say yes your transaction committed in that case if the power goes down before that message gets sent that transaction still considered committed CU depending on the recovery protocol we're going to use uh you know changes what made it to nonvolatile
6:39 storage all right so recovery algorithm is going to have two parts there's be the first part we're going to talk about today are all the extra things we're going to do while transactions are running so that we can handle the situation where there there might be a failure right so we're do a little extra work while our transactions are running to make sure that we can always recover things later on next class will be dealing with the situation okay after we've come back from a failure like we got power back the system comes back on
7:07 we have to look around at our disk and figure out okay what was the state of the system at the moment of the crash and try to put us back into the correct state so today's class is is preparing for the failure next class is how to handle the failure
7:22 okay so the the so the overall outline is first we got to discuss obviously what's going to happen in the buol right because that's where we have to Stage all our changes in memory so we have to understand what's going to go what's going to happen what what if the buff allowed to do to prepare ourselves and then we're going to talk about two different protocols uh Shadow paging and right ahead logging the spoiler is going to be right ahead logging is the approach you're going to want to use and most systems are going to use this
7:47 Shadow paging is what they invented at IBM back in the the very first system and system R some systems still do this today uh but in practice you don't want to do this right Ahad logging is always going to be the superior choice then we'll talk about what we're actually going to put in the rad log uh and then we'll do a preview of what checkpoints are going to look like uh and I'll explain what that is as we go along and then that'll segue into next class where we talk about how to uh do a better version of checkpoints and then load the checkpoints back in and then we have a a a speaker today coming from confluent
8:18 which the the big company backing uh building Kafka okay all right so as been as we talked about since the very beginning of the of the the semester this whole class has been about assuming we're we're dealing with disoriented database systems where the primary storage location of the database is add on some kind of nonvolatile storage a disc a spinning disc hard drive an SSD
8:40 cloud storage it doesn't matter and then we obviously have to use the classic one voman architecture where we copy pages from disk into memory and operate on them in memory because that's going to be faster for us and then we some algorithms and choices we're going to make to allow us to maximize the amount of sequential access for Reading Writing data from from dis that's going to be slower than Random Access whereas if if it's in memory it's in we do random access very
9:05 quickly so if we got we got to modify something we're going to first copy the the pages into memory perform the rights on the pages in memory and then we got to write back these dirty records out the disk because again if we crash you're going to lose all the contents of of dam the research basically says you get 30 seconds of dam you can actually still read things uh but all your program counters everything else is get blown away so you definitely need to make you know get out on disc if you want to retain
9:31 them so the thing we got have to guarantee is that again any transaction uh any for any transaction we told the outside world that you've successfully committed we have to guarantee that their changes are durable right and of course now that also means that we can't have any a a partial changes like we tell if a transaction didn't complete we don't want to retain half the rights they made to disc and because the other half was still sitting in memory because then you would have torn updates and that wouldn't be that would violate the adity
10:02 guarantee so the two key Primitives I'm going to rely on to achieve this are undue and redo right and they're they're exactly as they sound right so the undo is going to be the process of removing changes of or effects of of transactions that did not complete successfully right because they aborted because the the transaction said abort or the system crashed or the data system says you know because of two-phase locking or OCC they weren't allowed to commit so you have the
10:30 it doesn't matter the transaction is considered not not committed and then the redo process is just saying that okay for any transaction that did commit again where we told the outside world at least attempted to tell the outside world that your transaction has committed then we need make sure that all of their changes are are are retained when we come back now again another transaction May overwrite those changes from another you know from a pevious transaction that's fine but we you know we still need to make sure that every transaction that is committed everything's written out
11:00 so now how we're going to actually do undo and redo is going to depend on what the buffer pool manager is going to do for us so now we're going back to project one we're actually going to modify it a little further because it needs to be a bit smarter about what's going on in the system to make sure that we can recover if there's a
11:15 crash so here's the basic idea so say we have two two transactions now T1 wants to read a write a and transaction T2 wants a read B and write B right so they're not they're not conflicting we're still going to run two-phase locking or OC whatever protocol you want on top of this right the these different layers are are uh somewhat interchangeable but for this transaction they're commutative so there's no conflicts there so assum we have nothing in our buffer pool at the very beginning
11:39 T1 starts does a read on a so we know how to go at the dis fetch that page we're uh we're a object a exists assuming we have one page fetch it in our buffer B that's fine then we go ahead and do our our right on a all right so then we sorry then we update the record here set it to A3 now the Contex switch we come over here we do a read on B well that's already in our buffer pool so that's fine we're good there now we do a write on B again it's in the same page where a was we go ahead and update and that's fine and and we're
12:08 done and then now though T2 wants to commit so what do we say right any transaction where we tell the outside world that you're you're that it's committed we got to make sure that its changes are written at the disk okay well what if I go ahead and and write out this this page here write out the dis what's the problem with this
12:32 T1 updated a right those changes are in the same page where where T2 modified B and they went along for the ride because they're in the same page because can you can't do bite addressable updates you got to do page based block based so this 4 kilobyte page with they change to A and B got written out when B committed or sorry T2 committed so now we tell the outside world T2 is committed that's fine so it's durable but now we have the problem where T1 needs to roll back
13:00 all right but now we we got to go back on dis and undo the change we did uh on a right so that sucks now right because now we gota if we just we just wrote everything out when this guy could went to go to commit it's going to get a bunch of stuff that maybe from transactions that haven't committed
13:19 yet so that's obviously bad so the policies we got to be aware of there's two two decisions we can make in our profle manager and the first one's going to be uh called the steel policy and the second one's called the uh the um the force policy so in the steel policy it's going to it's it determines whether the the database system is allowed to evict a dirty object from the buffer pool so a dirty page in our last example that was modified by a transaction that has not committed yet so even though T2 is modified it and they're going to commit
13:52 there's still another dirty change in there from T1 T1 is not committed and the issue is going to be is that if we write out that dirty object to dis assuming again assuming it's a page then it's going to be overwriting on disk the most recent committed version of of of that object from another
14:12 transaction so with the steel policy enabled you're allowed to evict 30 pages uh before transactions committed and you essentially by by the byproduct of that you then overwrite the thing the the most recently committed version on on disk if you do no steal then you're not allowed to to do any eviction or overwriting meaning every every page in your buffer pole that has been modified by transaction has to stay pinned in there it cannot be
14:41 evicted so what we'll get to with the the red head logging is going to be using the steel policy right because if we're allowed to evict things that from uncommitted transactions then that gives the buffer pool manager replacement policy the lru K piece you guys built it gives it more options on how to you know what frames it can free
15:03 up right under if you don't if you do no steal then everything that a transaction modifies has to stay in memory and of course that means that if you have if the transaction modifies more pages then you have memory for them you're screwed because you can't evict anything
15:21 out the other policy is called the forest policy and this just says that when a transaction commits is the data requireed to write back and flush out all the changes for those dirty pages to the dis before we we tell the outside world that your transaction has
15:38 committed so if you do the force policy enabled the the right back is required mean when when a transaction calls commit anything they modify in the buer pool has to get written out if you do no Force you don't require
15:52 it so forcing is going to make it easier for Recovery because before I told the outside word you committed all your changes are on disk fantastic so when I crash come back I don't have to do anything right because I know if I told you you committed then everything's on disc and everything is is is correct because that's going to be slow now because now when I call commit I gotta flush everything and I've updated a billion tupal that I gota wait for all those billion tubes get
16:18 flushed so let's go back to the example we had before but now we're going to do no steel Force so no steal says again that no dirty Pages can be evicted from the buffer pole before transaction uh commits and for says when a transaction commits with then that's that's when we flush everything
16:35 out so again we do the read on a f buffle that's fine we do the write on a it updates the page says it A3 that's fine then context over to T2 T2 does does a read on B that's already buffer pole we're good there T2 does now the write on B uh and updates the page there now it wants to commit so again under the force policy when we call commit all the dirty pages that T2 modified have to be flushed to disk but of course we have the other problem with the the the conflict now is that under no steal
17:09 we're not allowed to write out any dirty pages from transactions that have not committed yet or any changes and because again we're dealing say 4 kiloby 8 kiloby Pages we have two tupos and never got modified one got Modified by T2 one got Modified by T1 now we have this conflict where like we want to flush this thing out but we can't because half of it half you know part of the changes can't be flushed out
17:29 out so a simple trick to fix this is just copy the page in a Breer pool but only include the changes from the transaction that did commit and then now we go ahead and write that out so then now when we come back over here and T1 goes and tries tries to roll back now this is Trivial to do because there isn't any you know none of this it it didn't modify any nothing that it modified made it out a
17:56 dis so at this point we crash we've already told T2 the the told the outside world T2 is committed so that's fine so we crash come back this thing is correct because it has changes from T2 but not
18:12 T1 do you think it's a good idea or a bad idea why is it bad it involves copy it says it involves a copy the M Copy correct yes so this part sucks right again it's on PowerPoint it's three three cells and a page whatever nothing I update a billion pages I got have a billion copies to remove anything you know say in a highly concurrent system you know thousands transactions running at the same time I got to keep track of what all pages they modified which you're sort of doing anyway but now I got to make copies of them to figure out what's the know what's the bare minimum I need to have to write something out the
18:48 desk right so there's a lot of overhead involved in this you don't you don't want to do this it does make again recovery easy right and it's it's pretty easy to implement right you never to undo undo changes from a board of transactions upon recovery because nothing got written a dis right you have to redo changes either because on the force policy you know that when you told the outside where the transaction committed all the changes are out on the dis so when you come back everything's just there
19:17 right like I said but you still have to maintain the right sets about what the transaction changes they making and that may you may run run out of memory pretty quickly if you make a lot of changes so again no system will actually actually do this a side comment also say too is the you actually burn out the hardware pretty quickly too so on ssds they have actually a limited number of wrs so if you just write to the same cell over and over again I mean it's in the hundreds of thousands but again if you're if you're flushing every transaction for every single page you'll burn it out pretty quickly right so the way the harbor vendors get around this is like you know you buy 128 gab SSD
19:56 there's really like 150 GB on there right you just can't get to it all because they know the cells are going to burn out and they just replace it with ones that uh that are uh you know that are that have le less wear leveling but eventually you'll burn it out right no no no no device is going to last forever
20:14 so again if you're flushing 100,000 transactions a second all the pages they modified on a single SSD you'll you'll you'll burn through that pretty quickly all right so we want to be a little smart about this all right and not have to make entire copies every single time
20:30 so this is what shadow paging is so Shadow paging is going to be a no steel Force bufferpool policy where instead of copying the entire database every single time we're basically going to be doing what what I just showed before we're going to be copying pages but we're not going to allow multiple transactions to update the same page at at the time same time so now when I have to do a a flush them out the disc I don't have to excise out the parts from from uncommitted transactions
20:59 like I said this is what IBM invented its system R in the very beginning this is what a lot of the early datab systems uh implemented in the 70s and ' 80s right Ahad loging came around late 7s early 80s and that's everyone switched over to that we'll see why this is going to have a bunch of problems other than the ones i' I've already talked about so to keep it really simple we're going to assume that we have a there's only one writer transaction at a
21:24 time uh and then you can have multiple read read transactions so in some cases in in SQL you actually can call begin when you start a transaction you you can give a hint and say I'm going to R read only and the day can can be aware of that and do some optimizations
21:38 accordingly so the there be essentially two page tables and you think of that as the page directory of like pointing to here's the latest version of of or here's the here's the page for this this for this page number within this copy of the database and so there'll be a Master Copy that's only going to contain changes from committed transactions and then the shadow copy will be a temporary space where we'll only we'll we'll apply the changes for uncommitted transactions
22:04 then when a transaction goes ahead and commits we flush out all those dirty pages from the shadow page table and then we have this pointer that says uh here's you know here's the the latest here's the current Master page table and we just swap that pointer swap you flush that out the disc and now we're pointing to the the old Shadow becomes the the current Shadow becomes the do
22:24 Master right so let's let's look how those look and this is basically what how copy and WR works if you ever do uh like in Linux like Linux is trying to do copy and WR it's basically the same idea all right so we have again we have in memory we have on disk we have this master page table right and then when a transaction comes along assuming that we're declaring that that were a a read write transaction so we'll make a a shadow page table which is copying the the current Master page table and all the pointers think of like the the the mapping of a page ID to some some page on disk all the pointers are going to be exactly the same in the very beginning
23:01 we're just because we're just going to point to the latest version of the database but then now if they the transaction modifies a page that the first time that it tries to modify a page like page one we're going to make a copy of the page on disk and in our buffer pool write our change uh to that and then and we do this for all the other changes so we're just basically replacing the links on our page table to copies of the pages uh for this particular
23:29 transaction now if any other transaction comes along that at this point and is readon then they'll look at the the the master pointer record and you'll see okay here's the here's the location of the master page table and so it'll run all its transactions uh and read all the data it wants from from the the master page table so it's seeing the older version of the of the database doesn't see any of the changes that the the the writing transaction
23:56 made then when the writing transaction go goes to commit right we flush all uh any any pages that it made any changes to made to the in the shadow page table those get written out the disk we then have to go update the master pointer record think of like it's in the header of the database file or some special location to say okay this transaction is committed and now the master pointer is going to point to this page table and this becomes the new Master page
24:22 table then again any other transaction that comes along say it's read only they're going they're going to they're going to see these records of course now we got to go ahead and clean up the the old Master page table so it's just like sort of garbage collection we saw and mvcc right mvcc had multiple versions you could have like you know every transaction is updating the same record
24:43 uh you you know have a long version chain this is basically a two version system so then we got to go ahead and and clean this up reclaim the space and then we'll just repeat the process the next the time next transaction comes along
25:00 so what are some problems with this yes it wouldn't work very well with multiple transactions he said would not work very well with multiple transactions yeah so be so the way you would have to if you want to handle multiple transactions you'd basically have to run them in sequential order I mean actually it's not really true you could still do two-phase locking or OC on top of this uh and you could allow them to to inter leave each other and you still protect the you know protect tupal and Records this is before but when when it goes time to commit if I have one if I have two transactions in a batch that I run one transaction finishes at 1 millisecond the other transaction finishes in 1 second the one millisecond transaction has to wait until the 1 second transaction finishes
25:43 then they go ahead and commit everything so you basically run things in batches the idea of having a single writer thread and multile reader threads that's not that outlandish that's what site how SE light works right and works pretty
26:00 well so recovery is super easy in this roll back is super easy as well if a transaction aborts what do you do drop the the shadow page table and just clean it up as if it was you know garbage like you would later on and then when you crash and come back it's super easy as well because as long as this pointer got updated then I know that the transaction has successfully committed and so when I crash and come back I don't I ignore anything that's in the shadow page table and the master page table has always the the latest version of the database system of all the Comm committed
26:33 records so undoing this is is easy because you just blow away the the the the shadow pages and leave the master and the and the database route alone and then there's no redo needed at all because when you come back everything G to be there yes uh I'm trying to understand this context within like the buffer pool manager context um so I understand that the master page table and Shadow page table lives in like buffer pool Manor in memory yes um but like the actual pages that was being modified like pointed by these page table pointers does it bypass do they bypass the buffer for man direct the no question is like what are these boxes what are these erors basically on dis right so this this is just the page table we had in your buff manag before
27:14 but now you basically partition it and say like here's the shadow pages and here's the the the master pages and then you would do copy on right so I'm showing the arrows happening like when say it's going back here when this guy modified one right you would recognize okay well I'm pointing to now the a page in in the master page table so I'll make a copy of it in my buffer pole so I can make changes to it and then at some point I got to make sure I I then write that out the dis as well so in this case here because it's a it's a no Ste steel
27:47 flush um that when a transaction commits that's when you write all the dirty changes out from the the P the shadow page table out on the disc for for illustration purposes I'm just showing it as they were as they were happening
28:00 but that obviously would be slow Okay so we've covered a lot of these before uh but why this sucks right so the the copying the P Tire page table is expensive right uh and then the overhead of commit is is high because you have to do that flush you have to make sure that everything gets gets written out another big problem is that and this is what the the IBM people saw uh when when they first built this is
28:30 that before all my data was nicely uh contiguous and thinking add- on dis so going back here before I made my P my shadow Pages everything was contiguous so now if I want to do a sequential scan I just read the pages one after another
28:45 but then after I've you know I've run a transaction and then I've cleaned things up now I got empty space in here that now all my data isn't contiguous so now I can't maximize the amount of squential iio I I can do so time things get fragmented and you got it basically uh you know clean things up you guys are appli to Young for this but the old days of the hard drive there us be like a defrag command uh that You'basically just repack everything like like like almost like running vacuum full and postr so you basically have to do the same thing
29:19 here so SE light actually started off doing something a little bit like Shadow paging not exactly um but they had this thing called the rollback mode the first versions of sqlite came with this and then I think 2010 uh they then added the right ahead log for for performance reasons obvious reasons right so the way SQL lights roll back mode would work is that you have your pages in memory you have your your your database on on disk but then you have this other file on the side called the journal file so that now when a transaction wants to modify a page right you you bring it up from the disc bring it into your buffer pole and then you would immediately copy it out into the journal file before you made any changes to
30:04 it then now uh you can go ahead and make your change in memory do the same thing for for the next page here make a copy of it write it out to the journal file and then now if when the system crashes sorry sorry say you you you say some of the changes got written out the dis for page two but then now the system crashes before you write write out page three at this point here you would know the transaction has not successfully committed
30:28 so the buffer pull in memory gets blown away but then upon recovery the very first thing you do is look for that journal file and then you copy back the the pages into into memory and because you know these are the the original versions of the pages before a transaction that started modifying them uh made any changes and then you just go ahead and just blindly copy them back out to disk to say because you know this was the correct version of of the database for these Pages before whatever transaction was running made any
31:01 changes right again stle light has a single writer thread so they're not worried about a bunch of changes being made uh to Pages by multiple transactions they know that there's only one transaction could be modifying things so either all their changes could should get applied or none of their changes get
31:16 applied so then I think when a transaction commits they just delete the file Mark the journal file as no longer needed so then when you come back you know not to uh reverse changes from a committed transaction so another big problem with these approaches is that
31:33 the they're requiring the data system basically do a bunch of non nonsequential rights to disk right remember we said that that was one of the big design decisions we wanted to do in the beginning is that we want to choose algorithms that may actually be not the most efficient way but you know on pencil on paper but because it'll maximize amount of scal IO we can do we'll get better performance so that shadow paging stuff or in the going back here right in my my SQL light example
32:02 Jal file that's sequential IO because I suck that into memory that's fast right but you know I'm showing page two and Page Three being updated but like but what the the the updates the pages were scattered around the file now I'm doing random IO to go correct the database and that's that's going to be bad that
32:20 sucks so we want a way to convert you know random rights to disk into sequential rights because that's always going to be much faster and the way we're going to do this is through the right Ahad log and as I said before this is pretty much the approach that every datab system that's out there today they're going to be doing something like this there might be some you know variance to what they're actually storing the right head log uh when they actually flush group commits
32:47 there's a bunch of tweaks you can do to this but at a high level this is what everyone's doing so the idea now is that we're going to maintain a a log file that's going to be separate from the the Heap files of of the database where the tables are and the log file is going to contain the bar of information you need to know what change a transaction made
33:09 to uh to to an object in the database and what was the state of that object before that change was applied you can store some extra stuff in there like check sums and time stamps and things like that but the bare minimum you need is here's the transaction that that's making the change here's what they're changing here's what it was before so I can do so I can do redo or sorry I can do undo and here's what it should be after so I I can do
33:34 redo and the key thing we're going to have to do to make this all work is this part right here is that if we tell a transaction tell the outside order that a transaction is committed then we need to guarantee that all the changes that it made to the database the the corresponding log records for those changes are flush to disk and before we're allowed to write out any dirty page from the buffer pool out the dis we need to make sure that the log records that made that that page dirty those are flushed out the dis
34:04 first so again going back to like think about like I I drew that diagram of like here's all the levels and then now we're adding recovery and currency control and and it encompasses everything because now we need to be now our buffer B manager needs to be aware of what transactions are what changes they made needs to know what log records are because now when it runs it's eviction policy it has to know okay the the log record for this that made this page dirty that's safe on disc I can go ahead and evict it or this other page is dirty
34:32 it's log record is in on dis I can't evict that because I would violate this guarantee and could prevent us could cause us to lose data so this approach is going to be using the steel no force is a buffable policy so steal means we're allowed to evct pages from uncommitted transactions
34:49 if those log records for that uncommitted transaction have been written a disk and no Force means that we don't require us to flush out all the dirty pages in our profer pool when a transaction commits we just have to make sure that the log record has been flushed out to
35:03 dis so you sort of think of like the different choices now in the quad chart right the doing steel steel no steel Force like in Shadow paging that's trivial to do right but it's going to be suck sucked for performance we want to be in this upper quadrant here we want to be uh we want to allow us we want steel to be turned on because we want to be able to evict things before things before transactions are committed that gives us more flexibility and can make more room for for for data as we need
35:32 and then we want to be able to not require Force because when a transaction commits we don't want to flush everything out which could be a bunch of random Io if we just flush out the log record well that's depending to a file that's sequential IO we can make that fast and work
35:47 well so again with Force it's going to require us to flush every page uh when trans commits but get poor response time uh with a no steal we're going to get bad performance because we have to keep you know we're keeping pages in memory
36:04 that we could have been used for new data that we may need for other transactions um but it's really easy for a boarded transactions because nothing got nothing got written dis and in this case here no force is be great for us because uh well it's it's G to if a if a
36:20 transaction fails the system crashes before it's before thing it's written out we got to be able to redo the changes and so we'll handle that with the rad log and then with steel this allows to flush out dirty Pages even before even a transaction that's updating it is still active because that we can reclaim that memory for other transactions that are running so we want to try to hit this again the top quadrant here in the top
36:44 right so the way it's going to work is that there going to be this log buffer space uh it could be backed by the buffer pool typically not not always but it's some dedicated space in memory where we're going to stay all the changes from transactions for all the log records for those changes and then we keep track of of of a way we have a way to keep track of like a log sequence number we'll cover next class we know the order in which these log records are getting applied
37:10 and then we know the the log record number that corresponds to a change that that made was made to a a page so that when a when we decide whether to evict a page under the steel policy we would know is the log record what's the what's the watermark what's the threshold for the log record numbers that have been written in disc and therefore I know anything that was modified by log records prior to that are durable in dis and therefore I can evict
37:35 it and as we said before a transaction is not considered committed we don't tell the outside world that your transaction is is safe and durable until we flush all the log records out to to non-bal storage now 30 secret is a bunch of systems actually don't do this by default right so everyone know what fsync is fsync is a blocking call telling the operating system that do not return to me until I know all my changes have been written or safe on disk um and so in some systems you call commit and it'll come back say yep good you're committed and then eventually it it it actually get flushed out so you can turn
38:13 synchronous commit on but you obviously going to pay the penalty that and we we'll performance penal we'll see how to make that faster in a second but most systems by default don't give you uh you know synchronous commits it's like good enough like if if you're okay with missing maybe if there's a crash you might miss the last 5 milliseconds that might be okay for some people some
38:34 applications all right so the protocol is uh when a transaction starts we're going to append a begin record to this log buffer we have in memory now most systems you know I'll show this for for completeness and in the in the diagrams in most systems you may not even store the begin record until you see the first query of a transaction so just just because you call begin doesn't mean you actually start writing anything
38:58 um in other systems you don't actually put a begin at all because you know the soon as you first time you see a query well that's the beginning of a transaction so that's the starting point but for Simplicity we we'll assume that there's always an explicit
39:11 begin and then now we're going to have a log entry a log record for every single change we make to an object and for this we're going to store four things transaction ID uh you know the transaction that made the change an object ID of what was modified by the transaction and then the before value that we would need to do undo and then the after value that we need to do
39:35 redo as I said in in different systems we'll have additional information maybe check sums timestamps and other information we'll see what uh we'll see different actually the logging schemes you actually store like here's the page number here's the offset here's the slot number there's a bunch of extra stuff we can store in there but for for now we won't put anything else and then actually as as I said last class the original version of postgress they really didn't do right ahead logging because they were doing a pendon mvcc
40:01 and they just assumed that the since I'm always making a new tupal uh if I have a way to say whether transaction is committed and write that out to the log and then I don't need to go back and and reapply any changes because I'm always doing copy on right so if you're not doing a pend if you're doing a pend MCC which most systems aren't uh then you you can get by without not having to sted the undo because you're always going to have the original version of the tup
40:28 so then now when a transaction finishes we're going to pen this commit record to the log and then before again before we tell the outside world that you're committed we got to flush the the the log up into that commit point or maybe even a little bit farther depending how we batch things up and then once that's D on the disc then we can acknowledge to the application to the outside world your transaction has
40:51 committed so let's see what it looks like so T1 starts it wants to do right on a and right on B so when it starts calls begin we add again we add a begin entry to our log again this this makes it look like the redhead buffer log space in memory is much larger than the buffer pool this is always going be much much larger right but for some make it fit on PowerPoint I'm just you know showing it approximate size whatever all right so we go we call begin so again we add we add a begin entry to the right hand log then it does a WRAL name so the very first thing we're going to do before we modify the page is we're going to put a log entry in uh with with T1 the transaction ID the object remodified
41:28 and then the before and after value then we go ahead and modify the page because we actually want to record in the page we'll see this next class we'll record actually the log record number the log sequence number of the change that we're
41:43 making so we need we need to put the entry in the log log first the buffer first before we make the change now we do a write on B same thing I'm going to pen the log entry in in the buffer go ahead and apply the change to the the
41:58 page then I go ahead and call commit and then now this point assuming there's no other transactions running I'll flush the log buffer and append it to the to the the log file out on disk and at this point again when we get acknowledgement from the hardware through the operating system or if we're doing you know if weing if you're doing uh the direct IO yourself like when we get the acknowledgement from the harbor that our changes have been flushed then we can tell the outside world
42:27 transactions committed because now at this point it doesn't matter whether this buffer pool actually the page dirty page actually makes that to the disk right if if we now crash this all all the the contents of memory get blown away everything we need to replay that transaction is out in that right ahead log we finally begin we we we scan through and say okay what the first thing we did was update a all right here's the value it should be and then update B here's what the value should be so we can recreate the page that was modified by the transaction
43:00 just through the wrer head log is that clear and now the benefit all set too is as I said this is all sequential IO right because I'm just appending the log wrri writing out cous uh data out the disk that's going be way faster than if I updated a lot of pages and have to do a bunch of random
43:22 IO right so now the the committing the transaction is is is much much faster furthermore Al you think about it too like if I update a billion tupes and say there's one billion tupos across one billion different pages right if I got to flush all the buffer pool pages I have to flush all 1 billion Pages which you know 1 billion times for 48 kilobytes versus the log record or have 1 billion entries sure but the amount of data I have to flush out is going to be much smaller than you know bu of bunch of 8 kilobyte rights
43:58 and that's all going be sequential because it's all be continuous memory I just write that all that out of course now the problem is going to be if I'm flushing every single transaction when they call commit that's going to be a
44:14 bottleneck right because the right time for ssds it's about you know about a millisecond 1 to five milliseconds that sucks if you have to go to S3 and forget about it that's 100 30 100 300 M plug so one trick we can do that was sort of similar to the example that I brought up when we were doing Shadow paging of batching things up we actually can batch together a bunch of uh transactions that committed right they're all allowed to
44:42 uh pend to the log and we we don't have to worry about having a single writer thread they can depend in any order that they want right because because up above all this is going to be the conero protocol that's determining who's allowed to modify what data at what time so all that still still is in place
44:58 but then now I'll batch up their changes to the right hand log so that there'll be some timeout every five milliseconds or so then I'll say okay whatever's in the buffer now that's going to get written out the
45:09 desk and so if if you're the first transaction in that one that five millisecond window yeah you got to wait 5 milliseconds but for some applications that's that's not that's not a lot of time that's not a big
45:20 deal so you basically you have to main two two right head log buffers now I'm not showing the buffer full Pages I'm just showing the the right head log buffers T1 starts does it does it right on a right uh so we put an entry in the log buffer for that does it right on B does Put another log entry on that then we contact switch over to T2 we have to put the begin entry for that does a right on C we have an entry and then now before we can do it write on D the buffer
45:45 buffer uh the log buffer is full in memory so we're going to go ahead and write that out the dis we do that asynchronously because no one's asked us to commit at this point so it's not like we' immediately have to do it
45:57 we'll write that asynchronously and then now we just tell any uh you know tell any other transaction that wants to add new entries to this other log buffer start filling that up while the other one's getting written out the
46:11 desk then now say that there's a stall for whatever reason right again under the group commit policy I would say okay every 5 milliseconds every 10 milliseconds usually something you can tune in the system how how often will Tri trigger a flush so say these guys are waiting waiting because they're going back to the client to get more information it doesn't matter so then at some later point they say okay well enough time has elapsed I'll go ahead and write out this log buffer even though it's not entirely full
46:38 yet and that's fine everything's still correct right and then now when that you know this one gets flushed out the other one the other one is is now free uh you know the the top one to the transactions started pending log records
46:54 there it's basically just doing double dou buffering here pretty good all right so you go back to this these these sort of quadrants the way to think about now a recovery policy or recovery protocol for a DAT system is how fast is it going to be at
47:15 runtime and how fast is it going to be for at recovery time again we're not really talking about the recovery process yet but you can sort of see we saw examples of this of like for shadow paging recovery was instantaneous because you just ignore whatever's in the shadow page table when you come
47:31 back so the for the runtime performance the the buffer pool manager with the rad log the rad log approach is going to be the the fastest under Ste no Force because again I'm depending log entries that's pretty easy to do and I flush them out and write them out as I needed as I need doing sequential iio whereas the the uh Shadow paging is to be expensive because you're cut just blindly copying whole
47:57 pages but now for recovery time Shadow paging is going to be instantaneous because you don't have to do any there's no log to look at whereas in the the uh with right hand logging there is a log and you B basic have to replay that
48:11 right because you have to do undo and redo uh to put the state of the back to where it should have been at the moment of the crash whereas with Shadow paging there's nothing to do because the deis magically or instantaneously comes back as being correct
48:28 all right so now we got to discuss what are we actually putting in the logs like what like I I sort of again I'm showing things on PowerPoint transaction ID object before and after value and could be a bit more so physical logging would be the approach of like basically doing a bite level diff of like here's what the page was before and here's what it was afterwards or here's what the record was before here's what it is afterwards
48:51 where you're act specifying the exact physical location of within a file within a p page here's the changes that I made logical logging is going to be the sort of other other end of the spectrum where instead of instead of recording the lowlevel bite level changes I'm making to data I just record here's the query I executed to make that
49:15 change and then now when you when you basically recover after a crash you just replay the query reexecute it physiological logging is somewhere in the middle where it is going to be like physical logging where I'm I'm going to keep track of like here's the exact page that I modified uh by this transaction when it made a change but I'm not going to tell you exactly what offset within that page I made the change so I'll just record the slot number and then now at runtime or when you recover the system
49:44 you would just you would the data system is allowed to decide where in the page it's allowed to reply the changes all right so again say we do a simple transaction that has one query like this if you're doing physical logging again you now within the each entry for the updating the table you're going to record like here's the page number and here's the offset within that page that I modified and you're also going to record the changes you make to index
50:09 pages so you have to say for for the primary key index here's the modification I made made to that page right because we had to make sure our indexes are in sync as well because it's basically another copy of the data and we don't have to because otherwise if you crash come back and all your indexes are gone now you have to do a one scan to rebuild
50:29 them logical logging just literally records here's the exact query that I executed so again when you when you crash assuming these things are are in order you're basically replaying the trace of the queries that were executed for transactions at run
50:44 time this is this is more tricky to do uh you typically only see this in in memory systems where there isn't actually um there isn't actually a a table Heap that you're maintaining it's like you have snapshots of the database
51:01 and you you bring them back entire thing back into memory and you reply the changes the challenge the tricky thing also the two is like if you have non-determinism in the query like I had where set valow equals XYZ but if it was like where was valow equals
51:16 random or Tim stamp I got to make sure that when I re-execute the query upon recovery that I get the same you know use the same seed or get the same value that I had when I ran before so a little more work you know you have to do for
51:30 this and then physiolog physiological logging again it's just a a hybrid approach of this where I'm still recording the changes I'm making within a page but I'm just telling you here's the page number that I modified or Here's the the the index page that I modified I don't know where the change is actually going to get applied you'll figure that out the system will figure that out upon
51:51 recovery so most systems are going to do physiological logging because it it uh again provides you more flexibility upon recovery more freedom when the system boots up of how to reply the changes you don't you don't have that exactly the same physical layout within a single page you know from one crash to the next or One recovery uh pass to the next you just have to make sure you're you Scope your changes in the same page
52:14 right because there's all this internal data structur keeping track of like here's the page directory and so forth you don't want to mess that up but within the page you can you can reorganize things and that indirection layer of of the slot array gives us that ability
52:28 so a bunch of I've already said before like logical logging is going to store way less data Than Physical loging and physical logical logging like if that update query I showed before if that updated 1 billion tupal with physical logging physiological logging I need 1 billion entries for all those T that I modified but with logical logging I Dore the query string and that one query string could represent a billion
52:51 changes but like I said if you start trying to recover the database after a crash if you if you're just replaying the the the queries again there's no magic button we can hit upon recovery to make those queries run faster faster than they would versus when they were actually running during regular execution like even though we're recovery mode we can't the quer the query takes you know an hour to run the first time it's going to take an hour to run the second time on
53:19 recovery it gets even more trickier if you're not running transactions at lower isolation levels because now you could you could if you start trying to intermix the transactions upon recovery you may not guarantee the exact same outcome you may read data that from another transaction that you would you didn't read the first time but now you're reading the second time so things get very very difficult if you start doing this and most systems don't do this for these
53:46 reasons so I'm going to show one quick slide about this other concept because I want you be aware of it uh but it's it's and it's very common in the real world but this is not something we'll cover in the exam but remember the beginning we talked about there's these OTB databases and you have these data warehouses and you can stream updates from the OTB database to the data warehouse and do all your all your analytics on that and we talked about this this being what's called extra extract transform and load
54:13 and the DBT guys talk came about this that's sort of what DBT is is providing for people um ability to do that so what's cool about the right ahead logging is that we can use the right ahead log not just for recovery but Al for replication and propagation of changes from one database to another database because what what is recovery
54:33 while I was taking the rad log and looking the changes that made and applying to a database you could do the same thing for another database that has a you know has a copy of the data we just sort of like it's in this virtual recovery mode you have another D where you're getting all the changes and you're just sending over the the redhead log and applies it to to that system it's essentially how distributive systems do replication as well so this is called change data capture and you would use this in the context of a ETL or extraction from load pipeline so there's a bunch of different ways to do this right ahead logging is the easiest one because you just you already have the mechanism to generate the rad log for recovery so now what you have is you just have to send that rad log over to another system who then applies it the change and synchronizes
55:15 its database with the the original one so you're piggybacking off a a core uh component or or of of the recovery protocol with right ahead logging in a d system to do more things with it to send changes because otherwise you have to replicate queries like it's another way to do this and we'll see that later on we talk about distributed databases next week um but this this is this is pretty
55:41 easy so there's a bunch of tools that that can do this uh Oracle Golden Gate uh is probably one of the most famous ones deum is an open source or tool out of uh out of red hat the reason why I'm kind of bringing this up now is today's talk uh outside speaker is from Kafka
55:58 and the beum basically is the is the arrow piece that facilitates the movement of the right ahead log from one system to another and you would you would send that over Kafka and Kafka guarantees that the the data will arrive in
56:14 order okay so right log that seems like clear wi we want to do this but there's an obvious downside is that the rad logs is going to grow forever right if I'm constantly running transactions I'm keep appending things the rad log they'll flush out the disc that's fine but this thing is going to grow
56:34 indefinitely and then now if I crash come back depending how long my rad log is that recovery time might be really really long like I have if my system has been running for a year or 10 years if I crash and come back I don't want have to replay 10 years of log of the
56:50 log so the way we're gonna we're avoid this is periodically the system is going to take what are called checkpoints where we're going to flush out all the dirty pages that are on disk put a little hint in the right hand log to say at this point in time we did a checkpoint and therefore the system may not have to go all the way back to the beginning of time in the right log to recover the database act back to the the the correct State because we we flushed everything out and then therefore if depending on uh you what transactions are running what they were doing we could truncate the log and cut off at some point and not you know not to not have to retain that that long
57:28 history so I'm going to show a naive checkpointing scheme today uh and how this we incorporate this incorporate this in the redhead log we'll see why it has problems and then next class we'll see how to actually do a more efficient one that everyone really
57:44 does so a naive checkpointing scheme would be blocking or consistent checkpoints and basically every so often you're going say all right I'm going take a checkpoint and you pause all transactions pause all queries maybe if some query is still running you let let it finish right you basically stop
58:00 everything then you flush out the the log records that that that are in memory to disk then you flush out all the dirty pages that are in the buffer pool out the disk write a checkpoint entry into the right head log file flush that then unpa
58:16 everyone and again because all the log records for uh any modified Pages written a dis even the transactions haven't committed yet which we allowed to do Under the steel policy that when we crash come back the we have enough information to restore the database back to the correct
58:34 state so let's see how this works so say we have this this righted ahead log we're generating here and then after this last entry by T3 we we crash right so now when the system's going to come back up it's going to look in in the the rad log and say aha I I took a checkpoint here at some you basically start at the end scan back until you find the checkpoint
58:57 so I know that at this checkpoint entry here I got to look around but before in going back in time and forward in time at that checkpoint to figure out what was running at this time what changes they made and what transactions I need to guarantee those changes are are are durable in dis and what transactions I need to roll back so at this point here we know because we if we look up in the log we'd see oh T1 committed when we took the checkpoint we flushed all the dirty Pages out the disc there we don't need to do anything with T1 we can just ignore it because we know all its changes are have been reflected in the pages on dis so that's fine that's
59:36 good but now for T1 for T2 and T3 we would look back and say well we see the begin entries for them uh before our checkpoint so these were active transactions at the moment the checkpoint occurred we paused them and then took the checkpoint so then now we got to scan for in the log and figure out what whether they committed or not so in the case of T2 we see a commit entry uh before we get to end of the log so we therefore we know we told the outside world this transaction is committed so therefore we need to make sure all the t2 changes made at the disk but in case of T3 T3
1:00:07 didn't we didn't see a commit message for T3 so therefore we need to make sure that all its changes get reversed and uh and undone so the reason why we have to stall the transactions is because we don't want to start flushing dirty Pages
1:00:24 uh and if a transaction take updates two pages or one query updates two pages we don't want to get you know half the updates on one page and then or get the updates on one page right that to dis and not write the ones from from another one all right so we'll see how to fix this uh next class these the techniques basically called fuzzy checkpoints where you allow transactions to keep modifying things while you're still running and the way we have to handle this we just sort of keep track of additional metadata about what was going on in the state of the system and what did our buffer pull look like at the moment we took the checkpoint
1:00:58 all right and so then we have to do extra work when we find the the checkpoint we scan back to figure out what transactions we're running and then we scan forward to see whether they committed but we'll see how we can add extra hints in the checkpoint records about what what what the ACT transactions were so we have to hunt forever for to find
1:01:14 them of course now in our example here it's on PowerPoint you know it's it's a small number of of log records and then I put a checkpoint in there but in a real system you got to be you got to be aware of like oh how often should I be taking a checkpoint
1:01:26 because that can have real effects on performance right just like the garbage collection stuff we talked about before or uh the compaction stuff in log structure emry like if I run these this background task of taking checkpoints over and over again constantly then I'm going to be spending more time taking checkpoints instead of running queries and transactions and it's going to make my system run
1:01:45 slower but if I turn off checkpoints or take a checkpoint every month then now if I do crash and come back now I got to replay one month's uh worth of logs so there is a magic number I can say oh yeah take a checkpoint every five minutes right even though that is often the default um the it really depends on the what is the acceptable amount of performance de uh penalty you're willing to pay in your application and how quickly you need to recover after a
1:02:14 crash and it and it varies depends on what kind of application it is I think I mentioned that there was this uh the the Puerto Rico power system or power company in the 1970s built a database system uh down there on the island and because they were having such frequent power outages that were
1:02:34 non-deterministic they wanted the system that that that had instantaneous recovery because they lost power the system crashed when it came back up they didn't want to spend you know hours and hours recovering the database because it might crash you know might lose power again so they essentially did Shadow paging because they were willing to pay the performance penalty at runtime but that gave them the instant recovery they needed in in their envir environment so how often people want to take checkpoints and what their the tolerance is for for Recovery times
1:03:02 depends on what uh depends on what the application actually is but honestly most people wrong with the default all right so to finish up so right ahead logging is almost always going to be the best approach to handle loss of uh crashes on system when you have to write things out to nonvolatile storage and the way we're going to handle this is due it's through the steel no Force policy where steel says again we're allowed to evict pages from transactions that have not committed
1:03:33 yet uh out the dis only if the log records that correspond to those changes that that made that page dirty as long as those have been flushed out the dis and then no Force says that we don't have to require all the dirty pages from a transaction be flush out the dis when it when it when it goes and
1:03:51 commits so again this is what we'll do at runtime we we're I'll pend these log records to the buffer and then occasionally take these checkpoints and then upon recovery we'll look in the right ahead log basically almost like the black box of an airplane to figure out what would what what was going on in the system at the moment of the crash and then try to recreate this the state of the database to be where where it should have been through a combination
1:04:12 of redoing transactions that did successfully commit and undoing the changes from transactions that did not commit and the and the checkpoints allow us to sort of shortcut or jump more quickly into what should be the starting point for uh for the the database
1:04:28 okay so any questions about this so the warning so I would say next class we're going to talk about uh how to do do better checkpoints and how to do recovery with Aries uh and I would say this is probably the third hardest lecture of the semester right and rightfully so because you don't you don't want people to lose data getting this right is really really hard uh and so you'll see that we'll first describe the areas recovery protocol we're going to be very very judicious and very careful like we're going to do this this this and this and actually in some cases we actually be redoing changes that we didn't actually need to redo because we want to be guaranteed that we're ending up the correct State we're going to do
1:05:07 this because people get mad when when you lose data okay all right uh this is mahes he's from conf which I said is the the company that that is building kfka um and a bunch of other tools and mahes can tell you like I told you again use kfka
2. Jump to
1:05:21 for change data capture and deum but people use kka for a lot of things as well beyond that so the floor is yours man go for it okay um so thank you Andrew and and Andy and it's great to meet all of you even though I can't see you I'll just assume you're there um so I'm going to be talking today about uh some work that I've been doing at conflent so for those of you who don't know what CFA is uh it's me yeah so CFA is what you call a publish subscribe
1:05:51 system um publish subscribe is an idea that emerged from academic research search in the ' 80s and early '90s and it's just this idea that you have a bunch of uh people or machines who are producing data producing a totally ordered stream of data and you have other people or machines consuming that data so you have a notion of a topic you publish something to a topic you subscribe to that topic and you pull updates from it and CFA is something that got built maybe 10 to 15 years back uh it was a project at LinkedIn uh and then the founder of that project Jake reps turned it into a company so at this point it's a pretty big deal practically
1:06:31 confluent is a billion dollar Revenue company um there are other um companies that sell CFA products that make quite a bit of money um but the thing about Kafka that's interesting is that it's not a cloud system uh it was designed for on premise workload so if you look at its design uh it's basically a single machine a broker and then you run a whole bunch of these Brokers and the Brokers do everything in one box what is called a hyperon converge design there a great design if you're downloading and running Kafka in an on premise setting
1:07:03 not so great if you want to run it in the cloud and today a lot of the Kafka business is in the cloud we're running Kafka as a service in the cloud so when I came to confluent uh two to three years back the Mandate was can we build a cloud first CFA what would that look like um and this turns out to intellectually not be that mystifying right because CFA if you really think about it topic is kind of like a file there's something called a topic partition I won't go into that but it's basically like an up only file you're appending to the file other people are reading from it and so the design of a cloud first CFA probably looks a lot like a distributed file system you have a compute layer you have a data layer um you need to store some metadata
1:07:47 somewhere uh and just to make it very clear this metadata is essentially a map from a topic name like a file name um to a list of data blobs that constitute the topic right so when you produce to the topic you're essentially adding more pointers in this link list uh and when you're reading from the topic you're just reading data from this list all right uh hopefully that Crystal Clear you know what we're talking about and so it turns out that if you really want to build a very scalable Cloud first implementation of the CFA API this this published subscribe API then what you're really looking for is a met dat layer
1:08:26 where you can store all of this metadata so for example when you produce data you when you publish data you can write it to something like S3 and then you go to this metadata layer and you write a new pointer saying the next data blob in this topic happens to be at this location in S3 so someone reading the topic subscribing to it can go and read the data okay um and that is a bit rushed so I apologize but I'm trying to fit this into a 10-minute talk um so so if if building a cloud first CFA is all about the metadata you know how do we make that work so confluent like a lot of other companies Builds on top of Cloud providers like AWS and Azure and so on
1:09:09 so the easiest thing we could have done is just take all of our stuff and shove it in a database like Dynamo DB or something like that I'm going to use the word database in a very loose um uh very imprecisely you know compared you're taking a database class so not talking necessarily about SQL databases you know I'm going to call Dynamo DB a database it has DB in the name so the the nice thing if you I store all of my metadata
1:09:35 and something like Dynamo DB is that from a very practical standpoint it's a very easy system to operate right um Dynamo DB is not going to lose my data so if the power goes off on my machines I don't have to worry about durability I kind of caught the tail of what Andy is talking about WR ahead logs and all of that that stuff is really complex and I don't want to deal with a lot of that so
1:10:00 Dynamo DB takes care of it right the the problem is that if I store all my metadata in Dynamo DB it's extremely expensive because every time I want to read my data I have to issue a request to Dynamo DB and these workloads tend to be fairly read
1:10:16 intensive the other issue is that again if I have a very chatty protocol I have to keep going back and forth on give me the next entry in the link list give me the next entry and so on and there's a third issue which is there's only like maybe five to 10 of these actually usable database apis that AWS will give me for example so I have an impedence Gap
1:10:36 problem the other option I have is I just build a new database from scratch and I run it on ec2 right and then I can do anything I want I can build you know a spanner clone or whatever the problem with that is um it's I mean I get all the properties I wanted but it is extremely difficult to operate a durable database in production because as nodes fail you have to make sure that you don't lose chorum you don't have data loss and so on there's like a 10x 100x difference between running a durable database
1:11:10 versus just running some soft State servers so the the intellectual question we were looking at is can we have our Kake and Eed to can we somehow make the cloud responsible for durability so all of our machines can re Boot and lose power and lose State and it doesn't matter at the same time can we get the cost latency and flexibility benefits that we would like to
1:11:34 have and uh in a in a previous life I used to work at Facebook before confluent before that as a professor before that is at Microsoft research and when I was at Microsoft research I did some work with someone called Phil Bernstein who you would have encountered I hope in this class um and Phil had this idea that you could build a replicated database on top of a shared log and then I did a bunch of work on making that a real system so the idea here is fairly simple if you give me any database your favorite single note database SQL light MySQL postgress or something simpler right Ro DB Berkeley DB and so on I can run multiple copies of the database and I can keep these copies synchronized through a shared log
1:12:21 what's a shared log it it literally is a log that sits across the network from your database copies uh and it's fault tolerant and and rep it's replicated now the implementation of the log itself can be some very complex distributed protocol the important bit is we are separating the the logic of the single node database from the logic used to replicate
1:12:45 it all right now when we I I'm going to like rush through how this might work so when a client talks to a copy of the database um it sends a command a mutation right a SQL command to the database the database does not execute the command it appends it to the shared log and then every copy of the database is playing that log forward and materializing the state so the database is the log right um or the log is the database as the famous saying goes um now why is this a good idea well we kind of liked it because um you can completely separate the database and the replication framework so you can run any database with any API and the logic used to replicated doesn't change and there were a whole bunch of reasons why in other settings you know you got some properties from this architecture you could replicate any API you only needed one copy of the database you didn't need Chums at the database layer I'm not going to go into those in too much detail but the one interesting property
1:13:44 that you know in in the early 2010s we kind of looked at it and we thought well that's nice but we don't know why it's useful is that you could use any consensus protocol under the log API once you have an API you can have any implementation you can virtualize and switch between
1:14:00 implementations and I remember in 2013 2014 having a conversation with someone and saying well we could also just use something like S3 for the log but why would we ever do that right that's such a dumb idea and and I kind of forgot about that idea for a while now coming back to 2024 at at
1:14:19 confluent we needed this metadata database and we wanted to somehow um get the flexibility and the cost and latency benefits of having our own database but we didn't want the headache of running a durable database it turns out that the architecture I just described is a perfect fit because I can spin up some ec2 machines and I can run whatever database I want to I can run Rock DB or something else and I can Implement a log
1:14:47 directly on something like Dynamo DB as a pass through shim and get a replicated fall tolerant database right using the protocol I described but every time I talk to a copy of my database I'm synchronizing via this shared log so this turns out to solve a lot of our problems because now we have you know the cost benefits and latency benefits because every time I want to read this database I have a full coherent cache sitting on my ec2 machine
1:15:15 uh at the same time if all my ec2 machines get blown away my log is still in Dynamo I'm missing some details because I do have to take snapshots and store it in three but you know but but basically none of my ec2 machines have any hard state in this
1:15:32 world so um I think that's pretty much all I have time for I did want to make uh you know two statements that are kind of interesting when I was a student you know I did my PhD at Cornell and um I remember my professors would say things like you know State machine replication it's very important it's used all over the place and I really didn't believe them as was like you know it looks too simple and it looks too abstract it can't be that important I'm sure in Industry they do something else but it turns out that if you really spend enough time in Industry you realize that all the Big Ideas are actually coming from academic research they're coming from rooms like the one you're in where someone has an idea and they write a paper and it turns out to be really
1:16:16 impactful and one of the reasons that's true is that when you come up with these new ideas um even though you know there's a lot of emphas empasis on saying tell me why your idea is practical often you can't tell at the time why it might be a good idea so there's something to be said for just doing random research um and some of it may be good some of it may be bad that's fine you just do a good job and then over time I think these ideas find
1:16:42 practical utility uh in my own case the reason I got into these kind of databases was because you know Phil came and gave a talk Phil Bernstein and he said we can build a faster database and I said sure I'll build you a log
1:16:55 uh and it turned out that at Facebook the reason this architecture made sense was they needed simple databases that you could evolve over time and the funny thing is that confluent the same design ends up being very important for saving cost which I didn't anticipate you know 10 to 15 years ago that that would be the case uh thank you that's all I
1:17:17 had thank you all right uh time for one or two questions so the log he's talking about is basically what this the whole class was about right here's all the changes you're making to the database and I was saying the CDC or the change data capture stuff the you don't have to replay the log on the same database that generated the entry you can send it to whatever else it doesn't actually even be the same database system so I could take postgress take out the the the the rad log entries send it over kofka to whatever and then replay it on my SQL whatever you want or snowflake
1:17:53 that's a very common pattern the other thing I also point out too is he mentioned uh Phil Bernstein remember I talked about uh HD Kung the guy invented OC and how he left CMU to go fix Harvard and I said the guy that that invented a lot of Cal stuff that was a professor at Harvard was a genius and they didn't give him tenure that's Phil Bernstein right the same dude the guy that invented all this like transaction
1:18:16 stuff he's like almost 80 I think uh but he's like he's a genius he invented a lot of this Cent stuff he laid down all the core principles of how all this stuff works that's the same guy that mes is talking about and he's he's still Microsoft today all right any last questions I need something refreshing when I get finished manifesting too cold a whole B like Smith and Wesson one court and my thoughts hip hop related
1:18:40 right R in my pants intoxicated lyrics are quicker with a simple Mo lier since on mer City Slicker play waves are picker rhes I create rotate at a we too quick to duplicate f a breeze at a skate mik at Fahrenheit when I hold it real tight then I'm in flight then we ignite but starts to boil you I heat up the party for you let my girl R me my mic down with oil Rec still turn with third de burn for one man I heat up your brain give it a suntan so just cool let the temperature rise to cool it off with s eyes