Uploaded image for project: 'Hadoop Common'
  1. Hadoop Common
  2. HADOOP-5638

More improvement on block placement performance

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: 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.

        Attachments

        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

              People

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

                Dates

                • Created:
                  Updated:
                  Resolved: