Video 7-4: Cache-oblivious B-trees, vEB layout, file-maintenance

0:02 In the last little bit of this unit on external memory, I want to look at a um a theoretical curiosity with some um sip over to practice. I think it's uh full of some beautiful constructions and that's the idea of a cache oblivious algorithm or data structure. Uh as the name suggests, this is uh designs that should somehow not need to know that there's a cache. But of course, that's easy. you just ignore it and be slow. The point is you want to not be specifically tied to a particular architecture but still be fast. And you can do this in a surprisingly strong sense. Uh the the cache oblivious model I guess I should say the CEO model cache oblivious model is like the external memory model that we've worked on in this unit all the time. But the algorithm is not allowed to know the values of B and M. And that's it. It's a pretty clever simple idea. Um, and then of course the hope is that the algorithm is uh optimal simultaneously for all choices of M and B.

1:13 Parenthesis maybe with some restrictions on on suitable choices. Maybe you don't want M divided by B to be tiny or so. But uh for for sensible choices we want the algorithm to do well no matter what M andB are. And uh so whether you look at the boundary between CPU little cache and main memory or main memory and disk or whatever level you pick if the algorithm can't tune itself to the parameters but has to be simultaneously good for all of them it will be simultaneously good for all of them. kind of a tautology club statement.

1:53 Now, of course, you could qu you could ask cool, but why would that even be possible? This sounds like asking for a lot. And we've seen a simple example where it is possible scanning an elements, the algorithm didn't need to know the block size. You just read one element after the other and it so happens that uh you fully use one block before you go to the next and that's optimal. So these things in principle can exist at least if your problem is sufficiently boring. Okay.

2:23 Um to make the model theoretically sound uh there's a few terms and conditions. Uh we're assuming an ideal cache. Part of it is to make the arguments easier. Part of it is crucial. Um first of all we we'll assume a fully associative cache. If you've not done some technical computer science, maybe you don't even know what I'm talking about. uh then forget about it. The point is that every position in the uh cache is supposed to be able to be eligible to hold any block of main me of the external memory. Uh this is standard if you look at memory to disk but is not standard for low-level caches. There is kind of a lie. Uh but we assume this either way and we assume that the decision um if you load a new block you usually have to evict another block because your memory is already full. Maybe initially that's not the case but after running for a bit. Um we haven't talked about this at all for external memory algorithms. And the reason there is that we assume we know M andB we tune everything to the hardware. So we decide exactly what block is evicted. It's part of the algorithm to say, I'm loading this block and I'm kicking out that one.

3:36 Now, here, this seems not to go well with the spirit of cache obliviousness. Uh, if the algorithm can't even know how big the blocks are are, how is it supposed to say which block to evict? It doesn't know there's a cache. So instead, we'll make this bold assumption that the cache uses an optimal offline eviction policy, which is 100% unrealistic. For the analysis, we can do that, right? We can just pretend. Suppose the algorithm for the cache knows the future and knows which page is going to be needed the furthest into the future. Again, kick that out. That's optimal.

4:17 Uh questionable. Um I'll I'll come to that in a bit. Uh actually right now um this is not as bad as it first sounds for the following classical problem or classical results that um uh we touched indirectly on but not really. There's this uh online algorithm the least recently used algorithm and that of course is not as good as the optimal offline. However, if you give it twice as much memory, then it's only twice as bad as OP, even though OP knows the future. This is a pretty pretty cool uh kind of powerful result because it tells you this this least recently used is really a sensible choice. And in the context of this cache oblivious model, we'll ignore constant factors all over the place because we don't really have a choice. uh you'll see in in in short bit why and so here um if you allow a constant factor blow up in the memory size or tune the parameter divide by two in the analysis result then you get essentially the same if you use LRU uh compared to this. So this is easier to analyze or work with. Um and if in practice you want to realize this, you should rely on LRU.

