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 2013/02/16 11:19:09 UTC
Backend improvements
Hi guys,
this week I worked on some improvements for the insertion operations
(add, delete, modify, etc), because since the last version, the
performances are really bad (well, way slower than it was 6 months earlier).
The reason we have worst performance is simplein order to guarantee that
the database is stable even if the server crashes, I have activated the
transaction support. It's great, from the data acces POV (even after a
crash, the base is restored at startup and we can access the data, which
was not the case before). The drawback is that inserting data is now 10
times slower: with M8, I was able to inject 600 entries per second, I'm
now leveling out at 50 per second - and it depends on the number of
indexes).
So I have modified the code yesterday to increase the performances.
There are two things ot consider when injectong data in a BTree with
transaction enabled :
- the number of entries stored in memory before being committed into a
journal
- the number of entries stored in the journal before being flushed to
the database
Obviously, teh second number must be higher than the first number (it
makes no sense to flush a journal which has not been updated yet).
I onducted some basic tests on JDBM, with various values. Here are some
of the results :
Old JDBM, no TM :
-----------------
13130ms transaction disabled
3770ms transaction disabled
3768ms transaction disabled
3756ms transaction disabled
3678ms transaction disabled
3678ms transaction disabled
3667ms transaction disabled
3687ms transaction disabled
3732ms transaction disabled
3721ms transaction disabled
average 3731ms
JDBM2, no TM :
--------------
12339ms transaction disabled
4087ms transaction disabled
4081ms transaction disabled
4050ms transaction disabled
4015ms transaction disabled
4003ms transaction disabled
4003ms transaction disabled
3973ms transaction disabled
4003ms transaction disabled
3986ms transaction disabled
average 4022ms (8% slower)
old JDBM, with a transaction manager (TM) :
-------------------------------------------
Here, CI = commits, and Sync = flush on disk.
18130ms with CI, Sync [1,1]
14448ms with CI, Sync [1,2]
12934ms with CI, Sync [1,5]
12264ms with CI, Sync [1,10]
11845ms with CI, Sync [1,20]
11481ms with CI, Sync [1,50]
11499ms with CI, Sync [1,100]
11423ms with CI, Sync [1,200]
11487ms with CI, Sync [1,500]
11481ms with CI, Sync [1,1000]
11534ms with CI, Sync [1,2000]
11471ms with CI, Sync [1,5000]
11550ms with CI, Sync [1,10000]
11300ms with CI, Sync [2,2]
9923ms with CI, Sync [2,5]
9177ms with CI, Sync [2,10]
8672ms with CI, Sync [2,20]
8454ms with CI, Sync [2,50]
1922030ms with CI, Sync [2,100]
8530ms with CI, Sync [2,200]
8324ms with CI, Sync [2,500]
8363ms with CI, Sync [2,1000]
8381ms with CI, Sync [2,2000]
8417ms with CI, Sync [2,5000]
8361ms with CI, Sync [2,10000]
7772ms with CI, Sync [5,5]
7191ms with CI, Sync [5,10]
6737ms with CI, Sync [5,20]
6503ms with CI, Sync [5,50]
6398ms with CI, Sync [5,100]
6398ms with CI, Sync [5,200]
6448ms with CI, Sync [5,500]
6428ms with CI, Sync [5,1000]
6371ms with CI, Sync [5,2000]
6385ms with CI, Sync [5,5000]
6422ms with CI, Sync [5,10000]
6348ms with CI, Sync [10,10]
5844ms with CI, Sync [10,20]
5565ms with CI, Sync [10,50]
5473ms with CI, Sync [10,100]
5471ms with CI, Sync [10,200]
5453ms with CI, Sync [10,500]
5491ms with CI, Sync [10,1000]
5517ms with CI, Sync [10,2000]
5950ms with CI, Sync [10,5000]
5806ms with CI, Sync [10,10000]
5054ms with CI, Sync [20,20]
4769ms with CI, Sync [20,50]
4657ms with CI, Sync [20,100]
4663ms with CI, Sync [20,200]
4650ms with CI, Sync [20,500]
4622ms with CI, Sync [20,1000]
4664ms with CI, Sync [20,2000]
4634ms with CI, Sync [20,5000]
4662ms with CI, Sync [20,10000]
4243ms with CI, Sync [50,50]
4134ms with CI, Sync [50,100]
4123ms with CI, Sync [50,200]
4107ms with CI, Sync [50,500]
4162ms with CI, Sync [50,1000]
4115ms with CI, Sync [50,2000]
4105ms with CI, Sync [50,5000]
4143ms with CI, Sync [50,10000]
3982ms with CI, Sync [100,100]
3926ms with CI, Sync [100,200]
3913ms with CI, Sync [100,500]
3948ms with CI, Sync [100,1000]
3942ms with CI, Sync [100,2000]
3934ms with CI, Sync [100,5000]
3936ms with CI, Sync [100,10000]
3928ms with CI, Sync [200,200]
3909ms with CI, Sync [200,500]
4116ms with CI, Sync [200,1000]
4016ms with CI, Sync [200,2000]
3919ms with CI, Sync [200,5000]
3892ms with CI, Sync [200,10000]
3797ms with CI, Sync [500,500]
3798ms with CI, Sync [500,1000]
3814ms with CI, Sync [500,2000]
3790ms with CI, Sync [500,5000]
3818ms with CI, Sync [500,10000]
3725ms with CI, Sync [1000,1000]
3786ms with CI, Sync [1000,2000]
3736ms with CI, Sync [1000,5000]
3769ms with CI, Sync [1000,10000]
3682ms with CI, Sync [2000,2000]
3678ms with CI, Sync [2000,5000]
3691ms with CI, Sync [2000,10000]
3459ms with CI, Sync [5000,5000]
3493ms with CI, Sync [5000,10000]
3277ms with CI, Sync [10000,10000]
As we can see, the more we differ the writings, the better the performances.
So I ajusted the parameters on the server, and I currently do a commit
every 2000 changes, and a flsuh every 4000 changes. It's hard coded atm,
but I will make it configurable.
The performances went up from 50 add per second to 185 add per second.
Good, but nothing to get excited with, compared to the 600 add/s we had
:/ With such numbers, it will take roughly 1h30 to inject 1M entries...
What can we do to improve those performances then ?
Atm, with JDBM, I see no bright future. There are ways to squeeze a bit
of performance though, but not a lot : we can bypass the full chain, and
inject the data directly into the btrees, but the gain will be marginal.
So here are a few possibities :
1) Add raw injection of data feature in JDBM
The idea is to order the data before injecting them, and apply an
algoithm that build the pages, without having to pass through the tree
reordering. If we can have N elements in each page, we order the data,
and we store N elements in each page keeping the largest element of each
page in a separate list. This is for the leaves. Then reproduce the same
procssing on the gathered list, but for parent pages - and link to the
leaves. etc, up to the root.
This is the fastest way to store data in a btree.
This requires a few operations :
- order the data on disk : an O(N x log(N)) operation
- modify JDBM to allow us to inject data in a page directly
I evaluate this to two or three weeks of work. The gan will be quite
big, the slower operation being the ordering of data
Although we are stuck with JDBM lack of globa transaction system, which
forces us to lock every operatio (including searches) while we add some
entries.
2) Switch to JDBM 4
We have to evaluate what JDBM 4 is briging to us. It's obviously a
better base, but we don't know to what extent, and we don't know if :
- we can have global corss-btrees transactions
- we can inject raw data in the files without going through the btree
operations
Evaluating JDBM4 is probably a week of work
3) Switch to Mavibot
Mavibot is a labs I started last year, which implements a MVCC Btree in
memory. It's working, t's fast, but it's in memory only atm (although
the data are regularly flushed on disk).
We need to improve it so that we add those features :
- Make it backed with a physical layer that access data on disk, and
avoid storing everything in memory
- Add a raw load feature
- Add a global transaction system, cross trees.
The last feature is probably easier to implement, as we do have a
version associated with each new modification : if we retin the version
we started with, we can gather all the btree's revision, and validate
them all in one shot, or rollback them all in one shot (a revision is
visible only if it has been validated).
One very interestig aspect of Mavibot is that you can update the btrees
concurrently with searches : searches are done on older revisions, which
don't interract with the pages being added.
I think there is one to two more month of work on Mavibot to get it to
the level we need.
Proposal
--------
IMO, we should investigate JDBM4 asap. It might solve many of the issues
we have, at a low price. Improving the existing JDBM is just a waste of
our precious time.
I the long term, I would favor Mavibot for a couple of reasons :
- first, it's a MVCC base, so we can conduct concurrent searches and
modifications (although we can't do many modifications at the same time).
- second, we have a complete understanding of the code : we wrote it.
It's easier to understand the impact of the modifications we hve done on it.
- third, we can have a dedicated backend based on the current Mavibot
code, where all the data are in memory (that would work with a few tens
of thousands entries, and the performances will be blazing fast).
I'd like to know what's your opinion.
Thanks !
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Backend improvements
Posted by Kiran Ayyagari <ka...@apache.org>.
On Sat, Feb 16, 2013 at 3:49 PM, Emmanuel Lécharny <el...@gmail.com>wrote:
> Hi guys,
>
> this week I worked on some improvements for the insertion operations
> (add, delete, modify, etc), because since the last version, the
> performances are really bad (well, way slower than it was 6 months
> earlier).
>
> The reason we have worst performance is simplein order to guarantee that
> the database is stable even if the server crashes, I have activated the
> transaction support. It's great, from the data acces POV (even after a
> crash, the base is restored at startup and we can access the data, which
> was not the case before). The drawback is that inserting data is now 10
> times slower: with M8, I was able to inject 600 entries per second, I'm
> now leveling out at 50 per second - and it depends on the number of
> indexes).
>
> So I have modified the code yesterday to increase the performances.
> There are two things ot consider when injectong data in a BTree with
> transaction enabled :
> - the number of entries stored in memory before being committed into a
> journal
> - the number of entries stored in the journal before being flushed to
> the database
>
> Obviously, teh second number must be higher than the first number (it
> makes no sense to flush a journal which has not been updated yet).
>
> I onducted some basic tests on JDBM, with various values. Here are some
> of the results :
>
> Old JDBM, no TM :
> -----------------
>
> 13130ms transaction disabled
> 3770ms transaction disabled
> 3768ms transaction disabled
> 3756ms transaction disabled
> 3678ms transaction disabled
> 3678ms transaction disabled
> 3667ms transaction disabled
> 3687ms transaction disabled
> 3732ms transaction disabled
> 3721ms transaction disabled
>
> average 3731ms
>
> JDBM2, no TM :
> --------------
>
> 12339ms transaction disabled
> 4087ms transaction disabled
> 4081ms transaction disabled
> 4050ms transaction disabled
> 4015ms transaction disabled
> 4003ms transaction disabled
> 4003ms transaction disabled
> 3973ms transaction disabled
> 4003ms transaction disabled
> 3986ms transaction disabled
>
> average 4022ms (8% slower)
>
> old JDBM, with a transaction manager (TM) :
> -------------------------------------------
>
> Here, CI = commits, and Sync = flush on disk.
>
> 18130ms with CI, Sync [1,1]
> 14448ms with CI, Sync [1,2]
> 12934ms with CI, Sync [1,5]
> 12264ms with CI, Sync [1,10]
> 11845ms with CI, Sync [1,20]
> 11481ms with CI, Sync [1,50]
> 11499ms with CI, Sync [1,100]
> 11423ms with CI, Sync [1,200]
> 11487ms with CI, Sync [1,500]
> 11481ms with CI, Sync [1,1000]
> 11534ms with CI, Sync [1,2000]
> 11471ms with CI, Sync [1,5000]
> 11550ms with CI, Sync [1,10000]
>
> 11300ms with CI, Sync [2,2]
> 9923ms with CI, Sync [2,5]
> 9177ms with CI, Sync [2,10]
> 8672ms with CI, Sync [2,20]
> 8454ms with CI, Sync [2,50]
> 1922030ms with CI, Sync [2,100]
> 8530ms with CI, Sync [2,200]
> 8324ms with CI, Sync [2,500]
> 8363ms with CI, Sync [2,1000]
> 8381ms with CI, Sync [2,2000]
> 8417ms with CI, Sync [2,5000]
> 8361ms with CI, Sync [2,10000]
>
> 7772ms with CI, Sync [5,5]
> 7191ms with CI, Sync [5,10]
> 6737ms with CI, Sync [5,20]
> 6503ms with CI, Sync [5,50]
> 6398ms with CI, Sync [5,100]
> 6398ms with CI, Sync [5,200]
> 6448ms with CI, Sync [5,500]
> 6428ms with CI, Sync [5,1000]
> 6371ms with CI, Sync [5,2000]
> 6385ms with CI, Sync [5,5000]
> 6422ms with CI, Sync [5,10000]
>
> 6348ms with CI, Sync [10,10]
> 5844ms with CI, Sync [10,20]
> 5565ms with CI, Sync [10,50]
> 5473ms with CI, Sync [10,100]
> 5471ms with CI, Sync [10,200]
> 5453ms with CI, Sync [10,500]
> 5491ms with CI, Sync [10,1000]
> 5517ms with CI, Sync [10,2000]
> 5950ms with CI, Sync [10,5000]
> 5806ms with CI, Sync [10,10000]
>
> 5054ms with CI, Sync [20,20]
> 4769ms with CI, Sync [20,50]
> 4657ms with CI, Sync [20,100]
> 4663ms with CI, Sync [20,200]
> 4650ms with CI, Sync [20,500]
> 4622ms with CI, Sync [20,1000]
> 4664ms with CI, Sync [20,2000]
> 4634ms with CI, Sync [20,5000]
> 4662ms with CI, Sync [20,10000]
>
> 4243ms with CI, Sync [50,50]
> 4134ms with CI, Sync [50,100]
> 4123ms with CI, Sync [50,200]
> 4107ms with CI, Sync [50,500]
> 4162ms with CI, Sync [50,1000]
> 4115ms with CI, Sync [50,2000]
> 4105ms with CI, Sync [50,5000]
> 4143ms with CI, Sync [50,10000]
>
> 3982ms with CI, Sync [100,100]
> 3926ms with CI, Sync [100,200]
> 3913ms with CI, Sync [100,500]
> 3948ms with CI, Sync [100,1000]
> 3942ms with CI, Sync [100,2000]
> 3934ms with CI, Sync [100,5000]
> 3936ms with CI, Sync [100,10000]
>
> 3928ms with CI, Sync [200,200]
> 3909ms with CI, Sync [200,500]
> 4116ms with CI, Sync [200,1000]
> 4016ms with CI, Sync [200,2000]
> 3919ms with CI, Sync [200,5000]
> 3892ms with CI, Sync [200,10000]
>
> 3797ms with CI, Sync [500,500]
> 3798ms with CI, Sync [500,1000]
> 3814ms with CI, Sync [500,2000]
> 3790ms with CI, Sync [500,5000]
> 3818ms with CI, Sync [500,10000]
>
> 3725ms with CI, Sync [1000,1000]
> 3786ms with CI, Sync [1000,2000]
> 3736ms with CI, Sync [1000,5000]
> 3769ms with CI, Sync [1000,10000]
>
> 3682ms with CI, Sync [2000,2000]
> 3678ms with CI, Sync [2000,5000]
> 3691ms with CI, Sync [2000,10000]
>
> 3459ms with CI, Sync [5000,5000]
> 3493ms with CI, Sync [5000,10000]
> 3277ms with CI, Sync [10000,10000]
>
> As we can see, the more we differ the writings, the better the
> performances.
>
> So I ajusted the parameters on the server, and I currently do a commit
> every 2000 changes, and a flsuh every 4000 changes. It's hard coded atm,
> but I will make it configurable.
>
> The performances went up from 50 add per second to 185 add per second.
> Good, but nothing to get excited with, compared to the 600 add/s we had
> :/ With such numbers, it will take roughly 1h30 to inject 1M entries...
>
> What can we do to improve those performances then ?
>
>
> Atm, with JDBM, I see no bright future. There are ways to squeeze a bit
> of performance though, but not a lot : we can bypass the full chain, and
> inject the data directly into the btrees, but the gain will be marginal.
>
> So here are a few possibities :
>
> 1) Add raw injection of data feature in JDBM
>
> The idea is to order the data before injecting them, and apply an
> algoithm that build the pages, without having to pass through the tree
> reordering. If we can have N elements in each page, we order the data,
> and we store N elements in each page keeping the largest element of each
> page in a separate list. This is for the leaves. Then reproduce the same
> procssing on the gathered list, but for parent pages - and link to the
> leaves. etc, up to the root.
>
> This is the fastest way to store data in a btree.
>
> This requires a few operations :
> - order the data on disk : an O(N x log(N)) operation
> - modify JDBM to allow us to inject data in a page directly
>
> I evaluate this to two or three weeks of work. The gan will be quite
> big, the slower operation being the ordering of data
>
> Although we are stuck with JDBM lack of globa transaction system, which
> forces us to lock every operatio (including searches) while we add some
> entries.
>
> 2) Switch to JDBM 4
>
> We have to evaluate what JDBM 4 is briging to us. It's obviously a
> better base, but we don't know to what extent, and we don't know if :
> - we can have global corss-btrees transactions
> - we can inject raw data in the files without going through the btree
> operations
>
> Evaluating JDBM4 is probably a week of work
>
I have already started evaluating this today will update this thread with
my findings
>
> 3) Switch to Mavibot
>
> Mavibot is a labs I started last year, which implements a MVCC Btree in
> memory. It's working, t's fast, but it's in memory only atm (although
> the data are regularly flushed on disk).
>
> We need to improve it so that we add those features :
> - Make it backed with a physical layer that access data on disk, and
> avoid storing everything in memory
> - Add a raw load feature
> - Add a global transaction system, cross trees.
>
> The last feature is probably easier to implement, as we do have a
> version associated with each new modification : if we retin the version
> we started with, we can gather all the btree's revision, and validate
> them all in one shot, or rollback them all in one shot (a revision is
> visible only if it has been validated).
>
> One very interestig aspect of Mavibot is that you can update the btrees
> concurrently with searches : searches are done on older revisions, which
> don't interract with the pages being added.
>
> I think there is one to two more month of work on Mavibot to get it to
> the level we need.
>
> Proposal
> --------
>
> IMO, we should investigate JDBM4 asap. It might solve many of the issues
> we have, at a low price. Improving the existing JDBM is just a waste of
> our precious time.
>
> I the long term, I would favor Mavibot for a couple of reasons :
> - first, it's a MVCC base, so we can conduct concurrent searches and
> modifications (although we can't do many modifications at the same time).
> - second, we have a complete understanding of the code : we wrote it.
> It's easier to understand the impact of the modifications we hve done on
> it.
> - third, we can have a dedicated backend based on the current Mavibot
> code, where all the data are in memory (that would work with a few tens
> of thousands entries, and the performances will be blazing fast).
>
> I'd like to know what's your opinion.
>
> Thanks !
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
>
--
Kiran Ayyagari
http://keydap.com
Re: Backend improvements
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 2/17/13 2:53 AM, Howard Chu a écrit :
> Emmanuel Lécharny wrote:
>>
>> I the long term, I would favor Mavibot for a couple of reasons :
>> - first, it's a MVCC base, so we can conduct concurrent searches and
>> modifications (although we can't do many modifications at the same
>> time).
>> - second, we have a complete understanding of the code : we wrote it.
>> It's easier to understand the impact of the modifications we hve done
>> on it.
>> - third, we can have a dedicated backend based on the current Mavibot
>> code, where all the data are in memory (that would work with a few tens
>> of thousands entries, and the performances will be blazing fast).
>>
>> I'd like to know what's your opinion.
>
> Is it a requirement to stick to pure java? We recently had someone
> inquire about a java wrapper for our Lightning DB library. Developing
> that could get you a big boost without as much development effort,
> assuming JNI is practical for deployments.
The pb with JNI is that deploying an application becomes a PITA, and I'm
not talking about embedding the server into a web application :/
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Backend improvements
Posted by Howard Chu <hy...@symas.com>.
Emmanuel Lécharny wrote:
> 3) Switch to Mavibot
>
> Mavibot is a labs I started last year, which implements a MVCC Btree in
> memory. It's working, t's fast, but it's in memory only atm (although
> the data are regularly flushed on disk).
>
> We need to improve it so that we add those features :
> - Make it backed with a physical layer that access data on disk, and
> avoid storing everything in memory
> - Add a raw load feature
> - Add a global transaction system, cross trees.
>
> The last feature is probably easier to implement, as we do have a
> version associated with each new modification : if we retin the version
> we started with, we can gather all the btree's revision, and validate
> them all in one shot, or rollback them all in one shot (a revision is
> visible only if it has been validated).
>
> One very interestig aspect of Mavibot is that you can update the btrees
> concurrently with searches : searches are done on older revisions, which
> don't interract with the pages being added.
>
> I think there is one to two more month of work on Mavibot to get it to
> the level we need.
>
> Proposal
> --------
>
> IMO, we should investigate JDBM4 asap. It might solve many of the issues
> we have, at a low price. Improving the existing JDBM is just a waste of
> our precious time.
>
> I the long term, I would favor Mavibot for a couple of reasons :
> - first, it's a MVCC base, so we can conduct concurrent searches and
> modifications (although we can't do many modifications at the same time).
> - second, we have a complete understanding of the code : we wrote it.
> It's easier to understand the impact of the modifications we hve done on it.
> - third, we can have a dedicated backend based on the current Mavibot
> code, where all the data are in memory (that would work with a few tens
> of thousands entries, and the performances will be blazing fast).
>
> I'd like to know what's your opinion.
Is it a requirement to stick to pure java? We recently had someone inquire
about a java wrapper for our Lightning DB library. Developing that could get
you a big boost without as much development effort, assuming JNI is practical
for deployments.
--
-- 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: Backend improvements
Posted by Pierre-Arnaud Marcelot <pa...@marcelot.net>.
Hi Emmanuel,
On 16 févr. 2013, at 11:19, Emmanuel Lécharny <el...@gmail.com> wrote:
> Proposal
> --------
>
> IMO, we should investigate JDBM4 asap. It might solve many of the issues
> we have, at a low price. Improving the existing JDBM is just a waste of
> our precious time.
+1
> I the long term, I would favor Mavibot for a couple of reasons :
> - first, it's a MVCC base, so we can conduct concurrent searches and
> modifications (although we can't do many modifications at the same time).
> - second, we have a complete understanding of the code : we wrote it.
> It's easier to understand the impact of the modifications we hve done on it.
> - third, we can have a dedicated backend based on the current Mavibot
> code, where all the data are in memory (that would work with a few tens
> of thousands entries, and the performances will be blazing fast).
+1.
Although, Mavibot may be a little bit unstable at first since it's a really new project with not a lot of people using it at the moment.
But in the long run, it looks like a really good candidate for what we need to do.
If there's enough RAM available I like the idea of the in-memory partition. :)
Regards,
Pierre-Arnaud