Buffer Pool Management in Database Systems | CMU 15-445

[00:00:01][Music] all right hey done grab your wrap you look down what's wrong city women woman problems what do you say men problems what are your problems they were saying your beats are too fresh and they can't handle it I'm not qualified to help I'm sorry okay all right so let's talk about databases then all right so a quick reminder homework one is due tonight and then project one is going out today I'll sit at the end of the class there's actually the website now the source code is online but I'll discuss what it is what you're required to do today and then just like before you're submitted some great scope and you know everything will be auto graded all right um I do want to spend some time talking whatever lab work loads is where after you've collected a bunch of data in the OLT side now you want to start analyzing it to extrapolate new information like people in the city of Pittsburgh are more likely to buy this kind of product I said you can use that information to then you know push information to the OTB side to get people to do things you want them to do and then the hybrid transaction analytical processing h-type workloads this is sort of a new buzzword that Gartner invented a few years ago basically describing these database systems that try to do both of them so a typical setup you'll see often is like this you'll have your front end ODB databases and then you have your giant back-end data warehouse so these are sometimes called data silos because you can do poncho updates into them sort of one database instance whether it's a single node or shivudu doesn't matter because it's a single logical database and then you apply your changes here but they don't really communicate with each other each one is sort of an island by itself so then you can do what's called extract transform and load or ETL and this is sort of a the term you use is described taking data out of these front ends cleaning it up processing it and then putting it to the back end data warehouse so the example I like to get for this is like Zynga the farmville people they buy a lot of gaming startups and then when they buy them they all run their own front end mediator basis but then when they want to put it in their back-end giant data warehouse so they can do analyze things to make you buy crap on farmville better right and so because say like in one database the first name of a customer will be F name another database we you know F first underscore name right so it's the same concept or same entity just with different different syntax and nomenclature so this ETL process cleans all that up you shove it to your data warehouse you do all your analytics here and then whatever new information you have you push it to the front all right and when you see things like people that bought this item also bought this item that's that they're doing that on the OLAP side and then they shove it to the front end to expose that through the OTP application so H tab basically says let's just also do some of the integral queries that we can normally only do on the OLAP side we can do it on the front end data silos you still want this giant thing your giant data warehouse because you want to be able to look at all your data silos put to put together but now instead of waiting for things to be propagated to the backend you can do some things on the front-end so that's basically what H type is so again this could be like your my sequel does your Postgres MongoDB whatever you want and then your back-end data warehouse would be Hadoop stuff spark greenplum Vertica there's there's large enterprise data warehouse systems redshift or snowflake your other cloud ones okay so this is clear okay so the main topic today we're talking about is now given that we've already spent two previous lectures on deciding how we're actually gonna represent the database in on disk now we want to talk about what we actually do to bring the database from those files on disk the pages on disk and bring them into memory so that we can operate on them right so remember that we the database system can't operate directly on disk we can't do reads and writes without having to bring into memory first that that's the von Neumann architecture now there are some new hardware coming out you can push execution logic down to the disks but we can ignore that for now so we're trying to figure out how do we want to bring back those pages in the disk and we want to do this and be able to support a database that exceeds the amount of memory that we have and we want to minimize the impact the slowdown or the problems of having queries tap that touch data on disk we want to make it appear as if everything's in memory so another way to think a problem is is also in terms of spatial versus temporal control so spatial control is you know where are we physically gonna write this data on disk right meaning like we want we know that these pages are can be used together often possibly one after another so when we write those pages out we want to write them sequentially so that when we go read them again though we though we you know write and physically close to each other and we don't have to do long seeks to find different spots on disk we also care about temporal control and this is where we make decisions about when do we read pages into memory what time we do this and then at some point we have to write it back out if it's been written if it's been modified and we don't make a decision of when we actually go ahead and do that and yeah this is the overarching goal of trying to minimize the number of stalls we have because our queries try to read data that we didn't have in memory and we had it right up you know that was out on disk we had to go fetch it so this is the overall architecture of the lower store manager but I showed in the beginning so we've sort of covered this part already so now we know how to have a database file or files on disk we know how to represent the page directory to find the data we need and then we have a bunch of pages a lot of pages log structure pages it doesn't matter we have a bunch of pages on disk and we know how to jump to them to find them so we now we're talking about this part up here at the buffer pool right when something else in the system like the execution engine the thing executing queries comes along says I want to read page two we got to know how to fetch the page directory into memory figure out what's in there and then go find the the page that we want and fetch that into memory and then the tricky thing is going to be if we don't have enough space now free memory to bring that page we need in we have to make decision what page to write out so that's you know this is what we're trying to solve today right and then the the other parts of the system don't need to know or really care about what's you know what's in memory with not in memory there's going to wait until you get the thing you and give you back a pointer to let you do whatever it is that you wanted to do okay so the things were talked about today is essentially just how to build what a buffer pool manager actually gonna do in some comedies the term buffer pool manager some systems will call this a buffer cache it's the same thing right it's memory manage by by the database system then we'll talk about how we actually can do different policies that decide what we know what pages we want to write out that that's what pages if you need to free up space additional optimizations we can do to minimize this impact and then we'll finish up talking about two other pieces of the data system that may need memory okay so again the buffer pool is essentially just a large memory region that we're gonna allocate inside our database system we're gonna call malloc I want to get some chunk chunk of memory and that's we're gonna put all our pages that we fetch from disk and so this is again this is all entirely managed by the memory by the database system other than having go to the operating system and ask for the memory right we have to use malloc there's we handed malloc or allocate memory on our own so we know s can provide us this but then we're gonna break up this memory region into fixed size or page size chunks called frames and this is you know frame seems kind of unusual why don't I just say page or block or whatever there's so many different terms in database systems to roughly describing the same thing so frames correspond to slots in the or see I use the term slot when use that frames correspond to regions or chunks in the buffer pool memory region that we can put pages in right and we slot is the thing we put things into pages within for tuples so for buffer pool it's it's frames for on the page it'll be slots so what happens is when the database system calls makes a request and say I want a page right we're gonna look to see whether it's already in our in our buffer pool if not then we go out in the disk make a copy of it fetch that you didn't put it into memory so this is a straight one-to-one copy we're not doing any D civilization all right we can ignore compression for now but whatever however it's represented on disk is exactly how it'll be represented in memory we're not doing any marshaling of the data we just take take it from the disk and put it directly in the memory all right we keep doing this roll all the other pages that that that we may need right so the in my earlier example when I sin I showed how the execution ender says hey I want a page to write it manually you know Buffalo manager magic figured out what page two is so in our if we're just organizing these things as frames pages can go in any order in the frames that they want right in this case here even though it's page one page one two three in my buffer pool its page one three that's not in the same order that it's out on disk so we need an extra indirection layer above this to figure out if I want a particular page what frame has the one I want because it's not going to match exactly the same order that it is on disk so this is what the page table is page table is just a hash table that's going to keep track of what pages we have in memory and if you ask for a particular page ID it'll tell you what frame that is located located in all right and so the database systems can have to maintain some additional metadata to keep track of what what's going on with the pages that it currently has in its buffer pool so the first thing we got to keep track of is called the dirty flag and this is just a flag single bit that tells us whether the page has been modified since it's been read from from disk did some query some transaction make a change to it the other thing that I keep track of also is called a pin count or a reference counter and this is just keeping track of the number of threads or queries that are currently running that want this page to remain in memory meaning we don't we don't want it written out to disk right it could be because I'm gonna update it so I do my fetch I go fetch the page I need bring into my buffer pool then I'm gonna go ahead and go ahead and modify I don't want that page to get evicted or swapped out back at the disk in between the time it's been brought in and before I can actually do my update to it there's also gonna prevent us from evicting pages that have not been safely written back to disk yet alright so again so like I get painted page and say I don't want this thing in to every ever be removed from the buffer pool for now and then say I'm reading a page here sorry I want to read a page that's not currently memory I want to put a latch on this this entry in the hash table so that I can go fetch the page and then update the page if I do not point to it right and I have to do this because multiple threats were running at the same time I can't assume that I'm the only person I'm looking at the page table so I want to rent somebody else from taking this this entry in my patient and while I'm fetching the page that I need they come and steal it from me and put something else in alright so again is theirs well see this as we go along later in the semester but there's a bunch of extra stuff we have to do to keep track of what pages have been modified so the dirty bit is just sort of one piece of it we also need keep track of who actually made the modification so because we want to write a log record to say here's the change that was made we're gonna make sure that log records written first before our page is written this is another example ymf is a bad idea because i can't guarantee the operating system is not gonna write my page out the disk before I want it to okay that's it doesn't doesn't prevent you from doing that at least on linux freebsd can let you do this but windows and linux don't want you prevent this alright so is this clear what we're trying to do here right basically managing our own memory but we're keeping track of how the transactions or queries are modifying the pages and we have to protect ourselves and the page table to prevent anybody else and you know addicting things or writing stuff before we're done with with what we wanted me to do any questions okay so I need to make a very important distinction now about the difference being locks and latches so this will come up later on you have to do this for the first project as well if you're coming from an operating system background in in there roll a lock is what we call a latch so in in in the let me try both of them in the context of databases and I'll see us to describe how they map into the OS world so a lock in dated in the database world is some higher-level logical primitive that's going to protect the contents of the database the logical contents like a tuple a table a database all right and the transaction is gonna hold this lock for its duration and while it's running which means could could be multiple queries this could be you know multiple milliseconds or multiple seconds even or even in minutes or hours if it's a really long running query so in that world again this is something that data systems can provide to us and expose to you as like the application programmer you even see what locks are being held for as you run queries latches are the low level protection primitives that we use for the critical sections of the internals of the database systems like perfecting protecting data structure perfecting protecting regions of memory and so for these these latches we're gonna hold for just the duration of the operation that we're making like if I go update my page table I take a latch on the entry on the location of that I'm gonna modify make the change and then I release the latch all right and we're not we don't need to worry about rolling back any changes in the same way we do for locks because it's it's an internal thing or updating the physical data structure of the database system I make the change and if I can't actually get the latch I want then I did a board and and don't worry about rolling back yes okay so he says rolling back changes this will come later on we talk about courtesy troll but basically say like I wanna take money out of my bank account and put it in your bank account so we take money out of my bank account but then the system crashes before I put the money in your account I want to roll back the change I made to my account because I don't to lose that money that's not to me like that right this will discuss a whole lecture on convergent roll it's awesome trust me but for now the main thing we're focused on this thing here right so again in the operating system world this would allow should be something like a mutex we're actually going to use mutexes in in our database system to protect the critical sections of things so I will try to be very careful and always say latch when I mean latch but occasionally I slip up and we'll use lock but I said it's an internal thing we mean latch it's also very confusing too because the mutex implementation you would use to protect you for his latch is called a spin lock alright but it's really you know this thing and not this thing ok all right so the other think we want to make is the difference between the page directory and the page table so remember the page directory is what we're going to use to figure out where to find pages in our files so we want page 1 2 3 it'll tell us what file at what all said or what's what set of files have-have what we're looking for so all the changes we're gonna make to the page directory have to be durable they have to be written about the disk because if we crash come back we want to know where to find the pages that we have the page table is an internal in memory map that just mats page IDs to where the the frames of a are in the buffer pool so this thing can be Italian ephemeral and we don't need to backup by disc because if we crash and come back our buffer pool is blown away anyway so who cares so this page directory has to be durable the the page table does not does not have to be and that means we just used whatever your favorite hash map or hash table implementation you want right for project 1 you're just used s to be a city map that's fine because again we don't have to worry about this thing being durable we have to make sure it's thread safe certainly but not not durable all right so now when we start talking about how we want to allocate memory in our database for the buffer pool we will we throw to think about this in two different ways so the first is that we can choose what I call a sort of global policies where we're trying to make decisions that benefit the entire workload that we're trying to turn trying to execute we look at all the queries all the transactions that are going on in the system we try to say at this point in time what's the right thing I should do for choosing what should be in memory versus not memory an alternative is to use a local policy we're on for each single query or each single transaction we're running we try to say what the best thing to do to make my one query one transaction go faster even though for the for the the global system that actually might be a bad a bad choice so the there's no one way that's better than another obviously there's optimization you can do if you have a global view versus a local view but then for each integer query you might be be more tailored to what they want to do to make that run fast so as we've seen a much of these examples as we go along for optimizations the most systems will probably try to do accommodation of the two of them what you'll be implementing for the first project is considered a global policy because there's just looking at you know what's the least recently used page and removing that even though that make me bad for one particular query all right so that basically all you really need to know about how to build a buffer pool right it's just you have a page table that map's page IDs to frames and then you look in the all set and you're in the allocated memory and that tells you here's the page that you were looking for it seems pretty simple right so now we want to talk about how to actually make this thing be super awesome or super tailored for the application that we're trying to run or the work over trying to run inside of our database system and this is gonna allow us to do certain things that the operating system can't do because it doesn't know anything about what kind of queries you're running it doesn't know what data they're touching what are they're gonna touch next all right so now we can talk about what we can do to make this thing do better than what sort of a naive scheme would do so talk about how to handle multiple buffer pools prefetching the scan sharing and then the last one be buffer pool bypass okay so in my example that I showed I referred to the buffer pool as a single entity and the datum has one buffer pool in actuality you can have multiple buffer pools so you have multiple regions of memory you've allocated they each have their own page table they each have their own been mapping to from page IDs to frame IDs or frames all right and the reason why you want to do this is now you can have for each buffer pool you can actually have local policy for that buffer pool that's tailored for whatever is the data that you're putting into it you know so for example I could have a a single buffer pool for each table because maybe some tables I'm doing a bunch of scruncho scans and some tables I'm doing point queries or I'm jumping to single pages at a time and I can have different cashman policies or different placement policies to decide based on the two workload types but I can't do that easily if it's a giant just a giant a buffer pool well let's say I have it I can have a buffer pool for an index and buffer pool for tables and then they have different access patterns and then I can have different policies for each of those the other big advantage you also get is that it's gonna end up reducing latch contention for the different threads that are trying to access it right so when I do that look up in the page table I have to take a latch on the entry that I'm looking at as I go find the frame that has the data that I want and I'll make sure that nobody else swaps that out what but you know from the time I do the lookup from the time I go get the page that I want and so that means that I could have a bunch of threads call contending on the same latch that could they're all accessing the same page table so no matter how many cores I have on my brand-new machine I'm not getting good scalability because everything's contended on these these critical sections but now if I just have multiple page tables each thread you know they could be accessing different pages of different page tables at the same time and therefore they're not contending on those latches and now I get better scalability now still could be still bottlenecks on the disk feed which is always a big problem at least internally now I'm not worried about them you know trying to all acquire the same latch so this is something you see mostly in the enterprise or expensive database systems so Oracle db2 Sybase and for max Seigle server all support this ability to have multiple purple's db2 you do all sorts of crazy things you can create multiple multiple buffer pools you can sign them different tables you can have different cashman policies for all for all them if you set them to be their different page sizes my Siegel even though it's open source actually has this as well it's it's not that as sophisticated you just say how many buffer pool instances you want and then they just do round-robin hashing to decide what what you know if you'll forgive and pagenty where's the data that I'm looking for what buffer pool has it so there's two ways to use these things right they've to map the thing that you're looking for to a buffer pool that has the page that that you want I said typically what happens is if you have multiple buffer pools you can't have a page in one you know in in buffer pool one this time and then when you fetch about the disco later on it comes out another one it always wants to be in the same location so you know how you know how to find it quickly so the first approach is that you can actually extend the record ID to now include additional metadata about what database object this buffer pool is managing so if you recall when we looked at the record IDs of Oracle and sequel server they had extra columns extra information that Postgres didn't have back postcode had the page and the slot number will have like the the object number page number and and a slot number so we could use that that additional object number they didn't have another map that says all right for object you know XYZ you can it's a Miss it's in this buffer pool or that buffer pool and so now the requests from up at level of the system you're saying give me you know give me a record one two three and I know how to split that up and find out what object it corresponds to and what buffer pool will maintain that data for the hashing approach again I think that's what my secret does it's pretty simple you just take the record ID you hash it and mod n by the number of buffer pools you have and that just tells you where to go get the dinner do you want and this you do is really quickly really fast it's not an expensive operation actually for either there's it's not an expensive operation all right the next optimization we can do is to do prefetching so the idea here is that again we want to minimize the stalls and the data system due to having to go to disk or read data so if we start doing like a scan and our buffer pool is emptying this query wants to read page zero page there is not in memory not in our buffer pool so we have to stall that thread until we go out the disk fetch it and then put it into our buffer pool then once it's in our proper pool then we hand back the pointer to the upper-level system say the page you wanted is now here in our in our memory go do whatever it is that you want to do so the way to think about this is like it's a you can think of this arrow is like a cursor so internally a database system is gonna keep track of this thing kind of cursor like as you iterate over every single page for that your query needs you just know where you left off the last time so when you go back and said give me the next page it doesn't start at the beginning it jumps where you were you left off so in this case here I get paid zero I'm done right now I start reading page one same thing I have to stall because it's not in memory the disk goes and gets it we've put in our tour buffer pool and then once I have that now I can now I can proceed operating their own so let's say this query here wants to scan the entire table alright these are for our table here here's all the pages so at this point the data used to probably recognize oh I know you're gonna end up scanning the entire table so rather than just wait with me waiting for you to ask each page one after another let me go ahead and jump ahead and say oh I think you're also going to need page two and three so let me go prefetch that for you put into the buffer pool so by the time you finished processing page one and now you go ask me for page 2 or page 3 it's already there now you don't have a stall and again based on how I laid out these pages on disk and that might have been a sequential read which is super fast so by preventing things ahead of time I you know I'm minimizing the amount of random i/o that I'm doing right let's keep going this down and and prefetch everything's that again that minimizes the impact of these distal x' so this example is pretty simple right the the operating system at you could figure this out too now and and nmap will actually do this for you right so an M map you can pat the flag say I'm gonna do a special read on these pages on disk and it'll go ahead and prefetch a bunch of them ahead of time and so again that will minimize the stalls having because because you had to read something from disk so M map can figure this out without even knowing anything out what the queries trying to do and the data system knows what the query wants to do and can go prefetch ahead of time but now there's to be some queries where the operating system is not going to be able to know what to do but we do in the nativist system because we know what the query wants so you so an example of this would be like an index game so let's say I want to do a scan on this table and I want to get all the values I want to find all the tuples with the value is between 100 and 250 so now let's say that I have an index on that value and I've explained what an index is just think of this as like a glossary in your textbook it allows you to jump to a particular page that has the data that you want all right so right so instead of spewing sequential scan I can just jump through the index and find exactly what I'm looking for so let's say that our in our index pages right we know ahead of time what the ranges are so when my query starts to do that scan I always got to read the first page for the index because that's the route alright so you know I have to jump to there but now I'm gonna do a lookup and say well I'm looking for my query was between 100 and 250 so I know that all the pages I need or the values I want where it's greater than equal to a hundred or gonna start on this side of the tree so now I'm gonna jump down into a page one and read that right that's still sequential at this point so again the operative system could Poli figure this out but now I'm gonna branch and go down here and I'm gonna scan across the leaf nodes but this is index page three index page five they're not contiguous with each other on on disk and so the operating system may try to end up prefetching page two and page three but I don't need page two that's wasted and I need page five and it didn't prefetch that so because we know what the queries gonna do we can go ahead and prefetch exactly the pages that we want and bring them into our buffer pool because we can we understand what the what's actually the context what are the context of the query and what do these pages actually representing because the operating system does these pages it doesn't know what's in them but we know because we wrote this code we know that these are index pages and they're connect together in some way so we know how to do this traversal so this doesn't come for free right there's some extra metadata we had to keep track of in these pages to say like here's the sibling here's my starting point or my end point here's his starting point so I know whether I'm gonna scan across over here and actually I can't know whether I need five before I look at three so you know this I'm not saying this is like super easy to do but you can kind of see again how we may not be jumping exactly through the pages sequentially in a way that the operative systems not be able to find again this this is this to me this is the classic example of what we can do in our database system that opera sim cannot do because it doesn't doesn't know about what's in the data it just sees a bunch of region writes all right the next optimization we can do is called scan sharing so the idea here is that we can have queries piggyback off each other and reuse the data that there that one query is reading from disk and use that for its query so this is different than result caching result caching is say I run exactly the same query and I compute some answer and I cache that results of that same query shows up again I can just rather rerunning the query I just give you the answer I had before this is at a lower level at the puffle manager in the storage layer where we're now and just have this cursor accessing pages we can then reuse the pages we're getting out from one thread for another thread so way it's gonna work is that when allow multiple queries to attach to a single cursor that's scanning through our pages and putting them to the buffer pool it's almost like a pub sub thing where we say I want to know whether you get a new page and then you can notify whatever thread that may be waiting for it even though they're not the one that actually did the read so depending on the implementation the queries do not need to be exactly the same typically in result caching they do in our and our world here they don't have to be just I need to know whether I'm reading the same pages and then in some cases to also if they're computing the similar result we could share those immediate results and across different threads so most like a it's called a materialized view we'll cover this later in the semester but for our purposes here with this game we're just looking at page accesses so again the way it works is that if a query starts a stand and then it recognizes that there's another query also doing the same scan it just attaches itself to the first guy's cursor and then as it gets pages we get notified that that page came in and we can we can access it as well so the important thing to know is that we have to keep track of where the second query came along sort of got on the train for the cursor so that we know if the cursor ends for the first query there may be other data we have to go back and read I said we can if we want to look at everything we start halfway we want to know where we started so we can come back and see the rest so as far as I know this technique is fully supported only in db2 and sequel server it's super hard to get correct it seems like kind of trivial but it can get pretty gnarly based on what the the queries doing Oracle supports has a basic scare chaning they call cursor sharing and then but it only works if you have two exact queries running exact same time whereas these guys can extrapolate based on the query that you know I need I know you're reading this table I need to read the same thing and jump on it this thing has to say I have two queries I'm doing the exact same thing so let's look an example so say we have our first query here it's computing the sum on a so the query the queries cursors are going to start and it's just gonna start scanning through the table looking at each page all right so now let's say at this point here it wants to read page three we don't have any a free frame and our buffer pool so we run our replacement policy algorithm to decide which of these pages we want to remove in this case here we'll do something simple and say well page zero was the last page that the the page that was the oldest since I've accessed it so let me go ahead and replace that with page three and then now I continue scanning but now let's say after this happens after we swap out page zero at page 3 a second query shows up that also wants to do a central scan on this table so without scan sharing it'll just start at the beginning like the first guy and just skin all the way down but this is actually the worst thing for us because the first thing is going to read is page zero but we just threw that out on disk so now we can end up thrashing because this guy can't proceed until page zeros is in so this is gonna you know it has to stolen to go fetch it back in but I I just had it in memory but I got rid of it so that's bad so with scan sharing this guy just hops along for the ride and read the same thing that q1 reads and you know produces you compute whatever enemy resulting needs for that part of the part of the data is looking at so now at this point q1 is done so it's cursor goes away and then q2 starts over at the beginning and those nodes that I started when you were reading page three so this is how long I need to scan down until I get my final result yes this question is each query is computing also intermediate results as as it reads this datum so they also now need a memory region to to put this data in that's separate from this buffer pool yes so we'll see this an exam on Postgres in a second but the typically that memory will also be backed by a buffer pool right and because like if I end up computing something you know say I'm computing a join and the output of that joint operator doesn't fit in memory I need B it started victim those pages out to disk so so any ephemeral memory like that would still be backed by a buffer pool but whether it's in the global buffer pool whether it's a private one for the query it depends on the implementation his question same it is I don't need I don't need to bring pages from disk in for that query in Amira's all buffer pool yeah yeah so as I'm writing data like so this guy and this is trivial table because the average is it's a scaler right let's say this is you know some really complex computation as I'm generating as I'm scanning this data I'm updating my enemy result I may overflow memory and those gets swapped out the disk so I'm writing to memory and then they would just get to get written out the disk as needed but it's not like I would read for my query yeah it doesn't make sense because anything you need free from like the low-level data is pages you're gonna put in the buffer pool that everyone can see all right so again this is another good point this is a shared data structure right so it did like q1 is was reading pages and putting to the buffer pool any other thread that need these pages is allowed to go go ahead and read it alright the pin latch the pin that just tells you that hey don't swap this out the disk the doesn't doesn't prevent anybody else aren't reading at the same time you are there's higher level things like the locks that keep track of what pages you're allowed to read and write from or what would you know with database objects this is the painted spacing says hey I'm operating on this don't swap it out so that didn't your question okay so there's another good example what's awesome about the relational model because the relational model is unordered meaning like it doesn't like I can actually have Q to start anywhere for some queries and the answer I'm gonna produce may be different from based on when I execute it but it still considered correct so if I changed this query to put compute the average and I limit it to a hundred meaning I only want me to be the average of 100 tuples it doesn't specify that I can only I have to look at the first one hundred tuples so I could start here at page three with my with my scan sharing on this cursor and see the first hundred tuples in these first three pages and then that's that's enough for me to compute the result if I started now at the beginning I may actually get a different result but according to the relational model that's still fine cuz the database is unordered yes yes so he perfect so he says would it also still be valid if we rather than having the cursor say all right well let's go look my dispatch is start fetching them what do I go check out the buffer pool and figure out what's actually a memory and compute the aggregation or this particular query which with what's a memory absolutely yes and the smartest systems can do that okay it doesn't matter writes in memory as long as I see a hundred tuples then that this query is still correct now this is I don't know like you wouldn't want to write this but it's yeah it's still valid all right the last optimization we'll talk about is the buffer pool bypass so this sort of related his question before about like the intermediate result memory but let's say that I have some queries where we're doing structural scans and the I don't want to pay the penalty of having to go look up in the page table and look at my buffer pool to go figure out whether the page I'm looking for is in memory furthermore I also don't want to pollute the cache and it may be reading some data that I'm not going to need in the near future so the the buffer pool bypass cash bypass depending what system it is the idea is that you allocate a small amount of memory to the to your your query a thread running it and then as it reads pages from disk right if it's not in the buffer pool it has to go to DISA to get it rather than putting it in the buffer pool it just puts it in its local memory and then when the queries done all that just gets dropped and thrown away all right and you do this again because you want to avoid the overhead of going to the patient we'll just yeah it's a hash table it has latches it's not it's not it's not super expensive but it's not free it's not cheap so in for max these are called light scans but pretty much every single again major database system supports something like this I don't know I don't know whether my sequel eight does I don't think five point seven does and then again if you recognize that you know that you only really want to do this if you know the intimate result or their thing you're scanning is not not huge if you're doing a sort that's gonna be you know terabytes of memory then you want to be back by the buffer pool because that thing can get paid up to disk as needed all right the last thing to sort of understand also too is what's actually going on below the database system what's happening as we read pages from the obvious and what is the operation actually doing so again all our disk operations are gonna be going through the OS API at the lowest level the F of them every to fright you know we're not going to access the roll all discs themselves so because we're now going through the operating system by default the operating system is gonna maintain its own separate cache for the file system all right this is called the OS page cache so that means again as I read a page from from disk the OS is gonna keep a cap copy of it in his file system cache or OS page cache and then I'll have another copy of it in my buffer pool so most database systems do not want to do want you to do this no no the operating system to do this so when you open a file you pass in the POSIX flag Oh direct or direct IO where you have the OS not do any of that caching itself and you manage what's in memory on your own so pretty much every single day tourism when you go to read the manual they would tell you that make sure you can actually turn this on the only database system that does is its Postgres as far as you know the only major data send that relies on the others page cache is Postgres and so the reason they said they do this because they claim that from engineering standpoint it's one less additional catchment thing they have to manage they still has their own buffer pool but it's not gonna be as big it's not gonna use all the memory on the system like my sequel or Oracle would use but let the OSD with some additional management themselves so from an engineering perspective it's less overhead on their part from actually maintaining that that piece of the system and it's a minor performance penalty to rely on this which we'll see in a second okay so I like using Postgres for demos because it's almost like a textbook imitation of a database system and you actually exposes a lot of the important concepts that we're talking about pretty pretty easily okay all right so this is running again a machine back in the lab let me turn on the lights and I type in those laptop cuz it's a pain to type on the on the surface I hate the keyboard alright so this is running this is just running H top it's a better version of top and the thing I want to I want to focus on is is the memory you should stuff up here so the green bars are telling you what's the resident set size of the processes running on this machine right it's the memory they've now looked the the orange bar here that's the filesystem page cache that's the operative systems page cache so again as whatever processes are running on this machine as they go read if they're not using direct i/o if they go read a page from a file the OS is also going to cache it as well so we can blow this all away so this is running on Linux so in Linux we can do a [Music] that's not Oh for sorry so we can run this command that we basically passive we we stink the OS the FASTA some cache and we passed this flag three into the proc file system to allow us to force the opposite to flush our page cache so now if we go back and look at H top now we see that the total amount of memory beat buying used but the machine went down to three gigs right so had 32 gigs before but now it's down to three gigs so we blew away the file system cache entirely ok so now let's go let's go bring up Postgres the first thing i want to do though is restart it and so by restarting it we're going to blow away it's it's its buffer pool all right so now bring this up and then reconnect we're ternal and timing and then we'll turn off the parallel threads so we're going to use that same table I showed them last class ten million entries of a bunch of decimals so we can run this query and now what I'm gonna do is I'm gonna use explain again but I'm gonna pass and analyze two flags analyze and buffers so analyze again is gonna actually run the query and also show you the query plan what happened this buffers flag is going to tell you how much data it read from disk what percentage of the pages it was reading rating the buffer pool verses on on disk and so because we blew away the file system cache we blew away the buffer pool because we restarted the database system it should the hit should be zero right and you see that it said that for the buffer pool it had to read four hundred four four four four to forty eight pages it had to read the table from disk and it took thirteen hundred milliseconds one point three seconds so if I run the same query again now you see it says that the hit was 32 so it was able to read 32 pages that were already in the puffer pool and then the rest it had been reaping disk alright the reason why I wasn't all the pages is because Postgres maintains a buffer pool sort of a small buffer pool ring per query that's 32 pages so for this one it was allowed to read 30 pages from the last time it ran I run this again it should go to thank the 64 yes so it keeps growing in size as I'm executing queries over never again because it recognizes that oh the data that I need is is it's not my buffer pool let me increase the size of its cache alright so now what we can do is we can force the database system to put everything in into into memory so they have this extension of Postgres comes by default when you when you install it called PG warm and all this does is that it's a function that we invoke on the data system to say hey go take all the pages for this this table and bring it to a buffer pool right and tells you that I ran I did that and I read four hundred forty four thousand two forty eight pages remember when I ran the query the first time the it said had to read four thousand four hundred twenty eight pages from disk because it's getting exactly you know that's the the number pages of this table he says there's six more pages already there right so this is like forcing just read everything and I think those 64 pages might have been yeah I think it doesn't look to see what's in memory it just says I'm gonna get everything cuz i if I do it again it should give me the same number yeah just reads everything alright so now if I go and run that query again I'm doing a little bit better by hit a sixteen sixteen thousand sixteen thousand pages I needed were in memory so I hit hit had it hit in the buffer pool but I started read a bunch some disk and we take a guess why yes he's wide still loading everything into the buffer pool depends on the size of the buffer pool right so we can do this in Postgres so Postgres has a flag called shared buffers and it tells me that it's currently set to 128 megabytes right but the size was about 4 for 4 to 8 so select you can use gimme you i'll updated you can use them as a calculator so for 4 to 8 times 8 divided by 1024 about giving megabytes so the size of my table I'm reading is 345 megabytes so again the shared buffer is 128 but my size my table is 345 so I can go to the post rest configuration in theory for this is post Chris 11 and then go find that particular parameter and lo behold it's 128 megabytes so let me set it to let's be generous let's say 360 megabytes right so now we will restart Postgres we will blow a our file system cache from the operating system because again as we read that page in actually we go back to H stop it got I mean it's hard to see we've got a little bit bigger hmm like if you see there's one bar there because that's that that's that's our table we were reading in so let me go blow away the file system cache and now go back to post grass I need to reconnect turn on timing set that to this to turn up parallel threads check to see that shared buffers is now oh I'm an idiot right sorry server 10 Klein 11 too many co-stars installation sorry so go back here is this put about the 1:28 I said about 360 now we start Postgres go back here reconnect 360 okay good turn on timing turn on parallel threads pre-warm we got it four four two eight four two four eight pages and now I've run that query again and now my head is four four to forty so I gave it a system the right amount of memory I prefetch and everything and now everything is hitting the buffer pool I had I didn't that such a disk at all for this particular query I do every lookup every page and I need to access I'm going looking in that but in that page table and finding the pate the page reference in a frame but everything is in memory here so how can we prove that the that the database system Postgres is using relying on the file system cache so let's turn off just explain everything here and let's see how long it actually takes right it's actually so the first time was twelve fifty and they got a little faster then it's 7:33 alright so it takes me roughly seven hundred milliseconds so what we can do is go restart Postgres [Music] and then that blows away the buffer pool and now if I come back and reconnect the Postgres which I think I need to yep so now I'm now I'm reconnected I slept a good turn on timing turn off parallel threads I run that same query before when everything was out on disk I think it took one point three seconds so this one and then with everything's in the buffer pool it took seven hundred milliseconds so this one should be roughly little bits where timing was all sorry well that ruined the demo so go back I go back this restart this go back to this reconnect timing is on yeah that's one yeah I got it parallel threads are off again so I'm gonna run this query I blew I restarted the database system that blows with the buffer pool but the operating system still has its file system cache so now that I run this query we're gonna have a bunch of buffer pool misses because nothing is in memory but it's still not going to take the full time right took 800 milliseconds instead instead of 1.3 seconds because the data that it needed was in the file system cache if I run this again I should get now 700 milliseconds no there goes let's go figure what happened still reading date from disk why is that well it's still running fast even though that time I think it's because that time slower because I think it's running explain analyze it'll slowly get faster as it creases the cache size for that for that query I think I think it's a query cache thing rather than the global thing but again the main takeaway we showed is that we had to give it a decent enough memory and put everything into our buffer pool and then we were able to get the full speed performance are starting questions yes pre run twice what I mean oh that's the file system cache that's about the US cash question yes yes yes so the very first time I did this the the buffer pool size was 120 megabytes the table size is 345 megabytes it didn't that's why I had I had to add lookups in read from disk in the very beginning huh there's not we spending all our time boy this is this is walkthrough right so let's do this go back we're going to blow away the file system cache restart Postgres you know now we go look and and in our I mean that that bar is not a trivial potentially for propose grass like there's other things running on the system but I blew away the false ISM cash I've restarted Postgres now there's nothing in memory so I go back to the Postgres you need to reconnect turn off pale threads and so if I run the query now the first time great nothing's in memory I had to read 44,000 pages okay so that's expected pre-warm tells the database system to go read everything that's on disk for that table brain to my buffer pool all 44 thousand pages yes I can do this again right it read 44,000 pages now I run the same query and now my hit is exactly 44,000 hit means like it was hit I the thing I was looking for was found in the buffer pool so I forced the day's doesn't bring everything back in the memory and the first example I only had a hundred twenty megabytes so I couldn't put everything on yes yes great so our question is so I said in the beginning that the Postgres is the only system that that does you the only major system that relies on the OS page cache why doesn't everybody else do this well because now I'm gonna have two copies or every single page potentially so I could have a page in the OS page cache then I'm gonna have a copy of that page in my my buffer pool because now if I modify that page now it's not exact copy anymore so the OS has the old one and I have the new one so it's it's redundant data so you're more efficient in terms of memory usage if you manage everything yourself furthermore to you know think of like in a different database system I mean most it isn't support Linux now right but like the major ones they got to support Windows BSD all these different operating systems where the OS page cache may have different performance implications or different policies and so to guarantee consistent performance or consistent behavior across different os's you just manage everything yourself it's a good question yes there's number pages but again so like I post as 8 kilobyte pages I take this number multiply 8 divided by 1024 that tells me them are megabytes of mic my thing I set my buffer pool size to that size and that can guarantee everything fits yes of course question is how does buffer pool interact with the OS page cache again be it's like these question is like are there different options how to use it no like so it's transparent to the program like I call read every go read a page from from the from disk if the OS has a page cache that serves me that page otherwise it goes out and disco gets it that's all transparent to me if I pass that flag direct i/o that tells the option system do not catch anything and it's always gonna go to disk and get it it's quite yes save it as the OS page cache is in between the sort of the disk and the data in the database absolutely yes it's gonna matter also to a lot when we start doing writes if you call like you write a C program you call F write does is the operations I'm actually gonna write that right away no puts it in the page cache and at some later point the disk schedule says all right I'm gonna go write this out it's only mine I call s Inc when is when actually it's written but if I want a complete control of how I'm ready everything out the disk I want to use direct i/o and most database systems do that yes yes all the t-80 and v60 and be into the book what would happen the first 1:28 and we would have been overwritten how many you did sir clearly you got hit but many times the query you have started from the starting so you should have got it because the memory presence was the later 128m let's I'm gonna get through the thing for the project but let's let me talk about it wherefore it's okay alright so the thing when to talk about now quickly is the buffer placement policy so again we talked about how right we how to find a page we want based on the page ID and the page table but now you know am all my examples we had enough memory mostly and so now we want to talk about what happens if I need to bring a page in and I don't have space for it what do I do so the things were to care about and a replacement policy are obviously correctness right we don't want to write out data or a big data that that someone pinned before they're actually done with it we're gonna care about accuracy because we're gonna make sure that we we Vic pages that are very unlikely be used in the future so we minimize the number of disk seeks we have we want overplay some policy to be fast because we don't you know the as we're doing a lookup in the page table or holding latches and we don't want have to run some MD complete algorithm to figure out what page to evict right because that may take longer than actually reading the page anyway and of course obviously we don't want to have a lot of metadata overhead of keeping track and all this additional data we don't want to have the metadata for a page keep track of how likely it's going to be used to be larger than the page itself so these replacement policies again as another good example what distinguishes between the high end very expensive enterprise databases and the open-source guys because the high end ones have very sophisticated replacement policies they track statistics of how pages were being used they try to extrapolate from what the queries are actually doing and to try to make the best decision whereas in the the open source guys and the newer systems not saying they're bad but they don't have you know millions of dollars in decades spent trying to make this thing run fast as possible and so the you know they'll do something more simple which is what we're gonna talk about here this is like one of the oldest problems in CS like everyone their uncle has a paper in the over the years on how to do caching and things like that I have one right like this is this is like one of the oldest problems in computer science there's a ton a long history of this all right so the easiest technique the use and pretty much everyone does the first time is LRU or at least recently used so all we do here just keep track of a timestamp of when a the last time a page was accessed and then we have to go figure out what page you will go evict we just look to see which page has that old it's timestamp and that's the one we go ahead and remove so way to speed this up instead just keeping a track of a you know a timestamp her page because then we have to do a special scan across all our pages in the buffer pool to figure out which one has the lowest timestamp we can just maintain a separate data structure like a queue that there's that's sorted by the their timestamps so anytime somebody reads and writes a page we just pull it out of the queue and put it back to the end because it's a first-in first-out what you guys will have to implement in the project is an approximation of LRU called clock actually quick show of hands who who here has heard a clock before nobody awesome okay cool here so I mean LRU Emily should know right okay good so clock so LRU is an exact least recently used clock is an approximation of this where you don't have to track the timestamp exactly every for every single page so instead we're all the only information we need to keep track of is a single reference bit per page that tells you whether that page was access since the last time you checked it so you're gonna organize your pages in a circular buffer like a clock and then you have a clock hand that goes around and does sweeps and check to see whether that reference bit is set to 1 or 0 and if it's set to 0 that you know has been access since the last time you checked it and therefore it can be evicted all right so say I page pages 1 2 3 4 again each one has their own reference bit in the very beginning the reference bit is set to 0 so let's say that some some query accesses page 1 so I'm gonna go ahead and flip its reference bit to 1 and no matter how many times somebody accesses this this page it's always set to 1 it's not a counter so now now I need Invicta page because I don't have any more space so my clock hands gonna start this first one I see that it's reference set the one and therefore it's been accessed and therefore I should not have victim but now I reset its reference bit to zero and then go on to the to the next one and I'm gonna sweep around if I come back around and set the zero then I know I can evict it so this guy here his bit is set to zero so we can go ahead and vicked it remove it and replace it with a new page and then we don't set its reference to one we just set it zero and then move on to the next one so let's say now page three and four have been access so we check that reset it to zero check that reset to zero now we've come back to the page one was the first one we checked its reference it was zero since the last time we checked so therefore it can be evicted so again reason why this is an approximation is because azzaman victim pages I'm not a victim exactly the one that's the most least least recently used it's sort of you know it's the same within some time window these pages have not been used and therefore it's if there's I go ahead and victim and the intuition here is that if the page hasn't been used in a while then it's probably not gonna be used again in the near future so therefore it's something I can go ahead in a bit right right so that assumption works a lot works well for simple things like doing point queries to go access single things but clock and LRU are susceptible to what is called sequential flooding and what this means is that when we have a special scan that's gonna read every single page that's gonna pollute our page cache and that's gonna end up having we can end up evicting pages that maybe we do really want that argument use very right and in the near future but because that scan read a bunch of pages all those pages are gonna have newer timestamps and then the page I actually do want right in this case here the most recently page use page is actually the one I want to evict not the least recently used so there's another good example where you if you could have different buffer pool different buffer pools or different tables based on how queries are going to access them maybe one I want to use most recently used in another one I want to use least recently used so let's look at example let's say I have one query that's doing a point lookup where where a equals we're ID equals one and it reads page zero so go ahead and fetch that into my buffer pool and I'm fine so then now have another query that's gonna do a central scan so it's gonna rip through all my all my pages and they want to once and make space for page three if again we're using least recently used then it would figure out that Oh page zero is the least recently used let me go ahead and evict that and put in page three but in my work load I'm executing queries that look like the first one over and over again so now if I execute this query all over again now I repaid zero I just evicted it and now I'm screwed because now I got to go out and disk and get it okay so what I really wanna should have done is is evicted one or two because this scans gonna go through go through a read more data and it's unlikely anybody else is going to come and read this thing here so the way there's three ways to get around this let me sort of cover some of these so far so the first is to do it's called LRU K where K is just you keep track of a number the the time the number of times a multiple timestamps every single time this the page is accessed so now when you want to say which which one should I remove you don't look to see which one has the lowest time Stan you go look at the intervals between those timestamps and you say which one has the Long's amount of time between one access to the next access and then can use that to figure out which one's the least likely to be used so this because we're using the history to estimate when it's can be accessed again to make help us make a better decision about what pages should be evicted so LRU K is what's used in the if the more sophisticated ad says we'll do something like this I don't know I think my sequel might use this I don't I don't remember all right the next optimization we can do which we sort of already talked about with having multiple buffer pools is to have localization and per query so rather than have that you know as I'm skating the table and putting it into the global buffer pool if I have a small little set aside some pages in the buffer pool that are susceptance till read them but it's it's I'm keeping track of how I'm using pages so then then when I want to make a decision what to evict from my query I evict the ones that are least recently used for me not the global view so we saw this in Postgres Perez had that hit memory show the hit was like 32 then with the 64 right that's this little ring buffer that they're keeping track of what pages that that queries accessing they make decisions what what to evict all right the last one is view priority hints again this is where we talked about before when we have we have indexes we know how they're scanning data know what pages different access so we can use that information to make decisions about what - a bit so let's say we have our B plus tree or whatever tree data structure we want and they have a bunch of queries they're gonna insert data where there's a global counter for this table or just incrementing it by one and inserting over and over again like a serial key or auto increment key so if we're now sorted on this index is sorted on ID from min to max we know that every single time we do an insert the ID value is always going to be one more than the last one we just inserted so that means we're always gonna be going down the right side of the tree and touching these pages so therefore we should have hints up into the buffer we'll manage and say these pages should try to stay in memory I don't care about these so much about these other ones here or likewise if I have a query that does lookups on on different IDs or actually any query that does a lookup on this index I know I'm always gonna be going through the blue page because that's how I enter this index I have to go through that so therefore I want to make sure that's always pinned in memory that always stays there right because otherwise if I if I get by get to the bottom and I need space and I Vic this thing it's a bad idea because I look and that's the least recently used but I know that the next queries gonna come through it and go to exactly for that page so again this is what the commercial systems can do provide you some extra information up above alright the last thing to talk about is how do we actually handle dirty pages so member that there's a dirty bit and the page that says whether a query has modified the contents of that page since the last time it it's in since since it was brought into the buffer pool so when we announced what paid to evict to bring a new page in the fastest thing we could do is just find a page that was that's not marked dirty and immediately just drop it and you know use its frame for a new buffer pool the slower thing we have to do is if a page is dirty we have to write it back out the disk safely before we can reuse that space for it for our new page so now there's this trade-off we have to make and our replacement policy decide well there's a bunch of pages that are all that are all clean and I could drop them super easily but they actually may be needed in the near future so I don't want to actually drop them instead I want to pay the penalty to write out a dirty page flush it remove it from my bumper pool and reuse its space so how you actually balance them is is super hard right because again I in this case here to do a disk read if I had to write out a dirty page it's to disk i/os one IO to write out the dirty page then remove it from the buffer pool and then another IO to read a page that I want in this case here it's one IO to just just go read the page that I want cuz I can drop the the page that's already in the buffer pool so how you actually figure that out again it's super hard and this is what the commercial systems my opinion do better than the open-source ones so way to get around this to avoid that the problem of having to write a page out as soon as I need it for free space in my buffer pool I can do background writing so periodically that data systems gonna have a thread they're gonna look through my buffer pool figure out what pages are marked dirty and just write them out to disk so that way I can flip them to be marked it's clean and now when I do from my replacement policy just slide what page to remove I have a bunch of clean pages I can I can drop right away so you gotta be careful when you do this because you don't want to write out dirty pages before the law of records that correspond to their to modifying them to make them dirty you know make sure they're the law were custom written out to disk first before you write out the dirty pages we'll have a whole lecture on why that's the case later on in the semester but just know there's like it's not just like I can blindly write any page I want I have to do some Etra step protection to make sure I'm writing things in the right order this is something that n mapkit cannot do all right so I'm gonna skip this for the other memory post just we've already sort of covered this it's more than just the pages from tables or indexes there's when we run queries we also needed to generate some some information all right so the again the the whole point of this lecture was to talk about how we can manage memory better than the OS because we know what kurz are doing we know what's in the pages we know how things are being accessed and we can make better decisions and essentially we're gonna use information on what in the query to you know for all these different things that we talked about and a bunch of optimization we can apply to help us make this work better all right so any questions about buffer pool all right here's what you really care about project one right so the for the first project you're me building your own buffer pool manager and replacement policy so this will all be done in our new database system called bust hub which is it's an open source system it's disk based again it's you will see this will be stub files in the code that you would download from github then a clearly show here's the function need to write and here's here's how to actually you know implement that what we're asking you to do so the project is the write up is available online the great scope isn't been set up yet we'll do that later today but if you can finish this project in a single day come talk to me because we wouldn't want to do other things so we are gonna already provide you to dis manager and already the page layouts so you don't worry about that you just will give you a page blocka blocka pages and it's up for you to decide how to store them in memory and then and and invoke the disk manager to write them out as needed so for the first one we have a separate class called clock replacer and you'll be implementing the clock policy that I talked about here today again it's an approximation of of LRU we just sweep the hand and flip these reference reference bits so that means you need keep track of as pages are being accessed because you'll see this in the buffer point API you have to know that when I say read a page or write a page that you go update the reference bit inside of your LRU replace or sorry your clock or placer so the one thing to be important to know is that if you do a sweep and all the pages have been modified then you just pick whatever one has the lowest frame ID or of all the pages are pin and you can't free one then you pick them on the lowest page ID right cuz otherwise you just spin forever and this will be in the write-up the major effort will be on the on the buffle manager so your element the clock replace your algorithm first and then you hook that into your buffer pool manager and for this one it's again it's up for you to decide how you actually want to maintain your memory how you decide what internal data structures you want to keep track of what pages that are available what pages are are dirty what pages are being pinned right you can do whatever you want it's just you have to implement the API that we expose to you so it's means super the thing that always tricks up students every year is to make sure you get the ordering of the operations of how to pin pages correct right so we'll do multi-threading graded test will try to read a page and pin at the same time and you'll make sure that everything turns out in the right order and this would be more clear when you look at the write up and see what we're asking you to do so how do you get started so again everything is available on github you want to go to your if you don't forgive it a github account sign up one it's free there's also I think an educational one that you get extra stuff but basically you'll go to the github page for the for the the database system and could be a little fork button and you fork it into your private repo a fokin is your own market is private so nothing's public and then just do all your changes in there if you sign up for the github account you can get free private forked repos right because if you put everything public than other students can see what you're doing and then potentially copy from you the very first thing you should try to do today or tomorrow as soon as possible be super helpful try to get the software to build on your whatever machine you're gonna do your development on so it works on Ubuntu it works on OSX it works on Windows with the Windows server or server like Linux whatever this package you can download install the thing though for OSX is not gonna support the clang formatting stuff that we'll talk about in a second so great skip we'll run this for you you can run it in docker if you this is a problem we can also give you a VM image but you'll have to you don't have to figure this out on your own we'll have instruction to try to help us out it does not compile an Android machine we tried it it doesn't work the software they have on there is too slow if this is a problem you don't have your laptop please email me and we'll figure something out ok so things to note should not change any file that other than what you must hand in because we're basically to blow everything away there's four files you have to turn in we blow everything else away and plop your code on top of the latest version of the the system and run all your tests the projects are cumulative meaning if you bomb this one you're gonna have problems later on because you know the next project is actually we use the buffer pool manager that you built today I build now we're also not gonna be providing solutions at the beginning and then we're not gonna happy debug and your code on Piazza another thing we're doing new this year is that we're requiring you to write good-looking code normally people like fit code and so now we all want to check to make sure it actually conforms to a good style guide so we followed the google sleeveless style guide and we also followed the docs in Java doc style guide so we have checks already in place that will check all these things for you like if you call make format it'll make sure your code looks pretty in the simplest aisle guide but there's a bunch of other things like how you allocate memory how you set up your for loops and so forth that we use clang tidy and clang format to to enforce more more detail so you'll run these commands like clang tidy collect check censored check lint it will throw errors they won't correct it for you or throw errors and say your code looks crappy here's how to fix it ok and we're gonna run though some grade scope so when you turn it in if you write crappy code you'll get you'll get a zero score because you'll fail these tests so this what I'm saying so Linux and Windows I think this works for OSX I don't think this works but we can we can provide you a PM you can do all your development in there ok last thing don't plagiarize we will run your code through moss there's some some people in China that take the code and I've already implemented some stuff there's is all crap we've run it doesn't work don't make your stuff again don't put your stuff on the public repo because if I run your stuff and someone copies from you because your account was public rerun the moss and you both come up as being duplicates of each other I don't know who stole from who all right so you broke they're gonna fail ok so don't put any of your code public you can do this thing then this semester because I know you want to go in the job market me like oh here's what I did in this class truth be told no one's actually gonna care because everyone's implementing the same thing it's not like an independent study where you you make some breaks it could break through so employers they don't care that much that you have your project online but if you want to do it and the semester if we're fine with that ok any questions next for hash table hit it home in schools with Michelle in case any same on Linda mix of broken bottles and crushed up kids let he's misty nights in my system cracking up on blessed let's go get the next one then get over the net will be son ricochet jelly hit the deli for a boat one naturally bless ya what rap is like a laser beam the pawns in the bush say not even like a chain wrap the bottle of us a nice go don't feel like drinking head boney to you drunk you can't try cross he's alive and if the sake don't know you can't a bang