5:39 Okay, there's another thing um another property that um I won't formally prove is a bit tricky. Uh but I think it's it's useful to know at least the informal version of it because it gives the whole model even more power. So far I've said a cache oblivious optimal algorithm that's this part means no matter what M and B are it's going to be within a constant factor of the best possible algorithm in terms of IO cost and uh this this is true for every single choice of M and B. But this informal theorem says if you have some uh assumptions on how the caches work which are not unrealistic in this case then the same algorithm is also optimal across a multi-level hierarchy like you have in real computers where there's not focusing on a single level but rather you have all of them at the same time. There's level one cache, level two cache, level three cache, main memory, SSD, hard disk, data center, what else not, right? And if all of these work according to some some principles, uh inclusive means lower levels are cached in the next level above. So a block load here always goes to one level above. It doesn't skip the hierarchy.

7:01 H and consistent paging means that the eviction policy needs to be coordinated. This is more tricky, but it's somewhat reasonable to assume this and then it means that the algorithm is is even optimal in this multi-level scenario if you analyze it all the way through. That's what makes these algorithms more promising than that first thing might seem even. Okay.

7:24 Now, still it seems like a bold claim that for something more interesting than scanning, this should even exist. Now, I'm going to show you uh two short examples of what you can do. And both of them are kind of clever and mind when I saw first saw them I felt woof something someone had a real real proper insight. This is cool. Okay.

7:51 The first really clever idea that uh fits in this in this regime is called the van mas layout. That's what VB stands for named after beta 1 m doas.

8:10 It's abbreviated because uh we'll use it so much. Um he essentially is known vanamea's trees are an integer data structure of the kind like Wi-Fi tries. Um they're the historically first of these that's why it's also named after this. there's a similarity to the data structure because I chose not to explain venom deboas trees because the Wi-Fi tries are nicer and and simpler um you will not see the connection maybe so this just is a definition for us um but kind of that you know where it comes from that's what BB stands for the problem we'll look at is essentially binary search we have a sorted list uh sorted array of elements and we want to find a certain element by by comparisons. [snorts] Of course, in internal memory, you just do binary search and that's best possible. We know in external memory, we should be doing a B tree like search. We want the log divided log base B of N. But how should we do this if we don't know B, right? Um the the trick of B trees is okay, I'm going to load B elements and the B elements are formed in a tiny search tree. I'm going to follow some path through this. I loaded B keys and I've used log B the height of the thing.

9:34 Not perfect, but we know best possible in this sense. Can we at least do that? Well, how if we don't know B? So we have to somehow find an arrangement of the elements in the in the array so that we can pretend to do a binary search and happen to have the elements that we touch next close by without knowing what close by means. And it turns turns out you can do this with a recursive scheme. Um I mean the van deoas layout but uh let me try to sketch what this looks like.

10:26 It's a recursive definition and I'm I'm going to define it over a hypothetical binary search tree, a balanced binary search tree. So you have your array and then on top of that sits a binary search tree and that has the usual meaning, right? There's an element that's the middle one. This is the search tree that you would use implicitly if you do a standard binary search in an array and so on and so forth. Now uh I know what positions I'm going to touch in a binary search. This is this is going to be the middle one n /2. These two are going to be n over4 and 3 n over4 and so on. Right? In principle, we know this. Now, if I leave them where they are in the array, every uh suppose I follow this path down, every node here is a cashmiz because they're in entirely different locations in the array. The first one sits here. This guy sits here.

11:27 So, I'm jumping all over the place. Bad. Instead, let me define um a recursive layout. If I have a single element, I'm just going to how do I write this?

11:48 Let me be a bit sloppy. If I have a single element, the layout for that single element uh is just that single element. There's no choice. That's the base case. Now if I have a larger tree of height h. So I'm uh looking at this tree height h. Then I'm going to split this. Me draw it again. Uh a bit wider maybe. That's my tree. Now uh it has a certain height. I'm going to cut the height in half.

12:30 And you round it somehow. There's the top part and the bottom part. The top part is one single tree of roughly square<unk> nodes. If you cut the height in half, that's 1/2 log n. The total number of nodes in a tree of height half log n is 2 to the power of that. the square root n.

