directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lécharny <>
Subject Re: Question about JDBM key/value replacement
Date Sun, 29 Apr 2012 00:30:34 GMT
Some more thoughts (see inline)

Le 4/28/12 6:53 PM, Selcuk AYA a écrit :
> On Sat, Apr 28, 2012 at 5:29 AM, Emmanuel Lécharny<>  wrote:
>> Le 4/27/12 8:39 PM, Alex Karasulu a écrit :
>>> On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA<>    wrote:
>>>> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny<>
>>>> wrote:
>>>>> What also would be the impact on the current code, assuming that we
>>>> update
>>>>> many elements on the RdnIndex, so that the optimistic locking scheme
>>>> keeps
>>>>> working ?
>>>> You know this better. If trying to maintain optimistic locking
>>>> adversely affects searches and we are OK with outstanding RW txn(this
>>>> includes all the operations in the interceptor chain in case of a
>>>> add/delete/modify), then we should get rid of optimistic locking.
>>> IMO I don't think we should get rid of optimistic locking.
>> That's an interesting decision to make...
>> It's pretty obvious that OCC is the way to go when we have low data
>> contention, and this is excactly the case for a LDAP server. Being allowed
>> to process more than one update at a time, and with a low risk to see a
>> collision, that's a clear plus in this context.
>> Now, the question is the added complexity of an OCC solution, compared with
>> a simple global lock over modification, assuming that we have a limited time
>> frame to implement the full OCC system.
> I am OK with going both ways. Just FYI, OCC solution is ready. Right
> now I am trying to handle this and that logical data cache consistency
> that people implemented over years.

Let me explain what would be the impact on OCC if we include the changes 
I have made on the RdnIndex.

First of all, the RdnIndex is used to :
- build the entry's DN before we return them to the client
- find an entry which DN's is known
- ultimately, browsing the DIT with a SUBLEVEL or ONELEVEL scope.

The first two cases are obvious, no need to go deep into it.

Th third use case is more interesting. In fact, it can be split in two :
- ONELEVEL scope searches
- SUBLEVEL scope searches

but in both case, the principles are the same : in order to know if we 
should use the RdnIndex to fetch the entries, we have to know how many 
entries we will get back.

If we go a step deeper, the way we fetch the entries from the master 
table depends on the filter we use. This flter has many expressions 
which are evaluated, and at the end of this evaluation, we will use the 
best possible index to quickly fetch the entries. This evaluation will 
use the number of candidates for each expression.

Having said that, we see that we need to know how many children an entry 
has to be able to select the RdnIndex when doing a ONELEVEL scope 
search, and how many descendants when doing a SUBLEVEL scope search.

Those two numbers (nbChildren/nbDescendants) are computed when we 
add/delete/move some entries, and for the nbDescendants value, we have 
to go up to the tree root (in our case, the naming context entry), 
updating all the ParentIdAndRdn elements.

Obvioulsy, as all the entries are depending on oe unique contextEntry, 
each time we will add/delete some entries, we will have to update its 
contexteEntry associated ParentIdAndRdn element.

Whe using an OCC system, we will detect a conflict for every 
addition/deletion, as the contextEntry's ParentIdAndRdn will be modified 
by all the concurrent hreads. Applying the algorithm blindly would 
result on every concurrent modification to be rollbacked, which would be 
even more costly tha using a global lock.

Is there a solution ? As those counters are incremented or decremented, 
and as we know what is our current modification, we should be able to 
update those numbers in the ParentidAndRdn without having to rollback 
the whole transaction.

I do think that we can have OCC and the RdnIndex multiple modifications 
working together.

Right now, the best would probably to finish the on-going work on the 
txn branch, without thinkig aboyt the ongoing work on the index branch. 
We know that merging both of them will imply some limited changes, but 
not necessarily huge.

Questions, thoughts, comments ?


Emmanuel Lécharny

View raw message