Yes, and it's snowing. DJ drop table, thank you. So I noticed you don't have your deck today, what happened? Remember how I forgot to get my girlfriend a gift? Yes, you had to buy her a gift now? Yeah, but I didn't have any money. Yeah, so what'd you do? I had to flip my word. You sold your deck? Yeah. How are you going to drop the beats now? I've got to make some bread to get a new one. But this is going to interfere with your album now, right? Yeah, it's probably delaying it back, you know. How long? You don't have anything.  Let's figure it out right here, yeah. All right, well, he's got his problems. We have database problems, but this is the last class. And as I said, it's just going to be the final review and then a system topary for what you guys voted on for what you wanted to talk about. So just real quickly, the remaining things for the semester, project four is due next week on the 10th. Yeah, it's way off. When's the 10th? Is that Monday or Wednesday? Not even close, right? So Tuesday, December 10th, with the final project and the extra credit will be due. We promised you feedback. We found people plagiarizing. So we had to deal with that first and then we'll hopefully be able to put out the reviews or the feedback for everyone else within the next day or so. So I apologize for the delay. Overall, they were pretty good. Some were better than others, obviously. But the feedback will help guide you to finish it up. So they put the extra credit and then plagiarize there. So you remember how when you filled out the form, you had to click the checkbox. Yes, I agree, I'm not going to plagiarize. They still plagiarize. Yes? And they'll still get zero. Well, they're very at least zero. Whether I go talk to the provisor or not, that's another story. Yeah. They, again, see me doesn't f**k around. They take this s**t seriously. And the fact that it made you click that checkbox and it's on video saying, me saying don't plagiarize, you don't have any evidence. You're f**k. Not you, I'm just saying whoever did it. Yeah. Yeah. And then the final exam is due on Monday, December 9th. Actually going back to extra credit. This is why we have, it's like a wiki style. So we have our vision. So the person could go back and try to remove the plagiarized text, but it's still in the database. We can always go see it. Anyway, again, not you, but in general. All right, the final exam is on Monday at 5.30 p.m. in Posner Hall, which I think is over there, the old business school. Yeah, so we'll cover that first, okay? So any questions about the extra credit or project four? And then for homework five, we will have that graded and released by Friday, whatever, I think it was due yesterday. So four days after that, unless everyone has already turned it in, we'll send it out, okay? All right. So final exam, all right. So you have to take it, or you don't have to, but you should. This is not live yet, but I'll post this after class. This will be basically a summary of everything that I've talked about. Like it's the same thing I did for the midterm. It's like the sheet of everything you need to know, what chapters in the book, what homeworks matter, and things like that. Again, Posner Hall at 100 at 5.30 p.m. Don't come to this room. And if you're curious why you should take this other than you want to pass the class, you can watch that video. All right, so what do you need to bring? You should bring your CMU ID because it's a class of 95 people, 96 people. I don't know everyone, so I need to check your ID. Just like the midterm, it's one page of handwritten notes double-sided, no shrinking on the slides, no copying and pasting of text. If you write it by hand on your iPad, and want to print that, that's okay. But again, just no text text, from a word processor. And then if you were in the class last Monday, bring your extra credit coupon and you have to turn that in when you turn in your exam. So the thing is, you're optional. If you want to change your clothes halfway through, somebody did that two years ago, I'm fine with that. Because also it's at 5.30, you could bring food. I think we'll give up candy. I'll try to do something better than that, but I can't promise anything, right? It's not going to be a full four course meal before the exam. What not to bring? Again, I think we talked about all the problems on the midterm. Everyone brought weird stuff in the previous years. Two years ago, again, somebody brought their roommate just to hang out. Don't do that, okay? Before we get into the course material for the exam, yes, sorry, go ahead. On the file exam, it says it's from Porter 101. Is that what pH means? Yeah. All right, then yeah, whatever that is, yes. Where's Porter Hall? Oh, that's the one over there, yeah. If it's not Gates, I don't know where it is, right? I'll be honest. This is my seventh year. Okay. So right, so I'll announce this on Piazza as well. I need everyone to fill out the course evaluations.  That actually is useful to me. I actually read these things. So the things that I'm interested in getting feedback from were like, was there a particular homework assignment you thought was unnecessary or stupid? Anything about the projects? I mean, you've seen my announcement on Piazza that we're looking for people to help with expanding bus tub further, fixing all the things and maybe went wrong this semester. But if there's, again, something about the project that you thought was too hard, the pacing was not right, you want a more documentation, less documentation, you thought it was too easy, too hard. Again, that feedback is actually super useful to me. So undergrads are awesome at filling out course evaluations.  The master students, you guys, you guys to click 5555 on everything and he's the greatest professor. I don't want any of that, right? I actually read this. The university apparently reads it too. I don't care about them, but I actually make the course better based on your feedback, right? One year, a kid psychoanalyzed me with the Meyer-Briggs test in the feedback. That was useful. So again, please go for those out and I'll send a reminder on Piazza. All right, so I didn't have office hours on Monday, but I'll have office hours, extra office hours this Friday at 3.30 in my office and then I'll have my regular office hours at 1.30 on the day of the exam. If you can't make either of these and you're dying to talk to me, please send me an email and I'll try to make arrangements. I may have to like do it over Skype or Hangouts because of the thing, the baby. And then all the TAs will have the regular office hours up until and including September, December 14th, right? So the due date for the project four is on the 10th, but again, you get four late days so it'll go out into the 14th, okay? Any questions about office hour stuff? All right, so this always comes up every year. What do you need to know from before the midterm? So the exam is not cumulative, meaning like I'm not gonna ask you questions specifically about like buffer pools, like how does this effect your policy work? But you obviously didn't know, it's a part of a database system. We've covered it through the full stack. You need to know how all these different pieces work together. So the things that you have to know about from the previous prior to the midterm would be the buffer hold management, hash tables, B plus trees, short models, and then enter a query parallelism, which is again running multiple queries at the same time and you obviously didn't know how that works because you have to do transactions that could be updating the database at the same time, okay? So this is clear, we're not asking you specific questions like in the earlier homeworks before the midterm, but this is background knowledge that you just, if you forgot this already, you have other problems, okay? All right, so the main thing we spent time talking about was about transactions, right? You should be aware of what the basic concept of ACID, what are the different properties that are combined in the acronym and what the data system is supposed to provide. Then we talked about the difference between conflict serializability and view serializability. Remember, view serializability nobody can actually do, so there's no way to actually check this. It's just a higher level concept, but for conflict serializability, you wanna know how to check this and how the data system can ensure that it generates a schedule that's guaranteed to be conflict serializable. What it means to have a recoverable schedule, right? Basically means no cascading of boards and then isolation levels and the anomalies, right? Dirty reads, unrepeatable reads and phantoms. Then we talked about concurrency protocols. It actually generates schedules on the fly for arbitrary transactions that are conflict serializable. So we spent a whole class talking about two-phase locking. So as you know what the basic protocol is, but the difference between the non-rigorous and rigorous one is, what's the difference? What does rigorous two-phase locking mean? In the back, yes. You release all the locks at the end. Thanks, Matt. Yeah, so rigorous is you release all the locks at the end. There is no shrinking phase. Regular two-phase locking, as soon as you release one lock, then you're now in the shrinking phase and you can't acquire any new locks. Then we talked about multi-granularity locking, right? And the big thing there was the intention locks. How do I notify or how do I post information about what I'm gonna do at the lower levels of the lock hierarchy in the upper level? So I don't have to take maybe locks on everything. If I want to update a billion tuples, and my table has a billion tuples, I better off just taking a single lock on the table rather than locking every single individual tuple. And then it's important to know how you release these locks, like in what order? Is it top-down or bottom-up? Then we spent a lecture on talking about timestamp ordering in concurrency control, right? So you should know what the Thomas Wright rule is, the basic protocol that we talked about. Then we spent time talking about optimistic concurrency control. What are the three phases? Read phase, validation phase, and write phase. When do we actually acquire a timestamp for a transaction in these different protocols? In the basic timestamp ordering, when do you get a timestamp? When the transaction starts in optimistic concurrency control, when do you get a timestamp? What's that? When you validate, yes. When you finish the read phase. Then we talked about multi-version concurrency control. I'm not gonna worry so much about the, again, the concurrency protocol that you would use in MVCC, like you're doing MV2PL or MVOCC. I more care about the version storage and the ordering of the delta records or doing the pen only, or you're doing the time travel tables, and then how you wanna do garbage collection. Then we spent a lot of time talking about crash recovery. Question, yes. I just wondered you to speak a little bit about the isolation levels. Right, so the isolation levels, again, it's sort of a, at the very top you have serializable isolation, and then below that you have a repeatable read, below that you have read committed, and below that you have uncommitted read. And so basically as you go down that hierarchy, the database system is not enforcing or protecting you from different, certain kind of anomalies.  But then if you go down to a repeatable read, then you're not gonna do phantom checking. If you go down to read committed, now you're not doing unrepeatable reads. And then read or uncommitted read or read uncommitted is no protections. Yes. So is a snapshot isolation one of these levels? So the question is snapshot isolation is one of these levels. Snapshot isolation is a weird one. It is, it's almost orthogonal to, so the answer is no, it's not in that main hierarchy. If you take the advanced class we'll discuss this a bit further. But basically in 1992 when they invented, when they came up with the ANSI standard for these isolation levels, the guy that was supposed to double check the other guy didn't double check that they missed snapshot isolation. So there's an anomaly that can occur on a snapshot isolation that cannot occur in the other ones. But the ANSI standard doesn't support it. You don't have to worry about that. Just go with the ANSI standard. So serializable, repeat or read, read committed, uncommitted reads, read uncommitted. Yeah, snapshot isolation is a, it's not a straight hierarchy. The tree actually is actually way more complicated but we'll cover that in the advanced class if you take that. The ANSI ones are fine for the final exam. All right, so we talked about crash recovery. We talked about the different preferable policies, steel versus no steel, what does steel mean? Yes, so she said, so the steel policy means that a, the data system is allowed to write dirty records or dirty pages out the disk from an uncommitted transaction. Under no steel, you're not allowed to do that. And then force versus no force, somebody other than Paulina? Correct, so she said, you have to write all the dirty records out the disk before transactions are allowed to be stated that it's committed. And then under no force, you don't have to do that. So with right-of-hand logging, is it using steel versus no steel? Using no steel, no, sorry, using steel, wrong, right? Because with right-of-hand logging, I'd have to make sure that the log records that correspond to the changes to the data, the data pages, the log records have to be written to disk before my transaction is allowed to commit. But I'm allowed to, at some later point, write out the dirty records after the transaction is already committed, which means that it's also no force. We talk about different logging schemes. The main distinction I care about is logical versus physical. Physical is where you're actually writing out the low-level bits or bytes that got changed to the database system in your log records.  And so there's trade-offs to these things, right? So if my query is gonna update a billion tuples, with logical logging, all I have to have is that update query in a single log record. And that's enough information for me to record what change got made. Under physical logging, I have to have a billion log records that correspond to all the change I made to every single tuple. Then we talked about how to do checkpoints. So you should know about the difference between the fuzzy versus non-fuzzy, right? Fuzzy means that I'm allowed to write out inconsistent data to the database system or to the disk when I'm taking the checkpoint, but I need to know what was going on at the time in my system when I'm taking the checkpoint so that I can reconcile after I'm recovering what pages may or may not have gotten written during the checkpoint or may have been modified while I was taking the checkpoint, right? In the non-fuzzy checkpoint case, you're basically stopping the world for a brief period while you write everything out. So that way you're guaranteed to have a consistent checkpoint. And then we talked about how to do areas of recovery for a lecture, right? What are the three phases? The analyze, the redo, and the undo. So you should know how far back in the log you need to look at for each of those phases, potentially, right? You should know about the compensation log records, when do you write them, when do you read them, right? If I have a compensation log record in my log and I apply it, but then I crash before I finish my recovery, when I come back around the second time, do I need to make another CLR for that first one? No, right? Because you've already done it. And the CLR has every information to tell you how to undo the original update. All right, and then we briefly talked about distributed databases. You know, we can't obviously go real deep into this beyond what was covered in homework five. As you know about the different system architectures we talked about, shared everything, shared disk, shared memory, shared nothing. What are the trade-offs for these? When would one be better than another? How are we actually gonna do replication in these different environments, the distributed environment? How do we make sure that the database system is fault-tolerant, how to make sure that database system that we're making updates is consistent across all the copies of the data? How do we do partitioning? Again, high-level things. We talked about hash partitioning. What are the benefits of them? How do we actually find the data you need? And then, two-phase commit. You know, under what circumstances, you know, at what steps would you do at different phases of the protocol? Don't worry about Paxos. That's too hard for a final exam in databases. Okay? So, any questions about the final? Just sweeten the deal. I forgot to announce this earlier. If you take the final exam, when you turn it in, I will give you a bus tub sticker. Or you can put it on your laptop. Okay? We have enough for everyone. Yes? What is the duration of the exam? This question is, what is the duration of the exam? It will be the same as the midterm, but you have three hours. And there's always somebody who takes three hours. Yeah. Yes? Well, yes? Is there going to be a practice exam, I thought? Yes, so the question is, will there be a practice exam? Yes, when I post the review guide, I will post the same way I did in the midterm. I'll post the practice exam. Yes? Will it be multiple choice exam? The question is, will there be multiple choice? Yes. It's easier to grade. Yes? So, going back one slide, why do we make the distinction between force and steel? Like, can there ever be a case where you have to know the force and know the steel? All right, so the question is, I made the distinction between force versus no force or steel versus no steel. Would there be a case where you would have one, like, when would you want to use one? Like, oh, oh. So, no, I think you have to be one, you have to be sort of like, steel no force or no steel force, right? We talked about shadow paging. Shadow paging was an example of no steel force, because I wasn't allowed to overwrite dirty pages from uncommitted transactions because I had this shadow copy on the side and I was making all my updates there, right? So, that's the no steel part. And then the force part is, when my transaction went to co-commit with shadow paging, I had to make sure all those dirty pages were flushed at disc and then I flipped the pointer, the root pointer to now point to the old, the shadow becomes the new master. When I do that, I have to make sure everything's already flushed. So, again, right ahead of logging is steel no force, shadow paging is no steel force. And then the main takeaway was that the right ahead logging is almost always, I can't think of some, maybe just some cases I haven't thought of it, it's almost always better. And it's what every system uses, most systems. Any other questions? Yes. Why is it unlike the midterm, we don't need a calculator for this? Yes, so this question is, unlike the midterm, do I not need a calculator? I forgot to highlight that, yes. You do not, you don't need it. Again, think of what we did in the homeworks. We didn't estimate joints. We didn't, yeah, I don't think it's like, whatever it is. There will be no questions on like query optimization stuff. That's the only thing I can think of when you need a calculator, right? So don't worry about that. Any other questions? Yes. About the locking, like the shared, you know, you know what you're gonna find. Like two phase locking stuff or the hierarchy? Yeah, the higher lock, different levels. Yeah, so her question is, are there more questions about like multi granularity locking? So in the textbook, all the odd problems, the solutions are online. I haven't looked at the newer version, but like there might be some questions in there you could look at. And if you do the odd ones and you go to the DB, like DB, the links on the course website, it's like dbbook.com, they'll have the solutions to the odd problems. You can just follow those. I'll put a link on the final review webpage. Yes? Yeah, bring it though. So actually can you bring notes from midterm? Yeah. One sheet. One sheet. Copy whatever you need. All right, so this is probably one of my favorite lectures. Well, they're all good, but because they get to talk about more databases. All right, so again, I asked everyone in the class to vote on what systems they were most interested in learning about. So here's the tally from last year for the top 10. Cockroach, DB, Spanner and MongoDB. And here's what we ended up with this year, which is very surprising. Scuba came out first, followed by Mongo, followed by Cockroach. And surprisingly, this is my, I think, fifth or sixth year teaching this Pupri thing. Spanner's always been the top three, right? And so the only thing I could think of that people, white people didn't vote for this as much is because the name got changed to Cloud Spanner, right? And maybe people didn't think it was the same thing. So that's okay. But Scuba's a really interesting system, so we'll start that with that first, okay? All right, so Facebook Scuba. And also I also noticed that people vote for the ones that has the name of the company in front of it, like Amazon Aurora, Baidu Ocean Base, then people vote for those things more. So anyway, all right, Facebook Scuba. So what we're trying to do here in the system Pupri is to show you that we can now look at real-world systems and start using the vernacular that we've discussed all throughout the entire semester to sort of start to understand what this thing is actually doing, right? So now I can say these things, oh, it's a shared nothing distributed system and you know what that means.  You know what the performance characteristics and performance challenges you would have in a system like this. So Scuba is an internal database system that Facebook has been working on for several years now. It was first announced in DODB in 2013 and they've been still working on it. It's not open source, right? It's only actually very recently is there now some public information about the newer version. And it actually turns out because the guy that is actually leading the project is CMU Database alum. Like he got his PhD here before I showed up and he's now running the development of this database system. And then his boss is actually a, his boss is the mother of another CS student here in the CS department who actually worked on Bust Hub over the summer, right? So it's all one giant CMU family. All right, so Scuba is a, it's meant, it's designed for having low latency queries and ingestion of internal metric data generated from Facebook's different services, right? So this is not running an O2P application. This is not running, it's not like a giant warehouse. Think of like every single time you click something on Facebook, right, on the website that causes a bunch of functions that are gonna vote on the servers and they can have their developers instrument those function calls to keep track of the performance metrics, right? Throughout the entire stack. And then all that data then gets shoved over to Scuba.  What are some problems I'm seeing in my giant fleet? So the newer version of Scuba is now a column store. It's a distributed shared nothing system. It's using a tiered store just means that, this just means that like you can have a, you know, you can have a in-memory cache, a flash cache and then maybe slower disks below that.  And so one interesting thing about the system as well is that since they are trying to have this thing be really fast, you wanna run your queries very quickly over a lot of data, they are not, although they're gonna support SQL, they're not gonna support joins or not gonna support global sorting.  Another interesting thing about it that's gonna be different than everything we talked about before is that they are gonna have, they're gonna use, have replication to have redundant deployments of an entire Scuba cluster. So you would think about like, you have a bunch of machines, I send all my data to this cluster, but I'm also gonna send it to two other clusters running in different data centers or different regions. But they're gonna allow for lossy fault tolerance in this environment because the data that they're collecting it's valuable but not like bank account valuable, right?  If that data gets lost, eh, right? It's not the end of the world.  And so the way they're gonna try to avoid that is by running multiple deployments, they'll run the query in different regions at the same time. And then when they get back to the result, they see which query actually read the, had the fewest number of missing data and then they use that as the correct result. But if they lose some data, it's not a big deal. And actually they're gonna be, they're gonna have a retention policy where you can say any data is stored in this table after seven days just thrown away. And who, because who cares? So here's the high level pipeline of what they're trying to do. So you have your different application servers, all right, these are all running the website, running all the backend stuff you need to support the website. So these guys are gonna be generating structured debug logs. So think of this as like a JSON document that the application server spits out to say, here's how much time I spent in the CPU for this function and that function. So then they're gonna load this into this internal tool that they developed called Scribe. Think of this as sort of like a Kafka kind of thing where you have a bunch of log records coming in and then you can have like a Pub-Sub system to say, here's how to categorize the data I've collected and here's, and other systems get notified when new information arrives to it. So this is an older thing that since it's over 10 years old, there's an open source version that they have on GitHub but that was like abandoned a decade ago. So supposedly the internal version it's much better than what's on online now. Right, so the Scribe is now gonna take the structured logs, look at some tag to say, it's generated for this particular application type or this service and it's gonna combine them and get it together based on that category.  Think of like Parquet or Orc that we talked about last week. I just think of like a standalone file, almost like a CSV, but it's actually a binary column store. And so after they have a large batch, they're gonna generate these column store files and then now they're gonna feed this into the leaf nodes in SCUBA. And so we'll talk in this section aggregation nodes and leaf nodes but this is basically the storage nodes. Think of this as like the shared disk architecture but you can actually have run queries down here or the last class when Shashank talked about Oracle Exadata but they had the storage nodes at the bottom could actually do filtering and predicate evaluation down there. Same idea here. So now one additional thing they're gonna do is that they're gonna each of these leaf nodes are gonna update this validation service with information about the number of tuples that they've inserted for each table. And we'll see in a second that this is how they're gonna determine when they run the query on multiple deployments or multiple clusters, you'll check that thing to say, well how much data is actually missing? So I know I inserted a million tuples but I only read maybe 500,000 so half of my data went missing. Again, they're not gonna go freak out, that's okay in their environment but they keep track of this and then they know that which query is producing the most accurate result. So now it's a SQL system so they have this SQL interface or these dashboards that people can use internally at Facebook that sends SQL queries to this execution layer which then is gonna send it to these aggregators who then are gonna farm it down to these leaf nodes. So I'll discuss this hierarchy in a few more slides but this is an important distinction between all the distributed databases we talked about because it's a heterogeneous environment. So the leaf nodes are doing things that are separate are different than what the aggregator nodes are doing. And you obviously have more of these because you have more data. Yes. The category is the same as attribute. The question is the category same as attribute? Yes, think of like it's some internal tag that Facebook is ascribing to a particular class of log records, right? So again, say it's like, I don't know, the Facebook inbox or messenger, right? So you'd say that would be one category. So all the log records from the messenger app go get combined together. Okay, so again, it's a heterogeneous architecture and we have leaf nodes, aggregator nodes. So leaf nodes are gonna store the columnar data that we're getting out from the record batchers in a columnar format.  So there may not be data that the query needs on that leaf node, but they're not gonna store any additional metadata or maintain any indexes on these leaf nodes to be able to figure out whether I need to touch data at them. So they're trying to make this thing be as fast as possible. They're trying to make this, both in terms of how fast the query can execute, but also how fast you can ingest new data. So if I don't have to maintain any metadata or catalog information about which data is at what leaf node, then I can ingest new data very quickly. And then every query shows up and just scans everything. And then that determines whether you have data that you actually need. Does that make sense, right? So like when we talked about partitioning before, we talked about how there's, and we'll see this in Mongo and Cockroach, they're gonna maintain this state table that says, if you want data within this range or this hash value, go to these nodes. They're not gonna have any of that. They just blast everything, every query goes everywhere. So the aggregator nodes, when they get a query, they're going to dispatch plan fragments to the leaf, it's shown in leaf nodes. They're then gonna do, on the leaf nodes, they're gonna do the scan and some basic computation, but they're gonna send the result up to the aggregator nodes, they're then going to combine the results from multiple leaf nodes to produce a single result and then send that up to a root node who combines the final result. So this is gonna allow them to scale out the system very easily because I now, if my aggregators are running slow, I can add those nodes because they don't have any state, right? That's not where the data is actually stored, or if I need to scale out my leaf nodes, I just add more of those and keep my aggregate nodes but the same. It's a very interesting architecture that shows up on a lot of other Facebook system design. The Memsegal guys, before they started Memsegal, they spent their time at Facebook and they saw this kind of architecture and then they sort of copied it or were inspired by it when they went off the Memsegal, so Memsegal works the same way. Okay, so again, we talked about this tolerating lost data or missing data, so if a leaf node either has no data or it's down and it can't produce any results within a timeout, then they just ignore it and that's okay. And they use the validation service to figure out well how much data did this thing actually have and that'll determine the quality of the query result. So let's see what the full pipeline looks like. So again, this is considered one scuba cluster. They're gonna have multiple instances of the same kind of cluster running in different data centers, different regions. And they're gonna invoke a query on all of them at the same time. And they all get back the same result and you pick out which one is the best one. So my query shows up, I wanna do an aggregation of the number of events that crashed on, there was a crash on a Monday. Again, so I can only do single table queries, I can do aggregations, I can do group buys, I can do filters, I can do scans, but I can't do global sorting and I can't do joins. So the root's gonna get the query and that's gonna break it up into query plan fragments that's gonna then distribute down to the aggregators and the aggregators are gonna distribute them down to their leaf nodes. All the leaf nodes are now gonna do a scan and then send results back up. But let's say, while we're executing this query, this node goes down, which happens, if you have a large cluster. So everybody else can still run, everybody else is still gonna be able to do the computation for this query. And then they send the results back up to the aggregators and then just again, combine it together. So I'm doing a count, I wanna know the number of events that occurred. So this guy says I have 10 events, he has 20 events. So this guy just takes 10 plus 20 and produces 30 and then sends it up to the root. And the root does the same thing, it just adds all the results from its different aggregators and then produces the final result. So this is clear, yes. So just breaking up the query mean like sending the same query to each other. We can write anywhere, so we couldn't use any information to optimize the query. Say it again, okay. Then for the query was just scan everything. Yes. And then what does the root send to each other? So this query is to scan everything. So there is no metadata, there's no catalog to tell me anything about whether or not these leaf nodes have the data that I have in my where clause. So I don't know where type is, I don't know where time is. So I send it to everyone. So everyone essentially is gonna, in this example here, everyone's gonna do the exact same query on the leaf nodes. So he's doing a count star where type equals crash, time equals Monday, he has 10, he just shoves that up. And this guy knows while I'm doing this count thing, so I just add it, sum up the numbers together, produce the result. Yeah, so you previously mentioned that we don't keep any metadata. Yes. So then is it true that for any query, the root always copies the same query too? This question is, is it true that for every single query you would always copy the same query down to leaf nodes? No, because like for averages, the way you do that is a count on a sum and then you compute the average at the top. So that would be different. Yeah. So there really isn't any, since there's no joins, there's not really a query optimizer here. It's just I need to know what the, I just convert the SQL to a query plan and to shove that down. And there's some basic heuristic they probably do to figure out like how to actually break it up and send it down leaf nodes. Yes. Why was this made to have both like a root and a creator as opposed to like a client cross all the leaf nodes or something like that? So his question is, why was it decided to have a root node here and have all the clients go to this versus having everyone potentially go to any aggregator and then any aggregator can talk to anybody else? So my understanding is that there's actually, there's a layer above this as well of the root where they're doing a mission control. So they can do some things like, oh, if a query, if a node is sending too many queries, if a client sending too many queries, maybe you want to throttle them or like if I know I'm getting bad data from some side of these nodes, then I can have someone make a decision about what to exclude or not include in my query execution. So it's allowed them to have a single location to have a global view of what's going on in the cluster. Doesn't know about what's in the database, right? Because that would be too extensive to maintain and keep fresh all the time. It just knows like these nodes are performing well or not well. Yes. In this case, I produced an IP but if there were events in that deep growth node, my result is not correct. So should look like a more... So his question is, say that this node had a ton of results, ton of, that would match my predicate. Wouldn't it be better for me just to abort this query because my account's going to be way off. How do you know that this node has all the data, has a lot of data that matters for your query? I don't know. You don't know? Yeah. In that case, it's better. So again, so think about what this is designed for. This is designed for logs being generated by machines, right? It's not like, hey, here's my bank account. I want that to be, you know, to the penny. So if you get lucy, lucy results, that still is probably okay. And then the way to sort of overcome that again is by having that validation service, they can determine how much data that they actually not read. So then also, again, then they have a bunch of redundant copies of the system running at the same time. They're all going to produce the same query. So the likelihood that every single cluster that's running SCUBA for a single query is going to have this node fail exactly, you know, exactly this node has this data fail is pretty low. So at least one of those clusters will have a more accurate result and that's the one they'll use. And that's way different than what we've talked about the entire semester. That's why I like the system. Because it's like, we talked about never losing data. Now I'm saying it's okay to lose data. Because if the tree falls in the woods and no one's around to hear it, who cares? If this node goes down and no one knows and it cares about what data's actually on it, doesn't matter. And because they're not, you know, running RAF or Paxos every single time they're updating data, this thing can run really fast. All right, so this just summarizes what I've already said before, right? So for every SCUBA deployment, there's multiple SCUBA deployments running in different regions. We're gonna run the query at the same time on all the regions and then they come back with the result and then the result is annotated with information from the validation service that says how much data did I end up not reading, right? And you pick the one that has the, that has the most, that read the most data, okay? Again, so we know the guy, Sabros that runs this, he got his Ph.D. from CMU in 2007, 2008 and now he's in charge of this. So, all right, any questions? All right, good stuff. All right, number two was Mongo. Mongo is always picked every year. So let me ask you guys, I ask this every year, why did you guys pick Mongo? I assume you picked Facebook because some of you want to get jobs at Facebook. So you think, I go in the job interview, I could talk intelligently about SCUBA. Same thing for Mongo, do you want to work at Mongo or do you want to use Mongo? Some people have already done internships, some people are going to do internships there, yes? It's much different than what we normally do. He says it's much different than what we normally do. Okay, so I've known the MongoDB guys for a long time. One of the co-founders actually went to Brown before I did. So he, we've known Elliot since like 2009 when he first started the system. He would come give talks at the CS department there all the time. And I actually was there in August. They have a new office building. They used to be right around the corner from Times Square, which is awful. They're still in midtown, but they have a nice office building. So, you know they're a big deal if you have the sign for your company outside the building, right? Above that says Warner Music Group. They have a lot of money. Mongo is doing pretty well. It's all for their databases. So this is their lobby. The lobby's nice, looks familiar, right? Yeah, the view is amazing. So this is from the kitchen. I mean, it was a cloudy day. The view is absolutely stellar. And again, all paid for by databases. It's amazing. All right, so what is Mongo? Mongo is a distributed document model data management system. So when I say document, think of JSON, like a JSON object. And in the MongoDB world, the language for what we talked about the entire semester is being slightly different. So again, instead of saying tuple, they say document, instead of saying table, they, or a relation, they say collection, but the high-level concepts are still the same. So it's one of the earliest, our original NoSQL systems. It was open source. It used to be GPL, but now they switched to the server-side public license. And this is basically to protect them from Amazon. Like MongoDB got so popular, they were worried about Amazon coming along and just running MongoDB in a hosted environment and selling it for cheaper than what MongoDB could. So they switched their license. Now, Amazon did come out with a system that does clone the MongoDB protocol called DocumentDB, but my understanding of how it works is that underneath the covers, it's just Postgres. So the wire protocol looks and smells like, looks like MongoDB, but underneath it is just Postgres. So it's going to be doing a centralized, shared nothing architecture with a heterogeneous configuration. And originally, as a NoSQL system, they didn't do transactions, and they didn't do joins, they didn't do SQL. And so right now, in the latest version of the Mongo, though, they do transactions, they brought in transactions, and they also do joins. The only thing they haven't brought in is SQL. Now, there are some hacky tools that can convert SQL into MongoDB queries. As far as I know, I've never run across anybody that runs this in those things in production. So MongoDB is going to have their own API, which I'll show in a second, that is basically you write JSON queries to read JSON data. So one important concept about the document data model, which is quickly different that we talked about in the entire semester, is this concept of denormalization. So in the relational model, we would define our tables or define our relations, and we would use foreign keys to say there's a reference from this table to another table. So again, if I'm modeling Amazon, is my store information, so I have customers, customers of orders, and orders have order items. So in a relational database system, I would define these as separate relations, and then if I want to say for a given customer, give me all the items that they bought, I would have to do a three-way join between these three tables. And the NoSQL guys argue that that was expensive to do to do these joins, because now you gotta run your hash join and nest a loop join, right? So what they would argue, you'd want to do in a document data model, is to denormalize, which basically says combine together the related information about a SQL entity in your application into a single JSON document. Right, so instead of in this environment here, instead of having a three different tables, you would have one table called customer, and then inside each customer record, you would embed their orders, and then within each order, you would embed their order items. So now if I want to go get all the order items that Andy bought, I go just get my customer record from the database system, and then I just traverse now inside the JSON document to get what I want. Now MongoDB did not invent that idea. That's an old idea from the 70s. XML databases did it in the early 2000s, late 1990s. The object-oriented guys did this in the 1980s, so MongoDB did not invent that. What MongoDB was sort of famous for was having a fast distributed JSON database system, right when sort of WebDuel and JavaScript was becoming prominent. So again, it would just look like this, your JSON document would have inside of it an array called orders, and within inside that, you have additional JSON documents for every single order, and inside every single order, you have an array for order items and then all the items that they bought, right? So again, we've talked to us that they're actually the first class. From a performance standpoint, this is going to be really fast, because again, it's one read to go get all Andy's order items. The bad thing is going to be, obviously, now we're going to duplicate a bunch of information about these different order items over and over again, and now I need to write in my application code to make sure that everything is, I maintain the integrity of all of this information. So if I change the name of item, I have to write code to go through all my, inside all my customer records to make sure I update everything. So the way you're going to actually get queries is through a JSON-only query API. They don't have a query optimizer, at least not in a cost-based one that we talked about before, and I think I briefly talked about this when we talked about query optimization. So what they basically do is your query shows up and they're going to generate sort of every possible combination for that given query, and then there's going to blast every node with different combinations of that query, and then whatever one comes back first, then they learn that that's the better one to use because it came back more quickly. So the next time you actually do that same query or similar query, they'll just reuse the query plan that they generated before. And they'll do this maybe like a thousand times and then just after the thousand query invocation, they'll do that sort of blast them all out first, blast them all out and see which one comes back first thing. So you may think it's kind of hacky, right? I spent two lectures talking about how hard it is to do a query cost-based query optimization and how hard the problem actually would be, and they chose this because back in the day they didn't do joins, so you didn't have to worry about join ordering, it was just basically was picking what index to use. So the random walk approach would actually work. I don't think they do anything sophisticated for the joins now. They might just use basic heuristic. This table or this collection is smaller than this one, so it's one versus the, one's the inner versus the outer. They support JavaScript UDS. We actually didn't talk about UDS this semester. It's basically like a function you can write in your query that gets invoked on the data server side. They do now support joins and they now support also multi-document transactions. So the early benchmark numbers for MongoDB were amazing. You could write data into it very quickly because what they were doing is one, they weren't doing transactions and they weren't actually guaranteeing anything was actually written to disk when you got response back that your write succeeded. It was actually even worse than that. If the database that got the packet for your write, they'd immediately come back when the acknowledges say, yeah, we got it. Then at some later point the write would actually be executed and logged to disk. So if you wanted to see whether your write actually made it to disk, when you got back to response, you had to go back again and say, hey, did my write make it?  That used to be the default for a long time. So if you look at the early benchmark numbers for MongoDB, they're amazing. Then 2013 or 2012, they actually turned that off. It's no longer the default. Now they're actually doing write-head log, we'll talk about in a second, and they support multi-document transactions across multiple machines, which is impressive. It's not easy to do. All right, so the system architecture I think we've already talked about before. It's a header genius, distributed components, shared nothing, the centralized query router. They're doing master slave replications. You can have your writes from one master node or master partition or shard. We'll go off to other shards. So part of the reason I think MongoDB was very successful in the early days was they actually supported auto-sharding. So the idea was here that you just start shoving data into your database and it'll be distributed across multiple nodes, but then if one of those nodes gets too full, MongoDB will automatically move your data around to balance things out. Didn't always work the way people thought it was gonna work, but back in 2010, when I would go out to Silicon Valley and you ask people, they're doing a startup and they're basing it on MongoDB, you ask them why and maybe say, oh, because this auto-sharding thing was a big deal for them.  But of course, no one does a startup thinking that they're gonna fail. Everyone thinks they're gonna be big, so of course I'm gonna need 20 machines in the future, so I wanna make sure MongoDB can scale up with me. With MySQL and Postgres and other relation databases at the time, you couldn't do that. So that, I think this was a big deal, but there's a famous four-square outage, if you wanna know what four-square is, think of like, how to describe this. It was an app you could check in what location you were in. It's still around, but it's not sort of the, not a phone app everyone uses, but they were using MongoDB, and there was a famous multi-day outage because the auto-sharding stuff got stuck. All right, so here's the architecture. Again, we talked about this before, and we have different type of node types. We have routers, we have config server, and we have a shards. So every query from the application always goes to the router, and the router says, oh, I know I wanna look up ID 101, but I don't know information about where that is. So I go to the config server, the config server tells me, and it looks into the shard table, it says the data you want is located in this node, so then now the router knows how to send the query to the right location, or it could blast it out to all of them. So again, this is an important distinction between the scuba stuff and what we're talking about here. Scuba doesn't have this partition or sharding table. It blasts the query to everyone. In MongoDB, since you don't wanna waste resources because you're trying to run update queries for your website real quickly, you maintain this information and figure out exactly where the query needs to go. So you're only touching the data, you're only touching the data that has the exact data you need. Yes? Yeah, so the question is, is there a cache on the router? Yes, so you wouldn't always have to do this, but this would be the, this would consider to be stateless. So if I crash, I come back, I get my cache version from this again. But any update to like, if I say I'm doing the auto sharding stuff and I add a new node or I move some of the data to another thing, I update this thing and that's done as a transaction. Yes? What's the origin of MongoDB? What is the origin of this? So what do you mean? Oh, the naming? Yeah. Oh, I think MongoDB just means humongous. That's all it is. Right, so, and so this is like, actually the S, I don't know what that is, but like maybe backwards, I don't know. Yeah, it's just demon or data. It's probably just demon and MongoDB, I don't know what that means. I don't know what the S means. So another thing I said during this semester was that never use MF for your database. Well, when MongoDB first came out, they were using MF for their database and we actually did a little study on MF database systems and in my, in our opinion, we haven't published this yet, the MongoDB implementation of using MF is probably the most sophisticated one that we've ever seen. It's probably the best one, but it still sucks. It's still bad, right? So basically what happened is, the way they would use MF is, they would have, they would basically maintain multiple copies of the database in memory and you would do your updates to this sort of private copy. That would then get read to disk and then you had to replay the log to update the sort of the master copy. And so the OS could swap things out anytime they wanted. It was a big, big pain for them. The other big problem they had was, they had a single lock for the database. Now this is not entirely because they were using MF, but I think it's sort of probably, probably helped make things easier using MF. So that means that in the entire database system, even though you maybe split across multiple machines, in the early versions of MongoDB, you could only have one writer in the entire cluster at a time. So if I have 20 machines, and I have one query that comes along, I basically lock all 20 machines to do update on one of them. And then in the newer versions of Mongo since version three, they got rid of this. So what they ended up doing was, they bought this storage engine startup called WireTiger, which was founded by the guy that, one of the guys that invented BerkeleyDB. BerkeleyDB is an embedded database, WireTiger is an embedded database. We didn't really talk about this too much, but Postgres, MySQL, these are all database systems that run as a standalone demon or standalone system, and you have multiple clients connected to them. SQL Lite is typically used as an embedded database. You embed it inside your application and it provides you the database functionality. But when your application closes, the database closes. So WireTiger is sort of like SQL Lite, but it doesn't support SQL, it supports like a key value store API. So probably one of the best acquisitions in a long time, they bought WireTiger and they replaced the M-Map stuff with the WireTiger engine. So when you run MongoDB now, you get the WireTiger engine by default and it's amazing. Questions, sorry, yes? Why if using M-Map is so complex, this question is, if using M-Map is so complex, why would you use this? So again, I want to prove this scientifically, I can't yet, I can't take everything what I say, like this is my opinion. M-Map is like a seductress, right? It's like, it's this sexy thing that looks like gives you what you want for a buffer pool manager, right, without having to do it because the OS does it for you. You don't need an eviction policy. The OS does that. You don't need to worry about paging, you know, keeping track of dirty pages and things like that. The OS does that.  That's when all the problems come in. It's sort of like the query optimizer. Instead of burying query optimizer, let's do something really simple and just blast everything out and see what comes back first. So instead of burying a buffer pool manager, I'll just use the OS's buffer pool cache or the M-Map cache. Let's take that one offline. Ella's a really smart guy, the co-founder and wildly successful, right? Like it's a public company, right? I think, you know, by using M-Map, although it causes problems in, it can cause problems when you really start to try to scale up and scale and hammer the system, it allows you to build a system pretty quickly. So instead of spending six months having to develop a buffer pool manager that's safe and transactional and things like that, just use these OS's M-Map. And then when they got enough customers, they got enough money, they bought WireTiger and did it right. MySQL was the same way, right? Well, it didn't use M-Map, which I don't think. Like MySQL with NADB is amazing. NADB is fantastic, it's a solid database engine, storage engine. But the original engine they used was my ISAM. That thing suckers, that thing lost data all the time, right, you have corruption. And so, but it got MySQL up and running pretty quickly, a lot of people were using it and then eventually NADB came along and MySQL bought them out and started using it. That's not a very uncommon strategy for a database business. All right, let's do a demo. So, what I'm gonna have to tell you is semi-illegal. All right, any questions about Mongo? Yes. Why would you might, why might you want to use Mongo over others? This question is why would you want to use, maybe use Mongo over others? So, the, I think that being a distributed architecture matters a lot. The document model is actually better for application development, right? Think about it, when you write Python code, you write Java code, you're writing an object. There's an object-oriented programming languages. And so, it kind of, if you can have now your object just be written out and there's a JSON document and then put into the database and fetch it back in and re-instantiate it in your application code, that could potentially be faster. But the thing I would stress though, there's nothing about what MongoDB is doing because it's a document database system that is different than anything we talked about this entire semester. WireTire doesn't know that it's actually being used for a document database system. It's doing write-ahead logging, it's doing all the crash recovery stuff we're doing, it's doing transactions underneath the covers in the same way that we talked about. So, there's nothing about in the document model that invalidates or changes anything we talked about here today. It's all at the application level, right? It's all sort of at the client level, what the query looks like, what the query is actually gonna do. Everything else below is everything we talked about the entire semester. Yes? Do they use special compression techniques? The question is, do they use special compression techniques? So, that would be in WireTiger. I think it's just snappy. Yeah. Yes? So, does that mean that if I use MongoDB, anyone can access my data? Again, the older versions, the default username password is test-test. It's not that way anymore. Yes. Okay. All right, so the last one, we have 10 minutes left, it's CockwareDB. Actually, I was there in the summer as well. So, when I went MongoDB and CockroachDB, their headquarters are in New York City. So, when I was out visiting Cockroach or whatever, I visited both of them at the same time. I visited their old office, they had this nice little pixel art thing for the Cockroach. I was actually, and this is their newer office though, I was actually surprised how big it actually is. I gave a talk there. They just raised $55 million as a series C round, which is a little money for a database company. So, that's actually very impressive. I assume that means they're doing well. So, that's good. All right, so, CockroachDB started in 2015 by some ex-Google employees. They were, I think, incorrectly characterized as the open source version of Spanner, from Google Spanner. I don't think they ever said that, people sort of attributed that to them. I would not say that's true at all. CockroachDB is sort of a core architecture that's fundamentally different than Spanner, and Spanner has one magic piece that nobody else has that Cockroach doesn't do, and nobody else does. So, is they decentralized, shared nothing, homogeneous, database-assisted architecture, and they're gonna be doing range partitioning. The internal storage engine that they're gonna use is RockDB. So, the same question is, why would anyone wanna use M-Map, right? Well, my answer was, because you don't have to build that piece yourself. So, CockroachDB, they didn't wanna spend time writing a storage manager, right? Same with the WireTiger piece from MongoDB. So, a lot of these newer database system startups, they're using RockDB or LevelDB, these embedded storage engines, so they don't have to worry about reading writing data from disk, and they worry about the higher-level parts of like, you know, managing transactions in a distributed environment. So, they're gonna be doing multi-version concurty control with optimistic, you know, optimistic concurty control protocol, and I don't know if this is still true, but they're only gonna support serializable snapshot isolation. So, I don't think they support the other isolation levels. They also speak the Postgres wire protocol. So, that means that if you have an existing Postgres application, you can just, in theory, point it to CockroachDB. If it's pointing at Postgres now, you migrate your data over to CockroachDB, and you don't have to change potentially any of the SQL. It's not entirely true for everything. Like, there's some things that are different, like auto increment keys, but in general, migrating to CockroachDB from Postgres should not be an owner's thing. So, at its core, CockroachDB is a distributed key value store, a transactional distributed key value store. So, that means that the lower storage engine of the system at RockDB is a key value system, but then the way they're doing transactions, or the way they're managing the database across multiple machines, is essentially just gonna be a key value store. So, using that, now they can build layers above that to provide the full sort of SQL compatibility that you would want. So, once you get past the SQL query shows up, they can then convert that SQL query. The query plan is essentially going to be a bunch of key value API calls that can then read and write data from different nodes. So, the way they're gonna coordinate the updates throughout the system is using Raft. Raft is essentially at a high level, same thing as Paxos. It's a consensus protocol that allows me to say, when I make an update, and I wanna commit a transaction across multiple machines, everyone's gonna agree, or Quorum has to agree that the updates allow it to proceed or to occur in order for that transaction to be able to commit. So, the way they're gonna do OCC is through using timestamps, it's using what are called hybrid clocks. So, I think I talked about this a little bit, or Prashant talked about this one, can we talk about timestamps and convergence control? We need a way to have a clock that we can uniquely identify every transaction, and that clock needs to always be increasing. So, we know what transaction in the serializable order, as during the execution, what transaction came before the other. So, you could just use the physical clock, which is from the actual CPU, like the machine itself, what's the system time. But the problem in that one is, that's not gonna be guaranteed to be highly synchronized across multiple machines, right? Every computer has a clock, that clock is not super, super accurate. It's not like an atomic clock, right? That's gonna be counting electrons coming off an atom. It's gonna be some kind of quartz crystal thing that has to approximate. So, now you're gonna have a bunch of skew in your clocks, and so now what could happen is, transaction rise on one node, it thinks it's time stamp one, another transaction rise on a node, it thinks it's time stamp one, and now I have a conflict that I've resolved. So, the way they're gonna handle that is through a hybrid clock, where you'll still use the system clock to try to get what the current time is, but then you'll also use a logical clock that allows you to have globally ordered transactions without having to synchronize every single time. So, basically it's like a little counter that says, here's my current time stamp, and I just, my machine would add one to this logical counter to increase it. So, what's gonna happen is, again under OCC, transaction's gonna stage all its rights in the system, so these are the modifications that I wanna make, yes, question. How's the hybrid clock? This question is, how's the hybrid clock different than the Google Spanner clock? The Google Spanner clock is not, the Google Spanner, so the true, I don't wanna get too much into Spanner. Google Spanner is relying on the, like, Harbor clocks to have super accurate times that are synchronized across all the machines. And the True Time API gives you a bound of how long you have to wait for someone to show up with a lower time stamp. It's a way to, basically this is like True Time, using only software. So, if you have really bad clock drift, like this one machine is one hour behind another machine, no transaction could potentially ever complete because every transaction that's been in the past and the future is getting messed up. So, you have to make sure that you try to keep your clocks in sync using like NTP. Spanner doesn't do that, Spanner doesn't, you know, the GPS satellites plus the atomic clocks. They have super fine granularity. All right, so, again, different than SCUBA, all the metadata about where the data exists with the transaction state is, that's gonna exist in our own key value store as well. And that's all considered as transactional. So, let's look at a simple example here. So, we have our application comes along and we'll maybe update data in this cluster. So, again, different from SCUBA, we maintain a partition table just like a MongoDB to keep track of what node is responsible for what range of data. So, when my query shows up, the first thing I have to consult is this partition table which actually would be replicated on every single machine and say, well, I wanna access key or ID equals 50, what node is the leader for that? And then, in this case here, it's this guy, so now my write has to go here to do my update and then the update has to get propagated to the other nodes and then we use raft to get everyone to agree that we're gonna go ahead and commit this transaction. So, instead of using two-phase commit, they're just using raft. So, now, if I wanna do, now I read, say for this ID equals 150, well, I'm always gonna go to the leader where this guy's located, even though I have multiple copies of the data on different nodes and in theory, I could read at these other nodes, but I always wanna do my read on the leader to make sure that I'm reading the most consistent or up-to-date version of it, because maybe these other nodes have not seen the latest update yet, because in a raft, you only need a quorum, you don't need to have every node agree, which is different, two-phase commit, you need everyone, this one, you always need a quorum.  So, to handle that, all the reads are always gonna go to whatever the leader node is for an ID. And to avoid having every read query go to just a one node, that's why we have this table up here to tell us which one's the leader and we're gonna distribute that across multiple nodes, so the reads can then be scattered across multiple machines. Again, it's just doing the consensus protocol, the replicated writes that we talked about in the semester. The hard, so the core concepts aren't mind-blowing or dramatically different than what we've already talked about, the hard part is the engineering, making this actually work. And that's what they're spending all their time to make happen, so that you don't have lost rights or missing updates and things like that. Okay, all right, so let's finish up. So, hopefully I conveyed throughout the entire semester that I love databases, they're awesome. You're gonna hit them throughout the rest of your life and so what hopefully this course has provided for you is the ability to say something's running slow in our application because it's the database. What kind of database system am I running on? What does my data look like? What does my query look like? It allows you to now make an informed decision about how these systems work and whether you're choosing the right database system for your given application or workload environment, right?  Like Excel is a database. So if you're using Excel, you're using a database. So, and the other thing I would say also too that's super important is I would avoid premature optimizations in deciding what database system to use. Always start with something that is maybe just good enough of what you need right now and don't worry about potentially scaling up to millions of users in the future. And that was sort of my MongoDB example.  I'm gonna have a million customers. Of course I want to distribute a database that can scale out.  Maybe you buy some better hardware and scale up a little bit more as your domain increases, but don't worry about bringing in a distributed system because that's gonna bring more complexities that you maybe need right now. And you should focus on what makes your app, you know, what you need for your application to succeed. So people also ask me, what database system should I start with if I'm building a new application? My interest is Postgres or MySQL. For, you know, 99% of the applications that's gonna be good enough because what'll happen is if your application does blow up and you do have a lot of customers, what are you gonna have? Money. So now you can go pay me to come tell you how to scale out your database, right? Or one of my students, right? So avoid, you know, introducing new complexity by bringing in a, you know, going overboard with a database system maybe you don't need. Like maybe starting with Amazon RDS would be a good choice.  All right, any questions? Yes? Boom, okay, all right. So, yes. So, I did get a, my test results came back last week. All right, this is it. It's mine. There's no, oh. So, the probability that I'm the father of my child is 99.9999998%. So, there is a 0.0000002% chance that it's not mine. But at this point, I've accepted my fate and it's definitely my kid, okay? Yeah, no, it's, yeah, no, it's mine. All right, all right, guys. So, I'll see you at the final exam on Monday and then the, I'll have office hours on Friday. And then again, this is the last class with DJ to the top table. So, again, round of applause for him being with a tire spacer, okay? All right, guys, take care. Good luck with your classes. Oh, yeah, coming through with my shell and crew Two cent for a case in me, St. I's crew In the mix of broken bottles and crushed up cans Met the cows in the jam, oh, I'll try, oh He's with St. I's in my system Crack another unblessed Let's go get the next one, then get over The object is to stay sober Lay on the sofa Better yet, damn it My reason why I'll be Tim, stressed out Can never be son Rick and say jelly Hit the deli for a part one Naturally blessed, yes My rap is like a laser beam The pawns and the bushes St. I spent like a king Crack the bottle of the St. I Sipping through gold, but you don't realize The drinking ain't only to be drunk You can't drive, keep my people still alive And if the St. don't know you're from a can of pain, pain


