You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-dev@jackrabbit.apache.org by Davide Giannella <gi...@gmail.com> on 2014/04/22 18:07:43 UTC
Avoiding conflicts (OAK-1717)
Good evening everyone,
(long email warning)
had an offline discussion with Marcel regarding OAK-1717.
Even by having annotating conflicts for the DocumentNS persistence by
implementing OAK-1185 could not suffice for some cases.
https://issues.apache.org/jira/browse/OAK-1717
https://issues.apache.org/jira/browse/OAK-1185
Se trying to see any other implementation and the suggestion was to rely
on the lexicographically nodes order that is implicitly provided by the
MongoNS. Getting rid therefore of the conflicting property (:next).
This could work perfectly for the ascending indexes but makes it a bit
more difficult for the descending use case.
Thinking around a possible algorithm to address the reverse-order case I
thought about something like "complement 9" where by dealing only with
letters and numbers I can convert easily
2013-03-01 becoming 7986-96-97 by doing 9-2 9-0 ... and 9-7 9-9 ... on
the way back.
Same principle if I deal with letters
A-Z is 65-90 assuming 65=0 we could have A = 65 = 0 = 90-0 = 90 = Z = 90
- 90 = 0 = 65 = A.
a-z is 97-122.
I think you got the trick by now.
Now the questions.
Unicode. This ugly beast. How deal in that case? How would a String
represent a unicode value that should be then a node name? Or to put it
in another way what will it be in a String (before or afterKeys) of the
update() method
http://goo.gl/D5FtYk
Second question. By getting rid of the skip list we won't be able to
quickly seek items on big indexes when searching. Ideas around it?
Thank you
Regards
Davide
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 06/05/2014 20:29, Michael Dürig wrote:
> On 6.5.14 2:59 , Davide Giannella wrote:
>> On 02/05/2014 10:38, Michael Dürig wrote:
>>> Stay with the linked list / skip list approach but defer inserting new
>>> keys to a background operation. Instead new keys are put into a
>>> "pending-non-conflicting-id" container until picked up by a background
>>> thread and merged into the linked list. Conflicts are simply handled
>>> by a first committer wins strategy in the same way we handle the
>>> entire index update currently.
>>>
>>> When such an index is used, the "pending-non-conflicting-id" container
>>> would have to be considered and its content would have to be merged
>>> into the linked list on the fly. This should be rather easy by first
>>> sorting these extra keys and then on the fly merging the linked list
>>> and the sorted extra keys.
>> ...
> ...
Had a long off-line discussion about the topic with Michael where we
brainstormed structures, use-cases and conflicts.
We're going to go for one of the following:
# Solution 1
:index : {
_pending : {
prop-550e8400-e29b-41d4-a716-446655440000 : {
foo="/path/to/the/content" },
prop-550e8400-e29b-41d4-a716-446655440000 : {
bar="-/path/to/the/content" } <== deletion
}
}
where each cluster node/session add a
prop-UUID : { $property-value = "${operation-if-needed}/pathtocontent" }
then the async merger will parse those, apply to the actual structure
and delete from the _pending area.
## Pros
definitely avoid conflicts
works as a sort of ChangeLog
## Cons
will be harder the merging of results.
# Solution 2
:index : {
keyA : {
path : { to : { content : {match=true} } }
},
keyB : {
path : { to : { content : {deleted=true} } }
}
}
where each cluster use the _pending area as it would be a real index (no
order in here though) and will never physically delete a node.
The async merger will parse and merge into the actual index cleaning-up
while doing it.
## Pros
Easy for on-the-fly merging while serving queries
## Cons
Could not avoid conflict as we expect.
Will update the ticket accordingly for the records.
Cheers
Davide
Re: Avoiding conflicts (OAK-1717)
Posted by Michael Dürig <md...@apache.org>.
On 6.5.14 2:59 , Davide Giannella wrote:
> On 02/05/2014 10:38, Michael Dürig wrote:
>> Stay with the linked list / skip list approach but defer inserting new
>> keys to a background operation. Instead new keys are put into a
>> "pending-non-conflicting-id" container until picked up by a background
>> thread and merged into the linked list. Conflicts are simply handled
>> by a first committer wins strategy in the same way we handle the
>> entire index update currently.
>>
>> When such an index is used, the "pending-non-conflicting-id" container
>> would have to be considered and its content would have to be merged
>> into the linked list on the fly. This should be rather easy by first
>> sorting these extra keys and then on the fly merging the linked list
>> and the sorted extra keys.
> Interesting idea. We could have the index with a structure like
>
> :index : {
> _pending : {
> keyA : {...},
> keyB : {...},
> ...
> keyN : {...}
> },
> :start : {...},
> ...
> keyN : {...}
> }
>
> where under `_pending` it's kept, as you said, a list of keys+documents
> but unlinked. This is maintained with a simple NodeBuilder.child(). The
> Async agent will be the only one taking care of doing
> NodeBuilder.remove() once merged.
>
> Will it be an unmanageable conflict if we have the agent on ClusterA
> removing the key "foobar" and in the same cycle ClusterB add a new
> document under "foobar"?
>
> Still not sure how I could manage deletions and edits (documents that
> changed key) in this scenario.
I think we can. At least if we can rely on the conflict resolution being
implemented as I described earlier [1]. You'd need to double check this
for the DocumentNS though. @Marcel, could you shed some light on this?
The keyXXX nodes from above would need to contain properties with unique
names that in turn point to the respective nodes for that key. When such
a node is removed the property would get removed, but not the parent
node, event if it happens to be empty. This would be left to the async
maintenance task.
For example say we initially have
keyA : { p5254=/foo/bar }
now someone adds /bar/baz and someone else adds /quz/qoz and someone
else again removes /foo/bar for the same keyA. This would result in:
keyA : { p6475=/bar/baz, p7489=/quz/qoz }
This would even work without conflict if two or more cluster nodes would
at the same time remove /foo/bar.
As special case is when the same node for keyA, say /x/y, is added
concurrently by multiple cluster nodes. This would now result in
keyA : { p6475=/bar/baz, p7489=/quz/qoz, p9873=/x/y, p1255=/x/y }
I.e. /x/y get's duplicated, which needs to be properly handled by the
async maintenance task and also when using the index before it has been
maintained.
[1]
https://issues.apache.org/jira/browse/OAK-1553?focusedCommentId=13940731&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13940731
>> I think such an approach is traded off very well: the index is always
>> consistent, however depending on the number of keys in the
>> "pending-non-conflicting-id" container performance might degrade a bit
>> until the background process has caught up again. Additionally this
>> approach is only slightly more complicated than what we already have.
> Well we could limit the sorting on the _pending area only to a
> configurable limit to avoid OOM. Let's say 1000 keys. It could be a
> decent compromise.
I think it is a decent compromise and we should not worry about it too
much at this point.
>
> In the meanwhile I was investigating the B-Tree (BT). It would work on
> paper of course and it has the same O() of the SkipList (SL). As
> advantage it could serve ascending and descending order off the same
> index. On the other hand it sounds as it will be less efficient in
> serving range queries. In the case of the SL all we have to do is
> seeking the correct start and then just "browse through", while in case
> of the BT to navigate it we'll have to continuously going up and down
> the tree, in-memory sorting of the current bucket and seeking where to
> go. Plus in the case of `lastModified` dates where we always have to add
> a greater element, it will require the update of all the buckets from
> top to leaf.
>
> What I'm not sure around the BT is the ability to manage conflict. Let's
> say we have
>
> A Z
> | \
> .. MQZ
> / | \
> OQ XYZ
>
> if the same instant ClusterA deletes O and Q the results will be
>
> A Z
> | \
> .. MZ
> / \
> XYZ
>
> and ClusterB adds P with the results will be
>
> A Z
> | \
> .. MQZ
> / | \
> OPQ XYZ
>
> how do we expect mongo to manage this situation during the cluster sync?
> Each letter is a node and the line points to subnodes.
My initial idea was that the btree maintenance would only be done by the
async task while added keys would be kept in a "pending" bucket... at
which point I realised that we could very well do the same thing with
the current linked/skip list approach, which probably performs better,
is easier to implement and closer to what we already have.
Michael
>
> Any thoughts on this?
>
> D.
>
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 02/05/2014 10:38, Michael Dürig wrote:
> Stay with the linked list / skip list approach but defer inserting new
> keys to a background operation. Instead new keys are put into a
> "pending-non-conflicting-id" container until picked up by a background
> thread and merged into the linked list. Conflicts are simply handled
> by a first committer wins strategy in the same way we handle the
> entire index update currently.
>
> When such an index is used, the "pending-non-conflicting-id" container
> would have to be considered and its content would have to be merged
> into the linked list on the fly. This should be rather easy by first
> sorting these extra keys and then on the fly merging the linked list
> and the sorted extra keys.
Interesting idea. We could have the index with a structure like
:index : {
_pending : {
keyA : {...},
keyB : {...},
...
keyN : {...}
},
:start : {...},
...
keyN : {...}
}
where under `_pending` it's kept, as you said, a list of keys+documents
but unlinked. This is maintained with a simple NodeBuilder.child(). The
Async agent will be the only one taking care of doing
NodeBuilder.remove() once merged.
Will it be an unmanageable conflict if we have the agent on ClusterA
removing the key "foobar" and in the same cycle ClusterB add a new
document under "foobar"?
Still not sure how I could manage deletions and edits (documents that
changed key) in this scenario.
> I think such an approach is traded off very well: the index is always
> consistent, however depending on the number of keys in the
> "pending-non-conflicting-id" container performance might degrade a bit
> until the background process has caught up again. Additionally this
> approach is only slightly more complicated than what we already have.
Well we could limit the sorting on the _pending area only to a
configurable limit to avoid OOM. Let's say 1000 keys. It could be a
decent compromise.
In the meanwhile I was investigating the B-Tree (BT). It would work on
paper of course and it has the same O() of the SkipList (SL). As
advantage it could serve ascending and descending order off the same
index. On the other hand it sounds as it will be less efficient in
serving range queries. In the case of the SL all we have to do is
seeking the correct start and then just "browse through", while in case
of the BT to navigate it we'll have to continuously going up and down
the tree, in-memory sorting of the current bucket and seeking where to
go. Plus in the case of `lastModified` dates where we always have to add
a greater element, it will require the update of all the buckets from
top to leaf.
What I'm not sure around the BT is the ability to manage conflict. Let's
say we have
A Z
| \
.. MQZ
/ | \
OQ XYZ
if the same instant ClusterA deletes O and Q the results will be
A Z
| \
.. MZ
/ \
XYZ
and ClusterB adds P with the results will be
A Z
| \
.. MQZ
/ | \
OPQ XYZ
how do we expect mongo to manage this situation during the cluster sync?
Each letter is a node and the line points to subnodes.
Any thoughts on this?
D.
Re: Avoiding conflicts (OAK-1717)
Posted by Michael Dürig <md...@apache.org>.
On 30.4.14 9:41 , Davide Giannella wrote:
> On 29/04/2014 16:06, Davide Giannella wrote:
>> ...
>>
>> Serving searches could be done either by the `:next` stream or by the
>> `:next` and then merged on the fly with the current `:next-ID` in the
>> iterator while returning the resultset.
>>
>> Any thoughts on the above?
> More thinking around it... if can't find a way to deliver merged
> searches on the fly it doesn't worth the effort as it will work as an
> asynchronous index with some extra complexity.
>
Another idea that came to mind, which might be easier to implement and
require fewer changes to the existing code:
Stay with the linked list / skip list approach but defer inserting new
keys to a background operation. Instead new keys are put into a
"pending-non-conflicting-id" container until picked up by a background
thread and merged into the linked list. Conflicts are simply handled by
a first committer wins strategy in the same way we handle the entire
index update currently.
When such an index is used, the "pending-non-conflicting-id" container
would have to be considered and its content would have to be merged into
the linked list on the fly. This should be rather easy by first sorting
these extra keys and then on the fly merging the linked list and the
sorted extra keys.
I think such an approach is traded off very well: the index is always
consistent, however depending on the number of keys in the
"pending-non-conflicting-id" container performance might degrade a bit
until the background process has caught up again. Additionally this
approach is only slightly more complicated than what we already have.
Michael
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 29/04/2014 16:06, Davide Giannella wrote:
> ...
>
> Serving searches could be done either by the `:next` stream or by the
> `:next` and then merged on the fly with the current `:next-ID` in the
> iterator while returning the resultset.
>
> Any thoughts on the above?
More thinking around it... if can't find a way to deliver merged
searches on the fly it doesn't worth the effort as it will work as an
asynchronous index with some extra complexity.
D.
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 29/04/2014 14:27, Michael Dürig wrote:
> Hi Davide,
>
> Sounds like an interesting idea. In fact, Tom and me discussed
> something very similar during lunch.
>
> In case of a "conflict" there would be multiple :next-xxx properties.
> When the index is used and those are traversed, the "right" :next-xxx
> property would need to be followed. At the same time the index could
> be marked as "dirty" so an async process could pick it up for cleaning
> at its convenience. We need to make sure this works for all types of
> conflicts. I.e. traversal in the face of multiple :next pointers
> doesn't accidentally drop a node. I don't think I have the full
> picture here yet.
Current situation
:index : {
:start : { :next=n0 },
:n0 : { :next=n2 },
:n1 : { :next=NIL },
:n2 : { :next=n1 }
}
What we're thinking around, let's say we have 2 cluster nodes
0) ContentStrategy (CS) on node A starts and elect a new ID as
previously said: `:next-1-1`
0.1) CS on node B starts and elect a new ID: `:next-2-2`
1) performing the operations we'll have something like
:index : {
:start : {
:next=,
:next-1-1=,
:next-2-2=
}
...
:nN : {
:next=,
:next-1-1=,
:next-2-2=
}
}
where we could have nodes with all the `:next*` as well as only the
`:next`; the one that should be full skiplist compliant.
2) OrderedIndexMerger (OIM) kicks in and starting from :start identify
all the `:next*` properties and in a way "mark" them for merging.
2.1) CS sees it marked and generate a new ID
3) OIM put the proper linking in place and delete the old property once
done.
As a way to "deliver the messages" around and giving the cluster the
chance to sync I was thinking:
2) OIM add a node under a proper structure
:index : {
:tomerge : {
1-1,
2-2,
}
}
2.1) before doing any linking operation each node check if the current
id is not under `:tomerge`. cluster sync and A sees 1-1 under :tomerge
mark for ACK and generate a new ID
:index : {
:tomerge : {
1-1 : { ack=true },
2-2
}
}
3) cluster sync, OIM as its duty inspect under `:tomerge` sees 1-1 with
ack and start putting it as final `:next`.
It's a bit complex but should work out any conflicts. Open point is:
what if a node is shutdown and could not ACK a merge? Probably working
out on a timeout. If it doesn't ACK in 3 cluster sync probably is dead
for us.
Serving searches could be done either by the `:next` stream or by the
`:next` and then merged on the fly with the current `:next-ID` in the
iterator while returning the resultset.
Any thoughts on the above?
> An alternative would be to change the linked list / skip list approach
> and use an ordered tree instead. This should also be free of conflicts
> and would also allow for skipping during traversal. As such trees
> might become unbalanced we'd also need some background process, which
> rebalances these trees. Rebalancing could occur on an as need basis:
> whenever an unbalanced tree is discovered when using an index, a
> balance operation would be scheduled.
I'm giving a look around at ordered/balanced trees (B-Tree in
particular) but I can't grasp on how we could have it working in our
situation without having to either link or sort in memory for siblings
and not risking a move of big sub-trees during insert/rebalancing. Plus
during rebalancing we risk collisions if we use pointers in the same way.
Any rough example on what you were thinking? Some quick stages like
empty, arrive 1, arrive 3, arrive 2, ... :)
D.
Re: Avoiding conflicts (OAK-1717)
Posted by Michael Dürig <md...@apache.org>.
Hi Davide,
Sounds like an interesting idea. In fact, Tom and me discussed
something very similar during lunch.
In case of a "conflict" there would be multiple :next-xxx properties.
When the index is used and those are traversed, the "right" :next-xxx
property would need to be followed. At the same time the index could
be marked as "dirty" so an async process could pick it up for cleaning
at its convenience. We need to make sure this works for all types of
conflicts. I.e. traversal in the face of multiple :next pointers
doesn't accidentally drop a node. I don't think I have the full
picture here yet.
An alternative would be to change the linked list / skip list approach
and use an ordered tree instead. This should also be free of conflicts
and would also allow for skipping during traversal. As such trees
might become unbalanced we'd also need some background process, which
rebalances these trees. Rebalancing could occur on an as need basis:
whenever an unbalanced tree is discovered when using an index, a
balance operation would be scheduled.
Michael
On 29 April 2014 14:53, Davide Giannella <gi...@gmail.com> wrote:
> Thank you all for the support and feedbacks.
>
> In the aim of find a structure that avoid conflicts I was thinking is to
> generate a "cluster-node-unique" :next
> property. Something like
>
> :next-System.nanoTime()-new Random(System.nanoTime()).nextLong()
>
> by the fact that we're going to generate this one once in a while it
> should not affect the performance too much by the usage of nanoTime.
>
> So we should have in the end a list that looks something like
>
> n0: {
> :next = ,
> :next-34567-4567 =,
> :next-76543-6543 =,
> :next-...
> }
>
> this should definitely avoid any concurrency.
>
> But it definitely has to be merged. So it comes an async process that
> runs on a single node (like the async index) in charge of touching the
> :next and in the future generate all the lanes of the skip list.
>
> What I would like to happen is something like: hey node A don't use any
> longer the unique "4568-789" as I'm going to merge it for you. Then node
> A generate a new ID and keep going. Once merged the async process will
> delete the no longer used unique-id.
>
> Other than the overall complexity of the algorithm I'm not sure on how
> to achieve this message.
>
> Any hints, ideas?
>
> Thank you
> Davide
>
>
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
Thank you all for the support and feedbacks.
In the aim of find a structure that avoid conflicts I was thinking is to
generate a "cluster-node-unique" :next
property. Something like
:next-System.nanoTime()-new Random(System.nanoTime()).nextLong()
by the fact that we're going to generate this one once in a while it
should not affect the performance too much by the usage of nanoTime.
So we should have in the end a list that looks something like
n0: {
:next = ,
:next-34567-4567 =,
:next-76543-6543 =,
:next-...
}
this should definitely avoid any concurrency.
But it definitely has to be merged. So it comes an async process that
runs on a single node (like the async index) in charge of touching the
:next and in the future generate all the lanes of the skip list.
What I would like to happen is something like: hey node A don't use any
longer the unique "4568-789" as I'm going to merge it for you. Then node
A generate a new ID and keep going. Once merged the async process will
delete the no longer used unique-id.
Other than the overall complexity of the algorithm I'm not sure on how
to achieve this message.
Any hints, ideas?
Thank you
Davide
Re: Avoiding conflicts (OAK-1717)
Posted by Jukka Zitting <ju...@gmail.com>.
Hi,
On Mon, Apr 28, 2014 at 9:43 AM, Davide Giannella
<gi...@gmail.com> wrote:
> On 23/04/2014 15:05, Michael Dürig wrote:
>> On the SegmentNS there is still a potential for conflicts between
>> sessions. So we'd need some conflict validation there too.
> Just for records. Worked a couple of days with Michael trying to
> reproduce the issue with concurrent sessions on Segment and didn't
> manage to reproduce it.
The SegmentMK guarantees serialized execution of commit hooks (even
for cluster merges once we implement that), so there's no need to
worry about conflicts within commit hooks.
BR,
Jukka Zitting
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 23/04/2014 15:05, Michael Dürig wrote:
> On 23.4.14 3:34 , Davide Giannella wrote:
>> On 23/04/2014 13:59, Michael Dürig wrote:
>>>
>>> Hi Davide,
>>>
>>> While this looks attractive at first I think there are several
>>> problematic aspects:
>>>
>>> 1. We need different implementations for this index depending on
>>> whether SegmentNS or DocumentNS is being used.
>> Yes that would be the case. For SegmentNS the current implementation
>> could be used without conflicts while if we initialise a DocumentNS we
>> provide a Mongo specific implementation during repository
>> initialisation.
>
> On the SegmentNS there is still a potential for conflicts between
> sessions. So we'd need some conflict validation there too.
Just for records. Worked a couple of days with Michael trying to
reproduce the issue with concurrent sessions on Segment and didn't
manage to reproduce it.
Here's the last try if anyone would wish to have a look.
https://github.com/davidegiannella/jackrabbit-oak/blob/a37707afc4cd0f44c784a56f52e41fe63547fd59/oak-jcr/src/test/java/org/apache/jackrabbit/oak/jcr/OrderedIndexConcurrentClusterIT.java#L234
D.
Re: Avoiding conflicts (OAK-1717)
Posted by Michael Dürig <md...@apache.org>.
On 23.4.14 3:34 , Davide Giannella wrote:
> On 23/04/2014 13:59, Michael Dürig wrote:
>>
>> Hi Davide,
>>
>> While this looks attractive at first I think there are several
>> problematic aspects:
>>
>> 1. We need different implementations for this index depending on
>> whether SegmentNS or DocumentNS is being used.
> Yes that would be the case. For SegmentNS the current implementation
> could be used without conflicts while if we initialise a DocumentNS we
> provide a Mongo specific implementation during repository initialisation.
On the SegmentNS there is still a potential for conflicts between
sessions. So we'd need some conflict validation there too.
>
> However while typing I'm thinking: is it possible to have, even by
> developing it, a DocumentNS that sits on top of something different than
> Mongo? If so, how could we differentiate then?
Yes and we actually have that with
org.apache.jackrabbit.oak.plugins.document.rdb.RDBDocumentStore.
>>
>> BTW, I noted that 3 is currently not implemented and that all values
>> are compared after having been converted to strings. I believe this is
>> wrong and we need to fix this. Could you double check on your side and
>> create an issue if needed?
> The current implementation of the IndexStoreStrategy[0] accept only
> Strings and you don't have any knowledge of the original type of the
> property.
>
> (0) http://goo.gl/KLKzDv
>
> However in all my testing I saw then treated correctly. For example
> dates arrives in a valid ISO format like ISO_8601_2000 IIRC that makes
> it String wise comparable.
This works since for ISO-8601 the chronological order is the same as the
lexicographical one.
It's done by using the
> Property.getValue(Type.STRING)[1]
>
> (1) http://goo.gl/YzRBQO
>
> Then we use the property value for creating nodes that are the "keys" of
> the index and therefore need a string representation of it.
And I'm pretty sure the lexicographical order of the string
representation will in general not be the one required. For example
longs and doubles will probably not work correctly. See
http://www.day.com/specs/jcr/2.0/3_Repository_Model.html#3.6.5.1%20CompareTo%20Semantics
Michael
>
> D.
>
>
Re: Avoiding conflicts (OAK-1717)
Posted by Davide Giannella <gi...@gmail.com>.
On 23/04/2014 13:59, Michael Dürig wrote:
>
> Hi Davide,
>
> While this looks attractive at first I think there are several
> problematic aspects:
>
> 1. We need different implementations for this index depending on
> whether SegmentNS or DocumentNS is being used.
Yes that would be the case. For SegmentNS the current implementation
could be used without conflicts while if we initialise a DocumentNS we
provide a Mongo specific implementation during repository initialisation.
However while typing I'm thinking: is it possible to have, even by
developing it, a DocumentNS that sits on top of something different than
Mongo? If so, how could we differentiate then?
> 2. The lexicographically order of the DocumentNS must coincide with
> Java's String.comparaTo(). Not sure whether this is already the case
> or whether this requirement can be imposed at all.
I think so. Will have to do some testing beforehand but it seems it is.
> 3. Depending on the property type you'd need to encode it into a
> string such that the lexicographic order coincides with the JCR's
> compareTo semantics [1]. On top of that you'd also need a reverse
> encoding for the descending order. Something along the lines you
> sketched below using some complement.
The encoding/decoding with something like what I said I think will be a
relatively small overhead.
> Overall I fear the complexity that comes along with such an approach...
>
> BTW, I noted that 3 is currently not implemented and that all values
> are compared after having been converted to strings. I believe this is
> wrong and we need to fix this. Could you double check on your side and
> create an issue if needed?
The current implementation of the IndexStoreStrategy[0] accept only
Strings and you don't have any knowledge of the original type of the
property.
(0) http://goo.gl/KLKzDv
However in all my testing I saw then treated correctly. For example
dates arrives in a valid ISO format like ISO_8601_2000 IIRC that makes
it String wise comparable. It's done by using the
Property.getValue(Type.STRING)[1]
(1) http://goo.gl/YzRBQO
Then we use the property value for creating nodes that are the "keys" of
the index and therefore need a string representation of it.
D.
Re: Avoiding conflicts (OAK-1717)
Posted by Michael Dürig <md...@apache.org>.
Hi Davide,
While this looks attractive at first I think there are several
problematic aspects:
1. We need different implementations for this index depending on whether
SegmentNS or DocumentNS is being used.
2. The lexicographically order of the DocumentNS must coincide with
Java's String.comparaTo(). Not sure whether this is already the case or
whether this requirement can be imposed at all.
3. Depending on the property type you'd need to encode it into a string
such that the lexicographic order coincides with the JCR's compareTo
semantics [1]. On top of that you'd also need a reverse encoding for the
descending order. Something along the lines you sketched below using
some complement.
Overall I fear the complexity that comes along with such an approach...
BTW, I noted that 3 is currently not implemented and that all values are
compared after having been converted to strings. I believe this is wrong
and we need to fix this. Could you double check on your side and create
an issue if needed?
Michael
[1]
http://www.day.com/specs/jcr/2.0/3_Repository_Model.html#3.6.5.1%20CompareTo%20Semantics
On 22.4.14 6:07 , Davide Giannella wrote:
> Good evening everyone,
>
> (long email warning)
>
> had an offline discussion with Marcel regarding OAK-1717.
>
> Even by having annotating conflicts for the DocumentNS persistence by
> implementing OAK-1185 could not suffice for some cases.
>
> https://issues.apache.org/jira/browse/OAK-1717
> https://issues.apache.org/jira/browse/OAK-1185
>
> Se trying to see any other implementation and the suggestion was to rely
> on the lexicographically nodes order that is implicitly provided by the
> MongoNS. Getting rid therefore of the conflicting property (:next).
>
> This could work perfectly for the ascending indexes but makes it a bit
> more difficult for the descending use case.
>
> Thinking around a possible algorithm to address the reverse-order case I
> thought about something like "complement 9" where by dealing only with
> letters and numbers I can convert easily
>
> 2013-03-01 becoming 7986-96-97 by doing 9-2 9-0 ... and 9-7 9-9 ... on
> the way back.
>
> Same principle if I deal with letters
>
> A-Z is 65-90 assuming 65=0 we could have A = 65 = 0 = 90-0 = 90 = Z = 90
> - 90 = 0 = 65 = A.
>
> a-z is 97-122.
>
> I think you got the trick by now.
>
> Now the questions.
>
> Unicode. This ugly beast. How deal in that case? How would a String
> represent a unicode value that should be then a node name? Or to put it
> in another way what will it be in a String (before or afterKeys) of the
> update() method
>
> http://goo.gl/D5FtYk
>
> Second question. By getting rid of the skip list we won't be able to
> quickly seek items on big indexes when searching. Ideas around it?
>
> Thank you
> Regards
> Davide
>