hadoop-common-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Inigo Goiri (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HADOOP-12185) NetworkTopology is not efficient adding/getting/removing nodes
Date Sun, 05 Jul 2015 22:13:04 GMT

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

Inigo Goiri commented on HADOOP-12185:
--------------------------------------

I've implemented it with only Map and there is one operation that gets much more expensive:
chooseRandom(). Right now, picking a random node is done selecting a random index in the list
of children which is O(k); however, the same operation is O(n) for HashMap. I thought about
using TreeMap or LinkedHashMap but both of them have the same issue to some degree.

Given that chooseRandom() is one of the most commonly used operations (e.g., block placement
in HDFS), I would stick to the addition of the auxiliary map. To speedup chooseRamdom (which
uses indexOf heavily) we can replace my proposed HashMap<String,Node> by HashMap<String,Integer>.
I'm going to do some performance analysis to see what's better.

> NetworkTopology is not efficient adding/getting/removing nodes
> --------------------------------------------------------------
>
>                 Key: HADOOP-12185
>                 URL: https://issues.apache.org/jira/browse/HADOOP-12185
>             Project: Hadoop Common
>          Issue Type: Improvement
>    Affects Versions: 2.7.0
>            Reporter: Inigo Goiri
>            Assignee: Inigo Goiri
>         Attachments: HADOOP-12185-1.patch
>
>
> NetworkToplogy uses nodes with a list of children. The access to these children is slow
as it's a linear search.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message