Video 4-5: Partial persistence transformation transformation

0:02 Now that we fixed the model of computation and namely linked data structures with bounded in-degree we can look at how to actually build partial persistence from that. And it'll be a general transformation from a given data structure to a partial persistent one, partially persistent one with only constant factors slowdowns and space overhead. Um I still think it's It is remarkable that this is possible. If you look at specific examples maybe you can build it but it's it's quite clever to come up with the the general transformation.

0:41 Uh all of this is um from a single paper if you like uh where they do this uh where they introduce this technique uh and even a version for for for full persistence. I'll only briefly comment about on this at the end. Uh I didn't spell out the final result. That's uh something to maybe start with.

1:21 So we're given an ephemeral data structure. But I want it to be bounded in-degree. And uh in the framework a linked data structure. >> with constant extra space per update step.

2:19 So, here unfortunately, we need um the more we write, the more space we need. On the other hand, maybe this is inevitable because I'm doing a change and I have to keep track of it.

2:56 So, what I mean by slow down is whatever the time was previously, it's within the same big O, but uh in in reality, it's a constant factor slower.

3:09 Um maybe the intuitive version should be we want to do something in between of this copy on write and fat nodes. Where copy on write meant as soon as I write a tiny bit, any any little change copies the entire node, which recursively copies all things that point to me. Uh fat nodes said, "No, no, no, no, I'm never going to copy. on just going to collect all the updates for good. That's a spectrum. I can do something in between. It turns out the sweet spot is really a very close to the copy on right. I'm only allowing a constant buffer of of rights per node. But that's just enough if you uh I mean again, we have this bounded in degree. So, constant it will depend on the in degree. We'll allow a carefully chosen number of of updates buffers so that not every update cascades all the way through the predecessors. But on the other hand, um I only have a constant space overhead.

4:33 So, for every node, I have a few fields that I can use to collect updates. But then once this overflows, I have to make copies. So, more concretely, um So, yeah.

5:07 One ephemeral node bounded by P. That's the assumption. And out degree, number of pointers it has, Is transformed into one persistent node where we now uh reserve P plus D plus E plus 1 um pointer fields.

6:12 And I guess pointer field here is is supposed to have um a little more space than just storing a pointer. Um Let me Let me instead call this differently. So, this is on top of of course I'm storing the same as in the ephemeral node with additionally uh so many Let's just call these extra pointers.

6:43 Or uh Yeah, that's also a clash of notation. I'm sorry. This is um Let's call it an update box. So, this is a single uh entry that has a timestamp and the field that it updates and the new value.

7:14 Okay? Uh every every one of these P plus D plus E plus 1 update boxes can store this triple of things. So, Yeah, what exactly is E? E is the number of extra pointers to be determined.

7:44 And I am uh uh uh uh the end he will be But if you if you want you can leave it open and then work backwards through the analysis to find out that that that suffices. So we'll leave ourselves space for storing a few updates. Important is that we're not distributing these in a fixed way to the fields. We just leave that open. Every update can specify what has been updated and what the new value was.

8:24 Okay. So that's one ephemeral node X. Uh clearly if I keep doing update steps on a specific node, this will eventually be overfull. So initially I'm using an update box whenever someone writes to this node. It's a constant still, right? These are all fixed constants. So whenever someone reads a um a field on this node, I can go through all the update boxes and check if any overrode the original value.

9:28 So this is a constant overhead um within the time allowed time bounds. Um if I keep maybe uh pointer right and an update step.

9:54 I will first fill the update boxes if I can. At some point this will overflow. I'll I've used up all update boxes in the node. And then um I may in general have a whole family of persistent nodes corresponding to a single ephemeral node.

10:28 And um they have this this plus one here. I think only E needs to be these these update boxes. The others are just the normal pointers from before. Uh it's a bit of a an awkward way to write it. Of course I could write them like this. Um Here I think ordinary pointers are good enough. In particular this this one this plus one comes from what I use here.

