[
https://issues.apache.org/jira/browse/HADOOP5638?page=com.atlassian.jira.plugin.system.issuetabpanels:alltabpanel ]
Hairong Kuang updated HADOOP5638:

Description:
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.
was:
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.
More improvement on block placement performance

Key: HADOOP5638
URL:
https://issues.apache.org/jira/browse/HADOOP5638Project: Hadoop Core
Issue Type: Improvement
Components: dfs
Reporter: Hairong Kuang
Assignee: Hairong Kuang
Fix For: 0.21.0
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.