You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@zookeeper.apache.org by "Stu Hood (JIRA)" <ji...@apache.org> on 2008/06/11 06:19:45 UTC
[jira] Created: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
DataTree does not use natural sort for getChildren
--------------------------------------------------
Key: ZOOKEEPER-44
URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
Project: Zookeeper
Issue Type: Improvement
Components: server
Affects Versions: 3.0.0
Reporter: Stu Hood
Priority: Minor
DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Benjamin Reed updated ZOOKEEPER-44:
-----------------------------------
Hadoop Flags: [Reviewed]
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619400#action_12619400 ]
Hudson commented on ZOOKEEPER-44:
---------------------------------
Integrated in ZooKeeper-trunk #42 (See [http://hudson.zones.apache.org/hudson/job/ZooKeeper-trunk/42/])
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff, seqfile2.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619290#action_12619290 ]
Stu Hood commented on ZOOKEEPER-44:
-----------------------------------
This is probably a separate issue, but is anyone worried by the fact that after ~2 billion creates, the sequence number will wrap around and break various algorithms?
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff, seqfile2.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Mahadev konar (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mahadev konar reassigned ZOOKEEPER-44:
--------------------------------------
Assignee: Jakob Homan (was: Benjamin Reed)
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Jakob Homan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jakob Homan updated ZOOKEEPER-44:
---------------------------------
Status: Patch Available (was: Open)
I've gone ahead and implemented the patch as discussed, which does the following:
* Implements the padding for sequential file names, padding ten zeroes to the name (enough to handle as many digits as can be generated by a 32-bit int). This allows the names to be sorted by natural order.
* Removed the server sorting the list of children, leaving it up to the client to do so if it wishes. This could give a very slight performance bump, particularly when dealing with directories with a large number of files.
* Updated the Javadoc to reflect this change in both versions of the getChildren method.
* Adds a unit test that checks that the sequential file names are being created correctly.
I thought about adding a GetChildrenSorted or such method, but since it's really easy for the client to sort the list once returned (java.Collections.List.Sort(children)), it seems like it would be more work to add and support these methods.
Hope this is useful.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Benjamin Reed
> Priority: Minor
> Fix For: 3.0.0
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Jakob Homan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jakob Homan updated ZOOKEEPER-44:
---------------------------------
Attachment: seqfile2.diff
Unnecessary placeholder removed.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff, seqfile2.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Mahadev konar (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619164#action_12619164 ]
Mahadev konar commented on ZOOKEEPER-44:
----------------------------------------
+1 .. thanks jakob ....
nit:
is %1$ redundant? i had to look up the formatter in java for this :)... i think %010d should be fine?
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Mahadev konar (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619293#action_12619293 ]
Mahadev konar commented on ZOOKEEPER-44:
----------------------------------------
2 billion creates seem to be a lot fo creates. also since we are working on an upgrade feature on zookeeper --- we can upgrade the version to be long sometime later ... -- which would make the wrap around 4* 10^18.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff, seqfile2.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Patrick Hunt updated ZOOKEEPER-44:
----------------------------------
Fix Version/s: 3.0.0
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Benjamin Reed
> Priority: Minor
> Fix For: 3.0.0
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Jakob Homan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jakob Homan updated ZOOKEEPER-44:
---------------------------------
Attachment: seqfile.diff
Implements the changes discussed in the Jira.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Benjamin Reed
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12604288#action_12604288 ]
Stu Hood commented on ZOOKEEPER-44:
-----------------------------------
I'd be fine with the sort being removed from getChildren, but fixing the natural sorting problem is still important. It causes undue pain for the client to have to perform an integer-aware sort to get the proper ordering for locks.
My workaround was to pad the sequence value before appending it to the path in create:
{code:java}
if ((createRequest.getFlags() & CreateFlags.SEQUENCE) != 0) {
path = path + String.format("%1$010d", parentCVersion);
}
{code}
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Priority: Minor
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619163#action_12619163 ]
Benjamin Reed commented on ZOOKEEPER-44:
----------------------------------------
+1 Fantastic job Jakob! This looks great. Test cases and everything.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Mahadev konar (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mahadev konar updated ZOOKEEPER-44:
-----------------------------------
Resolution: Fixed
Status: Resolved (was: Patch Available)
I just committed this. THanks Jakob.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Jakob Homan
> Priority: Minor
> Fix For: 3.0.0
>
> Attachments: seqfile.diff, seqfile2.diff
>
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12604265#action_12604265 ]
Patrick Hunt commented on ZOOKEEPER-44:
---------------------------------------
My personal preference would be to leave it unsorted and let the client sort if needed. That way you only pay the perf penalty if you need the children sorted. Either way we should address this -- remove the unnecessary sort and make sure to document that the results are unsorted.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Priority: Minor
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12604235#action_12604235 ]
Benjamin Reed commented on ZOOKEEPER-44:
----------------------------------------
Actually we have been meaning to remove the sort. It causes an unnecessary burden on the server. If we really want things sorted, we should do it in the client library. The question is: do we really want things sorted? Especially in Java it is easy enough for the user to sort the list themself if needed.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Priority: Minor
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Benjamin Reed (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12604290#action_12604290 ]
Benjamin Reed commented on ZOOKEEPER-44:
----------------------------------------
+1 Excellent suggestion!
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Priority: Minor
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (ZOOKEEPER-44) DataTree does not use natural sort
for getChildren
Posted by "Patrick Hunt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/ZOOKEEPER-44?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Patrick Hunt reassigned ZOOKEEPER-44:
-------------------------------------
Assignee: Benjamin Reed
+1, sounds like a great addition to a FAQ.
Assigning to Ben to remove the sort and document appropriately.
> DataTree does not use natural sort for getChildren
> --------------------------------------------------
>
> Key: ZOOKEEPER-44
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-44
> Project: Zookeeper
> Issue Type: Improvement
> Components: server
> Affects Versions: 3.0.0
> Reporter: Stu Hood
> Assignee: Benjamin Reed
> Priority: Minor
>
> DataTree.getChildren() performs Collection.sort() on the list of children before returning it, but Java's default comparator for Strings will sort 'lock-20' before 'lock-3' for instance.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.