You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by "Stefan Seelmann (JIRA)" <ji...@apache.org> on 2011/08/16 22:28:27 UTC
[jira] [Created] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Unexpected behaviour in JdbmIndex
---------------------------------
Key: DIRSERVER-1642
URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
Project: Directory ApacheDS
Issue Type: Bug
Reporter: Stefan Seelmann
During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
- in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
- an entry is deleted
- when the open cursors are advanced wrong/unexpected entries are returned
I was able to create a small test that shows the problem:
- the index contains six tuples:
(a,1)
(b,2)
(c,3)
(d,4)
(e,5)
(f,6)
- a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
- now tuple (c,3) is deleted
- when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Re: [jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Alex Karasulu <ak...@apache.org>.
Thanks Selcuk for your efforts. This a great summary and update of what
you've done. More inline ...
On Mon, Aug 29, 2011 at 12:17 PM, Selcuk AYA <ay...@gmail.com> wrote:
> Resending as previous send didnt seem to make it...
>
> Hi I just attached my latest changes for the jdbm branch and wanted to
> give a status update and some technical details:
>
> 1) Summary
> *We now have a jdbm tree which treats find, insert, remove and browse
> as actions that execute in isolation. In particular, read actions will
> not be affected by ongoing structural changes to the tree and will
> only see data changes that completed before they started.
>
> *We allow one writer and multiple readers to execute concurrently.
> Synchronized operations are mostly removed.
>
> * Exisiting tests except the StoredProceduteIT and the unit tests I
> added for the versioned tree pass( I did mvn clean install
> -Dintegration). I think the problem with StoredProceduteIT is an
> existing one. There is a code piece where I serialize and deserialize
> tuple values stored in JDBM btree in order to do a deep copy. With
> StoredProcedureIT hello world stored procedure deserialization throws
> a UTFDataFormatException. On a clean brach, I added similar code to
> deserialize B+ tree page values right after they are serialized, and I
> hit the same issue. So I think this is some existing issue with stored
> procedure serialization/deserialization.
>
>
Yes we need to get to the bottom of this yes. It must be something wrong
with the way the SP test works. If need be let's create a JIRA issue on the
Apache Jira for this and come back to it later.
> 2) Changes above JDBM level
> * I added changes to call the newly added browser->close() interface
> when the cursors are closed or a cursor is repositioned.
> * I hit some existing issues where cursors are not closed. In
> particular, I had to change SubentryInterceptor.java.java to close the
> cursor after search operations and change the JDBM container cursor to
> close the contained cursor when it is closed. If required, I can
> provide these changes as separate fixes
>
>
Please do when you have a chance. It would be nice to get this out in the M3
release to avoid consistency issues especially when long running operations
are concerned during replication updates.
> 3) Technical details at JDBM level:
>
> *The core functionality is at LRUCache.java. This implements a
> concurrent, versioned cache. There a power of two hash buckets and a
> lock for each of the 8 buckets(lock striping). Number of hash buckets
> x where x is closest power of two such that x < max number of cache
> entries.
>
> *Cache replacement policy is LRU. There are 16 lru lists and each
> cache entry is assigned to one of the lru lists. Each lru is protected
> by a separate lock. LRU replacement is supposed to be fast. Threads
> choose an lru based on an lru randomizer. Since replacement is
> supposed to be fast and each thread randomly chooses an lru to replace
> from, lru operations should not be a bottleneck.
>
> * Each cache entry has a [startVersion, endVersion) where it is valid.
> At any time, a hash bucket chain looks like this:
> (key1, startVersion11, endVersion11) <-> (key2, startversion21,
> endVersion21) <->
> |
> |
> (key1, startVersion12, endVersion12) (key2, startversion22,
> endVersion22)
> |
> |
> ....
> .......
>
> that is, there is a primary chain where entries for different keys are
> chained and then there is subchain where different versions for a
> given key are held. So, when readers search for a (key, version), they
> first walk the primary chain and then walk the subchain to find their
> entry.
>
> *As writes create previous versions of entries, they use part of the
> cache to store them. The rule is that such an entry cannot be replaced
> as long as there might be a reader which might read it. We keep track
> of the minimum read action version to make such entries replaceable .
>
> *As writes create previous versions of entries, they use part of the
> cache to store them. If there are long browse operations and quite a
> bit of updates going on at the same time, we might run into a case
> where most of the cache entries are used to store previous versions.
> We might even have a case where all entries store previous versions
> and they cannot be replaced(because of the rule above). In this case,
> writers wait for a freeable cache entry. When a reader cannot find a
> replaceable entry, it does read from disk while holding the bucket
> latch(and thus holding any possible writer on the same location). and
> return the entry to the user without populating the cache and thus
> without looking for a replaceable cache entry. Since readers always
> make progress, min read version will eventually advance and writers
> will progress too. Normally, when readers or writers do IO, they
> release the hash latch.
>
> * There some helper classes for the LRUCache to work. Maybe the most
> interesting ones are ActionVersioning which uses AtomicInteger and
> AtomicReference and is optimized for the read mostly case. Also we
> have ExplicitList where remove operations are O(1) given an
> element(this is in contrast to O(n) remove given a pointer to an
> element on Java's lists). Such fast removes are needed for lru
> algorithm.
>
> *When (key,value) pairs are added to the Btree or when they are
> retrieved, Btree does a deep copy of the value(through serialization,
> deserialization). This is needed so that Btree can store previous
> versions of values. I assumed key stored in Btrees are not changed. If
> the do, even the CacheRecordManager currently in use wouldnt work.
>
> 4) Possible improvements:
> *if most of the cache entries are used to store previous versions,
> cache effectiveness will decrease.A solultion is to start spilling
> previous versions to disk when such a thing happens. The subchain we
> talked about above would have to be spilled to disk. However, this is
> only a performance problem and is a corner case one as well if it is
> true that ldap is read mostly.
>
>
I think we should not jump the gun on this as you suggest. Let's see how
some performance metrics turn out first and take a more empirical approach.
We still need to turn on transactions and make sure the upper layers us what
you've done properly to avoid corruption.
> * Currently when a write action is executing, if there is an IO
> exception action is aborted and I do not advance the read version and
> thus readers do not see the affects of the aborted action. However, it
> seems that upper layers do not do enough cleanup in this case,
We need a review specifically to make sure the upper layers properly handle
these cases. Again let's leverage JIRA and make sure we get on this. It's
going to be critical to get out a solid ADS 2.0.0-M3 with replication.
> they
> continue using the jdbm stores and this will lead to inconsistency. A
> good thing would be to rollback all the dirty changes . Also, jdbm
> txns are not enable currently so a crash in the middle of syncing
> might leave the store inconsistent.
>
> 5) TODO:
> *add some more test cases for the verisioned btree to test corner cases.
> *I am not very willing to implement disk spilling since this is only a
> performance improvement needed in corner cases if stores are mostly
> read only. But if you guys think this is really necessary, I might
> look into this as well.
>
Thanks again Selcuk this is great work.
--
Best Regards,
-- Alex
Re: [jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Selcuk AYA <ay...@gmail.com>.
Resending as previous send didnt seem to make it...
Hi I just attached my latest changes for the jdbm branch and wanted to
give a status update and some technical details:
1) Summary
*We now have a jdbm tree which treats find, insert, remove and browse
as actions that execute in isolation. In particular, read actions will
not be affected by ongoing structural changes to the tree and will
only see data changes that completed before they started.
*We allow one writer and multiple readers to execute concurrently.
Synchronized operations are mostly removed.
* Exisiting tests except the StoredProceduteIT and the unit tests I
added for the versioned tree pass( I did mvn clean install
-Dintegration). I think the problem with StoredProceduteIT is an
existing one. There is a code piece where I serialize and deserialize
tuple values stored in JDBM btree in order to do a deep copy. With
StoredProcedureIT hello world stored procedure deserialization throws
a UTFDataFormatException. On a clean brach, I added similar code to
deserialize B+ tree page values right after they are serialized, and I
hit the same issue. So I think this is some existing issue with stored
procedure serialization/deserialization.
2) Changes above JDBM level
* I added changes to call the newly added browser->close() interface
when the cursors are closed or a cursor is repositioned.
* I hit some existing issues where cursors are not closed. In
particular, I had to change SubentryInterceptor.java.java to close the
cursor after search operations and change the JDBM container cursor to
close the contained cursor when it is closed. If required, I can
provide these changes as separate fixes
3) Technical details at JDBM level:
*The core functionality is at LRUCache.java. This implements a
concurrent, versioned cache. There a power of two hash buckets and a
lock for each of the 8 buckets(lock striping). Number of hash buckets
x where x is closest power of two such that x < max number of cache
entries.
*Cache replacement policy is LRU. There are 16 lru lists and each
cache entry is assigned to one of the lru lists. Each lru is protected
by a separate lock. LRU replacement is supposed to be fast. Threads
choose an lru based on an lru randomizer. Since replacement is
supposed to be fast and each thread randomly chooses an lru to replace
from, lru operations should not be a bottleneck.
* Each cache entry has a [startVersion, endVersion) where it is valid.
At any time, a hash bucket chain looks like this:
(key1, startVersion11, endVersion11) <-> (key2, startversion21,
endVersion21) <->
| |
(key1, startVersion12, endVersion12) (key2, startversion22,
endVersion22)
| |
.... .......
that is, there is a primary chain where entries for different keys are
chained and then there is subchain where different versions for a
given key are held. So, when readers search for a (key, version), they
first walk the primary chain and then walk the subchain to find their
entry.
*As writes create previous versions of entries, they use part of the
cache to store them. The rule is that such an entry cannot be replaced
as long as there might be a reader which might read it. We keep track
of the minimum read action version to make such entries replaceable .
*As writes create previous versions of entries, they use part of the
cache to store them. If there are long browse operations and quite a
bit of updates going on at the same time, we might run into a case
where most of the cache entries are used to store previous versions.
We might even have a case where all entries store previous versions
and they cannot be replaced(because of the rule above). In this case,
writers wait for a freeable cache entry. When a reader cannot find a
replaceable entry, it does read from disk while holding the bucket
latch(and thus holding any possible writer on the same location). and
return the entry to the user without populating the cache and thus
without looking for a replaceable cache entry. Since readers always
make progress, min read version will eventually advance and writers
will progress too. Normally, when readers or writers do IO, they
release the hash latch.
* There some helper classes for the LRUCache to work. Maybe the most
interesting ones are ActionVersioning which uses AtomicInteger and
AtomicReference and is optimized for the read mostly case. Also we
have ExplicitList where remove operations are O(1) given an
element(this is in contrast to O(n) remove given a pointer to an
element on Java's lists). Such fast removes are needed for lru
algorithm.
*When (key,value) pairs are added to the Btree or when they are
retrieved, Btree does a deep copy of the value(through serialization,
deserialization). This is needed so that Btree can store previous
versions of values. I assumed key stored in Btrees are not changed. If
the do, even the CacheRecordManager currently in use wouldnt work.
4) Possible improvements:
*if most of the cache entries are used to store previous versions,
cache effectiveness will decrease.A solultion is to start spilling
previous versions to disk when such a thing happens. The subchain we
talked about above would have to be spilled to disk. However, this is
only a performance problem and is a corner case one as well if it is
true that ldap is read mostly.
* Currently when a write action is executing, if there is an IO
exception action is aborted and I do not advance the read version and
thus readers do not see the affects of the aborted action. However, it
seems that upper layers do not do enough cleanup in this case, they
continue using the jdbm stores and this will lead to inconsistency. A
good thing would be to rollback all the dirty changes . Also, jdbm
txns are not enable currently so a crash in the middle of syncing
might leave the store inconsistent.
5) TODO:
*add some more test cases for the verisioned btree to test corner cases.
*I am not very willing to implement disk spilling since this is only a
performance improvement needed in corner cases if stores are mostly
read only. But if you guys think this is really necessary, I might
look into this as well.
regards,
Selcuk Aya
On Mon, Aug 29, 2011 at 10:23 AM, Selcuk Aya (JIRA) <ji...@apache.org> wrote:
>
> [ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
>
> Selcuk Aya updated DIRSERVER-1642:
> ----------------------------------
>
> Attachment: jdbm5.diff
>
> I changed jdbm-partition to use the versioned Btree. Test cases except StoredProcedureIT are passing. I think the issue with StoredProcedureIT is an exisiting one with serialization of the store procedure and I added an ignore for this test case.
>
>> Unexpected behaviour in JdbmIndex
>> ---------------------------------
>>
>> Key: DIRSERVER-1642
>> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
>> Project: Directory ApacheDS
>> Issue Type: Bug
>> Reporter: Stefan Seelmann
>> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff, jdbm3.diff, jdbm4.diff, jdbm5.diff
>>
>>
>> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
>> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
>> - an entry is deleted
>> - when the open cursors are advanced wrong/unexpected entries are returned
>> I was able to create a small test that shows the problem:
>> - the index contains six tuples:
>> (a,1)
>> (b,2)
>> (c,3)
>> (d,4)
>> (e,5)
>> (f,6)
>> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
>> - now tuple (c,3) is deleted
>> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
>> Note that this doesn't happen with AvlIndex.
>
> --
> This message is automatically generated by JIRA.
> For more information on JIRA, see: http://www.atlassian.com/software/jira
>
>
>
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Selcuk AYA <ay...@gmail.com>.
On Fri, Aug 19, 2011 at 12:36 PM, Emmanuel Lecharny <el...@gmail.com> wrote:
> On 8/19/11 10:30 AM, Selcuk AYA wrote:
>>
>> On Fri, Aug 19, 2011 at 10:14 AM, Emmanuel Lecharny<el...@gmail.com>
>> wrote:
>>>
>>> On 8/19/11 8:51 AM, Stefan Seelmann wrote:
>>>>
>>>> On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA<ay...@gmail.com>
>>>> wrote:
>>>>>
>>>>> Hi,
>>>>> Today we had some discussion with Alex, Emmanuel and others on how we
>>>>> can improve jdbm consistency semantics. I had spent sometime looking
>>>>> into this issue and thought it could be useful to put a summary of my
>>>>> findings here.
>>>>>
>>>>> Currently, jdbm has issues with both concurrency and consistency:
>>>>> 1) jdbm table lookups, insert and remove interfaces are synchronized
>>>>> methods. So even if all the directory server does is to lookups on
>>>>> tables, all lookups will be serialized. Moreover, the record manager
>>>>> operations are all synchronized methods too. This means, for example,
>>>>> while sync of dirty pages to disk goes on, no lookup operation can go
>>>>> ahead.
>>>>>
>>>>> 2) jdbm browser interface does not provide any consistency guarantees.
>>>>> If there are underlying changes to the store while the browser is
>>>>> open, then it might return inconsistent results. I think the situation
>>>>> is even worse if the underlying record manager is CacheRecordManager
>>>>> as the same page could be modified and read by a browser concurrently.
>>>>>
>>>>> I have been working on a scheme which introduces what can be defined
>>>>> as action consistency into the jdbm store.
>>>>> 1) Actions are lookup, insert, remove and browse. Each action is
>>>>> assigned a unique version. Actions are ReadWrite or ReadOnly.
>>>>> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
>>>>> concurrently.So synchronized methods will be removed.
>>>>> 3)We introduce a new record manager which caches jdbm B+ pages. Each
>>>>> page in the cache has a [startVersion, endVersion). When an action
>>>>> with version V1 wants to read a page, its read can be satisfied
>>>>> satisfied from that page's version with V1>= startVersion&& V1<
>>>>> endVersion.
>>>>> 4) Pages' previous versions are kept in memory. A page can be purged
>>>>> when the minimum version among all active actions is>= endVersion.
>>>>>
>>>>> So say we have three pages in a chain (A0->B0->C0) and each of them
>>>>> has version range [0, infinity). An write action starts and gets the
>>>>> version number 1. It updates B0 and C0 to B1 and C1 in any order.
>>>>> After these two updates, B0 and C0 will have version range [0,1) and
>>>>> and B1 and C1 will have version range [1,infinity). Before the write
>>>>> action completes, a read action comes, gets the current read version
>>>>> which is 0 and reads the chain. Since B0 and C0 will be the versions
>>>>> that can satisfy this read, the read only action will read the chain
>>>>> A0->B0->C0. When write action completes, it posts version 1 as the new
>>>>> read version. First read action completes, a second one starts with
>>>>> version 1 and that one will read A0->B1->C1. Since the minimum read
>>>>> version is now 1, B0 and C0 can be zapped.
>>>>
>>>> Here I have a question: How can we detect that the read is finished?
>>>> In the current JDBM implementation the "browse" action can take
>>>> forever, there is no way to tell JDBM that browse is finished (i.e. a
>>>> close() method).
>>
>> that is true. We will need to add a close() to the browse interface
>> and that should tell jdbm that the read finished. Since browse is
>> embedded under cursor and cursor is supposed to be closed at some
>> point ( ? ), this is reasonable I think.
>
> The cursor will be closed when we have read all the entries.
>>>
>>> First, browse will last at some point. The most we can do is to read
>>> *all*
>>> the entries from the master table using an index, but once it's done, the
>>> browse will stop. I wondered yesterday if a persistent search could
>>> change
>>> anything but no : the way it's handled is very different, we just
>>> register
>>> some listeners in the EventInterceptor, and every modification will
>>> trigger
>>> one listener. This is not a browse by all mean.
>>>
>>> Now, I guess we will have to store the used revision somewhere (like in
>>> the
>>> searchOperationContext), and when we don't have anymore element to send
>>> back
>>> to the user, then we can 'close' the browse, releasing the revision.
>>>
>> I assumed that each action(find, insert, remove,browse) is executed by
>> one thread so I thought we can store an actionContext at a thread
>> local variable as a thread enters an action. Version number can be
>> stored in this context. This way, except the close() call we add to
>> the Browse interface, we can keep most of the changes local to jdbm.
>
> Hmmm. The way it works, we execute a search on a single thread, but we also
> associate an operationContext instance which is carried all along the
> filters. Except that this instance is not passed to the JDBM layer. So, yes,
> it's probably a better idea to use a ThreadLocal variable here. Although we
> have to be sure that we don't reuse what we store in this variable.
>
>> With this, an insert implementation within B+tree looks like this for
>> example:
>> beginAction() // intiialize action context, get a version number
>> do the insert
>> endAction()
>>
>> for Browse, we might have:
>> Browse()
>> {
>> beginAction()
>> }
>>
>> close()
>> {
>> endAction()
>> }
>
> Sounds good.
>
> Do you want us to create a branch to experiment around these ideas ?
>
I already cloned the code and am experimenting on it. Will keep you
posted on how it goes.
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
>
regards,
Selcuk AYA
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 8/19/11 10:30 AM, Selcuk AYA wrote:
> On Fri, Aug 19, 2011 at 10:14 AM, Emmanuel Lecharny<el...@gmail.com> wrote:
>> On 8/19/11 8:51 AM, Stefan Seelmann wrote:
>>> On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA<ay...@gmail.com> wrote:
>>>> Hi,
>>>> Today we had some discussion with Alex, Emmanuel and others on how we
>>>> can improve jdbm consistency semantics. I had spent sometime looking
>>>> into this issue and thought it could be useful to put a summary of my
>>>> findings here.
>>>>
>>>> Currently, jdbm has issues with both concurrency and consistency:
>>>> 1) jdbm table lookups, insert and remove interfaces are synchronized
>>>> methods. So even if all the directory server does is to lookups on
>>>> tables, all lookups will be serialized. Moreover, the record manager
>>>> operations are all synchronized methods too. This means, for example,
>>>> while sync of dirty pages to disk goes on, no lookup operation can go
>>>> ahead.
>>>>
>>>> 2) jdbm browser interface does not provide any consistency guarantees.
>>>> If there are underlying changes to the store while the browser is
>>>> open, then it might return inconsistent results. I think the situation
>>>> is even worse if the underlying record manager is CacheRecordManager
>>>> as the same page could be modified and read by a browser concurrently.
>>>>
>>>> I have been working on a scheme which introduces what can be defined
>>>> as action consistency into the jdbm store.
>>>> 1) Actions are lookup, insert, remove and browse. Each action is
>>>> assigned a unique version. Actions are ReadWrite or ReadOnly.
>>>> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
>>>> concurrently.So synchronized methods will be removed.
>>>> 3)We introduce a new record manager which caches jdbm B+ pages. Each
>>>> page in the cache has a [startVersion, endVersion). When an action
>>>> with version V1 wants to read a page, its read can be satisfied
>>>> satisfied from that page's version with V1>= startVersion&& V1<
>>>> endVersion.
>>>> 4) Pages' previous versions are kept in memory. A page can be purged
>>>> when the minimum version among all active actions is>= endVersion.
>>>>
>>>> So say we have three pages in a chain (A0->B0->C0) and each of them
>>>> has version range [0, infinity). An write action starts and gets the
>>>> version number 1. It updates B0 and C0 to B1 and C1 in any order.
>>>> After these two updates, B0 and C0 will have version range [0,1) and
>>>> and B1 and C1 will have version range [1,infinity). Before the write
>>>> action completes, a read action comes, gets the current read version
>>>> which is 0 and reads the chain. Since B0 and C0 will be the versions
>>>> that can satisfy this read, the read only action will read the chain
>>>> A0->B0->C0. When write action completes, it posts version 1 as the new
>>>> read version. First read action completes, a second one starts with
>>>> version 1 and that one will read A0->B1->C1. Since the minimum read
>>>> version is now 1, B0 and C0 can be zapped.
>>> Here I have a question: How can we detect that the read is finished?
>>> In the current JDBM implementation the "browse" action can take
>>> forever, there is no way to tell JDBM that browse is finished (i.e. a
>>> close() method).
> that is true. We will need to add a close() to the browse interface
> and that should tell jdbm that the read finished. Since browse is
> embedded under cursor and cursor is supposed to be closed at some
> point ( ? ), this is reasonable I think.
The cursor will be closed when we have read all the entries.
>> First, browse will last at some point. The most we can do is to read *all*
>> the entries from the master table using an index, but once it's done, the
>> browse will stop. I wondered yesterday if a persistent search could change
>> anything but no : the way it's handled is very different, we just register
>> some listeners in the EventInterceptor, and every modification will trigger
>> one listener. This is not a browse by all mean.
>>
>> Now, I guess we will have to store the used revision somewhere (like in the
>> searchOperationContext), and when we don't have anymore element to send back
>> to the user, then we can 'close' the browse, releasing the revision.
>>
> I assumed that each action(find, insert, remove,browse) is executed by
> one thread so I thought we can store an actionContext at a thread
> local variable as a thread enters an action. Version number can be
> stored in this context. This way, except the close() call we add to
> the Browse interface, we can keep most of the changes local to jdbm.
Hmmm. The way it works, we execute a search on a single thread, but we
also associate an operationContext instance which is carried all along
the filters. Except that this instance is not passed to the JDBM layer.
So, yes, it's probably a better idea to use a ThreadLocal variable
here. Although we have to be sure that we don't reuse what we store in
this variable.
> With this, an insert implementation within B+tree looks like this for
> example:
> beginAction() // intiialize action context, get a version number
> do the insert
> endAction()
>
> for Browse, we might have:
> Browse()
> {
> beginAction()
> }
>
> close()
> {
> endAction()
> }
Sounds good.
Do you want us to create a branch to experiment around these ideas ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Selcuk AYA <ay...@gmail.com>.
On Fri, Aug 19, 2011 at 10:14 AM, Emmanuel Lecharny <el...@gmail.com> wrote:
> On 8/19/11 8:51 AM, Stefan Seelmann wrote:
>>
>> On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA<ay...@gmail.com> wrote:
>>>
>>> Hi,
>>> Today we had some discussion with Alex, Emmanuel and others on how we
>>> can improve jdbm consistency semantics. I had spent sometime looking
>>> into this issue and thought it could be useful to put a summary of my
>>> findings here.
>>>
>>> Currently, jdbm has issues with both concurrency and consistency:
>>> 1) jdbm table lookups, insert and remove interfaces are synchronized
>>> methods. So even if all the directory server does is to lookups on
>>> tables, all lookups will be serialized. Moreover, the record manager
>>> operations are all synchronized methods too. This means, for example,
>>> while sync of dirty pages to disk goes on, no lookup operation can go
>>> ahead.
>>>
>>> 2) jdbm browser interface does not provide any consistency guarantees.
>>> If there are underlying changes to the store while the browser is
>>> open, then it might return inconsistent results. I think the situation
>>> is even worse if the underlying record manager is CacheRecordManager
>>> as the same page could be modified and read by a browser concurrently.
>>>
>>> I have been working on a scheme which introduces what can be defined
>>> as action consistency into the jdbm store.
>>> 1) Actions are lookup, insert, remove and browse. Each action is
>>> assigned a unique version. Actions are ReadWrite or ReadOnly.
>>> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
>>> concurrently.So synchronized methods will be removed.
>>> 3)We introduce a new record manager which caches jdbm B+ pages. Each
>>> page in the cache has a [startVersion, endVersion). When an action
>>> with version V1 wants to read a page, its read can be satisfied
>>> satisfied from that page's version with V1>= startVersion&& V1<
>>> endVersion.
>>> 4) Pages' previous versions are kept in memory. A page can be purged
>>> when the minimum version among all active actions is>= endVersion.
>>>
>>> So say we have three pages in a chain (A0->B0->C0) and each of them
>>> has version range [0, infinity). An write action starts and gets the
>>> version number 1. It updates B0 and C0 to B1 and C1 in any order.
>>> After these two updates, B0 and C0 will have version range [0,1) and
>>> and B1 and C1 will have version range [1,infinity). Before the write
>>> action completes, a read action comes, gets the current read version
>>> which is 0 and reads the chain. Since B0 and C0 will be the versions
>>> that can satisfy this read, the read only action will read the chain
>>> A0->B0->C0. When write action completes, it posts version 1 as the new
>>> read version. First read action completes, a second one starts with
>>> version 1 and that one will read A0->B1->C1. Since the minimum read
>>> version is now 1, B0 and C0 can be zapped.
>>
>> Here I have a question: How can we detect that the read is finished?
>> In the current JDBM implementation the "browse" action can take
>> forever, there is no way to tell JDBM that browse is finished (i.e. a
>> close() method).
>
that is true. We will need to add a close() to the browse interface
and that should tell jdbm that the read finished. Since browse is
embedded under cursor and cursor is supposed to be closed at some
point ( ? ), this is reasonable I think.
> First, browse will last at some point. The most we can do is to read *all*
> the entries from the master table using an index, but once it's done, the
> browse will stop. I wondered yesterday if a persistent search could change
> anything but no : the way it's handled is very different, we just register
> some listeners in the EventInterceptor, and every modification will trigger
> one listener. This is not a browse by all mean.
>
> Now, I guess we will have to store the used revision somewhere (like in the
> searchOperationContext), and when we don't have anymore element to send back
> to the user, then we can 'close' the browse, releasing the revision.
>
I assumed that each action(find, insert, remove,browse) is executed by
one thread so I thought we can store an actionContext at a thread
local variable as a thread enters an action. Version number can be
stored in this context. This way, except the close() call we add to
the Browse interface, we can keep most of the changes local to jdbm.
With this, an insert implementation within B+tree looks like this for
example:
beginAction() // intiialize action context, get a version number
do the insert
endAction()
for Browse, we might have:
Browse()
{
beginAction()
}
close()
{
endAction()
}
> At least, this is how I foresee the solution...
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
>
regards,
Selcuk AYA
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 8/19/11 8:51 AM, Stefan Seelmann wrote:
> On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA<ay...@gmail.com> wrote:
>> Hi,
>> Today we had some discussion with Alex, Emmanuel and others on how we
>> can improve jdbm consistency semantics. I had spent sometime looking
>> into this issue and thought it could be useful to put a summary of my
>> findings here.
>>
>> Currently, jdbm has issues with both concurrency and consistency:
>> 1) jdbm table lookups, insert and remove interfaces are synchronized
>> methods. So even if all the directory server does is to lookups on
>> tables, all lookups will be serialized. Moreover, the record manager
>> operations are all synchronized methods too. This means, for example,
>> while sync of dirty pages to disk goes on, no lookup operation can go
>> ahead.
>>
>> 2) jdbm browser interface does not provide any consistency guarantees.
>> If there are underlying changes to the store while the browser is
>> open, then it might return inconsistent results. I think the situation
>> is even worse if the underlying record manager is CacheRecordManager
>> as the same page could be modified and read by a browser concurrently.
>>
>> I have been working on a scheme which introduces what can be defined
>> as action consistency into the jdbm store.
>> 1) Actions are lookup, insert, remove and browse. Each action is
>> assigned a unique version. Actions are ReadWrite or ReadOnly.
>> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
>> concurrently.So synchronized methods will be removed.
>> 3)We introduce a new record manager which caches jdbm B+ pages. Each
>> page in the cache has a [startVersion, endVersion). When an action
>> with version V1 wants to read a page, its read can be satisfied
>> satisfied from that page's version with V1>= startVersion&& V1<
>> endVersion.
>> 4) Pages' previous versions are kept in memory. A page can be purged
>> when the minimum version among all active actions is>= endVersion.
>>
>> So say we have three pages in a chain (A0->B0->C0) and each of them
>> has version range [0, infinity). An write action starts and gets the
>> version number 1. It updates B0 and C0 to B1 and C1 in any order.
>> After these two updates, B0 and C0 will have version range [0,1) and
>> and B1 and C1 will have version range [1,infinity). Before the write
>> action completes, a read action comes, gets the current read version
>> which is 0 and reads the chain. Since B0 and C0 will be the versions
>> that can satisfy this read, the read only action will read the chain
>> A0->B0->C0. When write action completes, it posts version 1 as the new
>> read version. First read action completes, a second one starts with
>> version 1 and that one will read A0->B1->C1. Since the minimum read
>> version is now 1, B0 and C0 can be zapped.
> Here I have a question: How can we detect that the read is finished?
> In the current JDBM implementation the "browse" action can take
> forever, there is no way to tell JDBM that browse is finished (i.e. a
> close() method).
First, browse will last at some point. The most we can do is to read
*all* the entries from the master table using an index, but once it's
done, the browse will stop. I wondered yesterday if a persistent search
could change anything but no : the way it's handled is very different,
we just register some listeners in the EventInterceptor, and every
modification will trigger one listener. This is not a browse by all mean.
Now, I guess we will have to store the used revision somewhere (like in
the searchOperationContext), and when we don't have anymore element to
send back to the user, then we can 'close' the browse, releasing the
revision.
At least, this is how I foresee the solution...
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Stefan Seelmann <se...@apache.org>.
On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA <ay...@gmail.com> wrote:
> Hi,
> Today we had some discussion with Alex, Emmanuel and others on how we
> can improve jdbm consistency semantics. I had spent sometime looking
> into this issue and thought it could be useful to put a summary of my
> findings here.
>
> Currently, jdbm has issues with both concurrency and consistency:
> 1) jdbm table lookups, insert and remove interfaces are synchronized
> methods. So even if all the directory server does is to lookups on
> tables, all lookups will be serialized. Moreover, the record manager
> operations are all synchronized methods too. This means, for example,
> while sync of dirty pages to disk goes on, no lookup operation can go
> ahead.
>
> 2) jdbm browser interface does not provide any consistency guarantees.
> If there are underlying changes to the store while the browser is
> open, then it might return inconsistent results. I think the situation
> is even worse if the underlying record manager is CacheRecordManager
> as the same page could be modified and read by a browser concurrently.
>
> I have been working on a scheme which introduces what can be defined
> as action consistency into the jdbm store.
> 1) Actions are lookup, insert, remove and browse. Each action is
> assigned a unique version. Actions are ReadWrite or ReadOnly.
> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
> concurrently.So synchronized methods will be removed.
> 3)We introduce a new record manager which caches jdbm B+ pages. Each
> page in the cache has a [startVersion, endVersion). When an action
> with version V1 wants to read a page, its read can be satisfied
> satisfied from that page's version with V1 >= startVersion && V1 <
> endVersion.
> 4) Pages' previous versions are kept in memory. A page can be purged
> when the minimum version among all active actions is >= endVersion.
>
> So say we have three pages in a chain (A0->B0->C0) and each of them
> has version range [0, infinity). An write action starts and gets the
> version number 1. It updates B0 and C0 to B1 and C1 in any order.
> After these two updates, B0 and C0 will have version range [0,1) and
> and B1 and C1 will have version range [1,infinity). Before the write
> action completes, a read action comes, gets the current read version
> which is 0 and reads the chain. Since B0 and C0 will be the versions
> that can satisfy this read, the read only action will read the chain
> A0->B0->C0. When write action completes, it posts version 1 as the new
> read version. First read action completes, a second one starts with
> version 1 and that one will read A0->B1->C1. Since the minimum read
> version is now 1, B0 and C0 can be zapped.
Here I have a question: How can we detect that the read is finished?
In the current JDBM implementation the "browse" action can take
forever, there is no way to tell JDBM that browse is finished (i.e. a
close() method).
> Concerns:
> 1)Previous versions of B+ tree pages could consume too much memory. As
> long as actions are kept small, this is not a problem. Only the
> browsing action does not follow this rule. There are a couple of
> options to deal with it. We can maybe spill previous versions to disk
> after some memory limit. Or we can think about chopping down browsing
> action into smaller read actions. Another way to deal with this
> problem would be to keep the previous versions of pages on disk rather
> than in memory. On disk, versions for a B+ page would form a
> chain.This is a radically different way of introducing action
> consistency but I thought this unneccesarily complicates free space
> management while all we need to do with old versions of pages after a
> restart is to toss them away.
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Emmanuel Lecharny <el...@gmail.com>.
On 8/18/11 10:41 PM, Selcuk AYA wrote:
> Hi,
> Today we had some discussion with Alex, Emmanuel and others on how we
> can improve jdbm consistency semantics. I had spent sometime looking
> into this issue and thought it could be useful to put a summary of my
> findings here.
>
> Currently, jdbm has issues with both concurrency and consistency:
> 1) jdbm table lookups, insert and remove interfaces are synchronized
> methods. So even if all the directory server does is to lookups on
> tables, all lookups will be serialized. Moreover, the record manager
> operations are all synchronized methods too. This means, for example,
> while sync of dirty pages to disk goes on, no lookup operation can go
> ahead.
Absolutely. Those synchronized were added a while back to try to
guaranty some kind of consistency... This is a ugly hack, and a
contention point for sure.
>
> 2) jdbm browser interface does not provide any consistency guarantees.
> If there are underlying changes to the store while the browser is
> open, then it might return inconsistent results. I think the situation
> is even worse if the underlying record manager is CacheRecordManager
> as the same page could be modified and read by a browser concurrently.
We already experience such inconsistency in the replication tests. Not
often, but still.
The reason we haven't noticed them up to now is that we have tests that
are run in one single thread, and for the concurrent tests we have done,
we never mixed searches and modifications together.
>
> I have been working on a scheme which introduces what can be defined
> as action consistency into the jdbm store.
> 1) Actions are lookup, insert, remove and browse. Each action is
> assigned a unique version. Actions are ReadWrite or ReadOnly.
> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
> concurrently.So synchronized methods will be removed.
Good.
> 3)We introduce a new record manager which caches jdbm B+ pages. Each
> page in the cache has a [startVersion, endVersion). When an action
> with version V1 wants to read a page, its read can be satisfied
> satisfied from that page's version with V1>= startVersion&& V1<
> endVersion.
> 4) Pages' previous versions are kept in memory. A page can be purged
> when the minimum version among all active actions is>= endVersion.
>
> So say we have three pages in a chain (A0->B0->C0) and each of them
> has version range [0, infinity). An write action starts and gets the
> version number 1. It updates B0 and C0 to B1 and C1 in any order.
> After these two updates, B0 and C0 will have version range [0,1) and
> and B1 and C1 will have version range [1,infinity). Before the write
> action completes, a read action comes, gets the current read version
> which is 0 and reads the chain. Since B0 and C0 will be the versions
> that can satisfy this read, the read only action will read the chain
> A0->B0->C0. When write action completes, it posts version 1 as the new
> read version. First read action completes, a second one starts with
> version 1 and that one will read A0->B1->C1. Since the minimum read
> version is now 1, B0 and C0 can be zapped.
Good.
>
> Concerns:
> 1)Previous versions of B+ tree pages could consume too much memory. As
> long as actions are kept small, this is not a problem. Only the
> browsing action does not follow this rule. There are a couple of
> options to deal with it. We can maybe spill previous versions to disk
> after some memory limit.
That's an option. For big bases, this is mandatory.
> Or we can think about chopping down browsing
> action into smaller read actions. Another way to deal with this
> problem would be to keep the previous versions of pages on disk rather
> than in memory. On disk, versions for a B+ page would form a
> chain.This is a radically different way of introducing action
> consistency but I thought this unneccesarily complicates free space
> management while all we need to do with old versions of pages after a
> restart is to toss them away.
I'd rather go for a flush to disk when necessary.
In any case, this is a very interesting analysis of our problem, and the
proposed solutions seems to fit with the current code base, and won't
necessarily lead to a huge modification of JDBM.
Thanks a lot for this mail Selcuk !
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Stefan Seelmann <se...@apache.org>.
Hi Selcuk,
this sounds very interesting. Looking forward to see that solution in action.
In the meantime I hacked a bit on the current JDBM code, I'll attach a
patch to Jira.
Kind Regards,
Stefan
On Thu, Aug 18, 2011 at 10:41 PM, Selcuk AYA <ay...@gmail.com> wrote:
> Hi,
> Today we had some discussion with Alex, Emmanuel and others on how we
> can improve jdbm consistency semantics. I had spent sometime looking
> into this issue and thought it could be useful to put a summary of my
> findings here.
>
> Currently, jdbm has issues with both concurrency and consistency:
> 1) jdbm table lookups, insert and remove interfaces are synchronized
> methods. So even if all the directory server does is to lookups on
> tables, all lookups will be serialized. Moreover, the record manager
> operations are all synchronized methods too. This means, for example,
> while sync of dirty pages to disk goes on, no lookup operation can go
> ahead.
>
> 2) jdbm browser interface does not provide any consistency guarantees.
> If there are underlying changes to the store while the browser is
> open, then it might return inconsistent results. I think the situation
> is even worse if the underlying record manager is CacheRecordManager
> as the same page could be modified and read by a browser concurrently.
>
> I have been working on a scheme which introduces what can be defined
> as action consistency into the jdbm store.
> 1) Actions are lookup, insert, remove and browse. Each action is
> assigned a unique version. Actions are ReadWrite or ReadOnly.
> 2) We allow one ReadWrite action and multiple ReadOnly actions to run
> concurrently.So synchronized methods will be removed.
> 3)We introduce a new record manager which caches jdbm B+ pages. Each
> page in the cache has a [startVersion, endVersion). When an action
> with version V1 wants to read a page, its read can be satisfied
> satisfied from that page's version with V1 >= startVersion && V1 <
> endVersion.
> 4) Pages' previous versions are kept in memory. A page can be purged
> when the minimum version among all active actions is >= endVersion.
>
> So say we have three pages in a chain (A0->B0->C0) and each of them
> has version range [0, infinity). An write action starts and gets the
> version number 1. It updates B0 and C0 to B1 and C1 in any order.
> After these two updates, B0 and C0 will have version range [0,1) and
> and B1 and C1 will have version range [1,infinity). Before the write
> action completes, a read action comes, gets the current read version
> which is 0 and reads the chain. Since B0 and C0 will be the versions
> that can satisfy this read, the read only action will read the chain
> A0->B0->C0. When write action completes, it posts version 1 as the new
> read version. First read action completes, a second one starts with
> version 1 and that one will read A0->B1->C1. Since the minimum read
> version is now 1, B0 and C0 can be zapped.
>
> Concerns:
> 1)Previous versions of B+ tree pages could consume too much memory. As
> long as actions are kept small, this is not a problem. Only the
> browsing action does not follow this rule. There are a couple of
> options to deal with it. We can maybe spill previous versions to disk
> after some memory limit. Or we can think about chopping down browsing
> action into smaller read actions. Another way to deal with this
> problem would be to keep the previous versions of pages on disk rather
> than in memory. On disk, versions for a B+ page would form a
> chain.This is a radically different way of introducing action
> consistency but I thought this unneccesarily complicates free space
> management while all we need to do with old versions of pages after a
> restart is to toss them away.
>
>
> thanks,
> Selcuk
>
>
>
>
> On Thu, Aug 18, 2011 at 11:48 AM, Emmanuel Lecharny (JIRA)
> <ji...@apache.org> wrote:
>>
>> [ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086892#comment-13086892 ]
>>
>> Emmanuel Lecharny commented on DIRSERVER-1642:
>> ----------------------------------------------
>>
>> Damn... The more I think about the issue, the more I find it critical.
>>
>> If we remove an entry while someone is doing a search, the search will fail. Also we have some problem during replication, just when we try to replicate some deletion, and it might prefectly explain why we get those issues.
>>
>>> Unexpected behaviour in JdbmIndex
>>> ---------------------------------
>>>
>>> Key: DIRSERVER-1642
>>> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
>>> Project: Directory ApacheDS
>>> Issue Type: Bug
>>> Reporter: Stefan Seelmann
>>> Attachments: IndexTest.java
>>>
>>>
>>> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
>>> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
>>> - an entry is deleted
>>> - when the open cursors are advanced wrong/unexpected entries are returned
>>> I was able to create a small test that shows the problem:
>>> - the index contains six tuples:
>>> (a,1)
>>> (b,2)
>>> (c,3)
>>> (d,4)
>>> (e,5)
>>> (f,6)
>>> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
>>> - now tuple (c,3) is deleted
>>> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
>>> Note that this doesn't happen with AvlIndex.
>>
>> --
>> This message is automatically generated by JIRA.
>> For more information on JIRA, see: http://www.atlassian.com/software/jira
>>
>>
>>
>
Re: [jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by Selcuk AYA <ay...@gmail.com>.
Hi,
Today we had some discussion with Alex, Emmanuel and others on how we
can improve jdbm consistency semantics. I had spent sometime looking
into this issue and thought it could be useful to put a summary of my
findings here.
Currently, jdbm has issues with both concurrency and consistency:
1) jdbm table lookups, insert and remove interfaces are synchronized
methods. So even if all the directory server does is to lookups on
tables, all lookups will be serialized. Moreover, the record manager
operations are all synchronized methods too. This means, for example,
while sync of dirty pages to disk goes on, no lookup operation can go
ahead.
2) jdbm browser interface does not provide any consistency guarantees.
If there are underlying changes to the store while the browser is
open, then it might return inconsistent results. I think the situation
is even worse if the underlying record manager is CacheRecordManager
as the same page could be modified and read by a browser concurrently.
I have been working on a scheme which introduces what can be defined
as action consistency into the jdbm store.
1) Actions are lookup, insert, remove and browse. Each action is
assigned a unique version. Actions are ReadWrite or ReadOnly.
2) We allow one ReadWrite action and multiple ReadOnly actions to run
concurrently.So synchronized methods will be removed.
3)We introduce a new record manager which caches jdbm B+ pages. Each
page in the cache has a [startVersion, endVersion). When an action
with version V1 wants to read a page, its read can be satisfied
satisfied from that page's version with V1 >= startVersion && V1 <
endVersion.
4) Pages' previous versions are kept in memory. A page can be purged
when the minimum version among all active actions is >= endVersion.
So say we have three pages in a chain (A0->B0->C0) and each of them
has version range [0, infinity). An write action starts and gets the
version number 1. It updates B0 and C0 to B1 and C1 in any order.
After these two updates, B0 and C0 will have version range [0,1) and
and B1 and C1 will have version range [1,infinity). Before the write
action completes, a read action comes, gets the current read version
which is 0 and reads the chain. Since B0 and C0 will be the versions
that can satisfy this read, the read only action will read the chain
A0->B0->C0. When write action completes, it posts version 1 as the new
read version. First read action completes, a second one starts with
version 1 and that one will read A0->B1->C1. Since the minimum read
version is now 1, B0 and C0 can be zapped.
Concerns:
1)Previous versions of B+ tree pages could consume too much memory. As
long as actions are kept small, this is not a problem. Only the
browsing action does not follow this rule. There are a couple of
options to deal with it. We can maybe spill previous versions to disk
after some memory limit. Or we can think about chopping down browsing
action into smaller read actions. Another way to deal with this
problem would be to keep the previous versions of pages on disk rather
than in memory. On disk, versions for a B+ page would form a
chain.This is a radically different way of introducing action
consistency but I thought this unneccesarily complicates free space
management while all we need to do with old versions of pages after a
restart is to toss them away.
thanks,
Selcuk
On Thu, Aug 18, 2011 at 11:48 AM, Emmanuel Lecharny (JIRA)
<ji...@apache.org> wrote:
>
> [ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086892#comment-13086892 ]
>
> Emmanuel Lecharny commented on DIRSERVER-1642:
> ----------------------------------------------
>
> Damn... The more I think about the issue, the more I find it critical.
>
> If we remove an entry while someone is doing a search, the search will fail. Also we have some problem during replication, just when we try to replicate some deletion, and it might prefectly explain why we get those issues.
>
>> Unexpected behaviour in JdbmIndex
>> ---------------------------------
>>
>> Key: DIRSERVER-1642
>> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
>> Project: Directory ApacheDS
>> Issue Type: Bug
>> Reporter: Stefan Seelmann
>> Attachments: IndexTest.java
>>
>>
>> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
>> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
>> - an entry is deleted
>> - when the open cursors are advanced wrong/unexpected entries are returned
>> I was able to create a small test that shows the problem:
>> - the index contains six tuples:
>> (a,1)
>> (b,2)
>> (c,3)
>> (d,4)
>> (e,5)
>> (f,6)
>> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
>> - now tuple (c,3) is deleted
>> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
>> Note that this doesn't happen with AvlIndex.
>
> --
> This message is automatically generated by JIRA.
> For more information on JIRA, see: http://www.atlassian.com/software/jira
>
>
>
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Stefan Seelmann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Stefan Seelmann updated DIRSERVER-1642:
---------------------------------------
Attachment: DIRSERVER-1642.patch
First try of a fix.
- the BPage.Browser stores the last key that was returned
- in case the BTree was modified the stored key is used to recover the BPage.Browser state
- to find out if the BTress was modified a modification counter is used
- added a new test class which should cover all cases
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Selcuk Aya (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Selcuk Aya updated DIRSERVER-1642:
----------------------------------
Attachment: jdbm1.diff
A basic working version for the jdbm versioned Btree.
SnapshotBtree: unit test for the versioned btree. Demonstrates consistent browsing actions while tree is modified.
LRUCache:implements a versioned lru cache. As new versions are created, part of the cache is used for storing previous versions of Btree pages. Concurrent read/write to a BPage is synchronized here.
ActionContext.java, ActionVersioning.java: basically keeps track of the versionassigned to the action. When client enters an action, its action context is stored in a thread local variable. ActionVersioning keeps track of the next readwrite action version and the minimum read version.
BPage and BTree:as updates are done to a page, they are copied on write at thislevel. Also browser keeps track of its action context.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Stefan Seelmann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086692#comment-13086692 ]
Stefan Seelmann commented on DIRSERVER-1642:
--------------------------------------------
I think Kiran is right and the problem is in JDBM. I looked into BPage.Browser. There an integer "int index" is used to store the current position. But if the BTree is modified the elements may be re-ordered in the BPage and the pointer now points to the wrong element. One idea I have is to modify the BPage.Browser to not use an int pointer, but to store the key element. Then for the next call of getNext() or getPrevious() the stored key element is used to lookup the actual index in the BTree. Of course such a lookup is more expensive than just incrementing an integer. I'm too tired to test that now.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Selcuk Aya (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Selcuk Aya updated DIRSERVER-1642:
----------------------------------
Attachment: jdbm5.diff
I changed jdbm-partition to use the versioned Btree. Test cases except StoredProcedureIT are passing. I think the issue with StoredProcedureIT is an exisiting one with serialization of the store procedure and I added an ignore for this test case.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff, jdbm3.diff, jdbm4.diff, jdbm5.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Kiran Ayyagari (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13085967#comment-13085967 ]
Kiran Ayyagari commented on DIRSERVER-1642:
-------------------------------------------
I have recently discussed this sort of behavior with Emmanuel while trying to consider JDBM for replication journal.
The javadoc of browse() method in BTree says:
WARNING: If you make structural modifications to the BTree during browsing, you will get inconsistent browing results.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Emmanuel Lecharny (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Emmanuel Lecharny resolved DIRSERVER-1642.
------------------------------------------
Resolution: Fixed
Fix Version/s: 2.0.0-M3
Fixed applying Selcuk's patches
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Fix For: 2.0.0-M3
>
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff, jdbm3.diff, jdbm4.diff, jdbm5.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Emmanuel Lecharny (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086861#comment-13086861 ]
Emmanuel Lecharny commented on DIRSERVER-1642:
----------------------------------------------
I think it's a bit more complex than just using the Key in the Browser. IMO, the remove (or add) operation must update the browser so that the call to a getNextTuple or getPreviousTuple still return the correct value. One idea would be to retain the last returned key, so that we can reinitialize the index. There is a corner case though for a delete : if the removed element is the last returned one, we must have a way to set the correct position by using the key we returned two calls before.
And i'm afraid it's not enough : for big indexes, the BTree will be span on multiple BPage, and during the remove operation, we don't have access to the browser.
Removing an element in a BTree while browsing it seems a bad idea...
Otherwise, the ultimate solution is to drop JDBM and to use a MVCC system, where elements are not deleted when in use. But this is another story...
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Emmanuel Lecharny (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086167#comment-13086167 ]
Emmanuel Lecharny commented on DIRSERVER-1642:
----------------------------------------------
Kiran is right here, but we must assume that even if we delete some element in the BTree, the cursor we have built on top of it should still be able to return the correct next element, as it stores the current position.
I think the problem has more to do with the way we manipulate the cursor's internal pointers than with the way JDBM deal with BTree modifications.
I will investigate this aspect anyway.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Selcuk Aya (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Selcuk Aya updated DIRSERVER-1642:
----------------------------------
Attachment: jdbm2.diff
modified BTree.java for the existing unit and integration tests to pass. Note that, jdbm-partition is not modified to use the new versioned B+tree and there are only a couple of unit tests for the versioned B+tree yet.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (DIRSERVER-1642) Unexpected behaviour in
JdbmIndex
Posted by "Emmanuel Lecharny (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086892#comment-13086892 ]
Emmanuel Lecharny commented on DIRSERVER-1642:
----------------------------------------------
Damn... The more I think about the issue, the more I find it critical.
If we remove an entry while someone is doing a search, the search will fail. Also we have some problem during replication, just when we try to replicate some deletion, and it might prefectly explain why we get those issues.
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Selcuk Aya (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Selcuk Aya updated DIRSERVER-1642:
----------------------------------
Attachment: jdbm4.diff
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff, jdbm3.diff, jdbm4.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Selcuk Aya (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Selcuk Aya updated DIRSERVER-1642:
----------------------------------
Attachment: jdbm3.diff
changes for jdbm partition to use the versioned Btree. THere are some failures with the server integration tests
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: DIRSERVER-1642.patch, IndexTest.java, jdbm1.diff, jdbm2.diff, jdbm3.diff
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (DIRSERVER-1642) Unexpected behaviour in JdbmIndex
Posted by "Stefan Seelmann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/DIRSERVER-1642?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Stefan Seelmann updated DIRSERVER-1642:
---------------------------------------
Attachment: IndexTest.java
Attached test case
> Unexpected behaviour in JdbmIndex
> ---------------------------------
>
> Key: DIRSERVER-1642
> URL: https://issues.apache.org/jira/browse/DIRSERVER-1642
> Project: Directory ApacheDS
> Issue Type: Bug
> Reporter: Stefan Seelmann
> Attachments: IndexTest.java
>
>
> During my experiments and tests of removing one-level and sub-level indices at least one integration test "SearchAuthorizationIT" failed (the test fails recursivelyDelete()). A debugging session showed that the follwing:
> - in recursivelyDelete() multiple search requests are done which leads to multiple open cursors in the XDBM search engine
> - an entry is deleted
> - when the open cursors are advanced wrong/unexpected entries are returned
> I was able to create a small test that shows the problem:
> - the index contains six tuples:
> (a,1)
> (b,2)
> (c,3)
> (d,4)
> (e,5)
> (f,6)
> - a cursor over the index is created and advanced two times, the expected tuples (a,1) and (b,2) were returned
> - now tuple (c,3) is deleted
> - when the cursor is advanced again the tuple (b,2) is returned again! I had expected (d,4).
> Note that this doesn't happen with AvlIndex.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira