[Mavibot] status

[Emmanuel Lécharny <el...@gmail.com>]

Hi guys,

I have been quite busy those last weeks, with very few hours available
to work on ApacheDS, and more specifically Mavibot.

2 weeks ago, I forked Mavibot in order to be able to work in a branch
and not breaking the trunk, and all my modifications (plenty of them)
since january have been committed there.

As I stated earlier, I'm trying to implement transactions and revisions
in Mavibot, now that we have a working system with no revision (it's
actually a MVCC Btree, but with locks : nothing really different from a
standard btree...). I'm done with the in memory B-tree, and I'm
currently working on the persisted b-tree, which proves to be wayy more
complex, mainly due to the fact that I have to hexdump the file and
analyze its content to see if all is correct, something which takes
forever... I'm also missing some cycles to do that corectly (ie, I need
a few hours in a row, something I don't have).

However, I'm progressing. Some big structure changes have been done :
- I have modified the BTreeHeader to not contain any BTree informations,
and I moved those inforamtions into the BTree structure
- The layout on disk has changed :
  - we have now a separate page to contain the common b-tree info
(serializer, page size, etc).
  - the BTreeHeader contain a reference to the rootPage and the btree
info, but that's all
- the BtreeOfBtrees contain reference to a btreeHeader associated to a
tuple <btree, revision>
- I have added the beginTransaction/commit/roolback methods, but I
wasn't very successfull with the idea of mixing auto-commit and declared
commit. Atm, it's all auto-commit (ie, one can't have more than one
operation per transaction.)
- I'm trying to implement these algorithms :

manage BTree
============

- create new BtreeInfo -> BIO
- create new RootPage -> RPO
- create new BtreeHeader<BIO, RPO> -> BHO
- insert the BtreeHeader into the BOB btree <rev, BHO>
  - create a new RP -> BOB-RP[i+1]
  - create a new Header -> BOB-Header[i+1] <BOB-I, BOB-RP[i+1]>
  - add the copied pages of i into the free list
  - add the BOB-RP[i] page into the free-list
  - add the BOB-Header[i] page into the free-list
  - update the current BOB and the old BOB pointers
- update the recordManager header

Add element
===========

- create a new RP -> Tree-RP[n+1]
- create a new Header -> Tree-Header[n+1] <Tree-I, Tree-RP[n+1]>
- add the copied pages into the CPB (Tree-RP[n], Tree-Header[n], copied
nodes and leaves)
  - create a new RP -> CPB-RP[i+1]
  - create a new Header -> CPB-Header[i+1] <CPB-I, CPB-RP[i+1]>
  - add the copied pages of i into the free list
  - add the CPB-RP[i] page into the free-list
  - add the CPB-Header[i] page into the free-list
  - update the current CPB and the old CPB pointers
- add the new header into the BOB tree
  - create a new RP -> BOB-RP[j+1]
  - create a new Header -> BOB-Header[j+1] <BOB-I, BOB-RP[j+1]>
  - add the copied pages of j into the free list
  - add the BOB-RP[j] page into the free-list
  - add the BOB-Header[j] page into the free-list
  - update the current BOB and the old BOB pointers
- update the recordManager header

It's almost done (atm, I'm able to write down a new BTree).

I do think it's a matter of a couple of days to get this done, I'll try
to squeeze some time next week.

Thanks !

-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com 

Re: [Mavibot] status

[Emmanuel Lécharny <el...@gmail.com>]

Hi,

some progress today : the addition of elements into a managed BTree now
produces a correct file layout (except the CopiedPageBtree which is not
yet updated).

I have solved a problem I faced last month, when I tried to mix explicit
transactions with automatic transactions. The solution is based on a
ReentrantLock and a counter. When a thread tries to modify one btree, it
acquires the lock, and the counter is incremented. Fr any inner
operation on one of the two internal BTree, the counter is also incremented.
When the operaiton is done, a commit is called, and the counter is
decremented. When the counter is 0, then we can write everything on disk.

