Hi,

I have 2 questions:
- why was it decided not to guarantee any order on the list returned from
getChildren, given that many use-cases require looking on the child with
the smallest id ?
Why not just keep this list in a sorted form on the server ?

-  In the queue recipe (src/recipes/queue), if element() is called twice
we'll always do getChildren twice. Wouldn't
it be better to save the list of children we got from the first element()
call and when going over the list
remove elements from it whenever we see that someone deleted the
corresponding node ?

Thanks,
Alex

On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:

> Hi,
>
> I have 2 questions:
> - why was it decided not to guarantee any order on the list returned from
> getChildren, given that many use-cases require looking on the child with
> the smallest id ?
> Why not just keep this list in a sorted form on the server ?
There is some discussion about this here:

https://issues.apache.org/jira/browse/ZOOKEEPER-44

-Flavio

Thanks Flavio. But what about just storing the list of children on the
server in the order of their creation ? Wouldn't this be consistent
with the sequential id and also cheap ? or am I missing something

Thanks,
Alex

On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>
> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>
>> Hi,
>>
>> I have 2 questions:
>> - why was it decided not to guarantee any order on the list returned from
>> getChildren, given that many use-cases require looking on the child with
>> the smallest id ?
>> Why not just keep this list in a sorted form on the server ?
>
>
> There is some discussion about this here:
>
> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>
> -Flavio
>

Hi Alex, I believe we currently use a set to hold the children of a znode. Are you proposing to use a different data structure?

-Flavio

On Sep 5, 2012, at 1:34 AM, Alexander Shraer wrote:

> Thanks Flavio. But what about just storing the list of children on the
> server in the order of their creation ? Wouldn't this be consistent
> with the sequential id and also cheap ? or am I missing something
>
> Thanks,
> Alex
>
> On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>>
>> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>>
>>> Hi,
>>>
>>> I have 2 questions:
>>> - why was it decided not to guarantee any order on the list returned from
>>> getChildren, given that many use-cases require looking on the child with
>>> the smallest id ?
>>> Why not just keep this list in a sorted form on the server ?
>>
>>
>> There is some discussion about this here:
>>
>> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>>
>> -Flavio
>>

Hi Flavio,

Yes, an ArrayList for example, sorted by creation order. Even
currently although DataNode stores it as a Set, when you retrieve the
list of children DataTree will convert the set to an ArrayList and
return a list. Obviously exists/create will have to traverse the list
to check if it already contains something, so it may be a bit slower,
but having a list may have lots of advantages (such as saving the sort
from clients in many use cases and potentially allowing us to add a
parameter to getChildren to retrieve only the first k znodes, which is
what Jordan meant I think). I'm not sure whether we'll be able to
store in sorted form or sort every time we load the database on
recovery, and probably there are other implications, but it seems
worthwhile to consider.

Alex

On Wed, Sep 5, 2012 at 4:24 AM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
> Hi Alex, I believe we currently use a set to hold the children of a znode. Are you proposing to use a different data structure?
>
> -Flavio
>
> On Sep 5, 2012, at 1:34 AM, Alexander Shraer wrote:
>
>> Thanks Flavio. But what about just storing the list of children on the
>> server in the order of their creation ? Wouldn't this be consistent
>> with the sequential id and also cheap ? or am I missing something
>>
>> Thanks,
>> Alex
>>
>> On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>>>
>>> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>>>
>>>> Hi,
>>>>
>>>> I have 2 questions:
>>>> - why was it decided not to guarantee any order on the list returned from
>>>> getChildren, given that many use-cases require looking on the child with
>>>> the smallest id ?
>>>> Why not just keep this list in a sorted form on the server ?
>>>
>>>
>>> There is some discussion about this here:
>>>
>>> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>>>
>>> -Flavio
>>>
>

Hi Alex, Let's see if we can do a rough analysis of the current implementation to compare with your proposal. The conversion to ArrayList upon a getChildren is correct, so storing an ArrayList gives us an advantage in the case we don't have to clone the children data structure when processing the getChildren call. I've seen though that we call contains on the children object when creating an object (DataTree.createNode). That operation shouldn't be linear. I don't think we use contains on children for the exists operation, so it is not a problem.

