CMU Database Group · 1:16:42 · https://www.youtube.com/watch?v=lgUNTj0Q54M
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 lot discuss this this be really fun lecture uh it's concurr stuff which I find super fascinating because it really breaks can break your mind sometimes thinking about like how you normally write programs and what's going on on the inside and what the application can see um we'll talk a little B about that today um for every in the class again project one was due last night um the again without naming names but we were discussing this uh someone got the highest score we've ever gotten on the leaderboard this semester
0:55 uh so congrats to that person um like normally 25 ,000 QPS is what we nor see on the leaderboard uh but someone got 150,000 which you've never had before and then we just saw this on the the nonia one then the the fastest we ever seen somebody who not seen you was
1:10 95,000 so 150,000 is is blowing everyone out of the water impressive all right so homework 3 is out and that'll be due uh this Sunday actually October 6th not September 6th is that even the right date yeah when is it when does that really do should be next week right yeah whatever this whatever this is wrong go by the website uh project two is out today I don't think we pushed the code yet but the write up is there and you can start looking at that and I'll discuss this the end of this class and uh we announce the recitation for next week and I'm going to say this multiple times throughout for the next three weeks
1:44 project two is much much harder than project one so there was a bunch of people that waited the last minute to do project one and yeah you got it in good you're not going to be able to pull that same stunt off this time okay so you should be doing project two immediately as soon as the code comes out start looking at it and start writing it immediately it will be much much harder much more difficult right and you're not going to get by running printf statements to try to debug things anymore you have to really use a debugger the midterm exam will be again in class on uh on Wednesday October 9th again in this room and then we'll I'll announce this and post the study guide
2:19 uh later this week okay I'll say also to a quick about project one the there was a couple people that used either chat TBT or found some rando's implementation on GitHub and we changed the semantics of the buffer pool this year from previous years as they kept breaking a bunch of tests and not knowing why uh they were failing it's because again things have slightly changed from year to year so I advise you again don't don't do that uh you're making your life
2:44 harder all right and then for some database talks coming up today again at at 4:30 we have the actually the creator of data Fusion uh is going to talk about something they've built at apple called Data Fusion Comet it'll be a spark accelerator for or accelerator for spark basically Sparks in Java it's row based it's slow uh we'll talk about next class what it means to be Vector based and then so when you're running your spark query it can drop down into Data fusion and run that really really quickly data bricks has their own thing called Photon
3:12 that's proprietary it's not open source this thing is open source all and then also tomorrow we're having a talk from one of the top people at Oracle talking about their their Json storage system uh and that'll be in Gates 8115 and that one would would be pizza and that's open to the public and then next week we have parade DB which is a uh it's a the version of postest where it drops down into Data Fusion uh and other rust rust
3:35 uh toolkits or libraries to accelerate the executional queries so it looks like post on the outside but the inside is doing a lot more okay again and these are all optional all right so last class we talked about different data structures right skip list inverted indexes Vector indexes uh blo filters are filtering um and when we talked about the B+ trees when talk about the hasht talk about these other data structures we made this huge assumption that the the the data structure we were talking about would be single threaded we did this to simplify
4:08 the discussion so we not worried about tripping over different threads updating things at the same time but obviously in in a in a modern system we need able to support multiple workers you threads or processes we'll talk about later but multiple workers running at the same time that want to make changes to our data structure and we need to make sure that we don't break things right and so that's what today's class is really about is how we introduce safety mechanisms in our data structure so that we can take advantage
4:36 of a modern CPU that has a lot of cores or when one thread stalls because it has to get something from disc or over the network right that we can allow other threads to keep running at the same time and hide those stalls that L the dis stall will be less of an issue for for uh maybe for the dash we're talking about unless there's there's you know you have to get something from from disc into memory um
4:58 but the other mechanism we talk about transactions later on that that can hide these things as well but it's really about these lowlevel PRI how to make our our our data structure thread safe now I will say we're not going to talk about it but there's a whole other category database systems that don't do any of the things that we're going to talk about today and because there's an argument to be made that introducing the latching protocols that we'll talk about
5:19 just makes things slower and that you actually would be faster if you just allow things to run single threaded like only one all one thread to do one thing at a time and then you don't have to do latching and that'll make things actually run fast fast as possible you're basically running a bare metal speed so most famous one is probably redus you might have heard that before do that's a single thread execution engine single process single thread so only one query within the process can touch the databas at a time and therefore you don't need any latches
5:46 because there there there won't be any conflicts uh there's volt DB it takes this to the extreme um that was based on a system I help built called called HTO there's another system called kdb out of this thing called KX you've never heard of kdb you probably never never will see kdb unless you go to Wall Street this thing is everywhere and it doesn't use SE it has its own K programming language but again the end the core engine itself is single threaded so it doesn't do a lot of these latching
6:14 stuff all right so how are we going to make sure that our threads don't trip on each other uh when we're when we're inside of our data stru inside the system so this is can be done through what is called a concurrency to protocol
6:26 and you can think of this as like the traffic cop inside the database syst that is responsible for determining what thread or what worker is allowed to read what data at what time and in what way right the idea is like it's the thing we're going to use to protect a shared object or entity within our system to ensure
6:44 correctness and I'm putting the word correct in quotes here because there's two Notions of correctness we we could care about there's logical correctness would be can my worker can my thread see the things that it should be allowed to see while it's running meaning like if I insert insert you know key five if I do a read again can I see while I see key five or could have come back missing meaning someone like deleted it by the time I did my reads right that's a higher level concept of correctness that we'll we'll cover after the midterm but
7:15 you'll see why we'll make certain decisions today where we know that something else is going to be responsible for maintaining this this logical correctness and there there's some optimizations we can do to uh to not slow things down the thing we're care about today is the physical correctness meaning how do we make sure that the internal representation of our data structure is is going to be sound or correct meaning if I do a look up of you know in a B+ tree and I I get a pointer to the next page that page that pointer is going to take me somewhere real right either a memory address or a page that actually exists which should be you know part of the B+ tree and not some random allet
7:53 and not some random page with a bunch of garbage in it because by the time I'd read it you I I got the I got the page I'm at I read the pointer then I before I can follow that pointer someone changes what the memory is pointing to underneath and then now I land in in no man's L and I seg faal so that's the thing we're care about today how do we make sure that the the data structure is correct when multiple threads are reading and writing to it at the same
8:16 time so begin to begin we'll talk about what latches are how you actually want to implement them and this going to be a high level over to understand what's going on underneath the covers with latching so that when we start using them in our system we can understand the ram ifications of protecting data structures with latches in one way versus another then we'll see a really simple latching scheme for hash tables
8:38 uh which would be pretty Tri to understand because hash tables are by themselves pretty simple but then we'll spend most of our time talking about B+ tree latching because that's the what you need for project two but also this is a more complicated scenario because you could have threads coming in different directions and splits and merges and the data structure is more Dynamic than than a hash table and then we'll finish off talking about how to do Lea not scans on the sibling pointers and then we'll finish up talking about project two
9:02 okay like I said I'm going to get very excited because to me this is this stuff is really cool uh but you tell me to slow down if I go too fast all right so we talked about this in the beginning in the semester we talked about this notion between locks versus latches and this is sort of like this this conflict between what we in the database World think about the semantics or how to describe certain
9:23 Concepts in in systems and what everyone else the operating system world people how they're describe things and we're correct and they're wrong uh least you know within the database system so there's a notion between a lock and a latch and a lock is going to be used to protect transactions from each other and latches are going to be used to protect workers meaning processes or threads like lowlevel things running in the system so a lock is going to be held for
9:48 the the duration of a transaction I haven't defined what a transaction is but think of like running multiple queries at the same time and I want them to be Atomic and they're going to be protecting The Logical contents of of the database a table a database itself a a single tupal and then the database system is going to be have mechanisms inside that it's going to implement in its concurrency show protocol that it's going to allow it to detect when there's
10:14 conflicts when there's Deadlocks or other problems and can automatically roll back changes to make sure that we don't have partial rights or torn updates right this is what sort of handling the unwashed masses like the JavaScript program is sending us crappy queries or whatever and we need handle that in in our
10:31 system the thing we care about today is is the latching again this is where we're we we we have these Primitives uh that allow us to protect critical sections of our data structures of our internals of our system that are going to be uh affected or touched by others working workers that we've implemented in our system running at the same time
10:54 so the critical sections for the the latches we protect are going to be really small relative to what locks are going to protect like think of lock as like I'm going to protect a tupal through multiple round trips between the application and and the database server back and forth like that could be
11:08 typically millisecs but could order in seconds worst case scenario order hours days and the old days you could have queries you know run for hours and days uh less it's more rare now but but in this in this world it's like an low level like I'm going to jump into a page do something that jump out right away right almost like the pin stuff you did for for the buffer pole and now the thing about the latches that there isn't going to be a highle traffic cop in our system that we're going to implement
11:36 that's going to be responsible for deciding who gets to read what at what time and how to deal with deadlocks it's only through us as the Sy programmers it's our responsibility to make sure that we don't do something stupid easier said than done we'll talk about how to handle some things later on but like there isn't going to be something to bail us out in the way that we'll have for locks and transactions right there won't be a deadlock detection algorithm running in the
11:58 background another way to think about it is this nice table from uh the guy this guy G scy uh again a famous database researcher he wrote that B+ Tre book I mentioned last class he's going to vent the volcano stuff we'll talk about next week he's GNA also invent a bunch of stuff with ciz we'll talk about later on but uh in the B plus book he's got this nice table where he shows the distinction between locks and latches
12:18 and the way to to read this is that sort of stop start from the to start from the top and go down and and that sort of defines what this thing is actually doing so in the case of latches a latch is going to be uh it's going to separate workers from each other that's going to protect the M data structures uh during during the operations dur the critical section we'll talk about modes in a second but it's only going to have two modes in a latch read and write right exclusive
12:42 non-exclusive and then for deadlock uh handling Deadlocks it's through avoidance through through coder discipline making sure that we don't write bad code that could put us into a deadlock and then we're going to maintain these latches inside our data structure again there isn't going to be a separate lock table there is like in case of transaction locks it's going to be in the in the pages themselves of our data structure is where we keep track of what latches are set or not
13:06 set locks on the other hand again we'll cover this at the midterm but again these these are for protecting transactions from each other there's a lot more modes shared exclusive update intention locks we'll cover these later on um but again and there'll be some some higher level mechanism that can protect ourselves from Deadlocks and and handle things you know like deciding what what thread to kill to break a deadlock whereas in our case we in latches we won't have
13:32 that all right so latches can only have latches going to have basically two modes read mode and write mode uh it's pretty much as you'd expect right so in read mode you you can have multiple threads read the same object at the same time and if the latch being that you want to acquire is already in read mode and you want to acquire in read mode then you you can go ahead and acquire it as well right basically have a simple counter that says how many latches hold this thing in read mode right mode is
14:00 you know a synonym for exclusive mode basically saying that there's some thread that can only have the latch and right mode at a time and any other uh latch acquisition requests are incompatible and therefore we'll have to wait right so basically read latch requests are compatible with read latches uh latches that already held in read mode and right latch requests are incompatible with everything
14:23 else so now if you actually want to start implementing latches uh there's some things we're going to care about in the Contex database because again these latches are going to be inlined in our data structure itself we obviously want them to have a small memory footprint and we don't want to store you know a kilobyte of data just for the latch because we could be said storing that for the data itself because that's going to be again have to sit in
14:46 somewhere in memory and the latches aren't going to you know even though we could store the latch itself in the page like within the frame of the buffer pool we don't care about when it gets written out the disc because uh you know you you wouldn't you wouldn't hold a latch for something that's going to get swapped out because then then the time that latch becomes too long and causes
15:05 problems we want to have a fast execution path when there's no conten in the latch which would be the common case in most scenarios right most of the times you're going to go request a latch and it's going to be available so you go ahead and acquire it and so you want that to be that operation to be fastest
15:19 possible we can't we want the the management of the latches to be decentralized again there isn't going to be a a higher level table that's keeping track of what latches are being held by what workers everything has to be done in line and then lastly we want to avoid expensive system calls because anytime we have to talk to the OS or go down to the OS that's just going to make things so much harder so much slower for
15:40 us right and again because we're database people we don't want to rely on operating system Primitives in a real system to do any of this the operating system people say the opposite right so there's this famous post from lonus uh from a few years ago talking about the pros cons of spin locks which we'll talk about in a second and he's got lonus has this big blurb right do not use spin locks in user space unless you actually know what you're doing and be aware that the likelihood you know what you're doing is actually basically nil right so again that's for the unwashed masses if you're actually someone responsible actually building a database system like we know what we're doing and he's actually
16:19 wrong so let's see how we can do better so I'm going to talk about basically three uh basic concepts that we can build on build up uh they're going to build one from on top one one on top of the other um and we're going to end building what essentially what is a reader writer lock now what I'll describe is how to do it in the context of of an the P threads or standard in the standard template library but in a real system you wouldn't rely again on P threads or Os Os level Primitives but for Simplicity I'm just going to show it in those terms there more advanced imitations that we're not going to cover in this class we covered the advanced class uh or adaptive spin locks from Apple uh the qbas spin lock from MCS locks and then there's this thing optimistic lock coupling that's used in
17:01 uh some of the German systems that basically has version information when you when you acquire latches I would say at this point I haven't looked in a while like what is the best latching lication you should use I mean post has its own thing like a lot of Open Source systems have have their own implementations that are pretty primitive uh compared to the modern things you can do um and then obviously the the commercial systems are are closed Source you can't see what they are I mean and the a lot of the commercial systems they have to be also portable right so like the P thread implementation on like FreeBSD might be is is definitely different than what's on on Linux and so they'll they don't want to rely on on the OS providing these Primitives and therefore they they they ship their own so that way the the semantics and the expected Behavior will be mostly the same from one system to the
17:46 next but just to highlight again how how what extra things you can do so this is the a Blog article from almost almost 10 years ago eight years ago from from Apple talking about their locking mechanism called uh parking lot which again as far as I know this is the best one that's still open source today um and so they had this little blurb here talking about how if you rely on P thread mutex their implementation is 64 times smaller uh and 180 times faster
18:11 than what the OS provides you and again that's like that's like a hardcoree like tight Loop Benchmark micro Benchmark um but when they say we actually run it compared to other things you know in sort of more full full workloads about 10 to 5% faster and just just replacing the latch implementation you can get a pretty significant
18:30 Improvement all right so let's look at the most basic lat you can Implement right the test and set spin latch or spin lock right and so the way this basically works is that it's you declare some flag or some some variable as as what as the latch so here I'm using syntactic sugar in C++ to say Atomic flag uh and Define my latch and this just again a synonym for uh defining an atomic Boolean and so this is going to create a you know 8bit value that I can set call test and set on and so now if I want to acquire a latch I just have something like this where I find the latch that I want to acquire and then I have a while that says keep trying to to test and see whether it's false and then if it's false set it to true and then if you're able to do that return true uh
19:20 should be actually while test and Le yeah if you if you can if you can set it actually this return to should be a knot here right so try to try to get it if you can't set it just Spin and keep trying over and over again so that's why it's called a spin lock you're just basically spinning over and over again until you can acquire the lock that you want the latch that you
19:37 want so this is obviously not scalable because what are you doing here if I can't get the latch I'm just burning CPU Cycles trying to set it over and over again um so you can inside this wild Loop you can be a bit more clever you can say well I've tried you know a million times let me stop and break out return back in air which we'll talk about how to handle that in a second or I could yield my thread and say well I can't get this now let me sleep for a little bit then then try again um but even if you do all those things this is not going to be very friendly for modern CPUs especially if you're running on a multi-socket system because now depending on where the latch is located
20:11 you might be going over an interconnect between the sockets trying to update things over and over again or check things over and over again so we're not going to talk about like Numa architectures in this class but say you have a two socket CPU and the latches over here on this side so this if you have a thread over here running on this socket and once acquire the latch it's calling this you know test and set over over the interconnect to try to get this value uh and that's going to be it's much much slower to go through that interconnect versus like running uh in local memory does everyone know what Numa is non-uniform memory access okay so Numa is this thing where um I think on a multi-socket CPU where every socket has its own local Dam that you can access really really fast but there there's other sockets you can also access their Dam but now you're going over this interconnect which I think is like 2x slower than your local Dam and so Intel does all these tricks to hide
21:03 that the location of memory from you so that you don't have to worry about that you know where is it actually located so it looks like giant uniform memory access even though the speed from one address might be different than another address you can get actually information about where the memory is located so you can be clever about like okay well I'm only going to access data that I know that's local my dam so all I'm trying to say is there's there's some interconnect
21:24 between these two so for me to go access this Dam that's 2x slower than the guy trying to go get it locally and so that sucks cuz now there's all this traffic on the interconnect again think of like you know two machines running in different data centers right it's not the same because we're talking about you know you know nanc but still it adds up you're trying to spin this to get this thing over and over
21:46 again all right does everyone know how this T Test and set works or compare and swap in Hardware all right so Modern Hardware modern CPUs provide you these Atomic instructions called test and set compare and swap right they're they're they're basically the same thing where you can give uh you you have an instruction where you can give it a memory address and a value you expect to be in that address and then within that single instruction it then checks to see what that value is what what you expect and if it is then you can go ahead and set it to your new value and you can do this again anatomically meaning like you know that somebody else isn't going to come in between the time you check and then you set it and try to try to write to before you
22:30 can right so this is a this is a built-in intrinsic I think this is GCC right simple compare and swap so anytime you see like a double underscore in any kind of code uh in C++ or C it's it's called an intrinsic think of like it's just an Al as to the underlying instruction that the harbor provides to do exactly this so even though instead of writing a ass you would use use an intrinsic right so in this case here I have the address the compare value and the new value so when this runs it takes that memory address looks to see what you know finds where it is checks to see whether the value is is that's in there is what you expect it to be and if it is
23:05 then again within within the a single Atomic operation you can go ahead and set it so I think Intel added this in x86 in the90s arm has their own version of this uh you typically don't want to write intrinsics because it makes the code less portable like if you land on x86 versus arm uh but you know if you know your own Hardware then you should be okay so the atomics came out in C++ 11 and there's this great blog article from the guy that I think he runs the standards committee that talks about what the the memory model and semantics of this are but for our purposes today we just need to know like I I want a single Atomic operation to set test some value and if I if it's correct then I go ahead and set it with what I want meaning I know I've acquired the
23:46 latch all right so that was the test and set that's the most basic one but in my example there it was a single bullan value meaning there wasn't different uh read write modes for that lash which is like do I have the Lash or not so if you want to do something that's a more complicated uh you can rely on start using OS Primitives like the OS blocking mutex so this is what you get if you call it standard mutex right so you say 10 m Tex M and then it has the lock and unlock operation all right so everybody know what you get when you call Standard mutex what what does the compiler actually give
24:20 you P thread mutex what is the P3 M Tex how's that implemented in Lent Linux what's that a fex fex exactly what is a fex it doesn't actually do a lot if there's only like one thread or there's no contention what what does fex stand for fast user fast user mutex and so his point yes like he was describing correctly uh so the way it basically works is that it's our spin latch that we had in the last last slide or two slides ago where that thing sits in user space and the idea is that you don't have to go down to the OS to try to acquire a heavyweight mutex you try to acquire the one in user cuz remember I said making system calls is very expensive right because there's there's
25:02 the security permissions it has to do with the hardware like you have to copy contacts it it sucks we never want to do that so if I now have two threads that try to acquire this latch they both first acquire try to acquire the user bace latch if one of them gets it then they have the latch the other guy has to go Den now down to the OS and and acquire lock conditional variable or mutex down there uh and and it waits until the other guy releases it
25:29 so I I've said before you know just now why system calls are expensive but now going down into the the to the schedule for the OS that's even worse because how does how does Linux maintain the list of of what threads to schedule or processes to schedule it's got it own hash table how's it protecting that it's got its own latches right so now you're taking latches down into this this this data structure to say hey I can't acquire this latch right now but you know wake me up or you know schedule me when it becomes available so now what should have been a single latch is multi multiple latches because I have to go tell the OS I can't be scheduled so that's terrible we never want to do
26:11 that so the and again but this example here it's still a single reader writer mode if you want to support reader writer latches there's more complicated examples but the at least in bus hub we're using the SD the Cent temp Shar mutex um but the you know any any other syst any other system would roll their own again relying on those those spin latches as basic Primitives and then what they do after that uh whether they have a queue and keep track of things that depends on the
26:40 implementation so if you call standard standard shared mutex what you get is a pthread rewrite lock uh which is actually a combination of some conditional variables and then another P thread M text which again is just a few texts so the basic idea is that in user space we would have a counter that keeps track of how many how many workers hold the latch in rewrite mode uh or different modes and then how many threads are waiting for for this again if you rely on the OS the OS is going to keep track of this for you down down in with the conditional variables down in the scheduler uh but we want to do this all all this in user space so now if a thread comes along and once acquire the latch in read mode we check to see whether anybody holds it in right mode
27:20 or read mode and they don't so we can go ahead and give it in read mode and we increment our counter by one another threat comes along was to also get in read mode again it's already in read mode uh so we can go ahead and give it the latch increment the counter let's say now the thread another thread comes along once to get in right mode it has to block and wait because the latch is being held in read mode so we would we would deschedule it put it in some kind of queue where we keep track of where it is and then now depending on on our scheduling policy if any other thread comes along and says I also want this now latch in read mode so even though it's I I can potentially get it because it's is going to be held in read mode because I have one writer waiting it's going to block and and uh and have to
28:01 sleep right this again some additional metadata cues are keeping track of who's Waiting For What and how long you've been waiting and other things it depends on sophistication it depends on um you know what data structure you want to use this in so if your critical section is really really short you probably maybe don't want to use something that's very heavy weight uh versus if the crital section might be a little bit longer maybe a couple micros seconds or even a
28:22 millisecond uh then then This heavyweight stuff might actually make sense but yes why do we want the third reader to be blocked question is why do you want the third reader to be blocked for fairness right because otherwise if readers keep showing up right I'll never put it in right mode so that's so that's a really simple scheduling policy you could do for this as soon as someone shows up and that's that's a writer the writer gets higher
28:48 priority okay okay so again the differ will do different things but these are the basic perimeters we need to do the more complicated latch we need for in our or in our data structures so let's start off with the easy case hash tables so we'll ignore the the the extendable hashing and the linear hatching uh which where you could resize things but the basic ideas are applicable to them that we'll talk about
29:13 so one of the advantages we're going to have in a hash table is that Deadlocks are not going to be possible because all the threads are going to move in the exact same direction meaning they're going to do some hash land in our data structure assuming it's linear probing it's you know a giant array of slots and then when they have to scan to find the matching key that they want they're just scanning from the top down and so as they go along they can release latches behind it to free things up and acquire new ones going forward but they know that nobody else is trying to acquire the latch uh that they need if you know if they need a latch we need a latch uh
29:51 and the person that holds the latch we need holds the latch he's waiting for our latch we know there can't be a deadlock because everyone's always going in the same direction Direction now de size the table do more complicated the most basic way to handle this is that you would have some some page at the top like the the the header of the the hash table and you just put a global right latch in that thing and anytime that you need to read it you just set it in read mode that's fine anytime you need to resize it you set it in write mode and then that locks the whole hash table and you go ahead and double the size and and rehash things
30:23 right but we can ignore that so the big question now which you want to do hashtable latching is which what what granularity we want to the granularity of the latches we want to have in our data structure because that's going to determine how much parallelism we'll be able to achieve but again it be classic computer science trade-off between compute versus storage
30:42 we could have a single latch for the entire data structure the amount of space it takes to store that single latch is small but then that makes our latch our our hasht will basically single threaded or we could have latches for every single individual slot that'll increase the amount of parallelism we have but again now we have to store that latch uh in our data structure in our in every single block or page so that's the basic two choices we have right so you can have either latches at the page of the block or the latches within each individual
31:09 slot so let's see what it looks like so say we do either the page or block latches so a thread T1 comes along they want to find D so the first thing we do is Hash D and say we land into this block here so I'll just take a BL a read latch on the entire block and so that that implicitly locks these slots with here within within my page or my my block then I can do the linear probe scanning go try to find the the record we want
31:36 right uh and then in the meantime another fed shows up and they want to insert e so when it it hashes it it want insert it into this record here right but now we want to take this latch and we want this take this block in in right mode but that's incompatible with the latch that's being held in read mode so this thread has to stall because we don't know what you know we don't know what what this thread's actually trying to do other than than it's just trying to read
32:03 things right we don't know there there could have been a free slot where it could have inserted something and not interfere with the the the other thre that's reading inside of it all right so then now T1 keeps scanning through the page and then when it's done it jumps down here uh it can go ahead and release the the latch on the first page even before it jumps to the second page down here because it's not dynamic we know that these things have to be read in in order right from top to the bottom so we can go ahead and release this latch even before we acquire the latch on this one here
32:37 because we know that someone isn't going to try to insert a new page inside inside inside here while we're we're going into it so we're not going to be do be able to do this when we talk about B plus trees we have to hold on the latch where we're currently at before we jump to the next page for the next node and acquire that latch because we don't know whether someone's going to start reorganizing things and swapp out where where we actually should be going to so this is one of the key difference between hash tables and B plus trees all right so then now again it gets the relash do a read here the t2 can can then acquire the the right latch on this page go ahead and do its insert uh but can't find a free slot has to go down here again wants to get this thing in right mode but it can't because this guy's here waits till that guy release it then it gets the right latch and then go ahead and keep scanning and and do the
33:24 insert all right slot latches are basically the same thing but again more fine grain so I come here now and I don't Qui the latch on the page I C latch on the value or of the slot I trying to find the thing I'm looking for this guy jumps down here ahead of me gets the right latch uh so now when this guy scans down and tries to do do the relatch on the next on the next slot it has to block and weight it actually could re could could release the latch up above I didn't show that um
33:51 yeah there it is so then then this guy keeps scanning going down this guy has going to keep blocking uh until this guy does his insert and then the the guy down below can get the find his read
34:05 right pretty straightforward and so in extendable hashing or linear probe hashing or sorry linear hashing you basically want to do page level latches uh and then you have a sort of separate latch for controlling the split pointer and that that so extra metad you would have in in front of the hash
34:25 table all right let's talk about B plus because that that's more complicated and more fun so again we want to allow multiple threads to to to access our data structure at the same time and we want to avoid two specific situations
34:38 and they're obviously going to be related to splits and merges because that's when the the data structure itself is reorganizing and therefore the pointers may end up being invalid if we come in at a bad time right so let's look at an example here so say we now we have T1 wants to delete 44 down here at the bottom so it's it's scanning down follows the the the the guide post to figure out when they want to go left and right we get down here we find 44 we go ahead and and and and and delete it right but now in this case this node I the leaf node I is is less than half full so we're going to have to rebalance we're going to have move a you know Ste steal from a a sibling so we're going to move 41 over let's say now before we can do uh uh do that move
35:24 over we get descheduled for whatever reason the SS SI schedule this thread or the whatever the the system scheduler whatever our thread is paused but then now T2 shows up and they want to find 41 so same thing they started the root they start scanning down the bottom tells them to go down this way and then now at this point they're at node D they look at they look at the the interner node keys and they say oh I want to I want to follow to find 41 between 38 and 44 so I want to go down to to node H but then I is
35:55 descheduled T1 wakes up it goes goese and moves 41 over and it's done that's fine but then now T2 wakes up it follows that pointer which was valid on the last uh on the last slide or so when it last looked at the node D it gets down to H and it gets a false negative right it completely missed the the the key that should have been there because someone moved it while it was
36:21 running so this is you know obviously dangling pointers is bad but this is another example we would have know correctness issues uh physical correctness issues with our data structure right because again there's no Global status about telling other threads what we're doing down inside our data structure we can only observe what the nodes that that we're connect to looking
36:43 at so we're going to way we're going to handle this is through a concur to a protocol called Latch crabing or latch coupling I think the textbook calls it latch coupling Wikipedia calls it latch coupling the basic idea here is that we want a way to allow uh we specify how we want our threads to acquire latches as they're going down in such a way that we can ensure that
37:05 something is going to get moved down below us and invalidate the the the information we've gathered on our way down into the data structure and the way this is going to work is that we'll get a latch for for the you know whatever parent we're looking at hold that figure out where we need to go next then get the latch for the child node the one below us where we need to go and then when we get to that child node if we know that it's considered safe meaning we know that it won't split or merge based on the operation that we're doing then we can go ahead and release release the latch on our
37:38 parent and it's sort of called Latch crabing because it's like it's like supposed to walk like a crab as you go down monkey bars might be another good example like I you know before I can jump to the next Monkey Bar I have to hold hold on to the one I'm currently holding swing over and then then I can let go of the one behind me
37:54 right so for find uh we're basically taking read latches all the way down just uh just until before and then because we're doing a read operation it's always safe for us to unlatch the parent it's for the inserts and deletes that's where we have to check whether once we latch our child we're jumping into if it's safe then we go ahead and release all the the latches on our ancestors you know on our parent above because we may in some cases have to hold the latch for the for the root
38:19 until we reach down far enough we know things are safe all right so let's say T1 wants to find 38 again start out the root I get the the root in in read latch mode jump down to B get that in read latch mode and this point here I'm on b i there's nothing there's no information about a that I need to get down you know further down because they told me where to go next so it's safe for me to go ahead and release the latch on a right because I'm obviously doing a read
38:46 operation get down to D same thing release the latch on B get down to H down here release latch on D and then I do my read and I'm done right that's pretty easy let's see now we delete 38 so again we get the right latch on a get down to B get the right latch on that now again we're doing a delete so at this point as we hold the right latch on B we don't know what's going to happen below us in our data structure we don't know whether
39:16 the the the leaf node is going to have to do a merge and therefore that could cause uh sort of reverberate a a chain reaction up the tree that would cause us have to do uh to to merge B with something else so because of this we can't release the latch on a because we don't know whether we don't update a because we did a
39:38 merge but then when we get down to D at this point here we recognize okay well I mean my simple example here I I have two two keys uh but at this point I know that no matter what if I delete below me in D I know that I'm not if I have to do a a merge down below I can easily delete I can accommodate a delet one key in D so therefore I'm never going to have to do any modifications to b and a above me
40:04 so at this point here we know that b is not going to merge so therefore we can release the latches on on uh b and a in what order should I release the latches on B and A or a and b in this
40:18 example what's that he said first B then a why just the opposite of theorder he said the opposite of the order you required them yesl so if you release a someone wants to acquire a then acquire B you have B they have a so she said uh you have to release B before a because you're worried about
40:46 Deadlocks so Deadlocks can't happen in this example here because everyone's going to be going starting from a right so you get you have to get the last one a before you get the last one b so there isn't a situation where someone would hold B and not a in this example
41:02 here so from a correctness standpoint both are correct like you can go top down from bottom up or top down or bottom up but for performance reasons you actually want to go top down because again the way to think about this is the latch on a implicitly has right latch on everything down
41:22 below right so no one even if someone was to come around on this side and do a read they can't do that because I hold the latch on a so I'm going to release the sort of the most encompassing latch first in that case would be the root and that could allow other threads to go down on this side here and not get blocked on me holding that latch so you always want to Le laters on the top going down because that that maximizes
41:46 or increases the amount of parallelism but both are still correct yes can you explain why we know that will not mer so he says the reason why we the question is why why do we know that that D will not merge C so at this point here I have two keys right so I get down here so no matter what happens below me right if I have to delete one of these guys down here and delete one of my guidepost keys I can absorb that that update and not have to go update my
42:16 parent right yes so this strategy consider Potential byat Threat question this we considered a a deadlock by by like the llvm's threat or Google threat sanitizer uh I don't think so why would it we can take that offline but it
42:41 shouldn't um always me that we should just acquire a we should just reverse I have to check whether we I double check take this line I double check what in Project two we we tweak the thread sanitizer give it perm like to try to avoid like false false positives but it shouldn't be an
43:08 issue again the O see the OS told you what you released them in the order that you acquired them so who told you this the thread standardizer or just OS classes but they're wrong right like it should be pretty obvious right you want to release a because that that unlocks implicitly all the other side of the tree yeah they're wrong I don't know who told you that it's
43:33 wrong okay all right so again we get down here then we get down to this guy on H and again I know I have to delete one of the key 41 I can I can this this node H can absorb that right I go ahead and release lash on D go ahead and do my delete and then I'm done or I'm sorry delete key 30
43:54 38 inserts going to work the same way so I want to insert 38 uh sorry insert 45 that's down here right so I I scan scan down take the right latch on on a take the right latch on B and again at this point here I know that if I had to do a split and another key is going to percolate up from the bottom of the tree into B I have space to accommodate it so I can go ahead and release the latch on a right because I'm never going have to modify it now I get down to D and it's the opposite I don't know what's below me in in my my leaf nodes so if a new key does come up I'm going to have to split D here so therefore I can't release the latch on B only when I get to the bottom now I see okay I'm not going to have to split this node so I it's okay for me to release uh b and d and I release B followed by D do my insert then I'm
44:49 done okay so let's see now if you insert key 25 so I same thing I get it right on a uh get the right on right latch on B get down here I can release the right latch on a just like before because I know that I'm never going to have to update it I get down to C same thing here I know I I would have room for it so therefore I I can release the latch on B
45:10 but now when I get down to F I see okay I am going to have to do a split right so in this case here I take the right latch I maintain the right latch on C I insert uh 25 but then I got to create a new node uh these things just get slit over izations these pointers haven't changed on on D and its Leaf nodes then I add the the new Leaf node for J and put the new guide post key into to C and uh and point to them
45:40 do I have to take the latch on on on Leaf no J that I just added to update this yeah yeah um or simp on F or if you're going if you go direction if you update G potentially yes uh we can ignore that um
46:02 but basically no because again I have right latch on this node here nobody can read this thing until I release my right latch so implicitly I also have J in in with a right latch so therefore it's safe for me just to do do my update
46:16 there and then once I have it once it's all done then I'll go ahead and release the latches reason we don't want Toge in the same level but question is is this the same reason why we don't want to merge NS from the same level what do you
46:32 mean uh your question is why don't we want to do what sorry Sor like why don't so going back here I can't I can't steal from these guys right these are full all right sorry I'm doing insert so there's no place for me to put anything I got I got to make a new node right so it goes there I'm missing a cing point but it would go there
46:55 too well talk about how to we'll talk about how to take the latch going this way in a few more slides but you would take the latch on this because again you're not updating its parent you're just updating what this The Sibling pointer is so I I get a right latch on this guy update the sibling pointer point back to my new one we talk about few more
47:15 slides okay so in all my examples what's the very first thing I did anytime I updated the data structure B plus 3 take a right latch on the root all right and this basically is going to limit the amount of parallelism we can achieve because it's basic it's putting our data structure in like a single threaded mode
47:35 right because again nobody else can take a even a read latch on the route if I'm holding it in right latch mode so a better approach is to basically do this optimistic lot coupling um it's I think the algorith is called the bar schik algorithm because written by this guy bar schlot be was the guy that that invented the B plus3 bone with the other guy from CMU uh back in the 70s I think this paper's from like 77 to 79 and and they're going to make this
48:04 observation that well most of the times the the the the root node is going to be safe from any splits or merges right assume you have these the really high fan out I'm sh my examples with two two keys per node think like hundreds of keys per node so the likelihood within any insert or delete operation that I'm going to have to you know up the root is very very low
48:29 so I'm going to assume that splits merges are rare and therefore I'm going to take relatches all the way down to the the data structure until I get to my leaf node then I take it in right mode because most of the times that's going to be good enough and if I'm wrong then I just repeat it again and take you know take the pessimistic right lock down right latches all the way
48:50 down so we're going to see this technique later on when transactions because there's a whole protocol called optimistic concurrency tool that was embedded here CMU where basically again I'm going to assume that conflicts are going to be rare and therefore I take the fast path of of you know taking lashes or locks in a more permissive mode and then just double check at the end was that was that assumption correct or not and and fix myself if need
49:14 be Intel used to have this actually in the hardware in x86 in the 2010s uh there's thing called TSX transactional memory and it did basically the same you could declare a block of C++ code or C code as being transac actional and it would run it then when when you when you finish that transactional piece of code it would then check to see whether any invariants were violated and then if if not you just run just fine uh you know just kep kept running if if you did violate then it would roll back and run it in a more uh in a sort of single threaded mode that was invented by a professor that used to be here at seu morce hurle uh he also invented L linearized ability which we'll cover later on um I think then Intel found a bug in it and they turned it off and I don't I think it's still still turned off as far as I know um but this is actually this basic idea was us using in Hardware which is pretty
50:03 cool all right so with this better latching ALG what we're going to do is if it's a read operation a find operation same as before just take read latches all the way down and then releasing the parent once we know once we land on our child node if it's an insert or delete we're going to set the latches uh in read mode as if we were doing a a read or find operation then when we get to right above the leaf node we take the the leaf node in right mode
50:28 uh and then we check to see whether we're going have to split and merge if we don't then we're fine we just do our update and we're done if we do have to do a split merge then we just a border operation come back and and try
50:38 again so I'm going back here deleting 38 down here to the bottom right I take uh the thread goes down takes read latch soon as it lands on the child on B it releases the latch on a gets down to D takes that in read mode that's fine releases the lat on b gets down to H and take release the Lash on D and at this point here we know that our guess turn out to be correct because we're deleting a key we're still going to be more than half full so therefore we're not going to do have to do a merge so therefore we can do our delete uh and not worry about rebalancing
51:13 anything right so this is a huge win for us because now we're not pessimistically blocking things from coming down to the tree if they're reading other parts of the branches as we're going down because we only took the right mode latch for just one node at the bottom
51:29 same thing if we're doing insert right take relatch here that's fine relatch here that's fine you release reash on a get down to C right get down to F now we recognize okay we are going to have to do a split so therefore we're just
51:43 restart our execution and take right latches on the way down and obviously you could be a bit clever and say okay well you know maybe I'll keep track of like what was the last you could say what was the last note where I I could have been unsafe and therefore take read latches up to that right you could do that that's maintaining additional metadata uh which could just be slow and then just blindly restarting starting starting over
52:10 again okay so most systems are going to implement some some variant of of this algorithm here again and we'll see this idea of like optimistically doing something uh you the fast path and then rolling back if you get it wrong we'll see this in other parts of the system as well
52:28 all right so the all the fs and examples we've shown down before so far in our B+ Tre have been going in again this top down manner right in this case there wasn't there couldn't be any Deadlocks because everyone's starting from the top and going down and only inquiring latches in that order but as we said last class we're going to have uh these sibling pointers that can now allow threads to at least along the leaf nose
52:52 go left and right in the case of the belink tree they have they have uh sibling pointers with the inner nodes but we we can ignore that for now um I can show how to handle that later on if you're curious but now we could have Deadlocks because now leave we have threads coming in different directions and need acquire latches that the other guy holds so really simple example here we have T1 wants to find all the keys greater than four so you start start at a get the get the relatch on this node
53:18 get down to C and now we're doing an ascending scan so now we need to go in in this order and we're not going to release the latch on C until we get the latch on B because we need to know that the the pointer we're pointing to is still correct like this is the right node we should be looking at someone doesn't swap it out uh from us while we're trying to get over so then then then we get over to to B then go ahead and release the latch latch on
53:41 C that's straight forward if we have another thread running the same time and wants to scan in different directions so T1 wants to get all the keys greater than one T2 wants to get all the keys less than four so they can both get the the root node in in in a read latch mode then they get the their two Leaf noes B and C in relatch modes accordingly and then now as they want to scan across
54:02 because these latches are compatible with each other it's they're allowed to acquire the the the opposite nodes in the right relatch mode and then they just swap over that's fine that's easy so now if we require have one of them do an update T1 wants to delete four and T2 wants to find out the key is greater than greater than than one so so let's say that this guy gets in there first he gets the read latch uh so he he gets down below and say again we're doing that optimistic lot coupling where he get the T1 got the a in read mode
54:37 gets down to C and once to do a delete recognizes that it can absorb the right or can absorb the delete without merging so it justes get C in in right latch mode but now B wants to again scan across and start looking at all the keys in in no sorry T1 once to scan across looking all the keys in in node C but it can't acquire the latch because the other thread is holding that leaf node in in right
55:03 mode right so the question is what what should it do there's three choices one is it could wait two is it could kill itself avoid the operation and you're shaking head no avoid its operation and come back and retry right hoping that the next time you come around the latch will be available and the alternative is you try to kill the other guy take their latch take their wallet right and and do whatever you want to
55:43 do which one's the right choice here wait raise your hand if you say wait raise your hand if you say kill yourself or sorry kill ourself and ra hand if say kill the other thread why how would you kill the other
56:00 thread why would you want to do it and how how would you do it the start yeah but how would you do it the latch you mean yeah latch but like what do that mean access to the latch I guess you yeah so like if his suggestion was or what if I just reset the latch and then so that that way I can take it okay that's fine but how do you tell the other thread that they don't have the latch
56:32 anymore right you could have like a a little Global flag that says okay you know kill yourself but you don't you don't know when they're going to check that s well that's that takes down everything yeah but he's close you could you could send a signal right but but how do you how do you handle that you need interrupt Handler you're going to put that sprinkle that in your code and that's going to suck right so this is not even really an option for us because we can't we can't do it if we and if we could do it like you know check some flag to see whether I should I kill myself now when do you do that do you check every single time you before you run a line of code go check to see whether you should kill yourself that would be impossibly slow
57:14 right now we said weit a lot of lot of you vote it for weight how long pretty fine he says pretty fine time pretty fine timeout what does that mean 100 milliseconds sorry I don't know the he said okay wait he says wait for let's take it give how about a millisecond okay okay and and if we get
57:47 just he said if you still can't get the latch then you just retry I kill yourself and rryy is why MC good enough yes delete deleting delete all so question is statement is well what if this case here three wasn't here and I delete four and now I have to do a a merge right um I me again this is a toy example but uh you would have had to acquire the I you could could have done that cuz this guy would have got the read latch on this give up the read latch of above this guy gets the right latch on that holds the right latch comes down here so yeah you could still do
58:38 that she again that's we're saying she said just wait for how long he said 100 milliseconds I got him down to a millisecond so he says wait until the other latch is released okay when will that happen does it matter does it does it matter uh well what if what if there again assuming I have a billion keys and this I'm on Leaf nose and it goes all the way over there right bu there more Lea notes over here does this guy does this thread know what this thread is
59:08 doing no so how long how long you know doesn't know how long it's going to take yes question stat is how is killing yourself better than waiting or this different from waiting because if I if I kill myself I'm going to come back and basically start waiting all over again so the so I mean I'll answer your question or statement like the correct answer is gonna be kill ourselves uh but you could do a little bit of waiting and the little bit of waiting could depend on what you've done so far meaning like if I had to do a bunch of Updates this I mean this guy's read only so it's not that big of a deal and index is stupidly small but if I did a bunch of updates I got to hold the right latches for all all the pages I or notes I modified so
1:00:05 other threads may be blocked waiting for me to release those latches and as soon as I can free them up they can maybe do a bunch of reads but if I did say a million updates then it was really expensive for me to do all those updates so killing myself might actually kind of suck too because I basically throw away a bunch of useful
1:00:24 work so you should sleep but like not a millisecond maybe like sleep like a Yi to the and then come back and kill yourself and it seems kind of counterintuitive because like like it seems wasteful right but again we don't know the other thread doesn't know anything about the other threads are doing and often times the most simple thing for this situation here because we're really worried about like you know microsecond times in our data structure accessing these nodes
1:00:50 killing yourself is actually going to be the best thing to do so your question is like I don't know how much work the other guy did so therefore and I don't know how much work it still needs to do so therefore I don't know how long I should be waiting for and depending on how much work I've done I could then be a little more sophisticated and say okay I've done a lot so therefore maybe just wait a little bit longer not milliseconds like again maybe like one one round of
1:01:16 scheduling but not not indefinitely because I maybe blocking other people blocking other threads trying to access to the data structure now when we talk about locks and transaction locks that's a whole different ball game because we know exactly what everyone is doing because SQL is declarative and we know what work you've done already and in some cases depending on how the transactions are submitted I know what work you're be doing in the future so therefore I can a better decision decide what what thread to kill to break a dead this deadlock or break break up this this
1:01:52 impasse but that's where again that's like the millisecond scale down to NCS or microseconds we don't have the time to to and don't want to maintain data structure to keep track of this information that's why again shooting yourself in the head on rolling back anything you've done is is going to be often times the best thing to
1:02:11 do so then you say okay what about the case where it's a high contention data structure where I keep restarting over and over again and I keep having to kill myself because I can't get the latches I need well when you when you when you roll back and and and ort and try try again there is a higher level mechanism like a schedule of the system would keep track of like okay you've gone to this data structure a million times you can't do what you need to do let me stop let me stop scheduling other threads from running so that your query can run and do what it needs to do because you've been waiting so long and now you have a higher priority but that mechanism is not inside of our data structure because think about it you would have to recreate that for every single B plus Tre you have in your system no right that'd be wasteful because now they're all maintaining their own this own you know history information all that should be in the higher level parts of the
1:03:00 system so again that means that in in in the in the the code of the system that actually uses these indexes it there's going to be a little while loop in there that says try to insert this key and there's some faires are not recoverable like if I try to insert a unique key and it comes back it already exists yeah I don't want to retry that that that won't make sense because that's it's a it's a high level Integrity violation so that goes back and Report the error but if I if I can't do the insert because I can't acquire the latches I need then I want to be able to retry and maybe I back off on on that on that Loop sleep a little bit longer before I retry
1:03:36 again so Simplicity is going to be our uh our benefit or to our benefit here right so this is basically what repeating would I just said so the latches aren't going to support any doct detection avoidance or mechanism so there's nothing to say okay you have this latch I have this latch let's try to figure out how to get along and how to share things right it's I only have in the scope of my thread running in my data structure what I know about myself
1:04:00 and therefore I should be able to go ahead and kill myself because again I can't send a signal to the other person right I can't set a flag to tell them to kill themselves I have to I can only deal with myself right and this is sometimes called the no weight mode I say almost no weight because again it's okay to put a little bit of sleep in but but micros seconds not 100 milliseconds is like basically going halfway to the country and back right across the country or going around the world is 300 milliseconds I think so like 100 milliseconds is is super super long don't do that and again there's this this this query engine thing thing we'll talk talk about next class this is the this is the part that's going to be responsible figuring out okay I I couldn't do my operation because on this data sh because I couldn't acire the latches I need go ahead and retry and this is all in this is all transparent
1:04:49 to the query that you're actually trying to run like when you get your query response you don't care that I try to acquire lash in this B plus tree 20 times and I couldn't do it right the query it'll run a little bit slower but you don't tell the application anything about this because they don't need to know they don't
1:05:03 care now in obvious scenarios where if everyone's trying to update the exact same key then there's no magic scheduling we can do to make that work well right if everybody's trying to update for whatever reason the same same page a billion times at a second that's going to become bottleneck no matter
1:05:21 what right and there's there's within the the data structure itself there isn't ways to handle that there's ways to handle that in uh in transactions higher level higher level parts of the system like was it last year people crashed the the the tayor sft ticket system crash or whatever because they were doing transactions the wrong way most likely there's there there's high level things that be able to handle that which we can talk about right so this clear so again this is a low this a lowle data concept where
1:05:51 I can't get the lates I need I go ahead and kill myself but I'm going to retry again and some someone else will be responsible for telling me to retry and I could have some additional history to make better decisions the next time I retry maybe sleep a little bit longer uh the next time I try again but beyond that there's no introspection into what other threads are doing because you just you simply can't know because by the time they get in and out
1:06:12 and you make any decisions based on that uh you know they''re already out of this out of the data structure and I can have hundreds of these B plus GES running at the same time in my in my
1:06:23 database okay yes whens how does it know has to UND yeah so question is if a Fred kills himself how does it know what to keep track how does it keep track of what it knows and need undo so basically you you you have in Fred local storage you keep track of like I update this node these is this is the change this is what I took out or put in there like so you can just reverse it and then when you roll back you undo that
1:06:54 yourself and you wanted to be Atomic so you not do doing partial update partial rollbacks okay all right so uh this is very very hard um and we you know we barely scratch the surface on how to make b b plus stre thread safe you know there's enough here for you to be able to do project two but like I said there's a whole bunch of other optimizations that that you could potentially do like delaying updates so that uh you don't have to do split emergence right away we saw similar things with like the B Epsilon tree with the the mod locks in every single node to make these updates go faster but the end of the day at some point you're going have to reorganize things and therefore you do need latching to protect yourself I would say also too A lot of the techniques we talked about in the B plus trees are going to be applicable to other data structures skip lists are are different beast but like the art in the the tries um some of the inverted index stuff again the latching stuff that we talked about here today are you can apply to those guys as
1:07:50 well okay all right so next class we're finally going to talk about how to do all the stuff we've done you take all the pieces we we've talked about so far this semester and now run run real queries uh so we'll quickly talk about again what the execution engine is look at a high level but then I think we'll start off talking about the Sorting algorithms uh and aggregations and then there we'll get into to joins and then full-fledged
1:08:13 query execution and that'll take us up to the the midterm okay all right project two so for project two you're going to be building a a a thread safe uh B uh B+ tree and then the pages in your B+ tree are going to be backed by pages in your buffal
1:08:34 manager right so if your buffo manager has bugs then you're GNA have a really hard time when you build the B+ tree because now you're not going to know whether you're seg faulting because your data structure is wrong or your buff manager is you know on the fritz so I'll talk about in the next slides but there's basically four steps you define what the pages should look like then the basic insert delete operations for them then you have you have to build a C++ iterator so that you can scan along the leaf nodes and then you have to again put it all together and make it thread safe so we'll Define what all the API you'll need for for the different parts of the data structure
1:09:05 and you're just going to fill fill in the methods and again this is much much harder than project one do not wait till the last minute to start immediately okay all right so the first task you're going to find what the page layout is and this year the page layout is going to be different than previous years we've done the b+3 so if you use chat TBT it's going to break um and so for Simplicity you're only going to need to support unique Keys you don't need need to support non-unique keys so you don't have to worry about overflow pages that that we talked about uh it's it's just going to be for for Unique Keys the basic operations to start with are Point queries uh uh do single key lookups so no not worry about necessarily range scans within the the data structure itself and then inserts with no splitting and removal with uh with sibling stealing and then supporting
1:09:53 merging so in the first the first uh the first phase here the first two tasks the three tasks this doesn't need to be thread safe so you can get that working the basic data structure working and not worry about other threads coming in at the same time and we have separate tests that that can check these things then the third task would be uh to again an index uh iterator so there's a CP plus the standard type of Library specifies what an iterator API should look like so you have to implement one of those so you can put it in a regular for Loop uh in your test code and I'm pretty sure this is true but'll double check you only need to support extending
1:10:28 scans uh because I think the iterator can only go plus plus go up and not go not go over reverse Direction and then you can finish off by talking about how to do or how to implement or extend your data structure to support uh a concurrent index with latch grabbing and coupling basically what we talked about here but then there's there's other uh optimizations that we can talk about if you're
1:10:48 curious so the the the semantics of what the data structure should do in different situations you should follow what we talk about in in the textbook which I again I think the slide follows as well but if there's any like discrepancy between the slide say one thing and the textbook says something different go by with what what's in the the textbook this shouldn't be an issue I think for this year because we cleaned up the tests uh than previous years but
1:11:11 again if you're unsure follow just follow the textbook and not let other online guides or Wikipedia the other advice I gave also to is make your page size and your buffle manager small like 512 bytes and this will cause it to do splits emerges more more more quickly than if you have larger larger uh uh larger page sizes
1:11:32 and then this happens every year make sure you always protect what the root page uh uh root page ID and data member looks like because that could again if you do a split on the merge so you do a split on the rout you can end up with a new root uh and that can cause
1:11:47 problems so just like in P1 we also have a leaderboard uh where if you're ranked to the first um um you you'll get 50% bonus points and then you have to pass all the test cases to qualify and you also have to submit it on time someone post on Pat today like it's not fair to the other people if you submit it the day after and then whole day you you do a bunch of optimizations so you can get that 50% so you have it has to be submitted on time
1:12:14 okay and then again don't plag youres or otherwise we report you to Warner home okay any questions about P2 so we'll announce when the recitation is the next week uh and then the the coach be going out either today or tomorrow yes so to confirm for the tree we can we're supposed to support like an arbitrary number of
1:12:31 keys all the examples on our slides are like this question is for uh for the B stre should you support an arbitrary number of uh key keys per no size I think it goes by so we only support fixed length keys so so no varchars uh and I think there's a Conant expression calculation where it gets the size of the it I think it automatically gets the size of the key you're trying to insert because it's templated and then use that to compute how many keys you actually have in
1:13:01 it yes how his question is how how his question is uh How likely are there unknown bugs that we're not testing for in P1 that could could you could hit later on the semester I mean we I like to think we've done a reasonable job of implementing enough tests to cover things um I think there
1:13:27 was pass okay that let's let's take that offline okay like I said thread sanitizer uh I said I think we might have turned it off for something like I know that it can give false positives for certain part certain things right
1:13:48 yes can we make submission to gra for P1 yes question can we still make submissions for P1 so we will make a new grac submission with the test from P1 or and then that you can just isn't graded just hit that up as much as you want
1:14:02 yes yes can P1 performance P2 this question is can P1 performance affect P2 performance what do you think how how much um again no no no actually going back so well so right so it's it's going to be in memory uh so we we save this somewhere
1:14:29 um so it's going to be in memory so it's not like you're spilling from dis uh so and it's not like it's the lru K pieces going to run so that like if you have a really slow lrq L lru implementation that's going to slow you down but like yeah if you hit the page table itself and that's inefficient that will slow you down
1:14:51 yes I forget whether we allow for swizzling I'll the double check that if you do swizzling then you almost never have to go to the buffer manager but I don't I don't know whether we say that or not okay any other
1:15:11 questions so again just going back here every year people wait to to to do this right I'm trust me I'm warning you every year people wait till till the last week to try to implement this and it it
1:15:28 the always fail I can't think of anybody who who's waited the last minute cuz we can see the submission history uh if I don't think anybody's everever like waited the last minute and is able to pull this off
1:15:40 right like the week before it's due you're like oh let me start my B+ tree right what's a latch right like like like if you do that you're going to have problems trust me okay refreshing when I get finish manifesting two cold a whole B like Smith and Weston one court and my thoughts hip hop related WR a rhyme in my pants in toxicated lyrics are quicker with a simple Mo licker since on my city slicker play waves are picker rhes I create rotate out of we too quick to duplicate feel a breeze at escate mik at Fahrenheit when I holding wheel tight
1:16:17 then I'm in flight then we ignite what starts to Bo you I heat up the party for you let my girl R me my mic down for all your Rec still turn with third de burn from one man I heat up your brain give it a Sunan so just cool at the temperature rise to cool it all with s ODS
1:16:38 [Music]