directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <akaras...@gmail.com>
Subject Re: AVL cursor problem?
Date Fri, 25 Nov 2011 09:22:34 GMT


Sent from my iPhone

On Nov 25, 2011, at 10:09 AM, Emmanuel L├ęcharny <elecharny@apache.org> wrote:

> On 11/25/11 8:51 AM, Selcuk AYA wrote:
>> I looked at the code some more and think that using read-write locks
>> might not be a good idea. There are cases where a cursor is held for a
>> partition and the same partition is changed. This makes it hard.
>> 
>> My suggestion is to use a ConcurrentSkipListMap implementation of
>> java( http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html
>> ) rather than our own implementation of avl as the backing sorted map
>> for our avl partition. We can build cursors over this map using the
>> iterator provided by this map ( I did something similar to provide a
>> cursor for the index changes of a txn). This iterator is weakly
>> consistent, that is, it might show future changes but will show a view
>> of the map at least as of the time of its creation. This works for us.
>> Even if cursor shows future changes, our txn layer above should  take
>> care of this and provide a transactionally consistent view.
>> 
>> The cost of the common operations would be amortized o(logn)  with
>> this map. So, this is similar to AVL tree cost. Note that, we would
>> need to use ConcurrentSkipListMaps to store dup values.
>> 
>> Let me know if you think this sounds OK with you.
> Sounds good to me.

Same here - go for it!

--Alex
> 

Mime
View raw message