Home | About | Sematext search-lucene.com search-hadoop.com
 Search Hadoop and all its subprojects:

Switch to Threaded View
Zookeeper >> mail # dev >> question about getChildren and queue recipe


Copy link to this message
-
Re: question about getChildren and queue recipe
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
>>>>
>>