That means we have pending writes until the commit is done, and if the
user has created an explicit transaction, we may have many modifications
being done without having to write them down the disk, we will do that
only when the user commit the explicit transaction.

Now, it's working, but there is a lot to do to keep in memory those
pending modifications, and to refer to them when needed, instead of
fetching the pages on the disk. The solved pb was about the lock.

I'm now working on handling the CopiedPage btree updates.


Le 2/23/14 9:17 PM, Emmanuel Lécharny a écrit :
> Hi guys,
>
> I have been quite busy those last weeks, with very few hours available
> to work on ApacheDS, and more specifically Mavibot.
>
> 2 weeks ago, I forked Mavibot in order to be able to work in a branch
> and not breaking the trunk, and all my modifications (plenty of them)
> since january have been committed there.
>
> As I stated earlier, I'm trying to implement transactions and revisions
> in Mavibot, now that we have a working system with no revision (it's
> actually a MVCC Btree, but with locks : nothing really different from a
> standard btree...). I'm done with the in memory B-tree, and I'm
> currently working on the persisted b-tree, which proves to be wayy more
> complex, mainly due to the fact that I have to hexdump the file and
> analyze its content to see if all is correct, something which takes
> forever... I'm also missing some cycles to do that corectly (ie, I need
> a few hours in a row, something I don't have).
>
> However, I'm progressing. Some big structure changes have been done :
> - I have modified the BTreeHeader to not contain any BTree informations,
> and I moved those inforamtions into the BTree structure
> - The layout on disk has changed :
>   - we have now a separate page to contain the common b-tree info
> (serializer, page size, etc).
>   - the BTreeHeader contain a reference to the rootPage and the btree
> info, but that's all
> - the BtreeOfBtrees contain reference to a btreeHeader associated to a
> tuple <btree, revision>
> - I have added the beginTransaction/commit/roolback methods, but I
> wasn't very successfull with the idea of mixing auto-commit and declared
> commit. Atm, it's all auto-commit (ie, one can't have more than one
> operation per transaction.)
> - I'm trying to implement these algorithms :
>
> manage BTree
> ============
>
> - create new BtreeInfo -> BIO
> - create new RootPage -> RPO
> - create new BtreeHeader<BIO, RPO> -> BHO
> - insert the BtreeHeader into the BOB btree <rev, BHO>
>   - create a new RP -> BOB-RP[i+1]
>   - create a new Header -> BOB-Header[i+1] <BOB-I, BOB-RP[i+1]>
>   - add the copied pages of i into the free list
>   - add the BOB-RP[i] page into the free-list
>   - add the BOB-Header[i] page into the free-list
>   - update the current BOB and the old BOB pointers
> - update the recordManager header
>
> Add element
> ===========
>
> - create a new RP -> Tree-RP[n+1]
> - create a new Header -> Tree-Header[n+1] <Tree-I, Tree-RP[n+1]>
> - add the copied pages into the CPB (Tree-RP[n], Tree-Header[n], copied
> nodes and leaves)
>   - create a new RP -> CPB-RP[i+1]
>   - create a new Header -> CPB-Header[i+1] <CPB-I, CPB-RP[i+1]>
>   - add the copied pages of i into the free list
>   - add the CPB-RP[i] page into the free-list
>   - add the CPB-Header[i] page into the free-list
>   - update the current CPB and the old CPB pointers
> - add the new header into the BOB tree
>   - create a new RP -> BOB-RP[j+1]
>   - create a new Header -> BOB-Header[j+1] <BOB-I, BOB-RP[j+1]>
>   - add the copied pages of j into the free list
>   - add the BOB-RP[j] page into the free-list
>   - add the BOB-Header[j] page into the free-list
>   - update the current BOB and the old BOB pointers
> - update the recordManager header
>
> It's almost done (atm, I'm able to write down a new BTree).
>
> I do think it's a matter of a couple of days to get this done, I'll try
> to squeeze some time next week.
>
> Thanks !
>


-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com