You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@zookeeper.apache.org by Alexander Shraer <sh...@gmail.com> on 2012/09/04 03:10:54 UTC
question about getChildren and queue recipe
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
Re: question about getChildren and queue recipe
Posted by Flavio Junqueira <fp...@yahoo-inc.com>.
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 <fp...@yahoo-inc.com> 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 <fp...@yahoo-inc.com> 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
>>>>
>>
Re: question about getChildren and queue recipe
Posted by Alexander Shraer <sh...@gmail.com>.
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 <fp...@yahoo-inc.com> 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 <fp...@yahoo-inc.com> 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
>>>
>
Re: question about getChildren and queue recipe
Posted by Flavio Junqueira <fp...@yahoo-inc.com>.
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 <fp...@yahoo-inc.com> 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
>>
Re: question about getChildren and queue recipe
Posted by Alexander Shraer <sh...@gmail.com>.
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 <fp...@yahoo-inc.com> 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
>
Re: question about getChildren and queue recipe
Posted by Flavio Junqueira <fp...@yahoo-inc.com>.
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