hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hadoop QA (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HADOOP-5638) More improvement on block placement performance
Date Fri, 10 Apr 2009 08:14:12 GMT

    [ https://issues.apache.org/jira/browse/HADOOP-5638?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697766#action_12697766
] 

Hadoop QA commented on HADOOP-5638:
-----------------------------------

-1 overall.  Here are the results of testing the latest attachment 
  http://issues.apache.org/jira/secure/attachment/12405099/excludedList2.patch
  against trunk revision 763728.

    +1 @author.  The patch does not contain any @author tags.

    +1 tests included.  The patch appears to include 3 new or modified tests.

    +1 javadoc.  The javadoc tool did not generate any warning messages.

    +1 javac.  The applied patch does not increase the total number of javac compiler warnings.

    +1 findbugs.  The patch does not introduce any new Findbugs warnings.

    +1 Eclipse classpath. The patch retains Eclipse classpath integrity.

    +1 release audit.  The applied patch does not increase the total number of release audit
warnings.

    -1 core tests.  The patch failed core unit tests.

    -1 contrib tests.  The patch failed contrib unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/178/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/178/artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/178/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hadoop-Patch-vesta.apache.org/178/console

This message is automatically generated.

> More improvement on block placement performance
> -----------------------------------------------
>
>                 Key: HADOOP-5638
>                 URL: https://issues.apache.org/jira/browse/HADOOP-5638
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: dfs
>            Reporter: Hairong Kuang
>            Assignee: Hairong Kuang
>             Fix For: 0.21.0
>
>         Attachments: excludedList.patch, excludedList1.patch, excludedList2.patch
>
>
> Block placement algorithm currently has an excluded node list, which contains all datanodes
that have been visited. This list is implemented as an array list, whose cost of inserting
is O(1) but the cost of query "contains" is O( n ), where n is the number of datanodes. This
makes the cost of block placement to be O(n*n) when a cluster is full.
> I propose to change the data structure of the excluded node list as a HashMap. So in
average, the cost of insertion is O(1) and the cost of query is O(1). This makes the block
placement algorithm to be O( n ) in average.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message