You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Emmanuel Lécharny <el...@gmail.com> on 2016/06/26 11:15:01 UTC
Rethinking Mavibot...
Hi guys,
now that I'm done with the LDAP API release and ApacheDS release, I'd
like to dedicate some time to complete Mavibot, as it's a critical part
of the server.
The current status is not exactly perfect. It's usable, but there is no
support for transaction across B-trees, which makes it as brittle as
JDBM when it comes to use it in ApacheDS (simply because an update
impact many B-Trees, so it has to be an all-or-nothing operation, which
implies a cross-B-trees transaction).
We have started to implement it in a branch (single-value) where other
changes have been applied :
- no support for multi-values (way too complex to support in this first
version)
- no support for in-memory B-trees (not critical, makes everything more
complex)
Here is how I see transactions being implemented :
- The recordManager will be responsible for creating new transactions.
- each operation on any B-tree will require an extra parameter, the
transaction that it belongs to
- transaction will not last forever, a default timeout of 30 mins will
be used, to avoid long-lasted transactions that would make the database
grow without control (keep in mind that a read transaction holds a
revision until it's aborted, which leads to holding old pages on disk).
So bottom line, here is what an operation will looks like :
RecordManager recordManager = new RecordManager( "MyDatabase" );
Transaction readTransaction = recordManager.beginReadTransaction();
BTree<Long, String> btree = recordManager.getManagedTree(
readTransaction, "MyBtree" );
boolean hasKey = btree.haskey( 1L );
readTransaction.abort(); // COuld have been commit();
More to come in the following weeks.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 02/07/16 � 00:38, Zheng, Kai a �crit :
> This sounds nice.
>
> In my view, we should probably start with the most popular platform like Linux and fallback to the current Java offering on other platforms that we don't support yet due to all kinds of constraints like resources and the library limit. Incrementally we can add to support more and more.
We just need the builds for the three different platforms we want to
support :
- linux, obviously
- Mac OSX
- Windows
We can embed the lib in our installers. All in all, we are talking about
2 files: the lib itself and the License file.
>
> By supporting a partition using LMDB, what did you mean? A partition using LMDB coexists with a partition using other means meanwhile? Thanks for the clarifying.
A Partition is a specific implementation of the LDAP backend based on a
specific DB engine. We have currently a support for JDBM, Mavibot, LDIF
and Oracle partitions.
However, we might change a few more things if we implement a LMDB
partition :
- we would make it the reference implementation
- we would change the LDAP server code to remove all the useless locks,
to have transaction being supported in the AbstractBTreePartition layer
I don't think that is a lot of work, and I do think it worth testing
that in a branch. I'll probably do that this summer.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
This sounds nice.
In my view, we should probably start with the most popular platform like Linux and fallback to the current Java offering on other platforms that we don't support yet due to all kinds of constraints like resources and the library limit. Incrementally we can add to support more and more.
By supporting a partition using LMDB, what did you mean? A partition using LMDB coexists with a partition using other means meanwhile? Thanks for the clarifying.
Regards,
Kai
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Saturday, July 02, 2016 5:03 AM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
As a matter of fact, things are moving in the LMDB landscape :
https://github.com/lmdbjava/lmdbjava
There is still some need of a Windows build for LMDB, but still, I think that would be great to have a partition that uses LMDB. Just for the sake of consitency.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
As a matter of fact, things are moving in the LMDB landscape :
https://github.com/lmdbjava/lmdbjava
There is still some need of a Windows build for LMDB, but still, I think
that would be great to have a partition that uses LMDB. Just for the
sake of consitency.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
That's right. We have to choose a broadly supported backend and include all the supported binary packages. Basically, we could have the current Mavibot or JDBM as the fallback. We should really really get it work in the best on the most typical platforms, such as Linux, and wouldn't worry too much about the else.
Regards,
Kai
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Monday, June 27, 2016 7:03 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
Le 27/06/16 à 12:49, Zheng, Kai a écrit :
> Thanks so much for the full explanation, Emmanuel. Sorry for my asking again.
>
>>> Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging.
> The packaging isn't really so much a problem. There is a nice way handling this: the binary package could be put into the jar just as a resource and while starting up it can be dynamically extracted, putted into a runtime folder to be loaded. Many Java projects do this way.
Yes, but that would require a built package for all the targets.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 12:49, Zheng, Kai a �crit :
> Thanks so much for the full explanation, Emmanuel. Sorry for my asking again.
>
>>> Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging.
> The packaging isn't really so much a problem. There is a nice way handling this: the binary package could be put into the jar just as a resource and while starting up it can be dynamically extracted, putted into a runtime folder to be loaded. Many Java projects do this way.
Yes, but that would require a built package for all the targets.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 02/07/16 � 00:50, Zheng, Kai a �crit :
> Hi Lucas,
>
> I understand what you meant and totally agree. That\u2019s why in the past years I would spend lots of spare time working on a pure Java Kerberos binding, Apache Kerby. However, for the backend part, as it regards to users\u2019 data, it must be strong so better to delegate to 3rd party offerings. You could think about this, developing another backend like Mavibot, would be how hard as it is being, while working on our core specific things such as LDAP and Kerberos, even given enough resources, right. It\u2019s good to have the current Java offering, and we can leverage it to do the unit testing, and fallback to some platforms, but basing on the fact that we have/support a strong backend for the most typical platform.
>
> Yes, the backend support should be pluggable and configurable so potentially the server can support whatever backend if the user would. Currently Apache Kerby goes that way.
So does ApacheDS. In order to switch from JDBM to Mavibot, you just have
a configuration to change. It can be improved, though, because we don't
have a Index factory.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
Hi Lucas,
I understand what you meant and totally agree. That’s why in the past years I would spend lots of spare time working on a pure Java Kerberos binding, Apache Kerby. However, for the backend part, as it regards to users’ data, it must be strong so better to delegate to 3rd party offerings. You could think about this, developing another backend like Mavibot, would be how hard as it is being, while working on our core specific things such as LDAP and Kerberos, even given enough resources, right. It’s good to have the current Java offering, and we can leverage it to do the unit testing, and fallback to some platforms, but basing on the fact that we have/support a strong backend for the most typical platform.
Yes, the backend support should be pluggable and configurable so potentially the server can support whatever backend if the user would. Currently Apache Kerby goes that way.
Regards,
Kai
From: Lucas Theisen [mailto:lucastheisen@pastdev.com]
Sent: Tuesday, June 28, 2016 9:26 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: RE: Rethinking Mavibot...
My 10 cents... a pure Java solution is much better for many reasons:
1) easier to use, don't have to think about a different version per OS
2) easier to build (obviously)
3) easier to test, don't have to worry about inconsistency introduced by different builds of the native lib
4) ...
That said, being able to plug in a different backend via configuration is always valuable, and already supported, so I certainly wouldn't complain if somebody wrote an adapter for the native storage engine.
Lucas
On Jun 28, 2016 8:57 AM, "Zheng, Kai" <ka...@intel.com>> wrote:
Yeah. It sounds like a great choice to consider https://github.com/deephacks/lmdbjni. It's still in updating. Would we proceed on this?
Anyway, will play around it this week and see if any concerns.
Regards,
Kai
-----Original Message-----
From: Shawn McKinney [mailto:smckinney@apache.org<ma...@apache.org>]
Sent: Monday, June 27, 2016 9:10 PM
To: Apache Directory Developers List <de...@directory.apache.org>>
Subject: Re: Rethinking Mavibot...
> On Jun 27, 2016, at 7:29 AM, Emmanuel Lécharny <el...@gmail.com>> wrote:
>
> Here is what I would suggest :
>
> - LMDB is an obvious candidate if we want to use something that
> exists, and which is proven to work.
> - There are a coupld of existing bindings for LMDB :
> https://github.com/deephacks/lmdbjni,
> https://github.com/chirino/lmdbjni
> (which is 3 years old)
> - We need to ensure that we have a build for Linux, Windows an MacOSX.
> A project like https://github.com/deephacks/lmdb might help
>
> We also need someone wanting to play around the idea.
This is a good discussion.
I agree with Kai, having a good and stable backend / database is critical to this project’s future. OTOH Emmanuel’s point that we’re open source (volunteers) is an obvious inhibiting factor.
So, do we have SWAG’s for the number of hours required for both approaches, i.e. apacheds w/ LMDB or Mavibot?
If we can have an apacheds & lmdb release in a few weeks, where mavibot might take many months, it might be worth a shot. Otherwise we should stay the course and not get sidetracked.
(my two cents)
Shawn
RE: Rethinking Mavibot...
Posted by Lucas Theisen <lu...@pastdev.com>.
My 10 cents... a pure Java solution is much better for many reasons:
1) easier to use, don't have to think about a different version per OS
2) easier to build (obviously)
3) easier to test, don't have to worry about inconsistency introduced by
different builds of the native lib
4) ...
That said, being able to plug in a different backend via configuration is
always valuable, and already supported, so I certainly wouldn't complain if
somebody wrote an adapter for the native storage engine.
Lucas
On Jun 28, 2016 8:57 AM, "Zheng, Kai" <ka...@intel.com> wrote:
> Yeah. It sounds like a great choice to consider
> https://github.com/deephacks/lmdbjni. It's still in updating. Would we
> proceed on this?
>
> Anyway, will play around it this week and see if any concerns.
>
> Regards,
> Kai
>
> -----Original Message-----
> From: Shawn McKinney [mailto:smckinney@apache.org]
> Sent: Monday, June 27, 2016 9:10 PM
> To: Apache Directory Developers List <de...@directory.apache.org>
> Subject: Re: Rethinking Mavibot...
>
>
> > On Jun 27, 2016, at 7:29 AM, Emmanuel Lécharny <el...@gmail.com>
> wrote:
> >
> > Here is what I would suggest :
> >
> > - LMDB is an obvious candidate if we want to use something that
> > exists, and which is proven to work.
> > - There are a coupld of existing bindings for LMDB :
> > https://github.com/deephacks/lmdbjni,
> > https://github.com/chirino/lmdbjni
> > (which is 3 years old)
> > - We need to ensure that we have a build for Linux, Windows an MacOSX.
> > A project like https://github.com/deephacks/lmdb might help
> >
> > We also need someone wanting to play around the idea.
>
> This is a good discussion.
>
> I agree with Kai, having a good and stable backend / database is critical
> to this project’s future. OTOH Emmanuel’s point that we’re open source
> (volunteers) is an obvious inhibiting factor.
>
> So, do we have SWAG’s for the number of hours required for both
> approaches, i.e. apacheds w/ LMDB or Mavibot?
>
> If we can have an apacheds & lmdb release in a few weeks, where mavibot
> might take many months, it might be worth a shot. Otherwise we should stay
> the course and not get sidetracked.
>
> (my two cents)
>
> Shawn
>
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
Yeah. It sounds like a great choice to consider https://github.com/deephacks/lmdbjni. It's still in updating. Would we proceed on this?
Anyway, will play around it this week and see if any concerns.
Regards,
Kai
-----Original Message-----
From: Shawn McKinney [mailto:smckinney@apache.org]
Sent: Monday, June 27, 2016 9:10 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
> On Jun 27, 2016, at 7:29 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
>
> Here is what I would suggest :
>
> - LMDB is an obvious candidate if we want to use something that
> exists, and which is proven to work.
> - There are a coupld of existing bindings for LMDB :
> https://github.com/deephacks/lmdbjni,
> https://github.com/chirino/lmdbjni
> (which is 3 years old)
> - We need to ensure that we have a build for Linux, Windows an MacOSX.
> A project like https://github.com/deephacks/lmdb might help
>
> We also need someone wanting to play around the idea.
This is a good discussion.
I agree with Kai, having a good and stable backend / database is critical to this project’s future. OTOH Emmanuel’s point that we’re open source (volunteers) is an obvious inhibiting factor.
So, do we have SWAG’s for the number of hours required for both approaches, i.e. apacheds w/ LMDB or Mavibot?
If we can have an apacheds & lmdb release in a few weeks, where mavibot might take many months, it might be worth a shot. Otherwise we should stay the course and not get sidetracked.
(my two cents)
Shawn
Re: Rethinking Mavibot...
Posted by Shawn McKinney <sm...@apache.org>.
> On Jun 27, 2016, at 7:29 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
>
> Here is what I would suggest :
>
> - LMDB is an obvious candidate if we want to use something that exists,
> and which is proven to work.
> - There are a coupld of existing bindings for LMDB :
> https://github.com/deephacks/lmdbjni, https://github.com/chirino/lmdbjni
> (which is 3 years old)
> - We need to ensure that we have a build for Linux, Windows an MacOSX. A
> project like https://github.com/deephacks/lmdb might help
>
> We also need someone wanting to play around the idea.
This is a good discussion.
I agree with Kai, having a good and stable backend / database is critical to this project’s future. OTOH Emmanuel’s point that we’re open source (volunteers) is an obvious inhibiting factor.
So, do we have SWAG’s for the number of hours required for both approaches, i.e. apacheds w/ LMDB or Mavibot?
If we can have an apacheds & lmdb release in a few weeks, where mavibot might take many months, it might be worth a shot. Otherwise we should stay the course and not get sidetracked.
(my two cents)
Shawn
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 13:02, Zheng, Kai a �crit :
> I really think the community need to think about this seriously because it regards how the parent project would evolve in the long term. Lacking a strong and solid LDAP server backend, it would shade our many efforts in other aspects. Considering we're lacking of enough hands here and implementing a high reliability and performance in favor of modern hardware capabilities would take lots of time, I strongly suggest we look at alternative options, and proceed in much easier way.
Here is what I would suggest :
- LMDB is an obvious candidate if we want to use something that exists,
and which is proven to work.
- There are a coupld of existing bindings for LMDB :
https://github.com/deephacks/lmdbjni, https://github.com/chirino/lmdbjni
(which is 3 years old)
- We need to ensure that we have a build for Linux, Windows an MacOSX. A
project like https://github.com/deephacks/lmdb might help
We also need someone wanting to play around the idea.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
I really think the community need to think about this seriously because it regards how the parent project would evolve in the long term. Lacking a strong and solid LDAP server backend, it would shade our many efforts in other aspects. Considering we're lacking of enough hands here and implementing a high reliability and performance in favor of modern hardware capabilities would take lots of time, I strongly suggest we look at alternative options, and proceed in much easier way.
Regards,
Kai
-----Original Message-----
From: Zheng, Kai [mailto:kai.zheng@intel.com]
Sent: Monday, June 27, 2016 6:49 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: RE: Rethinking Mavibot...
Thanks so much for the full explanation, Emmanuel. Sorry for my asking again.
>> Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging.
The packaging isn't really so much a problem. There is a nice way handling this: the binary package could be put into the jar just as a resource and while starting up it can be dynamically extracted, putted into a runtime folder to be loaded. Many Java projects do this way.
If we could go this way, I would love to do this and support in other aspects as well as possible, because it would sound very promising to come up a high performance and high reliability LDAP server for the Apache world.
Regards,
Kai
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Monday, June 27, 2016 6:03 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
Le 27/06/16 à 08:07, Zheng, Kai a écrit :
> Thanks for the update.
>
> It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
I think we already discussed that matter months ago. I also think that many don't understand why we *need* somthing like Mavibot. But let me try to explain again...
Back in 2006, we knew that we were going to have troubles with our choice (JDBM). Back then, we had little choice though :
- JDBM was the only open source, license compatible B-tree implementation in Java available.
- We had other more important issues to cope with.
However, during the Austin Apache Conference, during which CiuchDB was announced, we had a long discussion with Alex, Pierre-Arnaud and Ersin about the fact that we would need a MVCC based backend. Sadly, CouchDB was written in Erlang, so we had to wait.
We waited until 2011, where it appears that concurrent searches and updates would eventually generate errors (typically, some searches would fail). We added a hell lot of locks, up to the point it was impossible to do a search while doing an update, which was a very expensive penalty to pay. At teh same time, we started to look at alternatives, that does not include a rewite. Some guy started to implement MVCC on top of JDBM, but the result was not pleasant : if for any reason you forgot to close a cursor, the server would go west in a matter of minute. We can't forces the client to carrefully close their cursor, it was simply not an option, so we ditched the work.
What alternative did we have ? Not so much : Berkeley DB has been bought by Oracle, and the JE wasn't available with a compatible license. And as of today, there aren't any MVCC B-Tree implementation that I know of, with a compatible license. So we are in a kind of dead lock.
Funny enough, at the very same time, OpenLDAP has started to work on the exact same piece of code, for the exact same reason (BDB has changed its license, and some data corruption could occur under certain circonstances, requiering a tool to repair the database). So we new we weren't in bad company !
Bottom line, I started to work on a replacement for JDBM, which get pushed in the repository on january 2012 ( I started to work on that in the mid 2011). Kiran ported ApacheDS to use Mavibot as a backend around Srping 2013, and we now have an ApacheDS server that *works* with Mavibot. Not only that, but it's also faster than JDBM.
Is it enough ? No. For one single reason : Mavibot with no transaction support won't be any better than JDBM, for the exact same reasons : if we have a crash, we will potentially ends with a corrupted database (less often than JDBM but still). It's way better though because we can't have a failure during a search while updates are done, and courruption could be fixed easily.
Mavibot brings some other extra bonuses : we now can inject data in bulk mode, which is orders of magnitude faster than adding data when the server is up and running.
Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging. Right now, ApacheDS comes as a bundled package, or as an installer for Linux, Mac OSX and Windows. Having a dependency on a binary component might be a real trouble when it comes to package it properly. ATM, I'm not willing to spend some time on this aspect.
Last, not least, Mavibot is *NOT* a B-tree implementation. It's a MVCC (Multi-Version Concurrency Control B-tree implementation
(https://en.wikipedia.org/wiki/Multiversion_concurrency_control) which is *VERY* different. The critical aspect is the MVCC part, this is what guarantees consistancy, and lock free access to the underlying database.
What we are lacking atm, is the cross B-trees transaction support. This is what will bring two critical improvements to the ApacheDS server :
1) No need to implement a mechanism to restore a database if it crashes in the middle of an update (a LDAP update requires multiple updates to multiple indexes - typically 10 minimum, with some indexes being updated more than once, like the RDN index -).
2) Speed ! During a transaction, we work in memory, until we are done (with a commit or an abort). That saves us multiple updates on disk.
Typically, we would save 50% of the writes for a single Add operation.
That means an Add would be twice faster.
I hope this clarify the reason why we started to develop Mavibot, even though it's not going as fast as it should (well, at some point, we have a life, and a day job, that both don't let us work as much as we would like on our favorite project).
I would end by telling everyone that this is an Open Source project, and anyone is greatly welcome if they want to give an hand...
Thanks for 'listening'.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
Thanks so much for the full explanation, Emmanuel. Sorry for my asking again.
>> Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging.
The packaging isn't really so much a problem. There is a nice way handling this: the binary package could be put into the jar just as a resource and while starting up it can be dynamically extracted, putted into a runtime folder to be loaded. Many Java projects do this way.
If we could go this way, I would love to do this and support in other aspects as well as possible, because it would sound very promising to come up a high performance and high reliability LDAP server for the Apache world.
Regards,
Kai
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Monday, June 27, 2016 6:03 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
Le 27/06/16 à 08:07, Zheng, Kai a écrit :
> Thanks for the update.
>
> It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
I think we already discussed that matter months ago. I also think that many don't understand why we *need* somthing like Mavibot. But let me try to explain again...
Back in 2006, we knew that we were going to have troubles with our choice (JDBM). Back then, we had little choice though :
- JDBM was the only open source, license compatible B-tree implementation in Java available.
- We had other more important issues to cope with.
However, during the Austin Apache Conference, during which CiuchDB was announced, we had a long discussion with Alex, Pierre-Arnaud and Ersin about the fact that we would need a MVCC based backend. Sadly, CouchDB was written in Erlang, so we had to wait.
We waited until 2011, where it appears that concurrent searches and updates would eventually generate errors (typically, some searches would fail). We added a hell lot of locks, up to the point it was impossible to do a search while doing an update, which was a very expensive penalty to pay. At teh same time, we started to look at alternatives, that does not include a rewite. Some guy started to implement MVCC on top of JDBM, but the result was not pleasant : if for any reason you forgot to close a cursor, the server would go west in a matter of minute. We can't forces the client to carrefully close their cursor, it was simply not an option, so we ditched the work.
What alternative did we have ? Not so much : Berkeley DB has been bought by Oracle, and the JE wasn't available with a compatible license. And as of today, there aren't any MVCC B-Tree implementation that I know of, with a compatible license. So we are in a kind of dead lock.
Funny enough, at the very same time, OpenLDAP has started to work on the exact same piece of code, for the exact same reason (BDB has changed its license, and some data corruption could occur under certain circonstances, requiering a tool to repair the database). So we new we weren't in bad company !
Bottom line, I started to work on a replacement for JDBM, which get pushed in the repository on january 2012 ( I started to work on that in the mid 2011). Kiran ported ApacheDS to use Mavibot as a backend around Srping 2013, and we now have an ApacheDS server that *works* with Mavibot. Not only that, but it's also faster than JDBM.
Is it enough ? No. For one single reason : Mavibot with no transaction support won't be any better than JDBM, for the exact same reasons : if we have a crash, we will potentially ends with a corrupted database (less often than JDBM but still). It's way better though because we can't have a failure during a search while updates are done, and courruption could be fixed easily.
Mavibot brings some other extra bonuses : we now can inject data in bulk mode, which is orders of magnitude faster than adding data when the server is up and running.
Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But I have no idea what it would cost us in term of packaging. Right now, ApacheDS comes as a bundled package, or as an installer for Linux, Mac OSX and Windows. Having a dependency on a binary component might be a real trouble when it comes to package it properly. ATM, I'm not willing to spend some time on this aspect.
Last, not least, Mavibot is *NOT* a B-tree implementation. It's a MVCC (Multi-Version Concurrency Control B-tree implementation
(https://en.wikipedia.org/wiki/Multiversion_concurrency_control) which is *VERY* different. The critical aspect is the MVCC part, this is what guarantees consistancy, and lock free access to the underlying database.
What we are lacking atm, is the cross B-trees transaction support. This is what will bring two critical improvements to the ApacheDS server :
1) No need to implement a mechanism to restore a database if it crashes in the middle of an update (a LDAP update requires multiple updates to multiple indexes - typically 10 minimum, with some indexes being updated more than once, like the RDN index -).
2) Speed ! During a transaction, we work in memory, until we are done (with a commit or an abort). That saves us multiple updates on disk.
Typically, we would save 50% of the writes for a single Add operation.
That means an Add would be twice faster.
I hope this clarify the reason why we started to develop Mavibot, even though it's not going as fast as it should (well, at some point, we have a life, and a day job, that both don't let us work as much as we would like on our favorite project).
I would end by telling everyone that this is an Open Source project, and anyone is greatly welcome if they want to give an hand...
Thanks for 'listening'.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 13:05, Zheng, Kai a �crit :
>>> Transaction has to be started explicitely from the LDAP layer...
> Yeah, I agree. But that doesn't mean the LDAP layer has to implement the transaction support itself. It just needs to aware, start and end the transaction when performing add/delete/update operations.
...And this is why we need to implement the transaction engine in
Mavibot ;-)
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
>> Transaction has to be started explicitely from the LDAP layer...
Yeah, I agree. But that doesn't mean the LDAP layer has to implement the transaction support itself. It just needs to aware, start and end the transaction when performing add/delete/update operations.
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Monday, June 27, 2016 6:52 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
Le 27/06/16 à 12:33, Zheng, Kai a écrit :
> Yes, I agree. Is it possible to be a lightweight wrapper on top of the plugined DB enginene, for example, we wouldn't need to support the transaction stuffs by ourselves?
No. Transaction has to be started explicitely from the LDAP layer, which means either youhave to use a DB backend that support cross-B-trees transactions or you have to implement it above the DB backend, which is clearly not simple, and will not be simple.
> Is there any LDAP-centric engine already
There is no such thing.
> or allowing to do the mapping very directly?
The mapping is simple (kind of), as soon as you know how to use a key-value store.
There is no magic involved.
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 12:33, Zheng, Kai a �crit :
> Yes, I agree. Is it possible to be a lightweight wrapper on top of the plugined DB enginene, for example, we wouldn't need to support the transaction stuffs by ourselves?
No. Transaction has to be started explicitely from the LDAP layer, which
means either youhave to use a DB backend that support cross-B-trees
transactions or you have to implement it above the DB backend, which is
clearly not simple, and will not be simple.
> Is there any LDAP-centric engine already
There is no such thing.
> or allowing to do the mapping very directly?
The mapping is simple (kind of), as soon as you know how to use a
key-value store.
There is no magic involved.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
Yes, I agree. Is it possible to be a lightweight wrapper on top of the plugined DB enginene, for example, we wouldn't need to support the transaction stuffs by ourselves? Is there any LDAP-centric engine already or allowing to do the mapping very directly?
Regards,
Kai
-----Original Message-----
From: Howard Chu [mailto:hyc@symas.com]
Sent: Monday, June 27, 2016 6:15 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Re: Rethinking Mavibot...
Emmanuel Lécharny wrote:
> Le 27/06/16 à 08:07, Zheng, Kai a écrit :
>> Thanks for the update.
>>
>> It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
> I think we already discussed that matter months ago. I also think that
> many don't understand why we *need* somthing like Mavibot. But let me
> try to explain again...
As an aside, there are two things going on here - you need both an underlying DB engine, and you need an LDAP-centric "backend" on top of it. Even if you tried to plug in an off-the-shelf DB engine, you still need to implement the backend that uses it.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 12:15, Howard Chu a �crit :
> Emmanuel L�charny wrote:
>> Le 27/06/16 � 08:07, Zheng, Kai a �crit :
>>> Thanks for the update.
>>>
>>> It looks like to me there is much work to do. Is there any
>>> alternative option? I'm still thinking that if we could leverage any
>>> existing back end implementation, so we could focus on the LDAP
>>> specific logic for the master server component...this is worth being
>>> considered because in today's industry there are so many B-TREE's
>>> implementations already.
>> I think we already discussed that matter months ago. I also think that
>> many don't understand why we *need* somthing like Mavibot. But let me
>> try to explain again...
>
> As an aside, there are two things going on here - you need both an
> underlying DB engine, and you need an LDAP-centric "backend" on top of
> it. Even if you tried to plug in an off-the-shelf DB engine, you still
> need to implement the backend that uses it.
We have the abstracted layer for a decade now. That allowed us to use a
LDIF based backend, a JDBM backend, a BerkeleyDB backend, An Oracle
RDBMS backend and a Mavibot backend, beside a in-memory backend. And,
yes, this is a mandatory piece of the puzzle.
Re: Rethinking Mavibot...
Posted by Howard Chu <hy...@symas.com>.
Emmanuel L�charny wrote:
> Le 27/06/16 � 08:07, Zheng, Kai a �crit :
>> Thanks for the update.
>>
>> It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
> I think we already discussed that matter months ago. I also think that
> many don't understand why we *need* somthing like Mavibot. But let me
> try to explain again...
As an aside, there are two things going on here - you need both an underlying
DB engine, and you need an LDAP-centric "backend" on top of it. Even if you
tried to plug in an off-the-shelf DB engine, you still need to implement the
backend that uses it.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
Re: Rethinking Mavibot...
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 27/06/16 � 08:07, Zheng, Kai a �crit :
> Thanks for the update.
>
> It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
I think we already discussed that matter months ago. I also think that
many don't understand why we *need* somthing like Mavibot. But let me
try to explain again...
Back in 2006, we knew that we were going to have troubles with our
choice (JDBM). Back then, we had little choice though :
- JDBM was the only open source, license compatible B-tree
implementation in Java available.
- We had other more important issues to cope with.
However, during the Austin Apache Conference, during which CiuchDB was
announced, we had a long discussion with Alex, Pierre-Arnaud and Ersin
about the fact that we would need a MVCC based backend. Sadly, CouchDB
was written in Erlang, so we had to wait.
We waited until 2011, where it appears that concurrent searches and
updates would eventually generate errors (typically, some searches would
fail). We added a hell lot of locks, up to the point it was impossible
to do a search while doing an update, which was a very expensive penalty
to pay. At teh same time, we started to look at alternatives, that does
not include a rewite. Some guy started to implement MVCC on top of JDBM,
but the result was not pleasant : if for any reason you forgot to close
a cursor, the server would go west in a matter of minute. We can't
forces the client to carrefully close their cursor, it was simply not an
option, so we ditched the work.
What alternative did we have ? Not so much : Berkeley DB has been bought
by Oracle, and the JE wasn't available with a compatible license. And as
of today, there aren't any MVCC B-Tree implementation that I know of,
with a compatible license. So we are in a kind of dead lock.
Funny enough, at the very same time, OpenLDAP has started to work on the
exact same piece of code, for the exact same reason (BDB has changed its
license, and some data corruption could occur under certain
circonstances, requiering a tool to repair the database). So we new we
weren't in bad company !
Bottom line, I started to work on a replacement for JDBM, which get
pushed in the repository on january 2012 ( I started to work on that in
the mid 2011). Kiran ported ApacheDS to use Mavibot as a backend around
Srping 2013, and we now have an ApacheDS server that *works* with
Mavibot. Not only that, but it's also faster than JDBM.
Is it enough ? No. For one single reason : Mavibot with no transaction
support won't be any better than JDBM, for the exact same reasons : if
we have a crash, we will potentially ends with a corrupted database
(less often than JDBM but still). It's way better though because we
can't have a failure during a search while updates are done, and
courruption could be fixed easily.
Mavibot brings some other extra bonuses : we now can inject data in bulk
mode, which is orders of magnitude faster than adding data when the
server is up and running.
Otherwise, we could use LMDB, with a JNI wrapper. That is an option. But
I have no idea what it would cost us in term of packaging. Right now,
ApacheDS comes as a bundled package, or as an installer for Linux, Mac
OSX and Windows. Having a dependency on a binary component might be a
real trouble when it comes to package it properly. ATM, I'm not willing
to spend some time on this aspect.
Last, not least, Mavibot is *NOT* a B-tree implementation. It's a MVCC
(Multi-Version Concurrency Control B-tree implementation
(https://en.wikipedia.org/wiki/Multiversion_concurrency_control) which
is *VERY* different. The critical aspect is the MVCC part, this is what
guarantees consistancy, and lock free access to the underlying database.
What we are lacking atm, is the cross B-trees transaction support. This
is what will bring two critical improvements to the ApacheDS server :
1) No need to implement a mechanism to restore a database if it crashes
in the middle of an update (a LDAP update requires multiple updates to
multiple indexes - typically 10 minimum, with some indexes being updated
more than once, like the RDN index -).
2) Speed ! During a transaction, we work in memory, until we are done
(with a commit or an abort). That saves us multiple updates on disk.
Typically, we would save 50% of the writes for a single Add operation.
That means an Add would be twice faster.
I hope this clarify the reason why we started to develop Mavibot, even
though it's not going as fast as it should (well, at some point, we have
a life, and a day job, that both don't let us work as much as we would
like on our favorite project).
I would end by telling everyone that this is an Open Source project, and
anyone is greatly welcome if they want to give an hand...
Thanks for 'listening'.
RE: Rethinking Mavibot...
Posted by "Zheng, Kai" <ka...@intel.com>.
Thanks for the update.
It looks like to me there is much work to do. Is there any alternative option? I'm still thinking that if we could leverage any existing back end implementation, so we could focus on the LDAP specific logic for the master server component...this is worth being considered because in today's industry there are so many B-TREE's implementations already.
Sorry for the bothering and interrupting.
Regards,
Kai
-----Original Message-----
From: Emmanuel Lécharny [mailto:elecharny@gmail.com]
Sent: Sunday, June 26, 2016 7:15 PM
To: Apache Directory Developers List <de...@directory.apache.org>
Subject: Rethinking Mavibot...
Hi guys,
now that I'm done with the LDAP API release and ApacheDS release, I'd like to dedicate some time to complete Mavibot, as it's a critical part of the server.
The current status is not exactly perfect. It's usable, but there is no support for transaction across B-trees, which makes it as brittle as JDBM when it comes to use it in ApacheDS (simply because an update impact many B-Trees, so it has to be an all-or-nothing operation, which implies a cross-B-trees transaction).
We have started to implement it in a branch (single-value) where other changes have been applied :
- no support for multi-values (way too complex to support in this first
version)
- no support for in-memory B-trees (not critical, makes everything more
complex)
Here is how I see transactions being implemented :
- The recordManager will be responsible for creating new transactions.
- each operation on any B-tree will require an extra parameter, the transaction that it belongs to
- transaction will not last forever, a default timeout of 30 mins will be used, to avoid long-lasted transactions that would make the database grow without control (keep in mind that a read transaction holds a revision until it's aborted, which leads to holding old pages on disk).
So bottom line, here is what an operation will looks like :
RecordManager recordManager = new RecordManager( "MyDatabase" );
Transaction readTransaction = recordManager.beginReadTransaction();
BTree<Long, String> btree = recordManager.getManagedTree( readTransaction, "MyBtree" );
boolean hasKey = btree.haskey( 1L );
readTransaction.abort(); // COuld have been commit();
More to come in the following weeks.