CMU Database Group · 1:21:10 · https://www.youtube.com/watch?v=foMMYyycRgk
1. <Untitled Chapter 1>
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol yeah I know the snipers in the ri and then like I was late and like the cops like mouthing off to me and I'm like I didn't know all right sorry um all right there's a lot to cover today uh this is going to be a big sort of brain dump of a bunch of different data structures you guys should know about in Contex of databases uh so let's get as much as we can so again for the class uh project one again is due this Sunday
0:52 there's a recitation and the uh tutorial how to how to profile the performance of your system that's posted on PIAA and the video is available as I said begin the semester the we have extra office hours this Saturday right the day before any project is due uh and that'll be in Gates 5207 and you'll sign up using the the ohq uh website right other thing I point out too a reminder as I said beginning of semester do not email individual Tas about like how to debug your project please either come to office hours or post everything on Piaza
1:23 right because instead of explaining the same thing over and over again to different people we want if we post on Pat then everyone else can can see um you know can see what the solution is how to fix things homework 3 will be uh out today and then I'll be due on the actually October 6 not September 6 sorry so not not not the past in the future and then uh the midterm again will be in in three weeks coming up in class so again if
1:46 you're uh if you haven't started a project one uh you start now right like if you're struggling with with with a deadlock is this is going to be a problem because project two is be much harder than project one so if you don't what what a deadlock is now and you don't have to debug a multithreaded C++ program you're going to have a lot of problems later on so if you haven't started now please start and then if you have questions obviously don't show up on Saturday's office hours be like hey how do I get started you're GNA have problems
2:15 okay all right so last class we were making distinction about talking about indexes in the context of B plus trees uh and we sort of said that there's these notion of an index which is is the data structure we can maintain our database system that that that allow us to find the location of a given tupal or record based on some number attributes
2:34 right certain number of columns and so forth right and the b+3 is the most widely used one so today I'm going to talk a little bit about filters uh because this is going to be an important data structure that's going to allow us to do a bunch of other optimizations later on especially when we talk about joints and and similar to how the mod law keeps appearing in different contexts in the datab system the a filter is going to be useful in a different a bunch of contexts as well so the difference between a filter and index is the filter can tell you whether something exists like does ay ke exists in a set but it can't tell you where it is index will say yes it's in the set and oh by the way here's where to go find
3:07 it so a lot to cover today as I said so we start off talking about balloon filters a little bit about other filters that are out there and then this is going to be again a smorgus borg of a bunch of different data structures that are super useful and why they use in database system again not B plus3 is going to be the most common but we'll see how tries and uh skip list are used in other contexts as well and then we'll have a flash talk from the the co-founder of tid B I think he's the the CTO who was here last week can give the talk uh when we had our on campus event
3:33 okay so actually quick show at hands who here has heard of Bloom filter before half okay who here has heard of a try before all right okay skip list anybody very few and then Vector indexes and ver indexes well you know there isn't one data structure we can point out say that's what it is the same way like a tri radex tree is but we'll cover that all right so Bloom FS are super useful not just for databases but databas is the most important thing but you you'll see these throughout uh throughout other aspects of of
4:01 computing so a bloom filter is going to be a problemistic data structure that is going to answer again set membership queries because it's a filter it can tell you whether something exists in a set or not but the key thing about it is that it's probabilistic meaning unlike in a B+ tree which was always give you an exact answer like you say does this key exist you follow the the the inter nodes Leaf nodes down sorry inter noes down the pointers to the leaf noes and then the key Either is there or not there in in blim filter uh you'll never have false negatives meaning if you ask whether a key exists it it will definitely say yes it does not exist but it may give you false positives on on Keys meaning it'll tell you that it exists when it doesn't actually exist
4:43 and then it's up for you to go figure out you know look at the real data depending on whether you care you whether that you know the answer is correct or not you have to go then look up the real data to see whether that's true right so you so an example would be we saw this when we talked about chain hash table in my bucket list I could have a blooom filter in the the the bucket pointer array so when I Hash a key I land in I land in that bucket pointer I check the bloom filter based on that key to see whether my key could even exist in the chain and it might tell me yes and I go scan it and I find nothing but if it definitely doesn't exist then I know it's not in my chain
5:16 right so that's an example we can use this to optimize other things so blimp is going only have two operations or two commands you can do on it you can insert a record and then you can look up a record you can't do deletes we'll see accounting filter in a second that that'll handle delete but in in the the original balloon filter idea and how's what most why they Ed you can't delete keys and you'll see why in a second I think Bloom filter dates back to the 1970s it's called Bloom because the guy's name was Bloom that's why you'll see it with with a capital B because it's a it's a proper noun all right so at its core balloon fitter is just going to be a bit map right my my toy example here I'm showing eight eight bits uh and sometime you know typically it'll be much larger um but but not not significantly larger and obviously there's a trade-off between how big your bit map is and how many hash hashes you want to do into it that'll affect the false positive
6:12 rate all right so if I want to populate this thing at the beginning everything's all zeros so I say I want to insert the key RM so in this example here I'll have two hash functions right and I could be the same hash algorithm like like XX hash just with different seeds so that produces different random values but it doesn't matter so I'll get a hash value mod by the number of bits that I have and then whatever number comes out of that is going to correspond to the offset in my bit map where I'm going to flip the bit from zero to one right if it's already one then I'll just leave it
6:42 there say now I want to seert a uh another key jiza right same thing hash it twice moded by number of bits I get two locations and I flip the bits right so going back here actually from this case here I always land it in locations where the bits were always zero so I always flip it to uh from 0 to one and then say now we want to do a look up on Rizza it's just the reverse of an insert
7:05 right it's a pretty easy algorithm hash it again mod by the number of bits I land in my location and then as long as both bits that I land on are set to one then I know that this thing potentially exists in my in my uh my my my set right if one of those bits were set to zero then I wouldn't have't inserted it because I would have otherwise I would have set it to one
7:31 now we do look up on rayon the chef right same thing hash it get different locations do a look up in this case here the the the first hash gives us at um offset five that's set to zero right the second offset is at three is one so again even though one of them is set to one the other one set to zero so I know that this is this is uh this is not my set again this is why you can can guarantee that there's no false
7:57 negatives but but now if I do a look up ODB rest in peace uh same thing when I hash it I land locations now I to haveen Hash to locations where the bits are set to one so this response is going to come back with true but again in my toy example I didn't insert
8:13 it right so this clear again you can imagine like if you have a bigger bigger bigger bit map and more hashes you're the accuracy of of these lookups will will increase but again there's a trade-off between having a larger balloon filter
8:30 right spending more compute time hatching things so as I said before in this the the basic balloon filter you can't delete things right you can only insert and do lookups there's a variant called a counting balloon filter where instead of storing the bit you know sorry a single bit at every offset I'll to store an integer and every time now I hash when I do an insert and land in my bit map or my my my Vector I'll just increase the counter by by
8:56 one and then now I can actually do deletes as well because now I can go and uh when I want to delete something I just one yes responsibility delete something that was never inserted uh your statement is it would be the call responsibility to to make sure they don't delete something that was never
9:16 inserted yes but like yeah don't do that right but again this is something be internal the system we're not writing we could write bad code but we're not writing explicitly malicious code to to to mess out up right so again same thing I'll get uh I I'll get you know I could never get false negatives right because the counter is set to zero I know it could not any of the positions is not set to it's could not exist uh but I still could get false positives or I could count something that more that than it actually
9:51 exists a better variant is called cuckoo filters uh and the idea here is very similar to the cucko hash table that we talked about a few few uh classes ago where but instead of storing like the full key that we want to put into as we put in our and our hash table we're actually going to show what's called a fingerprint sort of thing it's like a hash but it's it's a way to reduce the the number of bits we have to do to uniquely represent
10:18 something uh you know a given key so the advantage of this is that versus using a hash is like this is potentially cheaper to compute and there's still because it's not sort of randomly permuting the bits in the way a hash function does there's still some resemblance to what the original key was and that means that things that are close together will potentially overlap in a way that you can't do with just regular hashing so again like before in in the counting mod fter you can do adding and you can do removing because it's just removing things out in and out of this hash
10:50 table and the last one is a a different data structure called succinct range filter which is it's a it be a very compact version as of a try that see later on um this one is actually immutable unlike the other two meaning I I have to have all the keys ahead of time and then uh the data structure is essentially Frozen but this going to allow me do the the same you know exact match key lookups like does this key exist or not but now I can also do range filter and say does a key exist in this
11:22 range could we think of an example of one of the the uh components we were talking about for in this class where I would WR I could have all the keys ahead of time and write something once and only once and never have to modify
11:34 again the log structure M yes so when we wrot out that SS table uh right you could you could you have all the keys you're doing this compaction so you could build this this uh this range filter now or at the moment you're doing the compaction and then write it out once and read it a bunch of different
11:52 times so the these two things were actually invented here at CMU right so the cuckoo filter was vented by by Dave aners uh and then the the surf the CNC range filter that was done by a PG student that was that was co-advised by myself in Dave Anderson right uh and so his exact example this is what we originally built the surf for we we put it on Rock DB right instead of they built a balloon filter in their SS tables we put in we put in Surf and then we saw the amount of bureaucracy you have to go through to get something merged by Facebook and we decided not to pursue it further but uh the code is there all right the coua filter is why they used in a bunch of different locations and actually if use redus redus will give you explicitly uh a CUA filter type right you can call a command and say the for key pair the value is going to be a cucko
12:40 filter right so again filters are super useful and again we'll see them over and again throughout the throughout the uh the semester all right so let's switch back over and now talk about indexes so last class we sort of showed the D+ tree and we showed all the the inner nodes and the root all the scaffolding above the the leaf nodes that but when I removed the leaf nodes sorry when I removed all the inner nodes and kept the leaf nodes it was essentially a link
13:08 list right so that's a link list is the easiest way to build a uh an order preserving data structure right that you you want to be dynamic meaning I want to be able to insert something into to different random locations at different times right and as we said before if without the things up above then it's always going to be uh a linear scan across every single entry or o o of n right because I got to keep scanning till I find the thing that I want now you could do uh you could do binary sege that cuts things down but the problem
13:40 with if it's a link list you don't know where to jump into right because you can't assume that the bits are all packed all right the values are all packed in the single right all right so what's one way we could speed this thing up well we saw in the case of B plus Stree we sort of built these nodes Above This that had these separators to tell us when when to go left and right
14:00 well what's something even more simple would be what if we just had another level of a link list up above the the bottom link list where it just skipped every other key right and we can do it again another level above now it skips every other key over the list below it so now when I want to do a look up right I could start here at the top figure out what this thing is pointing to and given the key that I'm looking for if it's if it's
14:27 less than what I'm pointing at then I know I don't want to go this way I want to go down and then now do the same look across there pretty basic right this is what a skip list is right it's just having these multi levels of a of a link list with these extra pointers that allow you to jump to different offsets into the link list that's at the bottom and what's going to be different than what the example I showed before is that if it's going to be a probalistic data structure
15:01 meaning you're not always going to have the the this the the higher levels skip the same number of keys you're essentially going to flip a coin every single time you insert something and decide you know how how many things you should be jumping I'll show that the next slide so in general every every level is going to have half the keys uh than the one below it right because the probability that you're going to have a A Link at a given level uh decreases as as you go up right from the bottom to the
15:30 top so like a B+ tree it's going to give us log and search times but it's going to Pro approximate right on average it's going to be log n but there's no guarantee because again we're going to be have some bit of Randomness to
15:44 it so skip lists are going be widely used for inmemory data structures so just going back to my example here right I'm showing this on PowerPoint you can essenti think of this this existing in memory so we're not really even talking about Pages anymore because this thing's not going to be spiled a disc we're going to assume that this is sitting in the Heap of of your
16:03 process right and for inmemory stuff it's it's it's pretty fast so this is used a lot of times for the M table in the log structure merrye like in rocks DB the M table we talked about is going to be a skip list in wire tiger which is the underlying engine for mongodb uh because they they had map that was a disaster they got rid of that bought wire tiger wi tiger had a log structure merry again using an inmemory
16:27 uh skip list couch base also uses this for in memory indexes single store originally started off as msql and that was an inmemory uh inmemory databas at least originally it was and those guys saw the things that Microsoft was doing this other project called hecaton uh and they were all in with skip list at Microsoft the guys saw th those talks they went off and did msql and and borrow the ideas and they built their entire system around skip list but then they missed the later talks from Microsoft that said skip lists are a bad idea uh but they they were still riding with it for a long time all right so skip lists are are they're they're newer than a B+ tree right from like from 1990
17:05 invented at University of Maryland and again they mostly appear for inm data structures there there are some attempts to make them with dis based all right so let's let's let's go through a cric is aable so we got through the different pieces we have so here we have the levels right and basically these are the entry points into the data structure at a different level and then below it you have the probability that a key is going to exist at this level so at the lowest level you have to have all the keys because you have to know that you know they have to exist in there so the probability is n
17:34 but then above it it's n n/ 2 and N four and so forth going up right and so this bottom layer here that's equivalent to the leaf nodes we saw in the B plus Tre again where it's in sorted order and has all the keys that could possibly exist in in your in your table or your set all right and then this one here now you see have we have the entry point into at this given level and then instead of immediately pointing to K1 it's going to point over here to K2
17:59 right and K2 is going to have a downward pointer to go back down to the level below me right where K2 is but also has a pointer to go across and jump to to the next entry yesil a p is like
18:17 probability uh all right yes it's it's yes it's the count yes on average is the count yes yes yeah divide by 100 okay all right so if I want to insert K K5 so what I got to do now I'm basically going to flip a coin uh you know a a a uniform random value like 01 and multiple times and every time I get a one then I'm allowed to have an entry at the the next level and then I flip the coin again if I get another one I can have entry at the next level if I get a zero then I stop wherever I'm at and I and I have my uh I that's where I then have my levels going across right so in this case here I flipped the coin
18:59 say I get a one then I'm allowed to go up here flip the coin again I get a one now I flip a coin here now I get a zero uh so I'm going to stop here and then now I got to put my entry in here so K so as I scan across I say this thing is pointing at to Infinity so I gotta I got to I know my entry should go at the very top in between the starting and the end point right there right so I would add my entry below and then I have to trace along here to know that I come after K K4 come after K4 there right so before I do anything when I set up the data structure these things are still pointing to wherever they were pointing before so any anybody coming along at the same time I am they're still going to follow the pointers and not see my
19:42 data right so now I got to start adding the pointers from the from the bottom to the top because I don't want someone to come across see that there's an entry at a higher level then try to go down looking for that key and they end up finding nothing so when I build this thing I'm building from the bottom to the top
20:00 right so again I have all my PES going down so I add I add the K5 to k6 and these guys here they're actually pointing to nothing at this point uh so they they just point to the end there and then now I flip this pointer here now anybody coming along they may not be able to use the the pointer to get down more quickly to where I am but they'll at least find me right if they come along in any other level
20:21 there flip the pointer for the next level flip and then flip the pointer for the next level and then now my key is fully integrated in the data so we don't do splits and merges like we did in the B+ tree it's just finding where we need to be in the in in the the link list and then inserting ourselves
20:41 and we can do a little tricks to to to just do essentially compare and swap in memory to replace these pointers and now have to take latches on anything so if you have the link list only going in One Direction then you can do this in a in a lock free manner a lat free manner like you just compare you just do compare and swap
21:00 all right so now if I want want to find a value so again I now I start at the top level and I again scan across and figure out what I'm pointing at from the entry point so in this case here I scan across I find K5 K3 is less than K5 so I know that the thing I'm looking for is not going to be after this K5 here so I need to start before it now I go down to the next level I scan across I see K2 K3 is greater than K2 so I know again the key I'm looking for if it exists which at this point I don't know whether it exists or not is going to be on the other side of this so whatever comes before this guy in the link list I can to skip
21:37 entirely so now I come across here follow the pointer that now I see K3 is less than K4 so again I know that K3 has to be before this so now I SC scan down on the bottom and then it's just just a sequential scan along the leaf nodes to find that I
21:54 want so it's in this diagram like here it looks like a right this looks like a bunch of Li l on top of each other but if you sort of visually you can s rotate it in your mind it's going to look similar to uh like a like a tree data structure right we just have we where these things are basically the split points that we had before yes if we start adding a lot more data do we choose to add another layer or are these layers like predetermined the question is if we start if we start adding a lot of keys uh do we do we choose to add more layers no you keep flipping on the coin right if you get 100 ones
22:29 you have to have 100 Levels I mean guess you could put a stop in there but like yeah that that's basically how it works the back yes his question is uh going back here when I was doing the insert as I'm flipping the coin and going up the side here like
22:59 if I flip the coin and get a get a get a one I need I need to go add add up here so I know I always have to have it at the leaf node but now I flip the coin it tells me I'm going to add this node here so every level as you go up you have to add your key in okay
23:11 yes yes his question is what's the point of flipping the coin can you deterministically find where it should be if you don't know the keys ahead of time how would you know how to space out the T like space out the levels know how many are each question you don't know how many keys there are in each level I mean you do know you do know the number of key each level yeah so so as soon as the dynamic data structure I don't know the keys ahead of time so I'm incrementally inserting
23:41 them but you know how many ke are each you need to keep sorted so rebalancing you have to resort to likeis like yeah if you don't if you don't rebalance you you have to you know Restort everything but flip flipping coin gives us the randomness and G gives us that that lend property we
24:02 want and because we don't know the keys ahead of time this is good enough yes so if you get very lucky every key is on the lowest level and not if you're lucky you always always have to have so if you have only one key that you fli the point 100 times and you have to insert into like the hundred level so you have a really long chain so every time you do like a like a sech you to go down that really long chain yes so that's that's the so like so I mean we'll see this when we talk about tries you could vertically compress that and recognize that okay there's I have 90 uh you know straight pointers down with nobody else there then yeah you could collapse that and just keep some extra metadata but uh there's variance like these are called Towers I think in the original paper right there's Alternatives called
24:54 Wheels like it there's optimization you can do OB yes I'm just showing like the vanilla skip list the basic idea again it's like it's different than the B+ Tre where we we were deterministically deciding where to go this is like adding Randomness to
25:10 it all right let's quickly see how to handle deletes right so there's G to be two steps first we're going to logically remove the key from the index by setting a flag in in in the record in the entry in in the link list that says hey this thing's been deleted then it's some later point when we know that no one could be looking at us which we're not really talk about multicurrency or multi-threading till next class if we know that nobody could be looking at us then we know it's safe to go ahead and actually physically delete it and swap
25:40 pointers again this is easier to do if the pointers are always going in One Direction so you're not worried about someone coming the other way and doing something weird right so again now with every single entry we're adding this little delete flag that's set to false right could be a single bite or a bit all right so n now we want to delete K5 again doing the traversal ago we find where K5 is then we go ahead and flip that bit to True right then now again anybody comes along that may be scanning along the leaf notes and finds this will
26:07 encounter five and they know to ignore it and just go past it again the the the data structure at this point is is still correct logically but then now when we do when we want to remove it we're going to start doing it from the the the top going down right so we remove this this this this up here so no one falls down so again by doing from the top going down we know that when we start when we actually physically remove this node
26:34 there isn't somebody coming down from above trying to trying to grab it right so we're because we're going to be deleting things as we go down versus like deleting from the top then all a sudden someone points to the node that got physically removed so we all we do is compare and Swap and change this pointer that's good change that pointer now we're good and then change that pointer and now we're good right and again assuming that there's no uh we are you know keeping track of like is someone still looking at K5 which we'll talk about next class right once we know that nobody's actually physically looking at any of these nodes then we can go ahead and actually physically remove it free the
27:10 memory all right so skip list are uh the advantage of skiplist is that they're going to use less memory than a B+ tree uh because you're not you don't have this extra space to account for new inserts showing up and therefore you know to avoid having to split all the time so typically they could be used less memory as long as you don't use reverse pointers and then we never have to do splits and merges when we delete things because it's just excising out
27:36 the individual key that we want from from the uh from the data structure if you got a spell a disc then this is terrible because uh now you now you're dealing with uh reorganizing things as is a block structured so instead of having a single Key by itself hanging out in memory now I got multiple keys in there now you got to account for that in and how you design the in the in in the the pointers and things like that it becomes more complicated because now you're your your sort of links going down or pointing to a page and you need to be aware of like oh that page may not have exactly that key that I'm trying to skip past and understand where where you know keep there's more meded to keep track of just scan
28:17 along and again for the uh for the M table you don't scan reverse uh so this is less of an issue but if you need to have it use this as a general data structure a general index where you need to be do ascending descending uh scans then skip list becomes more
28:33 problematic okay so going back to the b b plus3 again as we said before the the inter node are essentially guideposts that tell us whether we want to go how we go left or right till we get to to the leaf node so when we land on inter node at that point we don't know anything about
28:51 whether the key we're looking for actually exists or not right because we could see the key in an inter node and that tells us to go left or right but then when we get finally down to the leaf node we find out that it's that it's been
29:02 removed so if you're really memory constrained and you do something really stupid like you only have one uh you know you only have one one um one frame in your buff Pole to store store data then you might be like doing a having a buffer pole Miss for every single entry as you go down only to find out when you get once you get to the bottom that the key that you're looking for doesn't exist
29:28 so an alternative to a b+3 is called a tribe and tries are actually older than B+ trees tries are like from 1959 in invented by this this French dude uh and the B plus as we said last class was 7 1970
29:42 1971 and the inter thing about the tries is that you're not going to store the entire key uh at any one given node you're actually going to break up a key into its digits and I don't mean like a you know Arabic numeral I mean like sort of like one bite or one one one you know one sort of atomic unit of of of the key
30:03 and we're going to store that as at our nodes as we go down so to reconstruct the key it's actually the path from the route to the leaf node that gives us back the the data the key and not the indal key
30:17 itself so like I said these are really old sometimes you'll see them call digital search trees or prefix trees I think prefix trees is more common um and actually the the term triy means retrieval tree and it was invented by or the the French guy invented the data structure and then this guy Edward fenin coined the term try he's actually is or was I think he's dead now he seei a faculty right for the longest time he was on the website of the The Faculty list I never saw him uh any faculty meetings but he was still listed as being here so the guy that coined the term is was from
30:50 CMO all right so all the operations are going to have this complexity of okay where uh where K is going to be the length of the key because again may have a key that's really short I may a key that's really long and depending what key I'm looking for that's going to tell me how many NOS I have to go look at so we can jump through this really quick I think everyone is familiar with tries but say have a key hello again
31:10 when I want to do a look up to see whether it exists I follow down the the path into my uh into my try and that's that's going to find the key for me so the span of the try is going to be uh equivalent to the number of bits that we're going to use for each digit representation right
31:28 and the as we go down we we can start storing all the the the different bit combinations within a bite or something what whatever we're deciding how to chunk the thing chunk the keys uh and then if we if the thing you're looking for has an entry uh for the given key then you have a pointer to the next level for the next digit in the key otherwise you have a null and therefore if you're looking down that going down the path you know couldn't exist down below and you can
31:54 stop so the span is going to determine the fan out of of the uh of of each node and it's also going to determine the height of the tree because again really long Keys is going to give me a really long
32:06 tribe so let's see a s really simplistic uh uh try with representing one bit and we're going to see is how we can lay things out in in the data structure and we'll see how we can apply some optimizations to actually compress it
32:21 and depending on whether the data structure is mutable or not then some of these compression schemes will work for us some of these these won't so I have a one bit span try means every single level of my try it's going to correspond to a single bit within our key and again in a real system you wouldn't actually do it on a bit bit by bit level like this or one bit try uh you would do typically on a bite or some larger chunk
32:44 so say I want to insert Keys 10 25 and 31 so I can represent them as uh as 16 bit integers again assuming there were 32 or 64 bits you would have the full Keys uh ignoring bit packing optimization but you know assum that's the cas for for Simplicity all right so the DAT is going look like this right where again at every sing level there's a zero or one and if the key had exist in our set when we when we inserted
33:11 it uh if they have the value for that digit will have a PO or two the level below us right so when we want to do a look up we start the very beginning here which is again the first bit offset again we check to see whether the key we're looking for has a Z1 this case here we only have zeros when we inserted it so we have a pointer from the zero position down to the to the next level in the try
33:34 and the one we just leave is null right then we go down here and and for Simplicity I'm just showing this repeat 10 times because we have 10 positions in our in our in our bits or sorry in our integers they're all just set to zero right so just repeating over and over again having the uh the the zero bit set to a pointer and and everything else is is null then we get to the next discriminator here the first sort of discriminating uh bit position
34:01 and now we see that for some keys we have a zero we go down this path other Keys we have a one we go down the other path right and then for here you we see basically it's alternating back and forth between 0 1 01 and we have uh at each level just one pointer coming out and at the bottom just like it was in the the B plus Tre this the bottom position would have this uh either record ID or a pointer to or whatever it is that we're actually the the data structure we're pointing at
34:30 same thing on the other side here we have discriminating bits and then we we have a branch going below right all right so what's one optimization we can do for this to reduce the size of it and the advantage again reducing the size means that there's less CPU we have to spend to do lookups on it
34:48 yes right so he's correct he said if if you know that there's a single path there's one pointer coming out of one level uh down below it and you see this over and over again you can actually vertically compress them you can compact them right you know the second one the repeat 10 is is obvious example of this what's another optimization we could
35:12 do so what yes sorry right so you move the zeros and ones right so implicitly if I'm doring zeros and ones it's either the first bit or the second bit why store zeros and ones so I can horizontally compress each level right
35:28 and you end up with s sort of well we did the the horizontal compression that he proposed uh but now we can also do the the vertical compression that he propose and you end up with something like this so this is what a radex tree is radex tree is just a specialized form of the try like thing is try as the general TR data structure but then you can do this optimization compress it and you end up with what is known as a radex
35:52 tree sometimes also called a Patricia tree I don't know why I don't think there was anybody named Patricia that invented it it's just I probably should look that up where chat gbt what that is right but we've done the vertical compression and we've done the the horizontal compression right and another thing we've also done too is going back here uh we actually just cut off these bottom parts of the data structure here because there's nothing right it's just from the from the top to the bottom we're just going to always end up pointing to this outbound pointer so we cut all that off and now we have a shorter tribe now this example here actually could produce false positives
36:29 because I look up my try I follow the keys down follow the bits down and I and I and it says yes here's the point to the thing you want but then when I follow along then I find that the key actually isn't what I want it so you still have to do the extra check like we saw in Bloon filters where you know it told me it was there but I actually go really if I really care go really verify whether it's actually there or
36:48 not right so tries are used often times uh to replace B plus trees or even the skip list like in Cassandra they were you know Cassandra was using it's a log structure Mer tree they were using skip list right in the uh for the M table they switch to use a
37:10 TR and then other ones other other systems replace um replace a b tree entirely with with with tries or something called Art the Adaptive radex tree um and a bunch of these systems are using that right so the Adaptive radex tree started off in hyper this is a very influential German system uh at a tu Munich and then the ducky B guys basically copied a b a lot of the ideas out of hyper so duct B doesn't have a b BL tree as far as I know it has a radex tree and then Umbra was the followup to hyper because hyper got bought
37:45 by sales Tableau or Salesforce no they got bought by Tableau and then Tableau got bought by Salesforce so if you run tap low now they have an in memory cache it's running hyper um theym but then umbrella is the to it and then solid DB and gun I think are using uh just just radex trees not specifically the German try right and then there's actually a commercial incarnation of umbrella called cedb which again is just a fork of the I think it's the fork of the the original
38:13 unit code all right so quickly want to talk about how how you actually support modifications in a try uh again there's depending on how the data structure layout there's different approaches to do this I just want to show you that like it isn't always going to be immutable data stru and then you can make decisions how to adapt things and and and merge up and down accordingly so say iert the key key hair into this again I would follow my TR down the ha then I land this node here assuming I have space I can put the IR at the end and I have a pointer going out to the tubal but now say I want to delete hat same thing I follow the H go to the a go to the T find the entry that I want I go ahead and delete this and again I can decide whether I want to if just leave it there or not all right and and merge it up or leave it where it
38:59 is but now let's takee here I delete have then I follow go ahead and delete that and then now according some threshold it isn't like the the the B+ tree where you say if I'm less than half full then I have to merge you could just leave it you know you you could just leave it empty or having one enter there if you want it depends on whether you're willing to pay the uh the performance penalty to do the merge but let's this case here I do want to merge it so then I just slide it up here and I could pend to the a up above which was the only discriminating key to get me down below
39:28 and everything's still correct again so tries will be used again in many cases where the um often times will be more compact than a B plus tree as well because you're not repeating Keys over and again like every key will only sort of exist in in a in a form by
39:49 itself or only once okay so any questions about tries rad trees yes false the question is when would be false positives so going back here so I have this uh I have this bit you know this commun levels going down here and then what I was saying is after this discriminator mean I have pointers going both directions when I land here it's a straight path down to the to to the tubal pointer right so in a radex tree I would compress that means
40:27 cut off that that branching that P branching path entirely and now up above instead of having the pointer to the next level I have a pointer to the tupal right so now someone may do a look up on the key what is that 0 z
40:44 z right but they might have z z it might be z z z like four zeros or three zeros and then a one and both both of those keys is always going to land out on this pointer here so when I go then look at the Tuple I got to go see whether the key actually really does
41:04 exist yes so so in this example here you would only match the prefix of the key and that might be okay right it depends again it's classic compute versus storage trade-off okay so we finish up in in uh 20 minutes
41:29 good all right so in all the indexes we talked about so far you can use them for Point queries or range queries Point queries is like give me a single key and you know tell me whether exists or not get get the Tuple right finally all the customers that have you know the ZIP code 1527 could be a a producing multiple tup or single but the IDE is like you have one key discriminat discriminat looking it up and it's also used for range queries
41:57 so find me all the orders within some some kind of date range but they're not good if you want to do keyword searches where you actually want to look at the contents the inside of a attribute's value and look at sort of a portion of it rather than the entire thing right if I have if I have a column on on for zip codes that I'm doing my my first look up on it's the only thing in that colum is going to be the ZIP
42:23 code but if I'm storing say all the Wikipedia articles that exist my database and I want to find all the Articles where the word paavo is in it then all these data structures we talked about before aren't going to be good because how would it work right I would have to take the the the content field and build an index on that that doesn't make any sense right because I again I want I want a portion of it right so going back here again assuming this is a is a small mockup of the the um what the Wikipedia schema looks like if I build a B+ index on revisions on content then I can't really use it to do uh a predicate like this finding all the content where wild card Papo wad card
43:07 exist right because it's it's going to you can't use the index because to do that traversal down my B plus tree I have to have the entire key right actually this quer actually won't work either is actually technically incorrect as well because it's going to find wild card Pavo Wild Card meaning like if there's there's like another character at the end of paavo it'll it'll match that like that Russian scientist Pavo
43:35 right so actually this query also won't work either because I actually found out yesterday they removed the the Wikipedia article about me on Wikipedia and the reason I found out is that I got some spam email for some guy trying to get money out of me to get me to to get the Andy Andy Pablo article back on a Wikipedia uh so anyway it's a scam I'm not giving a money
43:57 anyway so I'm not on Wikipedia anymore all right so this is what an inverted index is going to solve for us right sometimes called a full text search Index right the idea is that we're going to have a mapping of the the we'll call it terms of the the sub elements of a of a of a value in our in our in our in our tupal for a given attribute and now we can do those partial lookups we want to do is find all the entries where this thing
44:23 matches all right this is originally called before Computing was called concordance right this has to do with like they would had people in the old days literally read books and find basically buildt the glossery find me all the pages where this thing exists like some some guy did it in the 1200s uh in Europe where he had 500 monks read the Bible and build basically a full text search Index
44:46 right so many of the major Data Systems that you care about will have some flavor of a full Tex index or inverted index that we'll talk about um but the the more specialized ones there are all more specialized libraries out there datab systems that are be actually way better than what the uh what like post will give you or what the other syst will give you and I'll talk a little bit about that so basically what the inverted index is going to look like is
45:13 there's going to be two two pieces there's the dictionary and the posting list so the dictionary is basically all the extracted terms you want to call it that right it doesn't have to be words could be other elements of of a of a value right there'll be a dictionary that's going to maintain all the terms and then the frequency in which those terms exist and then they'll just have a pointer
45:32 to uh a posting list where every single term here's all the record IDs where This this term exists right so so in my example here right there's three articles about that mention the word carnegi right and so I I have my my frequencies set to three and my posting list has the the record IDs or what whatever it is unique identifier for those three entries
45:57 so now when I want to say go find me all the Articles where you know the term wuang appears I would check this that's a quick lookup we'll talk about how how we find that in a second find my dictionary I get my pointer to my posting list and now I can immediately jump to exactly those those records that have the value that I
46:15 want versus having to a sequential scan and look at all the the values and basically split the strings or parse through it to try to find the thing you're looking for right you you're precomputing this index so as I said there's a bunch of libraries that provide these data structures the most well-known one is this thing called Lucine right it's in written in Java there's a one in C called zapan and then the new one is this tant tanivi uh which is not written in Rust think of like Lucine but in Rust
46:43 and we'll have people coming to talk about how they use that I I think next week the prb guys use this um and then again it's going to provide the dictionary and and the posting list that we'll talk about I'll show the next slide and then there's a bunch of systems that take these
46:57 uh these these you know inverted index libraries and build larger D systems around them the most well-known one is elastic search uh Sol uses Lucine solar uses Lucine I think Sphinx does as well uh open search is Amazon's Fork of elastic search because elastic search changes their license uh to make it less friendly for cloud vendors so they they a hard Fork
47:22 uh elastic search didn't realize that was a mistake and switch back their license like two weeks ago but by then open search is kind of uh Rising prominence um so anyway but at their core they're both just using Lucine and have like a sort of friendly nice interface and other features around
47:39 it and then best Splunk is actually spunk is much old spunk is very expensive and that's like that's very common in Enterprise world I think Cisco just bought them this Summer all right so let's talk about roughly what Lucine looks like and then we'll talk about what pcus looks like for these uh um um you know for these index so for luine the way they're going to organize their dictionary is through this FST or finite State transducer and
48:08 it's going to look almost like a try where it's G to break up the key into individual digits but instead of having at the like the leaf node of the the data structure the pointer to where I need to go actually the the the weights on the edges in my data structure it's going to tell me how to compute the offset to where I need to go that's a neat little trick and they're basically going to increment they incrementally create dictionaries for individual
48:34 records as they're inserted into the uh into the into the database so that sort of each dictionary is localized to some some subset of the documents then in the background they're going to do like the compaction stuff we saw in the log structure merrye they're going to start combining the segments together to make larger dictionaries and reduce the redundancy reduce the you know repetitive repeated values in the dictionaries so say that in our dictionary we have four Keys BR brav pav and in pla and so the finite tranducer will look like this where I'm going to again break up the digits and then each Edge is going to have a weight that's going to tell us how we get to to the bottom here so now if I want to do a look up like find paav as I Traverse
49:19 into my data structure I'll keep a rolling tally of the the offset based on the weights as I compute them and then when I'm done I you know hit a terminating node in Black here that's going to tell me okay where I'm at now I need to go look at uh you look up and that's going to tell me how to get where I need to
49:35 go all right so first first uh first character in pav is p so we land here and now our update Al that should be two not three sorry right then we follow this weight down here updates by one that should be three um and then this weight here you can have weights of zero that gives us uh three we would jump to that offset there right I'm off by one down there so this is like a different form of a try and because it's immutable we're not worried about maintaining this on the Fly we would we would have all the keys and the offsets ahead of time because the the dictionary is going to be
50:11 sorted other the interesting thing is that they're all they're going to use all the same techniques for compressing things that we talked about before because you're going to have this these immutable data structures and a bunch of the bits C the values we all laid out almost in like column in a column order like the posting list is just a column of of of integers so they can do Delta compression they can do bit packing they do all the things that we saw before with column
50:36 stores Lucine can also do some extra stuff like precompute aggregations for terms like rolling counts and things like that so now when do look up like count the number of times a a given term exists in all my values right I could just go through that frequency list very quickly and they have a preut they can preut one so so you don't have to look at every single segment separately
50:57 so Lucine is widely used and and it's it's pretty well optimized at this point so let's see what postgress does so postgress has this thing called The Gin the generalized inverted index and essentially the the dash structure they're going to use is going to be a forest of trees so they're going to use a B+ tree for the terms the dictionary and then the values in the or you know the keys or the terms and it be the entire Keys again we're not trying to store the entire Wikipedia article
51:24 we're breaking it up into uh uh in into terms and then storing that so then the values of this initial dictionary B plus Tre will vary depending on the number of records that uh correspond in the posting list so if you have a small number of of Records a few number of Records then the posting the posting list is just going to be a sort of array right that's just sitting in some page that's fine but if you have a lot so you can set a threshold to say if my posting list grows to this size
51:54 then they stop appending to this really long list because now if you if you have to find you know individual records you know you don't have to do you don't doal scan or binary search on this they instead will then create another B+ Tre that just has the that just has the the the the record
52:13 IDs also similar to we saw in um in last class we saw the the B Epsilon tree right where they had this mod log at every single node to absorb all the rights they recognized that if I do an insert into a into a table where I have one of these uh inverted indexes on say I have you know it's a it's a a large Wikipedia article I got to break it up on all the terms then have to insert all those entries into my into my dictionary
52:42 and now I'm doing all the splits stuff that we talked about last class and that could be expensive so instead what they'll do is they'll have this mod log on the side called the pending list they insert all the pending updates into that
52:53 and then occasionally when when this thing gets full then they'll they'll do uh they do a compaction and apply all the changes into the dictionary and you can do that bulk insert we saw before where you sort the things ahead of time and sort of build things from the bottom up so when I'm going to do a lookup now I got to first check the pending list like we did in you know in the M table
53:10 check see whether the thing I'm looking for is in there and then if it's if it's not then I got to switch over to the the full dictionary depends on what the query is again the solve the different problem then the plus Tre right and these other indexes because we're not trying to do again the point quer is we're trying to find find the things that have this the contents that I'm looking for I'm not going to talk about this there's a whole another class at CMU that does talks about you know text searching full text index indexes but
53:42 the like the things like Lucine elastic search have a bunch of other stuff that uh that go beyond what we talking about here like they know how to break up uh break up um to to normalize the the data you're storing in it so that you have match you can do fuzzy matches so for example if I have like wuang with a hyphen without a hyphen uh you can have your full text full text index or inverted index recognize that these things are actually really the same so if you see one you know it should map to the other or say like USA with with the dots without the dots those things should be equivalent based on the semantics of language and therefore they know how to handle those things like so they're not really just taking the RO
54:24 words they're not splitting on strings they're they're doing a bunch of other tricks right or they can throw away common words liketh to no yes things like that so inverted indexes are all about searching data based on its contents again as I said you can be a little fuzzy about
54:42 the the the the what characters are in a word and whether they match or not but a high level you're just trying to see does this thing exist in my in my data but sometimes you want to search on the semantics or the higher level meaning of what's in the data and if you're just looking for keywords or the terms you can't do
55:03 that right so instead of just finding all the the records with the can words mang say I want to find all the the records where there's lyrics about hip-hop groups you know sling and rocks what does that even mean like the D doesn't know what sling and rocks means doesn't know how to map that to a certain activity uh so if you try to do a key exact keyword search on inverted index this will produce
55:28 nothing so this is where the vector indexes come in and I sort of mentioned this briefly at the beginning in the semester but the idea is that we want to we want to rely on these embeddings that we can generate through Transformers
55:39 like things like opening eyes and the working on or the Bert from from Google that know how to take sort of arbitrary text or whatever data we want to store and then it spits out these floating Point arrays arrays of floating Point numbers where somehow embedded in those those numbers is a higher level meaning or deeper meaning of our data and then now when we do lookups like you know you know my example like trying to find find all the the the lyrics where they're slinging rocks it somehow knows what slinging rocks means knows that there's a bunch of lyrics talking about similar activities and therefore those those embeddings should should somehow match
56:15 but it's never going to be an exact match and so we have to rely on nearest neighbor search or approximate nearest neighbor search right find me the embeddings that are close to my embedding cuz somehow that somehow they're they're they're meaning somehow they're similar to each other so this being really different than all the queries we've seen before because there isn't going to be an exact correct answer because you don't know what the embedding actually is producing right it's not meant to be decip by humans and so when a query comes back with an answer there's no magic Oracle you can say yes this is I know for a fact this is the right answer I think of like I I have billions of records how would I know know within that billion that like the the thing I'm getting back is exactly what I
57:00 wanted right so it ends up being like what feels right what feels correct so there's a bunch of these Vector databases that are out there that have Vector indexes I'm actually showing that the vector database specific ones but as I said before a lot of the uh relational datab systems have their own flavors of these Vector indexes and they're standing on libraries that everybody's incorporating uh that that are built by other people so I want to talk about the the sort of the two basic approaches to this the the the inverted file ones and then the the the small worlds and I I'll just talk about a high level how to do this uh again there's other classes that that teach us but we we care about how we actually incorporate this in our in our database system and one of the big challenges
57:42 that the vector index uh you have to face is that the vector index will be lookups on the embedding but often times I want to have additional predicates of my wear claws that aren't going to be captured by the embedding right find me all the the lyrics where they're talking about slinging rocks n was written after
58:00 2015 2015 isn't going to be in the embedding that's going to be an additional attribute so now I have to decide do I want to filter on 2015 first uh then do my uh nearest neighbor look up on the vector or should I just get a bunch of vectors and then itly check to see whether they're you know the year is greater than 2015 which make me means I have to keep going back and if I don't have enough answers right if I'm throwing away too many
58:24 things so this is what the the the the pinee guys and we8 guys claim they they have have solved it's not clear the we8 guys more VOC about they're doing they're basically you'll when we talk about the the the graph structure the small worlds they can store the metadata in the nodes as well so like you don't have to go back and look at a separate index and look
58:43 up all right so the most basic one is do in inverted file the most common one is this IV IVF flap and the idea is that you're basically going to take your your vectors break them up to smaller groups using some clustering algor like K means pick your favorite one and then the idea is that when I want to do a a look up to see find me the nearest neighbors for my my lookup Vector uh embedding then I would land in some group and then just look around me to find the entries that that are close to
59:12 me right so you would take your say this is our Vector space we're plotting it down in two dimensions and then we use whatever K means clust you want to put them in groups right and then we have all the other vectors are hanging near the centroids for all of them so now when my my query comes along it gives me gives me a vector right I would land in some kind of space like this and I could just check whatever in the the group that I'm looking at just squally scan through to find the um find find the nearest neighbors I may want to check other nearby groups because maybe that'll improve my accuracy right I could build an index or do other pre-processing like quantizing the the
59:52 the the vectors as I'm storing it I still I still want to keep the original one but in this Vector index I'll I'll quantize them to be lower Dimensions so that my lookups are faster and without reducing accuracy but it's a really simple divide and conquer approach right I just do this this this clustering to land in some space where I know the data that I want should be close to
1:00:14 me the other approach is to do navigatable small worlds I'll show the the single one that's s single level but you basically can extend this through multiple levels again I think another class covers all this kind of stuff but the the idea is that we're going to have a graph structure where we would have we would specify how many edges we want coming out of the nodes that ises correspond to its nearest neighbors and then we have some entry point into our data structure that tell us where if we want to do a search where do we start
1:00:40 and then we just follow along the path in in this graph choosing a path that gets us closer to where our our Target Vector is so say our our our our query has some some some embedding right and that lands in the space here so to find the nearest neighbors we start at the entry point point and this again just follow along the path and find all the things that get us closer to and then at some point we'll get to a node where we can't get any closer and therefore our search
1:01:06 stops and then we can have multiple levels below this if we want to have additional things so I think uh Facebook's fast is probably the most well-known one of these uh that's actually worked on and then I think the original authors have this hnsw Li uh Li uh Live library you could Pally use as well but a lot again a lot of databas systems are using a fast one I think Pine con actually uses fast as
1:01:30 well okay so finish up so we're going to see filters again as I said multiple times the semester B plus trees are almost always going to be the the default Choice still over tries over R trees over uh or definitely over skipless um
1:01:50 and as I said the inverted index will go more details in in uh I think this is an LTI 1142 like they cover how to do the tokenizer they cover how to do all the the language modeling stuff all that is is in that course there's a whole another category of data structures we didn't talk about these multi-dimensional data structures things like R trees quad trees KD trees think of like geospatial things like if I have a a two-dimensional space how do I know my Point's going to land if I have a given point what what you know what
1:02:18 polygon does it land in right often times this is how they basically do look UPS like find me uh you find me shortest past and things like that in in in mapping um in mapping systems so that's covered in 15826
1:02:33 multimedia uh databases and that's called taught by Chris flutes which I I think he know I know he's teaching this semester he may not be teaching it next semester but again there's all these other data structures that do uh can handle multidimensional data much better than a you know regular b+g that we talked
1:02:50 about okay all right so we're switch over now to do the the talk from tidy B but next class will be how do we actually make our our indexes thread safe which is something we've been glossing over entirely throughout the entire semester
1:03:05 uh but now now now we'll actually understand like how that all works okay let's see Sony can you hear us yeah I'm right I'm here okay I got to turn up mute there we go all right Sun now say something sorry there we go can you hear us yeah I can hear you now yes all right one can let me make this full
1:03:35 screen and slide you over are you do you have in slide or can I say how awesome you are on my own must be something wrong with my audio I couldn't hear that all right let me uh let me check what see mic I'm on one
1:03:52 sec um do let's do is that better can you hear me yeah I can hear you so the echo's gone yes all right hold on let me do you can't see the class but I'll do you can look at me if you want okay I can't all right uh this is oh let me turn up the recording this is all correct so this is sunny um he used
2. Jump to
1:04:18 to R my SE for 20 years he knows everything about my squel but he's not at my SQL anymore he's with uh tidy B so Sunny the floor is yours go for it okay so this is a high level view of tidb and if there's one thing that I want you know people to take away from this is how does tidb handle scale and what the core idea is and the rest I think you should be able to figure out
1:04:40 so uh so what are the data growth Trends just I'll quickly go over all this a brief history of how tidb came about what problem it's trying to solve the general architecture and what we're trying to do next so these are the people that use DB so it's used by all the major companies and by Banks it's like a general purpose database that can handle petabytes of data so I just so this is roughly the way the data is growing every year I stole this from some site that obviously gives
1:05:10 statistics and as you can see I mean it's just getting out of control so this this is the problem that idb is trying to solve and if you look at 2014 that's when the founders of tdb were working for a company that was growing very quickly and then the data wasn't growing as much but it still was quite a lot so it was the best of times worst of times business was growing but handling that data that was coming in was becoming huge problem and there were hundreds of terabytes and the only solution in those days was manual sharding and resharding and it used to take forever weekends were short and so it was pretty bad and keeping consistency across shards was a very difficult problem because all they had was myql replication at that time and
1:05:56 so then they discovered spanner so spanner came up with this idea that you split the data into chunks and then you uh move it around and you have some kind of pxas or some kind of consistency protocol over it I won't go over this I'm sure you can read it from the Google spanner paper but spanner was proprietary and not open source and special Hardware is required to run spanner and the founders of tidb wanted to run this on commodity hardware and uh on standard SQL and not some custom SQL with some custom protocol they wanted to support MySQL because that was very popular it's still quite popular I think the second most or the the most popular open source database anyway so they decided to go with the MySQL protocol so this is the core idb design philosophy it's shared nothing architecture
1:06:44 developers should not be concerned with chart details developers should not have the should have the flexibility to Control Data placement so tidb also it does it automatically but it also gives you SQL to do placement on a rack in a particular host or the data center region and those sort of things as I said earlier standard SQL and uh you should not have to have any specialized interface and in order to support the distributed model of data that uh spanner sort of came up with and tidb
1:07:14 implements uh we need to provide strong transactional consistency guaranties out of the box so that it's easy to reason about the system and flexible read consist consistency Pol policy should be provided it is highly available but not at the cost of strong consistency so consistency is extremely important it just makes it easier for people to reason about things and uh reduces the risk and Corruption and those sort of things these are like hard really difficult to deal with in the production
1:07:45 system so this is the general architecture so you have a metadata server those are the PD cluster PD is as placement driver but it's really a metadata process and there's a cluster of them it's managed the state is managed through the PD instances themselves don't have any state they're all stateless uh and the tidb nodes that in red are also stateless the state is all in the storage cluster also there's an etcd uh instance running with the p PD where PD state is stored so PD is really the brains behind Tai KV so if for example a query comes into tid V the frontend SQL nodes the ones in red it has to ask PD where is this uh region or
1:08:33 tablet located and so it tells it that's the address you go to such and such poost and that's where the current leader of the raft group is and you can read the data from there so this allows for distributed execution of uh SQL query so let's say a query spread out across n shards or regions or tablets whatever you want to call them it can issue a request in parallel to the different T this B the blue nodes that you see there additionally it has an optional component called T flash so this is a column format version of the same data it's a copy of the data they do not participate in the raft election
1:09:07 that's the only thing they're just uh learner nodes they just read the data from the raft the raft messages from the log and convert it into a column store and that's and tib can the optimizer can even send sub queries to the column store in case it makes more sense to do an aggregation or a file scan or whatever on the column store so this is the high level thing so what is this thing mysterious thing called region oh hang on first we'll go to Tai KV so ta KV you can think of it as a rock DB uh distributed rocks DB and so it has an a key value API it has a transaction model which is percolator it's a modified version of percolator which also comes from Google and it uses raft to
1:09:53 distribute the region and underneath is one instance of Rox TB per ta KV and there's a thing called a CO processor so this is used internally for query push down I won't go into the details of that but it's essentially
1:10:08 aggregations scans and those sort of things can be pushed down so that they are processed closer to the physical data and reduces Network traffic and then they send the summary back to the SQL nodes and then they the node that issued the request can then collect them all and send the result back to the client so that's the the idea so just to give you an example so imagine you have a very large your entire database is composed of one table that's a way to uh imagine it in an abstract sense and there is some special encoding of the key that allows you to Separate Tables indexes and what not and imagine you can each of those uh that entire table is chunked up into the
1:10:48 regions which are by default 96 megabytes it can be changed but that's what they are so imagine and and they're all ordered and imagine your data is ordered and you can chop it up and each of those individual regions is a separate raft group and those regions are spread out across your ta KV cluster
1:11:08 so if you look at this uh like those disc type things you'll see there'll be uh I hope you can see the arrows so the there are arrows pointing from uh region two to one region uh 3 to1 so all that means is that where the arrows actually uh region one would be the leader region
1:11:28 so that's where the current data is it's quite possible that if the data has only been synced to region one and region uh like the first and the the leader and one follower and the third one is still in the process because that's all that the consensus protocol really requires
1:11:41 so T ta will always read from the leader it always gives you consistent data in theory you can read from the other regions but we don't do it simply because it's better to be correct than to be fast faster
1:11:56 so so if you understand this you'll more or less understand how ta's storage is scaled out he just chunks it up uses raft per chunk to spread the data around and PD monitors the health of all these nodes and PD is the one that knows where the data is actually located so that's the that's why it's called the placement driver and it also monitors the hotspots it monitors how much RAM is being used how much iio is being used uh how much free space there is uh all kinds of metrics and then it will also rebalance
1:12:27 to so that the load is spread evenly across your cluster not all your machines have to be the same size so it has to or have the same amount of capacity so it has to use all this information to cleverly place or move data around if there's a one of the nodes goes down then it does an election over uh the regions that were the leaders on that region so that is all localized to a region rest of the cluster can keep going if that uh if those Reg are not being accessed by anybody so that's how basically it
1:12:59 works so a region is like a logical scale unit so load balance scale out scale in are all balanced on regions so if a region shrinks I mean you delete some data it can uh merge the regions and go back to whatever it previous state was so they as I said you know they're replicated using the raft consensus protocol and each region is a separate raft group that's why we call it multi raft and the spread uh spread spread all across the cluster and a single node can contain many regions and regions are stored in rock TB and there is one rock TB per node so and rows are the key point is the rows in a region are
1:13:36 ordered we don't support hash partitioning so the distributed transactions in tidb are based on uh percolator so it supports supports read committed and snapshot isolation and the snapshot isolation because it's uh supports the MySQL protocol it's mapped to in odb's repeatable read There are some minor differences but we can we won't go over them now and a transaction require like it requires a start timestamp when it started when it ended so it's required for mbcc and the component that is responsible for handing out these timestamps is the placement driver which is why I said it's a metadata server it does more than one
1:14:20 job so tidb supports async commit and in this it uses two-phase commit and in this it the SQL nodes the front end SQL nodes which are stateless otherwise they actually in reality they have a little bit of state to optimize the distributed transactions actually uh but it's not like a permanent if it goes It goes but it does have they do try and store some some State um the TA nodes are the participants in the two-phase commit and
1:14:49 it works extremely well when the transaction right set is small and phase two time dominates so phase two in this case would be so you've sent out what you want to do and it's uh let's say these are the the first phase would be notifying all the changes you want to make and the second phase is when you you get
1:15:09 the uh a the ACT back saying that yep we can handle the second phase and so then it sends all the data that needs to be sent uh to all the different nodes and pass around so all this is handled through the raft log actually so if you only modify one
1:15:27 region or you insert a record without a second index because it would go to a second region uh it can do all this in a single one phase commit so if if your rights are small and they only Touch One region let say small batches or with that fit within a page it can do single phase commit basically the raft L you write to advance and the raft log is your
1:15:52 uh point that guarantees durability but it's nothing is perfect so as I said the data is growing massively so how do you improve stability at scale copying data so you add a new node moving data around becomes expensive before that node can start serving requests and before the data can be moved it can take a long time depending on the size of the node and your data compaction with in LSM trees is a huge problem and because there's one LSM and if your data is huge
1:16:21 uh it can become a big pain a really big pain so how do you solve all these problems so data volume is huge now we have customers asking for 200 paby clusters I mean this is in my mind it's ridiculous but that's what people are asking
1:16:38 multiple act so people also want to reduce cost they want to share a single cluster across multiple applications otherwise the complexity of managing things and the cost also goes up so you want to take the maintenance burden of a distribut distributed systems are difficult to manage so you want and also tradeoffs that you made in the design of your system they become knobs that you have to constantly tune and Fiddle with to balance your system manually so it is it just adds to the
1:17:06 complexity so you also want to scale down when the workload reduces so when you provision your system uh and you do capacity planning people obviously plan for Peak traffic but you don't get Peak traffic all the time maybe like these you know sales that like this Black Friday s or some other gimmicky sale thing that they have so the traffic will PE but most of the time it's low and you don't want to pay for all those instances so you want it to be elastic in the true sense so you want it to scale down and only pay for let's say if your instance is a quent so you only want to pay for storage cost not for all the networking and everything else that goes with it so that's like the
1:17:48 ideal so we wanted to Leverage The Cloud infrastructure so that a developer can start small and scale to any size so one of the things you want to do which is one of the cheapest things at least on AWS is S3 and
1:18:03 S3 the it's the costing is very interesting the amount of data you send it is not such a big deal it's a number of requests that you make so if you have your database doing sending every request to S3 it becomes extremely expensive but the size of the data is not such a big deal so you have to balance these two things so you want to leverage that for elasticity and resilience S3 is very resilient it is actually a fantastic system and you want to leverage that and other things in the cloud to but in our case let's say storage is like a very big thing and you also want to hide the complexity so you don't want people I mean you just want people to connect to a point run the queries and it should scale automatically it should scale down
1:18:45 automatically and you shouldn't have to worry about any of that stuff and you want to integrate like a reg it should be like a regular database and work with other uh services like I said earlier the only cost of a we instance should be storage and nothing
1:19:02 else so we came up with this thing called Sunny we're out of time want show show one last slide oh okay I'll just show this slide this is a new storage engine that's it okay all right uh time for one
1:19:17 question so you showed us SL said 200 pedabytes that's little of data that's a lot of data who has that kind of data not you guys like what what what organization in the world has 200 piz of data think like
1:19:37 acony they keep everything Sunny can't say it but I'll say it right right the has that kind of data it's a lot and it's hard right and so I say one more thing also too son said tidb started in 2014 the rule of it takes 10 years before your dat actually becomes good useful and safe it's 2024
1:20:00 it's 10 years right do the math all right let's get Sunny Round of Applause thank you all right again so uh if you have not started project one that's a huge problem it is due this Sunday if you're struggling in Project one that's a big problem
1:20:18 too do something I need something refreshing when I get finish manifesting c a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme and my pants intoxicated lyrics are quicker with a simple Mo lier since on mer City Slicker play Waves a picker rhes I create rotate at a r too quick to duplicate feel a breeze at escate mik's at fahren when I hold it real tight then I'm in flight then we ignite what St the boil I heat up the party for you let my girl R me and my mic down with oil Rec still turn a third degree burns from one man I heat up your brain give it a Sunan
1:20:59 so just cool let the temperature rise to cool it all was odds [Music]