13:03 So almost all nodes are in the bottom part. Of course, because it's uh not drawing to scale, it would be extremely wide. But the this here has many more of these triangles that are roughly the same size as the top one. Let's call these T1 and so on up to TK.

13:22 Uh now I need space. We define the layout of of the the order in which we want to list the nodes in this tree in an in an array or in a piece of memory by recursively laying out with the van deboas layout the first tree the the root tree if you like and then all the children after that and that is That is the simple idea you need. Um, and I'm going to show you some animations for how and why that works. Now, because this is um, the recursion is cutting the height of the tree in half. So, in terms of the number of elements we touch, this is doubly exponential. So, you cannot show too many iterations of this recursion without this whole thing being extremely big. So um let me try here. The largest that you can still reasonably show the individual elements is maybe that size. So it's um uh why is it 63? Fine. It's 63 elements.

14:38 Um because we count the internal nodes. Um the first level of the recursion cuts the height in half. So you have this top tree and the bottom trees. And you see in the array if you choose as page size as as B as block size the number of nodes that fit into either either of these trees it perfectly aligns and the top part comes first and then all the others. Now what happens within one block? You go one recursion level down and now uh the first level is kind of an even split. The height six is an even number so you can properly do it. For the second recursion, we split the top part which has height three. So the um t0 has height two and the others have height one single nodes. And so you see the within this first block that corresponded to the first three levels. I first put the first three nodes. They correspond to the recursive top part and then in order these children which are individual elements in this case.

15:45 Okay. I know it's a bit um brain Uh the recursive sub trees are the same. They come after and so here you have the top part first. Nominally you have another level of recursion for these three nodes. They just say do the root first then left then right. Uh you can of course draw the colors but then nothing is more is visible anymore. Okay. Now, uh why is this um the right thing to do?

16:25 The analysis is is really clever. We don't know what B is in the algorithm, but in the analysis, we know. Good point. Um for the analysis we'll use that there is some level of recursion of this VB layout with pieces. So these sub trees of height delta where delta is roughly the right height. So um the height of a block with the proper block size should be log B because we fit B nodes in a block. But we may not get exactly that. Um we may be a bit too small with our cutting in half. So it might be half the block size uh the the height of the tree if we're unlucky. Um let me try to show maybe this part briefly. So, uh, let me stick it to this, but mess with the block size.

17:37 Uh, I might make the block size a little smaller. So, now, um, it's the other way around. I need to make it bigger, right? So, now say 10, uh, elements fit in one block. Uh, I would want to have sub trees that are log 10 high. I can't really get that in my recursion. And I only have one where the height is three, not log 10, whatever that is. And so I always find one that is slightly below this log 10, the ideal height, but is not more than a factor two away in height because I have I cut the height in half at each recursive level. So say you start at the top. If your current height for the tree is too much, you cut it in half. If it's still too much, you cut it in half. after some amount of cutting in half, you'll be too small. And so then you have a range and that's the delta where you stop.

18:36 So there's there's some delta that falls in this range and that has um two consequences. For one, um, the way Venom Debo's layout works, there's this level delta where I put the pieces contiguous.

19:11 So reading such a piece costs a constant number of block transfers. is uh I guess at most two in real life, right? It could be that just that the boundary of a block, but that's all less than equal two is is true.

19:40 And um well, this is maybe one step in between. um it's contiguous in memory and it's not very big because how many elements do I have in a delta piece?

19:56 Well, it's at most two to the height and the upper bound to the height is this. So the number of elements in a piece is at most B. Touching B contiguous things costs at most two IO's. Right?

20:18 Now the second consequence is because of the lower bound any search path. Um you should think of um this now looking a bit like I have an animation of this shortly. Uh you're searching from the root down through this and you somehow end up at a leaf. How many such pieces can you traverse through? Well, the total height divided by the height of each piece and that's delta.