This talk is on Haloinfinity or proof-carrying data from additive polynomial commitments. I am Ben Fish from Stanford University and my co-authors on this work are Dan Bonet, Justin Drake, and Arielle Gabison. Proof-carrying data is an extension of non-interactive proof systems, so let's begin by briefly reviewing non-interactive proof systems. At a very high level, a prover sends a proof to a verifier that helps the verifier check some claim. The reason why this is useful is there is typically some asymmetry between the prover and the verifier, either in terms of computational resources or knowledge of secret information. One flavor of a non-interactive proof is a non-interactive zero-knowledge proof. Here, the prover wants to convince a verifier that a statement is true without revealing some secret evidence behind the statement's truth. In other words, the prover knows a private input w to some program such that the program evaluates to 1 on this private input, and the prover sends a proof to the verifier. The verifier runs verification algorithms to accept or reject. Soundness says that it's infeasible to produce a valid proof if the prover doesn't know such a w, and zero-knowledge says that the proof doesn't reveal anything about w. When the proof verification is asymptotically faster than program evaluation, then we call this verifiable computation, or SNARTS, which stands for succinct non-interactive arguments of knowledge. Here, the proof should be small and fast to verify even as the program grows very complex, or the witness grows very long. Zero-knowledge, in this case, is an optional extra feature. IBC, incrementally verifiable computation, enables incrementally updating a proof of a computation's correctness as the computation evolves. Each proof attests to the correctness of the computation up until this point. Importantly, for IBC to be non-trivial, the cost to produce the next proof at the i-thederation given the local state should be cheaper than producing the proof from scratch, in other words sublinear in the depth, and should not require the previous local inputs, which may have been discarded. IBC has been important for recent real-world applications, including to blockchains and certificate transparency logs. Although not quite the standard way of presenting IBC, I like to describe IBC as also optionally passing along a separate prover state in addition to the proof and the local computation output. This is not needed to verify the proof, but helps the prover to produce the next proof, which is why it makes sense to separate these components. Classical constructions of IBC via proof recursion did not utilize any extra prover state, but newer constructions such as in this work do. Proof carrying data, or PCD, generalizes IBC to any distributed computation where the nodes of the computation are organized as a directed acyclic graph. So IBC is a special case of proof carrying data corresponding to a path distributed computation. Similarly to IBC, we can separate the proof components passed along the edges of this computation into a proof and a prover state. The first is the actual proof that can be verified, and the second component helps the next node of the computation produce a proof. We can also have separate efficiency requirements for the two distinct proof components as they're used for different purposes, and as their requirements for each of them change based on the application. Classical constructions of PCD or IBC from Snarks used an idea called proof recursion. The high level concept is that the incremental proof pi i plus one is a proof for a witness consisting of the previous proof pi i, the previous output z i, and the local input y i plus one. The program checking the witness is checking the Snark verification of this previous proof pi i, and also checking the local computation. So the proving time is proportional to the size of the local computation and the size of the Snark verifier. Now I'm skipping some technical details of how the program works, which enables it to reference its own verifier. In a bit more detail, here is how it would work for a pre-processing Snark, which is a Snark that has a pre-processing algorithm that can produce compact proving and verification keys for a given program. Programs represented as having a variable public input x, which will be an input to both proof and verifier, and a variable private input w capturing the witness. So the recursive program on x w parses its public input as a variable verification key, the index i plus one, and the local output z i plus one. It parses w as local input y i plus one, the previous output z i, the previous proof pi i, and it runs the Snark verification algorithm on the verification key, the previous index, previous output, previous proof, and also checks the local predicate f. The actual verification key that we pass to this program will be the actual pre-processed verification key of the program, but is referenced as a variable inside the program since we don't have it yet. Halo is the first PCD based on an underlying proof system that has a linear time verifier. The classical method of constructing PCD solely from proof recursion would not work with a linear time verifier, but Halo manages to use proof recursion in a way that does not include the full verifier in the incremental provers program. This work generalizes Halo for a broad class of proof systems beyond the specific one used in Halo paper. There are two important recent papers related to ours that I'd like to mention here. The first is BCMS 20, which formalized and generalized the Halo method, identifying an underlying necessary property of argument or proof systems called an accumulation scheme, and BCMS 20, which further generalized the Halo method to work with even non-succinct argument systems that have something that they call a split accumulation scheme. Now, while these works focus on defining the abstraction of accumulation schemes for proof systems and how to use them to build PCD, our work focuses more on properties of polynomial commitment schemes that lead to proof systems with accumulation and split accumulation and also gives generic constructions of accumulation. Let me briefly review what polynomial commitment schemes are. A polynomial commitment scheme provides algorithms that enable producing a small value committing to a polynomial of bounded degree over a finite field, and then later to provide proofs of the valuations of this committed polynomial at chosen points. Although not a strict requirement, ideally these proofs should be succinct or sublinear indeed and efficient to verify, also sublinear indeed.  The normal commitment scheme should satisfy the usual definition of committed binding to its input domain, which are polynomials over Fp of degree at most d, and the non-interactive proof should be an argument of knowledge, of an opening of a commitment to a polynomial, such that the polynomial evaluates at z to a point y. A polynomial interactive oracle proof is a public coin interactive proof between the prover and verifier, where the prover sends polynomials to the verifier that the verifier accesses through oracles and uses those oracles for polynomial evaluation. It checks some equation of the responses that depends on the program, and the polynomials of the prover sends are dependent on the prover's witness. The protocol overall is a proof of knowledge of this witness. To compile this to a concrete interactive proof between the prover and the verifier, and also to compress the size of the communication, the prover instead sends commitments to the polynomials, and replaces the oracle polynomial evaluations with evaluation proofs using the polynomial commitment scheme. Finally, this can be transformed to a non-interactive proof using the standard Theatres-Chemier transform. An additive polynomial commitment scheme comes with a defined addition operation that enables taking linear combinations of commitments. The linear combination should itself be a valid commitment to the linear combination of the underlying committed polynomials. So there should additionally be an algorithm that derives an opening hint for this linear combination from the opening hints of the input commitments, which enables producing eval proofs for the linear combination. Now, it is always possible to trivially define this addition operation. For example, it could simply be the formal addition of the commitments. It is non-trivial when the addition operation is actually compressing, or there is a set of commitments to polynomials of bounded degree that is closed under addition that has polynomial bounded size. It is in this case that we call the polynomial commitment scheme additive. Linear combination schemes for polynomial commitments generalize additivity. Perhaps there is no compressing addition operation as previously defined, but there is a protocol between a prover and a verifier which outputs a succinct commitment to the linear combination with a proof of correctness to verifier checks. The security property of this linear combination protocol is that running an evaluation proof on the output C star is an argument of knowledge for openings of both C star and the formal linear combination of the input commitments to the same polynomial f. We call a linear combination scheme efficient if the lincombine protocol has a verifier that is sublinear in the maximum degree of the input polynomials. Note also that in our example the lincombine protocol takes just two commitments, but it could also take a linear combination of multiple commitments at once. So to summarize a non-additive polynomial commitment scheme construction, which may have no compressing add operation, could still have an efficient linear combination protocol with a succinct output. The result of our work stated informally is that we can achieve proof carrying data from any polynomial agreement scheme with an efficient linear combination scheme where the proving time inherits the same efficiency as the polynomial agreement scheme roughly on polynomials of degree of the size of the local predicate plus the size of the linear combination scheme verifier. If additionally, the polynomial commitment scheme is is additive doesn't just have an efficient linear combination scheme, then the PCS proof size is also inherited and there is no need to transfer prover states in the proof carrying data. Towards showing this result, we introduced two types of aggregation schemes for polynomial commitments, one that we call public aggregation, which is related to the BCMS idea of accumulation and the other which we call private aggregation, which is related to the BCLMS notion of split accumulation. Private aggregation is a public coin interactive protocol between a prover and a verifier, which aggregates commitment evaluation tuples. An evaluation tuple is a commitment and a claimed point on the committed polynomial. For simplicity, let's define the protocol for aggregating just two commitment tuples. But this generalizes to aggregating more than two. The verifiers inputs in this case are two commitments and two claimed points on the committed polynomials. While the prover additionally has the opening hints of the input commitments as private inputs to the aggregation protocol. The output of the aggregation protocol has a public component received by both parties, which is a new evaluation tuple in a private output just to the prover, which consists of an opening hint for the commitment to C star, and the polynomial F star that C star commits to. The security property of this aggregation protocol is that the composition of running the aggregation and subsequently running the eval protocol on the output tuple C star X or Y star is equivalent to running eval on both input tuples. In other words, it is a proof of knowledge for both input tuples. Public aggregation is very similar, except the key difference is that the aggregation prover does not need to know the opening hints for the input commitments. Instead, it has eval proofs for each input evaluation tuple. Here, the prover and verifier therefore have the same inputs. Only the verifier does less work than the prover. The output of the aggregation protocol is a new evaluation tuple as before and an opening hint for this tuple. For efficiency, the verifier does not need to read the full output. In particular, it does not need to read the opening hint, but it should be possible to derive this from the protocol transcript. The security property is the same. I will sketch how we can improve the efficiency of PCD with proof systems built from polynomial equipment schemes that admit aggregation. So given a proof system for a program on XW with the structure that proofs are a tuple T rho A, where T is an evaluation tuple, C alpha beta, rho is a PCS evaluation proof for T, and A is an additional component of the proof. And the verifier is split into two parts. One is a succinct part, which is efficient or sublinear in the size of the program. And the other is the evaluation proof verifier, which checks rho for T. Now, the first step is to show how we can build an aggregation scheme for these proofs using the aggregation scheme of the PCS. The aggregation prover will aggregate proofs by aggregating the evaluation tuple components into T star with proof pi aggregation. And the verifier will check the snark verification component of each proof, and then run the PCS aggregation scheme verifier to check T stars correctness. So the high level idea of how we'll improve PCD is that the prover will produce separately a proof pi f for the local predicate and aggregate this together with the previous proof into the new proof. So this new proof pi two is a proof for a program that calls the aggregation verifier with the previous proof pi one and the local proof pi f and an aggregation proof as a witness. In more detail, the proofs that are passed along edges of the PCD have two components, one being a primary proof component, the other an aggregation output. We preprocess the local program f so that the prover can independently produce proofs of the local computation's correctness. The primary proof passed along the edges is a proof for the program recursively defined as follows, it parses its input x as a variable verification key and index a local output and an aggregation output. It parses its witness as a previous output, a proof of the local computation correctness, the previous primary proof pi i and previous aggregation value T star i and then an aggregation proof and it runs the verifier of the aggregation protocol on the aggregation proof and these proofs pi i pi f and the previous aggregation value T star i in order to check that the new aggregation value T star i plus one is correct. So we can think of each T star value as a value that accumulates the unchecked polynomial commencing eval components of all prior proofs in the chain, which is why this technique has also been called proof accumulation and the complexity of the incremental prover's work is proportional to the size of the efficient part of the proof system verifier v snark and the size of the verifier for the polynomial scheme aggregation. If we are going to use private aggregation instead of public, then the next incremental prover needs to also receive the opening for the evaluation table T star i and the evaluation top component of pi i passed along as a prover's private state. Importantly, this additional witness does not grow in size. It's the same at each depth of the PCD. So the main theorems in this work concern the efficiency of aggregation schemes for polynomial commitments. A public or private aggregation scheme is said to be efficient if the aggregate protocol verifier is sublinear in the maximum degree of the committed polynomials. So our first theorem shows that every polynomial commitment scheme that has an efficient linear combination scheme also has an efficient aggregation scheme. And our second theorem is that every additive polynomial commitment scheme has an efficient public aggregation scheme. Both theorems are constructive. We show how to build an aggregation scheme from a linear combination scheme, which inherits the efficiency of the linear combination scheme. And we also show how to construct public aggregation for any additive PCS. I'll first show how to get private aggregation from a linear combination scheme. To simplify the presentation, let's assume the input evaluation tuples for claims about roots. It's easy to reduce the general case to proven claims about roots. And it's also easy to generalize the protocol that I'll give to aggregation of more than two commitment eval tuples. So the prover begins by defining the zero polynomials zi of x is equal to x minus xi and z of x to be the product of z1 of x and z2 of x. The verifier can do the same. The verifier sends a random challenge row. The prover constructs this quotient polynomial z2 f1 plus row z1 f2 divided by z of x. Note that both z2 f1 and z1 f2 have roots at both x1 and x2. It commits to this and sends it to the verifier. The verifier responds with another random challenge. And the prover constructs this polynomial g of x is equal to z2 of r times f1 plus row z1 of r times f2 minus z of r times q. This is defined such that if done correctly, g will have a root at r if the claim is true. If the scheme is additive, the verifier can homomorphically derive a succinct commitment cg to this polynomial g. But more generally, we can use the linear combination scheme in order to produce succinct commitments to g. The output of the prover is the commitment c star g, r and zero, and the opening of g. And the verifier's output is just the commitment. If the prover and verifier subsequently run the evaluation protocol on the output double c star r zero, then this turns into a batch evaluation protocol for the original claim. So this protocol builds on the classical one-round protocol to batch proving that multiple committed polynomials have a common root by opening a random linear combination of the commitments at this root. And the knowledge extractor in that case is based on the invertibility of a Vandermonde matrix. But to batch prove multiple committed polynomials at different points, the protocol here involves one more round as shown. And the knowledge extractor ends up being based on the invertibility of the Hadamard product of a random Vandermonde matrix with a square matrix of non-zero field elements. Next, we'll show how to build public activation for additive polynomial commitment schemes. An important building block for this is a succinct proof of knowledge protocol for pre-images of a homomorphism from integer vectors to an arbitrary abelian group. The protocol we described for this is a generalization of the bullet proofs protocol depicted here. Now I won't walk through the details of the protocol, but the verifier's final check is checking that the integer x prime times the homomorphism applied to an integer vector u is equal to the group element y prime, where the integer vector u is the coefficient vector of this polynomial which is defined from the transcript challenges in the protocol. So it's something the verifier can check on its own because u is publicly derivable from the protocol transcript. A critical observation that comes out of our analysis of the security of this protocol is that the verifier doesn't need to explicitly derive the vector u and check the evaluation of the homomorphism on u, which is a linear time part of the verification, if instead the prover provides any proof of knowledge of some pre-image of y prime. Now you might wonder why this is helpful because the goal is to construct a proof of knowledge of homomorphism pre-image in the first place. Repeating the protocol on u instead of having the verifier check u directly, obviously wouldn't reduce the verifier complexity of the protocol here, but this gives us a tool for public aggregation. The key idea being that we can think of this protocol as a reduction from proving a claim about a hidden pre-image x into a claim about a publicly known or derivable pre-image u, which can be extracted later by another prover just from reading the proof transcript. So we'll apply this sub-protocol as follows. First we'll need to do a slight compilation of an additive polynomial increment scheme into one that can be publicly aggregated. The new commit star must implement a homomorphism from integer vectors to g. This is often already the case, but if not we can define a new commitment algorithm that takes linear combinations of commitments to the monomials. And the new eval protocol on an evaluation tuple Cxy will work as follows. So first we define a new homomorphism Hx of f of bold f here denotes the coefficient vector of the polynomial which outputs two components versus the commitment and then the evaluation of f of x y. It then runs the homomorphism pre-image proof for the statement that Hx of bold f is equal to cy to get this integer vector u defined by on the previous slide and two values C prime and y prime such that Hx of u is equal to C prime y prime and then it runs eval on the evaluation tuple C prime x y prime. So notice u is public it can be derived from the HPI proof transcripts and so this reduces an eval instance with a private witness to an instance with a public witness. So finally if we're given eval star proofs for input tuples C i x i y i each of these contains an eval proof for a new tuple C i prime x i y i prime with a public witness u i derived from the proof transcript which enables the aggregation prover to run private aggregation, deriving these witnesses from the proof transcripts to reduce to a tuple C star x star y star with a public witness u star and opening an open star derivable from the transcript. So a major difference from the original halo is of course that the original halo was for a specific polynomial pigment bullet proofs and this is much more general however there are also mechanical differences beyond direct generalization and minor technical differences that it does not involve the verifier testing u of x at a random point but a more important difference is that the commitment function H does not need to be a collision-resistant homomorphism whereas the original halo relied on the collision resistance of the Pedersen hash. So in general the commitment function of course needs to be a binding commitment to polynomials but that is a weaker requirement than being a collision-resistant homomorphism over the integers.


