directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <elecha...@gmail.com>
Subject Re: [Mavibot] Transactions & troubles...
Date Fri, 20 Dec 2013 08:21:18 GMT
After a second thought, it might be simpler to use 2 tables to store the
references to the current BTrees and to the modified btrees. Here is a a
small diagram exposing the data structure needed to manage the atomic
updates of btrees :

  Mavibot header
+-------------------------------------+
| PageIO size                         |
+-------------------------------------+
| number of managed btrees            |
+-------------------------------------+
| offset of the current Btree offsets |--+
+-------------------------------------+   \
| offset of the new BTree offsets     |----)--------------+
+-------------------------------------+   /               |
                                         |                |
               +-------------------------+                |
               |                                          |
               V                                          V
  +-------------------------+                +-------------------------+
  | next Offset             |---+            | next Offset             |---+
  +-------------------------+   |            +-------------------------+   |
  | size                    |   |            | size                    |   |
  +-------------------------+   |            +-------------------------+   |
  | +---------------------+ |   |            | +---------------------+ |   |
  | | first Btree offset  | |   |            | | first Btree offset  | |   |
  | +---------------------+ |   |            | +---------------------+ |   |
  | | second BTree offset | |   |            | | second BTree offset | |   |
  | +---------------------+ |   |            | +---------------------+ |   |
  |            .            |   |            |            .            |   |
  |            .            |   |            |            .            |   |
  |            .            |   |            |            .            |   |
  | +---------------------+ |   |            | +---------------------+ |   |
  | | Nth Btree offset    | |   |            | | Nth Btree offset    | |   |
  | +---------------------+ |   |            | +---------------------+ |   |
  +-------------------------+   |            +-------------------------+   |
                                |                                          |
               +----------------+                         +----------------+
               |                                          |
               V                                          V
  +-------------------------+                +-------------------------+
  | next Offset             |---/            | next Offset             |---/
  +-------------------------+                +-------------------------+
  | +---------------------+ |                | +---------------------+ |
  | | N+1th Btree offset  | |                | | N+1th Btree offset  | |
  | +---------------------+ |                | +---------------------+ |
  | | N+2th BTree offset  |------+           | | N+2th BTree offset  | |
  | +---------------------+ |    |           | +---------------------+ |
  |            .            |    |           |            .            |
  |            .            |    |           |            .            |
  |            .            |    |           |            .            |
  | +---------------------+ |    |           | +---------------------+ |
  | | last Btree offset   | |    |           | | last Btree offset   | |
  | +---------------------+ |    |           | +---------------------+ |
  |                         |    |           |                         |
  |                         |    |           |                         |
  +-------------------------+    |           +-------------------------+
                                 |
           +---------------------+
           |
       V
      Btree Header
  +------------------+
  | revision         |
  +------------------+
  | nbElems          |
  +------------------+
  | rootPage offset  |---+
  +------------------+   |
  | pageSize         |   |
  +------------------+   |
  | btree name       |   |
  +------------------+   |
  | key serializer   |   |
  +------------------+   |
  | value serializer |   |
  +------------------+   |
  | dups allowed     |   |
  +------------------+   |
                         |
                         +
                        / \
                       /   \
                      /     \
                     /       \
                    /         \
                   /           \
                  /             \
                 /               \
                /                 \
               /                   \
              +                     +
              |                     |
              V                     V
            Node                  Leaf
      +-----------------+  +-------------------+
      | revision        |  | revision          |
      +-----------------+  +-------------------+
      | nbElems         |  | nbElems           |
      +-----------------+  +-------------------+
      | dataSize        |  | dataSize          |
      +-----------------+  +-------------------+
      | child[0]        |  | value[0] length   |
      +-----------------+  +-------------------+
      | key[0] length   |  | value[0]          |
      +-----------------+  +-------------------+
      | key[0]          |  | key[0] length     |
      +-----------------+  +-------------------+
      | child[1]        |  | key[0]            |
      +-----------------+  +-------------------+
      | key[1] length   |  | value[1] length   |
      +-----------------+  +-------------------+
      | key[1]          |  | value[1]          |
      +-----------------+  +-------------------+
      |         .       |  | key[1] length     |
      |         .       |  +-------------------+
      |         .       |  | key[1]            |
      +-----------------+  +-------------------+
      | child[N-1]      |  |         .         |
      +-----------------+  |         .         |
      | key[N-1] length |  |         .         |
      +-----------------+  +-------------------+
      | key[N-1]        |  | value[N-1] length |
      +-----------------+  +-------------------+
      | child[N]        |  | value[N-1]        |
      +-----------------+  +-------------------+
                           | key[N-1] length   |
                           +-------------------+
                           | key[N-1]          |
                           +-------------------+

As you can see, we maintain 2 versions of the BTree offsets, and we
switch from the current one to the modified one by changing the first
page, so it's a one step operation.

Btw, the Node has been simplified : there is no need to keep the lentght
of page offsets, they are always 8 bytes long.

-- 
Regards,
Cordialement,
Emmanuel L├ęcharny
www.iktek.com 


Mime
View raw message