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 2012/04/27 01:52:59 UTC
Question about JDBM key/value replacement
Hi guys,
currently, we can replace an existing value when its associated key
exists in the BTree. What I'd like to do is to replace both key and
value in this case.
The rational is that the key mau contain some extra information that are
not used to find the key, like the nbChildren/nbDescendant for a
ParentIdAndrdn key in the RdnIndex.
Is there an easy way to do that with JDBM, or should we extend the API
it offers ?
That would save us a lot of CPU, as we currently have to drop the key
and values and reinject them, which is an costly operation...
Ideas ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 5/7/12 10:01 AM, Selcuk AYA a écrit :
> What I understood from our original email exchange was that
> serializing updates on this auxiliary information was necessary for
> the correctness of the server. But it seems these values are used by
> the optimizer to decide which execution path to choose, so I dont
> think serialization is necessary and maintaining these values
> approximately is probably good enough. So I think we dont have a
> problem.
As soon as we can rebuild the DN wile fetching the entries during a
search, even if the RDN index is changed in the middle of the search,
then we are fine. The only thing is that the user should get back *all*
the entries that were selected when the search was sent. Thet means we
should not return a modified DN.
Does it make sense, or you need a bit more context ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
What I understood from our original email exchange was that
serializing updates on this auxiliary information was necessary for
the correctness of the server. But it seems these values are used by
the optimizer to decide which execution path to choose, so I dont
think serialization is necessary and maintaining these values
approximately is probably good enough. So I think we dont have a
problem.
thanks
Selcuk
On Sat, Apr 28, 2012 at 5:30 PM, Emmanuel Lécharny <el...@gmail.com> wrote:
> 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<el...@gmail.com>
>> wrote:
>>>
>>> Le 4/27/12 8:39 PM, Alex Karasulu a écrit :
>>>>
>>>> On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA<ay...@gmail.com>
>>>> wrote:
>>>>
>>>>> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny<el...@gmail.com>
>>>>> 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 ?
>
> Thanks
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
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<el...@gmail.com> wrote:
>> Le 4/27/12 8:39 PM, Alex Karasulu a écrit :
>>> On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA<ay...@gmail.com> wrote:
>>>
>>>> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny<el...@gmail.com>
>>>> 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 ?
Thanks
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
On Sat, Apr 28, 2012 at 5:29 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Le 4/27/12 8:39 PM, Alex Karasulu a écrit :
>>
>> On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA<ay...@gmail.com> wrote:
>>
>>> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny<el...@gmail.com>
>>> 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.
>
> Typically, as the server code continue to evolve fast, the longer we wait to
> implement a valid solution on trunk, the more likely we wll have some huge
> problems to merge.
>
> I stress out the fact that we are not facing a technical issue here, but
> more a roadmap issue.
>
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/27/12 8:39 PM, Alex Karasulu a écrit :
> On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA<ay...@gmail.com> wrote:
>
>> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny<el...@gmail.com>
>> 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.
Typically, as the server code continue to evolve fast, the longer we
wait to implement a valid solution on trunk, the more likely we wll have
some huge problems to merge.
I stress out the fact that we are not facing a technical issue here, but
more a roadmap issue.
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Alex Karasulu <ak...@apache.org>.
On Fri, Apr 27, 2012 at 8:11 PM, Selcuk AYA <ay...@gmail.com> wrote:
> On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny <el...@gmail.com>
> wrote:
> > Le 4/27/12 6:35 PM, Selcuk AYA a écrit :
> >>
> >> On Fri, Apr 27, 2012 at 9:08 AM, Emmanuel Lécharny<el...@gmail.com>
> >> wrote:
> >>>
> >>> We don't really care if that serialize the modifications, because the
> >>> server
> >>>
> >>> does not have to be fast when we inject data, only when we read data.
> At
> >>> least, we could think about a serialization over the operations on one
> >>> index
> >>> like the RdnIndex (as an entry modification may update more than one
> >>> entry
> >>> in this index).
> >>>
> >>> Is that a problem ?
> >>
> >> Depends. What I have been describing in the emails and trying to
> >> implement is an optimistic locking scheme where modifications can go
> >> in parallel unless they conflict. It seems we could just get a big
> >> lock for write txns rather than dealing with optimistic concurrency
> >> control.
> >
> >
> > Ok, I see.
> >
> > What would be the impact on the txn branch if we fallback to such a
> system ?
>
> we would remove the conflict detection and txn retry in case of
> conflicts and change how RW txns are handled.
>
> >
> > 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.
--
Best Regards,
-- Alex
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
On Fri, Apr 27, 2012 at 9:46 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Le 4/27/12 6:35 PM, Selcuk AYA a écrit :
>>
>> On Fri, Apr 27, 2012 at 9:08 AM, Emmanuel Lécharny<el...@gmail.com>
>> wrote:
>>>
>>> We don't really care if that serialize the modifications, because the
>>> server
>>>
>>> does not have to be fast when we inject data, only when we read data. At
>>> least, we could think about a serialization over the operations on one
>>> index
>>> like the RdnIndex (as an entry modification may update more than one
>>> entry
>>> in this index).
>>>
>>> Is that a problem ?
>>
>> Depends. What I have been describing in the emails and trying to
>> implement is an optimistic locking scheme where modifications can go
>> in parallel unless they conflict. It seems we could just get a big
>> lock for write txns rather than dealing with optimistic concurrency
>> control.
>
>
> Ok, I see.
>
> What would be the impact on the txn branch if we fallback to such a system ?
we would remove the conflict detection and txn retry in case of
conflicts and change how RW txns are handled.
>
> 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.
>
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
thanks
Selcuk
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/27/12 6:35 PM, Selcuk AYA a écrit :
> On Fri, Apr 27, 2012 at 9:08 AM, Emmanuel Lécharny<el...@gmail.com> wrote:
>> We don't really care if that serialize the modifications, because the server
>> does not have to be fast when we inject data, only when we read data. At
>> least, we could think about a serialization over the operations on one index
>> like the RdnIndex (as an entry modification may update more than one entry
>> in this index).
>>
>> Is that a problem ?
> Depends. What I have been describing in the emails and trying to
> implement is an optimistic locking scheme where modifications can go
> in parallel unless they conflict. It seems we could just get a big
> lock for write txns rather than dealing with optimistic concurrency
> control.
Ok, I see.
What would be the impact on the txn branch if we fallback to such a
system ?
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 ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
On Fri, Apr 27, 2012 at 9:08 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Le 4/27/12 5:46 PM, Selcuk AYA a écrit :
>
>> On Fri, Apr 27, 2012 at 6:06 AM, Emmanuel Lécharny<el...@gmail.com>
>> wrote:
>>>
>>> Le 4/27/12 2:09 PM, Selcuk AYA a écrit :
>>>
>>>> Hi,
>>>> On Thu, Apr 26, 2012 at 4:52 PM, Emmanuel Lécharny<el...@gmail.com>
>>>> wrote:
>>>>>
>>>>> Hi guys,
>>>>>
>>>>> currently, we can replace an existing value when its associated key
>>>>> exists
>>>>> in the BTree. What I'd like to do is to replace both key and value in
>>>>> this
>>>>> case.
>>>>>
>>>>> The rational is that the key mau contain some extra information that
>>>>> are
>>>>> not
>>>>> used to find the key, like the nbChildren/nbDescendant for a
>>>>> ParentIdAndrdn
>>>>> key in the RdnIndex.
>>>>>
>>>>> Is there an easy way to do that with JDBM, or should we extend the API
>>>>> it
>>>>> offers ?
>>>>
>>>> as I understand you are trying to store some auxiliary information per
>>>> key?
>>>
>>> Yep.
>>>
>>>
>>>> With JDBM we can:
>>>> - provide<K, aux> tuple as the key and pass the key comparator to
>>>> be the comparator for the actual keys.
>>>> - change JDBM code to update key inside when replacing an entry.
>>>>
>>>> however, in general, I do not think we can expect a key/value store to
>>>> update the key when replacing an entry. So I am not sure it is a good
>>>> idea to do this kind of thing.
>>>
>>>
>>> The pb is that those auxiliary informations are not part of the compare
>>> being done. Ie, two keys may be seen as equals, but the auxiliary
>>> information might be different. In this very case, I'd like the new
>>> version
>>> of the key replaced.
>>> It may be very specific to my need, and we can also consider that the
>>> value
>>> might cary those extra informations, too, instead of storing them in the
>>> key.
>>>
>>> So for the<ParentIdAndRdn, ID> tuple, where the data structure is :
>>> ParentIdAndRdn :
>>> {
>>> ID parentId,
>>> Rdn[] rdns,
>>> int nbChildren,
>>> int nbDescendant
>>> }
>>>
>>> we could inject the two ints after having read the value if this value
>>> structure was :
>>>
>>> AugmentedID
>>> {
>>> ID id
>>> int nbChildren,
>>> int nbDescendant
>>> }
>>
>> I think this would be better. However, note that in txns branch, we
>> removed most of the generics and assumed that indices store UUID as
>> their value. I hope we go with removal/add ( I guess this is what you
>> are doing now)
>
> Should not be a big problem here. Generics are an issue anyway...
>
OK, on txn branch the assumption that we store UUID as the value of an
index has to be removed then.
>>
>>> and serializing the ParentIdAndRdn ID and Rdn[] only.
>>
>> I am kind of confused, I have a couple of questions:
>>
>> 1) Can you explain why we need to store nbChildren and nbDescedant but
>> do not need to serialize it?
>
> We *do* serialize those elements. What I suggest is that we store those
> information in the values, not in the keys, as in any case, we will get a
> tuple <key, value>, so we will always have the extended informations.
>
>
>> What if the page storing an entry is
>> kicked out of cache and we loose nbChildren and nbDescendant?
>
> Then we will read them from disk, if the cache does not contain those
> information, right ?
>
>
>>
>> 2)Connected with the above question, how do we maintain these
>> auxiliary data? Are there maintained only in memory or on disk as
>> well? Do they have to absolutely correct to get consistent data out of
>> the server?
>
> On memory and on disk. They are absolutely critical as they are used to
> browe the tree while doing a One/Subtree scope search.
>
>
>>
>> 3) Lets say I have<rdn1, rdn2,rdn3> and<rdn1,rdn2, rdn4> . Thread 1
>> adds<rdn1, rdn2,rdn3, rdn5> and thread 2 add<rdn1,rdn2, rdn4,rdn6>
>> concurrently.
>> These two threads run concurrently but they should not
>> logically conflict. Now they have to read nbDescendants of<rdn1,rdn2>
>> and increment it but they have to do it in such a way that the net
>> effect of these two threads is serialized.
>
> yep.
>
>
>> I am not sure how to do
>> this.
>
> do you mean that the indexes aren't gloablly protected when we modify some
> data ? I thought that a modification will protect all the index it will
> update until they have all been updated, then the next modification can
> operate.
No.
>
> We don't really care if that serialize the modifications, because the server
> does not have to be fast when we inject data, only when we read data. At
> least, we could think about a serialization over the operations on one index
> like the RdnIndex (as an entry modification may update more than one entry
> in this index).
>
> Is that a problem ?
Depends. What I have been describing in the emails and trying to
implement is an optimistic locking scheme where modifications can go
in parallel unless they conflict. It seems we could just get a big
lock for write txns rather than dealing with optimistic concurrency
control.
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
thanks
Selcuk
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/27/12 5:46 PM, Selcuk AYA a écrit :
> On Fri, Apr 27, 2012 at 6:06 AM, Emmanuel Lécharny<el...@gmail.com> wrote:
>> Le 4/27/12 2:09 PM, Selcuk AYA a écrit :
>>
>>> Hi,
>>> On Thu, Apr 26, 2012 at 4:52 PM, Emmanuel Lécharny<el...@gmail.com>
>>> wrote:
>>>> Hi guys,
>>>>
>>>> currently, we can replace an existing value when its associated key
>>>> exists
>>>> in the BTree. What I'd like to do is to replace both key and value in
>>>> this
>>>> case.
>>>>
>>>> The rational is that the key mau contain some extra information that are
>>>> not
>>>> used to find the key, like the nbChildren/nbDescendant for a
>>>> ParentIdAndrdn
>>>> key in the RdnIndex.
>>>>
>>>> Is there an easy way to do that with JDBM, or should we extend the API it
>>>> offers ?
>>> as I understand you are trying to store some auxiliary information per
>>> key?
>> Yep.
>>
>>
>>> With JDBM we can:
>>> - provide<K, aux> tuple as the key and pass the key comparator to
>>> be the comparator for the actual keys.
>>> - change JDBM code to update key inside when replacing an entry.
>>>
>>> however, in general, I do not think we can expect a key/value store to
>>> update the key when replacing an entry. So I am not sure it is a good
>>> idea to do this kind of thing.
>>
>> The pb is that those auxiliary informations are not part of the compare
>> being done. Ie, two keys may be seen as equals, but the auxiliary
>> information might be different. In this very case, I'd like the new version
>> of the key replaced.
>> It may be very specific to my need, and we can also consider that the value
>> might cary those extra informations, too, instead of storing them in the
>> key.
>>
>> So for the<ParentIdAndRdn, ID> tuple, where the data structure is :
>> ParentIdAndRdn :
>> {
>> ID parentId,
>> Rdn[] rdns,
>> int nbChildren,
>> int nbDescendant
>> }
>>
>> we could inject the two ints after having read the value if this value
>> structure was :
>>
>> AugmentedID
>> {
>> ID id
>> int nbChildren,
>> int nbDescendant
>> }
> I think this would be better. However, note that in txns branch, we
> removed most of the generics and assumed that indices store UUID as
> their value. I hope we go with removal/add ( I guess this is what you
> are doing now)
Should not be a big problem here. Generics are an issue anyway...
>
>> and serializing the ParentIdAndRdn ID and Rdn[] only.
> I am kind of confused, I have a couple of questions:
>
> 1) Can you explain why we need to store nbChildren and nbDescedant but
> do not need to serialize it?
We *do* serialize those elements. What I suggest is that we store those
information in the values, not in the keys, as in any case, we will get
a tuple <key, value>, so we will always have the extended informations.
> What if the page storing an entry is
> kicked out of cache and we loose nbChildren and nbDescendant?
Then we will read them from disk, if the cache does not contain those
information, right ?
>
> 2)Connected with the above question, how do we maintain these
> auxiliary data? Are there maintained only in memory or on disk as
> well? Do they have to absolutely correct to get consistent data out of
> the server?
On memory and on disk. They are absolutely critical as they are used to
browe the tree while doing a One/Subtree scope search.
>
> 3) Lets say I have<rdn1, rdn2,rdn3> and<rdn1,rdn2, rdn4> . Thread 1
> adds<rdn1, rdn2,rdn3, rdn5> and thread 2 add<rdn1,rdn2, rdn4,rdn6>
> concurrently.
> These two threads run concurrently but they should not
> logically conflict. Now they have to read nbDescendants of<rdn1,rdn2>
> and increment it but they have to do it in such a way that the net
> effect of these two threads is serialized.
yep.
> I am not sure how to do
> this.
do you mean that the indexes aren't gloablly protected when we modify
some data ? I thought that a modification will protect all the index it
will update until they have all been updated, then the next modification
can operate.
We don't really care if that serialize the modifications, because the
server does not have to be fast when we inject data, only when we read
data. At least, we could think about a serialization over the operations
on one index like the RdnIndex (as an entry modification may update more
than one entry in this index).
Is that a problem ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
On Fri, Apr 27, 2012 at 6:06 AM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Le 4/27/12 2:09 PM, Selcuk AYA a écrit :
>
>> Hi,
>> On Thu, Apr 26, 2012 at 4:52 PM, Emmanuel Lécharny<el...@gmail.com>
>> wrote:
>>>
>>> Hi guys,
>>>
>>> currently, we can replace an existing value when its associated key
>>> exists
>>> in the BTree. What I'd like to do is to replace both key and value in
>>> this
>>> case.
>>>
>>> The rational is that the key mau contain some extra information that are
>>> not
>>> used to find the key, like the nbChildren/nbDescendant for a
>>> ParentIdAndrdn
>>> key in the RdnIndex.
>>>
>>> Is there an easy way to do that with JDBM, or should we extend the API it
>>> offers ?
>>
>> as I understand you are trying to store some auxiliary information per
>> key?
>
> Yep.
>
>
>> With JDBM we can:
>> - provide<K, aux> tuple as the key and pass the key comparator to
>> be the comparator for the actual keys.
>> - change JDBM code to update key inside when replacing an entry.
>>
>> however, in general, I do not think we can expect a key/value store to
>> update the key when replacing an entry. So I am not sure it is a good
>> idea to do this kind of thing.
>
>
> The pb is that those auxiliary informations are not part of the compare
> being done. Ie, two keys may be seen as equals, but the auxiliary
> information might be different. In this very case, I'd like the new version
> of the key replaced.
> It may be very specific to my need, and we can also consider that the value
> might cary those extra informations, too, instead of storing them in the
> key.
>
> So for the <ParentIdAndRdn, ID> tuple, where the data structure is :
> ParentIdAndRdn :
> {
> ID parentId,
> Rdn[] rdns,
> int nbChildren,
> int nbDescendant
> }
>
> we could inject the two ints after having read the value if this value
> structure was :
>
> AugmentedID
> {
> ID id
> int nbChildren,
> int nbDescendant
> }
I think this would be better. However, note that in txns branch, we
removed most of the generics and assumed that indices store UUID as
their value. I hope we go with removal/add ( I guess this is what you
are doing now)
>
> and serializing the ParentIdAndRdn ID and Rdn[] only.
I am kind of confused, I have a couple of questions:
1) Can you explain why we need to store nbChildren and nbDescedant but
do not need to serialize it? What if the page storing an entry is
kicked out of cache and we loose nbChildren and nbDescendant?
2)Connected with the above question, how do we maintain these
auxiliary data? Are there maintained only in memory or on disk as
well? Do they have to absolutely correct to get consistent data out of
the server?
3) Lets say I have <rdn1, rdn2,rdn3> and <rdn1,rdn2, rdn4> . Thread 1
adds <rdn1, rdn2,rdn3, rdn5> and thread 2 add <rdn1,rdn2, rdn4,rdn6>
concurrently. These two threads run concurrently but they should not
logically conflict. Now they have to read nbDescendants of <rdn1,rdn2>
and increment it but they have to do it in such a way that the net
effect of these two threads is serialized. I am not sure how to do
this. With subalias index this was not a problem because even if these
threads would change the same sub alias index, they would not change
the same index entry.This is going to affect txns big time.
>
> That may work...
>
> thoughts ?
>
>
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
Re: Question about JDBM key/value replacement
Posted by Emmanuel Lécharny <el...@gmail.com>.
Le 4/27/12 2:09 PM, Selcuk AYA a écrit :
> Hi,
> On Thu, Apr 26, 2012 at 4:52 PM, Emmanuel Lécharny<el...@gmail.com> wrote:
>> Hi guys,
>>
>> currently, we can replace an existing value when its associated key exists
>> in the BTree. What I'd like to do is to replace both key and value in this
>> case.
>>
>> The rational is that the key mau contain some extra information that are not
>> used to find the key, like the nbChildren/nbDescendant for a ParentIdAndrdn
>> key in the RdnIndex.
>>
>> Is there an easy way to do that with JDBM, or should we extend the API it
>> offers ?
> as I understand you are trying to store some auxiliary information per
> key?
Yep.
> With JDBM we can:
> - provide<K, aux> tuple as the key and pass the key comparator to
> be the comparator for the actual keys.
> - change JDBM code to update key inside when replacing an entry.
>
> however, in general, I do not think we can expect a key/value store to
> update the key when replacing an entry. So I am not sure it is a good
> idea to do this kind of thing.
The pb is that those auxiliary informations are not part of the compare
being done. Ie, two keys may be seen as equals, but the auxiliary
information might be different. In this very case, I'd like the new
version of the key replaced.
It may be very specific to my need, and we can also consider that the
value might cary those extra informations, too, instead of storing them
in the key.
So for the <ParentIdAndRdn, ID> tuple, where the data structure is :
ParentIdAndRdn :
{
ID parentId,
Rdn[] rdns,
int nbChildren,
int nbDescendant
}
we could inject the two ints after having read the value if this value
structure was :
AugmentedID
{
ID id
int nbChildren,
int nbDescendant
}
and serializing the ParentIdAndRdn ID and Rdn[] only.
That may work...
thoughts ?
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: Question about JDBM key/value replacement
Posted by Selcuk AYA <ay...@gmail.com>.
Hi,
On Thu, Apr 26, 2012 at 4:52 PM, Emmanuel Lécharny <el...@gmail.com> wrote:
> Hi guys,
>
> currently, we can replace an existing value when its associated key exists
> in the BTree. What I'd like to do is to replace both key and value in this
> case.
>
> The rational is that the key mau contain some extra information that are not
> used to find the key, like the nbChildren/nbDescendant for a ParentIdAndrdn
> key in the RdnIndex.
>
> Is there an easy way to do that with JDBM, or should we extend the API it
> offers ?
as I understand you are trying to store some auxiliary information per
key? With JDBM we can:
- provide <K, aux> tuple as the key and pass the key comparator to
be the comparator for the actual keys.
- change JDBM code to update key inside when replacing an entry.
however, in general, I do not think we can expect a key/value store to
update the key when replacing an entry. So I am not sure it is a good
idea to do this kind of thing.
>
> That would save us a lot of CPU, as we currently have to drop the key and
> values and reinject them, which is an costly operation...
>
> Ideas ?
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
thanks
Selcuk