directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
Subject svn commit: r879452 - in /websites/staging/directory/trunk/content: ./ mavibot/user-guide/ mavibot/user-guide/images/
Date Sun, 22 Sep 2013 16:02:44 GMT
Author: buildbot
Date: Sun Sep 22 16:02:44 2013
New Revision: 879452

Staging update by buildbot for directory

  (with props)
 (with props)
  (with props)
  (with props)
    websites/staging/directory/trunk/content/   (props changed)

Propchange: websites/staging/directory/trunk/content/
--- cms:source-revision (original)
+++ cms:source-revision Sun Sep 22 16:02:44 2013
@@ -1 +1 @@

Modified: websites/staging/directory/trunk/content/mavibot/user-guide/2.1-logical-structure.html
--- websites/staging/directory/trunk/content/mavibot/user-guide/2.1-logical-structure.html
+++ websites/staging/directory/trunk/content/mavibot/user-guide/2.1-logical-structure.html
Sun Sep 22 16:02:44 2013
@@ -147,18 +147,51 @@
 <h1 id="21-logical-structure">2.1 - Logical Structure</h1>
-<h2 id="special-btrees">Special BTrees</h2>
+<p><strong>Mavibot</strong> stores data into <em>BTree</em>s,
and we may manage many <em>BTree</em>s, so we have to define the right data structure
to handle those data.</p>
+<p>We can have three different ways to use <strong>Mavibot</strong> :
+<em> using in-memory </em>BTree<em>s (IN-MEMORY)
+</em> using in-memory <em>BTree</em>s stored on disk (PERSISTED)
+<em> storing the </em>BTree<em>s on disk (so called managed </em>BTree*s)
+<h2 id="in-memory-btrees">In Memory BTrees</h2>
+<p>They are <em>BTree</em>s stored in memory : as soon as you quit your
program, all the stored data will bo lost. The biggest advantage is that it's fast.</p>
+<p>As <em>Mavibot</em> is handling <strong>MVCC</strong> <em>BTree</em>s,
you have to keep in maind that for each modification, we copy pages and values, so the <em>BTree</em>s
will quickly grow and eat the memory. On the other hand, copied data which are not anymore
in use will be discarded automatically. The beauty of having a garbage collector is that we
don't have to take care of those copied data : if they are not any more referenced by any
objects using the <em>BTree</em>, they will be reclaimed by the GC.</p>
+<p>The following schema shows what is the logical data structure whe using a in memory
<em>BTree</em> :</p>
+<p><img alt="In-Memory BTree" src="images/InMemoryBTree.png" /></p>
+<h2 id="persistent-btrees">Persistent BTrees</h2>
+<p>A persistent <em>BTree</em> is a <em>BTree</em> which can
be flushed on disk on demand. The <em>BTree</em> is a in-Memory <em>BTree</em>,
but when you close it, all of its content latest revision is serialized on disk. You can re-read
it when needed.</p>
+<p>Otherwise, there is no difference with an in-memory <em>BTree</em></p>
+<h2 id="managed-btrees">Managed BTrees</h2>
+<p>Managed <em>BTree</em>s are very different : we will keep a updated
version of the <em>BTree</em> on disk after each modifciation. even if the program
crashes, you have the guarantee that the disk will contain everything needed to recover the
<em>BTree</em> as it was just before the crash.</p>
+<p>This is important to understand that we don't keep all the <em>BTree</em>
in memory when it's managed, but instead we try to limit the elements we load in memory. In
other words, there is no guarantee whatsoever that you will have any pat of the <em>BTree</em>
in memory, except the root page, so that means <strong>Mavibot</strong> may have
to fetch some missing data from disk at any moment.</p>
+<p>Obviously this approach have big pros and cons :</p>
+<p>Pros :
+<em> there is no limit but the available disk you have to the number of elements you
can store in your </em>BTree<em>
+</em> your <em>BTree</em> will always be consistent, even if you have a
+* you can stop your application and restart it, your data are still around</p>
+<p>Cons :
+<em> as your data may not be present in memory, it cost a lot to fetch them from disk
+</em> as we have to take care of missing data, accessing them requires an extra layer
of accessor to deal wth the fact they may be on disk, costing some extra memory</p>
+<p>Here, this is just a question of tradeoff : depending on your memory size, and the
level of robustness you want, you may decide to go for a in-memory <em>BTree</em>,
a persistent <em>BTree</em> or a managed one. Most of the time, though, managed
<em>BTree</em> is what you want to use.</p>
+<p>Also note that we use internal cache to speed up the data access. This cache and
its size can be configured.</p>
+<p>We will see how we manage <em>BTree</em>s internally.</p>
+<h3 id="users-btrees">User's BTrees</h3>
+<p>Managed user's <em>BTree</em>s are stored using <em>Nodes</em>
and <em>Leaves</em>. A <em>Node</em> contains only keys are references
to underlaying nodes or leaves. A <em>Leaf</em> contans keys and values. As we
don't want to eat too much memory, the references to nodes, meaves, keys and values are stored
as offset, read and translated to java objects on demand. For instance, we keep an offset
to a key until someone needs to access the key, then we deserialize this key and store it
in memory. This is the very same for references to nodes, leaves or values.</p>
+<p>Here is a schema describing this mechanism :</p>
+<p><img alt="Managed references" src="images/managedReferences.png" /></p>
+<p>In this schema, we have only loaded two pages in memory : the node and one leaf.
In these pages, the keys aren't yet objects, we are pointing to the page's raw data, except
for the <strong>D</strong> key which is already a Java Object (it has been deserialized).
The very same for the references to the leaves : we have only loaded and deserialized one
single leaf, the one containing the value <strong>D</strong>. In this leaf, the
keys aren't deserialized except the <strong>D</strong> key, and the only value
which is a Java instance is the deserialized <strong>vD</strong> value.</p>
+<p>So each elements is an instance of an encapsulating object which contains the offset
of the serialized element in a byte[], and the deserialized value if the value has already
been accessed.</p>
+<h3 id="special-btrees">Special BTrees</h3>
 <p>We have two special <em>BTree</em>s we use to manage the revisions and
