CMU Database Group · 1:05:22 · https://www.youtube.com/watch?v=bXpkEt5P_Js
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 lcks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol you know what sucks botching the recording third time this semester for the lecture and of course I got to re reccord it but I can't go back to campus because you have to tell your PO we're g to go first and they have to approve it before you can go anywhere so I figured it's Monday night let me go ahead and record re-record what we talked about today so last class we were talking about the the introduction to con currency control and we spent most of our time talking about acid atomicity
0:51 consistency isolation and durability and we spend most of our time discussing isolation and in particular we were talking about how we want have the system the D system be able to run transactions as if they were running uh one after another in serial order but of course then we we still want to be and leave them to allow for better parallelism to get better performance in our system and so we had this notion of this idea of of serializable schedules
1:18 where one where the outcome of the database is as if the transactions are executing in serial order even though they were being interleaved and so we talked about these two types of serializability or seriz well schedules talked about conflict seriz well cable right conflict sterilizable is one where we said that the we had this dependency graph and if we could recognize that that were there were no Cycles in the dependency graph where operations are occurring between one you between different transactions on the same object and in different orders then we know that the that schedule would be equivalent to a a Serial ordering and then we said there was this other notion
1:53 of uh serializability called view serializable where this is allows for additional uh uh schedules that you couldn't otherwise in Conflict stable because conflict ciz was trying to be a bit conservative in in how it schedules transactions but in order to make this work you had to have some higher level meaning or understand the semantics of what applications uh thought or cared about the data to identify that yeah you could reorder things a certain way right the example we showed that you could do a blind right on uh on on an object
2:24 where you don't care about the interner leavings or the transactions before then as long as the last transaction successfully written to that that the one object at the end of course as you said this in order to do this you either have to do static analysis or program analysis on the application code or do the worst thing possible which is talk to a human uh which is non-st startup for database systems so in that case you know for that reason no no dat system is going to support this so when you say I want serializable transactions in a databas system you're typically you're always you're always going to get serializable
2:54 isolation so last class though was looking at what we called Static schedules meaning where the the all the operations for for transactions were known to the database system ahead of time so all the reads and writs we would we would declare ahead of time and therefore we could then decide how to in or leave them to determine whether we could produce something that was conflict sterilizable um and of course now as we said in in a real system uh most systems don't work that way you have all the transactions operations ahead of time there are some systems that can do this and if you store procedures you potentially do this as well uh but most systems don't work like that right and so instead we have this uh sort of fog of War if you will where transactions
3:35 are submitting query requests they requesting to do some operations on some objects in the database and the database Sy has to figure out on the fly as it goes along in the you know who what operation from what transactions allowed to touch what data at what time and in what order and again to to ultimately end up with a uh execution schedule for transactions even though they're dynamically coming in um that we end up with the state the dat that be equivalent to one where we executed them in in serial
4:03 order so we be again the idea is we to figure this out on the fly without knowing the schedules ahead of time so in today's class the solution we're going to look at how to do this is is through locks and then next class on Wednesday we'll see how to do this with time stamps a different approach to trying to solve the same problem so if you recall back to the beginning of the semester uh when we talked about index ency control and the buffal manager and
4:28 we talked about latches the the the protection mechanisms we would have inside our data system to protect the critical sections of uh of the of the internals of the system and I sort of was being very hand Wy and say oh yeah there's this other thing called locks that if you're in the OS world then when when we say latch they what they really mean is a lock but in our world locks are something different because they're they're a high level construct so now today we're at the point where now we need it's time to talk about how we're going to use locks and protect transactions so again going back to this table that we had from the GS graphic guy um these locks now are being defined on to to separate transactions from each other based on the contents of the database so it's no longer lowlevel things like a node in a B+ tree or a pointer if you want to swap something out like in a link list for example um now it's protecting objects in the database so a database a table uh tupal attributes and so forth and
5:28 they're going to potentially hold the locks during the lifetime of a transaction so I could acquire a lock and hold it for for the that entire duration that long as that transaction lives and then I go ahead and release it whereas like the latches remember we were saying it's supposed to be for a a a small amount of time to come in get a you know a latch on something do some operation and immediately go ahead and release
5:48 it there was two types of modes for for latches there was just uh read and write now in locks we're going to first start off with just two modes uh shared and exclusive right shared just means read write or exclusive just means write we're just trying not use the same term
6:04 um but then there's also going to be these additional locks we uh modes we're going to have later on when we talk the end of the semester or end of the lecture about hierle locking that's going to make our things make the life even more complicated as well but these are going to be special locks we can have for for different contexts to explain to other transactions what we're trying to do in different parts of the
6:23 system in latches we we had to write our code uh in a correct manner to avoid deadlocks but again if we tried to acquire a latch and it wasn't available we said we just shoot ourselves in the head immediately and give it back up but now with locks
6:36 uh on transactions we are going to have additional protocols that are going to handle uh Deadlocks within the system itself because again it's going to be some some random JavaScript programmers sending you crappy queries and they may incur a deadlock and so we as the database system people building building it we have to protect them from themselves shooting themselves in the foot and so we're going to have this higher level concurenti mechanism a traffic coordinator or transaction coordinator if you will that can determine there's a deadlock and me go ahead and and break it or in some cases
7:09 to order the operation the request for for locks in such a way that we never have Deadlocks to begin with and then the other key thing about the the the locks um is that instead of having them being maintained inside of the data structure themselves remember like in the B+ tree the latches were in the nodes themselves we're now going to have this centralized
7:30 uh component in our data system called the transaction manager or the lock manager which essentially a hash table that can keep track of what locks exist who holds them in what mode and then a priority cues or cues to keep track of who's waiting what other transactions are waiting to acquire that lock and so this is going to be a much more expensive and heavy machinery in to to maintain this lock information versus the latching with be more lightweight
7:57 but the reason why we want to have this heavyweight lock manager is that we want to since since the the the since the duration that transaction be holding locks it's okay for us to pay this penalty to keep track of all the locks in the centralized location because now we have a complete global view of what all the transactions that are running in our system assuming it's a single node distributed Davis will make that harder for us later on but now we can at least see everything that's going on the system so we can make better decisions about how to how to deal with uh
8:28 conflicts or issues that come up because that'll allow us to get better parallelism if we do it this way all right so let's go back now to a really simple example that schedules that we showed before and we have T1 T2 T1 wants to read on a write on a read on a T2 wants to do a read on a followed by a right on a but now we're going to introduce these explicit lock and unlock commands in our transaction schedules so T1 starts off the first thing it's going to do is before it can do any any look up on a or write on a it's got to go to the lock man and say I want the lock on a because I want to do something with it
9:02 and then the lock manager keeps track of you know who holds the locks on a if if any transaction right does right now and in this example here nobody holds the lock so it's allowed to Grant the lock request to a and now a requires that lock so then it can go ahead and execute
9:16 and do the read on read on a and then now there's a context switch T2 starts running and the first thing it wants to do is request the lock on a so now in this case here since T1 already holds the lock uh the lock manager would recognize that t that that lock on a is already being held and therefore denies the request and essentially puts the the the thread the the worker running T2 the t2 request has to go into the the que
9:42 for that lock and it just has to stall and wait then T1 can switch back now do the write on a read on a and then at which point it releases the lock on a um while T2 is sleeping and then that request goes back to lock manager it releases the lock it's allowed to go ahead and commit later on but at this point when the lock is released on a then that uh wakes up T2 and the t2 can get the the lock request do the read and do the right right so at a high level this is what we're talk about today is how to design a protocol based on these sort of lock and unlock commands to generate schedules of transactions that end up if they uh serializable ordering
10:20 I will say also too that transactions typically don't make explicit requests for lock and unlock this sort of happens automatically if I run a select query for for example then I'll acquire like the share lock on it first the the right lock on relock on it first and that's not something the programmer has to write explicitly the DAT Sy will do this for you and likewise we'll see later on when you do uh commit uh it could go ahead and unlock things but I first want to understand how the protocol works today and then as we go along then see okay how can you actually do this uh automatically in a real system so today I want to first talk about the different lock types that that that can exist and the basic lock types and then we'll expand them later on when we talk about Hol locking uh at the bottom then we'll talk about the the basic two-phase
11:04 locking protocol basically understand how that works then we'll see how it'll strengthen it even further to avoid additional problems may occur uh later on and then we'll talk about how to deal with Deadlocks and preventions in different different ways and again I said we'll finish out with high go locking it's a way to uh be more efficient in a lock manager by taking locks on regions of objects rather than single objects at a
11:28 time all right so uh again in for the basic locks uh we're going to have shared locks and exclusive locks again shared locks are for reads exclusive locks are wrs and the compatibility Matrix here basically looks like like it did for read and write latches where if someone has a read latch or sorry shared lock uh somebody else inquire also a shared lock on that same object but anything else is incompatible so if I someone holds a shared lock I can't get a right someone holds a share lock I can't get exclusive lock someone holds an exclusive lock I can't get any other lock so again for Simplicity I'm showing just starting off with two lock types as a as a preview what's coming later on uh you can just see from the manuals of real database systems there's a their compatibility metrics are much much larger because there a bunch of different uh a bunch of different lock types you can have uh and for different types of objects like catalog for the updating tables for for catalog updates
12:22 versus doing index updates there's a whole bunch of different variations on this so again it's good to understand the basics of two-phase locking and then we'll how to make it more robust later on okay so how's this working with locks so the basic way we're going to go this is transactions before they can do any operation on a on an object like a read or write they have to go acquire the lock from the lock manager uh for that for that given object you can do lock upgrades meaning if I hold the the object in in a share lock I hold a share lock on an object and I know the next very very next thing I want to do is do a write on it I can then say I already hold a Shar loock upgrade it to an exclusive lock and that may be possible to go ahead and do uh otherwise you may have to may have to
13:05 stall and the lock manager is is responsible for figuring out who holds what locks uh in what mode and then who's waiting for those locks uh in what modes as well then as transactions finish with with what they uh whatever operation they want to do they go ahead and release locks so the lock manager is typically implemented as a as a hash table uh in some syst like postgress you can query it as if it's a real real table but I think it's just a just a view over a function um that accesses
13:33 the internal data structure because we don't need all the things that we've been talking about before like the well you don't need transactions on on the lock table because then you need a lock table to have a transaction so how you how could you do that but you still need to protect the data structure with latches um and you know when we talk about logging you don't need to save the lock table to dis because it doesn't make sense if you crash and come back uh who cares what locks are being held because those transactions are gone anyway right so it's sort of a special case of a kind of table that isn't
13:59 doesn't fall under the same protection mechanisms as a regular data table all right so if we go back to example here and now we're going to introduce the the same setup like before but now we're going to do ex use the different lock modes for our our transactions so T1 first gets the exclusive lock on a uh then does the read on a followed by the right on a now we could have gotten the share lock on a first do the read and then upgrade it to an exclusive lock and then do the right for for Simplicity to make it fit in the slides I'm just doing it as a you know single exclusive lock acquisition we'll see how to do that in Sequel uh at the end of the
14:36 lecture then after T1 has finished the first right it'll go ahead and release the lock on a right because there's a Conta switch T2 is going to start running so yeah let me go ahead and give up the lock T2 starts running it gets the exclus to lock on a then it does the right on a and then it says up I'm done and releases the the that lock back on on a but now T1 starts running again and it guesss the share lock on a goes ahead and reads it and then unlocks it but the problem is that in this example here T T1 is going to read the the right made by T2 when it should have seen the the the the right that it did
15:16 earlier right so this was this was unrepeatable read anomaly that that we saw before we're we're reading things multiple times and we're not seeing the same values right so this the main takeaway here is that just because we're doing using locks doesn't mean we're going to we can guarantee that we're going to you know always going to get a a serializable ordering of of schedules or transactions right so we want to be smart about how we lock things and unlock things to avoid anomalies like
15:43 this and this is what two- phase locking does for us so two-phase locking is going to be a cont protocol that we're going to use that's going to determine or or dictate at which point uh how we acquire locks and then what happens when we actually start want to go ahead and release them
15:59 and this was one this was the first prly uh correct concurenti protocol from the 1970s uh that could generate uh serializable ordering of transactions without having to know all the the queries ahead of time and this was invented by Jim Gray at IBM working on system R which you later one the toring wood for this in uh in the
16:19 1990s so twb locking is as it sound it has two phases so in the first phase called the the growing phase the transactions are allowed to to keep from requesting as many locks as they want uh and then the lock manager can just grant or deny them uh as as it normally would
16:36 but then soon as a transaction releases a lock then we automatically switch into the shrinking phase now at this point here when you're in the shrinking phase you can never go back the transaction can never go back and acquire new locks it can only release locks or commits and releases all the locks that that it has right and so again this is the key idea that that and this would avoid that problem we saw before because it unlocked the A and then it tried to acquire another lock that wouldn't be allowed in two phase locking because you can't go back and acquire locks once you once you unlock
17:09 something so way another way to think about this is that the you think about the lifetime of the transaction over time for a single transaction and along the the x-axis here we showing the the number of locks that it's accumulating over time so in the growing phase you're requiring lock lock lock lock you're getting all the locks that you want and then at some point say all right well that's enough I have enough locks and you go ahead and release them then you again
17:32 automatically uh uh switch into the shrinking phase where you're just returning locks back to the transaction manager so the way to sort of think about this is like you're climbing up the mountain acquiring locks then at some point you reach the peak and now you're going down the other side and you never come back to another Peak meaning like I can't release some locks and then go acquire more locks right because this would be a 2pl violation and you can't we can't allow this right and you guarantee this then we can we can we can show that we're always going to be able to generate uh you know conflicts oriz well
18:06 schedules all right so let's go back to our example before so T1 starts gets exclusive lock on a that gets granted so we give it back or sorry T1 starts running again does the read on a and then write on a and then now there's a contact switch where we switch back over now to T2 or T2 starts running it tries to get the exclusive lock on a but that that's blocked because it's being held by T1 so then it waits and then T1 can start running again do the read a that it wants to do go ahead and unlock it and then commit and then now the uh now when that when it's unlocked T T1 gets sorry T2 gets the lock on a it can go ahead and do the right and then releases it and again now we don't have that uh unrepeatable read problem that we had
18:49 before it's pretty simple but it's it's it's a really elegant Solution that's uh uh that you know works again without having to see all the transaction queries ahead of time so as I said two-phase locking by itself is is enough to guarantee that the uh transactions or schedules will be will be complex or liable um because any precedent graph for any transaction uh sequence of transactions is always going to be a CET mean there's not going to be
19:14 uh edges that could cause the cycle between them but there is another issue that can that can occur uh another problem that can occur that isn't a correctness issue but rather it's a performance issue um and that's called a cascading abort
19:30 so going back here so now we're going to do uh in T1 do a read on a write on a and then a read on B and write on B but then at some later point it's going to say it's going to go ahead and abort
19:42 right so if T2 starts running uh during this and gets the exclusive lock on a which is allowed to do because once T1 unlocks a and it's in the shrinking phase so that's fine so then T2 can grant that lock then it does the read on a but at this point here it's reading
19:58 the right that T1 made and then it has to stick around and then at some point when T T1 aborts we actually has have to Al also roll back T2 because we can't let T2 commit having seen the the uncommitted change from
20:17 T1 right so a schedule like this would be permissible under two-phase locking but when T2 goes to commit or any transaction that reads data from another uncommitted transaction you have to track the read read and write that and you have to recognize this transaction read something from a transaction that has not committed yet so when I go ahead and commit I have to wait to find out whether that other transaction successfully committed before I'm allowed to
20:41 commit right because the thing we want to avoid is is having T2 leak any changes that T1 made to the database leak to the outside world by allowing T2 to commit right because again you would be able to see uh See a change made to a a to the database from a transaction that end up getting rolled back
20:59 back the other problem also too is that any you know since since now we need to pause or need to wait to see whether other transactions commit before our transactions allowed to commit then we have to then if we identify that our transaction is going to abort because another transaction aborted then we have to roll back any changes that we made so now in this case here in T2 all the work that it did was running on the assumption that it would be allowed to commit you know because T read something from T1 and T1 is going to commit we have to roll all that back
21:29 and now all that's Wast of computation so my example here again I'm only showing you know T2 doing one read and one write that's no big big deal but always think of extremes like if if T2 did a billion reads and a billion writes
21:41 and then has to end up getting aborted because it read a change from a transaction that it didn't commit then that's that's a lot of ways to work and then the the application if it's written correctly would have to resubmit that if they want it redone to do all the work all over
21:56 again so the with two-phase locking there potentially be schedules that are serializable but uh we're not going to be always allow them uh because uh because you know it uh it not allow them because T locking again it's a bit more conservative than maybe it necessarily needs to be um but then we still have this problem where again we could have dirty reads because we're allowing transactions to keep running but then when they commit you got to wait to see whether anything they read from uncommitted transaction whether they have committed right these the the dirty read un repeatable read problem so the solution to this will be a variant of two-phase locking called strong strict two- phase locking I think the textbook might call them rigor two-phase locking
22:39 or other systems might call them rigor or rigor two phase locking but they're essentially the same thing and the basic idea here is we're going to make a a slight adjustment to TV's locking to to avoid this particular problem so under strong strict two-phase locking the way it works is that the growing phase just like before as as I'm acquiring locks right the growing phase the the number of locks I'm holding goes up but then now there isn't really a switch into shrinking phase because you don't actually release any any any locks in a shrinking phase it's only when the transaction commits when the end of the transaction then you release all the locks that you
23:16 have right because again the idea here is you don't want anybody to have read read something that you already did that you wrote so therefore I'm going to hold my exclusive lock on those objects that I wrote to until the very end then I can commit and then then someone else can then read my changes because that at that point I know I've successfully saved my change or committed there's a a slightly less
23:38 um conservative uh version of of this called strict two-phase locking uh where you just you're allowed to release the read uh shared locks and the shrinking phase but all the exclusive locks you hold at the very end but under strong shrick you hold both shared and exclusive locks to the very the very end of the transaction
23:56 right so the way thing about this is that the the the so the formal definition of a schedule uh that doesn't allow a other transaction to read or write data from another transaction till that other transaction has committed uh would be termed as being a strict schedule right sort of the strict ordering of of the operation so that we're not uh we're not modifying inflate data or reading from inflate
24:22 data so the opposite benefit is that we avoid the cascading abort problem that I shared before um and it actually simplifies simplifies the implementation because now when when a transaction aborts since we know that no other transaction could have read data that we wrote to uh it makes roll back really easy because when I when I transaction boards I know I'm only have to roll back that one transaction because the the there's not my data hasn't leaked to other inflate
24:50 transactions right whereas if you allow for Cas getting aborts have to handle them then I could have a long dependency chain of what transaction Red Data from what transaction red did from what transaction and then when I go to go ahead and abort I got to figure all that out and roll them all back in the right
25:05 order so most systems if they're going to do serializable they support seriz execution or serializable schedules or seriz isolation and they're doing two-phase locking they're going to give you strong strict two-phase locking I again also too because there isn't actually explicit unlock command like I'm showing my schedule like there isn't a SQL command that says unlock something
25:26 uh so there's isn't a way to say like I I I know I'm not going to read this thing again or write it again so I'll go ahead and release my locks now so most systems will just give you if you say I want serializable transactions you get strong strict two phase locking by
25:41 default all right so let's look at uh uh some other examples and how this all works together so say here now we have we it's similar to the banking example we saw last class we have T1 uh want to move $100 out of my account into my bookies account so debit $100 from from account a and credit $100 to account B
25:59 and then for T2 they want to compute the the sum of all the accounts uh all the bank accounts report it back to the you know to the application again I'm showing this Echo command here that there isn't a SQL command there isn't anything like that it's just a way to say here's the return statement of the operation of the transaction so here's here's how what happens if we execute these transactions without two-phase locking so T1 would start get the exclusive lock on a T2 would start get try to get the share lock on a but it can't because T1 holds the exus blck so it pauses and waits T1 is allowed to read a subtract $100 from it and write it back to the database now gohe goes ahead and unlocks a at which point the t2 gets the lock on a and it goes ahead and read the value of a so without a without the $100 I took out unlocks a
26:49 takes the share lock on B before the uh T1 can get the exclusive lock on B so so T2 sorry T1 has to wait t T1 T2 is allowed to then read read B adds to the total and produces the output and then at which point T1 can then run again uh and do the update on on B so if you look at the output of T2 it's going to be a plus b is going to equal 19900 so because we were able to read the the the value of a after taking $100 out but then the value of B before putting that $100 back in so now the bank is missing $100 here right because we're able to get in leading of of the transactions
27:31 that wouldn't occur if they were running in serial order so we do basic two-phase locking T1 gets the exclusive lock on a T2 pauses when it tries to get the share lock on a that's fine T1 gets the exclusive lock on B and then immediately release the uh exclusive lock on a at which point T2 can start running uh and then when T2 then tries to get the the shared lock on B that gets stalled because T T1 holds the lock on that T1 is allowed to then add the $100 to B
28:01 goes ahead unlocks and commits it and then at which point T2 can see the value B so even though we're actually able to the transactions so while uh while T1 was doing the update on B T2 was allowed to read a after it was modified by by T1
28:17 um but we're again we're we're producing things in the right order and we can the correct uh the correct number at the M if you do strong strict two-phase locking uh it's again basically T2 tries to get the share loock and a but it gets blocked until the very end that when T1 commits because again T1 is going to hold the locks that any locks that acquires till the very end to goes ahead and commits and then in this this point here you can it's it's basically running it in seral order uh and we're producing the correct
28:45 result so if we go back to that the schedule that we diagram we showed last time we sort of said this this region of space here is saying this is all possible schedule you could have for for transactions and we said there was a small chunk of it a sub set of of those schedules were the ones that were running in serial order and then the runs around them were the ones that would be conflicts realizable and the runs around them could be view sterilizable so any any schedule that's view sterilizable uh sorry any schedule that's conflict sterilizable is implicitly also conflict vizable and any
29:16 any schedule that's serial is is um implicitly conflict seriz and vizable so now there's this region here for uh no casting aborts where some of those schedules are going to overlap with the the serializable ones and the Ser ones but some of them are not going to be in that space and then within that region within conflict sterilizable and also bounded within no cascading boards we would have the strong strict uh two-phase locking
29:44 schedules all right so going back to the slide here we we've talked about how to uh handle the dirty read problems using strong stri two-phase locking so the next issue we got to deal with is is how to handle the Deadlocks and there be basically two approaches to this um um deadlock detection is using a background thread to figure out background worker to figure out when there's a deadlock and go ahead and try to break it and then prevention is the idea is like we're going to H order the way in which transaction of L acquire locks in such a way that we we guarantee that there won't couldn't possibly be a
30:14 deadlock so we go back here uh we have transaction T1 wants to take an exclusive lock on a and relock and take do a read and then lock on B T2 once gets a share lock on B take do a read on B and get a share lock on a so in this case here T1 starts gets exclusive lock on a that's fine T2 starts gets the share lock on B that's fine but then when it tries to get the Shar lock on a it has to stall and weight when T1 starts again tries to get the exclusive lock on B it stalls the hand the weight and of course this is your classic deadlock so this is the problem we're trying to avoid here right that that transactions could be waiting to require locks that being held by another transaction but that other transaction
30:50 is holding the lock that that we hold uh and they're waiting for get a lock that we hold right classic classic O Level parallel programing deadlock so it's essentially again a cycle of transaction that are waiting for locks to release by another that are never going to get released cuz un let we let's we do something so I said there's going to be two approaches here there'll be deadlock detection and Deadlock prevention and the one of the main takeaways is that the Enterprise
31:16 systems the high-end oracles and so forth like systems cost a lot of money they're actually going to implement both of these and they will have uh ways to toggle on one versus another based on the workload and they're also going to maintain a bunch of additional statistics internally in the system to make better decisions of how which one should you use and then if you have to do dead detection how you know what what transaction should you kill and and steal their locks from to give it to the other transaction uh in such a way that you can you can minimize amount of wayte to work and and improve your
31:48 performance but we'll cover with those protocols what those those this metrics are later on in a second so with deadlock detection the idea is here is that we're going to allow transactions to acquire locks as they need them or as they want them and then there'll be a background worker that that occasionally wakes up and looks at the a waight for a graph which is basically keeping track of what lock what transactions are waiting for what other
32:11 transactions and if it detects a cycle in that weight graph it knows that it has to go ahead and and choose a victim to kill you know take their wallet take their car take all their locks and give it to another transaction allow allow that transaction to run right and then of course now there's going to be this trade-off between how aggressive we want our this de loock detection worker to run right if we run it every 60 seconds then the overhead of checking the the for Cycles is pretty low but I may wor case scenario have to wait 60 seconds before
32:46 it can resolve a deadlock but if I have my deadlock detector run every every one Nan or one M microc then now I'm basically burning CPU Cycles checking for Deadlocks over and over again which I could have been using those resources to uh execute queries and execute transactions so again what the right mix of how aggressive you want to be depends on the workload depends on the hardare depends on a lot of different things that we've been talking about this entire
33:09 semester so let's look at simple example like this uh so again the T1 wants to get a share lock on B but that's being held by T2 T2 wants to get a share lock on excusive lock on C but that's being held by T3 and T3 wants to ex the lock on a but that's being held by T1 so I'm getting in this example here every time when one transaction is waiting for the lock for another transaction that waits for graph we introduce an edge so then now we got to run our cycle detection algorithm of which there are many pick your favorite uh and to decide which which one you want you know how to break this and so the way this typically Works since the since it's empty hard problem to find find these Cycles the they'll run a the DAV system will run a simp simple form where they maybe look for Cycles between just two transactions
33:55 like transaction one is waiting for transaction T2 and T2 is waiting for T1 so you do a quick pass to find Cycles to break uh uh really quickly using a a quick eristic algorithm but then if you don't find any any uh any Cycles just through that simple detection then you run the more expensive one uh that takes a longer time so that if you do that then you can find some quick quick things uh some obvious things pretty quickly um and avoid having to run a really large uh cycle detection algorithm uh that's that be more expensive again don't my example here I have three transaction in a high-end system they could be executing hundreds of thousands of of transactions a second
34:30 so in that environment you know you could have a huge graph with a huge number of Cycles uh with long edges and it might take a while to actually find them so you do the more expensive one only if you have to later
34:41 on so again the background worker runs the deadlock detection algorithm uh based on what we know in in our lock table in this lock manager again this is why we want to have that centralized data structure then has to decide which one's going to be the victim to go ahead and kill and steal their uh Ste steal their transaction to break the cycle and so what'll happen is the the when you identify the victim and you go ahead and abort it to break the cycle depending how the transaction was invoked you either have to send an exception back to
35:12 the client and say your transaction was killed please restart it or if it's in the case of a store procedure you could just actually just rerun it um from the very beginning um just you know invoke it as another RPC request and not have to alert the application you can maybe do this couple times and then if it still gets aborted then you then you only throw back the exception in that case so again as we said before there's there's a there's a trade opportunity how aggressive you want to be for running deadlock detection versus how much time you want to spend you know uh
35:40 you looking looking for uh looking for Cycles versus letting transactions run so now how to pick your your victim uh is a very complicated thing and this is what separates again the Enterprise systems from the open source ones um because there's a bunch of different things we consider uh in and a decision and again which may vary depending on the application needs and the Enterprise systems you can tune these these parameters to specify how you want to uh how you want to pick deadlock victims so it could be something like oh I want to run this transaction that is kill the transaction that's the oldest like it's been running for five days it might run for 500 days I don't want to wait let me just go ahead and kill it or you could say pick the youngest one because the transaction just showed up we'll go ahead and kill it and then the application can then resubmit it right
36:23 away it could be by based on how many queries they've already executed so so far so I've executed say a thousand queries maybe I'm less likely to go ahead and kill that versus a query that has run one query um because if I roll back th queries they may have to resit that again I have to do a th queries all over again and that would be you know a waste of resources to do that it could be the number of items that they've already locked so maybe I've only executed two queries but I've acquired a billion locks for some reason getting all those locks in the lock manager are
36:55 expensive uh so I don't want to have to that work and so I'm better off killing another transaction that has less locks could be the the number of times a transaction uh the the times youve roll back a given transaction before so if this transaction keeps getting roll back over and over again I may get so sympathetic and say okay well I can't just keep killing this guy I got to let him run at some point so after a certain amount of time you know if you can roll back 10 times then the data sets said okay well you've suffered enough uh let me go ahead and let let you uh you let you on again so
37:30 there's this is important because you you you want to you know you don't want to starve transactions actually so mistake I made was the by the number of transactions roll back with again that's the cas gting board thing if we have to kill this transaction but we know there's a thousand transactions that depend on what it wrote so if I kill this one transaction to break this break the deadlock I have to kill another thousand transactions as well then that may be really expensive than just killing one transaction by s so again like there's so many different factors you could account for all these things uh and getting this right is like super hard to do and this again the Enterprise systems can be a bit adaptive on this and try things out learn from that and get better over time in some cases they would just punt that out to assume a
38:13 experienced humans going to know how to set these things and the last one I was just saying is what I said before like if we know the transaction has been rested a ton of times we don't want to have it burn Cycles uh you we want be sympathetic say okay well you You'you've gone you've been restarted enough you can go ahead and run
38:29 all right so now the question is how far do you want to roll back and so the most simplistic thing to do is say just roll back everything that that the the transaction is done and start it from the beginning or you know punt it back to the application say restart it if you want to run it again um there are in some cases where you can run roll back to do partial roll backs to save points
38:48 think of this as like a a marker in the life of a transaction like you give it like a name or a number and you say I've done a bunch of work and it here's now here's a save point and then the transaction keeps on running so now but though if there's a deadlock I can roll back partially the changes back to that last save point and then resubmit things all over again um you typically only want to do this uh if you typically want to do this if you uh if you're running
39:16 like store procedures because you you don't know whether there's application logic where like given some output uh you given some result of a query have an if Clause that you know maybe runs one CER if if it's this if it's another love query if that without that logic running the system you may do the wrong thing um but you can do partial rollbacks and and still or end up with a serializable ordering in some
39:39 cases all right so that's deadlock detection right it's a background thread running to figure out what what to go ahead and kill the alternative is to do deadlock uh prevention the idea is that when a transaction goes to request a lock you decide at that moment are you allowed to take this lock or not uh and if it's being held by somebody else you decide okay am I allowed to wait for the lock or do I am I allowed to go kill the other guy take their wallet take their locks or do I commit suicide and kill myself because I if I I can't wait right so in this approach we don't require the background worker we don't need that waight for graph uh we're not looking for Cycles because again Cycles aren't going to be able to occur because in the way in in which we order the request and what transactions allowed to wait for other transactions we can guarantee that we're not going to have uh any deadlocks
40:28 so for this we're going to assume that the the older transaction the one with the older time stamp is going to have a higher priority um so we just assume transactions are assigned time samps when when they show up and the older you are potentially the the higher priority
40:44 and so the two variants of this deadlock prevention algorithm are going to be wait and die and wound and weight and the way to think about this is going to be and what age of a transaction is a if you have the age of one transaction and the age of another transaction they're never going to be equal because otherwise they'd be the same transaction
41:01 then the protocol specifies if I'm younger than them what do I do if they're older if I'm older than them what am I allowed to do and so wait and die the idea is that the old is allowed to wait for the young so if a requesting transaction comes along and they have a higher priority than the holding transaction um meaning the other transaction is older then we're allowed to wait for for that transaction to to
41:25 to release the lock and then then we acquire and get into what you want otherwise if we're younger than them then we we have to go kill ourselves because we we are not allowed to wait wounded weight is the opposite the young is lowed weight for the old so if the requesting transaction has a higher party than the holding transaction then the holding transaction has to abort uh you're allowed to shoot that other transaction kill them and abort them and then take take their lock and releases it otherwise you go ahead and
41:53 wait so looking at really simple two examples like this so T1 starts in the top here uh T1 is going to have a a older time stamp than T2 like one is less than two so at the very beginning T1 starts then T2 starts then T2 gets exclusive lock on a then T1 wants to acquire that exclusive lock on a and then now depending on what protocol we're using uh if if it's weight and die old weights or young then since T1 is older it's allowed to wait for T2 since T2 is younger uh or under wounded weight which is Young weights for old and that case uh T1 is allowed to shoot T T2
42:32 cause them to abort and then take take their locks and then down here at the bottom it's the opposite T1 starts it gets the S lock on a T2 wins the acquire the lock that lock on T1 on weight and die which is the old weights for young T2 has aort because T1 is older than T2 the young are not allowed to wait for the old on weight die so t T2 has to just give up an abort and kill
42:59 themselves in wound and weight since the young is allowed to wait for old uh T2 can wait for T T1 to release the lock and then then go ahead and inquire and do it at once so why does this work why does why can we guarantee that there's no Deadlocks well in the same way that we talked about with in a B+ tree when we were doing uh latching ignoring the sibling pointers where we had transactions only acquiring latches in One Direction like from the top of the B plus3 down to the bottom we weren't having anybody coming up from the the bottom to the top right this guarantees
43:29 that you know under weight and dying we wait since all of the the the weights of taquire latches are going or locks going in one direction we don't have anybody going in the other direction there can't be any
43:42 Deadlocks so now when a transaction restarts um to prevent it from getting re uh start for resources if a transaction gets aborted when it gets restarted it uses the same time stamp that it had before and then that guarantees that it's not just given a new time stamp over and over again and therefore may try to acquire locks over and over again and not be able to get them and get killed off So eventually it'll be the oldest person there the oldest transaction in the uh you know in in the system so depending on the protocol it could it'll be able to get the the locks that it either wants right away or it's allowed to wait for to get the chir locks that it needed and not have to
44:21 abort all right so everything we talked about so far have has been about assuming that for for one lock it goes to one object and again I've been being vague I haven't said what we're locking I said they're database objects you kind of assume that they're like tup but it doesn't necessarily have to be could have been a database could have been a table it doesn't matter and so the challenge with this this approach one to one mapping between the object we're trying to you know for a lock and an object the problem with this is that if we have to require a lot of locks then that's expensive again going to the lock manager is is is not like trying to acquire a latch because I I got to take latches to get into the lock manager table and then I may have to go go read some data update a queue and so forth right that's a very expensive to do
45:08 so if I have to do that for a billion times or a billion tubles that's going to be really expensive and so we're willing to make that trade-off because again the in the transaction world the the the the work we're doing for on an object require the locks for that could be you know could be milliseconds could be seconds could be hours days in some cases and so it's okay to pay that penalty to have to go maintain the go update the lock information but again we want to avoid maybe in the common case having to do that
45:44 excessively so this is why we're going to introduce uh now Hol locking through lock different lock granularities so now when a transaction wants acquire a lock and we can decide what scope what granularity it wants to acquire that lock four to try to balance the uh the need to to to or balance the acquiring as many locks that that it absolutely
46:08 needs uh versus maximizing the amount of parallels when want so there's this trade up between I can take very coar grain locks and therefore I only have to go to lock manager a small number of times but then that blocks anybody else from running in my system right when DB was first uh came out they had a single lock for the entire database that means nobody could read and write to the database while somebody was updating even one Tu even though it may be updating other parts of the database
46:32 that wouldn't be affected by that so that's really easy to implement because it's a single lock but you get terrible parallelism because now everyone's blocked behind uh a single writer giv me this Trail between trying to acquire the fewest locks that we need but also balance the the the granularity of those locks so that we can still get good
46:53 parallelism so the way to think about this is now your Davis is is is is represented in a hierarchy so you have a database at the top and the database is comprised of tables tables are comprised of pages uh or groupings of row groups or groupings of of of of tupal and then with those tupal we can have uh multiple attributes so now when T1 comes along and it gets a lock say on on a table that implicitly locks everything below it in the hierarchy from all all its descendants from that that node in the in the tree so if I get a lock on on the table I'm implicit locking all the things down below because everyone has to come through that same hierarchy when I want to acire Locks has to go in the in follow the same protocol and go in the same order that we saw
47:36 before so in terms of how these things are how how how common are these these different kind of lock hierarchies are implemented the most common ones be locks on tables and locks on tubles uh locks on pages are probably uh the next most common thing but not all systems actually Implement them uh locking databases are
47:57 some systems will do that if you're doing dmls or sorry ddls make changes to the schema but it's it's it's it's not as common as like locking tables and tupal and then super rare is being having sort of really fine grain locks on on individual attributes interal columns uh the only system I actually know that can do that that know that does this is um is yugabyte right they have a Cas they have an example where like you could uh instead of you try to C lock on two but you recognize you're only updating a you know some small set batteries you convert that actually down into a to lock on the on the columns
48:30 again that can try to maximize amount of parallelism in the system in that case all right so now now we're going to introduce additional lock modes and because now we're going to have this hierarchy because it may be the case that if we have to go acquire locks in this hierarchy uh at the upper levels in the system maybe you know if we have to update a a single tubal we don't want to acquire exclusive lock from the entire database entire table or you know a group a group of tubles and so but we still want to have a a way to provide hints to other transactions that may be trying to do uh do other types of locking in the hierarchy about what's going on down below without explicitly having to record
49:09 everything so this is where these new atttention locks are to come in and the idea again these are hints uh at a higher level node in this hierarchy to to instruct or tell the other transactions in that you're taking things in a shared exclusive mode at at lower parts of of the tree so the idea is that the intention locks tell you that somewhere down below I I have something an explicit locking mode but I have S this this fuzzy
49:35 intention locks up above and again it's just just just for hints so the the three types of intention locks are intention shared attention exclusive and shared intention exclusive so attention shared is saying that I'm I'm giving you hint to say at some lower point in the hierarchy I'm taking something with explicit uh shared lock tension exclusive is the opposite saying someone below me I'm taking something in an explicit exclusive lock and that prevents someone from again from taking incompatible locks that may be trying to read the whole all the tubl
50:09 but you know you need to update one of them so the intention exclusive can block them from doing that share and intention exclusive is really two locks put together so it's the regular shared lock we talked about before but then also an intention exclusive lock and so you would do this to say like I want to be able to read everything below me and and read that in a Shar mode blck but I'm also going to be updating a subset
50:32 potentially or some number of of those of object Peli in hierarchy in exclusive mode but I have not taken the whole thing as as an exclusive lock so again it's a way to introduce additional amount of parallelism but still have the hinting capability uh somewhere in between a shared you know a a shared lock or intention exclusive lock and a all sorry a shared lock and exclusive lock it's some want to say like it's a share lock but also like I'm modifying some
51:01 things so I'm I'm not going to go through the The Matrix like this but you can start to see it gets more complicated again the the intention shared is pretty much compatible with everything except for uh exclusive Lo exclusive mode locks um you if you have exclusive modes that blocks everything but then as you as you sort of have higher levels of intention or shared intention um then then you know it becomes more restrictive what you can
51:25 do so the protocol is going work like this it's the same thing as that two-phase locking that before so it's still going to have the growing phase and the shrinking phase right whether you're using strong strict or or regular two locking all that's going to be the
51:39 same so now what's going to happen though is that we have to Traverse that hierarchy and we we want to acquire try to decide what's the appropriate lock to acquire at some given level of the hierarchy and usually try to take uh intention locks as far as can to you get the very bottom where then you get actually get the the explicit locks of the things you want but it may be the case that as you're going down you
52:04 recognize uh that maybe I took something at a higher level in in intention mode lock and you realize that was a mistake I just want to go back and and go explicitly convert it into a share and exclusive lock and so you you can go back up the hierarchy and and Es or upgrade a lock type if you recognize that things aren't going the way you thought they were going to go so the
52:27 you start to see why the now we have all these different objects we want to take acire locks on and we have all these different lock modes we could have um this is why the the lock manager the lock table itself isn't going to be a regular table because if you think about if I have a a billion tupal I want a billion entries in my lock table for uh you know for any possible lock I'm going to take on those tupal instead the the lock table is meant to be a dynamic
52:52 where I can if I recognize that no one has a lock on something anymore I could go ahead and delete it to free up space right or if I bulkload a billion tupos but I only lock 100 of them for my transactions I don't I'm not wasting space in my lock table for you for all those to that no one's ever going to run in context of a
53:10 transaction all right so let's look at uh first example here um and we're going to be doing a getting the balance of my bank account and then also increase the increase my bookies bank account uh compute interest own by by
53:24 1% now the question is what locks are we going to obtain so for all the leaf nodes those you have to acquire in explicit mode so either shared mode or exclusive mode um but then the higher level uh we're going to try to acquire things in intention locks but we recognize in some cases it makes sense to go back and put into exposive mode we we can go ahead and do that so for Simplicity I'm not going to show uh attribute level locks or um page locks or or databas locks keep it simple do a to level hierarchy so T1 starts I'm going to read the record on a so what it wants to do is figure out how to get through the table to find the TU that that's down here that it wants to read
54:04 so the question is what lock do we want to acquire at the table level before we acquire the shared lock down below so in this case here we can say we can do an attention shared lock and say hey down below me in this table I'm taking one of these tupal one or more of these tup in shared mode I don't know what they are at this point I don't need to record that in the higher level of the hierarchy it's just a hint to say if you're coming down through hierarchy uh be aware that I have something down below in in shared mode and that might be incompatible with somebody else coming along later uh later on so once I have the intention shared lock on the on the table then I go ahead and get the shared lock uh on on the tupal and go ahead and do my
54:43 read now in case of T2 it wants to update the bank account record so now we got to look at the compatibility M and say what lock should we take on the table table level before we take the exclusive lock on the the tuo down below
54:57 so in this case here we want an intention share sorry intention exclusive because that's going to be a hint to say again it's somewhere in this table I'm I'm I'm taking a tubal in exclusive mode I don't know where but just be aware that this is happening and so it turns out now according to the C Matrix intention shared is compatible with intention exclusive so both transactions can hold uh different locks on the same object at the same time that are compatible so again now we need to keep track of what mode what locks are being held for a given object could be one or more and what modes they're actually
55:34 in all right so let's look more complicated example we have three transactions running T1 wants to read all the tupes in R and then update one of them T2 wants to read a single tupal in R and then T3 wants to just read all the tupes in R so when T1 starts again we got to go through the hierarchy and again it wants to read all the tupal but one of them is going to do a read followed by a write
55:57 so in this casee here we want to get a shared intention exclusive lock so what this is going to do for us is that the shared portion of this SI lock gets all the tupal uh at at the leaf nodes in the hierarchy in shared mode automatically because we have the table locked in shared mode but then there also an additional hint to say hey down below one of these tupal is going to be locked in exclusive mode I don't know which one it is again but like that's enough at the the high level hierarchy to tell you that there's something going on down below that does
56:28 this so now T2 comes along and it wants to read this one Tuple down here it's not the one being held in exclusive mode so in theory we should be able to allow these two transactions to run simultaneously at the same time so again looking at a compatib matrix the we can see that we can take an intention shared lock on the root node and that's compatible with the shared intention exclusive
56:50 mode um and then down below it can then take the share lock on 2 one right right and go ahead and read it now if you try to read the Tuple that was being Modified by T1 well the exclusive lock is obviously incompatible with the shared lock so it would have to stall and wait for that and depending we're doing deadlock detection or uh a wait and die we'd wait we have to decide how to resolve that at some point but in our example here it worked out just fine so now when T3 starts it wants to scan all the tuples in R down below so to do this it wants to get the the shared lock uh on something down Bel low but the say wants to get the share loock on the on the on the
57:31 table that's not compatible with Shar intention exclusive and and uh being held by T1 so therefore it has to stall in weight right so then now when t t T1 and T2 and T1 finish uh then now T3 can go ahead and get the shared lock on on on the table R and now go ahead and and can scan read everything
57:57 so as as I said before we we can support lock escalation so if we recognize that we the data can recognize that I'm acquiring a lot of locks at this lower level explicitly then it might be better off just go back up the hierarchy and escalate the lock I have up there to put into an explicit mode so I then get all the locks without having to have you know every entry for every single one of them inside my lock table I can this reduces the number of times I have to go to lock measure which I have to protect with latches just as as if it was my page table or any other data instruction in the system so now that you know if I'm going back in and out of the lock bager over and over again then there's going to be tension on those latches which would uh slow things
58:35 down all right so as I said the in in practice uh you typically don't specify I want I want chire lock or unlock things um again when you run a select query or Run update insert update delad query the the data system will automatically acquire the locks you need uh in the right mode for you automatic
58:57 um but there may be in some cases where you actually want to give hints to the database system and tell it about how you plan to use data use objects in the database uh so that you can override maybe what lock would normally try to acquire for you and put it in the mode that you know is going to help you later on it's like a hint to say here's what's going to happen later on my transaction
59:20 do acquire locks in this way for me and that'll make things better for us later on uh you can acquire exclusive locks on on databases uh we'll see example in in class next time on these advisory locks and postgress like these unnamed or these named objects you require locks on um and you can do certain things like
59:40 you can some systems acquire explicit locks and things but most applications aren't written that way so let me look at two two examples doing hints so the first to do is Select for update so so again when when you run a select query the data system will automatically lock any object you're reading in into shared mode but again a very common pattern is to do read modify WR and you saw this example of like my my transfering money in the bank account I had to read the record first then I modified it then wrote it back to the database with the new value so in that scenario if I if I was just doing the shared lock when I did the first select
1:00:16 I then have to go back into the lock manager then then upgrade my lock to an exclusive uh exclusive mode when the the update query comes the right query comes so instead I can add this modifier to my select queries I add this for update keyword at the end so now when I run the query it says run this Select Produce the result as a normal select would but when you acquire locks on anything don't acquire it in share mode acquire it for in in exclusive mode because I'm going to go ahead and update it later on so you're and that forces the system to acquire the the locks in right mode or
1:00:46 uh exclusive mode at the moment it tries to acquire them and read them because you know you're going to update things later on and in this this um a screenshot here from the postgress uh documentation you can see there's a bunch of different variations for this um you can set shared locks you do selects for you know select for share which is uh the ideas there if you're not running with serializable isolation you're running a low isolation level it forces transactions to hold locks uh maybe longer than they normally would at a lower isolation level um post I seel this and but SL for update is very common most systems actually support
1:01:22 this another one that's kind of cool is called F skip locked and so the idea here is that I can perform a select query but instead of waiting around to acquire locks on any data that I may want to read from my select I can tell the data system just just ignore it just skip anything that's that's locked and a locked it's already locked and I can't get it right so again think about sequential scan if I'm scanning and another transaction is updating data at the same time when I do that scan and it sees
1:01:54 that uh it sees that that the tup is locked with my uh skip locked modifier I just go ahead and skip it so may you say how's this actually useful why would any actually do this so a common design pattern is actually to put a to use a data system for as a queue so you could have a table here's all the the task that I'm putting into the queue and you can have a bunch of workers pulling the
1:02:19 the the most recent entry to pop out to process and work so in that casee the way it would work is like you would have a trans action start read the table pull out the first one essentially delete it or Market is being uh completed and then go ahead and commit but now another worker may come along and try to want to get the next task to do but it doesn't actually want the very first one that's that's already being held by another transaction it just can skip that one's locked and pick pick the next one right
1:02:46 so it's kind of it's kind of a cool idea it just starts to leak the abstractions transactions into the application which you you could argue is a good idea or a bad idea um uh I I think it's cool because again I I like transactions and it's it's it's a uh it's a different variations to try to do you know different variations on the basic protocol to handle different application scenarios um so I think it's worth
1:03:11 pursuing all right so to finish up uh two phase locking is used almost in every single data system we'll see next class optimistic currency control uh which is uh uh not as common um T locking is isn't is in most systems that that you can think of um but the OCC is still really important and using in other systems and again what two- phase locking at its core is doing it's it's generating it's automatically generating inter leading of transactions that can guarantee things that are scheduled that are conflict sterilizable in the case of using strong stri 2pl you can guarantee
1:03:45 that you don't have any cascading aborts we said how we looked how to handle Deadlocks either through detection mechanisms or prevention protocols um there's a bunch of other aspects of transactions that we haven't talked about we can talk about later on like n transactions we talked a little bit about save points uh there's there multi no transactions that distributed transactions we'll cover when we talk about distributed Daves later on the semester like transactions are super cool it's a super hard problem it's really hard to get right as I said it's the second hardest thing after query
1:04:12 optimization um but you know it's a really fascinating topic and people are still trying to make these things faster even even today all right so next class again as I said we'll talk about time time stamp ordering optimistic protocols and then we'll also finish up talking about uh variations isolation levels and additional anomalies that we haven't talked about so far
1:04:32 okay something refreshing when I get finished manifesting to cold a whole B like Smith and Weston one court and my th's hip hop related right R in my pants intoxicated lyrics are quicker with a simple Mo licker since I'm a city slicker play waves are picker rhms I create rotate at a r you quick to duplicate F A breze at a skate mik at Fahrenheit when now holding real tight then I'm in flight then we ignite Blood starts to Bo you I heat up the party for you let my girl R here 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 like The Temper to rise to cool it off with same eyes
1:05:18 [Music]