[CONF] Apache Labs > Mavibot

[confluence]

Mavibot Page edited by Emmanuel Lécharny Changes (2) This is the Mavibot lab page. Mavibot is a MVCC B+Tree [MVCC|http://en.wikipedia.org/wiki/Multiversion_concurrency_control] *B+Tree* implementation in Java. h1. Btree basics A *Btree* is a data structure that stores _<Key, Value>_ tuples in a tree, with the guarantee that the tree will be ordered, and that the depth of the tree is the same for all the leaves. A *Btree* has nodes and leaves (with the only exception of a *Btree* with only a root page). The nodes are used to route to the underlying values, and have children. Leaves don't have children. Nodes and leaves have a constant number of elements stored into them, and when they are full, they are split. If the split is done on a leaf, we may have to reorganize the tree so that either we can move some elements up and keep the tree at the current hight, or we may have to reorganize the full tree so that all the leaves are at the same level, which will then be one deeper than the tree before the split. h1. Btree vs B+Tree The difference between those two data structures is that *Btree* store values in the nodes, when *B+Tree* do store all the values in leaves. At first glance, we can say that finding a value in a *Btree* will be faster, as we may not go down to the leaves to find it. OTOH, a *B+Tree* has many advantages, but the two major advantages are : we don't need t go up in the tree to browse the tree when searching for more than one value, we can just read the leaves, as they are chained. We will have smaller nodes, so we can cache more of the tree pages than if we have values in the nodes. Those two big advantages make the *B+Tree* more interesting to use than the simpler *Btree*. (See [Wikipedia page on B+tree|http://en.wikipedia.org/wiki/B%2B_tree] and [Wikipedia page on Btree|http://en.wikipedia.org/wiki/B-tree]) h1. MVCC [MVCC|http://en.wikipedia.org/wiki/Multiversion_concurrency_control] (Multi Version Concurrency Control) is a way to provide concurrent access to the *Btree* (it's extensively used in many other areas, like programming languages and transactional memory). The main idea is to create a new version of the tree each time we do a modification. It also allows the reorganization of the data on the fly, but this is an extra benefit. The way it works is that when you do a search on the tree, you first acquire the current revision. Even if the search is taking a while, because it fetches many values, the tree will remain unchanged for the selected revision Any modification done on the tree will first create a new revision, and the modified pages will first be copied, so that the previous versions are still available for any search operation being executed at the same time. It has three direct consequences : * first, a search will always return 'outdated' values, in the way that new data won't be returned, as they will be stored in a version which is newer. * Second, and more important, we don't need any lock to access the data when doing a search, as there is no possible modification on a versionned tree. * Third, concurrent modifications are thus limited, as we want to be sure that we don't override some modification done by another thread. They are ways to mitigate this constraints, but in most of the case, it's acceptable. Full Content This is the Mavibot lab page. Mavibot is a MVCC B+Tree implementation in Java. Btree basics A Btree is a data structure that stores <Key, Value> tuples in a tree, with the guarantee that the tree will be ordered, and that the depth of the tree is the same for all the leaves. A Btree has nodes and leaves (with the only exception of a Btree with only a root page). The nodes are used to route to the underlying values, and have children. Leaves don't have children. Nodes and leaves have a constant number of elements stored into them, and when they are full, they are split. If the split is done on a leaf, we may have to reorganize the tree so that either we can move some elements up and keep the tree at the current hight, or we may have to reorganize the full tree so that all the leaves are at the same level, which will then be one deeper than the tree before the split. Btree vs B+Tree The difference between those two data structures is that Btree store values in the nodes, when B+Tree do store all the values in leaves. At first glance, we can say that finding a value in a Btree will be faster, as we may not go down to the leaves to find it. OTOH, a B+Tree has many advantages, but the two major advantages are : we don't need t go up in the tree to browse the tree when searching for more than one value, we can just read the leaves, as they are chained. We will have smaller nodes, so we can cache more of the tree pages than if we have values in the nodes. Those two big advantages make the B+Tree more interesting to use than the simpler Btree. (See Wikipedia page on B+tree and Wikipedia page on Btree) MVCC MVCC (Multi Version Concurrency Control) is a way to provide concurrent access to the Btree (it's extensively used in many other areas, like programming languages and transactional memory). The main idea is to create a new version of the tree each time we do a modification. It also allows the reorganization of the data on the fly, but this is an extra benefit. The way it works is that when you do a search on the tree, you first acquire the current revision. Even if the search is taking a while, because it fetches many values, the tree will remain unchanged for the selected revision Any modification done on the tree will first create a new revision, and the modified pages will first be copied, so that the previous versions are still available for any search operation being executed at the same time. It has three direct consequences : first, a search will always return 'outdated' values, in the way that new data won't be returned, as they will be stored in a version which is newer. Second, and more important, we don't need any lock to access the data when doing a search, as there is no possible modification on a versionned tree. Third, concurrent modifications are thus limited, as we want to be sure that we don't override some modification done by another thread. They are ways to mitigate this constraints, but in most of the case, it's acceptable. Change Notification Preferences View Online | View Changes | Add Comment --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@labs.apache.org For additional commands, e-mail: commits-h...@labs.apache.org