the copied pages. We will explain what they are good for</p>
-<h3 id="revision-tree">Revision tree</h3>
+<h4 id="revision-tree">Revision tree</h4>
 <p>We need to keep a track of each active revision, so that a search can work with
a specific revision. The idea is that when a search starts, it uses the latest revision, but
as some modification can occur while teh search is bieng processed, some new revisions will
be added. In some case, we may want to keep a revision active for quite a long time.</p>
 <p>So we store the active revisions in a dedicated <em>BTree</em>.</p>
 <p>As we may have many <em>BTree</em>s, we have to use a key which is a
combinaison of the <em>BTree</em> name and its revision. So the revision <em>BTree</em>
manage the revisions of all the managed <em>BTree</em>s.</p>
 <p>When a revision is not anymore used, we can remove it from the revision <em>BTree</em>.</p>
 <p>This <em>BTree</em> is not a <strong>MVCC</strong> <em>BTree</em>,
like the other ones. In other words, we only keep the latest revision of this <em>BTree</em>
(ie, all the modified pages are immediately freed)</p>
-<h3 id="copied-pages-btree">Copied pages BTree</h3>
+<h4 id="copied-pages-btree">Copied pages BTree</h4>
 <p>Once we create a new revision, the pages we copied are not anymore in use except
if the revisions they are associated with are still in use. The problem is that we can't discard
those pages and move them to the free list until the associated revision is free.</p>
 <p>We use a dedicated <em>BTree</em> to keep a track of the copied pages,
which will be reclaimed and moved to the free pages list once the associated revision will
be released.</p>
-<h2 id="managing-the-free-pages">Managing the free pages</h2>
+<h3 id="managing-the-free-pages">Managing the free pages</h3>
 <p>We have a mechanism to manage the <em>PageIO</em> that are not anymore
in use. This is a linked list in which the free pages are added. If we need some page, we
first look into this list, and get back as many <em>PageIO</em>s as we need -
until we reach the end of this list. If we free some page, we add them at the end of the free
 <p>We always free a logical page, which may be stored into many <em>PageIO</em>s.
The good thing is that those <em>PageIO</em>s are already linked, so we just need
to make the last free <em>PageIO</em> to point on the first freed <em>PageIO</em>,
and to move the pointer to the last free page to the last <em>PageIO</em> used
to store the logical page.</p>

Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/InMemoryBTree.graphml
Binary file - no diff available.

Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/InMemoryBTree.graphml
    svn:mime-type = application/xml

Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/InMemoryBTree.png
Binary file - no diff available.

Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/InMemoryBTree.png
    svn:mime-type = image/png

Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/managedReferences.graphml
Binary file - no diff available.

Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/managedReferences.graphml
    svn:mime-type = application/xml

Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/managedReferences.png
Binary file - no diff available.

Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/managedReferences.png
    svn:mime-type = image/png

View raw message