21:05 And uh if we insert the lower bound for delta, you get log n /ed 12 log b. But ignoring the constant factor that's log come on log base b of n. So b tree access time without knowing b right.

21:27 Um and here's here's an animation showing that part. Uh again this is drawn a bit bigger. Now uh we have 4,000 something keys and the recursion level is block size is seven. And so you see any search path crosses through only a bunch of these elements. Um and uh there's a a zoomed in view on the actual blocks because the overall blocks is now 4,000.

22:11 And if you see the first few are only touching this part and then you're touching another small part and another small part. You're even within these parts always staying very local. And that's that's the magic of this VB layout.

22:38 I think with that um uh we we move again to high altitude for the last bit. Um the ban deer boss layout is cool but you can only do it with static arrays. So far I cannot insert that completely messes up my my uh layout etc.

22:53 In the last little section let me uh point to what you can do with this van deoas layout beyond what we've seen so far. Um what we've seen is is a layout for a static array of elements so that I can search uh so that my my standard binary search happens to have optimal IO cost. That's really what it does. Uh but we can't really support any insertions as is. And there is a way to build on top of that something that can be called or has been called the cache oblivious B tree. The name is a bit misleading because it doesn't use B. it needs to be cache oblivious and it's also not properly a B tree in any way. Instead, um it stores the data in sorted order conceptually like what what we've done so far and on top of that an index a search tree that navigates in the same way as we've just seen. Uh but we need for supporting insertion deletions we need two changes. Number one, this is not really an array. It's a packed memory array. I'll try to very briefly show you the glimpse of that. Um it's a magical data structure that uh uses a constant factor more memory than you should need for the elements.

24:11 Um but it and so it stores them with gaps but allows you to insert at any point in time. Um and if needed you move elements a bit around. Now this is this is always possible if the moving around cost is high but you can do it with poly logarithmic move cost amortized. So some insertions might mess up the array entirely but most don't. And so you can insert into this low part at a reasonable cost.

24:41 And for the tree on top, we use what we've just seen um where we apply it to the nodes of a balanced binary search tree because it needs to be dynamic now as well. So the layout uses the nodes of a tree and the content of the nodes might change if the tree gets reorganized. uh and with that you get this overall IO bound and you should note that this one over B factor here probably means this is in practice uh not as not the dominant part and you're left with essentially the B tree uh complexity but again without knowing what B is because neither of these uh constructions uses the block parameters or the memory size you've seen the second part um and I want to give you a brief glimpse of how this is supposed to work.

25:36 So, a packed memory array is is essentially an array with gaps. And um in the interest of time, let me maybe only show this uh here.

25:53 So, what can you see? There's an array of elements here. These are initially evenly spread out but you'll see this is um it's just one starting configuration. The actual array is the numbers here below which is a constant factor larger. It's half full at this point. Now on top of every element there's um a segment tree if you like. So there's a root that covers the entire array. Then there's a left and right half. Each of these just define ranges uh subranges of the of the actual physical array. And the ranges remember a few things. They remember for example that they can hold up to a certain number of elements and they currently hold a certain smaller number of elements. And uh the magic of this data structure consists in the following um definition. Each of these ranges defines a density. How many of my slots can be occupied before I decide oh I'm I'm unhappy now.

26:51 I uh need to rebalance all the elements in my range and this density is chosen to be um uh sorry there's the current density but then uh there's a threshold density that's what I meant the density if I reach that I want to rebalance myself because I'm unhappy at the root this unhappiness balance uh is is 1/2 and It gets more and more strict the further you go down. And let me do it once smaller. The numbers are around. It's 1 point 0.5 at the top 0 0.6 0.7 0.8 0.9. So it linearly decre increases from some starting thresholds that you can choose. Here is 1/2 down to essentially one at the leaf level. And what this does is if I now insert an element after this this element here, it's going to be added in the middle between these two. Now um each element uh is now contributing another occupi occupied element in all the ranges that contain this position right all all of them above it.

28:11 And uh if I do another insertion then here I'm completely packed. So if I do one more insertion we have to spread things out.

