Video 4-3: Simple approaches to persistence

0:03 Now that you've seen a bit how we can use partial persistence, uh let's see how we can build it. So far, I've only claimed that there is a magic way to do it. And let's start simple. Let's try some some simple things first. Uh we need a bit of the terminology for that, and to make sure I'm slowing down on this. Let me handwrite this.

0:35 First of all, um we have this notion of versions. And this depends on what type of persistence we have. But for partial persistence, which is what I'll focus on, it's just a an update timestamp. So, it's the number of past updates.

1:06 In particular, it's just a number. Um that makes it easy to work with. Okay. Um that's what a version is for us. Now, we need to take um a few things we need to keep separate. Um we will both have an ephemeral data structure.

1:35 Let's say this is the the normal data structure, which doesn't necessarily store any past versions. And what we'll try to build is a persistent version of the same data structure.

1:58 And for for almost all of today let's say this is a partial persistent. Uh that has the same operations as this ephemeral version, but allows access to past versions.

2:20 So, I'll try to use these two terms um to always make clear which kind of data structure we're talking about. As a kind of forward pointer, the goal will be to have a general transformation.

2:36 Or maybe at this at this level of generality, it's more a wish than a goal. It would be nice uh if we didn't have to invent anything new for each of the many data structures that are known and instead have some some general black box thing that I can put an ephemeral data structure out and I get a persistent data structure back. I put an ephemeral data structure in and I get a persistent data structure out. In full generality, I don't think this is achievable. And what we'll see is some conditions that you can put on your data structure so that this becomes possible. Uh as a wish, you can wish for anything, so let's keep it fully general.

3:25 The last two things I want to distinguish is the notion of an operation versus a step. Uh we have access operations and update operations.

3:41 This is what you normally would would call uh one method offered by your data structure. Say, insert or search or successor. These are the normal kind of uh API calls of a data structure. Okay, so these are the methods of Now, we'll have to zoom in to make any progress. These operations usually consist of individual smaller steps. And so, uh the access operations They consist of sequences of access steps. Where for now, let's leave this a bit vague what exactly it means. But any kind of data structure will be built from somehow constituent parts. So, maybe you read a value or you follow a pointer. That's That's what an update what an access step could be. And an update operation also consists of steps. But it might do an alternation. I might do a few access steps to get to a certain point in the data structure, then I might do one update step. So, a single change, and then I may have to to do more access steps to get to the second position, and maybe do another update step. So, I have a a sequence of these things.

5:13 So, um sequence of and then first some access steps. And here that's plural. And one update step. Where you should think of this as as a single write operation. And then we can have a whole sequence of several of these in a row, going back and forth between update and access.

5:54 we'll speak of the total time as just the number of all steps that such an operation does. Uh that's kind of natural. For updates, we'll speak also of the update time as just the number of update steps. You'll see in a second that this plays a role. And maybe it's intuitive enough. Uh if we want to keep past versions, it's the updates, the changes, or the right accesses that are problematic, not the reads.

6:33 So far, so good? So, keep in mind ephemeral versus persistent, and the crucial thing that's maybe not completely intuitive, but operation as the bigger-level thing, an insertion into the data structure, and step, a single atomic change, or or read.

6:57 Okay. Um with that set up, how could we do this? Uh in principle, uh keep past versions of data structures around. Is this utterly hopeless and completely impossible? Uh one simple blanket approach would be whenever we write something, we make a copy and keep the old copy around, of whatever it is. Um indeed, if you don't care about space at all, space and time at all, this is not really hard to do. Uh the stupidest thing you could do is whenever somebody touches anything in your data structure, you make a copy of everything, and keep that around. Okay. That works, right? And you keep a history of that. Of course, it's not so satisfactory because uh needs a lot of space and you need time to copy the whole thing. Uh we should be able to do better. And it turns out maybe in general this is the only thing you could do. If you know nothing about the data structure, maybe this is the best you can do.

8:02 Just because it doesn't give you any any further access. But so uh to make the discussion a bit more concrete, let's think about two typical kind of data structures. One uh a balanced a binary binary search tree and the other a doubly linked list. Okay? Basic data structures. And um this is not a trick question. I'm just saying let's try to make those two partially persistent and see what happens. If we can figure out these two cases, maybe we can generalize.

8:36 Um this is what I uh explained in writing. Um so, a single operation consists of steps. Just to repeat that again. And for updates, it could mean a single step. For these kind of data structures, it could be that we change the value stored in some node. So, it could be the the key in a search tree or or the element in the list. We may change pointers from nodes in the data structure. And we may also allocate new nodes, of course. But that's by and large it. All these data structures do is essentially one of these three things. That's good. That makes it a bit easier to think about what could happen. Also, um they don't do a lot of update steps usually. In a linked list, it's a constant number of update steps to bend a few pointers. And in a binary search tree as well, even if you do a balanced binary search tree with rotations, often times they don't do more than a a number of changes per update even if you have to walk down the search path.

9:40 So, clearly copying everything is very wasteful. Uh that's an update step. So, these are the three examples of an update step. That's what I mean here. Uh yeah.

10:03 Maybe step is I kept the terminology from the original paper. I would call it atomic updates. It's a single smallest thing writing a single field or so.

10:16 Okay. So, copying the entire data structure is clearly a bit wasteful. We could instead copy only the parts that changed. It's only slightly more more clever. Um in a way you could treat everything as immutable. Every object that's written once is never changed. And upon an update, you create a copy of the thing you changed with the new value. Okay? Uh now of course this means if somebody else had a pointer to this node, that person also needs an update now because the pointer points to the old version. I want to point it to the new version. I can't change that pointer really so I have to copy that one as well. So, this may already think about how this uh spirals out of control. Um it works okay for for binary search trees.