11:36 This is pointer per node that I can use to have a singly linked list of this family. So, that means uh if if needed, I can go from my primary copy, my primary persistent node for X through all the past versions.

12:17 Uh a bit of notation still in this list, in the family, there will be a last node, the newest one. X bar again is the persistent version for an ephemeral node X.

12:38 And this last one is the live version of this live node. Whereas the others, we call them dead because they will not receive any updates. But we keep them for for accesses.

12:57 And derived from that is the notion of a live pointer. That's uh a pointer in the newest version. Uh the significance of these of these live pointers is that I might still update the thing they point to. And so, um for these live pointers, I need to store the reverse pointer. I need to be able to store where they came from. And that's where the plus, uh, plus P here comes from.

13:44 These D that's the normal out degree. Whereas these P pointers here we can store back pointers that allow me in principle to always know my predecessors. Uh, but I only need to keep those for live pointers. For dead pointers, I don't care.

14:33 Okay. Now, uh, I might have to delay the analysis for tomorrow, but let me at least try to give the algorithm for the update steps.

14:48 Okay, um, I'll talk about this later. Yeah. What did I do? Uh, I mean, let me let me maybe write this down, but, uh, I think we've talked about it already.

15:27 I need to somehow get started. So, there's one missing component I haven't explicitly mentioned. For each of the access pointers, the entry points into the data structures, where I can put in the version ID and I get back the pointer at that time.

16:09 Conceptually here, you could also say it's some some other dictionary, but we need for the for the formal statement, we need that this is constant time. If I'm given the version, I can in constant time get started. Uh That's that. Now, once I have my entry node, I'm going to follow uh access steps as described here. The The access operation on the ephemeral data structure tells me, "Ah, now go to this field, read out that value, or follow this pointer." Uh I mimic that step by step. Whenever I read the entry for some node, I'm guaranteed that either it's the original value that still sits in that field or it's in one of the update boxes where it has been overwritten. So, I always use whatever is the most recent one. And uh that's guaranteed to succeed because we have an invariant that we'll have to uphold.

17:27 Uh which says if some ephemeral point some ephemeral node points to another ephemeral node Y in a version then in our persistent data structure X bar reached from the entry in that version for version V has some entry for the pointer to our Y bar which could either be it's still the original content in the field or it is in one of the update boxes and then it's the most recent or the the the most recent before V.

18:56 And if that invariant holds then clearly the access is obvious. I'm I'm going to some pointer and there I always get the correct information from either the field or the update box so I follow this and simulate the same update opera and the same access operation, excuse me, as in the ephemeral data structure. And in each step, each access step has constant overhead because I might have to read this constant number of update boxes. That's all. So that's for for access.

19:39 The more interesting thing is how to maintain updates. I have to maintain these invariants and I have to somehow uh guarantee the the time.

19:52 It's actually fairly natural, but uh it still um it still has needs to cascade updates. So, what what we do is at each update step we may change some field entry or may may change a pointer. We'll go through the cases. Uh if I change a pointer um uh nothing really changes unless any change I do overflows my update boxes. In which case, I have to make a copy of myself to be uh able to store more changes. And at that point in time, I may have to update my predecessors. But then that's an update to my predecessors. Who knows? Maybe they overflow as well and I have to keep cascading updates.

20:44 And so uh the general way to do this Any updates happen in this node X? Um The general way to to up to to keep keep this going is to maintain a set of newly copied nodes and only do all the updates of predecessors at the end.

22:07 The way The way to do it uh is to maintain the set of changed or copied nodes and do this um do first all update steps and at the end of the update operation, repair all the predecessors. That way you can guarantee that you're not doing extra work that is invalidated soon after.

22:29 Uh again, the point is the granularity of versions is uh at operations. I'm only adding a new version after an operation is done. And so, uh I can override a change I made during the same update operation again. That's fine. I don't need to see this intermediate stage. I only care about the clean snapshots at the end of an operation. Uh and that's why this works.

23:36 >> Every operation should be the underlying.