28:29 And at this point you bubble up until you find the first interval that is still happy. And that spreads everything out. And now you see in this case we have another range that's just before overflowing. So if I hammer another insertion into this tightly occupied range, it'll bubble up even more. And so this was costly. Now I've rearranged a lot. On the other hand, all of them are green again. Okay. Now let me um let me reset this and show you the other part. There's an amortization going on. And uh in the animation is completely baked in. Um we had some fun. So uh every insertion pays remember the goal is to show log squared amortized cost per insertion. It's quite a lot. So log is of course the height of this tree. Log is the height of uh the number of of ranges. So I can pay the height in coins for each range that I'm inserted into. So here the height is five. If I insert an element, each of these ranges will will receive five coins.

29:45 Okay, it's going to ended up it ended up here. So here I get five coins. Five coins. Five coins. Five coins. Five coins. Five because that's the height. Uh then there's a um there's uh you need you need to multiply the coins with a certain constant factor to translate between coins and number of elements I'm allowed to move when I do a rebalance. And you can show that whenever an insertion inserts login coins in each range, any future rebalancing operation is paid only by the coins. And so the amortized cost because every element uh is equipped with these lock squared n coins initially uh you never run out of coins. So that's the amortized cost. Okay.

30:41 Um what else can I show? Um let's do one round and we see how the coins um accumulate a bit. So if I insert one more element here, now I got five coins in these ranges. But the the top has accumulated 10 coins because it got five from this side and five from this side. Okay, let's hammer another insertion into this tidy pack range. So something has to happen.

31:14 And maybe this is another interesting part. So this is now over its threshold because it's completely packed. So rebalancing this one would do nothing. I have to go one level up. And if I go to the next level up, this element is still happy with its current density. So that's the one that is rebalanced. And at this point, I'm looking at its number of coins. And um it received 10 coins, two inserts. Uh the 10, this was five a second before. The five came from the current new insertion that we just did. It's a bit um well uh and in this setup with the initial um with the root threshold at 1/2, each coin pays for moving four elements. But that's a universal constant. And so I could have paid for 40 moves and I only need two. So you see there's a lot of slack in that analysis. Uh but for the low ranges maybe that's expected.

32:21 Uh let's do one more and then um we'll finish for today. So here I need to bubble up one more step. And uh so this one was still all over threshold. The first one that was not is this. It has received 10 coins up to this point. So it uh could pay so sorry another again it receives the five coins only at this point from the newly inserted elements. Um so it could have paid for 60 elements moved uh but it only needs to move four. You could probably skew the coins to be distributed more towards the top.

33:01 Okay, so with that you can implement this packed memory array where the memory cells are the numbers at the bottom. That's the physical locations of your elements of your sorted sequence. The positions that are occupied by these elements here, that's the actual positions that store some some element. And um you can use this range tree also to guide you. So if you if you have a key uh the top range tree can store what's the um the key at this boundary. So you can use the range itself to binary search in the packed memory array. But you don't really have to. You could also just jump in the middle because you're only touching a constant number of elements before you reach another one. If you want it worst case uh you need to use the range tree annotation. Again um you can store in each range the number of elements that are in the range. We already do that. So you can do select and you can store the maximum in the range as a key. Then you can do searches for a key in logarithmic time.

34:12 So it behaves just like a binary search tree but it's tightly packed in a contiguous range of memory. So if you lay out um if you do the the actual searches with this vanim deboas layout you get the log base b of n searches.

34:37 All right. Uh I think that's a nice kind of climax for the module. Um of course you're not you're not expected to know more of the details of this data structure than what I've uh managed to show you now. But I think the the construction itself is rather clean and clear. The analysis is is a bit subtle. Um I can uh give you some material if you want to read more about it.

35:03 As a last point, let me just point out that I managed to smuggle five different projects of our own research into this module. And maybe you noticed [laughter] in case you didn't, here they are again. And maybe you can add some future entries to this uh as well.