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

          Tom White made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Owen O'Malley made changes -
          Component/s dfs [ 12310710 ]
          Hairong Kuang made changes -
          Status Patch Available [ 10002 ] Resolved [ 5 ]
          Hadoop Flags [Reviewed]
          Resolution Fixed [ 1 ]
          Hairong Kuang made changes -
          Attachment excludedList4.patch [ 12405706 ]
          Hairong Kuang made changes -
          Status Open [ 1 ] Patch Available [ 10002 ]
          Hairong Kuang made changes -
          Status Patch Available [ 10002 ] Open [ 1 ]
          Hairong Kuang made changes -
          Attachment excludedList3.patch [ 12405508 ]
          Hairong Kuang made changes -
          Status Open [ 1 ] Patch Available [ 10002 ]
          Hairong Kuang made changes -
          Status Patch Available [ 10002 ] Open [ 1 ]
          Hairong Kuang made changes -
          Attachment excludedList2.patch [ 12405099 ]
          Hairong Kuang made changes -
          Status Open [ 1 ] Patch Available [ 10002 ]
          Hairong Kuang made changes -
          Attachment excludedList1.patch [ 12405025 ]
          Hairong Kuang made changes -
          Link This issue is related to HADOOP-5603 [ HADOOP-5603 ]
          Hairong Kuang made changes -
          Attachment excludedList.patch [ 12404902 ]
          Hairong Kuang made changes -
          Field Original Value New Value
          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.
          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.
          Hairong Kuang created 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