About sorting on the client side, I believe Pat also said in ZOOKEEPER-55 that he would be in favor to have it done by the client in the case we decide to sort. For your use case, you could use sequential znodes and have your application sorting it. Given that it is not difficult to do on the application side and not all applications need it, it sounds like a good idea only if we can show that there is no significant performance penalty to the service.  

-Flavio

On Sep 5, 2012, at 5:12 PM, Alexander Shraer wrote:

> Hi Flavio,
>
> Yes, an ArrayList for example, sorted by creation order. Even
> currently although DataNode stores it as a Set, when you retrieve the
> list of children DataTree will convert the set to an ArrayList and
> return a list. Obviously exists/create will have to traverse the list
> to check if it already contains something, so it may be a bit slower,
> but having a list may have lots of advantages (such as saving the sort
> from clients in many use cases and potentially allowing us to add a
> parameter to getChildren to retrieve only the first k znodes, which is
> what Jordan meant I think). I'm not sure whether we'll be able to
> store in sorted form or sort every time we load the database on
> recovery, and probably there are other implications, but it seems
> worthwhile to consider.
>
> Alex
>
> On Wed, Sep 5, 2012 at 4:24 AM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>> Hi Alex, I believe we currently use a set to hold the children of a znode. Are you proposing to use a different data structure?
>>
>> -Flavio
>>
>> On Sep 5, 2012, at 1:34 AM, Alexander Shraer wrote:
>>
>>> Thanks Flavio. But what about just storing the list of children on the
>>> server in the order of their creation ? Wouldn't this be consistent
>>> with the sequential id and also cheap ? or am I missing something
>>>
>>> Thanks,
>>> Alex
>>>
>>> On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>>>>
>>>> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> I have 2 questions:
>>>>> - why was it decided not to guarantee any order on the list returned from
>>>>> getChildren, given that many use-cases require looking on the child with
>>>>> the smallest id ?
>>>>> Why not just keep this list in a sorted form on the server ?
>>>>
>>>>
>>>> There is some discussion about this here:
>>>>
>>>> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>>>>
>>>> -Flavio
>>>>
>>

I agree with
Alexander .
So why no server return children list just with the order of their creation?
2012/9/5 Alexander Shraer <[EMAIL PROTECTED]>
Thanks Flavio. But what about just storing the list of children on the
server in the order of their creation ? Wouldn't this be consistent
with the sequential id and also cheap ? or am I missing something

Thanks,
Alex

On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>
> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>
>> Hi,
>>
>> I have 2 questions:
>> - why was it decided not to guarantee any order on the list returned from
>> getChildren, given that many use-cases require looking on the child with
>> the smallest id ?
>> Why not just keep this list in a sorted form on the server ?
>
>
> There is some discussion about this here:
>
> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>
> -Flavio
>
     

FYI - it would also enable the partial getChildren() method

On Sep 4, 2012, at 5:32 PM, charles charles <[EMAIL PROTECTED]> wrote:

> I agree with
> Alexander .
> So why no server return children list just with the order of their creation?
> 2012/9/5 Alexander Shraer <[EMAIL PROTECTED]>
> Thanks Flavio. But what about just storing the list of children on the
> server in the order of their creation ? Wouldn't this be consistent
> with the sequential id and also cheap ? or am I missing something
>
> Thanks,
> Alex
>
> On Tue, Sep 4, 2012 at 3:11 PM, Flavio Junqueira <[EMAIL PROTECTED]> wrote:
>>
>> On Sep 4, 2012, at 3:10 AM, Alexander Shraer wrote:
>>
>>> Hi,
>>>
>>> I have 2 questions:
>>> - why was it decided not to guarantee any order on the list returned from
>>> getChildren, given that many use-cases require looking on the child with
>>> the smallest id ?
>>> Why not just keep this list in a sorted form on the server ?
>>
>>
>> There is some discussion about this here:
>>
>> https://issues.apache.org/jira/browse/ZOOKEEPER-44
>>
>> -Flavio
>>
>