[
https://issues.apache.org/jira/browse/HADOOP-5638?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Hairong Kuang updated HADOOP-5638:
----------------------------------
Status: Open (was: Patch Available)
> 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.
