Transcription
Hello everyone. Welcome to the first lesson on distributed systems and system design from Vladaten. So, before we design a system consisting of many components, right, we need to understand what is happening in the most important component, namely storage. So, this and all subsequent lectures we will talk about storage and we will talk within the scope of just one node. Just one node. And then we will figure out how to distribute it, how to replicate it, how to shard it, what else can be done there. We will talk about consensus algorithms and all sorts of other things. But first, let's figure out what is happening with one node. What is happening with one node. That's what we'll talk about. I'd like to start with this. Recently, DataDog bought the open-source database Neon for 1 billion. For 1 billion. If we look, what is Neon? What is Neon? Ne is a serverless PostgreSQL that can be scaled, branched, and so on. Okay. But we have, for example, Yugabyte, which is also a serverless PostgreSQL. And every year, tons of deals happen. Tons of deals happen that are related to databases. For example, for example, for example, for example, please, here, here new databases have appeared. Someone bought someone. Funding of 10 billion, 8 million, 8 million, 9 million, 12 million, 24 million has occurred. Recently, there was news that Databricks bought someone for 250 million. In general, something is constantly happening in databases. And you want to understand, what is the money being paid for, why does it cost so much, why does it cost so much. But like, we already have the conditional PostgreSQL, I don't know, MySQL, why do we need another database, another database, another database? And to answer these questions and so that next time you choose some new fancy solution for yourself, right, or see some new article on Hacker News about a new database that solves all your problems, you can open their landing page, open their offering, and read what they are actually offering you. For this, we need to understand what is happening in one node. So, let's first think, why do we need DBMS at all, that is, database management system or in Russian, a database management system. Why can't we just store everything in files? Let's just store everything in Excel, right, and that's it. We just store everything in Excel, and DBMS was invented and so on, because DBMS gives us key functionality that would be difficult to implement with files, right? For example, if it were files, we would write our own program for each file on how to parse it, say, CSV. If the schema conditionally changed, we would have to rewrite the program that parses it, right, if the format changed, we would also have to rewrite it. A database management system gives us data independence, meaning we don't depend on how our files are stored. That is, for us, there is conditional PostgreSQL. We put data into it, we get data from it, how it stores it, how it arranges it in directories, how it breaks files into pages. None of this interests us. We know that we have such an abstraction, a data store. We put data into it, we get data from it. Next, what does it give us? It gives us concurrency control. What is meant by this? When several users do something simultaneously, when there is some transactional workload, everyone starts trying to grab the same attribute, change it, how do we resolve all this correctly? There is a concert, I don't know, Travis Scott, everyone is buying tickets, who to give a ticket to, who not to give a ticket to, what to do with it. That is, a database management system can take some of these problems away from us. Or tell us explicitly that there is a problem here, you need to solve it somehow, right, with concurrent access. In the case of files, 10 people are editing one file, then how to save it, how to save some revisions, what to do with it, how to merge it all later. A problem constantly arises, a database management system takes some of these problems away from us. We will talk about how it does this and what problems can arise later. So, Crash Recovery. What does it do? Our data is stored in memory. It is clear that the electricity went out. Boom, everything from memory disappeared. A database management system tries to protect you as much as possible from such cases. That is, it keeps some kind of recovery manager, it keeps some kind of write-ahead log, which will save this data to a persistent disk for you. And then the next time you start up, it will roll back to some valid state, right, and you won't have half-finished transactions, for example. It also gives you Security Access Control. That is, for example, you can view this part of the database, you cannot view this part of the database, a junior project member comes, they cannot change the schema, this person can change it, this one can view, this one cannot view. All the conditional RBAC, right, a database management system can also provide us with security access control. Let's look at the architecture of a classic, conditional, relational DBMS, right, and try to invent our own. But how will we invent it? We will not invent it from scratch, but we will rely on existing solutions. And when we get stuck somewhere or something is missing somewhere, we will peek at how it is done elsewhere, how it is done in real systems. So. That is, once again, we are not building now, that is, it will not be the case that you watch this lecture and can build your own storage component from scratch, but you will know what moving parts there are and how they all fit together into the overall puzzle. Let's look at what architectures exist. So, the architecture of a classic relational database management system can be represented like this. What do we have here? We have SQL commands. SQL commands come to us from our application, or from the command line, from anywhere. So, SQL commands come to us, they go into the Query Evaluation Engine. So, we will talk about each of these components separately. They go into the Query Evaluation Engine. What happens there? Query parsing happens there. Then this query is broken down into relational expressions. And then plans are built from these relational expressions, equivalent plans are compared, and the one that is most optimal is chosen depending on the data statistics and how many operations it will iterate through. We will also look at this later. And we say: "Here, you need to execute this plan." Then this plan works. It uses some methods, which, for example, might pull an index or know that this will be stored here, this will be stored there, this can be used. In parallel with it, concurrency control, transaction manager, log manager work, which monitors which transactions are currently active, which transaction, for example, if it's some MVCC, what versioning, who can see which versions and so on. Or if it's some locking, who currently has a lock on what. The recovery manager keeps a write-ahead log, which writes such data, such changes, such changes, such and such changes have occurred and saves them to disk. We will talk about all these components in more detail separately in future lectures. So, we have a buffer manager, which moves data from disk to memory, and a disk space manager, which is responsible for, roughly speaking, how my bytes are arranged on disk. And the data itself is in the form of index files, data files, and system catalogs. So, this is a classic relational database management system. Let's look at what other options exist. There is, for example, this option, which is done like RDB. So, they have three components. These are Gateway, Executor, KV. And each of these architectures is divided into layers. And each of these components performs the role of several layers. For example, KV Storage. That is, it handles how we store bytes, how we correctly handle MVCC, how we arrange all this, how we sync all this. SQL Executor handles transactions, how to correctly distribute this transaction, right, if it's a transaction that involves multiple nodes. SQL Gateway is responsible for parsing this SQL query. So, for example, the same Neon, which, if you remember, there was news at the beginning, was bought for a lot of money, what does Neon do? Neon, conditionally, conditionally, what Neon does, it splits PostgreSQL into two components: compute and storage, right? That is, it deceives PostgreSQL, and PostgreSQL conditionally thinks that it works the same way it usually works. But in reality, no. In reality, under it lies conditional Amazon EBS, right, some distributed block storage, and PostgreSQL thinks it's working the same way it did before. How do they achieve this? They achieve this by intercepting this write-ahead log stream and storing and distributing it themselves in their custom storage, which they wrote, and with this, they can version it, for example. So, this is their main feature, branching and versioning, all thanks to this they can do it. We will also talk about what object storage looks like, right. So, the next one is TiDB. TiDB is also divided into several layers. We have conditional TiKV, which is actually LSM Storage RocksDB. Then each of these KV syncs with each other using Raft, and they form a cluster, to which we send our requests. We will analyze all these moving components so that next time you see something like this, or this, or this, you can understand what is written here, what is meant. Well, let's start from the very beginning. Let's start with storage. So, storage. Let's think, how do we arrange bytes? How do we arrange bytes? For example, I have a users table in my database, right? And what should I do? How should I represent this users table on my disk? Let's think about it. So, we thought, we thought, and we'll peek at the solution from InnoDB. So, InnoDB. What is it? InnoDB is one of the MySQL engines. What does InnoDB do? InnoDB, it's written here interestingly: table per file. That is, for example, we have a users table. The users table will be one file in a proprietary format, say, InnoDB. Okay. The table, say, Orders. Here's the second file. Let's take this idea with us. So, we have a users table. We have a users table, and this is a separate file. Okay. So, into this file, what do we want to put in storage? We want to be able to retrieve our records from this file. That is, someone will tell us: "Give me record number one from this file." And someone will add records to this file. For example, add 10, uh, I don't know, Vlad seven. Uh-huh. Okay. Now what do we do? Now what do we do? Now we need to think, where to write in this file, right? That is, we need to track where the end of the file is, where there is free space in the file, or if someone reads something and they both start editing it. How do we manage this file correctly, right? That is, should we put them one after another, or, I don't know, with gaps? What should we do with this? So, we will peek at an idea called paging. What will we do? We will break this file into blocks, into pages, where each page will have a fixed size. For example, 4 KB, 8 KB, 16 KB. Some of you might think about OS pages. If you thought about OS pages, that's great. If not, that's also fine. But the size of these pages doesn't necessarily have to match the size of the operating system. So. And the database understands better what page size will be optimal for its workload. So. Okay. So, now we have pages. That's great. Now, when we want to retrieve some data, we can say, for example: "This data is located in the first, in the third page, at the second position. Please, retrieve it." We'll retrieve it like this, this, this. If someone else wants to retrieve it, and we're doing something with it, we'll know that you'll have to wait. Or, someone took these three pages, and someone needs these other pages. We know that this page is already there, and we can, roughly speaking, share it, for example. Nice. Now we have some logical unit to work with. Now let's think, how do we write data to each page? How do we store data in each page? So, this is already interesting. Here's our page, right? That is, the file consists of pages. Here we look at one page. Here's our page. What do we need to store in it? Well, probably, probably, we need to store some header. Some header where we will track, for example, the checksum, check if the page is broken, not broken, when we moved it from memory to disk, from disk to memory. What else do we need to look at? We need to look at something related to some free space. Is there free space, when does it start, where does it end, and so on, and so on. Plus some other points, but for now, I think we'll stop here. Now, suppose all my data, right, all my records that I send to the database, like "write 10 Vlad 7", they are of fixed length, right? They are of fixed length, for example, 10 Vlad 7. They are of fixed length. Then how do I store them in a page? How do I store them in a page? Let's say they all weigh 32 bytes. Well, then, in principle, in principle, I can store them one after another in a page. I can store them one after another in a page. I put one record, I put the second record, I put the third record, I put the fourth record. Seems all nice. Now, if someone wants to ask: "Give me the fourth record." Yes, the header size is fixed, the size of one record is fixed. We can immediately give them the fourth record, conditionally, here, take it. Okay, that's great. What problems can arise? Problems can arise when, for example, some record is deleted here, and we have free space. That is, we need to track here, for example, that this is the next free space, there is free space here, and track from it the next free space, right? And the sequential number somehow, conditionally, might get messed up. Now the fourth one is actually lower. We'll have to walk a bit. But walking from record to record is not so difficult for us. Why? Because it's of fixed size, and we can just skip 32, 32, and get the next, next, next, next record. It seems okay in principle, but it's clear that we face such a problem, right, for example, storing this takes me, I don't know, how much, let's say 4 bytes for storage. This takes me, I don't know, 8 bytes. But what about this? What about this? What about this? This is already interesting. So, we can always give a fixed size with a margin for this, right? We, for example, say that this always weighs 255. Then, if I have "Vlad" written here, all the rest is unused space, well, we just waste it. We simplify it for ourselves by making all records fixed length, but then we waste all this space uselessly. It's clear that this is not the best option, but if our records start to be of different lengths, different lengths, then we won't be able to just jump from one to another, because one record is this long, another record is this long, a third record is this long, this long, then another long record, and we can't immediately jump from one record to another, for example, to the fourth position like this, because they are of different lengths. Plus, we also need to somehow understand when this record ends, and when another record begins? Or within one record, we even need to understand when this attribute began, and another attribute ended. And it is precisely with such moments that we will peek at how this can be encoded. This can be encoded as follows. So, look, we already have, that is, something similar is conditionally done by Protobuf. So, we already have a schema, right? We are still in a relational database. We have a schema. We know that here we have a conditionally variable-length ID. Here we have a variable-length last name. Here we have a variable-length department. Here we have a fixed one. We know this from our schema, roughly speaking, how each record looks. Now, what do we do when it's variable length? We say, here we store a fixed header and tell it that if you want to find this variable-length attribute, go to the 21st byte and read 5 bytes. If you want to find this one, go to the 26th byte and read 10 bytes. If you want this one, go to the 36th byte and read 10 bytes. This one is stored right here because it's fixed size. Okay. Okay. Now we can, for example, immediately retrieve the conditional third attribute from this record, because we know it's variable length. There will be three fixed headers. Here's the third one. We go and read it. Not bad. Already better. Already better. At least we can now understand where one attribute ends and another begins, where the third, the tenth. At least we can somehow distinguish one record from another. But the problem is that they will lie there, they will lie there, and we can't immediately take the fourth one, right? Well, we still can't immediately take the fourth one because they are all variable length. Plus, it might be that some attribute, some attribute, simply, roughly speaking, doesn't fit into our page. It's just larger than the page size, right? You decided to store something interesting in it. I don't know, some huge JSON or, uh, a movie encoded in Base64, decided to store it. We solve these moments with Overflow Pages. That is, in the original page, we will simply refer to it, saying, okay, if you want this data, it's stored over there, go and get it. That is, it can refer to an overflow page in PostgreSQL. In PostgreSQL, this is called TOAST (The Oversized-Attribute Storage Technique). Precisely for this. Precisely for this. Okay. We've also somehow solved this problem, but now we have a problem when they are of different lengths, and we want to conditionally retrieve from this page, right, this is, say, the third page, we want to get the second record from the third page. We unfortunately cannot answer this question so quickly. For this, we add another layer of indirection, right? So, what do we do? What do we do? We take a page. We take a page. It has a fixed header. And then for each record, we also make its own header. Fixed length like this. One, one, one, one, one. And each of these headers, the headers grow from the beginning to the end of the page, and from the end to the beginning of the page, our data grows. And we can say: "This header points here to this record. This one points here. Say, this one points here. This one points here. And now, when we are told: 'Give me the fourth record from this page', we can immediately, this is fixed length, each of them is fixed length, we can immediately find the fourth one and point to it. Here it is, take it from this page. And exactly the same approach, exactly the same approach is used by PostgreSQL. Exactly the same approach is used by PostgreSQL. Here you go. So, we have each, each page has its own, where the checksum is stored. LSN is for the write-ahead log version, flags. Lower, upper. Cool. What is this? Lower, upper is where the headers end, where our records themselves end. What can we do with this? Check how much free space we have, right? That is, they grow from here, these grow from here to here. And we can check how much free space is left, whether it's worth writing something to this page. PostgreSQL uses exactly the same approach. Please. So, we've invented PostgreSQL. Plus, each record header, each record header has its own fields, its own header, where we store, for example, for MVCC, which transaction it can, which transaction it cannot. A link to the next record, right? Because MVCC stores multiple versions of the same record. And other points that we will look at. And also, the point is that the page itself can also have a header. It's fixed size, 24 bytes, and it already contains the checksum. Well, we've seen this in another picture. Okay. Super, excellent. Super, excellent. Now another issue might arise. Now, how do we get the fourth record from the third page? Please, every day. But another issue has arisen: we remember that records are of variable length, right? And then this situation can occur. Here was a record, here was a record, here was a record, here was a record. I deleted this, I deleted this. I want to insert this. And in principle, there is space for it, right? There is space for it, in principle. Well, say, if this weighs eight, this weighs, there is space for it. But what will we have to do? We will have to delete this, delete this, and then move them together, right, move the free space. That is, move this one to the right or this one to the left. We'll have to do something with it. But when we do this, what will we have to do? We will have to reassemble all these pointers. And what if someone is working with this data? Then we will have to lock all this and make sure that no one is reading or modifying it in parallel. A problem. And it is a problem. And it is precisely with such a problem of dead tuples that Vacuum deals with. Vacuum is a conditional garbage collector in your storage, which, well, "vacuum reclaims storage occupied by tuples in normal PostgreSQL operation. Tuples are deleted or obsoleted by updates are not physically removed." That is, we don't delete them, but we just mark them as needing to be removed. And the next time Vacuum runs, it removes them. What does it do? And then, depending on how you tune it, Vacuum either writes all of this to a new page, or moves things within the same page. You can read more about this separately if you are interested. Okay. Great. So, in principle, we have more or less figured out all the issues that can arise within storage. We have more or less figured them out. The only thing we haven't figured out is what alternatives exist, right? But we will look at alternatives later. We will look at them later. So, what else? You may have often heard that there are row-oriented, column-oriented, right? Or they say columnar databases, columnar databases. I will show you with an abstract example why, for example, there is a separate subclass of databases that work with columns. And what does this give us? Let's take this example, remember how they are stored now. Here we have a page, we have a page. If you thought of ClickHouse, it's close, but ClickHouse uses a slightly different type of storage. But we are taking an abstract example now. Here I have a page, it has records. It has records. And the records are stored like this: 10 Vlad 7, right? Say, 7 is attractiveness on a scale of 100. And I have other records, say, some Oleg 5, I don't know, some Igor.
90, so there it is, blah blah blah blah blah blah. I also have many, many, many millions, millions of records. Here. And what do we want to do? We want, for example, to count like this, take and count some sum, some median, I don't know, average, multiply them somehow. We want to do something with these numbers, right, to calculate some statistics. And I have very many such records, billions, millions. Then what's the problem? Let's remember how all this is stored. To read this, I'll have to dig it all out of PG like this. Yes, I'll have to dig out the page, and then dig out this from the page. But essentially, I only need this number. And why did I take all of this? Why did I take all of this? I don't need it. And here I took too much. And here I took too much. And here I took too much. And here, and here, and here, and here. And here I took so much extra. Although in fact, I'm only interested in this. How can I solve this problem? I can solve this problem by reorganizing myself too. And now I will store all attributes together. of one type, blah blah blah blah blah. And here is the ID. Now I store all attributes together. And now, when I need, for example, to calculate this, I will dig them out, and they will all really be lying next to each other. What else can I do now? Since these are all attributes of the same type and they lie next to each other, I can already do some kind of compression, some kind of encoding here. Plus, I can also use vector operations. I can do parallel operations, if it's a sum, yes, then the sum is conditionally commutative, I can add this to this in parallel. That is, I can do various other optimizations. And when I dig out the data, I will actually dig out only what I need, without these extra attributes. Okay. for counting something. And this is awesome. And this is awesome. But, but, but when a problem arises, the problem arises when we need to assemble this record back. That is, when, for example, I want to know, who is this? I see that it is in the fourth position here, right? I have to find who is in the fourth position here, who is in the fourth position here. Conditionally, if something happens there, maybe lock them all and then reconstruct this. Assemble it like this. Ah, suppose it is compressed here, it needs to be uncompressed and output, right? That's why we conditionally have an analytical workload and a transactional workload. And that's why for an analytical workload, one type of storage is suitable, and for a transactional workload, another type of storage is suitable, because how the data is stored directly affects how we work with it. Okay. I hope this point has become clearer to you. That is, column-oriented, we store all attributes next to each other like this. Row-oriented, we store a record. Good. Good. So, we've more or less figured out this data file layer. Now, what's interesting? Now there's some system catalog. What is a system catalog? What is a system catalog? Hmm, I need to think. I'm pretending to think. So, the system catalog is essentially a directory that stores metadata about where everything is located. For example, this table is conditionally stored in PostgreSQL in this folder, in this directory, in these files. This table has this schema. These indexes are attached to this table. This table can be read by this, this, this user. Or this index is located in this file, this is located here. So, metadata about where your data is stored, how much free space there is, how many records are stored. All this metadata can be stored in this directory. Good. Good. So, now, interesting things. Now, interesting things. Look, we need to move data from disk to memory. We need to move data from disk to memory. Why do we want to do this? Why do we want to move it from disk to memory? As an analogy, for example, with your application, a regular web application that you are developing, right? You usually add some kind of cache like Redis and so on, but here, if you add a cache, you also have various problems with invalidation and so on. Here we will also see something similar. Well, one of the reasons, for example, is that for 2025, according to Planet Scale numbers, the link will be provided, to get something from memory. A round trip is 100 nanoseconds. Getting something from disk is 50 microseconds. To give you an idea of the scale, how it happens. So, we are talking about this order of magnitude, you understand? So, by the time you get something from disk, in memory, it's already completely, already, already an order of magnitude ahead. We've already finished everything, already gone home, but memory is less, and memory is volatile. What does volatile mean? It means that if, conditionally, the electricity goes out, which often happens in Uzbekistan, then all the data from your memory will disappear. Therefore, we need to work with it cleverly in memory, right, but not forget to save it to disk. Don't forget to save it to disk. And it is precisely for these moments, for these moments, that the buffer pool will be responsible. The buffer pool will be responsible. So, what can the buffer pool do? The buffer pool can pull pages from disk into its memory. It can also perform what functionality? For example, it sees your request, right, that you are doing some kind of select, and it can prefetch pages that you will need in advance. Or it sees that several requests want the same page, it won't push it out of the buffer pool, but will conditionally share it between them. Or, for example, a frequently used page, for example, a directory or an index root, it can take it and pin it. It can mark it as dirty, meaning that it needs to be, this depends on the eviction policy. We will talk more about what needs to be done with it. It can store who has locked it, who needs it now, that an exclusive lock is on it, a lock is on it. We will also talk about this later. So, the buffer pool performs not only the basic functionality of being just a cache. It also performs various such moments. But, but, but, but, it is understandable that, suppose, my database on disk has already grown so much that it occupies, I don't know, terabytes, but I don't have terabytes of memory. I have a limited amount of memory. Then the question arises: who to evict? Who to evict from memory? Who to evict from memory? Him, him, him, him. Who? I clicked in the wrong place. Him, him, him, him. Who? Who to evict? You can take the simplest policy. You can take FIFO. First in, first out. Okay, then we will first, for example, push in the catalog and indexes. We will also kick them out first when we have a regular select star or some kind of select scan. Bad. And there is another policy. There is a policy called. There is a problem on LeetCode. I recommend everyone to solve it. Or you can find it in my algorithm course. Just kidding. So, look, what is LRU? LRU is least recently used. It doesn't translate very well into Russian, but least recently used means the least recently used. The least recently used, or the one that hasn't been touched for a long time, roughly speaking, the one that hasn't been touched for a long time. For example, I have a cache of size three. I add 1. Okay. I touched it recently. I add 220. Okay, just touched it. I add 330. Okay. Just touched it. Now, when I want to add 440, I no longer have space in my cache. I have to push one of them out. Who to push out? I'll push out 10. Why? Because I added 10, 20, 30. And it turns out that 10 is the oldest one I touched. But if I now take and touch 10, right, 11, then I'll refresh it, like, I touched you, and then 20 will appear. And if I touch three, and then touch two, then who has become the least recently touched again, besides Vlad? 10. That's right. And now, when I add a new record, it will be pushed out of here. Okay? So, this is a cool policy. That is, conditionally, we will have some indexes that we will use frequently, or some popular table that we will use frequently. It will always be warmed up. But the problem with LRU is the so-called sequential flooding problem. What does this mean? Sequential flooding. To explain in simple terms, I had something here that I needed, right, then I would use it somewhere here with great pleasure, right, and use it here, right, I really need it. But here, for example, there is some huge select scan. A huge select scan that will calculate, I don't know, some sum of attributes, right, some kind of one-time value. But this select scan will be executed, and while it is being executed, it will start warming up, warming up, warming up, warming up, warming up, warming up. And it will turn out that they are all those who were recently touched. And these will turn out to be those who haven't been touched for a long time, and they will be evicted. Although they would be very useful here. This is the problem. You can also read about it. It's called sequential flooding. Nice, nice, nice, nice, nice, nice. Now, what have we understood? We have seen, so, how we store things on disk, right, how we move things into memory, warm up some catalogs that tell us where to look for what. But, but, but, but, but who comes to our storage and says that if I want to find this record, it is located in this page at this offset. Who is it? Who are you? Who is doing this? And in general, how can we solve this now? For example, we want to find something from a table with a specific ID or attribute. How can we do this? Well, we can dig out the entire table, iterate through it, and find what we need. Or we can use certain data structure mechanisms that will speed up this search, access to the data we need, or in other words. Spoiler alert, indexes. That's right. Think about what indexes you know. What indexes do you know? What indexes do you know? Okay, you've thought about it, so. But let's first clarify the basic terminology. So, what types of indexes can there be? Indexes can be clustered, non-clustered. So, what does clustered mean? Clustered means the index dictates the order in which records will be stored in files. Exactly, how they are stored, right, how they are stored in the index, conditionally. The order is dictated here as well. Non-clustered means when such an order is not dictated. For example, for example, for example, in MySQL, the NDB primary index is clustered, it will dictate the order in which files are stored. And in PostgreSQL, heap organization of files is used, and they are in random order. You have a primary index, right, which sets the primary key, but this primary index is only responsible for the unique constraint, so that you can distinguish one record from another thanks to it. One record from another, right, a conditional auto-increment, but it doesn't give us the order of records. Why do we need records in order, for example? Because if our records are in the order of the index, we can build a sparse index. What does a sparse index give us? Let's look. Here they are stored in order of IDs, right? We have dense and sparse indexes. So, a dense index maps one-to-one to records. A sparse index can map ranges. For example, here records are from 10101 to 3243. Here from 32343 to 76766. What does this give us? What does this give us? Thanks to this, we can make the index itself smaller and update it less often. But we can only do this when there is an order here. See, they are sorted by IDs. It's clear that if there is no order, then this range will give us nothing. There can be any random value here. Further, we can build a hierarchy of these sparse indexes, right, to further refine, but this is already a specificity. What is a secondary index? So, a secondary index is when you search by some other attribute. For example, I'm not searching by ID, I'm searching by, I don't know, by what, I'm searching by some computer science department, by some department where he works. I'm searching by salary, I'm searching by last name, something like that, right? So, if you conditionally have some primary key, and you are not searching by it, but by some secondary attribute, right, then you use a secondary index. So, okay. How can it be structured? It can be structured such that it either points to where to find this specific page, this record, right? But then what's the problem? Then, if vacuum works, then all indexes here will have to be changed. When they move, where who was located. What other problem is there? What other problem is there? Think. Or the second option, store a reference to the primary index. That is, we say: "This record, it is conditionally 151332343, this record is these, this record is these, this record is these." Then what's the problem? Then if the tuples in PG move somewhere, you don't have to update anything in your index, right? But you add a layer of indirection, meaning you have to go to the primary index later. Okay. So, some of the most popular indexes that can be named are hash indexes and B-trees. Let's look at hash indexes first. What is a hash index? To understand how a hash index works, let's look at how a hash map works. I advise you to watch videos on my YouTube channel or elsewhere, but let me explain briefly. So, you have some value X, you pass it through a hash function, it tells you where to put it, conditionally, in which bucket, right? Here, here, or here. Now, if, for example, it landed here, and there was already something there, what are the options? There's an option to chain them here and store multiple values, then what's the problem? If my hash function distributes unevenly, right, or the data is distributed that way, then it can happen that they all fall into one bucket, and they will be one after another, one after another. And then from the hash function, we get that it takes up a line, right, O(n), although we want to get it in constant time. What's another option? There's an option to do that if it's occupied here, right, let's write to the next bucket. But then there can be an order of addition, for example, such that everything was added not in its own buckets at first, and when people come to their own buckets, they will already be occupied, and they will start moving even further. There's an option to add a second hash function. There's an option to add, for example, extendable hashing. What does this mean? For example, you take a prefix and first choose based on the first bit of the prefix where it will go. To the first, second bucket. As soon as there's no space there, you take the next value in the prefix and split it into four. And then into eight. And then into sixteen. So, you always expand the prefix of where it will go. Okay. So, what is a hash function good for? A hash function is good when we want to find a specific value. A specific value. For example, I want to find computer science. Who works in computer science. Okay, we've attached a hash index to this attribute, conditionally. We passed it through a hash function. It will tell us: "Okay, these guys, these IDs 238 work in computer science. Nice. When does a hash index work poorly? A hash index works poorly when we need to find something like, who earns more than 7,000. Who earns more than 7,000? Because the order in which data will be placed by the hash function, right, no one guarantees us. No one guarantees us. And therefore, to find those who earn more than 7,000, what do I need to do? I will need to pass 7,000 through the hash function. Find, okay, these, these, these guys. 7,001, 7,002, 7,003, 7,004. So, each of these numbers will need to be passed and checked. What's the conclusion? When we need to precisely retrieve specific data, right, by a specific value, then hashing is super good. But when we need to retrieve ranges, then we have problems. Okay. So, the most common and universally used index, and the default index you always see, is the B+ tree. Let's talk about the B+ tree. Let's first look at how a B-tree works, and then look at how a B+ tree works. So, we will randomly add some values, right? I'll set a lower parameter here. We've randomly added them. Bam-bam-bam-bam-bam-bam-bam. Now, when I want to find 761, how can I do it? I see, is 761 less than 214? No, it's between 214 and 768. Yes, so I go down. Is it less than 719? No, it's greater. Yes, I go to the right, I get 761. 761. Bam, bam, bam, bam. Nice. I want to find 984. I also go to the right, to the right. I find it. And it keeps growing, growing, growing. Look, when an interesting moment occurs. I want to add 985. Here I have node 2. There's no space here anymore. What should I do then? To add it here, I need to split it into two nodes, distribute between them, and add a new pointer here. That I have another node with a new range. Let's look at this. Bam. But, but, but we need to remember that each of these nodes is also stored somehow. It is also stored somehow. So, conditionally, each of these nodes is, say, a separate page. And so, to perform this operation, I will need to lock this page, split it into two, lock here, update here, and do all of this. Okay, painful. Quite painful. Now I want to add 921. It will go here. And now I want to add 922. What will need to be done with this node? What will need to be done with this node? It needs to be split into two, redistributed. Well, when we split it into two, a new pointer needs to be attached here. There's no space here for a new pointer. So, it needs to be split into two. Then a new pointer needs to be attached here. And there's no space here either, so it needs to be split into two and a pointer attached here. And so, look, just adding 92 can cost us this much. 1, 2, 3, bam. Almost the entire tree from the root has been rebuilt. This is super painful. Remember that this is some kind of page, this is a page, this is a page, this is a page, this is a page, this is a page. All of this is now being rearranged like this. Painful, painful, painful, painful. But, but what does it give us? It gives us that when I want to find a specific value, I can find it in O(log MN), where m is the fanout, how many pointers come out of each node, right? So, in a binary search tree BST, we say it's log N, because we mean log 2 N, and here it's log MN, where m is the fanout, how many nodes come out of, and how many pointers come out of one node. Okay, this is painful. But now, when I want to find, for example, all values from 271 to 761, well, okay, I go here, take bam 271, bam 688. Then, unfortunately, I have to go up. Then I have to go down again. This is a bit unpleasant. This is a bit unpleasant. And also, if we look here, values are sometimes stored not only in leaf nodes, but also here. They are also stored here. This is even more painful. That's why we have a B+ tree for this. And all databases use B+ trees. B+ tree. Look, what is a B+ tree? Values are stored only in the leaves. At the same time, all values are linked to each other. What does this mean? I have a pointer to the neighboring node. And now, when I want to retrieve something from 176 to 429, I can go from left to right, bam, and get them all at once. Cool. This is cool. But what's the problem with this? When I add, for example, 388 here, it will go here. I want to add 389. What will I have to do? 1, 2, 3, 389. Here. Bam. Rebuild the tree again. But now, when we rebuild it, we need to track not only parent relationships, but also these pointers. They are also rebuilt. Look. Bam. This is, of course, more unpleasant in implementation, it will be much more complicated. I advise you to try. Okay. But now range scans are just taken and we can vacuum them up at once. Now, what is stored? What do I mean by what is stored here in the leaves, in the values? So, we have these options. In the leaves, we can store pointers, meaning this can be found in the 7th page, offset 2. Well, then when they move, we will have to update here too. Or, or it can be some kind of index-organized storage, where in the leaves, I store pages with values. Pages with values, right, okay, okay. We've seen this. So, what other indexes can there be? The pain of a B+ tree is that some operations are super painful, super painful, because to perform this operation, to add 393 here now, I will have to lock almost the entire tree to rebalance it correctly, to split these nodes correctly. Bam. So, we imagine that this is a page, this is a page, this is a page, this is a page, this is a page, this is a page. All of this will have to be locked because a modification will occur, right, and someone else might be working in the same tree, and everything will change for them. Therefore, we have to say: "Listen, I'm going to rebuild it now." For this, there are optimizations. For example, we have BP3, right? So, this is an optimization. What does it offer us? It offers us to store a certain buffer next to each node, instead of rebuilding it immediately. Store a certain buffer. Store a certain buffer. And we accumulate these changes and then either rebuild from scratch from the bottom, or, or, well, we decide ourselves what, when, and where to rebuild, right? So, we can accumulate changes up to a certain limit. But then a problem arises with reading, because we will then have to check if this record is in this buffer, plus manage all of this correctly. Okay. Okay. So, what other indexes can I have? I can have a bitmap index. What is a bitmap? A bitmap is when you have an attribute that has a fixed number of values, right? That is, it's not that it can take billions of values, but it takes a fixed number of values, say, it only takes male, female, or L1, L2, L3, L4, L5. And I want to check if there is anyone in this table with FIL L2 or not, immediately. How can I do this? How can I do this? Look, I have five records here, numbered from zero, right? What do I do? For everyone who is male, I put a bit of one at this position. 1, meaning the zero bit is 0, and the 1, 2, third bit is 0. What does this mean? It means that the first record will be male, and the third record will be male. Fail 1 1. Here 1 1 1. Ah. I do the same for L1, L2, L3, L4, L5. For L1, I do it here. A one, because at position L1 and the second position is one, because it's also L1. For example, L4. Why is there a one here? Because the third record is L4. Okay. What can I do now? If I want to check if there is FIL L2 in this table, I can take this mask, this mask, and do a bitwise operation. And I do a bitwise operation. And I'm left with one, right, at the second position. What does this mean? It means that at the first position, that the first position will be FEMALE L2. Well, obviously, the problem is, if the mask is too long, I will have to search for these bits.
which are included. Therefore, it is mainly used for whether there is Femil L2 at all, and if the value is greater than zero, then FMIL L2 is there. If the value is zero, then FMIL L2 is basically not there. You don't need to search in this table. Okay. Next index. The next index is the inverted index. Yes. Why do we need an inverted index? For example, I have three songs. I have three songs. And here I loved you so much, you left me. Love, love, love. Here we are standing by the entrance, but without you here, and the sun is like the moon, your love has gone. Here are three songs. And now I want to find all the songs in which the word love was. The word love and its derivatives, for example, like lovers or loves and something similar. Here's what I'll have to do. I'll have to go and sift through every song and look there to see if there's such a word, and in the end say that yes, okay, it was in the first song and it was in the third song. But we have an inverted index for this, right? That's Apache Lucene in Elasticsearch, and in PostgreSQL, you also have an inverted index. What does it allow us to do? It will take these songs, parse them, clean the words to all similar derivatives, and create an index of this type in advance. For example, the word abobaba in the first song, in the third song, the word love was in the second song, in the fourth song, the word XYZ appeared in the first song. So, this is an inverted index. And now, when you want to find, for example, love, you will immediately know, okay, it's the second and fourth song. It's the second and fourth song. So, we live in the year 2025, and now we can do something else in a different way. For example, for example, a song is built on metaphors, right? That is, he wrote everywhere: "You are like a frog, and I am like a pond, I hop without you." Something like that. So, it's clear that he's singing about a frog and a pond, but we all understood that he's singing about love. We all understood that he's singing about love, but the specific word love is not in the lyrics. But we understand the meaning of the song, that it's about love. So, for this, what do we have? For this, we have embeddings, right? What can you do? You can take some model, generate embeddings, so the flow is roughly like this. I'm talking about RAG, about vector databases. You take, generate embeddings through an embedding model, it gives us vectors. It gives vectors, that is, arrays of floats, right, that this song, it's in these vectors. Next, what do you do? You match these vectors with metadata, that, okay, this is this song or this cappuccino and something else that you want from your business, what you need, and put it into a vector database. And then you can ask the vector database, which song is about love, and there either similar results are found, or cosine distance is taken, and it's seen how which vector is closer. And based on the meaning, you can retrieve what you need. Okay. So, we are left with a painful index. We are left with a painful index, namely the geoindex. Namely the geoindex. So, get ready. For this, we will take R-tree. R-tree, right? So, there is PostGIS. PostGIS is used precisely for R-tree. So, what is R-tree? Why can't we use our usual indexes? For example, let's take our usual composite B-tree index, and we want to find here I have Y, here I have X, here I have Y, and I want to find, for example, all these cafes between X and Y. How will my composite index be built? It will sort first by X, then sort by Y. What will we get? We will get 0.1, 0.03, 0.04, 0.05, 11, 12, 13, and blah, blah, blah, blah, blah, blah, blah. But we understand that the closest cafes are those with 44, 55, 66, 45. But if we build such a usual index, it doesn't understand the relationship between these two variables. It just sorts them by one, then by another, right? And we will have to do a brute-force search and then measure the distance between each or each with each, right, the usual one, which is the square root. Not good. Or it's not necessarily location, it could be, for example, height, weight, right, a dependency. And we want to find the optimal height and weight when I have a dependency on several variables. Plus, it might not be two variables, it could be a three-dimensional space, right, some Formula 1 car and how worn the tires are, what the maximum speed is, something else, some parameters we want to find at the intersection. For such tasks, we have R-tree. So, what is R-tree? R-tree is essentially a B-tree that understands geometry. What is meant by this? What is meant when I want to find, for example, some R12, right, I draw a range and say: "Where did this range fall? In the upper hierarchy, in R1 or in R2?" Let's say it fell into both. Then I go to the left subtree, to the right subtree, then I look in this subtree where it fell? In R3, R4, R5. It fell into R4, I go, I retrieve R12. So. But we can have overlaps. We can have overlaps, right? And our task, the task of R-tree is to minimize these overlaps. Because every time we have an overlap, we have to iterate through an extra subtree that does not contain our values. If we look at a map, it will look like this. For example, I want to find all cafes, all attractions that are located here. I draw a square like this. How will this happen? It's seen, this square that I drew, where does it fall? In box 2 or in box 3? It falls into box 2. Okay. Now, where does this square fall? Box 4, box 5. It falls into box 4. And I say: "Okay, you are Brooklyn Bridge, go ahead." Or if we visualize it, it will look like this. I also draw this range. And each time I look, okay, this is in the fourth, and this I then split into two. Where? In the seventh or eighth? Okay, in the seventh. 13, 14, 15. Okay, where is 13 and in 14. It's a bit unusual to adjust to this, of course. The main problem is how to use it. From a user's perspective, you basically just set it up, and everything will start working great. But how is it built? It's built super specifically, honestly. It's built super specifically. Let me reload the page. Something went wrong with it. It's built super specifically. So, R-tree is built in such a way that we try to. So, where is this hyper? Ah, here is R-tree. Here is a rule on how to build an R-tree. If anyone is interested, you can look, you can try to implement it. Here, step by step, what to do, how to initialize, how to check with what, how to search, how to build intersections. So. But we essentially try to minimize this metric. That is, when we add a new node, what do we try to do? We try to minimize the area of this box that will cover these nodes. And at the same time, we try to ensure that it minimally overlaps with other boxes, right? So, for example, now we see, we have one box now. I add another point. another point. Two boxes were built. Now R0, R1, R2. Now, when I add a point here, it will measure. What's better to do with it? Is it better to attach it to this box or to this box? Which one minimizes the area? If neither minimizes the area, it will try: "Maybe then I should form a new box from these two?" Then maybe it will be better, and here to detach a new box, or to split the upper box, because we also remember that it works like a B-tree. It also tries to balance it, so that everything is evenly distributed across the tree, so that we get our search asymptotics. And now I add a point here, it goes to this tree. I add a point here, to this box, I add a point here, it splits into three boxes. I add a point here to this box, to this box, it splits into more boxes. So, it tries to maintain the height of the tree and at the same time minimize the coverage area. This is a super specific data structure because it's built on geometry. I've posted a lot of interesting blog posts in the Telegram channel where this can be applied. It's even used in game development, where you look at what part you need to render now, what you need to show. Plus, it's used in neural spaces, as I said before. So, you can look on Wikipedia that it's not necessarily a two-dimensional plane like this, it can also be a three-dimensional space, and there you build cubes like this. So. Well, in general, a super unusual data structure. Entire books are written about it. Plus, there are various variations of R-tree, R+ tree, R* tree. So. But I think for an interview, this will be enough for you. Okay. Okay. So, look, we've looked at storage, we've looked at indexes. We've managed to look at a lot of things already, right? So, if we look at this picture, we've looked at this, right, we've looked at this a little bit. What's left for us? We have this big piece, these big pieces, these big pieces left. But, but, but, but, but remember, at the very beginning of the presentation, we looked and this often flashed. This is built on LSM. This is built on LSM. If you take, for example, the most popular LSM storage, like RocksDB, you'll see that a lot is built on LSM. A lot is built on LSM, right? What is meant by this? For example, you open RocksDB, find the storage model here. So. And it's built on key-value on LSM. Hmm. Derived from RocksDB. And what is LSM? LSM is a completely different approach to storage. A completely different approach to storage. So, what was my problem with the B+ tree? When we added, I sometimes had to lock and rebuild the tree. So, rebuild the tree, rebalance, rebuild, rebalance, split. LSM is designed to solve this problem and support write-heavy workloads. How does it do that? How does it do that? Let me open a text editor. Ah. And let's look at RocksDB. Ah. So, this is their official repository. Facebook RDB storage engine server work storage focus fast storage. Okay, okay, okay, okay. And let's look at this structure. How is it organized? How is it organized? So, it's organized quite specifically. Quite specifically, when we have writes. When we have writes, writes are added to the MemTable. As soon as the MemTable is full, it's flushed down to an SST file. Then these SST files are compacted with each other, right? A new layer of SST files is built. They are compacted. A new layer of SST files, a new layer of SST files. At the same time, we maintain a write-ahead log. And we have some manifest log. Nothing is clear yet. Nothing is clear yet. But this is what is meant. This is what is meant. Let's assume we will store a data structure in memory called. We call it MemTable, but it's a data structure. It can be a red-black tree, it can be a skip list, it can be our B-tree that we saw. Okay. And we have on disk, specifically, our levels. And we will see what happens. This is what happens. Look, when we add a new entry, so, it's a key-value store, meaning store key-value, but this shouldn't mislead you. You can store, for example, key as primary one, and the value can be an encoded tuple, the entire record. So, you add primary values. So, the one property of MemTable is that it keeps them sorted. It's a data structure that keeps data sorted. Ordered set. At the same time, each of these SSTs, which is a sorted string table, also keeps them sorted. We will see why we need this. Let's add A2, a, B3, C4, D5, E6. Okay, we've added five entries. There's no space here. What do we do? We take them, flush them to disk. Flush them to disk. Okay. Now there's space again. Let's do something more interesting. Like A is now three, and C is deleted, and H is five. Hi, J is three, and M is two. It's full again. We flush this to disk as well. And here it's already raised, like. Now we can write here again, it's free again. So, the trick is, the trick is why we well support write-heavy workloads here, because we write directly to the MemTable. As soon as it's full, we flush it to disk, write to MemTable again. As soon as it's full, flush to disk, write to MemTable again. That is, there's no rebalancing or anything like that happening here. We write, write, write. Flush once. Write, write, write. Flush once. Write, write, write. Flush once. Now, what happens at this moment on disk, right? So, we've understood that our entries are great. But what about reading? What about reading? This is the problem. For example, if I had added A10, B13 here. Yes? Now, if someone came and said: "I want to read A." We would first check the MemTable for data, we would say: "A10, that's it, go away." Okay. But if someone comes for D or someone comes for C, what should we give them? Then we'll have to go to disk. Okay, we've remembered this point. And on disk, we have, let's say, several such files. And there are also some levels. Why do we need these levels? Look, we also set a limit here. We set, for example, that we only support, I don't know, two files of a certain length. When they are full, what do we need to do? We need to merge them, compact them, and merge them to the level below. Thanks to the fact that they are sorted, merging and compacting them is much easier for us. So, you might see such a task, for example, on LeetCode, merge sorted linked list or merge sorted, how to do it correctly? So, because they are sorted, it's much easier for us to do this. Even if we have several such tables, we can still do it easier, right? So, we use some min-heap, or when there are two, we use two pointers, and simply choose which one is smaller. We move one, we don't move the other. This is a specific detail, you can look it up somewhere, or in my algorithm course. Now we need to merge them together. How will we merge them? Each of these entries has a timestamp when it was added. We look in one, A2, in another, A3. Which one is newer? A3 is newer. So, A3 will go here. In one, B3, in the other, B is not there at all. B3 will go. In one, C4, in the other, C is deleted altogether. So, which one will go? C will not grow here at all now. In one, D5, in the other, D is not there at all. E6 is not there. And this will go here like this. Okay. From this, what else do we see? From this, we see that they grow from level to level. So, here the SST file is, let's say, larger in size, right? Then, of course, we can delete from here, we can delete from here, more will be added, they will fill up, we will merge them down here, a second file will appear here, right, there's also some limit for the level, when it needs to be merged. We will merge them, flush them to the level below, flush them to the level below. Flush to the level below. Okay. At the same time, all files are immutable. What does this mean? We've merged them, right, we don't modify them in place. That is, when something is updated, deleted, we don't do anything. We merge them with each other to the lower level. These files can be, for example, completely removed. Or, or, or, as Neon, whom we talked about at the beginning of the lecture, does, thanks to the fact that they are immutable, we can archive them somewhere, store some history, and we can specifically return to a snapshot, to a certain point, to certain SST files, just like that, bam. So, you can version them somehow and then go back from one to another, to where you are now. So, LSM, log-oriented storage, right, LSM storage is a completely different approach to how you store data. That is, you don't store them as we discussed at the beginning, with pages, right, or anything else. No, you store them in MemTable, then flush them to disk. SST files also have their own structure, they have their own format, their own header, but for now, you can roughly imagine that it's just key-value, key-value, key-value, key-value, key-value. Nice, nice, nice, nice, nice. So, where is the problem? The problem is that reading these SST files is expensive. Reading these SST files is expensive. For example, when I want to find A2, A2, what will I have to do? I'll have to read this SST file, right? This SST file. Or if they are not here, I'll have to read the file below, for example, and look for A2 there. A problem, a problem, a problem, a problem. Understandable, we can parallelize this, search in these files in parallel. A problem. So, what are the solutions for this? One solution is an approach called leveling. So, in one approach, what you do is, in the SST files at the lower levels, you start storing ranges. That is, for example, you know for sure that this file is a range from A to C. This file is from D to E, no, to F, to G, for example. And when they merge, here, for example, it will be from A to G. Okay. This already simplifies your search. So, you now know that if my key is in this range, then it should be somewhere in these files. Another optimization, another option, this is called tiering - this is when you don't look at this, you don't pay attention to the ranges, but you merge as is, as you are given. So, what's better about one option than the other? In one, you need to manage these ranges so that they are preserved, and in the other, you merge as you get them. Okay, the ranges helped a bit, but there's another brilliant idea that we can see here. It's to use a Bloom filter. Use a Bloom filter. So, what is it? What is a Bloom filter? What is a Bloom filter? Look, we take and make, let's say, 20 bits, right, a mask. We make a 20-bit mask and say that we have, I don't know, five hash functions. So, I get 100 bits. And now each hash function maps my value. For example, if my key is something like, I don't know, Vlad, or what can it be? Well, let's say 10. It says 10 maps to these values. Here, here, here, here. Now 13 maps here, 15 maps here. And now, so, for this file, when it's built, we create such a Bloom filter for it. We create a Bloom filter for it. And what can we do thanks to it? We can immediately say: "Is there a seven here at all?" And it will tell us: "No seven here." Why? Because seven will highlight certain bits that are not in this mask. And if this number seven were here, then this bit would be highlighted for sure, right? So, when we search for 10, it highlights bits where there is 10. And now we know that 10 is probably there. Why do I say probably? Why do I say probably? Because hash functions can have collisions. And what can happen? One and the same cell can be highlighted by several values, right? So, 10 itself, for example, is not there. 10 itself, for example, is not there. Okay. No, look, 13 itself is not here, but the cells that 13 maps to are highlighted. Why did this happen? Because the intersection of several values just mapped to the same cells in the hash function. And it seems to us from the Bloom filter as if it's there, but it's actually not there. It's actually not there. So, so, the Bloom filter tells us this. If the Bloom filter, so, this will sound like a quote from a street slang publication. If the Bloom filter told us that it exists, then it might not be there. Why? Because you just had an intersection. For example, let me highlight this point again, because it's important. For example, X maps to 01, right? G maps to 1, and Z maps to 1, no, to 0011. Before this, we added G and Z to the Bloom filter. What will my Bloom filter look like? It will be 1011. X will come with its 1001, and say that my bits are highlighted. They will say: "Yes, brother, your bits are highlighted." But X itself is not there. It's just G and Z that created such an intersection, understand? And therefore, if the Bloom filter said that it exists, then it might not be there. But if the Bloom filter, if the Bloom filter said that it's not there, then it's definitely not there. It's definitely not there. Why? Because if it were there, its bits would be highlighted. We only turn them on. But if they are not on at all, right, then it's not there, not even by intersection. Nice. At the same time, at the same time, we remember that each of these files is immutable. Each of these files is immutable. What does this give us? This gives us that no one will ever delete from the Bloom filter. Once we attach it here, it will stay here. The Bloom filter itself doesn't need to be changed, because if a value is deleted, then problems arise. We need to see who lit these cells, like, do I need to clean them up, do I not need to clean them up? What if they were hit by another intersection? But since the files are immutable, now the Bloom filter accurately tells us that it might be here, but when it's not, it accurately says no. And now, when you want to find a specific key, you can go to the Bloom filter in parallel, and it will tell you: "Listen, these files said it might be in them, go and look." And you go, bam, and look, and your search has sped up. Awesome. A fairy tale. And here there is such a website called Compaction. They also have a report on YouTube that you can watch. Here are various types of when we decide when to merge these tables, up to what size they should grow. Plus, these parameters can be tuned, or other strategies can be used for how you compact them. Yes, at the same time, you can have strategies where several levels are leveled, several levels are tiered, right? So, it's divided like this here. Well, remember, right, whether it intersects or not, the range. Let's look at the vanilla. So, roughly speaking, LSM will look like this. You fill one file, fill the second file, fill the third file, fill the fourth file, bam, flush them. Merge them, flush them. Then fill four more, flush them. Fill four more, flush them. Fill the last fourth one. Now it will merge with and be added here. They will all merge and be added to the level below. Flush, add. Merge. Merge. Merge. Merge. Merge. Merge. Merge. Merge. Merge. Merge. Merge. Merge. At the same time, here you can see, for example, how different strategies of when we compact and how we manage our ranges, which one will give us performance in terms of consumption, in terms of IO, how often we will go to disk. So. Super interesting to play with. I recommend just opening it, looking at it, watching the reports. So, here you can change parameters later. As you can see, there are interesting parameters like buffer and page size. Entry size. So, page size. What is meant by page size? I thought I said there are no slotted pages here. And as we saw before, there are no slotted pages here. But, but, but, each SST file, each SST file itself is divided into logical blocks, pages. So. And then there's a block cache that also knows how to pull them into memory, so to speak. Phew. The question arises, when we write to MemTable, our electricity might go out. What to do? Will that data be lost? No, that data is not lost, because we do write-ahead. That is, before writing to the MemTable, we write to the write-ahead log and say: "These are the
I make such changes. Here are such, such keys I add. Such, such keys I add." Plus, we have a log manifest, which generally tracks what state, what state, of which SST files. What we haven't looked at, we roughly understand how SST files look, we roughly understand how a merge looks. We don't understand what it is, what kind of table. Let's see what Roxdb tells us about this. What does Roxdb tell us about this? Let me write "skip lister alert" here. And we look at the "default implementation of table robblist skip list sorted set." Nice. At the same time, if we go to Wikipedia, we will see that this skiplist is used in Discord. Hmm, it got even more interesting. Why a skiplist in Discord? What kind of skiplist is this? So, get ready, because a skiplist is a super unusual data structure. Imagine we have a regular linked list. I add one to it, I add two to it. I add 10 to it. I add 11 to it. Okay, everything is clear. Now, to add seven, for example, you'll have to go to where seven needs to be added. There, bam-bam-bam, insert it here. Okay, good. For now, it maintains sorted order, but some insertions are certainly expensive, right? Searching turns out to be linear, so they came up with this clever optimization called a skiplist. So, a skiplist is a probabilistic data structure that gives us logarithmic complexity and uses an approach similar to how a Binary Search Tree works. Look, I'll add five here and set the parameter to 1 here. I'm setting this parameter manually here for educational purposes, but generally, it's chosen randomly. And look what it will do. What the heck? What was that? It grew the value of five upwards by several levels. Yes, unfortunately, the levels have intersected here now. Oops, what did I do? Ah, what a shame. Well, let's try to direct it more. What a shame, what a shame, what a shame. Yes. And I would like, for example, for seven not to be here, but for seven to grow really well. Wow, not bad. So, every time a value is added, it also grows upwards by several levels. And this moment, how many levels it will grow upwards, is determined randomly for us. But what does this give us now? Now, when I want to insert, for example, nine, what do I do? I go along the top level and look, where is nine? I've reached seven. I think, "Okay, 9 is greater than seven, so it's in the right part of this linked list." It's less than 12, so it's somewhere between 7 and 12. I descend from here. Now there's a link down, to the next level. I look, and is 9 greater than seven? Yes. Is it greater than eight? Yes. Okay. So, it's already located somewhere around here. Descending from here and inserting our nine. And thanks to randomness, it's calculated in such a way that our nodes will grow upwards, right, and they will grow in such a way that on average we get log n. On average, we get log n. That is, it will be sparse in such a way that, look, the logic is the same as in a Binary Search Tree. That is, it's like pointers. We think, "Okay, greater than seven, less than seven. If greater, then we know for sure that in the second half of this linked list, on the right, we need to check." At the same time, we can descend, there will be some new pointers, for example. We can understand from them. And here our K-value pairs will be stored, which we will take, they are in sorted order. Bam! Flush to disk. Awesome. A super unusual data structure. I understand, a super unusual data structure, but that's how it is. That's how it is. There is a problem on LeetCode, "Skip List." There is a problem on LeetCode. "Design Skip List." I recommend you solve it. I recommend you solve it. Generally, just to understand the skiplist for yourself, what's happening here. It's a very unusual data structure, super interesting, right? The chance that you'll encounter it somewhere else is probably small, but it will be cool to understand it for yourself. Okay. So, we've also looked at an alternative approach to managing your storage, which is LSM Storage. So now it's not so obvious because we have these variations of B-trees with buffers, right? But roughly, based on this, you should feel why for heavy, WR-intensive workloads or for distribution, you use LSM storage. Firstly, you have key-value pairs here. You can split ranges more easily or shard them somewhere more easily. Then, you don't waste time on writes, you just flush. It compacts at the bottom. At the same time, you lose on reads, of course. RocksDB is an implementation of LSM Stage, which is used somewhere. At the same time, I again recommend you return to the repository I've often talked about. Talentplan. Talentplan. And the key-value where you will build your storage on top of LSM storage. Don't use Badger there. Look at it, look at it. It will be interesting, truly. Okay. So, in our worldview, we've figured out this, figured out this. We are left with this and this. This is the topic of two future lectures. And with this, we can, in principle, figure it out now. Look. But people spend careers and scientific works on this, right? Millions of dollars. Because if you do this well, then, well, you get performance boosts, and that's millions of dollars. Unfortunately, I can't tell you about a million dollars right now, but I will tell you, I will tell you as I know. So, look, when a request comes to you, right? You write your standard SQL, like "select from," blah-blah-blah-blah-blah-blah-blah, blah-blah-blah-blah-blah. Ah, yes, you can't see the slide. It says "statistics about the data." Statistics about the data. So, "select from blint bl." Here's the request that came to you. First, it goes to the parser. What happens? It's simply like when you write your programming code, right? It's parsed and checked if the construction is valid. That is, this code is valid in principle. What you wrote is valid SQL or invalid SQL. After it understands that it's valid SQL, it will build a relational algebra expression from your query. What is meant by this? These are the scribbles, right? We'll break them down now. After that, it will build several equivalent expressions for you, go to the data statistics, where, in which relation, how many tuples, where what index is attached, how warmed up it is, how not warmed up it is. In short, it will gather as much information as possible about your data, pass it through optimizers, and choose the plan that will be most optimal for you. Then this plan will be executed on your data, and you will receive your result, accordingly, right? That is, you can view the plan of your query, for example, through "Explain Analyze." Through "Explain Analyze," then paste it into some website like this, and it will draw for you what's happening with your plan. And, for example, what was the most expensive part of your plan, where there were the most I/O operations. Here you will see, for example, a full table scan, and maybe you'll realize that for this query, you might try to add some index to avoid doing a full table scan, right? Or somehow warm it up differently, rebuild the query. So, the query optimizer will try to optimize for you and build the query in an optimal way. For example, look, this moment when it builds a relational algebra expression. Each of these symbols means something. It means something. Thank you, Captain Obvious. Each of these symbols means something. Golden quotes from Vlata, write them down. So, this symbol, right? This is projection. What does it mean? It means "course IDLE and course." If translated to SQL, it's "select course course ID title from." Like this, what we are selecting is "course ID title." This symbol is "join teaches." This symbol is "joins instructor." This symbol "de name = music." This is like "select by condition." That is, it looks like "select * from where?" Well, from this expression that you got, "where where where." "Name = music where deep name = music." This is the "where." This symbol. This symbol. Okay. What do we understand from this? So, all courses are retrieved. They are joined, taught, to see, there's likely some mapping table where we see which teacher teaches what, which course. We map, join with it, then join with teachers, and we only need teachers who work in the music department. So, the optimizer looks at this expression and thinks, "Why should I join with all teachers if I can join only with those who teach music, because I will filter them from above anyway?" Let me filter those who work in music right away, and then start joining. And these operations, for example, I can do them in parallel now. It rebuilds this query, rebuilds this tree, and gets and gives you an optimal query. How did it understand that I can painlessly move this down here, and everything will be fine, right? To move this operator down. But it didn't just understand that because we have laws by which we can move expressions in relational algebra, right? We have the law of equivalence, for example, for example, look, this select by one condition and by the second condition from the table is the same as select by one nested in select by another. That is, if we translate this into SQL, it will look like this: you did "select * from (select * from where condition 1) where condition 2." This is the same as doing this. "Select * from X where condition 1 and condition 2." That is, this is the same as this. I can turn this into this, for example. Or, by swapping condition 1 and condition 2 here, nothing will change, right? This is already the law of commutativity. So, this is written here. "Condition 1 and 2" is the same as this nesting, or the same as swapping them. The next law. When I do a join by some condition, it's the same as this join and this join. If we join this and then with this, it's the same as joining this with this. Or what is used in our example. If I join, and then filter by some condition, it's the same as filtering by the condition first, and then joining. Or this, this Cartesian product. These are all pairwise combinations. Take all pairwise combinations, and then select from them by condition is the same as joining by condition. Or joining here by condition two, and then selecting by condition one is the same as joining immediately by condition one and two. And with the help of such operators, with the help of such operators, with the help of such laws, right? You can read about them in Parus's book, there are a lot of them here. With the help of such laws and operators, we can transform one expression tree into another equivalent expression tree, right? Equivalent, meaning it carries the same meaning, right? We haven't lost anything, we haven't changed the logic of the query. We've changed the expression tree, but the meaning of the query hasn't changed, right? We haven't made it so that you wanted to filter by music, and now you don't filter by music. No, we've preserved everything, just restructured it to be more optimal. [Music] This lecture is now concluded. Thank you very much. I am sincerely grateful that you sat with me and listened to me. So, this component and this component we will discuss in the next lectures. If you have questions, please write comments. If you didn't like something somewhere, if you saw something somewhere, please let me know about it. But again, disclaimer, this is all done in an educational format, as if we are inventing something each time. So. Thank you very much. Thank you, thank you for your attention, truly. I appreciate you. Good luck. Bye. Well, that's it, I can't say bye. Homework in the description.