[CONF] Apache Labs > MVCC specifications

[confluence]

MVCC specifications Page added by Emmanuel Lécharny So we want MVCC implemented on top of a B+Tree. How do we do that ? Let's write down a piece of specifications first. How does it all work ? Simple. We do what we call CoW, or Copy on Write. In other words, when we want to update the B+tree, either by adding, modifying or removing elements in it, we don't modifying existing pages, but we copy the modified pages to create new ones. Let's see how it works with some diagrams. We will use a B+Tree with pages containing only 2 elements. That means a Node can have 3 children at most. (we could have used a larger page size, but for the demonstration, it's easier to have only 2 elements per page). This B+Tree will use single letters as keys, and a value named v{X} which is not interesting atm. We will inject the following set of data : {<E, vE>, <A, vA>, <D, vD>, <I, vI>, <G, vG>, <K, vK>, <H, vH>, <B, vB>} (in this order) 1) Insertion of <E, vE> This is easy : we create a root page, and we inject the tuple into it. The tree has the revision number 1. Unable to render embedded object: File (R1-node.png) not found. 2) Insertion of <A, vA> Here, we will copy the root page, attribute a new revision, 2, and inject the tuple into the new page. The old page r1 still exists and s pointed internally by the BTree instance Unable to render embedded object: File (R2-node.png) not found. 3) Insertion of <D, vD> Now, the first page is full, we need to split it and create a new level, by creating two leaves containing the three values. The root page now becomes a node, containing only links to the underlying leaves. Unable to render embedded object: File (R3-node.png) not found. We can see that the three versions are still present, and that we have copied all the pages so far. 4) Insertion of <I, vI> This time, we will only copy 2 pages, and we will point to the unchanged page : Unable to render embedded object: File (R4-node.png) not found. The root node has been modified because its right leaf has been split in two pages, with the pivotal key being moved up to the root. The leaf containing the <A, vA> tuple has remained unchanged, so we still point on it. This goes on and on like this, and the more tuples we add, the less pages are copied. Some importants rules In order to get the tree correctly balanced and easy to use, we have some more constraints to add. Change Notification Preferences View Online | Add Comment --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@labs.apache.org For additional commands, e-mail: commits-h...@labs.apache.org