I need money. And I'm not pretty enough to be a cosplay model. So I made this torture machine that my viewers can control so I can exploit them for money. Oh that's so painful. We built different torturing methods, but not one person cared about any of them. All they wanted was the taser. I can't control it. Torturing me you'd have to donate money to the stream. One dollar equals one second of torture. And after about an hour of pain and suffering while trying to play video games, we made a hundred dollars. I am now rich. Thanks guys. Want to see a part two with a more powerful taser? Check out the YouTube channel and let me know in the comments.


Super recognizers are individuals who have exceptional facial recognition skills. They are able to identify people from photographs or videos with greater accuracy than average people. A team of researchers conducted a study to determine if super recognizers could be selected from a larger population of police officers. The results showed that super recognizers outperformed other participants on several facial recognition tests. Furthermore, the researchers developed a selection process to identify super recognizers within a police force. This article was authored by James D. Dunn, Alice Taller, Richard the First Kemp, and others.


Hi and welcome to nursing school explained in this video on aneurysms. Now aneurysms can occur in any kind of blood vessel, but the most serious ones that we usually hear about are ones that occur either in the brain, so cerebral aneurysms or in the aorta, whether that's the thoracic or the abdominal aorta. And an aneurysm in general, what that term means, it's a permanent and localized outpouching or dilation of a blood vessel. So I've drawn out some graphs here so that you can kind of see what that means. Normally in a blood vessel, the blood flow just goes straight through as indicated in red here. When that blood vessel wall becomes turns into an aneurysm, then there are two different forms, which is what's called a fusiform aneurysm, where the vessel wall becomes weakened and then it kind of forms this outpouching here. And then when the blood flows through, it doesn't go straight anymore. It kind of gets a little bit more turbulent here. Or the other type of aneurysm is a secular aneurysm, where the blood vessel wall kind of builds this sac-like protrusion here that then again causes the blood flow to go through and become more turbulent. What happens then because there is so much pressure because of this turbulence, that the intima of the innermost layer of that blood vessel can become torn. And recall that there are several different layers that make an artery. And so when that gets torn, the vessel wall here becomes weaker and weaker. And then eventually, this could actually burst.