From commits-return-37846-apmail-directory-commits-archive=directory.apache.org@directory.apache.org Mon Nov 25 09:42:31 2013 Return-Path: X-Original-To: apmail-directory-commits-archive@www.apache.org Delivered-To: apmail-directory-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5C15B10A8F for ; Mon, 25 Nov 2013 09:42:31 +0000 (UTC) Received: (qmail 62861 invoked by uid 500); 25 Nov 2013 09:42:27 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 62819 invoked by uid 500); 25 Nov 2013 09:42:25 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 62783 invoked by uid 99); 25 Nov 2013 09:42:20 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 25 Nov 2013 09:42:20 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 25 Nov 2013 09:42:19 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 21194238896F for ; Mon, 25 Nov 2013 09:41:59 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r888002 - in /websites/staging/directory/trunk/content: ./ mavibot/user-guide/ mavibot/user-guide/images/ Date: Mon, 25 Nov 2013 09:41:59 -0000 To: commits@directory.apache.org From: buildbot@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20131125094159.21194238896F@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: buildbot Date: Mon Nov 25 09:41:58 2013 New Revision: 888002 Log: Staging update by buildbot for directory Added: websites/staging/directory/trunk/content/mavibot/user-guide/7.3-serializations.html websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.graphml (with props) websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.png (with props) Modified: websites/staging/directory/trunk/content/ (props changed) websites/staging/directory/trunk/content/mavibot/user-guide/7.2-physical-storage.html Propchange: websites/staging/directory/trunk/content/ ------------------------------------------------------------------------------ --- cms:source-revision (original) +++ cms:source-revision Mon Nov 25 09:41:58 2013 @@ -1 +1 @@ -1545025 +1545189 Modified: websites/staging/directory/trunk/content/mavibot/user-guide/7.2-physical-storage.html ============================================================================== --- websites/staging/directory/trunk/content/mavibot/user-guide/7.2-physical-storage.html (original) +++ websites/staging/directory/trunk/content/mavibot/user-guide/7.2-physical-storage.html Mon Nov 25 09:41:58 2013 @@ -133,13 +133,13 @@
@@ -225,8 +225,6 @@ it's something we might want to change l

(The Node is not described, as it's basically the same data structure, but with one extra value).

It does not need more space to serialize the data this way, as the offsets are ints, and in the previous version, those ints are used to store the length of the keys and values anyway.

The gain is that we can have access to a given key and value without having to read all the previous keys and values. Also we can now read a leaf or a node without having to deserialize all the keys and values they contain.

-

Page serialization

-

We serialize Node and Leaf differently on disk, as seen in a previois paragraph.

Added: websites/staging/directory/trunk/content/mavibot/user-guide/7.3-serializations.html ============================================================================== --- websites/staging/directory/trunk/content/mavibot/user-guide/7.3-serializations.html (added) +++ websites/staging/directory/trunk/content/mavibot/user-guide/7.3-serializations.html Mon Nov 25 09:41:58 2013 @@ -0,0 +1,221 @@ + + + + + 7.3 - Serializations — Apache Directory + + + + + + + + + + + + +
+ +
+
+ + + +
+
+ + + + + +

7.3 - Serializations

+

The logical pages are serialized before being stored on physical pages. This is a process that should obviously be reversible. W will describe in this chapter how we serialize Leaf and Node.

+

Leaf serialization

+

A Leaf contains some medata data, and a set of keys and values. A key can have many values, and we have as many keys as values. That being said, let's describe the internal format of a serialized leaf :

+
+    +----------------------------------+
+    | revision (long)                  | 8 bytes
+    +----------------------------------+
+    | nbElems (int)                    | 4 bytes
+    +----------------------------------+
+    | dataSize (int)                   | 4 bytes = sum[0..nbElems]( valueLength, keyLength ) + 8 x nbElems
+    +----------------------------------+
+    | +------------------------------+ |
+    | | valueLength[0] (int)         | | 4 bytes \
+    | +------------------------------+ |           > n+4 bytes
+    | | value[0] (byte[])            | | n bytes /
+    | +------------------------------+ |
+    | | keyLength[0] (int)           | | 4 bytes \
+    | +------------------------------+ |           > n+4 bytes
+    | | key[0] (byte[])              | | n bytes /
+    | +------------------------------+ |
+    ...                              ...
+    | +------------------------------+ |
+    | | valueLength[nbElems-1] (int) | | 4 bytes \
+    | +------------------------------+ |           > n+4 bytes
+    | | value[nbElems-1] (byte[])    | | n bytes /
+    | +------------------------------+ |
+    | | keyLength[nbElems-1] (int)   | | 4 bytes \
+    | +------------------------------+ |           > n+4 bytes
+    | | key[nbElems-1] (byte[])      | | n bytes /
+    | +------------------------------+ |
+    +----------------------------------+
+
+
+ +

We keep the length of each serialized key and value just because we need to provide a complete byte[] to the key or value deserializer (ie, the exact number of bytes needed to be able to deserialize the key or the value).

+

The dataSize value is used so that we can know how many bytes we will have to read - thus the number of physical pages to read - in order to get a full page.

+

Leaf deserialization

+

On the other way, when we deserialize a leaf, we won't deserialize the keys and the values (it would be too expensive, if the leaf is discarded from memory immediately, when we only need to read one single key and value). We thus keep the byte[] form of each keys and each values, which will be deserialized on demand.

+

We use two data structures to store a key and a value : + a KeyHolder for the key a ValueHolder for the value

+

KeyHolder

+

ValueHolder

+ + + + + +
+
+
+ +
+ + Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.graphml ============================================================================== Binary file - no diff available. Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.graphml ------------------------------------------------------------------------------ svn:mime-type = application/xml Added: websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.png ============================================================================== Binary file - no diff available. Propchange: websites/staging/directory/trunk/content/mavibot/user-guide/images/ug-btree-has-prev.png ------------------------------------------------------------------------------ svn:mime-type = image/png