11:14 First of all, we can only really do that if we know who points to an element. That's the first prerequisite. If I want to update I'm I'm changing node X by I'm replacing it by a copy with a different field value. Uh to uh make sure that the elements that previously point to X now point to X prime, I need to know who they are. And so this is an assumption that will always make in the rest. I can somehow get to the predecessors of a node, so I can follow pointers backwards. Of course, I can't really unless I do something about it. But it turns out here is not even a restriction. For for doubly linked lists, I always have the double pointers, so I can actually follow backwards. And for binary search trees, it's essentially child pointers, and I can remember the parent pointers of the parent from the recursive descent. So I can also arrange to have the predecessors available.

12:13 Okay. Um On top of that, there's there's some entry level into the data structure. For that, I just maintain uh which versions exist and the copy of these. So this is this is the first not completely stupid approach, and it might work for some. Um For binary search trees in particular, what what happens is if I change some node, I have to copy the path to the root. All of these re- inductively point to my node.

12:54 The good thing is it immediately supports full persistence because nowhere did I use that I'm working on the current or the the latest uh version. I I'm Uh also queries are super fast. Um as soon as I found the right starting point, I just read values as if there was no persistence. That's great. And um for for things like trees, the overhead of copying all the path is maybe a tolerable. And in a way, this is if you if you know Butter FS, Btrfs, there's a a file system based on B-trees. It's very popular for for network attached storage or these things because it essentially does this for files. You can copy a file by not doing anything apart from metadata change. And then you have two copies of the file that use the same space on disk. And if someone later changes one of the files, then you say it suddenly say, "Ah, I'm going to copy out the changed version, and now it's a separate version."

13:56 But you only pay for the changes. So if you want to keep backups, that's perfect because most backups the snapshot before and now is not very different. Only the few files that changed. So this is this is fine. But it doesn't work in generality. For doubly linked lists, ultimately everyone points to everyone if I follow enough pointers. So any change would have to escalate to copy the entire list.

14:26 Tough luck. Uh so this this doesn't work. Um at least not for this general case. Um I pointed this out because for trees or other data structures where there's not too many pointers that point recursively to something, this is a practical alternative that people use. Uh what could we do for doubly linked lists if this doesn't work? Well, another simple idea is whenever we have updates in every node of the data structure in these two examples, say, we keep an unbounded list of update logs. Instead of doing an update, we store I at time five, I updated my field F to value 17. Instead of writing the update, I just keep track of what I would have done. That's what I mean by a log. And then whenever we read or write or update, uh I have to just replay all the backlogged updates and then start going. Uh this this already sounds like it's going to be slow. In principle, this works.

15:33 Um the space usage is essentially as good as you can go. Um we need to store the the final version of the data structure. That's the size of the final version. And M um I didn't define this properly, right? This should be the number of updates.

15:54 However, the queries gets slower and slower over time. I have to replay all one after the other all the update steps. Uh that's a bit that's a bit slow. Now here um I'm doing this log at a global level for the entire data structure at operation granularity.

16:12 That's what's meant here with with the log. Now if you see these two extremes, copy on write and log everything, you could do some something in in between with a parameter you keep every so and so manyeth version and then a log between those. Then you can somehow try to get the best of both worlds. Uh but if you think about it, um either way, no matter how you choose your parameter, you get a slowdown in the number of um number of operations. M is number of operations.

16:52 Uh operations, not You don't need to a version in between. And you either get this square root M blowup in space or in time. You can choose which one, but uh you can't can't do better with this um global approach. Okay. Uh let me tell you about the the next approach. Um This is a refinement of this log everything approach where we do it um per node, not at the level of the entire data structure. So, here this only works if I make this assumption that my data structure consists of nodes. Uh so um for the two examples that we were thinking about, binary search trees or doubly linked lists, that's clearly the case. Then any update step is one of these three things. I can allocate a new node. I can change some information field, so anything that's not a pointer is an information field. And the last option is I change a pointer.

17:57 Um this is still general enough to uh encompass many data structures. Now, we'll see this is the model we'll keep working on. Now, if we keep a log of all the updates per node instead of for the global data structure, we're doing a little bit better because at least we distribute um keeping the log uh to the different parts of the data structure that may not all be updated. Um the log we can store as a balanced binary search tree. So, uh because we're now talking about individual updates, I don't have to replay the entire history. If I'm If I'm asking about a single information, the latest right is the only one that I care about. And that's that's the um that's the key thing here. I can for a read, just find what was the latest write operation to this field that I'm now reading. That value is what I should read. Whereas previously, if you do it at the level of the overall data structure, if an operation could be an insertion, I might I might have to do all the insertions one after the other to get the correct answer.

19:10 Uh so here, if you do it per field, this is more efficient because you can binary search over the log. Uh same same for the pointers. So, this is okay for updates um in terms of the space. But you have this binary search slow down for anything you do, basically. Any read needs to check for the last version. Any write needs to add to this binary search tree a new entry. At this point in time I've written this. So, you have a slow down of log M uh for anything you do. Um where if we're if we're a bit careful, it's not actually M, the total number of updates. It's M, the local number of changes to my field. That could be much smaller. And in particular, if you look at uh something like unbalanced binary search trees, maybe not the most exciting data structure in general, but okay. Maybe sometimes you can tolerate not balancing it.

20:14 Or you're using uh some random That's already tricky. The the The thing about unbalanced binary search trees is I may have a node that currently has null pointers, and I may insert something later, but that's by and large it. So, I guess uh with insert only, if I start deleting, it's also gone.

20:40 If I'm in this case, it's a bit like pathetic. I I have an unbalanced tree, and I only insert. I'm only ever going to override a child pointer once when it acquires a child and not going to change it ever. Then this is still good enough, but uh now I'm in a very restricted case.