Hadoop Common
  1. Hadoop Common
  2. HADOOP-5638

More improvement on block placement performance

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.21.0
    • Component/s: None
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      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.

      1. excludedList4.patch
        15 kB
        Hairong Kuang
      2. excludedList3.patch
        12 kB
        Hairong Kuang
      3. excludedList2.patch
        13 kB
        Hairong Kuang
      4. excludedList1.patch
        12 kB
        Hairong Kuang
      5. excludedList.patch
        10 kB
        Hairong Kuang

        Issue Links

          Activity

          No work has yet been logged on this issue.

            People

            • Assignee:
              Hairong Kuang
              Reporter:
              Hairong Kuang
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development